ceph/src/boost/boost/spirit/home/support/char_set/range_run_impl.hpp

   1 /*=============================================================================
   2     Copyright (c) 2001-2011 Joel de Guzman
   3
   4     Distributed under the Boost Software License, Version 1.0. (See accompanying
   5     file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   6 ==============================================================================*/
   7 #if !defined(BOOST_SPIRIT_RANGE_RUN_MAY_16_2006_0807_PM)
   8 #define BOOST_SPIRIT_RANGE_RUN_MAY_16_2006_0807_PM
   9
  10 #if defined(_MSC_VER)
  11 #pragma once
  12 #endif
  13
  14 #include <boost/spirit/home/support/char_set/range_functions.hpp>
  15 #include <boost/assert.hpp>
  16 #include <algorithm>
  17
  18 namespace boost { namespace spirit { namespace support { namespace detail
  19 {
  20     template <typename Run, typename Iterator, typename Range>
  21     inline bool
  22     try_merge(Run& run, Iterator iter, Range const& range)
  23     {
  24         // if *iter intersects with, or is adjacent to, 'range'...
  25         if (can_merge(*iter, range))
  26         {
  27             // merge range and *iter
  28             merge(*iter, range);
  29
  30             // collapse all subsequent ranges that can merge with *iter:
  31             Iterator i = iter+1;
  32             // 1. skip subsequent ranges completely included in *iter
  33             while (i != run.end() && i->last <= iter->last)
  34                 ++i;
  35             // 2. collapse next range if adjacent or overlapping with *iter
  36             if (i != run.end() && i->first-1 <= iter->last)
  37             {
  38                 iter->last = i->last;
  39                 ++i;
  40             }
  41
  42             // erase all ranges that were collapsed
  43             run.erase(iter+1, i);
  44             return true;
  45         }
  46         return false;
  47     }
  48
  49     template <typename Char>
  50     inline bool
  51     range_run<Char>::test(Char val) const
  52     {
  53         if (run.empty())
  54             return false;
  55
  56         // search the ranges for one that potentially includes val
  57         typename storage_type::const_iterator iter =
  58             std::upper_bound(
  59                 run.begin(), run.end(), val,
  60                 range_compare<range_type>()
  61             );
  62
  63         // return true if *(iter-1) includes val
  64         return iter != run.begin() && includes(*(--iter), val);
  65     }
  66
  67     template <typename Char>
  68     inline void
  69     range_run<Char>::swap(range_run& other)
  70     {
  71         run.swap(other.run);
  72     }
  73
  74     template <typename Char>
  75     void
  76     range_run<Char>::set(range_type const& range)
  77     {
  78         BOOST_ASSERT(is_valid(range));
  79         if (run.empty())
  80         {
  81             // the vector is empty, insert 'range'
  82             run.push_back(range);
  83             return;
  84         }
  85
  86         // search the ranges for one that potentially includes 'range'
  87         typename storage_type::iterator iter =
  88             std::upper_bound(
  89                 run.begin(), run.end(), range,
  90                 range_compare<range_type>()
  91             );
  92
  93         if (iter != run.begin())
  94         {
  95             // if *(iter-1) includes 'range', return early
  96             if (includes(*(iter-1), range))
  97             {
  98                 return;
  99             }
 100
 101             // if *(iter-1) can merge with 'range', merge them and return
 102             if (try_merge(run, iter-1, range))
 103             {
 104                 return;
 105             }
 106         }
 107
 108         // if *iter can merge with with 'range', merge them
 109         if (iter == run.end() || !try_merge(run, iter, range))
 110         {
 111             // no overlap, insert 'range'
 112             run.insert(iter, range);
 113         }
 114     }
 115
 116     template <typename Char>
 117     void
 118     range_run<Char>::clear(range_type const& range)
 119     {
 120         BOOST_ASSERT(is_valid(range));
 121         if (!run.empty())
 122         {
 123             // search the ranges for one that potentially includes 'range'
 124             typename storage_type::iterator iter =
 125                 std::upper_bound(
 126                     run.begin(), run.end(), range,
 127                     range_compare<range_type>()
 128                 );
 129
 130             // 'range' starts with or after another range:
 131             if (iter != run.begin())
 132             {
 133                 typename storage_type::iterator const left_iter = iter-1;
 134
 135                 // 'range' starts after '*left_iter':
 136                 if (left_iter->first < range.first)
 137                 {
 138                     // if 'range' is completely included inside '*left_iter':
 139                     // need to break it apart into two ranges (punch a hole),
 140                     if (left_iter->last > range.last)
 141                     {
 142                         Char save_last = left_iter->last;
 143                         left_iter->last = range.first-1;
 144                         run.insert(iter, range_type(range.last+1, save_last));
 145                         return;
 146                     }
 147                     // if 'range' contains 'left_iter->last':
 148                     // truncate '*left_iter' (clip its right)
 149                     else if (left_iter->last >= range.first)
 150                     {
 151                         left_iter->last = range.first-1;
 152                     }
 153                 }
 154
 155                 // 'range' has the same left bound as '*left_iter': it
 156                 // must be removed or truncated by the code below
 157                 else
 158                 {
 159                     iter = left_iter;
 160                 }
 161             }
 162
 163             // remove or truncate subsequent ranges that overlap with 'range':
 164             typename storage_type::iterator i = iter;
 165             // 1. skip subsequent ranges completely included in 'range'
 166             while (i != run.end() && i->last <= range.last)
 167                 ++i;
 168             // 2. clip left of next range if overlapping with 'range'
 169             if (i != run.end() && i->first <= range.last)
 170                 i->first = range.last+1;
 171
 172             // erase all ranges that 'range' contained
 173             run.erase(iter, i);
 174         }
 175     }
 176
 177     template <typename Char>
 178     inline void
 179     range_run<Char>::clear()
 180     {
 181         run.clear();
 182     }
 183 }}}}
 184
 185 #endif