[Boost-commit] svn:boost r53759 - in trunk: boost/spirit/home/qi/char/detail libs/spirit/test/qi

Subject: [Boost-commit] svn:boost r53759 - in trunk: boost/spirit/home/qi/char/detail libs/spirit/test/qi
From: frabar666_at_[hidden]
Date: 2009-06-08 16:18:45

Author: fbarel
Date: 2009-06-08 16:18:44 EDT (Mon, 08 Jun 2009)
New Revision: 53759
URL: http://svn.boost.org/trac/boost/changeset/53759

Log:
Spirit: fix two range_run issues (range truncation on set, lower bound underflow on clear)
Text files modified: 
   trunk/boost/spirit/home/qi/char/detail/range_run_impl.hpp |    77 +++++++++++++++++++++------------------ 
   trunk/libs/spirit/test/qi/range_run.cpp                   |    22 +++++++++++                             
   2 files changed, 64 insertions(+), 35 deletions(-)

Modified: trunk/boost/spirit/home/qi/char/detail/range_run_impl.hpp
==============================================================================
--- trunk/boost/spirit/home/qi/char/detail/range_run_impl.hpp	(original)
+++ trunk/boost/spirit/home/qi/char/detail/range_run_impl.hpp	2009-06-08 16:18:44 EDT (Mon, 08 Jun 2009)
@@ -31,16 +31,18 @@
             // merge range and *iter
             merge(*iter, range);
 
-            // collapse all subsequent ranges that can merge with *iter
-            Iterator i;
-            value_type last =
-                iter->last == integer_traits::const_max
-                ? iter->last : iter->last+1;
-
-            for (i = iter+1; i != run.end() && last >= i->first; ++i)
+            // collapse all subsequent ranges that can merge with *iter:
+            Iterator i = iter+1;
+            // 1. skip subsequent ranges completely included in *iter
+            while (i != run.end() && i->last <= iter->last)
+                ++i;
+            // 2. collapse next range if adjacent or overlapping with *iter
+            if (i != run.end() && i->first-1 <= iter->last)
             {
                 iter->last = i->last;
+                ++i;
             }
+
             // erase all ranges that were collapsed
             run.erase(iter+1, i);
             return true;
@@ -129,44 +131,49 @@
                     range_compare<range_type>()
                 );
 
-            typename storage_type::iterator left_iter;
-
-            // if *(iter-1) includes the 'range.first',
-            if ((iter != run.begin()) &&
-                includes(*(left_iter = (iter-1)), range.first))
+            // 'range' starts with or after another range:
+            if (iter != run.begin())
             {
-                // if the 'range' is in the middle,
-                if (left_iter->last > range.last)
+                typename storage_type::iterator const left_iter = iter-1;
+
+                // 'range' starts after '*left_iter':
+                if (left_iter->first < range.first)
                 {
-                    // break it apart into two ranges (punch a hole)
-                    Char save_last = left_iter->last;
-                    left_iter->last = range.first-1;
-                    run.insert(iter, range_type(range.last+1, save_last));
-                    return;
+                    // if 'range' is completely included inside '*left_iter':
+                    // need to break it apart into two ranges (punch a hole),
+                    if (left_iter->last > range.last)
+                    {
+                        Char save_last = left_iter->last;
+                        left_iter->last = range.first-1;
+                        run.insert(iter, range_type(range.last+1, save_last));
+                        return;
+                    }
+                    // if 'range' contains 'left_iter->last':
+                    // truncate '*left_iter' (clip its right)
+                    else if (left_iter->last >= range.first)
+                    {
+                        left_iter->last = range.first-1;
+                    }
                 }
-                else // if it is not in the middle,
+
+                // 'range' has the same left bound as '*left_iter': it
+                // must be removed or truncated by the code below
+                else
                 {
-                    // truncate it (clip its right)
-                    left_iter->last = range.first-1;
+                    iter = left_iter;
                 }
             }
 
-            // position i to the first range that 'range'
-            // does not intersect with
+            // remove or truncate subsequent ranges that overlap with 'range':
             typename storage_type::iterator i = iter;
-            while (i != run.end() && includes(range, *i))
-            {
-                i++;
-            }
-
-            // if *i includes 'range.last', truncate it (clip its left)
-            if (i != run.end() && includes(*i, range.last))
-            {
+            // 1. skip subsequent ranges completely included in 'range'
+            while (i != run.end() && i->last <= range.last)
+                ++i;
+            // 2. clip left of next range if overlapping with 'range'
+            if (i != run.end() && i->first <= range.last)
                 i->first = range.last+1;
-            }
 
-            // cleanup... erase all subsequent ranges that the
-            // 'range' includes
+            // erase all ranges that 'range' contained
             run.erase(iter, i);
         }
     }

Modified: trunk/libs/spirit/test/qi/range_run.cpp
==============================================================================
--- trunk/libs/spirit/test/qi/range_run.cpp	(original)
+++ trunk/libs/spirit/test/qi/range_run.cpp	2009-06-08 16:18:44 EDT (Mon, 08 Jun 2009)
@@ -161,6 +161,28 @@
         }
     }
     {
+        range_run<char> rr;
+        rr.set(range<char>('c', 'e'));
+        rr.set(range<char>('g', 'i'));
+        rr.set(range<char>('d', 'k'));
+        for (char c = 'a'; c <= 'm'; ++c)
+        {
+            BOOST_TEST((c >= 'c' && c <= 'k') == rr.test(c));
+        }
+    }
+    {
+        typedef boost::integer_traits<char> traits;
+        char const const_min = traits::const_min;
+        range_run<char> rr;
+        rr.set(range<char>(const_min, const_min+16));
+        rr.clear(range<char>(const_min, const_min+8));
+        BOOST_TEST(!rr.test(const_min));
+        BOOST_TEST(!rr.test(const_min+8));
+        BOOST_TEST(rr.test(const_min+9));
+        BOOST_TEST(rr.test(const_min+16));
+        BOOST_TEST(!rr.test(const_min+17));
+    }
+    {
         acid_test<char>();
         acid_test<signed char>();
         acid_test<unsigned char>();