#ifndef lib_aatree_h #define lib_aatree_h /* Cesar project {{{ * * Copyright (C) 2007 Spidcom * * <<>> * * }}} */ /** * \file lib/aatree.h * \brief Arne Andersson Trees. * \ingroup lib */ /* Set node. */ struct set_node_t { /** Pointer to parent node. */ set_node_t *father; /** Pointer to left and right children. */ set_node_t *left, *right; /** Node level. */ uint level; }; /* Forward declaration in lib/set.h. */ BEGIN_DECLS /** * Initialise a set. * \param set the set * \param less the "is lesser than" comparison function */ void set_init (set_t *set, set_node_less_t less); /** * Initialise a set node. * \param node the node to initialise */ void set_node_init (set_node_t *node); /** * Find a node inside a set. * \param set the set to look into * \param node node to compare with nodes inside the set * \return the found node or NULL if none found * * The \a node parameter just have to contains enough data to be used with the * comparison function. */ set_node_t * set_find (set_t *set, set_node_t *node); /** * Insert a node. * \param set the set * \param node node to insert * \return true if successful (not in the set yet) */ bool set_insert (set_t *set, set_node_t *node); /** * Remove a node from the set. * \param set the set * \param node the node to remove * * The node must be inside the set. */ void set_remove (set_t *set, set_node_t *node); /** * Return the first node. * \param set the set * \return the minimum node */ set_node_t * set_begin (set_t *set); /** * Return the node after the last one. * \param set the set * \return past the last node */ extern inline set_node_t * set_end (set_t *set) { return NULL; } /** * Return the next node. * \param set the set * \param node current node * \return the following node */ set_node_t * set_next (set_t *set, set_node_t *node); /** * Return whether the set is empty. * \param set the set * \return true if empty */ extern inline bool set_empty (set_t *set) { return set->root->level == 0; } /** * Return whether a node is in any set. * \param node initialised node * \return true if the node is in a set */ extern inline bool set_node_in_any_set (set_node_t *node) { return node->level != 0; } /** * Swap nodes of to compatibles sets. * \param a first set * \param b second set */ void set_swap (set_t *a, set_t *b); END_DECLS #endif /* lib_aatree_h */