/* Sequential list data type implemented by a binary tree.
   Copyright (C) 2006 Free Software Foundation, Inc.
   Written by Bruno Haible <bruno@clisp.org>, 2006.

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2, or (at your option)
   any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software Foundation,
   Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */

/* Common code of gl_avltree_list.c, gl_rbtree_list.c,
                  gl_avltreehash_list.c, gl_rbtreehash_list.c.  */

static gl_list_t
gl_tree_create_empty (gl_list_implementation_t implementation,
		      gl_listelement_equals_fn equals_fn,
		      gl_listelement_hashcode_fn hashcode_fn,
		      bool allow_duplicates)
{
  struct gl_list_impl *list =
    (struct gl_list_impl *) xmalloc (sizeof (struct gl_list_impl));

  list->base.vtable = implementation;
  list->base.equals_fn = equals_fn;
  list->base.hashcode_fn = hashcode_fn;
  list->base.allow_duplicates = allow_duplicates;
#if WITH_HASHTABLE
  list->table_size = 11;
  list->table =
    (gl_hash_entry_t *) xzalloc (list->table_size * sizeof (gl_hash_entry_t));
#endif
  list->root = NULL;

  return list;
}

static size_t
gl_tree_size (gl_list_t list)
{
  return (list->root != NULL ? list->root->branch_size : 0);
}

static const void *
gl_tree_node_value (gl_list_t list, gl_list_node_t node)
{
  return node->value;
}

static gl_list_node_t
gl_tree_next_node (gl_list_t list, gl_list_node_t node)
{
  if (node->right != NULL)
    {
      node = node->right;
      while (node->left != NULL)
	node = node->left;
    }
  else
    {
      while (node->parent != NULL && node->parent->right == node)
	node = node->parent;
      node = node->parent;
    }
  return node;
}

static gl_list_node_t
gl_tree_previous_node (gl_list_t list, gl_list_node_t node)
{
  if (node->left != NULL)
    {
      node = node->left;
      while (node->right != NULL)
	node = node->right;
    }
  else
    {
      while (node->parent != NULL && node->parent->left == node)
	node = node->parent;
      node = node->parent;
    }
  return node;
}

/* Return the node at the given position < gl_tree_size (list).  */
static inline gl_list_node_t
node_at (gl_list_node_t root, size_t position)
{
  /* Here we know that root != NULL.  */
  gl_list_node_t node = root;

  for (;;)
    {
      if (node->left != NULL)
	{
	  if (position < node->left->branch_size)
	    {
	      node = node->left;
	      continue;
	    }
	  position -= node->left->branch_size;
	}
      if (position == 0)
	break;
      position--;
      node = node->right;
    }
  return node;
}

static const void *
gl_tree_get_at (gl_list_t list, size_t position)
{
  gl_list_node_t node = list->root;

  if (!(node != NULL && position < node->branch_size))
    /* Invalid argument.  */
    abort ();
  node = node_at (node, position);
  return node->value;
}

static gl_list_node_t
gl_tree_set_at (gl_list_t list, size_t position, const void *elt)
{
  gl_list_node_t node = list->root;

  if (!(node != NULL && position < node->branch_size))
    /* Invalid argument.  */
    abort ();
  node = node_at (node, position);
#if WITH_HASHTABLE
  if (elt != node->value)
    {
      size_t new_hashcode =
	(list->base.hashcode_fn != NULL
	 ? list->base.hashcode_fn (elt)
	 : (size_t)(uintptr_t) elt);

      if (new_hashcode != node->h.hashcode)
	{
	  remove_from_bucket (list, node);
	  node->value = elt;
	  node->h.hashcode = new_hashcode;
	  add_to_bucket (list, node);
	}
      else
	node->value = elt;
    }
#else
  node->value = elt;
#endif
  return node;
}

#if !WITH_HASHTABLE

static gl_list_node_t
gl_tree_search (gl_list_t list, const void *elt)
{
  gl_listelement_equals_fn equals = list->base.equals_fn;
  /* Iterate across all elements.  */
  gl_list_node_t node = list->root;
  iterstack_t stack;
  iterstack_item_t *stack_ptr = &stack[0];

  for (;;)
    {
      /* Descend on left branch.  */
      for (;;)
	{
	  if (node == NULL)
	    break;
	  stack_ptr->node = node;
	  stack_ptr->rightp = false;
	  node = node->left;
	  stack_ptr++;
	}
      /* Climb up again.  */
      for (;;)
	{
	  if (stack_ptr == &stack[0])
	    return NULL;
	  stack_ptr--;
	  if (!stack_ptr->rightp)
	    break;
	}
      node = stack_ptr->node;
      /* Test against current element.  */
      if (equals != NULL ? equals (elt, node->value) : elt == node->value)
	return node;
      /* Descend on right branch.  */
      stack_ptr->rightp = true;
      node = node->right;
      stack_ptr++;
    }
}

