support/char_set/range_run_impl.hpp

0001 /*=============================================================================
0002     Copyright (c) 2001-2011 Joel de Guzman
0003
0004     Distributed under the Boost Software License, Version 1.0. (See accompanying
0005     file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
0006 ==============================================================================*/
0007 #if !defined(BOOST_SPIRIT_RANGE_RUN_MAY_16_2006_0807_PM)
0008 #define BOOST_SPIRIT_RANGE_RUN_MAY_16_2006_0807_PM
0009
0010 #if defined(_MSC_VER)
0011 #pragma once
0012 #endif
0013
0014 #include <boost/spirit/home/support/char_set/range_functions.hpp>
0015 #include <boost/assert.hpp>
0016 #include <algorithm>
0017
0018 namespace boost { namespace spirit { namespace support { namespace detail
0019 {
0020     template <typename Run, typename Iterator, typename Range>
0021     inline bool
0022     try_merge(Run& run, Iterator iter, Range const& range)
0023     {
0024         // if *iter intersects with, or is adjacent to, 'range'...
0025         if (can_merge(*iter, range))
0026         {
0027             // merge range and *iter
0028             merge(*iter, range);
0029
0030             // collapse all subsequent ranges that can merge with *iter:
0031             Iterator i = iter+1;
0032             // 1. skip subsequent ranges completely included in *iter
0033             while (i != run.end() && i->last <= iter->last)
0034                 ++i;
0035             // 2. collapse next range if adjacent or overlapping with *iter
0036             if (i != run.end() && i->first-1 <= iter->last)
0037             {
0038                 iter->last = i->last;
0039                 ++i;
0040             }
0041
0042             // erase all ranges that were collapsed
0043             run.erase(iter+1, i);
0044             return true;
0045         }
0046         return false;
0047     }
0048
0049     template <typename Char>
0050     inline bool
0051     range_run<Char>::test(Char val) const
0052     {
0053         if (run.empty())
0054             return false;
0055
0056         // search the ranges for one that potentially includes val
0057         typename storage_type::const_iterator iter =
0058             std::upper_bound(
0059                 run.begin(), run.end(), val,
0060                 range_compare<range_type>()
0061             );
0062
0063         // return true if *(iter-1) includes val
0064         return iter != run.begin() && includes(*(--iter), val);
0065     }
0066
0067     template <typename Char>
0068     inline void
0069     range_run<Char>::swap(range_run& other)
0070     {
0071         run.swap(other.run);
0072     }
0073
0074     template <typename Char>
0075     void
0076     range_run<Char>::set(range_type const& range)
0077     {
0078         BOOST_ASSERT(is_valid(range));
0079         if (run.empty())
0080         {
0081             // the vector is empty, insert 'range'
0082             run.push_back(range);
0083             return;
0084         }
0085
0086         // search the ranges for one that potentially includes 'range'
0087         typename storage_type::iterator iter =
0088             std::upper_bound(
0089                 run.begin(), run.end(), range,
0090                 range_compare<range_type>()
0091             );
0092
0093         if (iter != run.begin())
0094         {
0095             // if *(iter-1) includes 'range', return early
0096             if (includes(*(iter-1), range))
0097             {
0098                 return;
0099             }
0100
0101             // if *(iter-1) can merge with 'range', merge them and return
0102             if (try_merge(run, iter-1, range))
0103             {
0104                 return;
0105             }
0106         }
0107
0108         // if *iter can merge with with 'range', merge them
0109         if (iter == run.end() || !try_merge(run, iter, range))
0110         {
0111             // no overlap, insert 'range'
0112             run.insert(iter, range);
0113         }
0114     }
0115
0116     template <typename Char>
0117     void
0118     range_run<Char>::clear(range_type const& range)
0119     {
0120         BOOST_ASSERT(is_valid(range));
0121         if (!run.empty())
0122         {
0123             // search the ranges for one that potentially includes 'range'
0124             typename storage_type::iterator iter =
0125                 std::upper_bound(
0126                     run.begin(), run.end(), range,
0127                     range_compare<range_type>()
0128                 );
0129
0130             // 'range' starts with or after another range:
0131             if (iter != run.begin())
0132             {
0133                 typename storage_type::iterator const left_iter = iter-1;
0134
0135                 // 'range' starts after '*left_iter':
0136                 if (left_iter->first < range.first)
0137                 {
0138                     // if 'range' is completely included inside '*left_iter':
0139                     // need to break it apart into two ranges (punch a hole),
0140                     if (left_iter->last > range.last)
0141                     {
0142                         Char save_last = left_iter->last;
0143                         left_iter->last = range.first-1;
0144                         run.insert(iter, range_type(range.last+1, save_last));
0145                         return;
0146                     }
0147                     // if 'range' contains 'left_iter->last':
0148                     // truncate '*left_iter' (clip its right)
0149                     else if (left_iter->last >= range.first)
0150                     {
0151                         left_iter->last = range.first-1;
0152                     }
0153                 }
0154
0155                 // 'range' has the same left bound as '*left_iter': it
0156                 // must be removed or truncated by the code below
0157                 else
0158                 {
0159                     iter = left_iter;
0160                 }
0161             }
0162
0163             // remove or truncate subsequent ranges that overlap with 'range':
0164             typename storage_type::iterator i = iter;
0165             // 1. skip subsequent ranges completely included in 'range'
0166             while (i != run.end() && i->last <= range.last)
0167                 ++i;
0168             // 2. clip left of next range if overlapping with 'range'
0169             if (i != run.end() && i->first <= range.last)
0170                 i->first = range.last+1;
0171
0172             // erase all ranges that 'range' contained
0173             run.erase(iter, i);
0174         }
0175     }
0176
0177     template <typename Char>
0178     inline void
0179     range_run<Char>::clear()
0180     {
0181         run.clear();
0182     }
0183 }}}}
0184
0185 #endif