/*
 * frost_node.c
 *
 *  Created on: Jul 6, 2012
 *      Author: ergino
 */

#include "frost_node.h"
#include "frost_mem.h"
#include "frost_common.h"

/**
 * SECTION: trees-nary
 * @title: N-ary Trees
 * @short_description: trees of data with any number of branches
 *
 * The #FROST_Node struct and its associated functions provide a N-ary tree
 * data structure, where nodes in the tree can contain arbitrary data.
 *
 * To create a new tree use frost_node_new().
 *
 * To insert a node into a tree use frost_node_insert(),
 * frost_node_insert_before(), frost_node_append() and frost_node_prepend().
 *
 * To create a new node and insert it into a tree use
 * frost_node_insert_data(), frost_node_insert_data_before(),
 * frost_node_append_data() and frost_node_prepend_data().
 *
 * To reverse the children of a node use frost_node_reverse_children().
 *
 * To find a node use frost_node_get_root(), frost_node_find(),
 * frost_node_find_child(), frost_node_child_index(), frost_node_child_position(),
 * frost_node_first_child(), frost_node_last_child(), frost_node_nth_child(),
 * frost_node_first_sibling(), frost_node_prev_sibling(), frost_node_next_sibling()
 * or frost_node_last_sibling().
 *
 * To get information about a node or tree use FROST_NODE_IS_LEAF(),
 * FROST_NODE_IS_ROOT(), frost_node_depth(), frost_node_n_nodes(),
 * frost_node_n_children(), frost_node_is_ancestor() or frost_node_max_height().
 *
 * To traverse a tree, calling a function for each node visited in the
 * traversal, use frost_node_traverse() or frost_node_children_foreach().
 *
 * To remove a node or subtree from a tree use frost_node_unlink() or
 * frost_node_destroy().
 **/

/**
 * FROST_Node:
 * @data: contains the actual data of the node.
 * @next: points to the node's next sibling (a sibling is another
 *        #FROST_Node with the same parent).
 * @prev: points to the node's previous sibling.
 * @parent: points to the parent of the #FROST_Node, or is %NULL if the
 *          #FROST_Node is the root of the tree.
 * @children: points to the first child of the #FROST_Node.  The other
 *            children are accessed by using the @next pointer of each
 *            child.
 *
 * The #FROST_Node struct represents one node in a
 * <link linkend="glib-N-ary-Trees">N-ary Tree</link>. fields
 **/

#define frost_node_alloc0()         frost_new0 (FROST_Node, 1)
#define frost_node_free(node)       frost_free (node)

/* --- functions --- */
/**
 * frost_node_new:
 * @data: the data of the new node
 *
 * Creates a new #FROST_Node containing the given data.
 * Used to create the first node in a tree.
 *
 * Returns: a new #FROST_Node
 */
FROST_Node*
frost_node_new (frost_pointer data)
{
  FROST_Node *node = frost_node_alloc0 ();
  node->data = data;
  return node;
}

static void
frost_nodes_free (FROST_Node *node)
{
  while (node)
    {
      FROST_Node *next = node->next;
      if (node->children)
        frost_nodes_free (node->children);
      frost_node_free (node);
      node = next;
    }
}

/**
 * frost_node_destroy:
 * @root: the root of the tree/subtree to destroy
 *
 * Removes @root and its children from the tree, freeing any memory
 * allocated.
 */
void
frost_node_destroy (FROST_Node *root)
{
  frost_return_if_fail (root != NULL);

  if (!FROST_NODE_IS_ROOT (root))
    frost_node_unlink (root);

  frost_nodes_free (root);
}

/**
 * frost_node_unlink:
 * @node: the #FROST_Node to unlink, which becomes the root of a new tree
 *
 * Unlinks a #FROST_Node from a tree, resulting in two separate trees.
 */
void
frost_node_unlink (FROST_Node *node)
{
  frost_return_if_fail (node != NULL);

  if (node->prev)
    node->prev->next = node->next;
  else if (node->parent)
    node->parent->children = node->next;
  node->parent = NULL;
  if (node->next)
    {
      node->next->prev = node->prev;
      node->next = NULL;
    }
  node->prev = NULL;
}

