C Standard Library Extensions 1.2.6
cxtree.h
1/*
2 * This file is part of the ESO C Extension Library
3 * Copyright (C) 2001-2017 European Southern Observatory
4 *
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation; either version 2 of the License, or
8 * (at your option) any later version.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software
17 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
18 */
19
20#ifndef CX_TREE_H
21#define CX_TREE_H
22
23#include <cxmemory.h>
24
25CX_BEGIN_DECLS
26
27typedef struct _cx_tnode_ *cx_tree_iterator;
28typedef const struct _cx_tnode_ *cx_tree_const_iterator;
29
30typedef struct _cx_tree_ cx_tree;
31
72typedef cxbool (*cx_tree_compare_func)(cxcptr, cxcptr);
73
74/*
75 * Create, copy and destroy operations
76 */
77
78cx_tree *cx_tree_new(cx_tree_compare_func, cx_free_func, cx_free_func);
79void cx_tree_delete(cx_tree *);
80
81/*
82 * Nonmodifying operations
83 */
84
85cxsize cx_tree_size(const cx_tree *);
86cxbool cx_tree_empty(const cx_tree *);
87cxsize cx_tree_max_size(const cx_tree *);
89
90/*
91 * Special search operations
92 */
93
94cxsize cx_tree_count(const cx_tree *, cxcptr);
95cx_tree_iterator cx_tree_find(const cx_tree *, cxcptr);
96cx_tree_iterator cx_tree_lower_bound(const cx_tree *, cxcptr);
97cx_tree_iterator cx_tree_upper_bound(const cx_tree *, cxcptr);
98void cx_tree_equal_range(const cx_tree *, cxcptr, cx_tree_iterator *,
99 cx_tree_iterator *);
100
101/*
102 * Assignment operations
103 */
104
105void cx_tree_swap(cx_tree *, cx_tree *);
106cxptr cx_tree_assign(cx_tree *, cx_tree_iterator, cxcptr);
107
108/*
109 * Element access
110 */
111
112cxptr cx_tree_get_key(const cx_tree *, cx_tree_const_iterator);
113cxptr cx_tree_get_value(const cx_tree *, cx_tree_const_iterator);
114
115/*
116 * Iterator functions
117 */
118
119cx_tree_iterator cx_tree_begin(const cx_tree *);
120cx_tree_iterator cx_tree_end(const cx_tree *);
121cx_tree_iterator cx_tree_next(const cx_tree *, cx_tree_const_iterator);
122cx_tree_iterator cx_tree_previous(const cx_tree *, cx_tree_const_iterator);
123
124
125/*
126 * Inserting and removing elements
127 */
128
129cx_tree_iterator cx_tree_insert_unique(cx_tree *, cxcptr, cxcptr);
130cx_tree_iterator cx_tree_insert_equal(cx_tree *, cxcptr, cxcptr);
131void cx_tree_erase_position(cx_tree *, cx_tree_iterator);
132void cx_tree_erase_range(cx_tree *, cx_tree_iterator, cx_tree_iterator);
133cxsize cx_tree_erase(cx_tree *, cxcptr);
134void cx_tree_clear(cx_tree *);
135
136/*
137 * Debugging
138 */
139
140cxbool cx_tree_verify(const cx_tree *);
141
142CX_END_DECLS
143
144#endif /* CX_TREE_H */
cx_tree_iterator cx_tree_insert_equal(cx_tree *, cxcptr, cxcptr)
Insert data into a tree.
Definition: cxtree.c:1688
cxbool(* cx_tree_compare_func)(cxcptr, cxcptr)
The tree's key comparison operator function.
Definition: cxtree.h:72
cxsize cx_tree_erase(cx_tree *, cxcptr)
Erase all elements from a tree matching the provided key.
Definition: cxtree.c:1785
cxbool cx_tree_empty(const cx_tree *)
Check whether a tree is empty.
Definition: cxtree.c:1176
cx_tree_iterator cx_tree_insert_unique(cx_tree *, cxcptr, cxcptr)
Attempt to insert data into a tree.
Definition: cxtree.c:1661
cx_tree_iterator cx_tree_lower_bound(const cx_tree *, cxcptr)
Find the beginning of a subsequence.
Definition: cxtree.c:1528
cxsize cx_tree_max_size(const cx_tree *)
Get the maximum number of pairs possible.
Definition: cxtree.c:1299
void cx_tree_clear(cx_tree *)
Remove all pairs from a tree.
Definition: cxtree.c:1148
cxsize cx_tree_size(const cx_tree *)
Get the actual number of pairs in the tree.
Definition: cxtree.c:1276
cx_tree_compare_func cx_tree_key_comp(const cx_tree *)
Get the key comparison function.
Definition: cxtree.c:1326
cx_tree_iterator cx_tree_upper_bound(const cx_tree *, cxcptr)
Find the end of a subsequence.
Definition: cxtree.c:1557
cxptr cx_tree_get_value(const cx_tree *, cx_tree_const_iterator)
Get the data from a given iterator position.
Definition: cxtree.c:1468
cxptr cx_tree_get_key(const cx_tree *, cx_tree_const_iterator)
Get the key from a given iterator position.
Definition: cxtree.c:1441
void cx_tree_delete(cx_tree *)
Destroy a tree and all its elements.
Definition: cxtree.c:1250
cxptr cx_tree_assign(cx_tree *, cx_tree_iterator, cxcptr)
Assign data to an iterator position.
Definition: cxtree.c:1404
cx_tree_iterator cx_tree_begin(const cx_tree *)
Get an iterator to the first pair in the tree.
Definition: cxtree.c:1030
cx_tree * cx_tree_new(cx_tree_compare_func, cx_free_func, cx_free_func)
Create a new tree without any elements.
Definition: cxtree.c:1212
cx_tree_iterator cx_tree_previous(const cx_tree *, cx_tree_const_iterator)
Get an iterator for the previous pair in the tree.
Definition: cxtree.c:1117
cx_tree_iterator cx_tree_next(const cx_tree *, cx_tree_const_iterator)
Get an iterator for the next pair in the tree.
Definition: cxtree.c:1083
void cx_tree_equal_range(const cx_tree *, cxcptr, cx_tree_iterator *, cx_tree_iterator *)
Find a subsequence matching a given key.
Definition: cxtree.c:1588
cx_tree_iterator cx_tree_find(const cx_tree *, cxcptr)
Locate an element in the tree.
Definition: cxtree.c:1499
cxbool cx_tree_verify(const cx_tree *)
Validate a tree.
Definition: cxtree.c:1825
cx_tree_iterator cx_tree_end(const cx_tree *)
Get an iterator for the position after the last pair in the tree.
Definition: cxtree.c:1056
void cx_tree_erase_range(cx_tree *, cx_tree_iterator, cx_tree_iterator)
Erase a range of elements from a tree.
Definition: cxtree.c:1749
void cx_tree_erase_position(cx_tree *, cx_tree_iterator)
Erase an element from a tree.
Definition: cxtree.c:1715
cxsize cx_tree_count(const cx_tree *, cxcptr)
Get the number of elements matching a key.
Definition: cxtree.c:1616
void cx_tree_swap(cx_tree *, cx_tree *)
Swap the contents of two trees.
Definition: cxtree.c:1352