1 //===- llvm/ADT/BreadthFirstIterator.h - Breadth First iterator -*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file builds on the ADT/GraphTraits.h file to build a generic breadth
11 // first graph iterator. This file exposes the following functions/types:
13 // bf_begin/bf_end/bf_iterator
14 // * Normal breadth-first iteration - visit a graph level-by-level.
16 //===----------------------------------------------------------------------===//
18 #ifndef LLVM_ADT_BREADTHFIRSTITERATOR_H
19 #define LLVM_ADT_BREADTHFIRSTITERATOR_H
21 #include "llvm/ADT/GraphTraits.h"
22 #include "llvm/ADT/None.h"
23 #include "llvm/ADT/Optional.h"
24 #include "llvm/ADT/SmallPtrSet.h"
25 #include "llvm/ADT/iterator_range.h"
32 // bf_iterator_storage - A private class which is used to figure out where to
33 // store the visited set. We only provide a non-external variant for now.
34 template <class SetType> class bf_iterator_storage {
39 // The visited state for the iteration is a simple set.
40 template <typename NodeRef, unsigned SmallSize = 8>
41 using bf_iterator_default_set = SmallPtrSet<NodeRef, SmallSize>;
43 // Generic Breadth first search iterator.
44 template <class GraphT,
46 bf_iterator_default_set<typename GraphTraits<GraphT>::NodeRef>,
47 class GT = GraphTraits<GraphT>>
49 : public std::iterator<std::forward_iterator_tag, typename GT::NodeRef>,
50 public bf_iterator_storage<SetType> {
51 using super = std::iterator<std::forward_iterator_tag, typename GT::NodeRef>;
53 using NodeRef = typename GT::NodeRef;
54 using ChildItTy = typename GT::ChildIteratorType;
56 // First element is the node reference, second is the next child to visit.
57 using QueueElement = std::pair<NodeRef, Optional<ChildItTy>>;
59 // Visit queue - used to maintain BFS ordering.
60 // Optional<> because we need markers for levels.
61 std::queue<Optional<QueueElement>> VisitQueue;
67 inline bf_iterator(NodeRef Node) {
68 this->Visited.insert(Node);
71 // Also, insert a dummy node as marker.
72 VisitQueue.push(QueueElement(Node, None));
73 VisitQueue.push(None);
76 inline bf_iterator() = default;
78 inline void toNext() {
79 Optional<QueueElement> Head = VisitQueue.front();
80 QueueElement H = Head.getValue();
81 NodeRef Node = H.first;
82 Optional<ChildItTy> &ChildIt = H.second;
85 ChildIt.emplace(GT::child_begin(Node));
86 while (*ChildIt != GT::child_end(Node)) {
87 NodeRef Next = *(*ChildIt)++;
90 if (this->Visited.insert(Next).second)
91 VisitQueue.push(QueueElement(Next, None));
95 // Go to the next element skipping markers if needed.
96 if (!VisitQueue.empty()) {
97 Head = VisitQueue.front();
103 // Don't push another marker if this is the last
105 if (!VisitQueue.empty())
106 VisitQueue.push(None);
111 using pointer = typename super::pointer;
113 // Provide static begin and end methods as our public "constructors"
114 static bf_iterator begin(const GraphT &G) {
115 return bf_iterator(GT::getEntryNode(G));
118 static bf_iterator end(const GraphT &G) { return bf_iterator(); }
120 bool operator==(const bf_iterator &RHS) const {
121 return VisitQueue == RHS.VisitQueue;
124 bool operator!=(const bf_iterator &RHS) const { return !(*this == RHS); }
126 const NodeRef &operator*() const { return VisitQueue.front()->first; }
128 // This is a nonstandard operator-> that dereferenfces the pointer an extra
129 // time so that you can actually call methods on the node, because the
130 // contained type is a pointer.
131 NodeRef operator->() const { return **this; }
133 bf_iterator &operator++() { // Pre-increment
138 bf_iterator operator++(int) { // Post-increment
139 bf_iterator ItCopy = *this;
144 unsigned getLevel() const { return Level; }
147 // Provide global constructors that automatically figure out correct types.
148 template <class T> bf_iterator<T> bf_begin(const T &G) {
149 return bf_iterator<T>::begin(G);
152 template <class T> bf_iterator<T> bf_end(const T &G) {
153 return bf_iterator<T>::end(G);
156 // Provide an accessor method to use them in range-based patterns.
157 template <class T> iterator_range<bf_iterator<T>> breadth_first(const T &G) {
158 return make_range(bf_begin(G), bf_end(G));
161 } // end namespace llvm
163 #endif // LLVM_ADT_BREADTHFIRSTITERATOR_H