diff options
Diffstat (limited to 'src/zix/tree.h')
-rw-r--r-- | src/zix/tree.h | 121 |
1 files changed, 121 insertions, 0 deletions
diff --git a/src/zix/tree.h b/src/zix/tree.h new file mode 100644 index 0000000..670c437 --- /dev/null +++ b/src/zix/tree.h @@ -0,0 +1,121 @@ +/* + Copyright 2011 David Robillard <http://drobilla.net> + + Permission to use, copy, modify, and/or distribute this software for any + purpose with or without fee is hereby granted, provided that the above + copyright notice and this permission notice appear in all copies. + + THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. +*/ + +#ifndef ZIX_TREE_H +#define ZIX_TREE_H + +#include <stdbool.h> + +#include "zix/common.h" + +#ifdef __cplusplus +extern "C" { +#endif + +/** + @addtogroup zix + @{ + @name Tree + @{ +*/ + +/** + A balanced binary search tree. +*/ +typedef struct ZixTreeImpl ZixTree; + +/** + An iterator over a @ref ZixTree. +*/ +typedef struct ZixTreeNodeImpl ZixTreeIter; + +/** + Create a new (empty) tree. +*/ +ZixTree* +zix_tree_new(bool allow_duplicates, ZixComparator cmp, void* cmp_data); + +/** + Free @a t. +*/ +void +zix_tree_free(ZixTree* t); + +/** + Insert the element @a e into @a t and point @a ti at the new element. +*/ +ZixStatus +zix_tree_insert(ZixTree* t, void* e, ZixTreeIter** ti); + +/** + Remove the item pointed at by @a ti from @a t. +*/ +ZixStatus +zix_tree_remove(ZixTree* t, ZixTreeIter* ti); + +/** + Set @a ti to an element equal to @a e in @a t. + If no such item exists, @a ti is set to NULL. +*/ +ZixStatus +zix_tree_find(const ZixTree* t, const void* e, ZixTreeIter** ti); + +/** + Return the data associated with the given tree item. +*/ +void* +zix_tree_get(ZixTreeIter* ti); + +/** + Return an iterator to the first (smallest) element in @a t. +*/ +ZixTreeIter* +zix_tree_begin(ZixTree* t); + +/** + Return an iterator the the element one past the last element in @a t. +*/ +ZixTreeIter* +zix_tree_end(ZixTree* t); + +/** + Return true iff @a i is an iterator to the end of its tree. +*/ +bool +zix_tree_iter_is_end(ZixTreeIter* i); + +/** + Return an iterator that points to the element one past @a i. +*/ +ZixTreeIter* +zix_tree_iter_next(ZixTreeIter* i); + +/** + Return an iterator that points to the element one before @a i. +*/ +ZixTreeIter* +zix_tree_iter_prev(ZixTreeIter* i); + +/** + @} + @} +*/ + +#ifdef __cplusplus +} /* extern "C" */ +#endif + +#endif /* ZIX_TREE_H */ |