C Standard Library Extensions  1.2.1
cxtree.h
1 /* $Id: cxtree.h,v 1.5 2011-02-21 14:15:31 rpalsa Exp $
2  *
3  * This file is part of the ESO C Extension Library
4  * Copyright (C) 2001-2011 European Southern Observatory
5  *
6  * This program is free software; you can redistribute it and/or modify
7  * it under the terms of the GNU General Public License as published by
8  * the Free Software Foundation; either version 2 of the License, or
9  * (at your option) any later version.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software
18  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
19  */
20 
21 /*
22  * $Author: rpalsa $
23  * $Date: 2011-02-21 14:15:31 $
24  * $Revision: 1.5 $
25  * $Name: not supported by cvs2svn $
26  */
27 
28 #ifndef CX_TREE_H
29 #define CX_TREE_H
30 
31 #include <cxmemory.h>
32 
33 CX_BEGIN_DECLS
34 
35 typedef struct _cx_tnode_ *cx_tree_iterator;
36 typedef const struct _cx_tnode_ *cx_tree_const_iterator;
37 
38 typedef struct _cx_tree_ cx_tree;
39 
75 typedef cxbool (*cx_tree_compare_func)(cxcptr, cxcptr);
76 
77 /*
78  * Create, copy and destroy operations
79  */
80 
81 cx_tree *cx_tree_new(cx_tree_compare_func, cx_free_func, cx_free_func);
82 void cx_tree_delete(cx_tree *);
83 
84 /*
85  * Nonmodifying operations
86  */
87 
88 cxsize cx_tree_size(const cx_tree *);
89 cxbool cx_tree_empty(const cx_tree *);
90 cxsize cx_tree_max_size(const cx_tree *);
91 cx_tree_compare_func cx_tree_key_comp(const cx_tree *);
92 
93 /*
94  * Special search operations
95  */
96 
97 cxsize cx_tree_count(const cx_tree *, cxcptr);
98 cx_tree_iterator cx_tree_find(const cx_tree *, cxcptr);
99 cx_tree_iterator cx_tree_lower_bound(const cx_tree *, cxcptr);
100 cx_tree_iterator cx_tree_upper_bound(const cx_tree *, cxcptr);
101 void cx_tree_equal_range(const cx_tree *, cxcptr, cx_tree_iterator *,
102  cx_tree_iterator *);
103 
104 /*
105  * Assignment operations
106  */
107 
108 void cx_tree_swap(cx_tree *, cx_tree *);
109 cxptr cx_tree_assign(cx_tree *, cx_tree_iterator, cxcptr);
110 
111 /*
112  * Element access
113  */
114 
115 cxptr cx_tree_get_key(const cx_tree *, cx_tree_const_iterator);
116 cxptr cx_tree_get_value(const cx_tree *, cx_tree_const_iterator);
117 
118 /*
119  * Iterator functions
120  */
121 
122 cx_tree_iterator cx_tree_begin(const cx_tree *);
123 cx_tree_iterator cx_tree_end(const cx_tree *);
124 cx_tree_iterator cx_tree_next(const cx_tree *, cx_tree_const_iterator);
125 cx_tree_iterator cx_tree_previous(const cx_tree *, cx_tree_const_iterator);
126 
127 
128 /*
129  * Inserting and removing elements
130  */
131 
132 cx_tree_iterator cx_tree_insert_unique(cx_tree *, cxcptr, cxcptr);
133 cx_tree_iterator cx_tree_insert_equal(cx_tree *, cxcptr, cxcptr);
134 void cx_tree_erase_position(cx_tree *, cx_tree_iterator);
135 void cx_tree_erase_range(cx_tree *, cx_tree_iterator, cx_tree_iterator);
136 cxsize cx_tree_erase(cx_tree *, cxcptr);
137 void cx_tree_clear(cx_tree *);
138 
139 /*
140  * Debugging
141  */
142 
143 cxbool cx_tree_verify(const cx_tree *);
144 
145 CX_END_DECLS
146 
147 #endif /* CX_TREE_H */
cx_tree_iterator cx_tree_insert_unique(cx_tree *, cxcptr, cxcptr)
Attempt to insert data into a tree.
Definition: cxtree.c:1669
void cx_tree_clear(cx_tree *)
Remove all pairs from a tree.
Definition: cxtree.c:1156
cxbool cx_tree_verify(const cx_tree *)
Validate a tree.
Definition: cxtree.c:1833
cx_tree_compare_func cx_tree_key_comp(const cx_tree *)
Get the key comparison function.
Definition: cxtree.c:1334
cx_tree_iterator cx_tree_begin(const cx_tree *)
Get an iterator to the first pair in the tree.
Definition: cxtree.c:1038
cx_tree_iterator cx_tree_insert_equal(cx_tree *, cxcptr, cxcptr)
Insert data into a tree.
Definition: cxtree.c:1696
cx_tree_iterator cx_tree_lower_bound(const cx_tree *, cxcptr)
Find the beginning of a subsequence.
Definition: cxtree.c:1536
cxsize cx_tree_count(const cx_tree *, cxcptr)
Get the number of elements matching a key.
Definition: cxtree.c:1624
cxbool(* cx_tree_compare_func)(cxcptr, cxcptr)
The tree's key comparison operator function.
Definition: cxtree.h:75
cxbool cx_tree_empty(const cx_tree *)
Check whether a tree is empty.
Definition: cxtree.c:1184
cxsize cx_tree_erase(cx_tree *, cxcptr)
Erase all elements from a tree matching the provided key.
Definition: cxtree.c:1793
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:1125
void cx_tree_erase_position(cx_tree *, cx_tree_iterator)
Erase an element from a tree.
Definition: cxtree.c:1723
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:1091
cxsize cx_tree_max_size(const cx_tree *)
Get the maximum number of pairs possible.
Definition: cxtree.c:1307
cxsize cx_tree_size(const cx_tree *)
Get the actual number of pairs in the tree.
Definition: cxtree.c:1284
cxptr cx_tree_get_key(const cx_tree *, cx_tree_const_iterator)
Get the key from a given iterator position.
Definition: cxtree.c:1449
cx_tree_iterator cx_tree_upper_bound(const cx_tree *, cxcptr)
Find the end of a subsequence.
Definition: cxtree.c:1565
void cx_tree_delete(cx_tree *)
Destroy a tree and all its elements.
Definition: cxtree.c:1258
cxptr cx_tree_assign(cx_tree *, cx_tree_iterator, cxcptr)
Assign data to an iterator position.
Definition: cxtree.c:1412
cx_tree_iterator cx_tree_find(const cx_tree *, cxcptr)
Locate an element in the tree.
Definition: cxtree.c:1507
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:1220
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:1064
void cx_tree_erase_range(cx_tree *, cx_tree_iterator, cx_tree_iterator)
Erase a range of elements from a tree.
Definition: cxtree.c:1757
void cx_tree_swap(cx_tree *, cx_tree *)
Swap the contents of two trees.
Definition: cxtree.c:1360
cxptr cx_tree_get_value(const cx_tree *, cx_tree_const_iterator)
Get the data from a given iterator position.
Definition: cxtree.c:1476
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:1596