/**
 * frost_node_copy_deep:
 * @node: a #FROST_Node
 * @copy_func: the function which is called to copy the data inside each node,
 *   or %NULL to use the original data.
 * @data: data to pass to @copy_func
 *
 * Recursively copies a #FROST_Node and its data.
 *
 * Return value: a new #FROST_Node containing copies of the data in @node.
 *
 * Since: 2.4
 **/
FROST_Node*
frost_node_copy_deep (FROST_Node     *node,
          FROSTCopyFunc  copy_func,
          frost_pointer   data)
{
  FROST_Node *new_node = NULL;

  if (copy_func == NULL)
    return frost_node_copy (node);

  if (node)
    {
      FROST_Node *child, *new_child;

      new_node = frost_node_new (copy_func (node->data, data));

      for (child = frost_node_last_child (node); child; child = child->prev)
    {
      new_child = frost_node_copy_deep (child, copy_func, data);
      frost_node_prepend (new_node, new_child);
    }
    }

  return new_node;
}

/**
 * frost_node_copy:
 * @node: a #FROST_Node
 *
 * Recursively copies a #FROST_Node (but does not deep-copy the data inside the
 * nodes, see frost_node_copy_deep() if you need that).
 *
 * Returns: a new #FROST_Node containing the same data pointers
 */
FROST_Node*
frost_node_copy (FROST_Node *node)
{
  FROST_Node *new_node = NULL;

  if (node)
    {
      FROST_Node *child;

      new_node = frost_node_new (node->data);

      for (child = frost_node_last_child (node); child; child = child->prev)
    frost_node_prepend (new_node, frost_node_copy (child));
    }

  return new_node;
}

/**
 * frost_node_insert:
 * @parent: the #FROST_Node to place @node under
 * @position: the position to place @node at, with respect to its siblings
 *     If position is -1, @node is inserted as the last child of @parent
 * @node: the #FROST_Node to insert
 *
 * Inserts a #FROST_Node beneath the parent at the given position.
 *
 * Returns: the inserted #FROST_Node
 */
FROST_Node*
frost_node_insert (FROST_Node *parent,
           frost_int   position,
           FROST_Node *node)
{
  frost_return_val_if_fail (parent != NULL, node);
  frost_return_val_if_fail (node != NULL, node);
  frost_return_val_if_fail (FROST_NODE_IS_ROOT (node), node);

  if (position > 0)
    return frost_node_insert_before (parent,
                 frost_node_nth_child (parent, position),
                 node);
  else if (position == 0)
    return frost_node_prepend (parent, node);
  else /* if (position < 0) */
    return frost_node_append (parent, node);
}

/**
 * frost_node_insert_before:
 * @parent: the #FROST_Node to place @node under
 * @sibling: the sibling #FROST_Node to place @node before.
 *     If sibling is %NULL, the node is inserted as the last child of @parent.
 * @node: the #FROST_Node to insert
 *
 * Inserts a #FROST_Node beneath the parent before the given sibling.
 *
 * Returns: the inserted #FROST_Node
 */
FROST_Node*
frost_node_insert_before (FROST_Node *parent,
              FROST_Node *sibling,
              FROST_Node *node)
{
  frost_return_val_if_fail (parent != NULL, node);
  frost_return_val_if_fail (node != NULL, node);
  frost_return_val_if_fail (FROST_NODE_IS_ROOT (node), node);
  if (sibling)
    frost_return_val_if_fail (sibling->parent == parent, node);

  node->parent = parent;

  if (sibling)
    {
      if (sibling->prev)
    {
      node->prev = sibling->prev;
      node->prev->next = node;
      node->next = sibling;
      sibling->prev = node;
    }
      else
    {
      node->parent->children = node;
      node->next = sibling;
      sibling->prev = node;
    }
    }
  else
    {
      if (parent->children)
    {
      sibling = parent->children;
      while (sibling->next)
        sibling = sibling->next;
      node->prev = sibling;
      sibling->next = node;
    }
      else
    node->parent->children = node;
    }

  return node;
}

