// removes the first node, then removes all nodes
// that are multiples of the first node and then
// returns that first node
int LList :: remove_mult () {
	LList_Node * current_node = head -> next;
	int result = remove_node ();

	for (int i = 0; i < size; i++) {
		if (current_node -> get_value () % result == 0) {
			remove_node (i);
		}

		current_node = current_node -> next;
	}

	return result;
}

int main()
{
    int i;
    double a[] = { 0.0, 1.0, 2.0, 3.0 };
    int n = sizeof(a) / sizeof(a[0]);

    // An initially empty list.
    struct Node *list = NULL;

    // Insert the first node.
    list = insert(NULL, a[0]);

    // Then we use insert() to successively append to the list.
    struct Node *node = list;
    for (i = 1; i < n; i++) {
        node = insert(node, a[i]);
    }
    print("original list", list);

    // test find() function
    assert(find(list, 0.0) == list);
    assert(find(list, 1.0) == list->next);
    assert(find(list, 2.0) == list->next->next);
    assert(find(list, 3.0) == list->next->next->next);
    assert(find(list, 2.1) == NULL);

    // insert 2.1 right after 2.0
    node = find(list, 2.0);
    node = insert(node, 2.1);
    assert(node->next->data == 3.0);
    print("inserted 2.1", list);

    // remove in this order: 2.1, 0.0, 3.0, 1.0, 2.0
    i = remove_node(&list, 2.1); print("removed 2.1", list); assert(i==1);
    i = remove_node(&list, 0.0); print("removed 0.0", list); assert(i==1);
    i = remove_node(&list, 3.0); print("removed 3.0", list); assert(i==1);
    i = remove_node(&list, 1.0); print("removed 1.0", list); assert(i==1);
    i = remove_node(&list, 2.0); print("removed 2.0", list); assert(i==1);
    assert(list == NULL);

    // Something to think about:
    //
    // Could we have implemented remove_node() so that you can pass 
    // the result of find(), i.e., remove_node(find(2.0)) for example?
    //
    // If not, how can we modify our list structure to make it work?

    return 0;
}

static
struct node *
remove_node(struct node *n, double v)
{
	if (n == NULL) {
		return NULL;
	} else if (n->data == v) {
		struct node *next = n->next;
		free(n);
		return remove_node(next, v);
	} else {
		n->next = remove_node(n->next, v);
		return n;
	}
}

LinkedList remove_tail(LinkedList _ll) {
    if (is_empty(_ll) == FALSE) {
        if (_ll->next != NULL) {
            Node* tmp = _ll;
            while (tmp->next->next != NULL) {
                tmp = tmp->next;
            }
            remove_node(tmp->next);
            tmp->next = NULL;
            return _ll;
        }
        _ll = remove_node(_ll);
        return _ll;
    } else return;
}

int main(void) {
	node* head = initialize();
	show(head); // 0 1 2 3 3 4 5

	remove_node(&head, 3);
	show(head);  // 0 1 2 4 5

	remove_node(&head, 0);
	show(head);  // 1 2 4 5

	remove_node(&head, 7);
	show(head);  // 1 2 4 5

	return 0;
}

int main()
{
	initialize();

	int n, m, idx = 0;
	scanf("%d %d", &n, &m);
	
	for (int i = 1; i <= n; i++)
		insert(i);

	node_t *tmp = head;
	while (!is_empty())
	{
		for (int i = 0; i < m; i++)
		{
			tmp = tmp->next;
			if (tmp == tail)
				tmp = head->next;
		}
		seq[idx++] = tmp->num;
		node_t *tmp2 = tmp->prev;
		remove_node(tmp);
		tmp = tmp2;
	}

	printf("<");
	for (int i = 0; i < idx - 1; i++)
		printf("%d, ", seq[i]);
	printf("%d>\n", seq[idx - 1]);

	terminate();
	return 0;
}

int start(){

	struct node *head;
	head = (struct node*) malloc(sizeof(struct node));
	head->next = NULL;
	head->payload = 0;
	head->id = 0;

	int selection = 0;

	do{
		selection = menu();
		switch(selection){
			case 1:
					add_node(head);
					break;
			case 2:
					remove_node(head);
					break;
			case 3:
					view_list(head);
					break;
			case 4:
					break;
			case 0:
					break;
			default:
					break;
		}

	}while(selection != 0);

	return 0;
}

