utility/chset/range_run.ipp

0001 /*=============================================================================
0002     Copyright (c) 2001-2003 Joel de Guzman
0003     http://spirit.sourceforge.net/
0004
0005     Use, modification and distribution is subject to the Boost Software
0006     License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0007     http://www.boost.org/LICENSE_1_0.txt)
0008 =============================================================================*/
0009 #ifndef BOOST_XPRESSIVE_SPIRIT_RANGE_RUN_IPP
0010 #define BOOST_XPRESSIVE_SPIRIT_RANGE_RUN_IPP
0011
0012 ///////////////////////////////////////////////////////////////////////////////
0013 #include <algorithm> // for std::lower_bound
0014 #include <boost/limits.hpp>
0015 #include <boost/assert.hpp>
0016 #include <boost/xpressive/detail/utility/chset/range_run.hpp>
0017
0018 ///////////////////////////////////////////////////////////////////////////////
0019 namespace boost { namespace xpressive { namespace detail
0020 {
0021
0022 ///////////////////////////////////////////////////////////////////////
0023 //
0024 //  range class implementation
0025 //
0026 ///////////////////////////////////////////////////////////////////////
0027 template<typename Char>
0028 inline range<Char>::range(Char first, Char last)
0029   : first_(first)
0030   , last_(last)
0031 {
0032 }
0033
0034 //////////////////////////////////
0035 template<typename Char>
0036 inline bool range<Char>::is_valid() const
0037 {
0038     return this->first_ <= this->last_;
0039 }
0040
0041 //////////////////////////////////
0042 template<typename Char>
0043 inline bool range<Char>::includes(range<Char> const &r) const
0044 {
0045     return (this->first_ <= r.first_) && (this->last_ >= r.last_);
0046 }
0047
0048 //////////////////////////////////
0049 template<typename Char>
0050 inline bool range<Char>::includes(Char v) const
0051 {
0052     return (this->first_ <= v) && (this->last_ >= v);
0053 }
0054
0055 //////////////////////////////////
0056 template<typename Char>
0057 inline bool range<Char>::overlaps(range<Char> const &r) const
0058 {
0059     Char decr_first = (std::min)(this->first_, Char(this->first_-1));
0060     Char incr_last = (std::max)(this->last_, Char(this->last_+1));
0061
0062     return (decr_first <= r.last_) && (incr_last >= r.first_);
0063 }
0064
0065 //////////////////////////////////
0066 template<typename Char>
0067 inline void range<Char>::merge(range<Char> const &r)
0068 {
0069     this->first_ = (std::min)(this->first_, r.first_);
0070     this->last_ = (std::max)(this->last_, r.last_);
0071 }
0072
0073 ///////////////////////////////////////////////////////////////////////
0074 //
0075 //  range_run class implementation
0076 //
0077 ///////////////////////////////////////////////////////////////////////
0078 template<typename Char>
0079 inline bool range_run<Char>::empty() const
0080 {
0081     return this->run_.empty();
0082 }
0083
0084 template<typename Char>
0085 inline bool range_run<Char>::test(Char v) const
0086 {
0087     if(this->run_.empty())
0088     {
0089         return false;
0090     }
0091
0092     const_iterator iter = std::lower_bound(
0093         this->run_.begin()
0094       , this->run_.end()
0095       , range<Char>(v, v)
0096       , range_compare<Char>()
0097     );
0098
0099     return (iter != this->run_.end() && iter->includes(v))
0100         || (iter != this->run_.begin() && (--iter)->includes(v));
0101 }
0102
0103 template<typename Char>
0104 template<typename Traits>
0105 inline bool range_run<Char>::test(Char v, Traits const &tr) const
0106 {
0107     const_iterator begin = this->run_.begin();
0108     const_iterator end = this->run_.end();
0109
0110     for(; begin != end; ++begin)
0111     {
0112         if(tr.in_range_nocase(begin->first_, begin->last_, v))
0113         {
0114             return true;
0115         }
0116     }
0117     return false;
0118 }
0119
0120 //////////////////////////////////
0121 template<typename Char>
0122 inline void range_run<Char>::swap(range_run<Char> &rr)
0123 {
0124     this->run_.swap(rr.run_);
0125 }
0126
0127 //////////////////////////////////
0128 template<typename Char>
0129 void range_run<Char>::merge(iterator iter, range<Char> const &r)
0130 {
0131     BOOST_ASSERT(iter != this->run_.end());
0132     iter->merge(r);
0133
0134     iterator i = iter;
0135     while(++i != this->run_.end() && iter->overlaps(*i))
0136     {
0137         iter->merge(*i);
0138     }
0139
0140     this->run_.erase(++iter, i);
0141 }
0142
0143 //////////////////////////////////
0144 template<typename Char>
0145 void range_run<Char>::set(range<Char> const &r)
0146 {
0147     BOOST_ASSERT(r.is_valid());
0148     if(!this->run_.empty())
0149     {
0150         iterator iter = std::lower_bound(this->run_.begin(), this->run_.end(), r, range_compare<Char>());
0151
0152         if((iter != this->run_.end() && iter->includes(r)) ||
0153            (iter != this->run_.begin() && (iter - 1)->includes(r)))
0154         {
0155             return;
0156         }
0157         else if(iter != this->run_.begin() && (iter - 1)->overlaps(r))
0158         {
0159             this->merge(--iter, r);
0160         }
0161         else if(iter != this->run_.end() && iter->overlaps(r))
0162         {
0163             this->merge(iter, r);
0164         }
0165         else
0166         {
0167             this->run_.insert(iter, r);
0168         }
0169     }
0170     else
0171     {
0172         this->run_.push_back(r);
0173     }
0174 }
0175
0176 //////////////////////////////////
0177 template<typename Char>
0178 void range_run<Char>::clear(range<Char> const &r)
0179 {
0180     BOOST_ASSERT(r.is_valid());
0181     if(!this->run_.empty())
0182     {
0183         iterator iter = std::lower_bound(this->run_.begin(), this->run_.end(), r, range_compare<Char>());
0184         iterator left_iter;
0185
0186         if((iter != this->run_.begin()) &&
0187            (left_iter = (iter - 1))->includes(r.first_))
0188         {
0189             if(left_iter->last_ > r.last_)
0190             {
0191                 Char save_last = left_iter->last_;
0192                 left_iter->last_ = r.first_-1;
0193                 this->run_.insert(iter, range<Char>(r.last_+1, save_last));
0194                 return;
0195             }
0196             else
0197             {
0198                 left_iter->last_ = r.first_-1;
0199             }
0200         }
0201
0202         iterator i = iter;
0203         for(; i != this->run_.end() && r.includes(*i); ++i) {}
0204         if(i != this->run_.end() && i->includes(r.last_))
0205         {
0206             i->first_ = r.last_+1;
0207         }
0208         this->run_.erase(iter, i);
0209     }
0210 }
0211
0212 //////////////////////////////////
0213 template<typename Char>
0214 inline void range_run<Char>::clear()
0215 {
0216     this->run_.clear();
0217 }
0218
0219 //////////////////////////////////
0220 template<typename Char>
0221 inline typename range_run<Char>::const_iterator range_run<Char>::begin() const
0222 {
0223     return this->run_.begin();
0224 }
0225
0226 //////////////////////////////////
0227 template<typename Char>
0228 inline typename range_run<Char>::const_iterator range_run<Char>::end() const
0229 {
0230     return this->run_.end();
0231 }
0232
0233 }}} // namespace boost::xpressive::detail
0234
0235 #endif