/**
 * frost_node_insert_after:
 * @parent: the #FROST_Node to place @node under
 * @sibling: the sibling #FROST_Node to place @node after.
 *     If sibling is %NULL, the node is inserted as the first child of @parent.
 * @node: the #FROST_Node to insert
 *
 * Inserts a #FROST_Node beneath the parent after the given sibling.
 *
 * Returns: the inserted #FROST_Node
 */
FROST_Node*
frost_node_insert_after (FROST_Node *parent,
             FROST_Node *sibling,
             FROST_Node *node)
{
  frost_return_val_if_fail (parent != NULL, node);
  frost_return_val_if_fail (node != NULL, node);
  frost_return_val_if_fail (FROST_NODE_IS_ROOT (node), node);
  if (sibling)
    frost_return_val_if_fail (sibling->parent == parent, node);

  node->parent = parent;

  if (sibling)
    {
      if (sibling->next)
    {
      sibling->next->prev = node;
    }
      node->next = sibling->next;
      node->prev = sibling;
      sibling->next = node;
    }
  else
    {
      if (parent->children)
    {
      node->next = parent->children;
      parent->children->prev = node;
    }
      parent->children = node;
    }

  return node;
}

/**
 * frost_node_prepend:
 * @parent: the #FROST_Node to place the new #FROST_Node under
 * @node: the #FROST_Node to insert
 *
 * Inserts a #FROST_Node as the first child of the given parent.
 *
 * Returns: the inserted #FROST_Node
 */
FROST_Node*
frost_node_prepend (FROST_Node *parent,
        FROST_Node *node)
{
  frost_return_val_if_fail (parent != NULL, node);

  return frost_node_insert_before (parent, parent->children, node);
}

/**
 * frost_node_get_root:
 * @node: a #FROST_Node
 *
 * Gets the root of a tree.
 *
 * Returns: the root of the tree
 */
FROST_Node*
frost_node_get_root (FROST_Node *node)
{
  frost_return_val_if_fail (node != NULL, NULL);

  while (node->parent)
    node = node->parent;

  return node;
}

/**
 * frost_node_is_ancestor:
 * @node: a #FROST_Node
 * @descendant: a #FROST_Node
 *
 * Returns %frost_true if @node is an ancestor of @descendant.
 * This is true if node is the parent of @descendant,
 * or if node is the grandparent of @descendant etc.
 *
 * Returns: %frost_true if @node is an ancestor of @descendant
 */
frost_bool
frost_node_is_ancestor (FROST_Node *node,
            FROST_Node *descendant)
{
  frost_return_val_if_fail (node != NULL, frost_false);
  frost_return_val_if_fail (descendant != NULL, frost_false);

  while (descendant)
    {
      if (descendant->parent == node)
    return frost_true;

      descendant = descendant->parent;
    }

  return frost_false;
}

/**
 * frost_node_depth:
 * @node: a #FROST_Node
 *
 * Gets the depth of a #FROST_Node.
 *
 * If @node is %NULL the depth is 0. The root node has a depth of 1.
 * For the children of the root node the depth is 2. And so on.
 *
 * Returns: the depth of the #FROST_Node
 */
frost_uint
frost_node_depth (FROST_Node *node)
{
  frost_uint depth = 0;

  while (node)
    {
      depth++;
      node = node->parent;
    }

  return depth;
}

/**
 * frost_node_reverse_children:
 * @node: a #FROST_Node.
 *
 * Reverses the order of the children of a #FROST_Node.
 * (It doesn't change the order of the grandchildren.)
 */
void
frost_node_reverse_children (FROST_Node *node)
{
  FROST_Node *child;
  FROST_Node *last;

  frost_return_if_fail (node != NULL);

  child = node->children;
  last = NULL;
  while (child)
    {
      last = child;
      child = last->next;
      last->next = last->prev;
      last->prev = child;
    }
  node->children = last;
}

