00001 /* Part of the culibs project, <http://www.eideticdew.org/culibs/>. 00002 * Copyright (C) 2007 Petter Urkedal <urkedal@nbi.dk> 00003 * 00004 * This program is free software: you can redistribute it and/or modify 00005 * it under the terms of the GNU General Public License as published by 00006 * the Free Software Foundation, either version 3 of the License, or 00007 * (at your option) any later version. 00008 * 00009 * This program is distributed in the hope that it will be useful, 00010 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00011 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00012 * GNU General Public License for more details. 00013 * 00014 * You should have received a copy of the GNU General Public License 00015 * along with this program. If not, see <http://www.gnu.org/licenses/>. 00016 */ 00017 00018 #ifndef CUEX_ATREE_H 00019 #define CUEX_ATREE_H 00020 00021 #include <cuex/fwd.h> 00022 #include <cuoo/type.h> 00023 #include <cu/algo.h> 00024 #include <cu/clos.h> 00025 00026 CU_BEGIN_DECLARATIONS 00027 00028 extern cuoo_type_t cuexP_anode_type; 00029 00030 /** \defgroup cuex_atree_h cuex/atree.h: Associative Trees of Expressions 00031 ** @{ \ingroup cuex_mod 00032 ** 00033 ** This is a low-level interface for implementing semi-lattices, sets, maps, 00034 ** and other collections of expressions which are keyed on a machine word 00035 ** computed form the expressions. 00036 ** 00037 ** The internal structure of the tree is hidden. The leafs of the tree are 00038 ** the inserted expressions. 00039 ** Most of the functions below takes a \a get_key argument, which when passed 00040 ** a leaf node shall compute a \c cu_word_t typed key. 00041 ** Since \c cu_word_t is at least the size of pointers, to implement a set of 00042 ** hash-consed objects, cast the leaf value pointer to \c cu_word_t, and to 00043 ** implement a map, use a binary operation as leafs, and cast the first 00044 ** operand to \c cu_word_t. 00045 ** The same \a get_key must be used consistently when operating on the same 00046 ** tree, which also means that union and intersections can only be used on 00047 ** trees of the same \a get_key. 00048 ** A high-level interface will typically embed these trees in a top-level node 00049 ** and either use a fixed \a get_key or one stored on the top-level node. */ 00050 00051 CU_SINLINE cuoo_type_t 00052 cuex_anode_type() 00053 { return cuexP_anode_type; } 00054 00055 /** An empty container. */ 00056 CU_SINLINE cuex_t 00057 cuex_atree_empty() 00058 { return NULL; } 00059 00060 /** True iff \a tree is the empty container. */ 00061 CU_SINLINE cu_bool_t 00062 cuex_atree_is_empty(cuex_t tree) 00063 { return tree == NULL; } 00064 00065 CU_SINLINE cuex_t 00066 cuex_atree_singleton(cuex_t e) 00067 { return e; } 00068 00069 /** True iff \a tree is a singleton. */ 00070 CU_SINLINE cu_bool_t 00071 cuex_atree_is_singleton(cuex_t tree) 00072 { 00073 return tree != NULL 00074 && cuex_meta(tree) != cuoo_type_to_meta(cuex_anode_type()); 00075 } 00076 00077 /** True iff \a tree is te empty tree or a singleton. */ 00078 CU_SINLINE cu_bool_t 00079 cuex_atree_is_empty_or_singleton(cuex_t tree) 00080 { 00081 return tree == NULL 00082 || cuex_meta(tree) != cuoo_type_to_meta(cuex_anode_type()); 00083 } 00084 00085 /** Find \a find_key in \a tree, assuming \a tree is keyed by \a get_key. 00086 ** Returns the matching element, i.e. the element \e e such that 00087 ** <code>cu_call(get_key, e)</code> equals \a find_key. Returns \c NULL if no 00088 ** such element exists. */ 00089 cuex_t 00090 cuex_atree_find(cu_clop(get_key, cu_word_t, cuex_t), 00091 cuex_t tree, cu_word_t key); 00092 00093 /** As \ref cuex_atree_find, but returns the index of \a key, or \c (size_t)-1 00094 ** if not found. Note that the complexity of this call is linear in the 00095 ** cardinality of \a tree. */ 00096 size_t 00097 cuex_atree_find_index(cu_clop(get_key, cu_word_t, cuex_t), 00098 cuex_t tree, cu_word_t key); 00099 00100 /** If the key of \a value is not already in \a tree, returns the result of 00101 ** inserting \a value into \a tree, else returns \a tree. */ 00102 cuex_t 00103 cuex_atree_insert(cu_clop(get_key, cu_word_t, cuex_t), 00104 cuex_t tree, cuex_t value); 00105 00106 /** If the key of \a value is in \a tree, then replace the element with \a 00107 ** value, otherwise insert \a value. */ 00108 cuex_t 00109 cuex_atree_replace(cu_clop(get_key, cu_word_t, cuex_t), 00110 cuex_t tree, cuex_t value); 00111 00112 /** As \ref cuex_atree_insert, but if a key-equal element \e e is present in \a 00113 ** tree, replace it with <code>\a merge_values(\e e, \a value)</code>. */ 00114 cuex_t 00115 cuex_atree_deep_insert(cu_clop(get_key, cu_word_t, cuex_t leaf), 00116 cu_clop(merge, cuex_t, cuex_t leaf0, cuex_t leaf1), 00117 cuex_t tree, cuex_t value); 00118 00119 /** If \a erase_key is in \a tree, returns \a tree with the value corresponding 00120 ** to \a erase_key erased, otherwise returns \a tree. */ 00121 cuex_t 00122 cuex_atree_erase(cu_clop(get_key, cu_word_t, cuex_t), 00123 cuex_t tree, cu_word_t erase_key); 00124 00125 /** If \c *\a tree has a node where \a get_key returns \a erase_key, updates 00126 ** <code>*\a tree</code> by removing this node and returns the node, otherwise 00127 ** returns \c NULL. */ 00128 cuex_t 00129 cuex_atree_find_erase(cu_clop(get_key, cu_word_t, cuex_t), 00130 cuex_t *tree, cu_word_t erase_key); 00131 00132 /** Returns the union of \a tree0 and \a tree1, considering two elements equal 00133 ** if the corresponding values returned by \a get_key are equal. For common 00134 ** nodes, those from \a tree0 are used in the result. */ 00135 cuex_t 00136 cuex_atree_left_union(cu_clop(get_key, cu_word_t, cuex_t), 00137 cuex_t tree0, cuex_t tree1); 00138 00139 /** As \ref cuex_atree_left_union except \c NULL is returned in case \a tree0 00140 ** and \a tree1 coincides on any of their keys. */ 00141 cuex_t 00142 cuex_atree_disjoint_union(cu_clop(get_key, cu_word_t, cuex_t), 00143 cuex_t tree0, cuex_t tree1); 00144 00145 /** As \ref cuex_atree_left_union, except merge any duplicate element with \a 00146 ** merge_values. If \a merge at some point returns \c NULL, the algorithm 00147 ** terminates and returns \c NULL. */ 00148 cuex_t 00149 cuex_atree_deep_union(cu_clop(get_key, cu_word_t, cuex_t), 00150 cu_clop(merge, cuex_t, cuex_t leaf0, cuex_t leaf1), 00151 cuex_t tree0, cuex_t tree1); 00152 00153 /** Returns the intersection of \a tree0 and \a tree1, considering two elements 00154 ** equal if the corresponding values returned by \a get_key are equal. The 00155 ** nodes from \a tree0 are used in the result. */ 00156 cuex_t 00157 cuex_atree_left_isecn(cu_clop(get_key, cu_word_t, cuex_t), 00158 cuex_t tree0, cuex_t tree1); 00159 00160 /** As \ref cuex_atree_left_isecn, but merge intersecting elements from \a 00161 ** tree0 and \a tree1 using \a merge_values. */ 00162 cuex_t 00163 cuex_atree_deep_isecn(cu_clop(get_key, cu_word_t, cuex_t), 00164 cu_clop(merge, cuex_t, cuex_t leaf0, cuex_t leaf1), 00165 cuex_t tree0, cuex_t tree1); 00166 00167 /** True iff \a tree0 ⊆ \a tree1 where elements are considered equal iff their 00168 ** \a get_key values are equal. */ 00169 cu_bool_t cuex_atree_subseteq(cu_clop(get_key, cu_word_t, cuex_t), 00170 cuex_t tree0, cuex_t tree1); 00171 00172 /** As \ref cuex_atree_subseteq, except for any pair (\e e0, \e e1) of elements 00173 ** of (\a tree0, \a tree1) with equal keys, return false unless <code>\a 00174 ** value_subseteq(\e e0, \e e1)</code> returns true. */ 00175 cu_bool_t 00176 cuex_atree_deep_subseteq(cu_clop(get_key, cu_word_t, cuex_t), 00177 cu_clop(value_subseteq, cu_bool_t, cuex_t, cuex_t), 00178 cuex_t tree0, cuex_t tree1); 00179 00180 /** Returns the ordering of \a tree0 and \a tree1, where elements are 00181 ** considered equal iff their \a get_key values are equal. */ 00182 cu_order_t cuex_atree_order(cu_clop(get_key, cu_word_t, cuex_t), 00183 cuex_t tree0, cuex_t tree1); 00184 00185 /** A variant of \a cuex_atree_order which also takes into account value 00186 ** ordering. Whenever the keys of two elements are equal, either \a 00187 ** value_subseteq or \a value_order is used to determine their ordering. The 00188 ** latter function is used when one of the two possible orderings of the trees 00189 ** have been excluded. The use of two ordering callbacks is purely an 00190 ** optimisation which may be hidden by a high-level interface; either callback 00191 ** can be implemented in terms of the other. */ 00192 cu_order_t 00193 cuex_atree_deep_order(cu_clop(get_key, cu_word_t, cuex_t), 00194 cu_clop(value_subseteq, cu_bool_t, cuex_t, cuex_t), 00195 cu_clop(value_order, cu_order_t, cuex_t, cuex_t), 00196 cuex_t tree0, cuex_t tree1); 00197 00198 /** Call \a f with each value in \a tree. */ 00199 void cuex_atree_iter(cuex_t tree, cu_clop(f, void, cuex_t leaf)); 00200 00201 /** Returns the conjunction af \a f applied to all keys in \a tree. Stops as 00202 ** soon as \a f returns false. */ 00203 cu_bool_t cuex_atree_conj(cuex_t tree, cu_clop(f, cu_bool_t, cuex_t leaf)); 00204 00205 /** Returns the image of \a tree under \a f. Note that \a get_key is only used 00206 ** for building the result, and may in fact be different from the \a get_key 00207 ** which was used to build \a tree (thus its order in the argument list). If 00208 ** \a f leaves the key of its argument unchanged, see \ref 00209 ** cuex_atree_isokey_image for a faster alternative. */ 00210 cuex_t cuex_atree_image(cuex_t tree, cu_clop(f, cuex_t, cuex_t), 00211 cu_clop(get_key, cu_word_t, cuex_t leaf)); 00212 00213 /** Returns the image of \a tree under \a f assuming \a f does not change the 00214 ** key of it's argument. The key referred to is the result of the \e get_key 00215 ** used to build the container \ref cuex_atree_insert, so the condition is 00216 ** that \e get_key(\a f(\e e)) = \e get_key(\e e) for all elements \e e in \a 00217 ** tree. If this condition is not met see \ref cuex_atree_image. */ 00218 cuex_t cuex_atree_isokey_image(cuex_t tree, cu_clop(f, cuex_t, cuex_t leaf)); 00219 00220 /** The depth of the deepest tree node of \a tree. The empty tree and 00221 ** singletons have depth 0. A tree node has depth one plus the maximum of the 00222 ** depths of its branches. */ 00223 int cuex_atree_depth(cuex_t tree); 00224 00225 /** Cardinality (number of elements) of \a tree. Note that the complexity of 00226 ** this call is linear in the cardinality of \a tree. */ 00227 size_t cuex_atree_card(cuex_t tree); 00228 00229 00230 /** \name Iterator Support 00231 ** @{ 00232 ** The following can be used to implement iterators for expression types 00233 ** defined in terms of associated trees. */ 00234 00235 /** The size required by an iterator over \a tree. */ 00236 size_t cuex_atree_itr_size(cuex_t tree); 00237 00238 /** Initialise an \a itr as an iterator over all elements of \a tree, where \a 00239 ** itr points to memory of at least <code>\ref cuex_atree_itr_size(\a 00240 ** tree)</code> bytes. */ 00241 void cuex_atree_itr_init(void *itr, cuex_t tree); 00242 00243 /** Pop off and return the next subtree from \a itr, or return \c NULL if \a 00244 ** itr is empty. */ 00245 cuex_t cuex_atree_itr_get(void *itr); 00246 00247 /** Pop off the next \e subtree from \a itr and return <code>cucon_opn_at(\e 00248 ** subtree, 1)</code>, or return \c NULL if \a itr is empty. */ 00249 cuex_t cuex_atree_itr_get_at_1(void *itr); 00250 00251 00252 /** @} 00253 ** \name Specialisations Acting on a Certain Operand of the Members 00254 ** @{ 00255 ** The following functions are specialised variants of the corresponding 00256 ** functions from the primary API, where the leafs are assumed to be 00257 ** operations of sufficient arity, and callbacks acting on leaves are replaced 00258 ** by callbacks acting on a given operand of the leaves. The caller is 00259 ** responsible of ensuring that all leafs have the proper form. 00260 **/ 00261 00262 /** As \ref cuex_atree_deep_insert, but merge only operand \a merge_index of 00263 ** values. */ 00264 cuex_t 00265 cuex_atree_deep_insert_iv(cu_clop(get_key, cu_word_t, cuex_t), 00266 cu_rank_t merge_index, 00267 cu_clop(merge_fn, cuex_t, cuex_t val0, cuex_t val1), 00268 cuex_t tree, cuex_t value); 00269 00270 /** As \ref cuex_atree_deep_union, except that \a merge_fn only acts on operand 00271 ** \a merge_index of the leaves. */ 00272 cuex_t 00273 cuex_atree_deep_union_iv(cu_clop(get_key, cu_word_t, cuex_t), 00274 cu_rank_t merge_index, 00275 cu_clop(merge_fn, cuex_t, cuex_t val0, cuex_t val1), 00276 cuex_t tree0, cuex_t tree1); 00277 00278 /** As \ref cuex_atree_deep_isecn, but \a merge_fn only merges operand \a 00279 ** merge_index. */ 00280 cuex_t 00281 cuex_atree_deep_isecn_iv(cu_clop(get_key, cu_word_t, cuex_t), 00282 cu_rank_t merge_index, 00283 cu_clop(merge_fn, cuex_t, cuex_t val0, cuex_t val1), 00284 cuex_t tree0, cuex_t tree1); 00285 00286 /** As \ref cuex_atree_deep_order, but only pass operand \a value_index of the 00287 ** leaves to the ordering functions. */ 00288 cu_order_t 00289 cuex_atree_deep_order_iv(cu_clop(get_key, cu_word_t, cuex_t), 00290 cu_rank_t value_index, 00291 cu_clop(value_subseteq, cu_bool_t, cuex_t, cuex_t), 00292 cu_clop(value_order, cu_order_t, cuex_t, cuex_t), 00293 cuex_t tree0, cuex_t tree1); 00294 00295 /** A variant of \a cuex_atree_conj which expects elements to be operations of 00296 ** at least \a value_index + 1 operands, and calls \a f with operand \a 00297 ** value_index. */ 00298 cu_bool_t cuex_atree_conj_iv(cuex_t tree, cu_rank_t value_index, 00299 cu_clop(f, cu_bool_t, cuex_t val)); 00300 00301 /** A variant of \ref cuex_atree_isokey_image which assumes that elements are 00302 ** operations of arity at least \a value_index + 1, and transforms only 00303 ** operand \a value_index of the elements. This specialisation applies to 00304 ** map-like types with inert keys, such as \ref cuex_labelling_h "labellings". 00305 **/ 00306 cuex_t cuex_atree_isokey_image_iv(cuex_t tree, cu_rank_t value_index, 00307 cu_clop(f, cuex_t, cuex_t val)); 00308 00309 00310 00311 /** @} 00312 ** \name Specialisations for Key-Value Formed Members 00313 ** @{ 00314 ** The following functions are specialised variants of the corresponding 00315 ** functions from the primary API, where the leafs are assumed to be binary 00316 ** operations where the first operand serves as a key and the second operand 00317 ** serves as a value. Callbacks generally receive the key as the first 00318 ** argument and one or two values as the next arguments. 00319 **/ 00320 00321 /** As \ref cuex_atree_deep_insert, but assume leafs are key-value binary 00322 ** operations. \a merge receives the common first operand (key) and each of 00323 ** the second operands (values) and shall return the merged value. */ 00324 cuex_t 00325 cuex_atree_deep_insert_kv(cu_clop(merge, cuex_t, 00326 cuex_t key, cuex_t val0, cuex_t val1), 00327 cuex_t tree, cuex_t value); 00328 00329 /** As \ref cuex_atree_deep_union, except that \a merge_fn only acts on the 00330 ** second operand of leafs and also receives the first operand (the key). */ 00331 cuex_t 00332 cuex_atree_deep_union_kv(cu_clop(merge, cuex_t, 00333 cuex_t key, cuex_t val0, cuex_t val1), 00334 cuex_t tree0, cuex_t tree1); 00335 00336 /** As \ref cuex_atree_deep_isecn, except it assumes the first operand of 00337 ** leaves are keys and the second oprand are values. \a merge receives the 00338 ** common keys and the two values to be merged. */ 00339 cuex_t 00340 cuex_atree_deep_isecn_kv(cu_clop(merge, cuex_t, 00341 cuex_t key, cuex_t val0, cuex_t val1), 00342 cuex_t tree0, cuex_t tree1); 00343 00344 /** As \ref cuex_atree_deep_order, but assume leafs are operations where the 00345 ** first operand are keys and the second are values. The common key and the 00346 ** values to compare are passed to the ordering functions. */ 00347 cu_order_t 00348 cuex_atree_deep_order_kv(cu_clop(value_subseteq, cu_bool_t, 00349 cuex_t key, cuex_t val0, cuex_t val1), 00350 cu_clop(value_order, cu_order_t, 00351 cuex_t key, cuex_t val0, cuex_t val1), 00352 cuex_t tree0, cuex_t tree1); 00353 00354 /** A variant of \a cuex_atree_conj which expects that elements are operations 00355 ** of at least 2 operands, and calls back \a f with the first two operands of 00356 ** the elements. This specialisation applies to implementations of map-like 00357 ** types such as \ref cuex_labelling_h "labellings". */ 00358 cu_bool_t cuex_atree_conj_kv(cuex_t tree, 00359 cu_clop(f, cu_bool_t, cuex_t key, cuex_t val)); 00360 00361 /** A variant of \ref cuex_atree_isokey_image which assumes elements to be 00362 ** operations of arity at least 2, and transforms the second operand. Both 00363 ** the first and second operands are passed to \a f in order. This is suited 00364 ** for map-like types where the first operand is an inert key and the second 00365 ** operand is a transformable value. */ 00366 cuex_t cuex_atree_isokey_image_kv(cuex_t tree, 00367 cu_clop(f, cuex_t, cuex_t key, cuex_t val)); 00368 00369 /** @} 00370 ** @} */ 00371 CU_END_DECLARATIONS 00372 00373 #endif