/**
 * Puts a new node containing i at the appropriate position in a list
 * sorted in ascending order.
 */
void insert_sorted(int i)
{
    // initalize new node 
    node* new_node = create_node();

    // set new node's i value
    new_node->i = i;

    // set new node's next value to NULL
    new_node->next = NULL;

    // check if list is empty
    if (first == NULL)
        first = new_node;

    // then check if i belongs at beginning of list
    else if (new_node->i < first->i)
    {
        new_node->next = first;
        first = new_node;
    }

    // else check if i belongs at end or middle of the list
    else
    {
        // initialize pred_node with same value's as first node's 
        node* pred_node = first;

        while (true)
        {
            // check for insertion at end of list
            if (pred_node->next == NULL)
            {
                pred_node->next = new_node;
                break;
            }

            // check for insertion in the middle of the list
            else if (pred_node->next->i > new_node->i)
            {
                new_node->next = pred_node->next;
                pred_node->next = new_node;
                break;
            }

            // in each loop, set pred_node to the next node in the linked list
            pred_node = pred_node->next;
        } 
    }
}

void LinkedList::add_at_n (int data,int n)
{
	node *temp = create_node(data);
	node *temp2 = head;
	for(int i=0; i< n-2;i++)
	{
		temp2 = (*temp2).link;

	}
	node* temp3 = (*temp2).link;
	(*temp2).link = temp;
	(*temp).link = temp3;

}

/** push_back
  *
  * Adds the data to the back/end of the linked list
  *
  * @param llist a pointer to the list.
  * @param data pointer to data the user wants to store in the list.
  */
void push_back(list* llist, void* data)
{
    node *newTail = create_node(data);
    if (llist->size == 0) {
      llist->head = newTail;
      llist->tail = newTail;
    } else {
      node *oldTail = llist->tail;
      oldTail->next = newTail;
      llist->tail = newTail;
      newTail->prev = oldTail;
    }
    llist->size++;
}

int main(int argc,char* argv[])
{
		struct node *first = NULL;
		struct node *last = NULL;
		struct node *p = NULL;

		if ( (first = create_node()) == NULL )
		{
				return 0;
		}

		if ( (first = add_to_node( first, 0)) == NULL )
		{
				printf("add false!\n"); 
		}
		last = first;

		if ( (first = add_to_node( first, 0)) == NULL )
		{
				printf("add false!\n"); 
		}

		if ( (first = add_to_node( first, 1)) == NULL )
		{
				printf("add false!\n"); 
		}

		if ( (first = add_to_node( first, 2)) == NULL )
		{
				printf("add false!\n"); 
		}

		if ( (first = add_to_node( first, 3)) == NULL )
		{
				printf("add false!\n"); 
		}

		first = delete_node(first);

		
		show(first);
		
		printf("\b\n");
		
		show(last);

		printf("\b\n");

		return 0;
}

//creates a bst with the minimum height
bst* createMinBST(int a[], int start, int end){
  
 
  if (start > end)
    return NULL;

  int middle = (start+end)/2;
  bst* root = create_node(a[middle]);
  root->left = createMinBST(a, start, middle-1);
  root->right = createMinBST(a, middle + 1, end);

  return root;

}

t_cmd	*create_last_node(char *str, int **occ)
{
    t_cmd	*node;
    int		cmd_len;

    node = NULL;
    if (str)
    {
        cmd_len = ft_strlen(str);
        node = create_node(str, NULL);
        (*occ)++;
    }
    return (node);
}

/**
 * Puts a new node containing i at the front (head) of the list.
 */
void prepend(int i)
{
    // initalize new node 
    node* new_node = create_node();

    // set new node's i value
    new_node->i = i;

    // set new node's next pointer to first node in list
    new_node->next = first;

    // new node now becomes first/front/head node in list  
    first = new_node;
}

Node * merge_two(Node * head)
{//merge the last two nodes in the list into one tree node
	if (head -> next -> next == NULL)
	{//we are at the left child to merge, head -> next is the right child
		Node * newParent = create_node(0);
		newParent -> left = head;
		newParent -> right = head -> next;
		newParent -> left -> next = NULL;
		return (newParent);
	}
	//head -> next becomes the new parent
	head -> next = merge_two(head -> next);
	return (head);
}

void init(const char *s)
{
  int  i;
  int  freq[128] = {0};
  char cxt[16];

  while (*s) {
    freq[(int)*s]++;
    s++;
  }

  for (i = 0; i < 128; i++) {
    if (freq[i]) {
      insert(create_node(freq[i], i, 0, 0));
    }
  }

  while (tail > 2) {
    insert(create_node(0, 0, pop(), pop()));
  }

  prepare(tree[1], cxt, 0);
}