/**
 * frost_node_max_height:
 * @root: a #FROST_Node
 *
 * Gets the maximum height of all branches beneath a #FROST_Node.
 * This is the maximum distance from the #FROST_Node to all leaf nodes.
 *
 * If @root is %NULL, 0 is returned. If @root has no children,
 * 1 is returned. If @root has children, 2 is returned. And so on.
 *
 * Returns: the maximum height of the tree beneath @root
 */
frost_uint
frost_node_max_height (FROST_Node *root)
{
  FROST_Node *child;
  frost_uint max_height = 0;

  if (!root)
    return 0;

  child = root->children;
  while (child)
    {
      frost_uint tmp_height;

      tmp_height = frost_node_max_height (child);
      if (tmp_height > max_height)
    max_height = tmp_height;
      child = child->next;
    }

  return max_height + 1;
}

static frost_bool
frost_node_traverse_pre_order (FROST_Node        *node,
               FROSTTraverseFlags    flags,
               FROST_NodeTraverseFunc func,
               frost_pointer      data)
{
  if (node->children)
    {
      FROST_Node *child;

      if ((flags & ICE_TRAVERSE_NON_LEAFS) &&
      func (node, data))
    return frost_true;

      child = node->children;
      while (child)
    {
      FROST_Node *current;

      current = child;
      child = current->next;
      if (frost_node_traverse_pre_order (current, flags, func, data))
        return frost_true;
    }
    }
  else if ((flags & ICE_TRAVERSE_LEAFS) &&
       func (node, data))
    return frost_true;

  return frost_false;
}

static frost_bool
frost_node_depth_traverse_pre_order (FROST_Node        *node,
                 FROSTTraverseFlags    flags,
                 frost_uint         depth,
                 FROST_NodeTraverseFunc func,
                 frost_pointer      data)
{
  if (node->children)
    {
      FROST_Node *child;

      if ((flags & ICE_TRAVERSE_NON_LEAFS) &&
      func (node, data))
    return frost_true;

      depth--;
      if (!depth)
    return frost_false;

      child = node->children;
      while (child)
    {
      FROST_Node *current;

      current = child;
      child = current->next;
      if (frost_node_depth_traverse_pre_order (current, flags, depth, func, data))
        return frost_true;
    }
    }
  else if ((flags & ICE_TRAVERSE_LEAFS) &&
       func (node, data))
    return frost_true;

  return frost_false;
}

static frost_bool
frost_node_traverse_post_order (FROST_Node        *node,
                FROSTTraverseFlags    flags,
                FROST_NodeTraverseFunc func,
                frost_pointer          data)
{
  if (node->children)
    {
      FROST_Node *child;

      child = node->children;
      while (child)
    {
      FROST_Node *current;

      current = child;
      child = current->next;
      if (frost_node_traverse_post_order (current, flags, func, data))
        return frost_true;
    }

      if ((flags & ICE_TRAVERSE_NON_LEAFS) &&
      func (node, data))
    return frost_true;

    }
  else if ((flags & ICE_TRAVERSE_LEAFS) &&
       func (node, data))
    return frost_true;

  return frost_false;
}

static frost_bool
frost_node_depth_traverse_post_order (FROST_Node        *node,
                  FROSTTraverseFlags    flags,
                  frost_uint         depth,
                  FROST_NodeTraverseFunc func,
                  frost_pointer      data)
{
  if (node->children)
    {
      depth--;
      if (depth)
    {
      FROST_Node *child;

      child = node->children;
      while (child)
        {
          FROST_Node *current;

          current = child;
          child = current->next;
          if (frost_node_depth_traverse_post_order (current, flags, depth, func, data))
        return frost_true;
        }
    }

      if ((flags & ICE_TRAVERSE_NON_LEAFS) &&
      func (node, data))
    return frost_true;

    }
  else if ((flags & ICE_TRAVERSE_LEAFS) &&
       func (node, data))
    return frost_true;

  return frost_false;
}

