1/*=============================================================================
2 Copyright (c) 2001-2011 Joel de Guzman
3
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
9
10#if defined(_MSC_VER)
11#pragma once
12#endif
13
14#include <boost/spirit/home/support/char_set/range_functions.hpp>
15#include <boost/assert.hpp>
16#include <algorithm>
17
18namespace boost { namespace spirit { namespace support { namespace detail
19{
20 template <typename Run, typename Iterator, typename Range>
21 inline bool
22 try_merge(Run& run, Iterator iter, Range const& range)
23 {
24 // if *iter intersects with, or is adjacent to, 'range'...
25 if (can_merge(*iter, range))
26 {
27 // merge range and *iter
28 merge(*iter, range);
29
30 // collapse all subsequent ranges that can merge with *iter:
31 Iterator i = iter+1;
32 // 1. skip subsequent ranges completely included in *iter
33 while (i != run.end() && i->last <= iter->last)
34 ++i;
35 // 2. collapse next range if adjacent or overlapping with *iter
36 if (i != run.end() && i->first-1 <= iter->last)
37 {
38 iter->last = i->last;
39 ++i;
40 }
41
42 // erase all ranges that were collapsed
43 run.erase(iter+1, i);
44 return true;
45 }
46 return false;
47 }
48
49 template <typename Char>
50 inline bool
51 range_run<Char>::test(Char val) const
52 {
53 if (run.empty())
54 return false;
55
56 // search the ranges for one that potentially includes val
57 typename storage_type::const_iterator iter =
58 std::upper_bound(
59 run.begin(), run.end(), val,
60 range_compare<range_type>()
61 );
62
63 // return true if *(iter-1) includes val
64 return iter != run.begin() && includes(*(--iter), val);
65 }
66
67 template <typename Char>
68 inline void
69 range_run<Char>::swap(range_run& other)
70 {
71 run.swap(other.run);
72 }
73
74 template <typename Char>
75 void
76 range_run<Char>::set(range_type const& range)
77 {
78 BOOST_ASSERT(is_valid(range));
79 if (run.empty())
80 {
81 // the vector is empty, insert 'range'
82 run.push_back(range);
83 return;
84 }
85
86 // search the ranges for one that potentially includes 'range'
87 typename storage_type::iterator iter =
88 std::upper_bound(
89 run.begin(), run.end(), range,
90 range_compare<range_type>()
91 );
92
93 if (iter != run.begin())
94 {
95 // if *(iter-1) includes 'range', return early
96 if (includes(*(iter-1), range))
97 {
98 return;
99 }
100
101 // if *(iter-1) can merge with 'range', merge them and return
102 if (try_merge(run, iter-1, range))
103 {
104 return;
105 }
106 }
107
108 // if *iter can merge with with 'range', merge them
109 if (iter == run.end() || !try_merge(run, iter, range))
110 {
111 // no overlap, insert 'range'
112 run.insert(iter, range);
113 }
114 }
115
116 template <typename Char>
117 void
118 range_run<Char>::clear(range_type const& range)
119 {
120 BOOST_ASSERT(is_valid(range));
121 if (!run.empty())
122 {
123 // search the ranges for one that potentially includes 'range'
124 typename storage_type::iterator iter =
125 std::upper_bound(
126 run.begin(), run.end(), range,
127 range_compare<range_type>()
128 );
129
130 // 'range' starts with or after another range:
131 if (iter != run.begin())
132 {
133 typename storage_type::iterator const left_iter = iter-1;
134
135 // 'range' starts after '*left_iter':
136 if (left_iter->first < range.first)
137 {
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)
141 {
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));
145 return;
146 }
147 // if 'range' contains 'left_iter->last':
148 // truncate '*left_iter' (clip its right)
149 else if (left_iter->last >= range.first)
150 {
151 left_iter->last = range.first-1;
152 }
153 }
154
155 // 'range' has the same left bound as '*left_iter': it
156 // must be removed or truncated by the code below
157 else
158 {
159 iter = left_iter;
160 }
161 }
162
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)
167 ++i;
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;
171
172 // erase all ranges that 'range' contained
173 run.erase(iter, i);
174 }
175 }
176
177 template <typename Char>
178 inline void
179 range_run<Char>::clear()
180 {
181 run.clear();
182 }
183}}}}
184
185#endif
186

source code of boost/libs/spirit/include/boost/spirit/home/support/char_set/range_run_impl.hpp