| 130 | // states (pair of node pointer and child iterator) as we walk it. |
| 131 | template <typename NodeTy> |
| 132 | class PostOrderTreeDFIterator { |
| 133 | static_assert(!std::is_pointer<NodeTy>::value && |
| 134 | !std::is_reference<NodeTy>::value, |
| 135 | "NodeTy should be a class"); |
| 136 | // Type alias to keep track of the const qualifier. |
| 137 | using NodeIterator = |
| 138 | typename std::conditional<std::is_const<NodeTy>::value, |
| 139 | typename NodeTy::const_iterator, |
| 140 | typename NodeTy::iterator>::type; |
| 141 | |
| 142 | // Type alias to keep track of the const qualifier. |
| 143 | using NodePtr = NodeTy*; |
| 144 | |
| 145 | public: |
| 146 | // Standard iterator interface. |
| 147 | using reference = NodeTy&; |
| 148 | using value_type = NodeTy; |
| 149 | |
| 150 | static inline PostOrderTreeDFIterator begin(NodePtr top_node) { |
| 151 | return PostOrderTreeDFIterator(top_node); |
| 152 | } |
| 153 | |
| 154 | static inline PostOrderTreeDFIterator end(NodePtr sentinel_node) { |
| 155 | return PostOrderTreeDFIterator(sentinel_node, false); |
| 156 | } |
| 157 | |
| 158 | bool operator==(const PostOrderTreeDFIterator& x) const { |
| 159 | return current_ == x.current_; |
| 160 | } |
| 161 | |
| 162 | bool operator!=(const PostOrderTreeDFIterator& x) const { |
| 163 | return !(*this == x); |
| 164 | } |
| 165 | |
| 166 | reference operator*() const { return *current_; } |
| 167 | |
| 168 | NodePtr operator->() const { return current_; } |
| 169 | |
| 170 | PostOrderTreeDFIterator& operator++() { |
| 171 | MoveToNextNode(); |
| 172 | return *this; |
| 173 | } |
| 174 | |
| 175 | PostOrderTreeDFIterator operator++(int) { |
| 176 | PostOrderTreeDFIterator tmp = *this; |
| 177 | ++*this; |
| 178 | return tmp; |
| 179 | } |
| 180 | |
| 181 | private: |
| 182 | explicit inline PostOrderTreeDFIterator(NodePtr top_node) |
| 183 | : current_(top_node) { |
| 184 | if (current_) WalkToLeaf(); |
| 185 | } |
| 186 | |
| 187 | // Constructor for the "end()" iterator. |
| 188 | // |end_sentinel| is the value that acts as end value (can be null). The bool |
| 189 | // parameters is to distinguish from the start() Ctor. |