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

#ifndef FROST_NODE_H_
#define FROST_NODE_H_

#include "frost_common.h"

#ifdef __cplusplus
extern "C"
{
#endif

typedef struct _FROST_Node       FROST_Node;

/* Tree traverse flags */
typedef enum
{
  ICE_TRAVERSE_LEAVES     = 1 << 0,
  ICE_TRAVERSE_NON_LEAVES = 1 << 1,
  ICE_TRAVERSE_ALL        = ICE_TRAVERSE_LEAVES | ICE_TRAVERSE_NON_LEAVES,
  ICE_TRAVERSE_MASK       = 0x03,
  ICE_TRAVERSE_LEAFS      = ICE_TRAVERSE_LEAVES,
  ICE_TRAVERSE_NON_LEAFS  = ICE_TRAVERSE_NON_LEAVES
} FROSTTraverseFlags;

/* Tree traverse orders */
typedef enum
{
  ICE_IN_ORDER,
  ICE_PRE_ORDER,
  ICE_POST_ORDER,
  ICE_LEVEL_ORDER
} FROSTTraverseType;

typedef frost_bool    (*FROST_NodeTraverseFunc)    (FROST_Node         *node,
                         frost_pointer   data);
typedef void        (*FROST_NodeForeachFunc) (FROST_Node         *node,
                         frost_pointer   data);

/**
 * FROSTCopyFunc:
 * @src: A pointer to the data which should be copied
 * @data: Additional data
 *
 * A function of this signature is used to copy the node data
 * when doing a deep-copy of a tree.
 *
 * Returns: A pointer to the copy
 *
 * Since: 2.4
 */
typedef frost_pointer    (*FROSTCopyFunc)            (frost_constpointer  src,
                                                 frost_pointer       data);

/* N-way tree implementation
 */
struct _FROST_Node
{
  frost_pointer data;
  FROST_Node   *next;
  FROST_Node   *prev;
  FROST_Node   *parent;
  FROST_Node   *children;
};

/**
 * FROST_NODE_IS_ROOT:
 * @node: a #FROST_Node
 *
 * Returns %TRUE if a #FROST_Node is the root of a tree.
 *
 * Returns: %TRUE if the #FROST_Node is the root of a tree
 *     (i.e. it has no parent or siblings)
 */
#define  FROST_NODE_IS_ROOT(node)   (((FROST_Node*) (node))->parent == NULL && \
                 ((FROST_Node*) (node))->prev == NULL && \
                 ((FROST_Node*) (node))->next == NULL)

/**
 * FROST_NODE_IS_LEAF:
 * @node: a #FROST_Node
 *
 * Returns %TRUE if a #FROST_Node is a leaf node.
 *
 * Returns: %TRUE if the #FROST_Node is a leaf node
 *     (i.e. it has no children)
 */
#define  FROST_NODE_IS_LEAF(node)   (((FROST_Node*) (node))->children == NULL)

FROST_Node*   frost_node_new     (frost_pointer      data);
void     frost_node_destroy     (FROST_Node        *root);
void     frost_node_unlink      (FROST_Node        *node);
FROST_Node*   frost_node_copy_deep       (FROST_Node            *node,
                 FROSTCopyFunc         copy_func,
                 frost_pointer          data);
FROST_Node*   frost_node_copy            (FROST_Node            *node);
FROST_Node*   frost_node_insert      (FROST_Node        *parent,
                 frost_int          position,
                 FROST_Node        *node);
FROST_Node*   frost_node_insert_before   (FROST_Node        *parent,
                 FROST_Node        *sibling,
                 FROST_Node        *node);
FROST_Node*   frost_node_insert_after    (FROST_Node            *parent,
                 FROST_Node            *sibling,
                 FROST_Node            *node);
FROST_Node*   frost_node_prepend     (FROST_Node        *parent,
                 FROST_Node        *node);
frost_uint    frost_node_n_nodes     (FROST_Node        *root,
                 FROSTTraverseFlags    flags);
FROST_Node*   frost_node_get_root    (FROST_Node        *node);
frost_bool frost_node_is_ancestor (FROST_Node        *node,
                 FROST_Node        *descendant);
frost_uint    frost_node_depth       (FROST_Node        *node);
FROST_Node*   frost_node_find        (FROST_Node        *root,
                 FROSTTraverseType     order,
                 FROSTTraverseFlags    flags,
                 frost_pointer      data);

/* convenience macros */
/**
 * frost_node_append:
 * @parent: the #FROST_Node to place the new #FROST_Node under
 * @node: the #FROST_Node to insert
 *
 * Inserts a #FROST_Node as the last child of the given parent.
 *
 * Returns: the inserted #FROST_Node
 */
#define frost_node_append(parent, node)             \
     frost_node_insert_before ((parent), NULL, (node))