static frost_bool
frost_node_traverse_in_order (FROST_Node        *node,
              FROSTTraverseFlags    flags,
              FROST_NodeTraverseFunc func,
              frost_pointer      data)
{
  if (node->children)
    {
      FROST_Node *child;
      FROST_Node *current;

      child = node->children;
      current = child;
      child = current->next;

      if (frost_node_traverse_in_order (current, flags, func, data))
    return frost_true;

      if ((flags & ICE_TRAVERSE_NON_LEAFS) &&
      func (node, data))
    return frost_true;

      while (child)
    {
      current = child;
      child = current->next;
      if (frost_node_traverse_in_order (current, flags, func, data))
        return frost_true;
    }
    }
  else if ((flags & ICE_TRAVERSE_LEAFS) &&
       func (node, data))
    return frost_true;

  return frost_false;
}

static frost_bool
frost_node_depth_traverse_in_order (FROST_Node        *node,
                FROSTTraverseFlags    flags,
                frost_uint         depth,
                FROST_NodeTraverseFunc func,
                frost_pointer      data)
{
  if (node->children)
    {
      depth--;
      if (depth)
    {
      FROST_Node *child;
      FROST_Node *current;

      child = node->children;
      current = child;
      child = current->next;

      if (frost_node_depth_traverse_in_order (current, flags, depth, func, data))
        return frost_true;

      if ((flags & ICE_TRAVERSE_NON_LEAFS) &&
          func (node, data))
        return frost_true;

      while (child)
        {
          current = child;
          child = current->next;
          if (frost_node_depth_traverse_in_order (current, flags, depth, func, data))
        return frost_true;
        }
    }
      else if ((flags & ICE_TRAVERSE_NON_LEAFS) &&
           func (node, data))
    return frost_true;
    }
  else if ((flags & ICE_TRAVERSE_LEAFS) &&
       func (node, data))
    return frost_true;

  return frost_false;
}

static frost_bool
frost_node_traverse_level (FROST_Node         *node,
               FROSTTraverseFlags     flags,
               frost_uint          level,
               FROST_NodeTraverseFunc  func,
               frost_pointer           data,
               frost_bool          *more_levels)
{
  if (level == 0)
    {
      if (node->children)
    {
      *more_levels = frost_true;
      return (flags & ICE_TRAVERSE_NON_LEAFS) && func (node, data);
    }
      else
    {
      return (flags & ICE_TRAVERSE_LEAFS) && func (node, data);
    }
    }
  else
    {
      node = node->children;

      while (node)
    {
      if (frost_node_traverse_level (node, flags, level - 1, func, data, more_levels))
        return frost_true;

      node = node->next;
    }
    }

  return frost_false;
}

static frost_bool
frost_node_depth_traverse_level (FROST_Node             *node,
                 FROSTTraverseFlags flags,
                 frost_uint      depth,
                 FROST_NodeTraverseFunc  func,
                 frost_pointer           data)
{
  frost_uint level;
  frost_bool more_levels;

  level = 0;
  while (level != depth)
    {
      more_levels = frost_false;
      if (frost_node_traverse_level (node, flags, level, func, data, &more_levels))
    return frost_true;
      if (!more_levels)
    break;
      level++;
    }
  return frost_false;
}

/**
 * frost_node_traverse:
 * @root: the root #FROST_Node of the tree to traverse
 * @order: the order in which nodes are visited - %ICE_IN_ORDER,
 *     %ICE_PRE_ORDER, %ICE_POST_ORDER, or %ICE_LEVEL_ORDER.
 * @flags: which types of children are to be visited, one of
 *     %ICE_TRAVERSE_ALL, %ICE_TRAVERSE_LEAVES and %ICE_TRAVERSE_NON_LEAVES
 * @max_depth: the maximum depth of the traversal. Nodes below this
 *     depth will not be visited. If max_depth is -1 all nodes in
 *     the tree are visited. If depth is 1, only the root is visited.
 *     If depth is 2, the root and its children are visited. And so on.
 * @func: the function to call for each visited #FROST_Node
 * @data: user data to pass to the function
 *
 * Traverses a tree starting at the given root #FROST_Node.
 * It calls the given function for each node visited.
 * The traversal can be halted at any point by returning %frost_true from @func.
 */
