Extend StringRef's edit-distance algorithm to permit an upper bound on the allowed...

[oota-llvm.git] / include / llvm / ADT / GraphTraits.h

diff --git a/include/llvm/ADT/GraphTraits.h b/include/llvm/ADT/GraphTraits.h
index 99a69b8cc87f1cec52d2542004093872c93e0e42..0fd1f5022af77e9b904675e28c77b8cf7cfd9a44 100644 (file)
--- a/include/llvm/ADT/GraphTraits.h
+++ b/include/llvm/ADT/GraphTraits.h
@@ -2,8 +2,8 @@
 //
 //                     The LLVM Compiler Infrastructure
 //
-// This file was developed by the LLVM research group and is distributed under
-// the University of Illinois Open Source License. See LICENSE.TXT for details.
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
@@ -30,7 +30,7 @@ struct GraphTraits {
   // typedef NodeType          - Type of Node in the graph
   // typedef ChildIteratorType - Type used to iterate over children in graph
 
-  // static NodeType *getEntryNode(GraphType *)
+  // static NodeType *getEntryNode(const GraphType &)
   //    Return the entry node of the graph
 
   // static ChildIteratorType child_begin(NodeType *)
@@ -73,9 +73,29 @@ struct GraphTraits {
 //
 template <class GraphType>
 struct Inverse {
-  GraphType &Graph;
+  const GraphType &Graph;
 
-  inline Inverse(GraphType &G) : Graph(G) {}
+  inline Inverse(const GraphType &G) : Graph(G) {}
+};
+
+// Provide a partial specialization of GraphTraits so that the inverse of an
+// inverse falls back to the original graph.
+template<class T>
+struct GraphTraits<Inverse<Inverse<T> > > {
+  typedef typename GraphTraits<T>::NodeType NodeType;
+  typedef typename GraphTraits<T>::ChildIteratorType ChildIteratorType;
+
+  static NodeType *getEntryNode(Inverse<Inverse<T> > *G) {
+    return GraphTraits<T>::getEntryNode(G->Graph.Graph);
+  }
+
+  static ChildIteratorType child_begin(NodeType* N) {
+    return GraphTraits<T>::child_begin(N);
+  }
+
+  static ChildIteratorType child_end(NodeType* N) {
+    return GraphTraits<T>::child_end(N);
+  }
 };
 
 } // End llvm namespace