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

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

diff --git a/include/llvm/ADT/ImmutableSet.h b/include/llvm/ADT/ImmutableSet.h
index ac06a4072b8fa14cc965099cac9af20ef0b5bde2..70c3caf2a06117aadd75224250de4af3a4901612 100644 (file)
--- a/include/llvm/ADT/ImmutableSet.h
+++ b/include/llvm/ADT/ImmutableSet.h
@@ -27,6 +27,7 @@ namespace llvm {
 //===----------------------------------------------------------------------===//
 
 template <typename ImutInfo> class ImutAVLFactory;
+template <typename ImutInfo> class ImutIntervalAVLFactory;
 template <typename ImutInfo> class ImutAVLTreeInOrderIterator;
 template <typename ImutInfo> class ImutAVLTreeGenericIterator;
 
@@ -39,6 +40,7 @@ public:
 
   typedef ImutAVLFactory<ImutInfo>          Factory;
   friend class ImutAVLFactory<ImutInfo>;
+  friend class ImutIntervalAVLFactory<ImutInfo>;
 
   friend class ImutAVLTreeGenericIterator<ImutInfo>;
   friend class FoldingSet<ImutAVLTree>;
@@ -187,6 +189,8 @@ public:
   unsigned verify() const {
     unsigned HL = getLeft() ? getLeft()->verify() : 0;
     unsigned HR = getRight() ? getRight()->verify() : 0;
+    (void) HL;
+    (void) HR;
 
     assert(getHeight() == ( HL > HR ? HL : HR ) + 1
             && "Height calculation wrong");
@@ -389,7 +393,7 @@ public:
   // These have succinct names so that the balancing code
   // is as terse (and readable) as possible.
   //===--------------------------------------------------===//
-private:
+protected:
 
   bool           isEmpty(TreeTy* T) const { return !T; }
   unsigned Height(TreeTy* T) const { return T ? T->getHeight() : 0; }
@@ -581,25 +585,14 @@ public:
         continue;
       
       // We found a collision.  Perform a comparison of Contents('T')
-      // with Contents('L')+'V'+Contents('R').
+      // with Contents('TNew')
       typename TreeTy::iterator TI = T->begin(), TE = T->end();
       
-      // First compare Contents('L') with the (initial) contents of T.
-      if (!CompareTreeWithSection(TNew->getLeft(), TI, TE))
-        continue;
-      
-      // Now compare the new data element.
-      if (TI == TE || !TI->ElementEqual(TNew->getValue()))
-        continue;
-      
-      ++TI;
-      
-      // Now compare the remainder of 'T' with 'R'.
-      if (!CompareTreeWithSection(TNew->getRight(), TI, TE))
+      if (!CompareTreeWithSection(TNew, TI, TE))
         continue;
       
       if (TI != TE)
-        continue; // Contents('R') did not match suffix of 'T'.
+        continue; // T has more contents than TNew.
       
       // Trees did match!  Return 'T'.
       return T;