[834] | 1 | /* |
---|
| 2 | Copyright (c) 2003-2006, Troy Aaron Johnson |
---|
| 3 | All rights reserved. |
---|
| 4 | |
---|
| 5 | Redistribution and use in source and binary forms, with or without |
---|
| 6 | modification, are permitted provided that the following conditions |
---|
| 7 | are met: |
---|
| 8 | |
---|
| 9 | * Redistributions of source code must retain the above copyright |
---|
| 10 | notice, this list of conditions and the following disclaimer. |
---|
| 11 | * Redistributions in binary form must reproduce the above copyright |
---|
| 12 | notice, this list of conditions and the following disclaimer in the |
---|
| 13 | documentation and/or other materials provided with the distribution. |
---|
| 14 | * Neither the name of Troy Aaron Johnson nor the names of any |
---|
| 15 | contributors may be used to endorse or promote products derived from |
---|
| 16 | this software without specific prior written permission. |
---|
| 17 | |
---|
| 18 | THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" |
---|
| 19 | AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
---|
| 20 | IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
---|
| 21 | ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE |
---|
| 22 | LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
---|
| 23 | CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
---|
| 24 | SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
---|
| 25 | INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
---|
| 26 | CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
---|
| 27 | ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
---|
| 28 | POSSIBILITY OF SUCH DAMAGE. |
---|
| 29 | */ |
---|
| 30 | |
---|
| 31 | #ifndef TREE_H |
---|
| 32 | #define TREE_H |
---|
| 33 | |
---|
| 34 | #include <cassert> |
---|
| 35 | #include <list> |
---|
| 36 | #include <stdexcept> |
---|
| 37 | #include <string> |
---|
| 38 | |
---|
| 39 | /* master invariant checks are sprinkled throughout to check |
---|
| 40 | for catastrophic errors */ |
---|
| 41 | #if defined(TREE_NO_ERROR_CHECKING) |
---|
| 42 | #define TREE_MASTER_INVARIANT |
---|
| 43 | #else |
---|
| 44 | #if defined(TREE_EXCEPTIONS) |
---|
| 45 | #define TREE_MASTER_INVARIANT check_master_invariant() |
---|
| 46 | #else |
---|
| 47 | #define TREE_MASTER_INVARIANT assert(master != NULL); \ |
---|
| 48 | assert(master->next_sibling != NULL) |
---|
| 49 | #endif |
---|
| 50 | #endif |
---|
| 51 | |
---|
| 52 | /* experimental */ |
---|
| 53 | // #define TREE_POINTER_SPECIALIZATION |
---|
| 54 | |
---|
| 55 | namespace taj /* my initials */ |
---|
| 56 | { |
---|
| 57 | |
---|
| 58 | /** Provides a generic n-ary acyclic tree container that behaves similarly |
---|
| 59 | * to and is mostly compatible with other standard C++ templates. Various |
---|
| 60 | * iterators are provided, with pruning options. Iterators are also used |
---|
| 61 | * to represent subtrees. |
---|
| 62 | * |
---|
| 63 | * In the spirit of the standard template library, the BSD license makes |
---|
| 64 | * my tree class available for all to use. I would appreciate receiving |
---|
| 65 | * patches to fix any bugs you may discover or suggestions on how to |
---|
| 66 | * improve the template. |
---|
| 67 | * |
---|
| 68 | * The STL list template was my initial inspiration for how to implement |
---|
| 69 | * the tree class, but I determined there was little benefit from |
---|
| 70 | * starting with that code. This template class does not use any code |
---|
| 71 | * from the STL classes, but is designed to be compatible and have similar |
---|
| 72 | * method names for consistency. I intend for this class to be very |
---|
| 73 | * efficient in terms of size and speed, just like the STL classes. |
---|
| 74 | * |
---|
| 75 | * The std::list template uses many supporting classes that are found in |
---|
| 76 | * the std namespace or public in the std::list namespace. This tree |
---|
| 77 | * template does not pollute the global namespace as much by keeping all |
---|
| 78 | * the supporting classes inside the main class. If the user includes |
---|
| 79 | * the taj namespace, the only name that gets sucked into the enclosing |
---|
| 80 | * namespace is tree. I feel this is a better design. The following were |
---|
| 81 | * some motivating factors: |
---|
| 82 | * |
---|
| 83 | * 1) The tree_node class should be invisible to the user. The user wants to |
---|
| 84 | * think of the N in tree<N> as the node type of the tree. In the standard |
---|
| 85 | * list template, struct _List_node is similarly irrelevant to the user |
---|
| 86 | * but unnecessarily appears in the std namespace. |
---|
| 87 | * |
---|
| 88 | * 2) The base template for the iterators should be a true class instead of a |
---|
| 89 | * wide-open struct. Furthermore, it should not be accessible to the user. |
---|
| 90 | * A consequence of nesting the iterators inside the tree class is needing |
---|
| 91 | * to make the tree their friend, but this is an example of how to use |
---|
| 92 | * friends correctly. |
---|
| 93 | * |
---|
| 94 | * There is a lot of code here, so I have divided it into several header |
---|
| 95 | * files and code files. The only header the user needs to include is tree.h. |
---|
| 96 | * |
---|
| 97 | * tree.h - the main header file for the tree class |
---|
| 98 | * tree_node.h - class that represents tree nodes |
---|
| 99 | * tree_iterator.h - base class for ALL iterators |
---|
| 100 | * iterator.h - base class for ONLY non-const iterators |
---|
| 101 | * const_iterator.h - base class for ONLY const_iterators |
---|
| 102 | * (const_)preorder_iterator.h - iterators for preorder traversal |
---|
| 103 | * (const_)postorder_iterator.h - iterators for postorder traversal |
---|
| 104 | * (const_)bfs_iterator.h - iterators for breadth-first traversal |
---|
| 105 | * (const_)sibling_iterator.h - iterators for a single tree level |
---|
| 106 | * |
---|
| 107 | * There is no "in-order" traversal because the tree is not necessarily |
---|
| 108 | * binary. There are also .cc files which get included by this file, because |
---|
| 109 | * all the code for the template needs to be in tree.h. |
---|
| 110 | * |
---|
| 111 | * Note concerning GCC 3.4: Template code checks are much stricter in 3.4. |
---|
| 112 | * It is possible to have a template that compiles with GCC 3.3 but that does |
---|
| 113 | * not compile with 3.4. The following GCC "bug" reports explain the |
---|
| 114 | * workarounds, which have been incorporated into this template class. |
---|
| 115 | * |
---|
| 116 | * http://gcc.gnu.org/bugzilla/show_bug.cgi?id=15552 |
---|
| 117 | * http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17649 |
---|
| 118 | * |
---|
| 119 | * The same issue has found its way into the C++ FAQ |
---|
| 120 | * |
---|
| 121 | * http://www.parashift.com/c++-faq-lite/templates.html#faq-35.12 |
---|
| 122 | * http://www.parashift.com/c++-faq-lite/templates.html#faq-35.13 |
---|
| 123 | * |
---|
| 124 | * A final note: C++ template code is weird and classes as complicated as |
---|
| 125 | * this one will give your compiler good exercise. I have tested this |
---|
| 126 | * class with the Debian releases of GCC 3.3.5, GCC 3.4.4, GCC 4.0.3 and |
---|
| 127 | * I expect to use it with later versions. I have no idea if it works |
---|
| 128 | * under other C++ compilers. If there are changes that will allow it to |
---|
| 129 | * work under more compilers while still allowing it to work under GCC, |
---|
| 130 | * then you are encouraged to suggest them. |
---|
| 131 | * |
---|
| 132 | * @author Troy A. Johnson |
---|
| 133 | */ |
---|
| 134 | template <class N> |
---|
| 135 | class tree |
---|
| 136 | { |
---|
| 137 | private: |
---|
| 138 | |
---|
| 139 | #include "tree_node.h" |
---|
| 140 | #include "tree_iterator.h" |
---|
| 141 | |
---|
| 142 | /** The real root of the tree as opposed to the first node inserted by |
---|
| 143 | * the user. Also used as the end for preorder and postorder iterators |
---|
| 144 | * since they finish by "falling off" the root of the tree. (The |
---|
| 145 | * breadth-first iterator uses NULL for its end because it falls off |
---|
| 146 | * the leaves.) As far as the user is concerned, the first node is |
---|
| 147 | * master->next_sibling. This corresponds to the _M_node in |
---|
| 148 | * _List_alloc_base for the standard list template. |
---|
| 149 | */ |
---|
| 150 | tree_node<N>* master; |
---|
| 151 | |
---|
| 152 | public: |
---|
| 153 | |
---|
| 154 | /* avoid annoying forward reference problems */ |
---|
| 155 | |
---|
| 156 | class iterator; |
---|
| 157 | class const_iterator; |
---|
| 158 | |
---|
| 159 | class sibling_iterator; |
---|
| 160 | class const_sibling_iterator; |
---|
| 161 | |
---|
| 162 | class preorder_iterator; |
---|
| 163 | class const_preorder_iterator; |
---|
| 164 | |
---|
| 165 | class postorder_iterator; |
---|
| 166 | class const_postorder_iterator; |
---|
| 167 | |
---|
| 168 | class bfs_iterator; |
---|
| 169 | class const_bfs_iterator; |
---|
| 170 | |
---|
| 171 | #include "iterator.h" |
---|
| 172 | #include "const_iterator.h" |
---|
| 173 | |
---|
| 174 | #include "sibling_iterator.h" |
---|
| 175 | #include "const_sibling_iterator.h" |
---|
| 176 | |
---|
| 177 | #include "preorder_iterator.h" |
---|
| 178 | #include "const_preorder_iterator.h" |
---|
| 179 | |
---|
| 180 | #include "postorder_iterator.h" |
---|
| 181 | #include "const_postorder_iterator.h" |
---|
| 182 | |
---|
| 183 | #include "bfs_iterator.h" |
---|
| 184 | #include "const_bfs_iterator.h" |
---|
| 185 | |
---|
| 186 | /* no dfs_iterator - use preorder_iterator instead */ |
---|
| 187 | |
---|
| 188 | /** Thrown if tree exceptions are turned on and a NULL is encountered |
---|
| 189 | * in an incorrect place. */ |
---|
| 190 | class null_tree_exception : public std::runtime_error |
---|
| 191 | { |
---|
| 192 | public: |
---|
| 193 | null_tree_exception(const std::string& s) |
---|
| 194 | : std::runtime_error("null_tree_exception " + s) { } |
---|
| 195 | }; |
---|
| 196 | |
---|
| 197 | private: |
---|
| 198 | |
---|
| 199 | #if !defined(TREE_NO_ERROR_CHECKING) && defined(TREE_EXCEPTIONS) |
---|
| 200 | void check_master_invariant(void) |
---|
| 201 | { |
---|
| 202 | if (master == NULL) |
---|
| 203 | throw new null_tree_exception("tree master is null"); |
---|
| 204 | |
---|
| 205 | if (master->next_sibling == NULL) |
---|
| 206 | throw new null_tree_exception("tree master->next_sibling is null"); |
---|
| 207 | } |
---|
| 208 | #endif |
---|
| 209 | |
---|
| 210 | /** Initializes the master node. Every tree constructor needs to |
---|
| 211 | * do this so it's a separate method. |
---|
| 212 | */ |
---|
| 213 | void createMaster(void) |
---|
| 214 | { |
---|
| 215 | master = new tree_node<N>; |
---|
| 216 | master->parent = NULL; |
---|
| 217 | master->first_child = master->last_child = NULL; |
---|
| 218 | master->prev_sibling = master->next_sibling = master; |
---|
| 219 | } |
---|
| 220 | |
---|
| 221 | /** Replaces this tree with copies of all nodes below (and including) |
---|
| 222 | * the node pointed to by subtree. Used by multiple constructors. |
---|
| 223 | * |
---|
| 224 | * @param subtree Location from which to begin copying. |
---|
| 225 | */ |
---|
| 226 | void copy_subtree(const_iterator subtree); |
---|
| 227 | |
---|
| 228 | /** Determines the leftmost child of this tree. |
---|
| 229 | * Used as a starting point for postorder traversals. |
---|
| 230 | * |
---|
| 231 | * @return A pointer to the leftmost node or master if |
---|
| 232 | * the tree is empty. |
---|
| 233 | */ |
---|
| 234 | tree_node<N>* leftmostChild(void) const |
---|
| 235 | { |
---|
| 236 | TREE_MASTER_INVARIANT; |
---|
| 237 | |
---|
| 238 | tree_node<N>* p = master->next_sibling; |
---|
| 239 | |
---|
| 240 | while (p->first_child != NULL) |
---|
| 241 | p = p->first_child; |
---|
| 242 | |
---|
| 243 | return p; |
---|
| 244 | } |
---|
| 245 | |
---|
| 246 | public: |
---|
| 247 | |
---|
| 248 | /** Provides access to an iterator suitable for postorder traversal, |
---|
| 249 | * initially pointing to the leftmost child of this tree. |
---|
| 250 | * |
---|
| 251 | * @return An iterator for postorder traversal. |
---|
| 252 | */ |
---|
| 253 | postorder_iterator beginPost(void) |
---|
| 254 | { return postorder_iterator(leftmostChild()); } |
---|
| 255 | |
---|
| 256 | /** Provides access to an iterator suitable for postorder traversal, |
---|
| 257 | * initially pointing to the leftmost child of this tree. |
---|
| 258 | * |
---|
| 259 | * @return A constant iterator for postorder traversal. |
---|
| 260 | */ |
---|
| 261 | const_postorder_iterator beginPost(void) const |
---|
| 262 | { return const_postorder_iterator(leftmostChild()); } |
---|
| 263 | |
---|
| 264 | /** Provides access to an iterator representing the end of a |
---|
| 265 | * postorder traversal. |
---|
| 266 | * |
---|
| 267 | * @return The end of a postorder traversal. |
---|
| 268 | */ |
---|
| 269 | postorder_iterator endPost(void) |
---|
| 270 | { return postorder_iterator(master); } |
---|
| 271 | |
---|
| 272 | /** Provides access to an iterator representing the end of a |
---|
| 273 | * constant postorder traversal. |
---|
| 274 | * |
---|
| 275 | * @return The end of a constant postorder traversal. |
---|
| 276 | */ |
---|
| 277 | const_postorder_iterator endPost(void) const |
---|
| 278 | { return const_postorder_iterator(master); } |
---|
| 279 | |
---|
| 280 | /** Provides access to an iterator suitable for preorder traversal, |
---|
| 281 | * initially pointing to the root of this tree. |
---|
| 282 | * |
---|
| 283 | * @return An iterator for preorder traversal. |
---|
| 284 | */ |
---|
| 285 | preorder_iterator beginPre(void) |
---|
| 286 | { return preorder_iterator(master->next_sibling); } |
---|
| 287 | |
---|
| 288 | /** Provides access to an iterator suitable for preorder traversal, |
---|
| 289 | * initially pointing to the root of this tree. |
---|
| 290 | * |
---|
| 291 | * @return A constant iterator for preorder traversal. |
---|
| 292 | */ |
---|
| 293 | const_preorder_iterator beginPre(void) const |
---|
| 294 | { return const_preorder_iterator(master->next_sibling); } |
---|
| 295 | |
---|
| 296 | /** Provides access to an iterator representing the end of a |
---|
| 297 | * preorder traversal. |
---|
| 298 | * |
---|
| 299 | * @return The end of a preorder traversal. |
---|
| 300 | */ |
---|
| 301 | preorder_iterator endPre(void) |
---|
| 302 | { return preorder_iterator(master); } |
---|
| 303 | |
---|
| 304 | /** Provides access to an iterator representing the end of a |
---|
| 305 | * constant preorder traversal. |
---|
| 306 | * |
---|
| 307 | * @return The end of a constant preorder traversal. |
---|
| 308 | */ |
---|
| 309 | const_preorder_iterator endPre(void) const |
---|
| 310 | { return const_preorder_iterator(master); } |
---|
| 311 | |
---|
| 312 | /** Provides access to an iterator suitable for breadth-first traversal, |
---|
| 313 | * initially pointing to the root of this tree. |
---|
| 314 | * |
---|
| 315 | * @return An iterator for breadth-first traversal. |
---|
| 316 | */ |
---|
| 317 | bfs_iterator beginBfs(void) |
---|
| 318 | { return bfs_iterator(master->next_sibling); } |
---|
| 319 | |
---|
| 320 | /** Provides access to an iterator suitable for breadth-first traversal, |
---|
| 321 | * initially pointing to the root of this tree. |
---|
| 322 | * |
---|
| 323 | * @return A constant iterator for breadth-first traversal. |
---|
| 324 | */ |
---|
| 325 | const_bfs_iterator beginBfs(void) const |
---|
| 326 | { return const_bfs_iterator(master->next_sibling); } |
---|
| 327 | |
---|
| 328 | /** Provides access to an iterator representing the end of a |
---|
| 329 | * breadth-first traversal. |
---|
| 330 | * |
---|
| 331 | * @return The end of a breadth-first traversal. |
---|
| 332 | */ |
---|
| 333 | bfs_iterator endBfs(void) |
---|
| 334 | { return bfs_iterator(NULL); } |
---|
| 335 | |
---|
| 336 | /** Provides access to an iterator representing the end of a |
---|
| 337 | * constant breadth-first traversal. |
---|
| 338 | * |
---|
| 339 | * @return The end of a constant breadth-first traversal. |
---|
| 340 | */ |
---|
| 341 | const_bfs_iterator endBfs(void) const |
---|
| 342 | { return const_bfs_iterator(NULL); } |
---|
| 343 | |
---|
| 344 | /** Creates an empty tree. A root node can be created with setRoot later. |
---|
| 345 | */ |
---|
| 346 | tree(void) |
---|
| 347 | { |
---|
| 348 | createMaster(); |
---|
| 349 | } |
---|
| 350 | |
---|
| 351 | /** Creates a single-node tree. |
---|
| 352 | * |
---|
| 353 | * @param root_data The data to use for the root of the tree. |
---|
| 354 | */ |
---|
| 355 | explicit tree(const N& root_data) |
---|
| 356 | { |
---|
| 357 | createMaster(); |
---|
| 358 | setRoot(root_data); |
---|
| 359 | } |
---|
| 360 | |
---|
| 361 | /** Copies an existing subtree. |
---|
| 362 | * |
---|
| 363 | * @param subtree The root of the original subtree |
---|
| 364 | * from which to make the copy. |
---|
| 365 | */ |
---|
| 366 | explicit tree(const_iterator subtree) |
---|
| 367 | { |
---|
| 368 | createMaster(); |
---|
| 369 | copy_subtree(subtree); |
---|
| 370 | } |
---|
| 371 | |
---|
| 372 | /** Copies an existing tree. |
---|
| 373 | * |
---|
| 374 | * @param orig The original tree from which to make the copy. |
---|
| 375 | */ |
---|
| 376 | tree(const tree<N>& orig) |
---|
| 377 | { |
---|
| 378 | createMaster(); |
---|
| 379 | copy_subtree(orig.getRoot()); |
---|
| 380 | } |
---|
| 381 | |
---|
| 382 | /** Creates a tree using copies of items of another container. |
---|
| 383 | * The range copied is [first, last). |
---|
| 384 | * |
---|
| 385 | * @param first First item to put in the tree. |
---|
| 386 | * @param last The item after the final item to put in the tree. |
---|
| 387 | * @param n Creates a n-ary tree. Must be greater than zero. |
---|
| 388 | */ |
---|
| 389 | template <class InputIterator> |
---|
| 390 | tree(InputIterator first, InputIterator last, unsigned int n); |
---|
| 391 | |
---|
| 392 | /** Copies an existing tree. |
---|
| 393 | * |
---|
| 394 | * @param orig The original tree from which to make the copy. |
---|
| 395 | * |
---|
| 396 | * @return A reference to this tree to be used in chained assignments. |
---|
| 397 | */ |
---|
| 398 | const tree<N>& operator = (const tree<N>& orig) |
---|
| 399 | { |
---|
| 400 | copy_subtree(orig.getRoot()); |
---|
| 401 | return *this; |
---|
| 402 | } |
---|
| 403 | |
---|
| 404 | /** Empties and destroys the tree. |
---|
| 405 | */ |
---|
| 406 | virtual ~tree(void) |
---|
| 407 | { |
---|
| 408 | TREE_MASTER_INVARIANT; |
---|
| 409 | clear(); |
---|
| 410 | delete master; |
---|
| 411 | } |
---|
| 412 | |
---|
| 413 | /** Empties the tree. All nodes are deleted. If the node type |
---|
| 414 | * is a pointer, it is the user's responsibility to delete |
---|
| 415 | * the data to which they point before clearing the tree. |
---|
| 416 | */ |
---|
| 417 | void clear(void); |
---|
| 418 | |
---|
| 419 | /** Checks if the tree is empty. |
---|
| 420 | * |
---|
| 421 | * @return true if the tree is empty, false otherwise. |
---|
| 422 | */ |
---|
| 423 | bool empty(void) const |
---|
| 424 | { |
---|
| 425 | TREE_MASTER_INVARIANT; |
---|
| 426 | return (master->next_sibling == master); |
---|
| 427 | } |
---|
| 428 | |
---|
| 429 | /** Provides access to the root of the tree. |
---|
| 430 | * |
---|
| 431 | * @return An iterator pointing at the root node. |
---|
| 432 | */ |
---|
| 433 | iterator getRoot(void) |
---|
| 434 | { |
---|
| 435 | TREE_MASTER_INVARIANT; |
---|
| 436 | return iterator(master->next_sibling); |
---|
| 437 | } |
---|
| 438 | |
---|
| 439 | /** Provides access to the root of an unmodifiable tree. |
---|
| 440 | * |
---|
| 441 | * @return An iterator pointing at the root node. |
---|
| 442 | */ |
---|
| 443 | const_iterator getRoot(void) const |
---|
| 444 | { |
---|
| 445 | TREE_MASTER_INVARIANT; |
---|
| 446 | return const_iterator(master->next_sibling); |
---|
| 447 | } |
---|
| 448 | |
---|
| 449 | /** Determines the height of the tree. This operation is |
---|
| 450 | * general and is linear in the size of the tree, not |
---|
| 451 | * the height. |
---|
| 452 | * |
---|
| 453 | * @return The height of the tree. |
---|
| 454 | */ |
---|
| 455 | size_t height(void) const; |
---|
| 456 | |
---|
| 457 | /** Determines the height of the tree using |
---|
| 458 | * the leftmost grandchild of the root. This operation is |
---|
| 459 | * guaranteed to be linear in the height of the tree, but |
---|
| 460 | * may not be the true height for some trees. |
---|
| 461 | * |
---|
| 462 | * @return The height of the leftmost grandchild of the root. |
---|
| 463 | */ |
---|
| 464 | size_t height_leftmost(void) const; |
---|
| 465 | |
---|
| 466 | /** Sets the data of the root node, or creates one if it was not set |
---|
| 467 | * when the tree was created. |
---|
| 468 | * |
---|
| 469 | * @return An iterator pointing to the root node. |
---|
| 470 | */ |
---|
| 471 | iterator setRoot(const N& root_data) |
---|
| 472 | { |
---|
| 473 | if (empty()) |
---|
| 474 | { |
---|
| 475 | tree_node<N>* root = new tree_node<N>(root_data); |
---|
| 476 | root->parent = NULL; |
---|
| 477 | root->first_child = root->last_child = NULL; |
---|
| 478 | root->next_sibling = root->prev_sibling = master; |
---|
| 479 | |
---|
| 480 | master->prev_sibling = master->next_sibling = root; |
---|
| 481 | } |
---|
| 482 | else |
---|
| 483 | *getRoot() = root_data; |
---|
| 484 | |
---|
| 485 | return getRoot(); |
---|
| 486 | } |
---|
| 487 | |
---|
| 488 | /** Determines the number of nodes in the tree. |
---|
| 489 | * Unfortunately this requires a full tree traversal. |
---|
| 490 | * This could be expensive, but it's far simpler than |
---|
| 491 | * making iterators aware of what tree they are modifying |
---|
| 492 | * and updating the current size of that tree. For simple |
---|
| 493 | * insertion and deletion that might not be difficult, |
---|
| 494 | * but for more complex operations it very well might be. |
---|
| 495 | * Doing it this way makes size a known expensive operation |
---|
| 496 | * instead of adding overhead to a large number of other calls. |
---|
| 497 | * If the user knows how many nodes they have added or deleted |
---|
| 498 | * since their last size call, then they can compute the current |
---|
| 499 | * size without calling size. It should be noted that the |
---|
| 500 | * standard library list template works the same way. |
---|
| 501 | * |
---|
| 502 | * @return The number of nodes in the tree. |
---|
| 503 | */ |
---|
| 504 | size_t size(void) const; |
---|
| 505 | }; |
---|
| 506 | |
---|
| 507 | #include "tree_iterator.cc" |
---|
| 508 | |
---|
| 509 | #include "iterator.cc" |
---|
| 510 | |
---|
| 511 | #include "const_iterator.cc" |
---|
| 512 | |
---|
| 513 | /* keep this include last */ |
---|
| 514 | #include "tree.cc" |
---|
| 515 | |
---|
| 516 | /* TODO - Pointer specialization |
---|
| 517 | |
---|
| 518 | This is experimental and may not work at all. |
---|
| 519 | */ |
---|
| 520 | |
---|
| 521 | #if defined(TREE_POINTER_SPECIALIZATION) |
---|
| 522 | template class tree<void*>; |
---|
| 523 | |
---|
| 524 | template <class N> |
---|
| 525 | class tree<N*> : private tree<void*> |
---|
| 526 | { |
---|
| 527 | public: |
---|
| 528 | |
---|
| 529 | /* do not prefix these forward declarations with tree<N*>:: */ |
---|
| 530 | |
---|
| 531 | class iterator; |
---|
| 532 | class const_iterator; |
---|
| 533 | |
---|
| 534 | class sibling_iterator; |
---|
| 535 | class const_sibling_iterator; |
---|
| 536 | |
---|
| 537 | class preorder_iterator; |
---|
| 538 | class const_preorder_iterator; |
---|
| 539 | |
---|
| 540 | class postorder_iterator; |
---|
| 541 | class const_postorder_iterator; |
---|
| 542 | |
---|
| 543 | class bfs_iterator; |
---|
| 544 | class const_bfs_iterator; |
---|
| 545 | |
---|
| 546 | class iterator : private virtual tree<void*>::iterator |
---|
| 547 | { |
---|
| 548 | friend class tree<N*>; |
---|
| 549 | |
---|
| 550 | typedef class tree<N*>::iterator self; |
---|
| 551 | typedef class tree<void*>::iterator super; |
---|
| 552 | |
---|
| 553 | protected: |
---|
| 554 | |
---|
| 555 | iterator(const super& iter) : super(iter) { } |
---|
| 556 | |
---|
| 557 | public: |
---|
| 558 | |
---|
| 559 | iterator(void) { } |
---|
| 560 | |
---|
| 561 | iterator(const self& iter) : super(iter) { } |
---|
| 562 | |
---|
| 563 | // operator const_iterator() |
---|
| 564 | // { return static_cast<typename tree<void*>::const_iterator>(*this); } |
---|
| 565 | |
---|
| 566 | bool operator == (const self& iter) const |
---|
| 567 | { return super(*this) == super(iter); } |
---|
| 568 | |
---|
| 569 | bool operator != (const self& iter) const |
---|
| 570 | { return super(*this) != super(iter); } |
---|
| 571 | |
---|
| 572 | using super::clear; |
---|
| 573 | |
---|
| 574 | using super::depth; |
---|
| 575 | |
---|
| 576 | typename tree<N*>::sibling_iterator beginChildren(void) const |
---|
| 577 | { return self(super::beginChildren()); } |
---|
| 578 | |
---|
| 579 | typename tree<N*>::sibling_iterator endChildren(void) const |
---|
| 580 | { return self(super::endChildren()); } |
---|
| 581 | |
---|
| 582 | N*& |
---|
| 583 | operator * (void) const { return reinterpret_cast<N*&>(this->current->data); } |
---|
| 584 | |
---|
| 585 | N** |
---|
| 586 | operator -> (void) const { return reinterpret_cast<N**>(&(this->current->data)); } |
---|
| 587 | |
---|
| 588 | self absorb_back(tree<N*>* t) |
---|
| 589 | { return super::absorb_back(t); } |
---|
| 590 | |
---|
| 591 | self push_back(N* data) |
---|
| 592 | { return super::push_back(data); } |
---|
| 593 | |
---|
| 594 | N* replace(N* data) |
---|
| 595 | { return reinterpret_cast<N*>(super::replace(data)); } |
---|
| 596 | }; |
---|
| 597 | |
---|
| 598 | class const_iterator : private virtual tree<void*>::const_iterator |
---|
| 599 | { |
---|
| 600 | friend class tree<N*>; |
---|
| 601 | |
---|
| 602 | typedef class tree<N*>::const_iterator self; |
---|
| 603 | typedef class tree<void*>::const_iterator super; |
---|
| 604 | |
---|
| 605 | protected: |
---|
| 606 | |
---|
| 607 | const_iterator(const super& iter) : super(iter) { } |
---|
| 608 | |
---|
| 609 | public: |
---|
| 610 | |
---|
| 611 | const_iterator(void) { } |
---|
| 612 | |
---|
| 613 | const_iterator(const self& iter) : super(iter) { } |
---|
| 614 | |
---|
| 615 | bool operator == (const self& iter) const |
---|
| 616 | { return super(*this) == super(iter); } |
---|
| 617 | |
---|
| 618 | bool operator != (const self& iter) const |
---|
| 619 | { return super(*this) != super(iter); } |
---|
| 620 | |
---|
| 621 | using super::depth; |
---|
| 622 | |
---|
| 623 | N* const & |
---|
| 624 | operator * (void) const { return reinterpret_cast<N* const &>(this->current->data); } |
---|
| 625 | |
---|
| 626 | N* const * |
---|
| 627 | operator -> (void) const { return reinterpret_cast<N* const *>(&(this->current->data)); } |
---|
| 628 | }; |
---|
| 629 | |
---|
| 630 | class sibling_iterator : public tree<N*>::iterator, private tree<void*>::sibling_iterator |
---|
| 631 | { |
---|
| 632 | friend class tree<N*>; |
---|
| 633 | |
---|
| 634 | private: |
---|
| 635 | |
---|
| 636 | sibling_iterator(const tree<void*>::sibling_iterator& iter) : tree<N*>::iterator(iter) { } |
---|
| 637 | |
---|
| 638 | public: |
---|
| 639 | |
---|
| 640 | sibling_iterator(void) { } |
---|
| 641 | |
---|
| 642 | sibling_iterator(const tree<N*>::iterator& iter) : tree<N*>::iterator(iter) { } |
---|
| 643 | |
---|
| 644 | using tree<N*>::iterator::operator *; |
---|
| 645 | |
---|
| 646 | typename tree<N*>::sibling_iterator& operator ++ (void) |
---|
| 647 | { ++static_cast<tree<void*>::sibling_iterator>(*this); return *this; } |
---|
| 648 | }; |
---|
| 649 | #if 0 |
---|
| 650 | class const_sibling_iterator : public const_iterator |
---|
| 651 | { |
---|
| 652 | friend class tree<N*>; |
---|
| 653 | |
---|
| 654 | private: |
---|
| 655 | |
---|
| 656 | // const_sibling_iterator(const tree<void*>::const_sibling_iterator& iter) : const_iterator(iter) { } |
---|
| 657 | |
---|
| 658 | public: |
---|
| 659 | |
---|
| 660 | const_sibling_iterator(const const_iterator& iter) : const_iterator(iter) { } |
---|
| 661 | }; |
---|
| 662 | #endif |
---|
| 663 | class preorder_iterator : public tree<N*>::iterator, private tree<void*>::preorder_iterator |
---|
| 664 | { |
---|
| 665 | friend class tree<N*>; |
---|
| 666 | |
---|
| 667 | private: |
---|
| 668 | |
---|
| 669 | preorder_iterator(const tree<void*>::preorder_iterator& iter) : tree<N*>::iterator(iter) { } |
---|
| 670 | |
---|
| 671 | public: |
---|
| 672 | |
---|
| 673 | preorder_iterator(const tree<N*>::iterator& iter) : tree<N*>::iterator(iter) { } |
---|
| 674 | |
---|
| 675 | using tree<N*>::iterator::operator ==; |
---|
| 676 | using tree<N*>::iterator::operator !=; |
---|
| 677 | using tree<N*>::iterator::operator *; |
---|
| 678 | |
---|
| 679 | typename tree<N*>::preorder_iterator& operator ++ (void) |
---|
| 680 | { ++static_cast<tree<void*>::preorder_iterator>(*this); return *this; } |
---|
| 681 | |
---|
| 682 | using tree<N*>::iterator::replace; |
---|
| 683 | }; |
---|
| 684 | |
---|
| 685 | class const_preorder_iterator : public tree<N*>::const_iterator, private tree<void*>::const_preorder_iterator |
---|
| 686 | { |
---|
| 687 | friend class tree<N*>; |
---|
| 688 | |
---|
| 689 | private: |
---|
| 690 | |
---|
| 691 | const_preorder_iterator(const tree<void*>::const_preorder_iterator& iter) : tree<void*>::const_preorder_iterator(iter) { } |
---|
| 692 | |
---|
| 693 | public: |
---|
| 694 | |
---|
| 695 | const_preorder_iterator(const tree<N*>::const_iterator& iter) : tree<N*>::const_iterator(iter) { } |
---|
| 696 | |
---|
| 697 | using tree<N*>::const_iterator::operator *; |
---|
| 698 | |
---|
| 699 | typename tree<N*>::const_preorder_iterator& operator ++ (void) |
---|
| 700 | { ++static_cast<tree<void*>::const_preorder_iterator>(*this); return *this; } |
---|
| 701 | }; |
---|
| 702 | #if 0 |
---|
| 703 | class postorder_iterator : private tree<void*>::postorder_iterator |
---|
| 704 | { |
---|
| 705 | friend class tree<N*>; |
---|
| 706 | |
---|
| 707 | private: |
---|
| 708 | |
---|
| 709 | // postorder_iterator(const tree<void*>::postorder_iterator& iter) : iterator(iter) { } |
---|
| 710 | |
---|
| 711 | public: |
---|
| 712 | |
---|
| 713 | postorder_iterator(const iterator& iter) : tree<void*>::postorder_iterator(iter) { } |
---|
| 714 | }; |
---|
| 715 | |
---|
| 716 | class const_postorder_iterator : private tree<void*>::const_postorder_iterator |
---|
| 717 | { |
---|
| 718 | friend class tree<N*>; |
---|
| 719 | |
---|
| 720 | private: |
---|
| 721 | |
---|
| 722 | // const_postorder_iterator(const tree<void*>::const_postorder_iterator& iter) : const_iterator(iter) { } |
---|
| 723 | |
---|
| 724 | public: |
---|
| 725 | |
---|
| 726 | const_postorder_iterator(const const_iterator& iter) : tree<void*>::const_postorder_iterator(iter) { } |
---|
| 727 | }; |
---|
| 728 | |
---|
| 729 | class bfs_iterator : private tree<void*>::bfs_iterator |
---|
| 730 | { |
---|
| 731 | friend class tree<N*>; |
---|
| 732 | |
---|
| 733 | private: |
---|
| 734 | |
---|
| 735 | // bfs_iterator(const tree<void*>::bfs_iterator& iter) : iterator(iter) { } |
---|
| 736 | |
---|
| 737 | public: |
---|
| 738 | |
---|
| 739 | bfs_iterator(const iterator& iter) : tree<void*>::bfs_iterator(iter) { } |
---|
| 740 | }; |
---|
| 741 | |
---|
| 742 | class const_bfs_iterator : private tree<void*>::const_bfs_iterator |
---|
| 743 | { |
---|
| 744 | friend class tree<N*>; |
---|
| 745 | |
---|
| 746 | private: |
---|
| 747 | |
---|
| 748 | // const_bfs_iterator(const tree<void*>::const_bfs_iterator& iter) : const_iterator(iter) { } |
---|
| 749 | |
---|
| 750 | public: |
---|
| 751 | |
---|
| 752 | const_bfs_iterator(const const_iterator& iter) : tree<void*>::const_bfs_iterator(iter) { } |
---|
| 753 | }; |
---|
| 754 | #endif |
---|
| 755 | tree(void) : tree<void*>::tree() |
---|
| 756 | { |
---|
| 757 | } |
---|
| 758 | |
---|
| 759 | /** Creates a single-node tree. |
---|
| 760 | * |
---|
| 761 | * @param root_data The data to use for the root of the tree. |
---|
| 762 | */ |
---|
| 763 | explicit tree(N* root_data) : tree<void*>::tree(root_data) |
---|
| 764 | { |
---|
| 765 | } |
---|
| 766 | |
---|
| 767 | explicit tree(const_iterator subtree) : tree<void*>::tree(subtree) |
---|
| 768 | { |
---|
| 769 | } |
---|
| 770 | |
---|
| 771 | tree(const tree<N*>& orig) : tree<void*>::tree(orig) |
---|
| 772 | { |
---|
| 773 | } |
---|
| 774 | |
---|
| 775 | preorder_iterator beginPre(void) |
---|
| 776 | { return tree<void*>::beginPre(); } |
---|
| 777 | |
---|
| 778 | const_preorder_iterator beginPre(void) const |
---|
| 779 | { return tree<void*>::beginPre(); } |
---|
| 780 | |
---|
| 781 | preorder_iterator endPre(void) |
---|
| 782 | { return tree<void*>::endPre(); } |
---|
| 783 | |
---|
| 784 | const_preorder_iterator endPre(void) const |
---|
| 785 | { return tree<void*>::endPre(); } |
---|
| 786 | |
---|
| 787 | iterator getRoot(void) |
---|
| 788 | { return tree<void*>::getRoot(); } |
---|
| 789 | |
---|
| 790 | const_iterator getRoot(void) const |
---|
| 791 | { return tree<void*>::getRoot(); } |
---|
| 792 | |
---|
| 793 | iterator setRoot(N* root_data) |
---|
| 794 | { return tree<void*>::setRoot(root_data); } |
---|
| 795 | }; |
---|
| 796 | |
---|
| 797 | #if 0 |
---|
| 798 | template class tree<void*>; |
---|
| 799 | template class tree<void*>::tree_node<void*>; |
---|
| 800 | |
---|
| 801 | template <class N> |
---|
| 802 | class tree<N*> : public tree<void*> |
---|
| 803 | { |
---|
| 804 | public: |
---|
| 805 | |
---|
| 806 | // class const_iterator; |
---|
| 807 | |
---|
| 808 | private: |
---|
| 809 | |
---|
| 810 | template <class T> |
---|
| 811 | class tree_node<T*> : public tree_node<void*> |
---|
| 812 | { |
---|
| 813 | public: |
---|
| 814 | |
---|
| 815 | tree_node(void) : tree_node<void*>() { } |
---|
| 816 | |
---|
| 817 | tree_node(T* data) : tree_node<void*>(data) { } |
---|
| 818 | }; |
---|
| 819 | /* |
---|
| 820 | template <class T, class R, class P> |
---|
| 821 | class tree_iterator<T*, R*, P*> : public tree_iterator<void*, void*&, void**> |
---|
| 822 | { |
---|
| 823 | |
---|
| 824 | }; |
---|
| 825 | */ |
---|
| 826 | public: |
---|
| 827 | |
---|
| 828 | tree(void) : tree<void*>() |
---|
| 829 | { |
---|
| 830 | std::cout << "specialized tree default constructor" << std::endl; |
---|
| 831 | } |
---|
| 832 | |
---|
| 833 | explicit tree(N* root_data) : tree<void*>(root_data) |
---|
| 834 | { |
---|
| 835 | } |
---|
| 836 | }; |
---|
| 837 | /* |
---|
| 838 | template<class N> |
---|
| 839 | class tree<N*>::iterator : public tree<N>::template tree_iterator<N*, N&, N*> |
---|
| 840 | { |
---|
| 841 | |
---|
| 842 | }; |
---|
| 843 | */ |
---|
| 844 | |
---|
| 845 | template <class N> |
---|
| 846 | class tree<N*>::const_iterator : public tree<void*>::iterator |
---|
| 847 | { |
---|
| 848 | private: |
---|
| 849 | |
---|
| 850 | /* this typedef is very convenient and allows Java-like code */ |
---|
| 851 | typedef typename tree<N*>::template tree_iterator<N*, const N*&, const N**> super; |
---|
| 852 | |
---|
| 853 | public: |
---|
| 854 | |
---|
| 855 | typename super::reference |
---|
| 856 | operator * (void) const { return this->current->data; } |
---|
| 857 | }; |
---|
| 858 | |
---|
| 859 | //template <class N*> |
---|
| 860 | //typename tree<N*>::template tree_iterator<N*, const N*&, const N**>::reference |
---|
| 861 | //tree<N*>::template const_iterator::operator * (void) const |
---|
| 862 | //{ return this->current->data; } |
---|
| 863 | |
---|
| 864 | #endif |
---|
| 865 | #endif |
---|
| 866 | |
---|
| 867 | } /* namespace taj */ |
---|
| 868 | |
---|
| 869 | #undef TREE_MASTER_INVARIANT |
---|
| 870 | |
---|
| 871 | #endif |
---|