1 // Generated by gmmproc 2.64.2 -- DO NOT MODIFY! 2 #ifndef _GLIBMM_BALANCEDTREE_H 3 #define _GLIBMM_BALANCEDTREE_H 4 5 6 /* Copyright (C) 2010 Szilárd Pfeiffer <mailbox@pfeifferszilard.hu> 7 * 8 * This library is free software; you can redistribute it and/or 9 * modify it under the terms of the GNU Library General Public 10 * License as published by the Free Software Foundation; either 11 * version 2 of the License, or (at your option) any later version. 12 * 13 * This library is distributed in the hope that it will be useful, 14 * but WITHOUT ANY WARRANTY; without even the implied warranty of 15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 16 * Library General Public License for more details. 17 * 18 * You should have received a copy of the GNU Library General Public 19 * License along with this library. If not, see <http://www.gnu.org/licenses/>. 20 */ 21 22 23 #include <glibmm/refptr.h> 24 #include <glibmm/ustring.h> 25 #include <glibmm/error.h> 26 #include <glibmm/arrayhandle.h> 27 #include <glib.h> 28 29 namespace Glib 30 { 31 32 /** Balanced Binary Trees — a sorted collection of key/value pairs optimized for searching and traversing in order. 33 * The BalancedTree structure and its associated functions provide a sorted 34 * collection of key/value pairs optimized for searching and traversing in 35 * order. 36 * 37 * To insert a key/value pair into a BalancedTree use insert(). 38 * 39 * To lookup the value corresponding to a given key, use lookup(). 40 * 41 * To find out the number of nodes in a BalancedTree, use nnodes(). To get the height of a BalancedTree, use height(). 42 * 43 * To traverse a BalancedTree, calling a function for each node visited in the traversal, use foreach(). 44 * 45 * To remove a key/value pair use remove(). 46 * 47 * Any type to be used with this template must implement copy constructor. 48 * Compiler-generated implementations are OK, provided they do the right 49 * thing for the type. Both keys and values are stored in the balanced binary 50 * tree as copies, created by copy contructors. 51 * 52 * Type of key to be used with this template must implement: 53 * - less than operator 54 * - greater than operator 55 * 56 * @newin{2,24} 57 */ 58 template <typename K, typename V> 59 class BalancedTree 60 { 61 public: 62 #ifndef DOXYGEN_SHOULD_SKIP_THIS 63 using CppObjectType = BalancedTree; 64 using BaseObjectType = GTree; 65 #endif /* DOXYGEN_SHOULD_SKIP_THIS */ 66 67 private: 68 69 public: 70 using TraverseFunc = sigc::slot<bool, const K&, const V&>; 71 using CompareFunc = sigc::slot<int, const K&, const K&>; 72 73 protected: BalancedTree()74 BalancedTree() : 75 key_compare_slot(sigc::ptr_fun(key_compare)) 76 { 77 gobject_ = g_tree_new_full(on_compare_tree, &key_compare_slot, on_destroy_key, on_destroy_value); 78 } 79 BalancedTree(const CompareFunc & key_compare_slot_)80 BalancedTree(const CompareFunc &key_compare_slot_) : 81 key_compare_slot(key_compare_slot_) 82 { 83 gobject_ = g_tree_new_full(on_compare_tree, &key_compare_slot, on_destroy_key, on_destroy_value); 84 } 85 86 //TODO: Add move operations, being careful of universal references and overload resolution. 87 88 public: create()89 static Glib::RefPtr< BalancedTree<K, V> > create() 90 { 91 return Glib::RefPtr< BalancedTree<K, V> >(new BalancedTree()); 92 } 93 create(const CompareFunc & key_compare_slot)94 static Glib::RefPtr< BalancedTree<K, V> > create(const CompareFunc &key_compare_slot) 95 { 96 return Glib::RefPtr< BalancedTree<K, V> >(new BalancedTree(key_compare_slot)); 97 } 98 ~BalancedTree()99 ~BalancedTree() 100 { 101 g_tree_destroy(gobject_); 102 } 103 104 105 /// Provides access to the underlying C GObject. gobj()106 inline GTree* gobj() 107 { 108 return gobject_; 109 } 110 111 /// Provides access to the underlying C GObject. gobj()112 inline const GTree* gobj() const 113 { 114 return gobject_; 115 } 116 117 /** Increments the reference count of tree by one. It is safe to call 118 * this function from any thread. 119 */ reference()120 void reference() 121 { 122 g_tree_ref(gobject_); 123 } 124 125 126 /** Decrements the reference count of tree by one. If the reference count 127 * drops to 0, all keys and values will be destroyed and all memory allocated 128 * by tree will be released. 129 * 130 * It is safe to call this function from any thread. 131 */ unreference()132 void unreference() 133 { 134 g_tree_unref(gobject_); 135 } 136 137 138 /** Inserts a key/value pair into a BalancedTree. If the given key already 139 * exists in the BalancedTree its corresponding value is set to the new 140 * value. 141 * 142 * The tree is automatically 'balanced' as new key/value pairs are added, 143 * so that the distance from the root to every leaf is as small as possible. 144 * 145 * @param key The key to insert. 146 * @param value The value corresponding to the key. 147 */ insert(const K & key,const V & value)148 void insert(const K &key, const V &value) 149 { 150 g_tree_insert(gobj(), reinterpret_cast<void *>(new K(key)), reinterpret_cast<void *>(new V(value))); 151 } 152 153 154 /** Removes a key/value pair from a BalancedTree. 155 * 156 * If the key does not exist in the BalancedTree, the function does nothing. 157 * 158 * @param key The key to remove. 159 * @result true if the key was found (prior to 2.8, this function returned 160 * nothing) 161 */ remove(const K & key)162 bool remove(const K &key) 163 { 164 return g_tree_remove(const_cast<GTree*>(gobj()), &key); 165 } 166 167 168 /** Gets the value corresponding to the given key. Since a BalancedTree is 169 * automatically balanced as key/value pairs are added, key lookup is very 170 * fast. 171 * 172 * @param key The key to look up. 173 * @result The value corresponding to the key, or <tt>nullptr</tt> if the key was 174 * not found. 175 */ lookup(const K & key)176 V* lookup(const K &key) 177 { 178 return reinterpret_cast<V *>(g_tree_lookup(gobj(), &key)); 179 } 180 181 lookup(const K & key)182 const V* lookup(const K &key) const 183 { 184 return reinterpret_cast<const V *>(g_tree_lookup(gobj(), &key)); 185 } 186 187 188 /** Gets the height of a BalancedTree. 189 * 190 * If the BalancedTree contains no nodes, the height is 0. 191 * If the BalancedTree contains only one root node the height is 1. 192 * If the root node has children the height is 2, etc. 193 * 194 * @result the height of the BalancedTree. 195 */ height()196 gint height() const 197 { 198 return g_tree_height(const_cast<GTree*>(gobj())); 199 } 200 201 202 /** Gets the number of nodes in a BalancedTree. 203 * 204 * @result the number of nodes in the BalancedTree. 205 */ nnodes()206 gint nnodes() const 207 { 208 return g_tree_nnodes(const_cast<GTree*>(gobj())); 209 } 210 211 212 /** Calls the given function for each of the key/value pairs in the 213 * BalancedTree. 214 * The function is passed the key and value of each pair. The tree is 215 * traversed in sorted order. 216 * 217 * The tree may not be modified while iterating over it (you can't 218 * add/remove items). To remove all items matching a predicate, you need 219 * to add each item to a list in your TraverseFunc as you walk over 220 * the tree, then walk the list and remove each item. 221 * 222 * @param func The function to call for each node visited. If this function 223 * returns true, the traversal is stopped. 224 */ foreach(const TraverseFunc & func)225 void foreach(const TraverseFunc& func) const 226 { 227 TraverseFunc func_copy = func; 228 g_tree_foreach(const_cast<GTree*>(gobj()), c_callback_traverse, reinterpret_cast<gpointer>(&func_copy)); 229 } 230 ; 231 232 /** Searches a BalancedTree using @a search_func. 233 * 234 * The @a search_func is called with a reference to the key of a key/value pair 235 * in the tree. If @a search_func returns 0 for a key/value pair, then search() 236 * will return the value of that pair. If @a search_func returns -1, searching 237 * will proceed among the key/value pairs that have a smaller key; if 238 * @a search_func returns 1, searching will proceed among the key/value pairs 239 * that have a larger key. 240 * 241 * @param search_func A function used to search the BalancedTree. 242 * @param key The key to search for. 243 * @result The value corresponding to the found key, or <tt>nullptr</tt> if the key 244 * was not found. 245 */ search(const CompareFunc & search_func,const K & key)246 V* search(const CompareFunc &search_func, const K& key) 247 { 248 sigc::slot<int, const K&, const CompareFunc&, const K&> real_slot = sigc::ptr_fun(on_compare_key); 249 sigc::slot<int, const K&> bound_slot = sigc::bind(real_slot, search_func, key); 250 gpointer value = g_tree_search(gobj(), c_callback_search, reinterpret_cast<gconstpointer>(&bound_slot)); 251 252 return reinterpret_cast<V*>(value); 253 } 254 255 /** Searches a BalancedTree using @a search_func. 256 * 257 * The @a search_func is called with a reference to the key of a key/value pair 258 * in the tree. If @a search_func returns 0 for a key/value pair, then search() 259 * will return the value of that pair. If @a search_func returns -1, searching 260 * will proceed among the key/value pairs that have a smaller key; if 261 * @a search_func returns 1, searching will proceed among the key/value pairs 262 * that have a larger key. 263 * 264 * @param search_func A function used to search the BalancedTree. 265 * @param key The key to search for. 266 * @result The value corresponding to the found key, or <tt>nullptr</tt> if the key 267 * was not found. 268 */ search(const CompareFunc & search_func,const K & key)269 const V* search(const CompareFunc &search_func, const K& key) const 270 { 271 return const_cast<BalancedTree<K, V>*>(this)->search(search_func, key); 272 } 273 274 275 // The following functions don't make sense for the C++ wrapper. 276 277 278 private: 279 /// Method for comparing keys by func (Internal use). on_compare_key(const K & key_a,const CompareFunc & func,const K & key_b)280 static gint on_compare_key(const K& key_a, const CompareFunc& func, const K& key_b) 281 { 282 return func(key_a, key_b); 283 } 284 285 /// Wrapper for invoking GCompareFunc. c_callback_search(gconstpointer a,gconstpointer b)286 static gint c_callback_search(gconstpointer a, gconstpointer b) 287 { 288 const sigc::slot<int, const K&>* slot = reinterpret_cast<const sigc::slot<int, const K&> *>(b); 289 return (*slot)(*reinterpret_cast<const K*>(a)); 290 } 291 292 /// Wrapper for invoking GTraverseFunc. c_callback_traverse(gpointer key,gpointer value,gpointer slot)293 static gboolean c_callback_traverse(gpointer key, gpointer value, gpointer slot) 294 { 295 const TraverseFunc* tf = reinterpret_cast<const TraverseFunc*>(slot); 296 return (*tf)(*reinterpret_cast<const K*>(key), *reinterpret_cast<const V*>(value)); 297 } 298 299 /// Method for comparing key values (Internal use). on_compare_tree(gconstpointer a,gconstpointer b,gpointer data)300 static gint on_compare_tree(gconstpointer a, gconstpointer b, gpointer data) 301 { 302 const K& key_a = *reinterpret_cast<const K*>(a); 303 const K& key_b = *reinterpret_cast<const K*>(b); 304 const CompareFunc& func = *reinterpret_cast<const CompareFunc*>(data); 305 306 return func(key_a, key_b); 307 } 308 309 /// Method for destroying keys (Internal use). on_destroy_key(gpointer data)310 static void on_destroy_key(gpointer data) 311 { 312 K* key = reinterpret_cast<K*>(data); 313 delete key; 314 } 315 316 /// Method for destroying values (Internal use). on_destroy_value(gpointer data)317 static void on_destroy_value(gpointer data) 318 { 319 V* value = reinterpret_cast<V*>(data); 320 delete value; 321 } 322 323 /// Key compare function when it is not by the user (Internal use). key_compare(const K & key_a,const K & key_b)324 static int key_compare(const K& key_a, const K& key_b) 325 { 326 if(key_a < key_b) 327 return -1; 328 329 if(key_a > key_b) 330 return 1; 331 332 return 0; 333 } 334 335 GTree* gobject_; 336 CompareFunc key_compare_slot; 337 338 339 }; 340 341 } // namespace Glib 342 343 344 #endif /* _GLIBMM_BALANCEDTREE_H */ 345 346