errcode_t setup_tree(root_t **roots, const char *word)
{
	root_t *root;
	node_t *p;
	int len, i, idx;
	char c;

	len = strlen(word);

	assert(roots && word && len > 0);

	if ((c = to_lowercase(word[0])) < 0) {
		return 0;
	}

	idx = c - 'a';
	root = roots[idx];

	for (i = 1, p = root->n; i < len; i++) {
		/* Illegal word, skip it, resulting in leaf node's cnt == 0 */
		if ((c = to_lowercase(word[i])) < 0) {
			return 0;
		}

		idx = c - 'a';

		if (p->children[idx] != NULL) {
			p = p->children[idx];
			continue;
		}

		pthread_mutex_lock(&root->mutex);
		if (!p->children[idx]) {
			if (!(p->children[idx] = create_node(c))) {
				pthread_mutex_unlock(&root->mutex);
				return ERR_NO_MEM;
			}
		}
		pthread_mutex_unlock(&root->mutex);

		p = p->children[idx];
	}

	/* update counter on the leaf node */
	pthread_mutex_lock(&root->mutex);
	p->cnt++;
	pthread_mutex_unlock(&root->mutex);

	return 0;
}

/**
 * Puts a new node containing i at the end (tail) of the list.
 */
void append(int i)
{
    // initalize new node 
    node* new_node = create_node();

    // set new node's i value
    new_node->i = i;

    // set new node's next value to NULL
    new_node->next = NULL;

    // insert node immediately following previous node
    insert_node(new_node);
}

Node* Parser::parse_expression()
{ // expects TOKEN_INTEGER, TOKEN_WORD or TOKEN_OPENING_PAREN as current token
	Node *node = create_node(NODE_EXPRESSION);

	if (_current->kind == TOKEN_INTEGER) {
		Node *node_const = create_node(NODE_CONSTANT);
		node_const->constant_number = _current->integer;
		node->next.push_back(node_const);
	} else if (_current->kind == TOKEN_WORD) {
		Node *node_word = create_node(NODE_WORD);
		node_word->word_word = _current->word;
		node->next.push_back(node_word);
	} else if (_current->kind == TOKEN_OPENING_PAREN) {
		node->next.push_back(parse_function_call());
	} else {
		printf("Error: unknown expression: ");
		_current->print();
	}

	next_token();

	return node;
}

/** push_back
  *
  * Adds the data to the back/end of the linked list
  *
  * @param llist a pointer to the list.
  * @param data pointer to data the user wants to store in the list.
  */
void push_back(list* llist, void* data)
{
	node* add_node = create_node(data);

	if(llist->head == NULL && llist->tail == NULL){
		llist->head = add_node;
		llist->tail = add_node;
	} else{
		add_node->prev = llist->tail;	
		llist->tail->next = add_node;	
		llist->tail = add_node;
	}
	llist->size += 1;
}

Node * addNode(Node *node, int value){
        if(node == NULL){
                return create_node(value);
        }
        else{
          if (node->value > value){
                node->left = addNode(node->left, value);
          }
          else{
                node->right = addNode(node->right, value);
          }
        }
        return node;
}

void add_iterative(struct linkedlist* l, int x)
  //@ requires list(l, ?vs);
  //@ ensures list(l, append(vs, cons(x, nil)));
{
  //@ open list(l, vs);
  if(l->head == 0) {
    struct node* n = create_node(0, x);
    l->head = n;
    //@ open lseg(0, 0, _);
    //@ close lseg(0, 0, _);
    //@ close lseg(n, 0, cons(x, nil));
    //@ close list(l, append(vs, cons(x, nil)));
  } else {
    struct node* head = l->head;
    struct node* current = l->head;
    //@ close lseg(head, head, nil);
    //@ open lseg(head, 0, vs);
    while(current->next != 0) 
      //@ invariant current!= 0 &*& lseg(head, current, ?vs1) &*& current->value |-> ?v &*& current->next |-> ?n &*& malloc_block_node(current) &*& lseg(n, 0, ?vs2) &*& vs == append(vs1, cons(v, vs2));
    {
      //@ open lseg(n, 0, _);
      struct node* oldcurrent = current;
      current = current->next;
      //@ appendlemma(head, oldcurrent);
      //@ appendlemma2(vs1, v, vs2);
    }
    //@ open lseg(0, 0, _);
    struct node* nn = create_node(0, x);
    current->next = nn;
    //@ close lseg(0, 0, nil);
    //@ close lseg(nn, 0, _);
    //@ close lseg(current, 0, _);
    //@ appendlemma3(head, current);
    //@ appendlemma2(vs1, v, cons(x, nil));
    //@ close list(l, append(vs, cons(x, nil)));
  }
}

node *unbalanced_binary_tree_2() {
    node *node_pointer = create_node();
    node_pointer->left = create_node();
    node_pointer->right = create_node();
    node_pointer->right->left = create_node();
    node_pointer->right->left->left = create_node();
    node_pointer->right->right = create_node();
    return node_pointer;
}

