1 /*=============================================================================
2 Copyright (c) 2001-2011 Joel de Guzman
4 Distributed under the Boost Software License, Version 1.0. (See accompanying
5 file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6 ==============================================================================*/
7 #if !defined(BOOST_SPIRIT_RANGE_RUN_MAY_16_2006_0807_PM)
8 #define BOOST_SPIRIT_RANGE_RUN_MAY_16_2006_0807_PM
14 #include <boost/spirit/home/support/char_set/range_functions.hpp>
15 #include <boost/assert.hpp>
18 namespace boost { namespace spirit { namespace support { namespace detail
20 template <typename Run, typename Iterator, typename Range>
22 try_merge(Run& run, Iterator iter, Range const& range)
24 // if *iter intersects with, or is adjacent to, 'range'...
25 if (can_merge(*iter, range))
27 // merge range and *iter
30 // collapse all subsequent ranges that can merge with *iter:
32 // 1. skip subsequent ranges completely included in *iter
33 while (i != run.end() && i->last <= iter->last)
35 // 2. collapse next range if adjacent or overlapping with *iter
36 if (i != run.end() && i->first-1 <= iter->last)
42 // erase all ranges that were collapsed
49 template <typename Char>
51 range_run<Char>::test(Char val) const
56 // search the ranges for one that potentially includes val
57 typename storage_type::const_iterator iter =
59 run.begin(), run.end(), val,
60 range_compare<range_type>()
63 // return true if *(iter-1) includes val
64 return iter != run.begin() && includes(*(--iter), val);
67 template <typename Char>
69 range_run<Char>::swap(range_run& other)
74 template <typename Char>
76 range_run<Char>::set(range_type const& range)
78 BOOST_ASSERT(is_valid(range));
81 // the vector is empty, insert 'range'
86 // search the ranges for one that potentially includes 'range'
87 typename storage_type::iterator iter =
89 run.begin(), run.end(), range,
90 range_compare<range_type>()
93 if (iter != run.begin())
95 // if *(iter-1) includes 'range', return early
96 if (includes(*(iter-1), range))
101 // if *(iter-1) can merge with 'range', merge them and return
102 if (try_merge(run, iter-1, range))
108 // if *iter can merge with with 'range', merge them
109 if (iter == run.end() || !try_merge(run, iter, range))
111 // no overlap, insert 'range'
112 run.insert(iter, range);
116 template <typename Char>
118 range_run<Char>::clear(range_type const& range)
120 BOOST_ASSERT(is_valid(range));
123 // search the ranges for one that potentially includes 'range'
124 typename storage_type::iterator iter =
126 run.begin(), run.end(), range,
127 range_compare<range_type>()
130 // 'range' starts with or after another range:
131 if (iter != run.begin())
133 typename storage_type::iterator const left_iter = iter-1;
135 // 'range' starts after '*left_iter':
136 if (left_iter->first < range.first)
138 // if 'range' is completely included inside '*left_iter':
139 // need to break it apart into two ranges (punch a hole),
140 if (left_iter->last > range.last)
142 Char save_last = left_iter->last;
143 left_iter->last = range.first-1;
144 run.insert(iter, range_type(range.last+1, save_last));
147 // if 'range' contains 'left_iter->last':
148 // truncate '*left_iter' (clip its right)
149 else if (left_iter->last >= range.first)
151 left_iter->last = range.first-1;
155 // 'range' has the same left bound as '*left_iter': it
156 // must be removed or truncated by the code below
163 // remove or truncate subsequent ranges that overlap with 'range':
164 typename storage_type::iterator i = iter;
165 // 1. skip subsequent ranges completely included in 'range'
166 while (i != run.end() && i->last <= range.last)
168 // 2. clip left of next range if overlapping with 'range'
169 if (i != run.end() && i->first <= range.last)
170 i->first = range.last+1;
172 // erase all ranges that 'range' contained
177 template <typename Char>
179 range_run<Char>::clear()