static size_t
gl_tree_indexof (gl_list_t list, const void *elt)
{
  gl_listelement_equals_fn equals = list->base.equals_fn;
  /* Iterate across all elements.  */
  gl_list_node_t node = list->root;
  iterstack_t stack;
  iterstack_item_t *stack_ptr = &stack[0];
  size_t index = 0;

  for (;;)
    {
      /* Descend on left branch.  */
      for (;;)
	{
	  if (node == NULL)
	    break;
	  stack_ptr->node = node;
	  stack_ptr->rightp = false;
	  node = node->left;
	  stack_ptr++;
	}
      /* Climb up again.  */
      for (;;)
	{
	  if (stack_ptr == &stack[0])
	    return (size_t)(-1);
	  stack_ptr--;
	  if (!stack_ptr->rightp)
	    break;
	}
      node = stack_ptr->node;
      /* Test against current element.  */
      if (equals != NULL ? equals (elt, node->value) : elt == node->value)
	return index;
      index++;
      /* Descend on right branch.  */
      stack_ptr->rightp = true;
      node = node->right;
      stack_ptr++;
    }
}

#endif

static gl_list_node_t
gl_tree_add_at (gl_list_t list, size_t position, const void *elt)
{
  size_t count = (list->root != NULL ? list->root->branch_size : 0);

  if (!(position <= count))
    /* Invalid argument.  */
    abort ();
  if (position == count)
    return gl_tree_add_last (list, elt);
  else
    return gl_tree_add_before (list, node_at (list->root, position), elt);
}

static bool
gl_tree_remove_at (gl_list_t list, size_t position)
{
  gl_list_node_t node = list->root;

  if (!(node != NULL && position < node->branch_size))
    /* Invalid argument.  */
    abort ();
  node = node_at (node, position);
  return gl_tree_remove_node (list, node);
}

static bool
gl_tree_remove (gl_list_t list, const void *elt)
{
  gl_list_node_t node = gl_tree_search (list, elt);

  if (node != NULL)
    return gl_tree_remove_node (list, node);
  else
    return false;
}

#if !WITH_HASHTABLE

static void
gl_tree_list_free (gl_list_t list)
{
  /* Iterate across all elements in post-order.  */
  gl_list_node_t node = list->root;
  iterstack_t stack;
  iterstack_item_t *stack_ptr = &stack[0];

  for (;;)
    {
      /* Descend on left branch.  */
      for (;;)
	{
	  if (node == NULL)
	    break;
	  stack_ptr->node = node;
	  stack_ptr->rightp = false;
	  node = node->left;
	  stack_ptr++;
	}
      /* Climb up again.  */
      for (;;)
	{
	  if (stack_ptr == &stack[0])
	    goto done_iterate;
	  stack_ptr--;
	  node = stack_ptr->node;
	  if (!stack_ptr->rightp)
	    break;
	  /* Free the current node.  */
	  free (node);
	}
      /* Descend on right branch.  */
      stack_ptr->rightp = true;
      node = node->right;
      stack_ptr++;
    }
 done_iterate:
  free (list);
}

#endif

/* --------------------- gl_list_iterator_t Data Type --------------------- */

static gl_list_iterator_t
gl_tree_iterator (gl_list_t list)
{
  gl_list_iterator_t result;
  gl_list_node_t node;

  result.vtable = list->base.vtable;
  result.list = list;
  /* Start node is the leftmost node.  */
  node = list->root;
  if (node != NULL)
    while (node->left != NULL)
      node = node->left;
  result.p = node;
  /* End point is past the rightmost node.  */
  result.q = NULL;
#ifdef lint
  result.i = 0;
  result.j = 0;
  result.count = 0;
#endif

  return result;
}