/**
 * FROSTTraverseFlags:
 * @ICE_TRAVERSE_LEAVES: only leaf nodes should be visited. This name has
 *                     been introduced in 2.6, for older version use
 *                     %ICE_TRAVERSE_LEAFS.
 * @ICE_TRAVERSE_NON_LEAVES: only non-leaf nodes should be visited. This
 *                         name has been introduced in 2.6, for older
 *                         version use %ICE_TRAVERSE_NON_LEAFS.
 * @ICE_TRAVERSE_ALL: all nodes should be visited.
 * @ICE_TRAVERSE_MASK: a mask of all traverse flags.
 * @ICE_TRAVERSE_LEAFS: identical to %ICE_TRAVERSE_LEAVES.
 * @ICE_TRAVERSE_NON_LEAFS: identical to %ICE_TRAVERSE_NON_LEAVES.
 *
 * Specifies which nodes are visited during several of the tree
 * functions, including frost_node_traverse() and frost_node_find().
 **/
/**
 * FROST_NodeTraverseFunc:
 * @node: a #FROST_Node.
 * @data: user data passed to frost_node_traverse().
 * @Returns: %frost_true to stop the traversal.
 *
 * Specifies the type of function passed to frost_node_traverse(). The
 * function is called with each of the nodes visited, together with the
 * user data passed to frost_node_traverse(). If the function returns
 * %frost_true, then the traversal is stopped.
 **/
void
frost_node_traverse (FROST_Node        *root,
         FROSTTraverseType     order,
         FROSTTraverseFlags    flags,
         frost_int          depth,
         FROST_NodeTraverseFunc func,
         frost_pointer      data)
{
  frost_return_if_fail (root != NULL);
  frost_return_if_fail (func != NULL);
  frost_return_if_fail (order <= ICE_LEVEL_ORDER);
  frost_return_if_fail (flags <= ICE_TRAVERSE_MASK);
  frost_return_if_fail (depth == -1 || depth > 0);

  switch (order)
    {
    case ICE_PRE_ORDER:
      if (depth < 0)
    frost_node_traverse_pre_order (root, flags, func, data);
      else
    frost_node_depth_traverse_pre_order (root, flags, depth, func, data);
      break;
    case ICE_POST_ORDER:
      if (depth < 0)
    frost_node_traverse_post_order (root, flags, func, data);
      else
    frost_node_depth_traverse_post_order (root, flags, depth, func, data);
      break;
    case ICE_IN_ORDER:
      if (depth < 0)
    frost_node_traverse_in_order (root, flags, func, data);
      else
    frost_node_depth_traverse_in_order (root, flags, depth, func, data);
      break;
    case ICE_LEVEL_ORDER:
      frost_node_depth_traverse_level (root, flags, depth, func, data);
      break;
    }
}

static frost_bool
frost_node_find_func (FROST_Node    *node,
          frost_pointer  data)
{
  frost_pointer *d = data;

  if (*d != node->data)
    return frost_false;

  *(++d) = node;

  return frost_true;
}

/**
 * frost_node_find:
 * @root: the root #FROST_Node of the tree to search
 * @order: the order in which nodes are visited - %ICE_IN_ORDER,
 *     %ICE_PRE_ORDER, %ICE_POST_ORDER, or %ICE_LEVEL_ORDER
 * @flags: which types of children are to be searched, one of
 *     %ICE_TRAVERSE_ALL, %ICE_TRAVERSE_LEAVES and %ICE_TRAVERSE_NON_LEAVES
 * @data: the data to find
 *
 * Finds a #FROST_Node in a tree.
 *
 * Returns: the found #FROST_Node, or %NULL if the data is not found
 */
