Upcoming Events
Unite 2010
11/10 - 11/12 @ Montréal, Canada

GDC China
12/5 - 12/7 @ Shanghai, China

Asia Game Show 2010
12/24 - 12/27  

GDC 2011
2/28 - 3/4 @ San Francisco, CA

More events...
Quick Stats
114 people currently visiting GDNet.
2406 articles in the reference section.

Help us fight cancer!
Join SETI Team GDNet!
Link to us Events 4 Gamers
Intel sponsors gamedev.net search:

C++ Trees Part 2: Basic core::tree<>Functionality


6. Conclusion

The primary goal of this article was to explain the design of the core::tree<> and the core::tree<>::iterator and the driving force behind that design. I had also hoped to explain the design in such a way that you, the reader, could understand the core::tree<> concepts well enough that they would seem natural and simple (as that is the greatest accomplishment anyone wishing to convey an idea can achieve).

Furthermore, this article was meant to identify and explain all interfaces currently implemented within the core::tree<> and the core::tree<>::iterator (sections 5.1 – 5.3).

After reading through the sections describing the core::tree<> and core::tree<>::iterator API, it may strike the reader as odd that the core::tree brings with it both ordered (insert) and unordered (push_front, push_back) insertion functionality.

The reasoning for these ordered and unordered insert interfaces is simple: a goal of the core::tree<> is to be a base framework for building a wide variety of very different and very specific trees. To achieve that end, it was identified that some trees need ordered inserts (nested sets [9]), yet others do not (control trees in compiler design [10]). Due to this varying need of ordered and unordered trees, both pieces of functionality were made available. This allows the programmer (particularly a tree designer) to achieve whatever goals he or she is hoping to, without hacking an interface that is restricting implementation in some way. Furthermore, the tree designer can then "block off" interfaces into the core::tree<> that conceptually violate the newly defined tree type's behavior, preventing clients from using that behavior.

Additionally, a number of working coding examples have been given throughout the article illustrating the use of the core::tree<> and the core::tree<>::iterator. I have tried to include as many diagrams as possible, displaying a variety of trees.

While I had hopes of having more concrete coding examples of trees (and their numerous uses), I did not want the sheer length of this article to become too daunting for readers, so I removed them. Further installments of the C++ tree series can be expected to contain more code snippets of varying trees.

As with all software, there will surely be bugs in the core::tree<>. I would like to apologize beforehand for any trouble you encounter using the core::tree<> and core::multitree<> libraries. Lastly, I would like to thank all of you for your generous feedback, criticisms and critiques, both private and public. Your input helps to make the core::tree<> library (and my writing) better.

7. Acknowledgements

I would like to thank Trevor Hill and David Stewart for supporting me in my pursuit of building a generic tree container and promoting its use in numerous areas. Mr. Stewart has been invaluable to the continual growth of the tree container. I would also like to thank Mark Holmes, Lori Peek and Paul Rogers for reviewing previous drafts of this article. Their feedback and editorial corrections have served to make this article more correct and clear. Lastly, any mistakes that have managed to find their way into the draft you are currently reading are solely the responsibility and fault of the author.

8. References

[1,2,3,9,11] Knuth, Donald. The Art of Computer Programming, Volume 1, 3rd edition. Addison-Wesley, Upper Saddle River, NJ 1997. p 308-312.

[4] Meyers, Scott. Effective STL. Addison-Wesley, Upper Saddle River, NJ 2001. preface.

[5] Josuttis, Nicolai M. The C++ Standard Library. Addison-Wesley, Upper Saddle River, NJ 1999. pp 73-82.

[6] Russell, Stuart and Peter Norvig. Artificial Intelligence: A Modern Approach, 2nd Edition. Prentice Hall, Upper Saddle River, NJ 2003. pp 94-105.

[7] Peitgen, Heinz-Otto, Hartmut Jurgens and Dietmar Saupe. Chaos and Fractals: New Frontiers of Science. Springer-Verlag. pp 63-66.

[8] Stroustrup, Bjarne. The C++ Programming Language, Special Edition. Addison-Wesley, Upper Saddle River, NJ 1997. p 962.

[10] Muchnick, Steven. Advanced Compiler Design and Implementation. Morgan Kaufmann Publishers, 340 Pine Street, Sixth Floor, San Francisco, CA 1997. p 198.

9. core::tree<> and core::multitree<> source

tree.h
multitree.h



Contents
  Introduction
  Concept of Design
  Subtleties of the core::tree<>
  The core::tree<> API
  Conclusion

  Printable version
  Discuss this article

The Series
  Part 1
  Part 2