Changeset 2357 for trunk/yat/utility/Segment.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/Segment.h (modified) (9 diffs)

trunk/yat/utility/Segment.h

@@ -23 +23 @@
 */
 
+#include "yat_assert.h"
+
 #include <algorithm>
 #include <functional>
@@ -33 +35 @@
      \brief a class for a Segment or Interval
 
-     A class for a Segment [begin, end). 
+     A Segment is defined by its \a begin and \a end. The end is not
+     included in the Segment, i.e., you could write the Segment as
+     [begin, end). Type T must be comparable, optionally with a
+     comparator Compare, which should implement <a
+     href="http://www.sgi.com/tech/stl/StrictWeakOrdering.html">
+     Strict Weak Ordering.</a>.    
 
      \since new in yat 0.7
@@ -89 +96 @@
 
   /**
-     \return true if all elements in \a lhs is less than all elements
-     in \a rhs, i.e., returns false if rhs.begin() is less than
-     lhs.end()
+     This function takes two Segment and compare them with comparator
+     Compare. If all elements in \a lhs is less than all elements in
+     \a rhs, \c true is returned. In other words, \c false is returned
+     if \a rhs.begin() is less than \a lhs.end().
+
+     The exception is if both \a lhs and \a rhs are empty Segment
+     (i.e. begin equals end) and their begins and ends are equal, in
+     which case \c false is returned. This exception implies that
+     compare(x,x) always returns false.
 
      \relates Segment
@@ -101 +114 @@
   {
     Compare c;
+    // begin <= end
+    YAT_ASSERT(!c(lhs.end(), lhs.begin()));
+    YAT_ASSERT(!c(rhs.end(), rhs.begin()));
+    // take care of case when both sides are zero segments
+    if (!c(lhs.begin(), lhs.end()) && !c(rhs.begin(), rhs.end())) {
+      return c(lhs.begin(), rhs.begin());
+    }
+
     return ! c(rhs.begin(), lhs.end());
   }
 
   /**
-     \return -1 if all elements in lhs is less than all elements in
-     rhs; +1 if all elements in rhs is less than all elements in lhs;
-     and 0 if lhs and rhs overlap.
+     \return -1 if compare(lhs, rhs) is \c true, +1 if compare(rhs,
+     lhs) is \c true, and 0 otherwise
 
      \relates Segment
+
+     \see compare(const Segment<T, Compare>&, const Segment<T, Compare>&)
 
      \since new in yat 0.7
@@ -115 +137 @@
   template<typename T, class Compare>
   int compare_3way(const Segment<T, Compare>& lhs, 
-                    const Segment<T, Compare>& rhs)
+                   const Segment<T, Compare>& rhs)
   {
     if (compare(lhs, rhs))
@@ -125 +147 @@
 
   /**
-     \return -1 if lhs is less than all elements in rhs; +1 if all
-     elements in rhs is less than lhs; and 0 if lhs and rhs overlap
+     \return -1 if \a element is less than all elements in \a segment,
+     0 if \a element overlaps with \a segment, and 1 otherwise.
 
      \relates Segment
@@ -133 +155 @@
    */
   template<typename T, class Compare>
-  int compare_3way(const T& lhs, 
-                   const Segment<T, Compare>& rhs)
+  int compare_3way(const T& element, 
+                   const Segment<T, Compare>& segment)
   {
     Compare comp;
-    if (comp(lhs, rhs.begin()))
+    if (comp(element, segment.begin()))
       return -1;
-    if (comp(lhs, rhs.end()))
+    if (comp(element, segment.end()))
       return 0;
     return 1;
@@ -145 +167 @@
 
   /**
-     \return intersection of \a a and \a b. If \a a and \b do not
+     \return intersection of \a a and \a b. If \a a and \a b do not
      overlap an empty Section is returned (begin==end), but the exact
      value of begin is undefined.
@@ -161 +183 @@
 
     result.begin() = std::max(a.begin(), b.begin(), comp);
+    // the first max is needed in case a and b don't overlap
     result.end() = std::max(result.begin(), 
                             std::min(a.end(), b.end(), comp),