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

Conclusion