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

Timestamp:

Dec 1, 2010, 10:08:29 PM (12 years ago)

Author:

Peter

Message:

use compare(Segment, Segment) as comparator in SegmentSet? which allows simplifications in SegmentSet? code. Add some tests and docs.

File:

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

trunk/yat/utility/SegmentSet.h

@@ -51 +51 @@
     /// value_type same as key_type
     typedef key_type value_type;
+
     /// key_compare
-    struct key_compare
+    class key_compare : public std::binary_function<key_type, key_type, bool>
     {
+    public:
       /// return true if lhs.begin() < rhs.begin()
       bool operator()(const key_type& lhs, const key_type& rhs) const
-      { return Compare()(lhs.begin(),rhs.begin()); }
+      { return compare(lhs,rhs); }
     };
+
     /// value_compare is same as key_compare
     typedef key_compare value_compare;
@@ -81 +84 @@
 
     /**
-       \brief default constructor
+       \brief creates a set with no segments
      */
     SegmentSet(void) {}
 
     /**
+       \return const iterator to first Segment
+     */
+    const_iterator begin(void) const { return set_.begin(); }
+
+    /**
        \return iterator to first Segment
      */
-    const_iterator begin(void) const { return set_.begin(); }
-
-    /**
-       \return iterator to first Segment
-     */
     iterator begin(void) { return set_.begin(); }
 
     /**
-       \brief erases all the segments
+       \brief erases all segments
      */
     void clear(void) { set_.clear(); }
 
     /**
-       \return 1 if there is a set that overlaps with \a vt
-     */
-    size_t count(const typename value_type::value_type& vt) const;
-
-    /**
-       \return \c true if SegmentSet is empty
+       \return 1 if there is a set that overlaps with \a element
+     */
+    size_type count(const T& element) const;
+
+    /**
+       \return \c true 
     */
     bool empty(void) const { return set_.empty(); }
@@ -124 +127 @@
        vt. If no Segment contains \a vt, end() is returned.
      */
-    const_iterator find(const typename value_type::value_type& vt) const;
+    const_iterator find(const T& vt) const;
 
     /**
@@ -141 +144 @@
     /**
        insert \a segment into set. If there is no gap between \a
-       segment and neighboring segments the segments are merged. Note
-       that this might also happen for non-overlapping segments, e.g.,
-       [0,1) and [1,2) would be merged into [0,2).
+       segment and neighboring segments the segments are merged.
      */
     const_iterator insert_merge(const value_type& segment);
+
+    /**
+       \return Comparison functor to compare to segments
+     */
+    key_compare key_comp(void) const { return key_compare(Compare()); }
 
     /**
@@ -151 +157 @@
        \a segment or is greater than \a segment.
      */
-    const_iterator lower_bound(const value_type& segment) const;
+    const_iterator lower_bound(const key_type& segment) const;
 
     /**
        \return number of segments in set
      */
-    size_t size(void) const { return set_.size(); }
+    size_type size(void) const { return set_.size(); }
 
     /**
@@ -162 +168 @@
        \a segment.
      */
-    const_iterator upper_bound(const value_type& segment) const;
+    const_iterator upper_bound(const key_type& segment) const;
+
+    /**
+       \return Comparison functor to compare to segments
+     */
+    value_compare value_comp(void) const { return key_comp(); }
 
   private:
@@ -172 +183 @@
        overlap with \a segment.
      */
-    std::pair<iterator, iterator> overlap_range(const value_type& segment) 
+    // FIXME: can this be removed?
+    std::pair<iterator, iterator> overlap_range(const key_type& segment) 
     {
       iterator first = set_.lower_bound(segment);
@@ -187 +199 @@
     }
 
-
-    /**
-       pair.first first (smallest) segment that overlaps with \a
-       segment and pair.second first (smallest) segment that does not
-       overlap with \a segment.
-     */
-    std::pair<const_iterator, const_iterator> 
-    overlap_range(const value_type& segment) const
-    {
-      const_iterator first = set_.lower_bound(segment);
-      if (first!=begin()) {
-        --first;
-        if (compare(*first, segment))
-          ++first;
-      }
-      const_iterator last = first;
-      while (last!=end() && !compare(segment, *last))
-        ++last;
-      return std::make_pair(first, last);
-    }
-
     // using compiler generated copying
     //SegmentSet(const SegmentSet&);
