00001 #pragma once
00002
00003 #include <stack>
00004 #include <vector>
00005
00006 namespace MosesTraining {
00007 namespace Syntax {
00008
00009 template<typename T>
00010 Tree<T>::~Tree() {
00011 for (typename std::vector<Tree *>::iterator p = children_.begin();
00012 p != children_.end(); ++p) {
00013 delete *p;
00014 }
00015 }
00016
00017 template<typename T>
00018 void Tree<T>::SetParents() {
00019 for (typename std::vector<Tree *>::iterator p = children_.begin();
00020 p != children_.end(); ++p) {
00021 (*p)->parent() = this;
00022 (*p)->SetParents();
00023 }
00024 }
00025
00026 template<typename T>
00027 std::size_t Tree<T>::Depth() const {
00028 std::size_t depth = 0;
00029 Tree *ancestor = parent_;
00030 while (ancestor != 0) {
00031 ++depth;
00032 ancestor = ancestor->parent_;
00033 }
00034 return depth;
00035 }
00036
00037 template<typename T>
00038 template<typename V>
00039 class Tree<T>::PreOrderIter {
00040 public:
00041 PreOrderIter();
00042 PreOrderIter(V &);
00043
00044 V &operator*() { return *node_; }
00045 V *operator->() { return node_; }
00046
00047 PreOrderIter &operator++();
00048 PreOrderIter operator++(int);
00049
00050 bool operator==(const PreOrderIter &);
00051 bool operator!=(const PreOrderIter &);
00052
00053 private:
00054
00055 V *node_;
00056
00057
00058
00059 std::stack<std::size_t> index_stack_;
00060 };
00061
00062 template<typename T>
00063 template<typename V>
00064 Tree<T>::PreOrderIter<V>::PreOrderIter()
00065 : node_(0) {
00066 }
00067
00068 template<typename T>
00069 template<typename V>
00070 Tree<T>::PreOrderIter<V>::PreOrderIter(V &t)
00071 : node_(&t) {
00072 }
00073
00074 template<typename T>
00075 template<typename V>
00076 Tree<T>::PreOrderIter<V> &Tree<T>::PreOrderIter<V>::operator++() {
00077
00078 if (!node_->children().empty()) {
00079 index_stack_.push(0);
00080 node_ = node_->children()[0];
00081 return *this;
00082 }
00083
00084
00085
00086 V *ancestor = node_->parent_;
00087 while (ancestor) {
00088 std::size_t index = index_stack_.top();
00089 index_stack_.pop();
00090 if (index+1 < ancestor->children_.size()) {
00091 index_stack_.push(index+1);
00092 node_ = ancestor->children()[index+1];
00093 return *this;
00094 }
00095 ancestor = ancestor->parent_;
00096 }
00097 node_ = 0;
00098 return *this;
00099 }
00100
00101 template<typename T>
00102 template<typename V>
00103 Tree<T>::PreOrderIter<V> Tree<T>::PreOrderIter<V>::operator++(int) {
00104 PreOrderIter tmp(*this);
00105 ++*this;
00106 return tmp;
00107 }
00108
00109 template<typename T>
00110 template<typename V>
00111 bool Tree<T>::PreOrderIter<V>::operator==(const PreOrderIter &rhs) {
00112 return node_ == rhs.node_;
00113 }
00114
00115 template<typename T>
00116 template<typename V>
00117 bool Tree<T>::PreOrderIter<V>::operator!=(const PreOrderIter &rhs) {
00118 return node_ != rhs.node_;
00119 }
00120
00121 template<typename T>
00122 template<typename V>
00123 class Tree<T>::LeafIter {
00124 public:
00125 LeafIter();
00126 LeafIter(V &);
00127
00128 V &operator*() { return *node_; }
00129 V *operator->() { return node_; }
00130
00131 LeafIter &operator++();
00132 LeafIter operator++(int);
00133
00134 bool operator==(const LeafIter &);
00135 bool operator!=(const LeafIter &);
00136
00137 private:
00138
00139 V *node_;
00140
00141
00142
00143 std::stack<std::size_t> index_stack_;
00144 };
00145
00146 template<typename T>
00147 template<typename V>
00148 Tree<T>::LeafIter<V>::LeafIter()
00149 : node_(0) {
00150 }
00151
00152 template<typename T>
00153 template<typename V>
00154 Tree<T>::LeafIter<V>::LeafIter(V &t)
00155 : node_(&t) {
00156
00157 while (!node_->IsLeaf()) {
00158 index_stack_.push(0);
00159 node_ = node_->children()[0];
00160 }
00161 }
00162
00163 template<typename T>
00164 template<typename V>
00165 Tree<T>::LeafIter<V> &Tree<T>::LeafIter<V>::operator++() {
00166
00167
00168 V *ancestor = node_->parent_;
00169 while (ancestor) {
00170 std::size_t index = index_stack_.top();
00171 index_stack_.pop();
00172 if (index+1 < ancestor->children_.size()) {
00173 index_stack_.push(index+1);
00174 node_ = ancestor->children()[index+1];
00175
00176 while (!node_->IsLeaf()) {
00177 index_stack_.push(0);
00178 node_ = node_->children()[0];
00179 }
00180 return *this;
00181 }
00182 ancestor = ancestor->parent_;
00183 }
00184 node_ = 0;
00185 return *this;
00186 }
00187
00188 template<typename T>
00189 template<typename V>
00190 Tree<T>::LeafIter<V> Tree<T>::LeafIter<V>::operator++(int) {
00191 LeafIter tmp(*this);
00192 ++*this;
00193 return tmp;
00194 }
00195
00196 template<typename T>
00197 template<typename V>
00198 bool Tree<T>::LeafIter<V>::operator==(const LeafIter &rhs) {
00199 return node_ == rhs.node_;
00200 }
00201
00202 template<typename T>
00203 template<typename V>
00204 bool Tree<T>::LeafIter<V>::operator!=(const LeafIter &rhs) {
00205 return node_ != rhs.node_;
00206 }
00207
00208 }
00209 }