FROST_Node*
frost_node_find (FROST_Node      *root,
         FROSTTraverseType   order,
         FROSTTraverseFlags  flags,
         frost_pointer        data)
{
  frost_pointer d[2];

  frost_return_val_if_fail (root != NULL, NULL);
  frost_return_val_if_fail (order <= ICE_LEVEL_ORDER, NULL);
  frost_return_val_if_fail (flags <= ICE_TRAVERSE_MASK, NULL);

  d[0] = data;
  d[1] = NULL;

  frost_node_traverse (root, order, flags, -1, frost_node_find_func, d);

  return d[1];
}

static void
frost_node_count_func (FROST_Node     *node,
           FROSTTraverseFlags flags,
           frost_uint     *n)
{
  if (node->children)
    {
      FROST_Node *child;

      if (flags & ICE_TRAVERSE_NON_LEAFS)
    (*n)++;

      child = node->children;
      while (child)
    {
      frost_node_count_func (child, flags, n);
      child = child->next;
    }
    }
  else if (flags & ICE_TRAVERSE_LEAFS)
    (*n)++;
}

/**
 * frost_node_n_nodes:
 * @root: a #FROST_Node
 * @flags: which types of children are to be counted, one of
 *     %ICE_TRAVERSE_ALL, %ICE_TRAVERSE_LEAVES and %ICE_TRAVERSE_NON_LEAVES
 *
 * Gets the number of nodes in a tree.
 *
 * Returns: the number of nodes in the tree
 */
frost_uint
frost_node_n_nodes (FROST_Node          *root,
        FROSTTraverseFlags  flags)
{
  frost_uint n = 0;

  frost_return_val_if_fail (root != NULL, 0);
  frost_return_val_if_fail (flags <= ICE_TRAVERSE_MASK, 0);

  frost_node_count_func (root, flags, &n);

  return n;
}

/**
 * frost_node_last_child:
 * @node: a #FROST_Node (must not be %NULL)
 *
 * Gets the last child of a #FROST_Node.
 *
 * Returns: the last child of @node, or %NULL if @node has no children
 */
FROST_Node*
frost_node_last_child (FROST_Node *node)
{
  frost_return_val_if_fail (node != NULL, NULL);

  node = node->children;
  if (node)
    while (node->next)
      node = node->next;

  return node;
}

/**
 * frost_node_nth_child:
 * @node: a #FROST_Node
 * @n: the index of the desired child
 *
 * Gets a child of a #FROST_Node, using the given index.
 * The first child is at index 0. If the index is
 * too big, %NULL is returned.
 *
 * Returns: the child of @node at index @n
 */
FROST_Node*
frost_node_nth_child (FROST_Node *node,
          frost_uint  n)
{
  frost_return_val_if_fail (node != NULL, NULL);

  node = node->children;
  if (node)
    while ((n-- > 0) && node)
      node = node->next;

  return node;
}

/**
 * frost_node_n_children:
 * @node: a #FROST_Node
 *
 * Gets the number of children of a #FROST_Node.
 *
 * Returns: the number of children of @node
 */
frost_uint
frost_node_n_children (FROST_Node *node)
{
  frost_uint n = 0;

  frost_return_val_if_fail (node != NULL, 0);

  node = node->children;
  while (node)
    {
      n++;
      node = node->next;
    }

  return n;
}

/**
 * frost_node_find_child:
 * @node: a #FROST_Node
 * @flags: which types of children are to be searched, one of
 *     %ICE_TRAVERSE_ALL, %ICE_TRAVERSE_LEAVES and %ICE_TRAVERSE_NON_LEAVES
 * @data: the data to find
 *
 * Finds the first child of a #FROST_Node with the given data.
 *
 * Returns: the found child #FROST_Node, or %NULL if the data is not found
 */
FROST_Node*
frost_node_find_child (FROST_Node      *node,
           FROSTTraverseFlags  flags,
           frost_pointer    data)
{
  frost_return_val_if_fail (node != NULL, NULL);
  frost_return_val_if_fail (flags <= ICE_TRAVERSE_MASK, NULL);

  node = node->children;
  while (node)
    {
      if (node->data == data)
    {
      if (FROST_NODE_IS_LEAF (node))
        {
          if (flags & ICE_TRAVERSE_LEAFS)
        return node;
        }
      else
        {
          if (flags & ICE_TRAVERSE_NON_LEAFS)
        return node;
        }
    }
      node = node->next;
    }

  return NULL;
}