void remove_dups(Node* tip) {
    Node* n = tip;
    Node* dups = NULL;
    Node* prev = NULL;
    print_list(n);

    while(n != NULL) {
        Node* next = n->next;
        Node* prev = n;
        while(next != NULL) {
            if(n->data == next->data) {
                //found a dup
                prev->next = next->next;
                next = prev->next;
            } else {
                prev = next;
                next = next->next;
            }
        } 
        n = n->next;
    }

    print_list(dups);

    n = dups;
    while(n != NULL) {
        Node* next = n->next;
        remove_node(tip, n);
    }
    print_list(tip);

}

linked_list* merge_paths(linked_list* elist, linked_list* vlist)
{
   list_node* enode;
   list_node* vnode;
   char* vpath;

   if (elist && vlist)
   {
      for (vnode = list_tail(vlist) ; vnode ; vnode = previous(vnode))
      {
	 vpath = (char*) get_value(vnode);

	 for (enode = head(elist) ; enode ; enode = next(enode))
	    if (!strcmp(vpath, (char*) get_value(enode)))
	    {
	       remove_node(elist, enode, 0);
	       break;
	    }

	 add_to_head(elist, get_value(vnode));
      }
   }
   else if (vlist && head(vlist))
   {
      return(vlist);
   }

   return(elist);
}

int main()
{
	nAryTree tree;

	int root = 0;

	initializeTree(&tree, sizeof(int), &root);

	int infoChild = 1;
	add_child(&tree, &root, &infoChild, compare_int);

	infoChild = 2;
	add_child(&tree, &root, &infoChild, compare_int);

	infoChild = 3;
	add_child(&tree, &root, &infoChild, compare_int);
	
    root = 2;
    infoChild = 4;
    add_child(&tree, &root, &infoChild, compare_int);

	print_pre_order(&tree, print_integer);
    printf("\n");
    int nodeThatShallBeRemoved = 1;
	
	Node removed;
	
	remove_node(&tree,&nodeThatShallBeRemoved,&removed, compare_int);

    print_pre_order(&tree, print_integer);

	return 0;
}

/**********************************************************
 * Finds first fit
 * Goto each head pointer in the separated list and find
 * a free block
 * RETURN null if not found
 **********************************************************/
void* search_node (size_t req_size)
{
    PRINTDBG (("Searching: %ld\n", req_size));

    int sl_index = 0, i;
    for(i = 0; i < NUM_SEG_LIST; i++) {
        if (req_size >= SEG_SIZES[i])
            sl_index = i;
        else
            break;
    }

    while (sl_index < NUM_SEG_LIST) {
        dlist *current = (dlist*)sep_list_head[sl_index];
            if (current != NULL) {
                if(req_size <= GET_SIZE(HDRP((void*)current))) {
                    remove_node(sl_index, (void*)current);
                    return (void*)current;
                }
                // else {
                //     return search_full(sl_index+1, req_size);
                // }
            }
        sl_index++;
    }
    return NULL;
}

void test_remove_non_existent(void){
	linked_list * head = NULL;
	head = append(head, 10);
	display(head);
	head = remove_node(head, 0);
	display(head);
}

void test_remove_from_empty(void){
	linked_list * head = NULL;
	head = remove_node(head, 10);
	display(head);
	head = append(head, 10);
	display(head);
}

// Desc : Remove a employee from list
// Params : head - The head node of list
// Return : None
void remove_employee(Node *head)
{
  Node* node;
  char emp_no[7];

  if(head->next == NULL)
  {
    printf("\n:: There is no employee!\n");
    return;
  }

  sort_list(head);
  print_list(head);

  printf("\n> Employee Number : ");
  gets(emp_no);
  fflush(stdin);

  node = find_node(head, emp_no);
  if(node)
  {
    remove_node(head, node);
    printf(":: Success!\n");
  }else{
    printf(":: The employee number does not exist!\n");
  }
}

/*
 * Removes the 1st node containing x from the list, *listPtr.
 * Returns 1 if a node is removed, 0 otherwise.
 *
 * Note that a pointer to a list (rather than a list) is passed in
 * so that the caller's list can be modified if the head node gets 
 * removed.
 */