/**
 * frost_node_insert_data:
 * @parent: the #FROST_Node to place the new #FROST_Node under
 * @position: the position to place the new #FROST_Node at. If position is -1,
 *     the new #FROST_Node is inserted as the last child of @parent
 * @data: the data for the new #FROST_Node
 *
 * Inserts a new #FROST_Node at the given position.
 *
 * Returns: the new #FROST_Node
 */
#define frost_node_insert_data(parent, position, data)      \
     frost_node_insert ((parent), (position), frost_node_new (data))

/**
 * frost_node_insert_data_before:
 * @parent: the #FROST_Node to place the new #FROST_Node under
 * @sibling: the sibling #FROST_Node to place the new #FROST_Node before
 * @data: the data for the new #FROST_Node
 *
 * Inserts a new #FROST_Node before the given sibling.
 *
 * Returns: the new #FROST_Node
 */
#define frost_node_insert_data_before(parent, sibling, data)    \
     frost_node_insert_before ((parent), (sibling), frost_node_new (data))

/**
 * frost_node_prepend_data:
 * @parent: the #FROST_Node to place the new #FROST_Node under
 * @data: the data for the new #FROST_Node
 *
 * Inserts a new #FROST_Node as the first child of the given parent.
 *
 * Returns: the new #FROST_Node
 */
#define frost_node_prepend_data(parent, data)           \
     frost_node_prepend ((parent), frost_node_new (data))

/**
 * frost_node_append_data:
 * @parent: the #FROST_Node to place the new #FROST_Node under
 * @data: the data for the new #FROST_Node
 *
 * Inserts a new #FROST_Node as the last child of the given parent.
 *
 * Returns: the new #FROST_Node
 */
#define frost_node_append_data(parent, data)            \
     frost_node_insert_before ((parent), NULL, frost_node_new (data))

/* traversal function, assumes that `node' is root
 * (only traverses `node' and its subtree).
 * this function is just a high level interface to
 * low level traversal functions, optimized for speed.
 */
void     frost_node_traverse    (FROST_Node        *root,
                 FROSTTraverseType     order,
                 FROSTTraverseFlags    flags,
                 frost_int          max_depth,
                 FROST_NodeTraverseFunc func,
                 frost_pointer      data);

/* return the maximum tree height starting with `node', this is an expensive
 * operation, since we need to visit all nodes. this could be shortened by
 * adding `frost_uint height' to struct _FROST_Node, but then again, this is not very
 * often needed, and would make frost_node_insert() more time consuming.
 */
frost_uint    frost_node_max_height   (FROST_Node *root);

void     frost_node_children_foreach (FROST_Node       *node,
                  FROSTTraverseFlags   flags,
                  FROST_NodeForeachFunc func,
                  frost_pointer     data);
void     frost_node_reverse_children (FROST_Node       *node);
frost_uint    frost_node_n_children   (FROST_Node       *node);
FROST_Node*   frost_node_nth_child    (FROST_Node       *node,
                  frost_uint        n);
FROST_Node*   frost_node_last_child   (FROST_Node       *node);
FROST_Node*   frost_node_find_child   (FROST_Node       *node,
                  FROSTTraverseFlags   flags,
                  frost_pointer     data);
frost_int     frost_node_child_position   (FROST_Node       *node,
                  FROST_Node       *child);
frost_int     frost_node_child_index  (FROST_Node       *node,
                  frost_pointer     data);

FROST_Node*   frost_node_first_sibling    (FROST_Node       *node);
FROST_Node*   frost_node_last_sibling     (FROST_Node       *node);

/**
 * frost_node_prev_sibling:
 * @node: a #FROST_Node
 *
 * Gets the previous sibling of a #FROST_Node.
 *
 * Returns: the previous sibling of @node, or %NULL if @node is the first
 *     node or %NULL
 */
#define  frost_node_prev_sibling(node)  ((node) ? \
                     ((FROST_Node*) (node))->prev : NULL)

/**
 * frost_node_next_sibling:
 * @node: a #FROST_Node
 *
 * Gets the next sibling of a #FROST_Node.
 *
 * Returns: the next sibling of @node, or %NULL if @node is the last node
 *     or %NULL
 */
#define  frost_node_next_sibling(node)  ((node) ? \
                     ((FROST_Node*) (node))->next : NULL)

/**
 * frost_node_first_child:
 * @node: a #FROST_Node
 *
 * Gets the first child of a #FROST_Node.
 *
 * Returns: the first child of @node, or %NULL if @node is %NULL
 *     or has no children
 */
#define  frost_node_first_child(node)   ((node) ? \
                     ((FROST_Node*) (node))->children : NULL)

#ifdef __cplusplus
}
#endif

#endif /* FROST_NODE_H_ */
