#include <tree.h>
This implementation allows one to quickly get the parent, child, or siblings of any node. All data put into a Tree must be a subclass of TreeNode. TreeNode will automatically manage all of the parent/child/sibling pointers as well as the LargeIndexes for you. For more information on how to implement a TreeNode, see that page.
There are two ways to access nodes in these data structures: either by looking at the root node and traversing the tree manually by using the parent/child/sibling relationships, or by specifying a LargeIndex describing a path down the tree. These indices are set up and maintained such that at the nth level of the tree, the LargeIndex has size n (the root node has size 0 which is an empty LargeIndex). The ith element of the LargeIndex specifies the link traversed to get from the (i-1)st level to the ith level.
The sibling pointers are managed such that GetNextSibling() always returns a Bin with the next highest index in that branch of the tree. This multi-resolution histogram is stored sparsely: if you consider the Bins referred to by [0 1] and [0 3], it is possible that [0 3] is the sibling after [0 1] (as long as there is no such bin [0 2]).
Note that using LargeIndex and the link structure between Bins is redundant, as a LargeIndex specifies a path down the tree. When reading and writing the Tree to disk, we only persist the LargeIndexes-- the link structure is inferred from the LargeIndex values upon reading from disk. The purpose of the link structure is to speed up computations and lookups.
** If you have build problems: remember that since Tree is a class template, when using your own TreeNodes in a Tree, you'll run into linker errors if you don't do an explicit instantiation of Tree<YourTreeNode>. To deal with this, you will need to do two things:
If you are still having problems:
TreeNode constructors: the default one, which takes no arguments, and the one which takes a const LargeIndex&. MyNode::MyNode(const MyNode& other) : TreeNode(other) {
// your copy code
} WriteData is a const function.
Public Member Functions | |
| Tree () | |
| ~Tree () | |
| Tree (const Tree< T > &other) | |
| Copy constructor. | |
| Tree (const Tree< T > &one, const Tree< T > &two) | |
| T *const | GetRootNode () const |
| Get a pointer to the root node. | |
| int | GetNumNodes () const |
| Get the total number of nodes in the tree. | |
| T * | GetNode (const LargeIndex &index) |
| Get a node specified by the given index. | |
| T * | GetNode (const LargeIndex &index, TreeNode *finger) |
| Get a pointer to the node with the specified index. | |
| T * | GetRootNode () |
| Get a pointer to the node with specified index. | |
| T * | AddNode (const T &new_node) |
| Insert a copy of the given node into the tree. | |
| T * | AddNode (const T &new_node, TreeNode *parent) |
| Insert a copy of the given bin into the tree. | |
| void | ReadFromStream (istream &input_stream) |
| Reads a tree from the stream. | |
| void | WriteToStream (ostream &output_stream) const |
| Write the tree to a stream. | |
| void | DeleteNode (TreeNode *node) |
| Removes a node, and all of its children, from the tree. | |
| PreorderIterator | BeginPreorder () const |
| Start of a preorder depth-first traversal. | |
| PostorderIterator | BeginPostorder () const |
| Start of a postorder depth-first traversal. | |
| BreadthFirstIterator | BeginBreadthFirst () const |
| Start of a breadth-first traversal. | |
Static Public Member Functions | |
| static const PreorderIterator & | EndPreorder () |
| End of a preorder depth-first traversal. | |
| static const PostorderIterator & | EndPostorder () |
| End of a postorder depth-first traversal. | |
| static const BreadthFirstIterator & | EndBreadthFirst () |
| End of a breadth-first traversal. | |
Classes | |
| class | BreadthFirstIterator |
| Breadth-first iterator for Trees. More... | |
| class | Iterator |
| An iterator for Trees. More... | |
| class | PostorderIterator |
| class | PreorderIterator |
| Preorder depth-first iterator for Trees. More... | |
| Tree | ( | ) |
| ~Tree | ( | ) |
| T *const GetRootNode | ( | ) | const |
Get a pointer to the root node.
| int GetNumNodes | ( | ) | const |
Get the total number of nodes in the tree.
| T * GetNode | ( | const LargeIndex & | index | ) |
Get a node specified by the given index.
| T * GetNode | ( | const LargeIndex & | index, | |
| TreeNode * | finger | |||
| ) |
Get a pointer to the node with the specified index.
Returns NULL if the node is not found.
| T * GetRootNode | ( | ) |
Get a pointer to the node with specified index.
Same as GetNode(LargeIndex), but localizes the search to the subtree given by <finger>. Returns NULL if there is no such node in a subtree of <finger>.
| T * AddNode | ( | const T & | new_node | ) |
Insert a copy of the given node into the tree.
Returns a pointer to the newly-added node in the tree. This function completely ignores any parent/child/sibling pointers in <new_node>.
This function requires the parent bin to already exist in the tree. It will NOT create new bins along the way (it will abort if there is no parent node, i.e., a node whose index is a prefix of that of <new_node> and whose index size is exactly 1 less than the new node's index size. The insertion happens such that the sibling relationships remain sorted by index.
If there is already is a node with the given index (call it N), we call N.Combine(new_node), and no new node is inserted into the tree. This applies to the root node as well.
| T * AddNode | ( | const T & | new_node, | |
| TreeNode * | parent | |||
| ) |
Insert a copy of the given bin into the tree.
Same as AddBin(const Node&), except it starts the search for the bin at <parent>. In this case, <parent> must be the direct parent of the node we are inserting (it cannot be a higher-up ancestor).
| void ReadFromStream | ( | istream & | input_stream | ) |
Reads a tree from the stream.
File format:
The ordering of the bins is a depth-first traversal of the tree.
Aborts if the stream is bad.
| void WriteToStream | ( | ostream & | output_stream | ) | const |
Write the tree to a stream.
Aborts if the stream is bad. See ReadFromStream for the format.
| void DeleteNode | ( | TreeNode * | node | ) |
Removes a node, and all of its children, from the tree.
The node must be owned by this tree. Tree will not check for that.
| Tree< T >::PreorderIterator BeginPreorder | ( | ) | const |
Start of a preorder depth-first traversal.
| const Tree< T >::PreorderIterator & EndPreorder | ( | ) | [static] |
End of a preorder depth-first traversal.
| Tree< T >::PostorderIterator BeginPostorder | ( | ) | const |
Start of a postorder depth-first traversal.
| const Tree< T >::PostorderIterator & EndPostorder | ( | ) | [static] |
End of a postorder depth-first traversal.
| Tree< T >::BreadthFirstIterator BeginBreadthFirst | ( | ) | const |
Start of a breadth-first traversal.
| const Tree< T >::BreadthFirstIterator & EndBreadthFirst | ( | ) | [static] |
End of a breadth-first traversal.
1.5.1