1 /*=============================================================================
2 Copyright (c) 2001-2003 Joel de Guzman
3 http://spirit.sourceforge.net/
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_XPRESSIVE_SPIRIT_RANGE_RUN_IPP
10 #define BOOST_XPRESSIVE_SPIRIT_RANGE_RUN_IPP
12 ///////////////////////////////////////////////////////////////////////////////
13 #include <algorithm> // for std::lower_bound
14 #include <boost/limits.hpp>
15 #include <boost/assert.hpp>
16 #include <boost/xpressive/detail/utility/chset/range_run.hpp>
18 ///////////////////////////////////////////////////////////////////////////////
19 namespace boost { namespace xpressive { namespace detail
22 ///////////////////////////////////////////////////////////////////////
24 // range class implementation
26 ///////////////////////////////////////////////////////////////////////
27 template<typename Char>
28 inline range<Char>::range(Char first, Char last)
34 //////////////////////////////////
35 template<typename Char>
36 inline bool range<Char>::is_valid() const
38 return this->first_ <= this->last_;
41 //////////////////////////////////
42 template<typename Char>
43 inline bool range<Char>::includes(range<Char> const &r) const
45 return (this->first_ <= r.first_) && (this->last_ >= r.last_);
48 //////////////////////////////////
49 template<typename Char>
50 inline bool range<Char>::includes(Char v) const
52 return (this->first_ <= v) && (this->last_ >= v);
55 //////////////////////////////////
56 template<typename Char>
57 inline bool range<Char>::overlaps(range<Char> const &r) const
59 Char decr_first = (std::min)(this->first_, Char(this->first_-1));
60 Char incr_last = (std::max)(this->last_, Char(this->last_+1));
62 return (decr_first <= r.last_) && (incr_last >= r.first_);
65 //////////////////////////////////
66 template<typename Char>
67 inline void range<Char>::merge(range<Char> const &r)
69 this->first_ = (std::min)(this->first_, r.first_);
70 this->last_ = (std::max)(this->last_, r.last_);
73 ///////////////////////////////////////////////////////////////////////
75 // range_run class implementation
77 ///////////////////////////////////////////////////////////////////////
78 template<typename Char>
79 inline bool range_run<Char>::empty() const
81 return this->run_.empty();
84 template<typename Char>
85 inline bool range_run<Char>::test(Char v) const
87 if(this->run_.empty())
92 const_iterator iter = std::lower_bound(
96 , range_compare<Char>()
99 return (iter != this->run_.end() && iter->includes(v))
100 || (iter != this->run_.begin() && (--iter)->includes(v));
103 template<typename Char>
104 template<typename Traits>
105 inline bool range_run<Char>::test(Char v, Traits const &tr) const
107 const_iterator begin = this->run_.begin();
108 const_iterator end = this->run_.end();
110 for(; begin != end; ++begin)
112 if(tr.in_range_nocase(begin->first_, begin->last_, v))
120 //////////////////////////////////
121 template<typename Char>
122 inline void range_run<Char>::swap(range_run<Char> &rr)
124 this->run_.swap(rr.run_);
127 //////////////////////////////////
128 template<typename Char>
129 void range_run<Char>::merge(iterator iter, range<Char> const &r)
131 BOOST_ASSERT(iter != this->run_.end());
135 while(++i != this->run_.end() && iter->overlaps(*i))
140 this->run_.erase(++iter, i);
143 //////////////////////////////////
144 template<typename Char>
145 void range_run<Char>::set(range<Char> const &r)
147 BOOST_ASSERT(r.is_valid());
148 if(!this->run_.empty())
150 iterator iter = std::lower_bound(this->run_.begin(), this->run_.end(), r, range_compare<Char>());
152 if((iter != this->run_.end() && iter->includes(r)) ||
153 (iter != this->run_.begin() && (iter - 1)->includes(r)))
157 else if(iter != this->run_.begin() && (iter - 1)->overlaps(r))
159 this->merge(--iter, r);
161 else if(iter != this->run_.end() && iter->overlaps(r))
163 this->merge(iter, r);
167 this->run_.insert(iter, r);
172 this->run_.push_back(r);
176 //////////////////////////////////
177 template<typename Char>
178 void range_run<Char>::clear(range<Char> const &r)
180 BOOST_ASSERT(r.is_valid());
181 if(!this->run_.empty())
183 iterator iter = std::lower_bound(this->run_.begin(), this->run_.end(), r, range_compare<Char>());
186 if((iter != this->run_.begin()) &&
187 (left_iter = (iter - 1))->includes(r.first_))
189 if(left_iter->last_ > r.last_)
191 Char save_last = left_iter->last_;
192 left_iter->last_ = r.first_-1;
193 this->run_.insert(iter, range<Char>(r.last_+1, save_last));
198 left_iter->last_ = r.first_-1;
203 for(; i != this->run_.end() && r.includes(*i); ++i) {}
204 if(i != this->run_.end() && i->includes(r.last_))
206 i->first_ = r.last_+1;
208 this->run_.erase(iter, i);
212 //////////////////////////////////
213 template<typename Char>
214 inline void range_run<Char>::clear()
219 //////////////////////////////////
220 template<typename Char>
221 inline typename range_run<Char>::const_iterator range_run<Char>::begin() const
223 return this->run_.begin();
226 //////////////////////////////////
227 template<typename Char>
228 inline typename range_run<Char>::const_iterator range_run<Char>::end() const
230 return this->run_.end();
233 }}} // namespace boost::xpressive::detail