C++ Trees Part 2: Basic core::tree<>Functionality
|
|
ADVERTISEMENT |
1. Introduction
One of the most highly respected computer scientists of the twenty-first century, Dr. Donald Knuth, describes trees as,
"the most important nonlinear structures that arise in computer algorithms." [1]
As Knuth argues above, trees are important. Unfortunately, trees are also complex. In his revered series of computer science books, The Art of Computer Programming, Dr. Knuth dedicates nearly one-fifth of his first volume solely to the discussion of trees, explaining their driving concepts and numerous uses. As detailed by Knuth in his text, the concepts surrounding trees are so vast it takes a great deal of energy to convey them correctly. It is my hope that this installment of the C++ tree series will explain the core::tree<> design and implementation correctly (and clearly) that when finishing this article, the core::tree<> design, implementation and use will seem simple and natural.
This article is presented in the following fashion:
- Introduction
- Terminology
- Concept of Design
- Subtleties of the core::tree<>
- The core::tree<> API
- Conclusion
- Acknowledgements
- References
- core::tree<> and core::multitree<> source
A detailed analysis of the design concepts used to build the core::tree<> and a thorough explanation of how those design concepts fit together, will be given. Moreover, all the current interfaces for the core::tree<> and the core::tree<>::iterator will be explained in detail. Coding examples are provided using the core::tree<> throughout the article.
2. Terminology
The acronym "STL" refers to C++'s Standard Template Library [4].
The term "single-level container" refers to a container with a single-level, such as a vector, set, list, deque, or any of the STL containers -- not a tree container, which can potentially contain many levels.
The terms "tree" and "subtree" will be used interchangeably throughout this article. In general, both terms refer to the same concept, except; 1) a tree contains a root node that has no parent and 2) a subtree has a root node that has a parent and, thus, is a child of a parent tree (as noted by Knuth's definition of trees below).
The term "node" will be used to identify the wrapper of a single element within a container, including tree containers.
The term "branch" will be used to identify a single node within a tree container and only a tree container.
The term "tree" and "subtree" will follow Knuth's definition from The Art of Computer Programming [2]:
A finite set T of one or more nodes such that:
- there is one specially designated node called the root of the tree, root(T); and
- the remaining nodes (excluding the root) are partitioned into m >= 0 disjoint sets T1, ..., Tm, and each of these sets in turn is a tree. The trees T1, ..., Tm are called the subtrees of the root.
Figure 2.1: Simple Tree
In short, the above definition says "trees are defined by trees". Truthfully, there is no distinction between a node in a tree and the tree itself (as all nodes in a tree are trees themselves). Knuth notes that his definition of trees is a recursive one, as he defines trees in terms of trees. He further explains that trees can be defined in nonrecursive ways, yet it is most appropriate to define trees recursively as recursion is an innate characteristic of tree structures [3].
Figure 2.1 illustrates the basic concepts of a tree. All nodes within the blue border make up the tree contained by node 1's root. All nodes within the green border on the left make up the subtree contained by node 2's root. All nodes within the green border on the right make up the subtree contained by node 3's root.
Node 1 is the root node of the entire tree. There is only one root node for the tree in its entirety. However, for each subtree there is a root node for that subtree, therefore each node of a tree is considered a root node for the subtree it creates (even if that subtree contains only the root node) [11].
For example, node 2 is the root node for the subtree created from 2, 4, 5 and 6, and node 3 is the root node for the subtree created from 3, 7, 8 and 9. Node 4 is also the root node for the subtree it creates, however, its subtree consists only of itself (node 4). The same is true of nodes 5, 6, 7, 8 and 9.
3. Concept of Design
3.1 A core::tree<> must be concretely constructed
Although this point is probably well understood, it bears mentioning here. Following the notion all STL containers follow, the core::tree<> container must be concretely constructed to exist. Nothing fancy is going on here, but this is an important clarification to ensure the concepts of the core::tree<> are clearly understood.
As stated in Knuth's definition of trees, there is one specially designated node of the tree called the root. While each subtree has its own root, only one root node exists for the tree in its entirety – the root for the entire tree. Conceptually, root node of the entire tree is the initial core::tree<> object. Therefore, for all uses of core::tree<> and core::tree<>::iterator, at least one core::tree<> object must be concretely constructed.
To concretely construct a core::tree<>, you might do the following:
core::tree<int> t;
In the above code sample, t is the root node of the entire tree and is a concrete core::tree<int> object. All modifications made through iterators based off of t are stored within the core::tree<> t. When t is destroyed, the entire tree t contains is destroyed. This is identical to the behavior of STL containers [5].
The point being made here may seem overly obvious (and that's good if it is), but it bears mentioning. The reasoning is, the core::tree<> and the core::tree<>::iterator are mostly interchangeable. However, simply constructing a core::tree<>::iterator will not create a core::tree<>. Additionally, each time a core::tree<> is concretely constructed, an entire tree is created.
That being said, each time a core::tree<>::iterator is constructed, nothing more than your typical iterator is constructed. When it is destructed, only the iterator (not the tree it points to) is destroyed.
3.2 Understanding the core::tree<> recursive characteristic
The recursive characteristic of trees is important to conceptualize when working with trees or understanding any generic framework or algorithm for trees [6] (i.e. the core::tree<> framework). A child node of one tree may be the parent node of another tree. While there is always one root node for the entire tree (as explained in section 3.1), a tree can have any number of children nodes. Each of these children nodes are root nodes to the subtrees they create.
Therefore, the role of a node in a tree changes depending on how it is viewed. In one case, a node may be a child node for a parent, merely existing to be iterated over for the larger container it resides in. Yet, in another case, the same node may be a parent node for several children, now acting as the container of perhaps, many children nodes.
This brings us to a fundamental rule for trees, which paraphrases Knuth's definition of trees:
All branches within a tree are trees themselves [7].
It is from this understanding that the core::tree<> implementation was designed, instinctively following Knuth's recursive tree definition and the notion of self-similarity (the concept that some "things" are made up of pieces that are similar to the "thing" they are making up, for example, trees) common in the field of chaos [7].
The following two concepts are fundamental to understanding the design of the core::tree<> family:
a core::tree<> is a core::tree<>::iterator
a core::tree<>::iterator is a core::tree<>
In both cases (trees as iterators and iterators as trees), it is important to understand that; 1) when given a core::tree<>, you also are given a core::tree<>::iterator – as any tree is also a node of a tree and 2) when given a core::tree<>::iterator, you are also given a core::tree<> – as any node within a tree is also a tree, itself.
The following two sections breakdown the above two concepts; 3.3) trees as iterators and 3.4) iterators as trees. A great deal of detail is spent clarifying these concepts as they are building blocks of the core::tree<> functionality.
3.3 A core::tree<> is core::tree<>::iterator
Each node within a tree is a tree itself. This follows Knuth's definition of trees. However, each node within a tree is just that as well, a node. Therefore, any level of a tree can be thought of as 1) a single-level store of trees and 2) a single-level store of nodes. For example, consider the following tree in Figure 3.1:
Figure 3.1: Isolating a single-level of a tree
In the green highlighted section of Figure 3.1, two nodes (b and c) are identified as children of node a. While b and c are subtrees themselves (i.e. containers), they must also be accessible from their containing parent. In order to first conceptualize this, consider b and c outside of the context of a tree and instead, in a single-level container.
If b and c were contained in a single-level (outside of a tree), they might look something like this:
Figure 3.2: Single-level view of a tree
Figure 3.2 shows how b and c would be contained by themselves outside of the context of a tree. Given this context, b and c could be wrapped in single-level container. For example, b and c could be stored within an std::set:
std::set<char> s;
s.insert('b');
s.insert('c');
To iterate through the single-level set, the following could be done:
for (std::set<char>::iterator iter = s.begin(); iter != s.end(); ++iter)
{
std::cout << *iter << std::endl;
}
In this case, an std::set<char>::iterator iter is used to move through the set elements one at a time. Thus, using the std::set<> example as a base concept of how a node can be iterated through in any single-level container, the same functionality must also be reproduced from the tree container – in other words, the core::tree<> must allow each node to be acted on as an iterator. Thankfully, it does this quite naturally.
Reproducing the same behavior as the single-level std::set<> with the core::tree<> is simple:
core::tree<char> t;
t.insert('b');
t.insert('c');
for (core::tree<char>::iterator iter = t.begin(); iter != t.end(); ++iter)
{
std::cout << *iter << std::endl;
}
With the exception of changing the container type and variable name, all other pieces of functionality are exactly the same in the tree implementation as in the set implementation. However, the underlying storage mechanism between the std::set<> and the core::tree<> are largely different. Each node within the std::set<> is simply a node. Each node within the core::tree<> is not only a node, but also a fully functional tree, with all the properties and functionality of the core::tree<> container. Given that context, each node of the core::tree<> must not only be a fully functioning tree, it must also be able to be acted upon as an iterator.
In summary, the above demonstrates why a core::tree<> must be a core::tree<>::iterator (as explained in the std::set<> coding example) and how they achieve this goal (as explained in the core::tree<> coding example). As stated initially, each node within the tree is a tree itself (including all the functionality of a tree), but also has all the functionality of an iterator. This is functionally important as without it, it would be impossible to iterate through a core::tree<> without the root core::tree<> container being passed to any piece of code that uses it.
3.4 A core::tree<>::iterator is a core::tree<>
To demonstrate the necessity of a core::tree<>::iterator behaving as a core::tree<> the tree example in section 3.3 can be built upon. To begin, it is necessary to first revisit the code in the previous section:
core::tree<char> t;
t.insert('b');
t.insert('c');
In the above code snippet, the tree t is concretely constructed and has two children inserted into it. According to the above code, the following tree is built:
Figure 3.3: b-c tree
Notice how the label is not present in the root node tree in Figure 3.3. The missing label can be fixed easily enough, it was simply not labeled before. The following code corrects the missing label issue (and includes all the code to rebuild the tree, include nodes: a, b and c):
core::tree<char> t;
*t = 'a'; // or t.data('a');
t.insert('b');
t.insert('c');
The following tree is now being built with a, b, and c clearly labeled (as seen in Figure 3.4):
Figure 3.4: a-b-c tree
To continue building the next level of the tree (beyond b and c), iterators of the core::tree<> are needed to access the deeper levels of the tree, as the nodes beyond b and c cannot be inserted directly from the core::tree<char> t (inserts, push_backs, push_fronts can only insert to the level directly underneath them).
Figure 3.5 shows the tree nodes currently built outlined in blue and the tree nodes not yet built outlined in green:
Figure 3.5: Building nodes: d, e, f and g
To insert nodes d, e, f and g, access to nodes b and c are first needed. This access is needed so insertion functionality can be called from b and c to insert their children. Nodes d and e can be inserted once access to node b is obtained. Nodes f and g can be inserted once access to node c is obtained.
Initially, the work to insert nodes d, e, f and g must be done with only the tree t (which is the 'a' node in figure 3.5), as only tree t is immediately available. From the core::tree<> t, search functionality can be called – single-level search functionality (i.e. find()) or multi-level search functionality (i.e. tree_find_depth(), tree_find_breadth()) – all of which return iterators to elements found from their search results. Since it is known that nodes b and c are one level below the tree's root node, a single-level find() can be used for gaining access to them.
Once the tree iterators (to nodes b and c) are obtained from the single-level find results of tree t, they can be used as tree containers and the remaining d, e, f and g nodes can be inserted into their subtrees.
It is important to note that while most of the work will be done with iterators, the insert functionality that will be performed is actually tree container functionality, not tree iterator functionality. An iterator is just a wrapper for an element that knows its location within a container. A container, on the other hand, is the store that holds those elements accessed by iterators. When dealing with the core::tree<> much of the functionality used within the iterator is actually container-based functionality, not iterator-based functionality.
The following code includes the initial tree building (a, b and c) and further contains the code required to insert nodes; d, e, f and g:
core::tree<char> t;
*t = 'a';
t.insert('b');
t.insert('c');
core::tree<char>::iterator iter;
// find the 'b' node
iter = t.find('b');
// insert nodes d and e inside the b tree
iter.insert('d');
iter.insert('e');
// find the 'c' node
iter = t.find('c');
// insert nodes f and g inside the c tree
iter.insert('f');
iter.insert('g');
With the above code, nodes d, e, f and g are inserted into their correct locations within the tree. As stated previously, the majority of the work done (total lines of code) is performed by tree iterators. However, 67% of the work done by the tree iterators is tree container-based functionality (4 of the 6 iterator calls highlighted in blue are 'inserts' – i.e. container functionality). Thus, the tree iterator is acting more like a tree container, than as a tree iterator.
To further drive home the point of tree iterators acting as tree containers, a closer look can be taken on how to output the tree generated by the previous code snippet. One way to perform that is through the following code:
std::cout << *t << std::endl;
for (iter = t.begin(); iter != t.end(); ++iter)
{
std::cout << *iter << std::endl;
for (core::tree<char>::iterator inner = iter.begin(); inner != iter.end(); ++inner)
{
std::cout << "\t" << *inner << std::endl;
}
}
Again, as seen from above, even in cases where the tree iterator is strongly performing tree iterator functionality, it is necessary for it to behave as a tree container. In the above code snippet, the two blue highlighted uses of iter (iter.begin() and iter.end()) are uses where the tree iterator is being called upon to perform tree container actions (begin() returns the first element of the tree, end() returns the last element of the tree).
In summary, scenarios have been shown where tree construction was only possible through first iterating to that point and then using that iterator to perform tree container functionality (as in the d, e, f, g code snippet). Additionally, a case has been shown where even performing highly iterator based functionality, tree iterators are required to act as tree containers to complete their assigned task (as in the above tree output code snippet).
Through the above two code snippets, it should be clear why tree iterators must act as tree containers and additionally, how these tree iterators perform their required tree container actions in a rather seamless manner.
4. Subtleties of the core::tree<>
The core::tree<> family consists of 4 generic trees:
core::tree - a tree that restricts element containment, like std::set
core::multitree - a tree with no element containment restriction, like std::multisetcore::tree_pair - a tree pair that restricts element containment, like std::map
core::multitree_pair - a tree pair with no element containment restriction, like std::multimap
Two trees of the core::tree family are not discussed in this article; tree_pair and multitree_pair. The functionality of core::tree_pair<> and core::tree_multipair<> is slightly more advanced than the core::tree<> and core::multitree<> and will be covered in later installments of the C++ tree series.
4.1 Differences between the tree container and the tree iterator
The basic functionality of core::tree<> containers and iterators are similar to that of STL's containers and iterators. A core::tree<> must be concretely constructed to store elements (as stated in 3.1). A core::tree<>::iterator must be created to iterate over those elements. Beyond these two definitions, the behavior begins to get a bit blurry.
When a core::tree<> is destroyed, its elements (its entire tree) are destroyed with it. When a core::tree<>::iterator is destroyed, only the iterator is destroyed, not the elements it currently points to.
For example, consider the following code:
int main()
{
core::multitree<int> t;
t.push_back(5);
t.push_back(3);
t.push_back(1);
t.push_back(5);
outputTree(t);
return 0;
}
void outputTree(const core::multitree<int>& t)
{
for (core::multitree<int>::iterator iter = t.begin(); iter != t.end(); ++iter)
{
std::cout << *iter << std::endl;
}
}
When the core::multitree<int> t goes out of scope in main(), all elements within it (5, 3, 1, 5) are destroyed, including the entire tree structure contained within it. However, when the outputTree() function exits and the iterator iter goes out of scope, only the iterator is destroyed, not the tree it points to.
Thus, the conceptual use of the core::tree<> and the core::tree<>::iterator are quite similar to that of STL's containers and iterators. A core::tree<>::iterator is used to iterate through a core::tree<> (and perform additional actions), but never actually destroy memory of the tree when going out of scope. A core::tree<> stores the tree structure and at least one concrete tree is needed to create a tree structure (as stated in section 3.1). When a concrete core::tree<> is destroyed (a concrete one, not a pointer or reference to one), all elements contained within are destroyed as well.
The fundamental difference between STL concepts of containers and iterators and the core::tree's concept of containers and iterators is that core::tree container actions can be (and must be) performed through iterators.
To further explain the differences between the core::tree<> and the core:: tree<>::iterator through a working example, consider building the following tree:
Figure 4.1: Building an integer tree
The core::tree<> family was designed with the innate recursive definition of trees in mind and therefore allows container functionality within iterators. An example of this is the following code, building the above tree in Figure 4.1 (the following code is intentionally different from the code written in section 3.4 to show different ways of performing the same actions using the core::tree<> library):
core::tree<int> t; // one core::tree<> must always be concretely constructed core::tree<int>::iterator iter; *t = 1; // store 1 as the root iter = t.push_back(2); // insert 2 into the first level // iter now points to the 2 tree, now 4, 5 and 6 can be pushed into it iter.push_back(4); iter.push_back(5); iter.push_back(6); iter = t.push_back(3); // insert 3 into the first level // iter now points to the 2 tree, now 7, 8 and 9 can be pushed into it iter.push_back(7); iter.push_back(8); iter.push_back(9);
The above code shows a sample behavior of core::tree<> and core::tree<>::iterator interaction. Once the core::tree<> is defined, most of the remaining work is done from a core::tree<>::iterator (or several iterators). However, the core::tree<>::iterator will generally perform actions of both the iterator and container (any time you have a core::tree<>::iterator, you really have an iterator and a tree).
In summary, some of the fundamental differences between a core::tree<> and a core::tree<>::iterator:
- When a core::tree<> goes out of scope (is destroyed) all elements from the tree are destroyed.
- When a core::tree<>::iterator goes out of scope (is destroyed) no elements of the tree are destroyed.
- A core::tree<>::iterator contains a pointer to the core::tree<> its currently pointing to. The tree contained within an iterator can be accessed directly from tree_ptr() or tree_ref() iterator functions.
- A core::tree<> can be wrapped inside of a core::tree<>::iterator. The tree_iterator() function of the core::tree<> can be called to return any core::tree<> as a core::tree<>::iterator.
- All insert, search and iteration functionality return iterators.
- All insert, search and removal functionality are called from trees.
At this point, it becomes clear that tree container and tree iterator functionality are generally performed through a tree iterator (once a concrete core::tree<> is defined somewhere). Yet, much of the work a tree iterator performs is actually tree container work. The iterator is not actually performing the functionality itself, instead it is merely passing a function call on from the client to the tree container, acting as a middle-man.
From the initial rules of recursion in sections 3.2 - 3.4, it is important to remember, 1) whenever you have a tree iterator, you also have a tree container and 2) whenever you have a tree container, you also have a tree iterator. Outside of the encapsulation of tree container functionality within a tree iterator (i.e. calling "begin()" from a tree iterator, which is clearly a tree container piece of functionality), there are direct ways to get access to the contained tree container (and vice versa).
Given a tree iterator, pointing to a valid tree, you can call tree_ptr() or tree_ref() to return the pointer or reference of the tree the iterator is pointing to. Given a tree container, you can call tree_iterator() to return the tree's wrapping iterator.
In many cases, a tree iterator can perform tree container actions directly through its tree-container-encapsulated iterator interface. However, in some rare cases, certain functionality can only be achieved through tree containers directly. Because of this, the tree_ptr(), tree_ref() functionality was created to enable tree iterators to return their contained tree container when needed. Likewise, the tree_iterator() functionality was created for the same purpose, except when converting a tree container into a tree iterator.
4.2 Differences between core::tree<> and core::multitree<>
The fundamental difference between the core::tree<> and the core::multitree<> is similar to the difference between std::set and std::multiset:
core::tree<> - at any given level within the tree, no more than one equivalent element can exist
core::multitree<> - at any given level within the tree, any number of equivalent elements can exist
Other than the single difference listed above, the core::tree<> and the core::multitree<> behaviors are the same.
4.3 core::tree<> requirements
In order to use the core::tree<> with your own user defined type (i.e. classes, structs), a few pieces of functionality may be required.
For example, consider the following class:
class SomeClass
{
private:
int someData_;
};
Before SomeClass can be contained within a core::tree as follows:
core::tree<SomeClass> someClassTree;
the following functionality may be required depending on how the core::tree<> is used with that class:
- must be default constructible (which SomeClass already is)
- may require operator<()
- may require operator==()
For native types (int, char, bool, etc.), the above three requirements are always fulfilled, so no additional work must be done for a core::tree<> to contain native types.
Moreover, it is possible to use the core::tree<> without the definition of operator<() and operator==() for the contained object type, as long as a predicate [8] is used for any insert() functions used and for any find() functions used. If predicates are used for both inserts and finds, the core::tree will use those predicates in place of the default operator<() and operator==() behaviors, respectively. In conjunction, push_front() and push_back() functionality can be used in place of insert() functionality to add items to the tree in an unordered way that does not require the definition of operator<() for the contained class.
5. The core::tree<> API
The following is a complete list of the core::tree<> container and core::tree<>::iterator (and core::multitree<> / core::multitree<>::iterator) functionality at the time of the writing of this article. As with all software, the core::tree<>, core::multitree<> and their iterators grow as more functionality is needed. The following list may change as revisions are inserted (more likely than not, the existing functionality will remain and only additions [not subtractions] will be made).
5.1 core::tree<> container functionality
Assignment:
const tree& operator=() - the assignment operator for the tree copies all contents from one tree to another, clearing the entire contents of the left-hand side (lhs) before assignment.
void copy_tree(const tree& in) - the copy_tree() function attempts to copy the entire contents of the passed in tree into the tree it is passed into. However, it does not clear the contents of the existing tree before copying (this would result in potential duplicate nodes in a multitree). Lastly, it does not copy the contents of the subtree's object whose tree it is receiving (i.e. the root data of the tree passed in is not copied to the receiving tree).
Iteration:
iterator tree_iterator() - returns the tree iterator of the tree.
iterator begin() const - returns the first element within the first level of the tree called into. For example, if the tree::iterator iter is defined and is currently on level 3 of the tree and iter.begin() is called, the first element on level 4 within iter's tree is returned.
iterator in() const - same functionality as begin() renamed to "in" for tree concept (stepping, "in" a level).
const iterator& end() const - returns the end iterator for all trees. The end iterator for all trees is the same, thus comparing an iterator against any tree's end will be equal if the iterator is at the end of the given tree.
iterator out() const - returns the containing parent of the tree. For example, if the tree::iterator iter is defined and is currently on level 3 of the tree and iter.out() is called, the parent of the iter on level 2 would be returned.
Access:
T& operator*() - returns a reference to the object contained within the node it is called on.
T& data() - same as operator*().
const T& data(const T&) - sets the current node's data and returns it.
const T& operator*() const - same as operator*(), except const.
const T& data() const - same as operator*() const.
Informative:
size_t level() const – returns the zero-based level of the current node.
size_t size() const - returns the number of children immediately contained within the tree (does not include the total number of nodes within the tree, just the children immediately within the tree).
Insertion:
iterator push_front(const T &inT) - inserts an element at the beginning of the subtree.
iterator push_back(const T &inT) - inserts an element at the end of the subtree.
iterator insert(const T &inT) - inserts an element into the tree as a direct child of the current tree. An iterator to the inserted child is returned. operator<() is used to determine where the insert occurs.
iterator insert(const T &inT, bool (*pObj)(const T&, const T&)) - inserts an element into the tree as a direct child of the current tree using a predicate function passed in as the second argument. An iterator to the inserted child is returned.
iterator insert(const iterator &i) - inserts an element into the tree passing an iterator as the argument (the element itself is what is inserted) as a direct child of the current tree. An iterator to the inserted child is returned. operator<() is used to determine where the insert occurs.
iterator reinsert(tree *in, bool (*pObj)(const T&, const T&)) - reinserts an existing tree into the current tree, using a predicate function as the second parameter. This works similar to the inserts of elements, except that the entire tree already exists and all the tree's children go with the insert. An iterator to the inserted child is returned.
iterator reinsert(tree *in) - reinserts an existing tree into the current tree. This works similar to the inserts of elements, except that the entire tree already exists and all the tree's children go with the insert. An iterator to the inserted child is returned. operator<() is used to determine where the insert occurs.
Removal:
void clear() - clears the current tree of all children within it. It does not remove the data element associated with the tree that calls this function.
bool remove(const T &in) - attempts to remove the passed in reference to the object from the tree's children. If the element is found and removed from the children's list from the tree, true is returned. Otherwise false is returned. operator== is the function used to determine equivalence in this function.
bool erase(const iterator& i) – attempts to remove the element contained within the iterator from the tree's children. If the element is found and removed from the children's list from the tree, true is returned. Otherwise false is returned. operator== is the function used to determine equivalence in this function.
Find:
iterator find(const T &inT) const - attempts to find an element from the tree's children. This search performs a single-level linear search. If the element is found, an iterator to the element is returned. operator== is the function used to determine equivalence in this function.
iterator find(const T &inT, bool (*obj)(const T&, const T&)) const - attempts to find an element from the tree's children. This search performs a single-level linear search. If the element is found, an iterator to the element is returned. The second argument passed in to this function as the predicate is used to determine equivalence.
iterator find(const T &inT, const iterator &iter) const – attempts to find an element from the tree's children, using the passed in iterator as the starting point to begin searching. This search performs a single-level linear search. If the element is found, an iterator to the element is returned. operator== is the function used to determine equivalence in this function.
iterator find(const T &inT, const iterator &iter, bool (*obj)(const T&, const T&)) const - attempts to find an element from the tree's children, using the passed in iterator as the starting point to begin searching. This search performs a single-level linear search. If the element is found, an iterator to the element is returned. operator== is the function used to determine equivalence in this function. The third argument passed in to this function as the predicate is used to determine equivalence.
iterator tree_find_depth(const T &inT) const - attempts to find an element in the tree, searching in depth first order. This search performs an entire tree search, starting from the tree's immediate children, until the innermost depth of the tree. If the element is found, an iterator to the element is returned. operator== is the function used to determine equivalence in this function.
iterator tree_find_depth(const T &inT, bool (*obj)(const T&, const T&)) const - attempts to find an element in the tree, searching in depth first order. This search performs an entire tree search, starting from the tree's immediate children, until the innermost depth of the tree. If the element is found, an iterator to the element is returned. The second argument passed in as the predicate is the function used to determine equivalence in this function.
iterator tree_find_depth(const T &inT, const iterator &iter) const - attempts to find an element in the tree, searching in depth first order, using the passed in iterator as the starting point for the search. This search performs an entire tree search, starting from the tree's immediate children, until the innermost depth of the tree. If the element is found, an iterator to the element is returned. operator== is the function used to determine equivalence in this function.
iterator tree_find_depth(const T &inT, const iterator &iter, bool (*obj)(const T&, const T&)) const - attempts to find an element in the tree, searching in depth first order, using the passed in iterator as the starting point for the search. This search performs an entire tree search, starting from the tree's immediate children, until the innermost depth of the tree. If the element is found, an iterator to the element is returned. The third argument passed in to this function as the predicate is used to determine equivalence.
iterator tree_find_breadth(const T &inT) const – attempts to find an element in the tree, searching in breadth first order. This search performs an entire tree search, starting from the tree's immediate children, until the innermost depth of the tree. If the element is found, an iterator to the element is returned. operator== is the function used to determine equivalence in this function.
iterator tree_find_breadth(const T &inT, bool (*obj)(const T&, const T&)) const – attempts to find an element in the tree, searching in breadth first order. This search performs an entire tree search, starting from the tree's immediate children, until the innermost depth of the tree. If the element is found, an iterator to the element is returned. The second argument passed in as the predicate is the function used to determine equivalence in this function.
iterator tree_find_breadth(const T &inT, const iterator &iter) const - attempts to find an element in the tree, searching in breadth first order, using the passed in iterator as the starting point for the search. This search performs an entire tree search, starting from the tree's immediate children, until the innermost depth of the tree. If the element is found, an iterator to the element is returned. operator== is the function used to determine equivalence in this function.
iterator tree_find_breadth(const T &inT, const iterator &iter, bool (*obj)(const T&, const T&)) const - attempts to find an element in the tree, searching in breadth first order, using the passed in iterator as the starting point for the search. This search performs an entire tree search, starting from the tree's immediate children, until the innermost depth of the tree. If the element is found, an iterator to the element is returned. The third argument passed in to this function as the predicate is used to determine equivalence.
5.2 core::tree<>::iterator functionality
Note: tree_iterator, core::tree<>::iterator and iterator are the same concept, however in some places in the source code due to the templatized nature of the tree code, tree_iterator is needed to define specific behavior. For example, the core::tree<>::iterator class is of tree_iterator type and therefore the destructor must be defined as a ~tree_iterator(). For all practical uses of the core::tree<>::iterator simply mentally replace tree_iterator with iterator.
Assignment:
iterator(const tree_iterator& i) – copy constructor for tree_iterators.
iterator(tree<T> &tree_ref) - copy constructor for trees.
iterator& operator=(const tree_iterator& iter) - operator=() for iterators.
const iterator& operator=(const tree_iterator& iter) const - operator=() for const iterators. Copying iterators isn't actually changing data, thus doing operator= as constant is logical.
const iterator& operator=(const tree<T>& rhs) const - operator=() for trees. This function simply pushes a tree into a tree_iterator.
Iteration:
const iterator& operator++() const - prefix increment on iterators. Again, iterating through iterates is not actually changing any data, therefore this constant member function is logical.
iterator operator++(int) const - postfix increment on iterators. Again, iterating through iterates is not actually changing any data, therefore this constant member function is logical.
const iterator& operator--() const - prefix decrement on iterators. However it is strongly suggested this is used minimally, as running off the beginning of a tree is easy to do as there is no check for validity as there is for incrementation (for example, begin() returns the iterator to the first element, end() returns the iterator past the last element). Therefore, using begin() to check for validity is only good against comparing to the starting point, not before the starting point.
Access:
tree<T>* tree_ptr() - returns the tree pointer contained within the iterator. This function should be used as minimally as possible. However, in some cases, access to the tree pointer contained by the iterator is necessary.
tree<T>& tree_ref() - returns the tree reference contained within the iterator. If this function is called and assigned to a concrete tree (not a tree reference) an entire copy of the tree will be made, locally. Be careful when using this function.
Comparison:
bool operator==(const tree_iterator& rhs) const - equivalence operator for iterators.
bool operator!=(const tree_iterator& rhs) const - nonequivalence operator for iterators.
Removal:
void clear_children() - removes all children within the tree (but not the tree itself)
5.3 Additional core::tree<>::iterator functionality
The following functionality is defined within the core::tree::iterator, but behaves exactly as it does within the core::tree<>:
Iteration:
iterator in() const
iterator out() const
const iterator& end() const
iterator next() const
Access:
T& operator*()
const T& operator*()
T& data()
const T& data() const
const T& data(const T &inData) const
Informative:
size_t size() const
size_t level() const
Insertion:
iterator push_back(const T& t)
iterator push_front(const T& t)
iterator insert(const T& t)
iterator insert(const T& t, bool (*obj)(const T&, const T&))
iterator reinsert(const iterator &in, bool (*obj)(const T&, const T&))
iterator reinsert(const iterator &in)
Removal:
bool remove(const T &inT)
void clear_tree()
Find:
iterator find(const T &inT) const
iterator find(const T &inT, bool (*obj)(const T&, const T&)) const
iterator find(const T &inT, const iterator &iter) const
iterator find(const T &inT, const iterator &iter, bool (*obj)(const T&, const T&)) const
iterator tree_find_depth(const T &inT) const
iterator tree_find_depth(const T &inT, bool (*obj)(const T&, const T&)) const
iterator tree_find_depth(const T &inT, const iterator &iter) const
iterator tree_find_depth(const T &inT, const iterator &iter, bool (*obj)(const T&, const T&)) const
iterator tree_find_breadth(const T &inT) const
iterator tree_find_breadth(const T &inT, bool (*obj)(const T&, const T&)) const
iterator tree_find_breadth(const T &inT, const iterator &iter) const
iterator tree_find_breadth(const T &inT, const iterator &iter, bool (*obj)(const T&, const T&)) const
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
Discuss this article in the forums
Date this article was posted to GameDev.net: 4/16/2005
(Note that this date does not necessarily correspond to the date the article was written)
See Also:
C and C++
Featured Articles
© 1999-2011 Gamedev.net. All rights reserved. Terms of Use Privacy Policy
Comments? Questions? Feedback? Click here!