/**
 * frost_node_child_position:
 * @node: a #FROST_Node
 * @child: a child of @node
 *
 * Gets the position of a #FROST_Node with respect to its siblings.
 * @child must be a child of @node. The first child is numbered 0,
 * the second 1, and so on.
 *
 * Returns: the position of @child with respect to its siblings
 */
frost_int
frost_node_child_position (FROST_Node *node,
               FROST_Node *child)
{
  frost_uint n = 0;

  frost_return_val_if_fail (node != NULL, -1);
  frost_return_val_if_fail (child != NULL, -1);
  frost_return_val_if_fail (child->parent == node, -1);

  node = node->children;
  while (node)
    {
      if (node == child)
    return n;
      n++;
      node = node->next;
    }

  return -1;
}

/**
 * frost_node_child_index:
 * @node: a #FROST_Node
 * @data: the data to find
 *
 * Gets the position of the first child of a #FROST_Node
 * which contains the given data.
 *
 * Returns: the index of the child of @node which contains
 *     @data, or -1 if the data is not found
 */
frost_int
frost_node_child_index (FROST_Node    *node,
            frost_pointer  data)
{
  frost_uint n = 0;

  frost_return_val_if_fail (node != NULL, -1);

  node = node->children;
  while (node)
    {
      if (node->data == data)
    return n;
      n++;
      node = node->next;
    }

  return -1;
}

/**
 * frost_node_first_sibling:
 * @node: a #FROST_Node
 *
 * Gets the first sibling of a #FROST_Node.
 * This could possibly be the node itself.
 *
 * Returns: the first sibling of @node
 */
FROST_Node*
frost_node_first_sibling (FROST_Node *node)
{
  frost_return_val_if_fail (node != NULL, NULL);

  if (node->parent)
    return node->parent->children;

  while (node->prev)
    node = node->prev;

  return node;
}

/**
 * frost_node_last_sibling:
 * @node: a #FROST_Node
 *
 * Gets the last sibling of a #FROST_Node.
 * This could possibly be the node itself.
 *
 * Returns: the last sibling of @node
 */
FROST_Node*
frost_node_last_sibling (FROST_Node *node)
{
  frost_return_val_if_fail (node != NULL, NULL);

  while (node->next)
    node = node->next;

  return node;
}

/**
 * frost_node_children_foreach:
 * @node: a #FROST_Node
 * @flags: which types of children are to be visited, one of
 *     %ICE_TRAVERSE_ALL, %ICE_TRAVERSE_LEAVES and %ICE_TRAVERSE_NON_LEAVES
 * @func: the function to call for each visited node
 * @data: user data to pass to the function
 *
 * Calls a function for each of the children of a #FROST_Node.
 * Note that it doesn't descend beneath the child nodes.
 */
/**
 * FROST_NodeForeachFunc:
 * @node: a #FROST_Node.
 * @data: user data passed to frost_node_children_foreach().
 *
 * Specifies the type of function passed to frost_node_children_foreach().
 * The function is called with each child node, together with the user
 * data passed to frost_node_children_foreach().
 **/
void
frost_node_children_foreach (FROST_Node        *node,
             FROSTTraverseFlags    flags,
             FROST_NodeForeachFunc  func,
             frost_pointer      data)
{
  frost_return_if_fail (node != NULL);
  frost_return_if_fail (flags <= ICE_TRAVERSE_MASK);
  frost_return_if_fail (func != NULL);

  node = node->children;
  while (node)
    {
      FROST_Node *current;

      current = node;
      node = current->next;
      if (FROST_NODE_IS_LEAF (current))
    {
      if (flags & ICE_TRAVERSE_LEAFS)
        func (current, data);
    }
      else
    {
      if (flags & ICE_TRAVERSE_NON_LEAFS)
        func (current, data);
    }
    }
}
