include/llvm/ADT/DepthFirstIterator.h

   1 //===- Support/DepthFirstIterator.h - Depth First iterator ------*- C++ -*-===//
   2 //
   3 // This file builds on the Support/GraphTraits.h file to build generic depth
   4 // first graph iterator.  This file exposes the following functions/types:
   5 //
   6 // df_begin/df_end/df_iterator
   7 //   * Normal depth-first iteration - visit a node and then all of its children.
   8 //
   9 // idf_begin/idf_end/idf_iterator
  10 //   * Depth-first iteration on the 'inverse' graph.
  11 //
  12 // df_ext_begin/df_ext_end/df_ext_iterator
  13 //   * Normal depth-first iteration - visit a node and then all of its children.
  14 //     This iterator stores the 'visited' set in an external set, which allows
  15 //     it to be more efficient, and allows external clients to use the set for
  16 //     other purposes.
  17 //
  18 // idf_ext_begin/idf_ext_end/idf_ext_iterator
  19 //   * Depth-first iteration on the 'inverse' graph.
  20 //     This iterator stores the 'visited' set in an external set, which allows
  21 //     it to be more efficient, and allows external clients to use the set for
  22 //     other purposes.
  23 //
  24 //===----------------------------------------------------------------------===//
  25
  26 #ifndef SUPPORT_DEPTHFIRSTITERATOR_H
  27 #define SUPPORT_DEPTHFIRSTITERATOR_H
  28
  29 #include "Support/GraphTraits.h"
  30 #include "Support/iterator"
  31 #include <vector>
  32 #include <set>
  33
  34 // df_iterator_storage - A private class which is used to figure out where to
  35 // store the visited set.
  36 template<class SetType, bool External>   // Non-external set
  37 class df_iterator_storage {
  38 public:
  39   SetType Visited;
  40 };
  41
  42 template<class SetType>
  43 class df_iterator_storage<SetType, true> {
  44 public:
  45   df_iterator_storage(SetType &VSet) : Visited(VSet) {}
  46   df_iterator_storage(const df_iterator_storage &S) : Visited(S.Visited) {}
  47   SetType &Visited;
  48 };
  49
  50
  51 // Generic Depth First Iterator
  52 template<class GraphT, class SetType =
  53                             std::set<typename GraphTraits<GraphT>::NodeType*>,
  54          bool ExtStorage = false, class GT = GraphTraits<GraphT> >
  55 class df_iterator : public forward_iterator<typename GT::NodeType, ptrdiff_t>,
  56                     public df_iterator_storage<SetType, ExtStorage> {
  57   typedef forward_iterator<typename GT::NodeType, ptrdiff_t> super;
  58
  59   typedef typename GT::NodeType          NodeType;
  60   typedef typename GT::ChildIteratorType ChildItTy;
  61
  62   // VisitStack - Used to maintain the ordering.  Top = current block
  63   // First element is node pointer, second is the 'next child' to visit
  64   std::vector<std::pair<NodeType *, ChildItTy> > VisitStack;
  65 private:
  66   inline df_iterator(NodeType *Node) {
  67     this->Visited.insert(Node);
  68     VisitStack.push_back(std::make_pair(Node, GT::child_begin(Node)));
  69   }
  70   inline df_iterator() { /* End is when stack is empty */ }
  71
  72   inline df_iterator(NodeType *Node, SetType &S)
  73     : df_iterator_storage<SetType, ExtStorage>(S) {
  74     if (!S.count(Node)) {
  75       this->Visited.insert(Node);
  76       VisitStack.push_back(std::make_pair(Node, GT::child_begin(Node)));
  77     }
  78   }
  79   inline df_iterator(SetType &S)
  80     : df_iterator_storage<SetType, ExtStorage>(S) {
  81     // End is when stack is empty
  82   }
  83
  84 public:
  85   typedef typename super::pointer pointer;
  86   typedef df_iterator<GraphT, SetType, ExtStorage, GT> _Self;
  87
  88   // Provide static begin and end methods as our public "constructors"
  89   static inline _Self begin(GraphT G) {
  90     return _Self(GT::getEntryNode(G));
  91   }
  92   static inline _Self end(GraphT G) { return _Self(); }
  93
  94   // Static begin and end methods as our public ctors for external iterators
  95   static inline _Self begin(GraphT G, SetType &S) {
  96     return _Self(GT::getEntryNode(G), S);
  97   }
  98   static inline _Self end(GraphT G, SetType &S) { return _Self(S); }
  99
 100   inline bool operator==(const _Self& x) const {
 101     return VisitStack.size() == x.VisitStack.size() &&
 102            VisitStack == x.VisitStack;
 103   }
 104   inline bool operator!=(const _Self& x) const { return !operator==(x); }
 105
 106   inline pointer operator*() const {
 107     return VisitStack.back().first;
 108   }
 109
 110   // This is a nonstandard operator-> that dereferences the pointer an extra
 111   // time... so that you can actually call methods ON the Node, because
 112   // the contained type is a pointer.  This allows BBIt->getTerminator() f.e.
 113   //
 114   inline NodeType *operator->() const { return operator*(); }
 115
 116   inline _Self& operator++() {   // Preincrement
 117     do {
 118       std::pair<NodeType *, ChildItTy> &Top = VisitStack.back();
 119       NodeType *Node = Top.first;
 120       ChildItTy &It  = Top.second;
 121
 122       while (It != GT::child_end(Node)) {
 123         NodeType *Next = *It++;
 124         if (!this->Visited.count(Next)) {  // Has our next sibling been visited?
 125           // No, do it now.
 126           this->Visited.insert(Next);
 127           VisitStack.push_back(std::make_pair(Next, GT::child_begin(Next)));
 128           return *this;
 129         }
 130       }
 131
 132       // Oops, ran out of successors... go up a level on the stack.
 133       VisitStack.pop_back();
 134     } while (!VisitStack.empty());
 135     return *this;
 136   }
 137
 138   inline _Self operator++(int) { // Postincrement
 139     _Self tmp = *this; ++*this; return tmp;
 140   }
 141
 142   // nodeVisited - return true if this iterator has already visited the
 143   // specified node.  This is public, and will probably be used to iterate over
 144   // nodes that a depth first iteration did not find: ie unreachable nodes.
 145   //
 146   inline bool nodeVisited(NodeType *Node) const {
 147     return this->Visited.count(Node) != 0;
 148   }
 149 };
 150
 151
 152 // Provide global constructors that automatically figure out correct types...
 153 //
 154 template <class T>
 155 df_iterator<T> df_begin(T G) {
 156   return df_iterator<T>::begin(G);
 157 }
 158
 159 template <class T>
 160 df_iterator<T> df_end(T G) {
 161   return df_iterator<T>::end(G);
 162 }
 163
 164 // Provide global definitions of external depth first iterators...
 165 template <class T, class SetTy = std::set<typename GraphTraits<T>::NodeType*> >
 166 struct df_ext_iterator : public df_iterator<T, SetTy, true> {
 167   df_ext_iterator(const df_iterator<T, SetTy, true> &V)
 168     : df_iterator<T, SetTy, true>(V) {}
 169 };
 170
 171 template <class T, class SetTy>
 172 df_ext_iterator<T, SetTy> df_ext_begin(T G, SetTy &S) {
 173   return df_ext_iterator<T, SetTy>::begin(G, S);
 174 }
 175
 176 template <class T, class SetTy>
 177 df_ext_iterator<T, SetTy> df_ext_end(T G, SetTy &S) {
 178   return df_ext_iterator<T, SetTy>::end(G, S);
 179 }
 180
 181
 182 // Provide global definitions of inverse depth first iterators...
 183 template <class T, class SetTy = std::set<typename GraphTraits<T>::NodeType*>,
 184           bool External = false>
 185 struct idf_iterator : public df_iterator<Inverse<T>, SetTy, External> {
 186   idf_iterator(const df_iterator<Inverse<T>, SetTy, External> &V)
 187     : df_iterator<Inverse<T>, SetTy, External>(V) {}
 188 };
 189
 190 template <class T>
 191 idf_iterator<T> idf_begin(T G) {
 192   return idf_iterator<T>::begin(G);
 193 }
 194
 195 template <class T>
 196 idf_iterator<T> idf_end(T G){
 197   return idf_iterator<T>::end(G);
 198 }
 199
 200 // Provide global definitions of external inverse depth first iterators...
 201 template <class T, class SetTy = std::set<typename GraphTraits<T>::NodeType*> >
 202 struct idf_ext_iterator : public idf_iterator<T, SetTy, true> {
 203   idf_ext_iterator(const idf_iterator<T, SetTy, true> &V)
 204     : idf_iterator<T, SetTy, true>(V) {}
 205   idf_ext_iterator(const df_iterator<Inverse<T>, SetTy, true> &V)
 206     : idf_iterator<T, SetTy, true>(V) {}
 207 };
 208
 209 template <class T, class SetTy>
 210 idf_ext_iterator<T, SetTy> idf_ext_begin(T G, SetTy &S) {
 211   return idf_ext_iterator<T, SetTy>::begin(G, S);
 212 }
 213
 214 template <class T, class SetTy>
 215 idf_ext_iterator<T, SetTy> idf_ext_end(T G, SetTy &S) {
 216   return idf_ext_iterator<T, SetTy>::end(G, S);
 217 }
 218
 219
 220 #endif