ceph/src/boost/libs/spirit/include/boost/spirit/home/classic/utility/impl/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_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