1 /* 2 * This file is part of gtkD. 3 * 4 * gtkD is free software; you can redistribute it and/or modify 5 * it under the terms of the GNU Lesser General Public License 6 * as published by the Free Software Foundation; either version 3 7 * of the License, or (at your option) any later version, with 8 * some exceptions, please read the COPYING file. 9 * 10 * gtkD 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 Lesser General Public License for more details. 14 * 15 * You should have received a copy of the GNU Lesser General Public License 16 * along with gtkD; if not, write to the Free Software 17 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110, USA 18 */ 19 20 // generated automatically - do not change 21 // find conversion definition on APILookup.txt 22 // implement new conversion functionalities on the wrap.utils pakage 23 24 25 module glib.BBTree; 26 27 private import glib.ConstructionException; 28 private import glib.TreeNode; 29 private import glib.c.functions; 30 public import glib.c.types; 31 private import gtkd.Loader; 32 33 34 /** 35 * The GTree struct is an opaque data structure representing a 36 * [balanced binary tree][glib-Balanced-Binary-Trees]. It should be 37 * accessed only by using the following functions. 38 */ 39 public class BBTree 40 { 41 /** the main Gtk struct */ 42 protected GTree* gTree; 43 protected bool ownedRef; 44 45 /** Get the main Gtk struct */ 46 public GTree* getBBTreeStruct(bool transferOwnership = false) 47 { 48 if (transferOwnership) 49 ownedRef = false; 50 return gTree; 51 } 52 53 /** the main Gtk struct as a void* */ 54 protected void* getStruct() 55 { 56 return cast(void*)gTree; 57 } 58 59 /** 60 * Sets our main struct and passes it to the parent class. 61 */ 62 public this (GTree* gTree, bool ownedRef = false) 63 { 64 this.gTree = gTree; 65 this.ownedRef = ownedRef; 66 } 67 68 ~this () 69 { 70 if ( Linker.isLoaded(LIBRARY_GLIB) && ownedRef ) 71 g_tree_unref(gTree); 72 } 73 74 75 /** 76 * Creates a new #GTree. 77 * 78 * Params: 79 * keyCompareFunc = the function used to order the nodes in the #GTree. 80 * It should return values similar to the standard strcmp() function - 81 * 0 if the two arguments are equal, a negative value if the first argument 82 * comes before the second, or a positive value if the first argument comes 83 * after the second. 84 * 85 * Returns: a newly allocated #GTree 86 * 87 * Throws: ConstructionException GTK+ fails to create the object. 88 */ 89 public this(GCompareFunc keyCompareFunc) 90 { 91 auto __p = g_tree_new(keyCompareFunc); 92 93 if(__p is null) 94 { 95 throw new ConstructionException("null returned by new"); 96 } 97 98 this(cast(GTree*) __p); 99 } 100 101 /** 102 * Creates a new #GTree like g_tree_new() and allows to specify functions 103 * to free the memory allocated for the key and value that get called when 104 * removing the entry from the #GTree. 105 * 106 * Params: 107 * keyCompareFunc = qsort()-style comparison function 108 * keyCompareData = data to pass to comparison function 109 * keyDestroyFunc = a function to free the memory allocated for the key 110 * used when removing the entry from the #GTree or %NULL if you don't 111 * want to supply such a function 112 * valueDestroyFunc = a function to free the memory allocated for the 113 * value used when removing the entry from the #GTree or %NULL if you 114 * don't want to supply such a function 115 * 116 * Returns: a newly allocated #GTree 117 * 118 * Throws: ConstructionException GTK+ fails to create the object. 119 */ 120 public this(GCompareDataFunc keyCompareFunc, void* keyCompareData, GDestroyNotify keyDestroyFunc, GDestroyNotify valueDestroyFunc) 121 { 122 auto __p = g_tree_new_full(keyCompareFunc, keyCompareData, keyDestroyFunc, valueDestroyFunc); 123 124 if(__p is null) 125 { 126 throw new ConstructionException("null returned by new_full"); 127 } 128 129 this(cast(GTree*) __p); 130 } 131 132 /** 133 * Creates a new #GTree with a comparison function that accepts user data. 134 * See g_tree_new() for more details. 135 * 136 * Params: 137 * keyCompareFunc = qsort()-style comparison function 138 * keyCompareData = data to pass to comparison function 139 * 140 * Returns: a newly allocated #GTree 141 * 142 * Throws: ConstructionException GTK+ fails to create the object. 143 */ 144 public this(GCompareDataFunc keyCompareFunc, void* keyCompareData) 145 { 146 auto __p = g_tree_new_with_data(keyCompareFunc, keyCompareData); 147 148 if(__p is null) 149 { 150 throw new ConstructionException("null returned by new_with_data"); 151 } 152 153 this(cast(GTree*) __p); 154 } 155 156 /** 157 * Removes all keys and values from the #GTree and decreases its 158 * reference count by one. If keys and/or values are dynamically 159 * allocated, you should either free them first or create the #GTree 160 * using g_tree_new_full(). In the latter case the destroy functions 161 * you supplied will be called on all keys and values before destroying 162 * the #GTree. 163 */ 164 public void destroy() 165 { 166 g_tree_destroy(gTree); 167 } 168 169 alias foreac = foreach_; 170 /** 171 * Calls the given function for each of the key/value pairs in the #GTree. 172 * The function is passed the key and value of each pair, and the given 173 * @data parameter. The tree is traversed in sorted order. 174 * 175 * The tree may not be modified while iterating over it (you can't 176 * add/remove items). To remove all items matching a predicate, you need 177 * to add each item to a list in your #GTraverseFunc as you walk over 178 * the tree, then walk the list and remove each item. 179 * 180 * Params: 181 * func = the function to call for each node visited. 182 * If this function returns %TRUE, the traversal is stopped. 183 * userData = user data to pass to the function 184 */ 185 public void foreach_(GTraverseFunc func, void* userData) 186 { 187 g_tree_foreach(gTree, func, userData); 188 } 189 190 /** 191 * Calls the given function for each of the nodes in the #GTree. 192 * The function is passed the pointer to the particular node, and the given 193 * @data parameter. The tree traversal happens in-order. 194 * 195 * The tree may not be modified while iterating over it (you can't 196 * add/remove items). To remove all items matching a predicate, you need 197 * to add each item to a list in your #GTraverseFunc as you walk over 198 * the tree, then walk the list and remove each item. 199 * 200 * Params: 201 * func = the function to call for each node visited. 202 * If this function returns %TRUE, the traversal is stopped. 203 * userData = user data to pass to the function 204 * 205 * Since: 2.68 206 */ 207 public void foreachNode(GTraverseNodeFunc func, void* userData) 208 { 209 g_tree_foreach_node(gTree, func, userData); 210 } 211 212 /** 213 * Gets the height of a #GTree. 214 * 215 * If the #GTree contains no nodes, the height is 0. 216 * If the #GTree contains only one root node the height is 1. 217 * If the root node has children the height is 2, etc. 218 * 219 * Returns: the height of @tree 220 */ 221 public int height() 222 { 223 return g_tree_height(gTree); 224 } 225 226 /** 227 * Inserts a key/value pair into a #GTree. 228 * 229 * Inserts a new key and value into a #GTree as g_tree_insert_node() does, 230 * only this function does not return the inserted or set node. 231 * 232 * Params: 233 * key = the key to insert 234 * value = the value corresponding to the key 235 */ 236 public void insert(void* key, void* value) 237 { 238 g_tree_insert(gTree, key, value); 239 } 240 241 /** 242 * Inserts a key/value pair into a #GTree. 243 * 244 * If the given key already exists in the #GTree its corresponding value 245 * is set to the new value. If you supplied a @value_destroy_func when 246 * creating the #GTree, the old value is freed using that function. If 247 * you supplied a @key_destroy_func when creating the #GTree, the passed 248 * key is freed using that function. 249 * 250 * The tree is automatically 'balanced' as new key/value pairs are added, 251 * so that the distance from the root to every leaf is as small as possible. 252 * The cost of maintaining a balanced tree while inserting new key/value 253 * result in a O(n log(n)) operation where most of the other operations 254 * are O(log(n)). 255 * 256 * Params: 257 * key = the key to insert 258 * value = the value corresponding to the key 259 * 260 * Returns: the inserted (or set) node. 261 * 262 * Since: 2.68 263 */ 264 public TreeNode insertNode(void* key, void* value) 265 { 266 auto __p = g_tree_insert_node(gTree, key, value); 267 268 if(__p is null) 269 { 270 return null; 271 } 272 273 return new TreeNode(cast(GTreeNode*) __p); 274 } 275 276 /** 277 * Gets the value corresponding to the given key. Since a #GTree is 278 * automatically balanced as key/value pairs are added, key lookup 279 * is O(log n) (where n is the number of key/value pairs in the tree). 280 * 281 * Params: 282 * key = the key to look up 283 * 284 * Returns: the value corresponding to the key, or %NULL 285 * if the key was not found 286 */ 287 public void* lookup(void* key) 288 { 289 return g_tree_lookup(gTree, key); 290 } 291 292 /** 293 * Looks up a key in the #GTree, returning the original key and the 294 * associated value. This is useful if you need to free the memory 295 * allocated for the original key, for example before calling 296 * g_tree_remove(). 297 * 298 * Params: 299 * lookupKey = the key to look up 300 * origKey = returns the original key 301 * value = returns the value associated with the key 302 * 303 * Returns: %TRUE if the key was found in the #GTree 304 */ 305 public bool lookupExtended(void* lookupKey, out void* origKey, out void* value) 306 { 307 return g_tree_lookup_extended(gTree, lookupKey, &origKey, &value) != 0; 308 } 309 310 /** 311 * Gets the tree node corresponding to the given key. Since a #GTree is 312 * automatically balanced as key/value pairs are added, key lookup 313 * is O(log n) (where n is the number of key/value pairs in the tree). 314 * 315 * Params: 316 * key = the key to look up 317 * 318 * Returns: the tree node corresponding to 319 * the key, or %NULL if the key was not found 320 * 321 * Since: 2.68 322 */ 323 public TreeNode lookupNode(void* key) 324 { 325 auto __p = g_tree_lookup_node(gTree, key); 326 327 if(__p is null) 328 { 329 return null; 330 } 331 332 return new TreeNode(cast(GTreeNode*) __p); 333 } 334 335 /** 336 * Gets the lower bound node corresponding to the given key, 337 * or %NULL if the tree is empty or all the nodes in the tree 338 * have keys that are strictly lower than the searched key. 339 * 340 * The lower bound is the first node that has its key greater 341 * than or equal to the searched key. 342 * 343 * Params: 344 * key = the key to calculate the lower bound for 345 * 346 * Returns: the tree node corresponding to 347 * the lower bound, or %NULL if the tree is empty or has only 348 * keys strictly lower than the searched key. 349 * 350 * Since: 2.68 351 */ 352 public TreeNode lowerBound(void* key) 353 { 354 auto __p = g_tree_lower_bound(gTree, key); 355 356 if(__p is null) 357 { 358 return null; 359 } 360 361 return new TreeNode(cast(GTreeNode*) __p); 362 } 363 364 /** 365 * Gets the number of nodes in a #GTree. 366 * 367 * Returns: the number of nodes in @tree 368 */ 369 public int nnodes() 370 { 371 return g_tree_nnodes(gTree); 372 } 373 374 /** 375 * Returns the first in-order node of the tree, or %NULL 376 * for an empty tree. 377 * 378 * Returns: the first node in the tree 379 * 380 * Since: 2.68 381 */ 382 public TreeNode nodeFirst() 383 { 384 auto __p = g_tree_node_first(gTree); 385 386 if(__p is null) 387 { 388 return null; 389 } 390 391 return new TreeNode(cast(GTreeNode*) __p); 392 } 393 394 /** 395 * Returns the last in-order node of the tree, or %NULL 396 * for an empty tree. 397 * 398 * Returns: the last node in the tree 399 * 400 * Since: 2.68 401 */ 402 public TreeNode nodeLast() 403 { 404 auto __p = g_tree_node_last(gTree); 405 406 if(__p is null) 407 { 408 return null; 409 } 410 411 return new TreeNode(cast(GTreeNode*) __p); 412 } 413 414 alias doref = ref_; 415 /** 416 * Increments the reference count of @tree by one. 417 * 418 * It is safe to call this function from any thread. 419 * 420 * Returns: the passed in #GTree 421 * 422 * Since: 2.22 423 */ 424 public BBTree ref_() 425 { 426 auto __p = g_tree_ref(gTree); 427 428 if(__p is null) 429 { 430 return null; 431 } 432 433 return new BBTree(cast(GTree*) __p, true); 434 } 435 436 /** 437 * Removes a key/value pair from a #GTree. 438 * 439 * If the #GTree was created using g_tree_new_full(), the key and value 440 * are freed using the supplied destroy functions, otherwise you have to 441 * make sure that any dynamically allocated values are freed yourself. 442 * If the key does not exist in the #GTree, the function does nothing. 443 * 444 * The cost of maintaining a balanced tree while removing a key/value 445 * result in a O(n log(n)) operation where most of the other operations 446 * are O(log(n)). 447 * 448 * Params: 449 * key = the key to remove 450 * 451 * Returns: %TRUE if the key was found (prior to 2.8, this function 452 * returned nothing) 453 */ 454 public bool remove(void* key) 455 { 456 return g_tree_remove(gTree, key) != 0; 457 } 458 459 /** 460 * Inserts a new key and value into a #GTree as g_tree_replace_node() does, 461 * only this function does not return the inserted or set node. 462 * 463 * Params: 464 * key = the key to insert 465 * value = the value corresponding to the key 466 */ 467 public void replace(void* key, void* value) 468 { 469 g_tree_replace(gTree, key, value); 470 } 471 472 /** 473 * Inserts a new key and value into a #GTree similar to g_tree_insert_node(). 474 * The difference is that if the key already exists in the #GTree, it gets 475 * replaced by the new key. If you supplied a @value_destroy_func when 476 * creating the #GTree, the old value is freed using that function. If you 477 * supplied a @key_destroy_func when creating the #GTree, the old key is 478 * freed using that function. 479 * 480 * The tree is automatically 'balanced' as new key/value pairs are added, 481 * so that the distance from the root to every leaf is as small as possible. 482 * 483 * Params: 484 * key = the key to insert 485 * value = the value corresponding to the key 486 * 487 * Returns: the inserted (or set) node. 488 * 489 * Since: 2.68 490 */ 491 public TreeNode replaceNode(void* key, void* value) 492 { 493 auto __p = g_tree_replace_node(gTree, key, value); 494 495 if(__p is null) 496 { 497 return null; 498 } 499 500 return new TreeNode(cast(GTreeNode*) __p); 501 } 502 503 /** 504 * Searches a #GTree using @search_func. 505 * 506 * The @search_func is called with a pointer to the key of a key/value 507 * pair in the tree, and the passed in @user_data. If @search_func returns 508 * 0 for a key/value pair, then the corresponding value is returned as 509 * the result of g_tree_search(). If @search_func returns -1, searching 510 * will proceed among the key/value pairs that have a smaller key; if 511 * @search_func returns 1, searching will proceed among the key/value 512 * pairs that have a larger key. 513 * 514 * Params: 515 * searchFunc = a function used to search the #GTree 516 * userData = the data passed as the second argument to @search_func 517 * 518 * Returns: the value corresponding to the found key, or %NULL 519 * if the key was not found 520 */ 521 public void* search(GCompareFunc searchFunc, void* userData) 522 { 523 return g_tree_search(gTree, searchFunc, userData); 524 } 525 526 /** 527 * Searches a #GTree using @search_func. 528 * 529 * The @search_func is called with a pointer to the key of a key/value 530 * pair in the tree, and the passed in @user_data. If @search_func returns 531 * 0 for a key/value pair, then the corresponding node is returned as 532 * the result of g_tree_search(). If @search_func returns -1, searching 533 * will proceed among the key/value pairs that have a smaller key; if 534 * @search_func returns 1, searching will proceed among the key/value 535 * pairs that have a larger key. 536 * 537 * Params: 538 * searchFunc = a function used to search the #GTree 539 * userData = the data passed as the second argument to @search_func 540 * 541 * Returns: the node corresponding to the 542 * found key, or %NULL if the key was not found 543 * 544 * Since: 2.68 545 */ 546 public TreeNode searchNode(GCompareFunc searchFunc, void* userData) 547 { 548 auto __p = g_tree_search_node(gTree, searchFunc, userData); 549 550 if(__p is null) 551 { 552 return null; 553 } 554 555 return new TreeNode(cast(GTreeNode*) __p); 556 } 557 558 /** 559 * Removes a key and its associated value from a #GTree without calling 560 * the key and value destroy functions. 561 * 562 * If the key does not exist in the #GTree, the function does nothing. 563 * 564 * Params: 565 * key = the key to remove 566 * 567 * Returns: %TRUE if the key was found (prior to 2.8, this function 568 * returned nothing) 569 */ 570 public bool steal(void* key) 571 { 572 return g_tree_steal(gTree, key) != 0; 573 } 574 575 /** 576 * Calls the given function for each node in the #GTree. 577 * 578 * Deprecated: The order of a balanced tree is somewhat arbitrary. 579 * If you just want to visit all nodes in sorted order, use 580 * g_tree_foreach() instead. If you really need to visit nodes in 581 * a different order, consider using an [n-ary tree][glib-N-ary-Trees]. 582 * 583 * Params: 584 * traverseFunc = the function to call for each node visited. If this 585 * function returns %TRUE, the traversal is stopped. 586 * traverseType = the order in which nodes are visited, one of %G_IN_ORDER, 587 * %G_PRE_ORDER and %G_POST_ORDER 588 * userData = user data to pass to the function 589 */ 590 public void traverse(GTraverseFunc traverseFunc, GTraverseType traverseType, void* userData) 591 { 592 g_tree_traverse(gTree, traverseFunc, traverseType, userData); 593 } 594 595 /** 596 * Decrements the reference count of @tree by one. 597 * If the reference count drops to 0, all keys and values will 598 * be destroyed (if destroy functions were specified) and all 599 * memory allocated by @tree will be released. 600 * 601 * It is safe to call this function from any thread. 602 * 603 * Since: 2.22 604 */ 605 public void unref() 606 { 607 g_tree_unref(gTree); 608 } 609 610 /** 611 * Gets the upper bound node corresponding to the given key, 612 * or %NULL if the tree is empty or all the nodes in the tree 613 * have keys that are lower than or equal to the searched key. 614 * 615 * The upper bound is the first node that has its key strictly greater 616 * than the searched key. 617 * 618 * Params: 619 * key = the key to calculate the upper bound for 620 * 621 * Returns: the tree node corresponding to the 622 * upper bound, or %NULL if the tree is empty or has only keys 623 * lower than or equal to the searched key. 624 * 625 * Since: 2.68 626 */ 627 public TreeNode upperBound(void* key) 628 { 629 auto __p = g_tree_upper_bound(gTree, key); 630 631 if(__p is null) 632 { 633 return null; 634 } 635 636 return new TreeNode(cast(GTreeNode*) __p); 637 } 638 }