int dictionary_insert(struct dictionary *dict, const wchar_t *word)
{
	assert(dict != NULL);
	struct dictionary *node = NULL;

	/* Pierwsze slowo */
	if (dict->children_size == 0)
	{
		for(node = dict; *word; node = *node->children)
		{
			put_child(node, create_node(*word));
			word++;
		}
		put_child(node, create_node(NULL_MARKER));
		return 1;
	}
	node = dict;
	struct dictionary *found = NULL;
	while (find_child(node, &found, *word) && *word)
	{
		node = found;
		word++;
	}
	if (*word == L'\0')
	{
		if (find_child(node, &found, NULL_MARKER))
			return 0;
		put_child(node, create_node(NULL_MARKER));
	}
	else
	{
		struct dictionary *tmp = create_node(*word);
		put_child(node, tmp);
		dictionary_insert(tmp, ++word);
	}
	return 1;
}

void CGI_write_zboco(double parent_id, cgns_zboco *zboco) {
    int n;

    if (zboco->link && keep_links) {
        create_node (zboco->id, parent_id, 0);
        return;
    }

    /* ZoneBC_t */
    if (cgi_new_node(parent_id, "ZoneBC", "ZoneBC_t", &zboco->id,
        "MT", 0, 0, 0)) error_exit (NULL, 0);

    /* BC_t */
    for (n=0; n<zboco->nbocos; n++)
        CGI_write_boco (zboco->id, &zboco->boco[n]);

    /* Descriptor_t */
    for (n=0; n<zboco->ndescr; n++)
        create_node (zboco->descr[n].id, zboco->id, 1);

    /* ReferenceState_t */
    if (zboco->state) create_node (zboco->state->id, zboco->id, 1);

    /* DataClass_t */
    if (zboco->data_class &&
        cgi_write_dataclass (zboco->id, zboco->data_class))
        error_exit (NULL, 0);

    /* DimensionalUnits_t */
    if (zboco->units) create_node (zboco->units->id, zboco->id, 1);

    if (keep_nodes || FileVersion >= 2100) {
        /* UserDefinedData_t */
        for (n=0; n<zboco->nuser_data; n++)
            create_node (zboco->user_data[n].id, zboco->id, 1);
    }
}

/*
 * Insert an item to the tree.
 * Return 0 if a new node was created, 1 if a node was updated, or -1 on error.
 */
int
mtree_trie_insert(struct mtree_trie *trie, const char *key, void *item)
{
	struct mtree_trie	*u;
	struct mtree_trie	*node;
	size_t			 bit;

	assert(trie != NULL);
	assert(item != NULL);
	assert(key != NULL && *key != '\0');

	u = find_node(trie, key);
	if (u != NULL && strcmp(u->key, key) == 0) {
		/*
		 * Already in the trie, just update the item.
		 */
		u->item = item;
		return (1);
	}
	if ((node = create_node(key, item)) == NULL)
		return (-1);

	if (u == NULL) {
		/*
		 * Trie is empty, insert to the left under the head.
		 */
		for (bit = 0; KEY_BIT(key, node->key_len, bit) == 0; bit++)
			;
		node->bit   = bit;
		node->left  = trie;
		node->right = node;
		trie->left  = node;
	} else {
		for (bit = 0;; bit++) {
			int kbit = KEY_BIT(key, node->key_len, bit);

			if (kbit != KEY_BIT(u->key, u->key_len, bit)) {
				if (kbit == 0)
					node->right = NULL;
				else
					node->left = NULL;
				node->bit = bit;
				break;
			}
		}
		trie->left = insert_node(trie->left, node, trie);
	}
	return (0);
}

int 
main()
{
	struct Tnode   *root = NULL, *node;
	int		key       , ival, *sum, ssum = 0;
	sum = &ssum;
	do {
		printf("\n[1] Insert value");
		printf("\n[2] Left Branch Sum ");
		printf("\n[3] Right Branch Sum ");
		printf("\n[4] Exit ");
		printf("\nEnter the input key : ");
		scanf("%d", &key);
		switch (key) {
		case 1:
			printf("\n Enter the value to be inserted :");
			scanf("%d", &ival);
			if (create_node(ival, &node))
				insert_node(&root, &node);
			else
				printf("\n Memory is Full !! ");
			break;
		case 2:
			*sum = 0;
			if (root != NULL) {
				branchsum(&(root->left), &sum);
				printf("\n Left Branch Sum = %d", *sum);
			} else
				printf("\n Enter some value in tree");
			break;
		case 3:
			*sum = 0;
			if (root != NULL) {
				branchsum(&(root->right), &sum);
				printf("\n Right Branch Sum = %d", *sum);
			} else
				printf("\n Enter some value in tree");
			break;
		case 4:
			break;
		default:
			printf("\t Enter the Correct key !!!!! ");
			break;
		}
	} while (key != 4);

	printf("\n Thank you for using codingstreet.com 's datastructure solution ");
	return 0;
}