]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | /////////////////////////////////////////////////////////////////////////////// | |
20 | namespace boost { namespace spirit { | |
21 | ||
22 | BOOST_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, 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 | ||
214 | BOOST_SPIRIT_CLASSIC_NAMESPACE_END | |
215 | ||
216 | }} // namespace boost::spirit | |
217 | ||
218 | #endif |