@@ -214 +205 @@
 
   template<typename T, class Compare>
-  size_t 
-  SegmentSet<T, Compare>::count(const typename value_type::value_type& vt) const
+  typename SegmentSet<T, Compare>::size_type 
+  SegmentSet<T, Compare>::count(const T& vt) const
   {
     if (find(vt)==end())
@@ -225 +216 @@
   template<typename T, class Compare>
   typename SegmentSet<T, Compare>::const_iterator 
-  SegmentSet<T, Compare>::find(const typename value_type::value_type& vt) const
+  SegmentSet<T, Compare>::find(const T& vt) const
   {
     Segment<T, Compare> segment(vt, vt);
-    std::pair<const_iterator, const_iterator> p = overlap_range(segment);
-    if (p.first == end())
+    const_iterator iter = lower_bound(segment);
+    Compare comp;
+    if (iter==end() || comp(vt, iter->begin()))
       return end();
-    Compare comp;
-    if (comp(vt, p.first->begin()))
-        return end();
-    return p.first;
+    return iter;
   }
 
@@ -242 +231 @@
   SegmentSet<T, Compare>::insert(const value_type& segment)
   {
-    std::pair<iterator, iterator> p = overlap_range(segment);
-    std::pair<typename SegmentSet<T, Compare>::iterator, bool> result;
-    if (p.first==p.second) {
-      result.first = set_.insert(p.first, segment);
-      result.second = true;
-      return result;
-    }
-    result.first = p.first;
-    result.second = false;
-    return result;
+    return set_.insert(segment);
   }
 
@@ -260 +240 @@
   {
     std::pair<iterator, iterator> p = overlap_range(segment);
-    if (p.first==p.second) {
+    if (p.first==p.second) { // no overlap between set and segment
       return set_.insert(p.first, segment);
     }
+    /*
+      p.first           last         p.second
+      --->    --->      --->         --->
+
+       ----------------------->
+           segment
+     */
     Compare comp;
-    if (comp(segment.begin(), p.first->begin()))
-      const_cast<value_type&>(*p.first).begin() = segment.begin();
-
-    --p.second;
-    const_cast<value_type&>(*p.first).end() = 
-      std::max(p.second->end(), segment.end(), comp);
-    ++p.second;
-    iterator begin(p.first);
-    ++begin;
-    set_.erase(begin, p.second); 
-    return p.first;
+    iterator last=p.second;
+    YAT_ASSERT(last==end() || compare(segment, *last));
+    YAT_ASSERT(last!=begin()); // last!=p.first
+    --last;
+    YAT_ASSERT(compare_3way(segment, *last)==0);
+
+    Segment<T, Compare> segment2(std::min(p.first->begin(),segment.begin(),comp),
+                                 std::max(last->end(),segment.end(),comp));
+    set_.erase(p.first, p.second); 
+    // FIXME: use a better hint than end()
+    return set_.insert(end(), segment2);
   }
 
@@ -280 +267 @@
   template<typename T, class Compare>
   typename SegmentSet<T, Compare>::const_iterator
-  SegmentSet<T, Compare>::lower_bound(const value_type& segment) const
+  SegmentSet<T, Compare>::lower_bound(const key_type& segment) const
   {
     const_iterator result = set_.lower_bound(segment);
-    if (result!=begin()) {
-      --result;
-      if (compare(*result, segment))
-        ++result;
-    }
+    // result is larger or overlapping with segment (i.e.! result<segment)
+    YAT_ASSERT(result==end() || !compare(*result,segment));
     return result;
   }
@@ -294 +278 @@
   template<typename T, class Compare>
   typename SegmentSet<T, Compare>::const_iterator
-  SegmentSet<T, Compare>::upper_bound(const value_type& segment) const
-  {
-    const_iterator result = set_.lower_bound(segment);
-    while (result!=end() && !compare(segment, *result))
-      ++result;
+  SegmentSet<T, Compare>::upper_bound(const key_type& segment) const
+  {
+    const_iterator result = set_.upper_bound(segment);
+    // result is larger than segment
+    YAT_ASSERT(result==end() || compare(segment, *result));
     return result;
   }