ceph/src/boost/boost/xpressive/detail/utility/chset/range_run.ipp

   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_XPRESSIVE_SPIRIT_RANGE_RUN_IPP
  10 #define BOOST_XPRESSIVE_SPIRIT_RANGE_RUN_IPP
  11
  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>
  17
  18 ///////////////////////////////////////////////////////////////////////////////
  19 namespace boost { namespace xpressive { namespace detail
  20 {
  21
  22 ///////////////////////////////////////////////////////////////////////
  23 //
  24 //  range class implementation
  25 //
  26 ///////////////////////////////////////////////////////////////////////
  27 template<typename Char>
  28 inline range<Char>::range(Char first, Char last)
  29   : first_(first)
  30   , last_(last)
  31 {
  32 }
  33
  34 //////////////////////////////////
  35 template<typename Char>
  36 inline bool range<Char>::is_valid() const
  37 {
  38     return this->first_ <= this->last_;
  39 }
  40
  41 //////////////////////////////////
  42 template<typename Char>
  43 inline bool range<Char>::includes(range<Char> const &r) const
  44 {
  45     return (this->first_ <= r.first_) && (this->last_ >= r.last_);
  46 }
  47
  48 //////////////////////////////////
  49 template<typename Char>
  50 inline bool range<Char>::includes(Char v) const
  51 {
  52     return (this->first_ <= v) && (this->last_ >= v);
  53 }
  54
  55 //////////////////////////////////
  56 template<typename Char>
  57 inline bool range<Char>::overlaps(range<Char> const &r) const
  58 {
  59     Char decr_first = (std::min)(this->first_, Char(this->first_-1));
  60     Char incr_last = (std::max)(this->last_, Char(this->last_+1));
  61
  62     return (decr_first <= r.last_) && (incr_last >= r.first_);
  63 }
  64
  65 //////////////////////////////////
  66 template<typename Char>
  67 inline void range<Char>::merge(range<Char> const &r)
  68 {
  69     this->first_ = (std::min)(this->first_, r.first_);
  70     this->last_ = (std::max)(this->last_, r.last_);
  71 }
  72
  73 ///////////////////////////////////////////////////////////////////////
  74 //
  75 //  range_run class implementation
  76 //
  77 ///////////////////////////////////////////////////////////////////////
  78 template<typename Char>
  79 inline bool range_run<Char>::empty() const
  80 {
  81     return this->run_.empty();
  82 }
  83
  84 template<typename Char>
  85 inline bool range_run<Char>::test(Char v) const
  86 {
  87     if(this->run_.empty())
  88     {
  89         return false;
  90     }
  91
  92     const_iterator iter = std::lower_bound(
  93         this->run_.begin()
  94       , this->run_.end()
  95       , range<Char>(v, v)
  96       , range_compare<Char>()
  97     );
  98
  99     return (iter != this->run_.end() && iter->includes(v))
 100         || (iter != this->run_.begin() && (--iter)->includes(v));
 101 }
 102
 103 template<typename Char>
 104 template<typename Traits>
 105 inline bool range_run<Char>::test(Char v, Traits const &tr) const
 106 {
 107     const_iterator begin = this->run_.begin();
 108     const_iterator end = this->run_.end();
 109
 110     for(; begin != end; ++begin)
 111     {
 112         if(tr.in_range_nocase(begin->first_, begin->last_, v))
 113         {
 114             return true;
 115         }
 116     }
 117     return false;
 118 }
 119
 120 //////////////////////////////////
 121 template<typename Char>
 122 inline void range_run<Char>::swap(range_run<Char> &rr)
 123 {
 124     this->run_.swap(rr.run_);
 125 }
 126
 127 //////////////////////////////////
 128 template<typename Char>
 129 void range_run<Char>::merge(iterator iter, range<Char> const &r)
 130 {
 131     BOOST_ASSERT(iter != this->run_.end());
 132     iter->merge(r);
 133
 134     iterator i = iter;
 135     while(++i != this->run_.end() && iter->overlaps(*i))
 136     {
 137         iter->merge(*i);
 138     }
 139
 140     this->run_.erase(++iter, i);
 141 }
 142
 143 //////////////////////////////////
 144 template<typename Char>
 145 void range_run<Char>::set(range<Char> const &r)
 146 {
 147     BOOST_ASSERT(r.is_valid());
 148     if(!this->run_.empty())
 149     {
 150         iterator iter = std::lower_bound(this->run_.begin(), this->run_.end(), r, range_compare<Char>());
 151
 152         if((iter != this->run_.end() && iter->includes(r)) ||
 153            (iter != this->run_.begin() && (iter - 1)->includes(r)))
 154         {
 155             return;
 156         }
 157         else if(iter != this->run_.begin() && (iter - 1)->overlaps(r))
 158         {
 159             this->merge(--iter, r);
 160         }
 161         else if(iter != this->run_.end() && iter->overlaps(r))
 162         {
 163             this->merge(iter, r);
 164         }
 165         else
 166         {
 167             this->run_.insert(iter, r);
 168         }
 169     }
 170     else
 171     {
 172         this->run_.push_back(r);
 173     }
 174 }
 175
 176 //////////////////////////////////
 177 template<typename Char>
 178 void range_run<Char>::clear(range<Char> const &r)
 179 {
 180     BOOST_ASSERT(r.is_valid());
 181     if(!this->run_.empty())
 182     {
 183         iterator iter = std::lower_bound(this->run_.begin(), this->run_.end(), r, range_compare<Char>());
 184         iterator left_iter;
 185
 186         if((iter != this->run_.begin()) &&
 187            (left_iter = (iter - 1))->includes(r.first_))
 188         {
 189             if(left_iter->last_ > r.last_)
 190             {
 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));
 194                 return;
 195             }
 196             else
 197             {
 198                 left_iter->last_ = r.first_-1;
 199             }
 200         }
 201
 202         iterator i = iter;
 203         for(; i != this->run_.end() && r.includes(*i); ++i) {}
 204         if(i != this->run_.end() && i->includes(r.last_))
 205         {
 206             i->first_ = r.last_+1;
 207         }
 208         this->run_.erase(iter, i);
 209     }
 210 }
 211
 212 //////////////////////////////////
 213 template<typename Char>
 214 inline void range_run<Char>::clear()
 215 {
 216     this->run_.clear();
 217 }
 218
 219 //////////////////////////////////
 220 template<typename Char>
 221 inline typename range_run<Char>::const_iterator range_run<Char>::begin() const
 222 {
 223     return this->run_.begin();
 224 }
 225
 226 //////////////////////////////////
 227 template<typename Char>
 228 inline typename range_run<Char>::const_iterator range_run<Char>::end() const
 229 {
 230     return this->run_.end();
 231 }
 232
 233 }}} // namespace boost::xpressive::detail
 234
 235 #endif