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>();