Changeset 3344 for trunk/yat/utility/SegmentSet.h

Timestamp:

Nov 6, 2014, 1:09:32 PM (8 years ago)

Author:

Peter

Message:

new function SegmentSet::insert_merge with hint. refs #818

File:

• trunk/yat/utility/SegmentSet.h (modified) (2 diffs)

trunk/yat/utility/SegmentSet.h

@@ -66 +66 @@
       std::pair<typename me::iterator, typename me::iterator> p =
         this->overlap_range(segment);
+      return insert_merge(p, segment);
+    }
+
+    /**
+       \brief insert with a hint
+
+       Similar to insert_merge(1) but \a hint help to find where to
+       insert \a segment. For the \a hint to be useful, \a segment
+       should not be greater than element hint points to and not
+       smaller than element --hint points to.
+
+       \since New in yat 0.13
+     */
+    typename me::iterator insert_merge(typename me::iterator hint,
+                                       const typename me::value_type& segment)
+    {
+      std::pair<typename me::iterator, typename me::iterator> p(hint, hint);
+      if (this->container_.empty())
+        return insert_merge(p, segment);
+
+      //.If hint points to an element that is less than segment, hint
+      //is no good and we ignore the hint.
+      if (hint!=this->end() && compare(*hint, segment))
+        return insert_merge(segment);
+
+      if (p.first!=this->begin()) {
+        --p.first;
+        // If --hint point to an element greater than segment, hint is
+        // no good.
+        if (compare(segment, *p.first))
+          return insert_merge(segment);
+        // find first element that is smaller than segment
+        while (p.first!=this->begin() && !compare(*p.first, segment))
+          --p.first;
+        YAT_ASSERT(p.first==this->begin() || compare(*p.first, segment));
+        YAT_ASSERT(p.first!=this->end());
+        if (compare(*p.first, segment))
+          ++p.first;
+      }
+
+      // find first element greater than segment
+      while (p.second!=this->end() && !compare(segment, *p.second))
+        ++p.second;
+
+      return insert_merge(p, segment);
+    }
+
+  private:
+    // used by public functions insert_merge.
+    //
+    // p.first points to the first segment that overlaps with \a segment or
+    // is greater than segment.
+    // p.second points to the first segment that is greater than \a segment
+    typename me::const_iterator
+    insert_merge(const std::pair<typename me::iterator,
+                                 typename me::iterator>& p,
+                 const typename me::value_type& segment)
+    {
+      YAT_ASSERT(p.first==this->end() || !compare(*p.first, segment));
+      YAT_ASSERT(p.second==this->end() || compare(segment, *p.second));
       if (p.first==p.second) { // no overlap between set and segment
         return this->container_.insert(p.first, segment);
@@ -91 +151 @@
     }
 
-  private:
     // using compiler generated copying
     //SegmentSet(const SegmentSet&);