static gl_list_iterator_t
gl_tree_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index)
{
  size_t count = (list->root != NULL ? list->root->branch_size : 0);
  gl_list_iterator_t result;

  if (!(start_index <= end_index && end_index <= count))
    /* Invalid arguments.  */
    abort ();
  result.vtable = list->base.vtable;
  result.list = list;
  /* Start node is the node at position start_index.  */
  result.p = (start_index < count ? node_at (list->root, start_index) : NULL);
  /* End point is the node at position end_index.  */
  result.q = (end_index < count ? node_at (list->root, end_index) : NULL);
#ifdef lint
  result.i = 0;
  result.j = 0;
  result.count = 0;
#endif

  return result;
}

static bool
gl_tree_iterator_next (gl_list_iterator_t *iterator,
		       const void **eltp, gl_list_node_t *nodep)
{
  if (iterator->p != iterator->q)
    {
      gl_list_node_t node = (gl_list_node_t) iterator->p;
      *eltp = node->value;
      if (nodep != NULL)
	*nodep = node;
      /* Advance to the next node.  */
      if (node->right != NULL)
	{
	  node = node->right;
	  while (node->left != NULL)
	    node = node->left;
	}
      else
	{
	  while (node->parent != NULL && node->parent->right == node)
	    node = node->parent;
	  node = node->parent;
	}
      iterator->p = node;
      return true;
    }
  else
    return false;
}

static void
gl_tree_iterator_free (gl_list_iterator_t *iterator)
{
}

/* ---------------------- Sorted gl_list_t Data Type ---------------------- */

static gl_list_node_t
gl_tree_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
			   const void *elt)
{
  gl_list_node_t node;

  for (node = list->root; node != NULL; )
    {
      int cmp = compar (node->value, elt);

      if (cmp < 0)
	node = node->right;
      else if (cmp > 0)
	node = node->left;
      else /* cmp == 0 */
	{
	  /* We have an element equal to ELT.  But we need the leftmost such
	     element.  */
	  gl_list_node_t found = node;
	  node = node->left;
	  for (; node != NULL; )
	    {
	      int cmp2 = compar (node->value, elt);

	      if (cmp2 < 0)
		node = node->right;
	      else if (cmp2 > 0)
		/* The list was not sorted.  */
		abort ();
	      else /* cmp2 == 0 */
		{
		  found = node;
		  node = node->left;
		}
	    }
	  return found;
	}
    }
  return NULL;
}

static size_t
gl_tree_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
			    const void *elt)
{
  gl_list_node_t node;
  size_t position;

  for (node = list->root, position = 0; node != NULL; )
    {
      int cmp = compar (node->value, elt);

      if (cmp < 0)
	{
	  if (node->left != NULL)
	    position += node->left->branch_size;
	  position++;
	  node = node->right;
	}
      else if (cmp > 0)
	node = node->left;
      else /* cmp == 0 */
	{
	  /* We have an element equal to ELT.  But we need the leftmost such
	     element.  */
	  size_t found_position =
	    position + (node->left != NULL ? node->left->branch_size : 0);
	  node = node->left;
	  for (; node != NULL; )
	    {
	      int cmp2 = compar (node->value, elt);

	      if (cmp2 < 0)
		{
		  if (node->left != NULL)
		    position += node->left->branch_size;
		  position++;
		  node = node->right;
		}
	      else if (cmp2 > 0)
		/* The list was not sorted.  */
		abort ();
	      else /* cmp2 == 0 */
		{
		  found_position =
		    position
		    + (node->left != NULL ? node->left->branch_size : 0);
		  node = node->left;
		}
	    }
	  return found_position;
	}
    }
  return (size_t)(-1);
}

static gl_list_node_t
gl_tree_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar,
			const void *elt)
{
  gl_list_node_t node = list->root;

  if (node == NULL)
    return gl_tree_add_first (list, elt);

  for (;;)
    {
      int cmp = compar (node->value, elt);

      if (cmp < 0)
	{
	  if (node->right == NULL)
	    return gl_tree_add_after (list, node, elt);
	  node = node->right;
	}
      else if (cmp > 0)
	{
	  if (node->left == NULL)
	    return gl_tree_add_before (list, node, elt);
	  node = node->left;
	}
      else /* cmp == 0 */
	return gl_tree_add_before (list, node, elt);
    }
}

static bool
gl_tree_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar,
			   const void *elt)
{
  gl_list_node_t node = gl_tree_sortedlist_search (list, compar, elt);
  if (node != NULL)
    return gl_tree_remove_node (list, node);
  else
    return false;
}