00001 #pragma once 00002 00003 #include <vector> 00004 00005 namespace MosesTraining { 00006 namespace Syntax { 00007 00008 // A basic k-ary tree with node values of type T. Each node has a vector of 00009 // pointers to its children and a pointer to its parent (or 0 for the root). 00010 // 00011 // See the unit tests in tree_test.cc for examples of usage. 00012 // 00013 // Note: a Tree owns its children: it will delete them on destruction. 00014 // 00015 // Note: it's the user's responsibility to ensure that parent and child pointers 00016 // are correctly set and maintained. A convenient(-ish) way of building a 00017 // properly-connected tree is to add all the nodes as children of their 00018 // respective parents (using the children() accessor) and then call 00019 // SetParents() on the root at the end. 00020 // 00021 template<typename T> 00022 class Tree { 00023 public: 00024 // Constructors 00025 Tree() 00026 : value_() 00027 , children_() 00028 , parent_(0) {} 00029 00030 Tree(const T &value) 00031 : value_(value) 00032 , children_() 00033 , parent_(0) {} 00034 00035 // Destructor (deletes children) 00036 ~Tree(); 00037 00038 // Access tree's value. 00039 const T &value() const { return value_; } 00040 T &value() { return value_; } 00041 00042 // Access tree's parent. 00043 const Tree *parent() const { return parent_; } 00044 Tree *&parent() { return parent_; } 00045 00046 // Access tree's children. 00047 const std::vector<Tree *> &children() const { return children_; } 00048 std::vector<Tree *> &children() { return children_; } 00049 00050 // Set the parent values for this subtree (excluding this node). 00051 void SetParents(); 00052 00053 // Leaf predicate. 00054 bool IsLeaf() const { return children_.empty(); } 00055 00056 // Calculate the depth of this node within the tree (where the root has a 00057 // depth of 0, root's children have a depth 1, etc). 00058 std::size_t Depth() const; 00059 00060 // Iterators 00061 // 00062 // All iterators are forward iterators. Example use: 00063 // 00064 // const Tree<int> &root = GetMeATree(); 00065 // for (Tree<int>::ConstPreOrderIterator p(root); 00066 // p != Tree<int>::ConstPreOrderIterator(); ++p) { 00067 // std::cout << p->value() << "\n"; 00068 // } 00069 00070 private: 00071 // Use templates to avoid code duplication between const and non-const 00072 // iterators. V is the value type: either Tree<T> or const Tree<T>. 00073 template<typename V> class PreOrderIter; 00074 // template<typename V> class PostOrderIter; TODO 00075 template<typename V> class LeafIter; 00076 00077 public: 00078 // Pre-order iterators. 00079 typedef PreOrderIter<Tree<T> > PreOrderIterator; 00080 typedef PreOrderIter<const Tree<T> > ConstPreOrderIterator; 00081 00082 // Post-order iterators. 00083 // typedef PostOrderIter<Tree<T> > PostOrderIterator; TODO 00084 // typedef PostOrderIter<const Tree<T> > ConstPostOrderIterator; TODO 00085 00086 // Leaf iterators (left-to-right). 00087 typedef LeafIter<Tree<T> > LeafIterator; 00088 typedef LeafIter<const Tree<T> > ConstLeafIterator; 00089 00090 private: 00091 T value_; 00092 std::vector<Tree *> children_; 00093 Tree *parent_; 00094 }; 00095 00096 } // namespace Syntax 00097 } // namespace MosesTraining 00098 00099 #include "tree-inl.h"