1/*=============================================================================
2 Copyright (c) 2001-2003 Joel de Guzman
3 http://spirit.sourceforge.net/
4
5 Use, modification and distribution is subject to the Boost Software
6 License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
7 http://www.boost.org/LICENSE_1_0.txt)
8=============================================================================*/
9#ifndef BOOST_SPIRIT_RANGE_RUN_IPP
10#define BOOST_SPIRIT_RANGE_RUN_IPP
11
12///////////////////////////////////////////////////////////////////////////////
13#include <algorithm> // for std::lower_bound
14#include <boost/spirit/home/classic/core/assert.hpp> // for BOOST_SPIRIT_ASSERT
15#include <boost/spirit/home/classic/utility/impl/chset/range_run.hpp>
16#include <boost/spirit/home/classic/debug.hpp>
17#include <boost/limits.hpp>
18
19///////////////////////////////////////////////////////////////////////////////
20namespace boost { namespace spirit {
21
22BOOST_SPIRIT_CLASSIC_NAMESPACE_BEGIN
23
24 namespace utility { namespace impl {
25
26 ///////////////////////////////////////////////////////////////////////
27 //
28 // range class implementation
29 //
30 ///////////////////////////////////////////////////////////////////////
31 template <typename CharT>
32 inline range<CharT>::range(CharT first_, CharT last_)
33 : first(first_), last(last_) {}
34
35 //////////////////////////////////
36 template <typename CharT>
37 inline bool
38 range<CharT>::is_valid() const
39 { return first <= last; }
40
41 //////////////////////////////////
42 template <typename CharT>
43 inline bool
44 range<CharT>::includes(range const& r) const
45 { return (first <= r.first) && (last >= r.last); }
46
47 //////////////////////////////////
48 template <typename CharT>
49 inline bool
50 range<CharT>::includes(CharT v) const
51 { return (first <= v) && (last >= v); }
52
53 //////////////////////////////////
54 template <typename CharT>
55 inline bool
56 range<CharT>::overlaps(range const& r) const
57 {
58 CharT decr_first =
59 first == (std::numeric_limits<CharT>::min)() ? first : first-1;
60 CharT incr_last =
61 last == (std::numeric_limits<CharT>::max)() ? last : last+1;
62
63 return (decr_first <= r.last) && (incr_last >= r.first);
64 }
65
66 //////////////////////////////////
67 template <typename CharT>
68 inline void
69 range<CharT>::merge(range const& r)
70 {
71 first = (std::min)(first, r.first);
72 last = (std::max)(last, r.last);
73 }
74
75 ///////////////////////////////////////////////////////////////////////
76 //
77 // range_run class implementation
78 //
79 ///////////////////////////////////////////////////////////////////////
80 template <typename CharT>
81 inline bool
82 range_run<CharT>::test(CharT v) const
83 {
84 if (!run.empty())
85 {
86 const_iterator iter =
87 std::lower_bound(
88 run.begin(), run.end(), v,
89 range_char_compare<CharT>()
90 );
91
92 if (iter != run.end() && iter->includes(v))
93 return true;
94 if (iter != run.begin())
95 return (--iter)->includes(v);
96 }
97 return false;
98 }
99
100 //////////////////////////////////
101 template <typename CharT>
102 inline void
103 range_run<CharT>::swap(range_run& rr)
104 { run.swap(rr.run); }
105
106 //////////////////////////////////
107 template <typename CharT>
108 void
109 range_run<CharT>::merge(iterator iter, range<CharT> const& r)
110 {
111 iter->merge(r);
112 iterator i = iter + 1;
113
114 while (i != run.end() && iter->overlaps(*i))
115 iter->merge(*i++);
116
117 run.erase(iter+1, i);
118 }
119
120 //////////////////////////////////
121 template <typename CharT>
122 void
123 range_run<CharT>::set(range<CharT> const& r)
124 {
125 BOOST_SPIRIT_ASSERT(r.is_valid());
126 if (!run.empty())
127 {
128 iterator iter =
129 std::lower_bound(
130 run.begin(), run.end(), r,
131 range_compare<CharT>()
132 );
133
134 if ((iter != run.end() && iter->includes(r)) ||
135 ((iter != run.begin()) && (iter - 1)->includes(r)))
136 return;
137
138 if (iter != run.begin() && (iter - 1)->overlaps(r))
139 merge(iter: --iter, r);
140
141 else if (iter != run.end() && iter->overlaps(r))
142 merge(iter, r);
143
144 else
145 run.insert(iter, r);
146 }
147 else
148 {
149 run.push_back(r);
150 }
151 }
152
153 //////////////////////////////////
154 template <typename CharT>
155 void
156 range_run<CharT>::clear(range<CharT> const& r)
157 {
158 BOOST_SPIRIT_ASSERT(r.is_valid());
159 if (!run.empty())
160 {
161 iterator iter =
162 std::lower_bound(
163 run.begin(), run.end(), r,
164 range_compare<CharT>()
165 );
166
167 iterator left_iter;
168
169 if ((iter != run.begin()) &&
170 (left_iter = (iter - 1))->includes(r.first))
171 {
172 if (left_iter->last > r.last)
173 {
174 CharT save_last = left_iter->last;
175 left_iter->last = r.first-1;
176 run.insert(iter, range<CharT>(r.last+1, save_last));
177 return;
178 }
179 else
180 {
181 left_iter->last = r.first-1;
182 }
183 }
184
185 iterator i = iter;
186 while (i != run.end() && r.includes(*i))
187 i++;
188 if (i != run.end() && i->includes(r.last))
189 i->first = r.last+1;
190 run.erase(iter, i);
191 }
192 }
193
194 //////////////////////////////////
195 template <typename CharT>
196 inline void
197 range_run<CharT>::clear()
198 { run.clear(); }
199
200 //////////////////////////////////
201 template <typename CharT>
202 inline typename range_run<CharT>::const_iterator
203 range_run<CharT>::begin() const
204 { return run.begin(); }
205
206 //////////////////////////////////
207 template <typename CharT>
208 inline typename range_run<CharT>::const_iterator
209 range_run<CharT>::end() const
210 { return run.end(); }
211
212 }} // namespace utility::impl
213
214BOOST_SPIRIT_CLASSIC_NAMESPACE_END
215
216}} // namespace boost::spirit
217
218#endif
219

source code of boost/libs/spirit/include/boost/spirit/home/classic/utility/impl/chset/range_run.ipp