int remove_node(struct Node **listPtr, double x)
{
    // check for NULL pointer or empty list, 
    // in which cases we simply return 0;
    if (listPtr && *listPtr) {

        // currentNode is the node we are looking at.
        struct Node *currentNode = *listPtr;

        if (currentNode->data == x) {

            // The data matches x; let's remove the currentNode.
            // We modify the caller's list by changing *listPtr.
            // Note that "currentNode = currentNode->next" won't work
            // because currentNode is just a local variable.
            *listPtr = currentNode->next;

            // deallocate the currentNode and return 1.
            free(currentNode);
            return 1;

        } else {

            // The data does not match. Recursively call remove_node()
            // again with the list starting from the 2nd element.
            return remove_node(&currentNode->next, x);
        }
    }

    return 0;
}

//remove the last node just before the tail.
__EXTERN_API__ void *link_list_remove_last( friso_link_t link ) {
	if ( link->size > 0 ) {
		return remove_node( link, link->tail->prev );
	}

	return NULL;
}

int read_node_content(c_list *list, char *index, char *content, unsigned int *len){
	if(!list)
		return -1;
	
	pthread_rwlock_rdlock((list->lock));
	
	c_node *tmp = search_node(list, index);
	
	if(!tmp)
	{
		pthread_rwlock_unlock((list->lock));
		return -1;
	}
	
	*len = tmp->length;
	memcpy(content, tmp->content,*len);
	
	pthread_rwlock_unlock((list->lock));
	
	pthread_rwlock_wrlock((list->lock));
	add_node(remove_node(index, list), list);
	pthread_rwlock_unlock((list->lock));
	
	return 0;
}

// Removes a node at index and returns the value of the node
int LList :: remove_node (int index) {
	int result = 0;

	if (index == 0) {
		result = remove_node ();
	} else if (index > 0 && index < size) {
		LList_Node * current_node = head;
		LList_Node * next_node;

		for (int i = 0; i < index - 1; i++) {
			current_node = current_node -> next;
		}

		next_node = current_node -> next;
		current_node -> next = next_node -> next;

		result = next_node -> get_value ();
		delete (next_node);
		size--;

	} else if (index >= size){
		perror ("LList:remove_node error - index is greater than size");
	} else {
		perror ("LList:remove_node error - unknown error");
	}

	return result;
}

void* fair_sequencing(void* t)
{
  while(1)
  {
    pthread_mutex_lock(&me_mutex); //so we can't enter here until I know who I am
    pthread_mutex_unlock(&me_mutex);
    pthread_mutex_lock(&dump_backlog_mutex);
    if(DUMP_BACKLOG)
    {
      dump_backlog();
      DUMP_BACKLOG = FALSE;
    }
    pthread_mutex_unlock(&dump_backlog_mutex);
    pthread_mutex_lock(&CLIENTS->mutex);
    node_t* curr = CLIENTS->head;
    while(me->isleader && curr != NULL && DUMP_BACKLOG == FALSE)
    {
      client_t* client = (client_t*)curr->elem;
      if(client->unseq_chat_msgs->head != NULL)
      {
	assign_sequence((chatmessage_t*)client->unseq_chat_msgs->head->elem);
	remove_node(client->unseq_chat_msgs,client->unseq_chat_msgs->head);
      }
      curr = curr->next;
    }
    pthread_mutex_unlock(&CLIENTS->mutex);

    usleep(FAIR_SEQ_WAIT);
  }

  pthread_exit((void *)t);
}

/*
 * remove_node_at()
 *
 * Removes a node at a specified location, and returns a pointer to the data
 * from the removed node
 *
 * Precondition: pos <= length(list), and head is not null
 * Postcondition: A pointer to the data is returned
 *
 * @param head - A double pointer to the head of the list
 * @param pos - The position of the node to remove
 * @return void* - A pointer to the data of the removed node
 */
void* remove_node_at(t_node** head, unsigned int pos)
{
    t_node* prev;
    t_node* nextNode;
    void* returnElem = NULL;

    if(head != NULL)
    {
        if(pos == 0)
            returnElem = remove_node(head);
        else
        {
            nextNode = (*head)->next;

            while(pos > 0 && nextNode != NULL)
            {
                prev = nextNode;
                nextNode = nextNode->next;
                pos--;
            }

            returnElem = prev->elem;
            prev->next = nextNode;
        }
    }

    return returnElem;
}