/*============================================================================= | |
Copyright (c) 2001-2011 Joel de Guzman | |
Distributed under the Boost Software License, Version 1.0. (See accompanying | |
file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) | |
==============================================================================*/ | |
#if !defined(BOOST_SPIRIT_RANGE_RUN_MAY_16_2006_0807_PM) | |
#define BOOST_SPIRIT_RANGE_RUN_MAY_16_2006_0807_PM | |
#if defined(_MSC_VER) | |
#pragma once | |
#endif | |
#include <boost/spirit/home/support/char_set/range_functions.hpp> | |
#include <boost/assert.hpp> | |
#include <boost/integer_traits.hpp> | |
#include <algorithm> | |
namespace boost { namespace spirit { namespace support { namespace detail | |
{ | |
template <typename Run, typename Iterator, typename Range> | |
inline bool | |
try_merge(Run& run, Iterator iter, Range const& range) | |
{ | |
// if *iter intersects with, or is adjacent to, 'range'... | |
if (can_merge(*iter, range)) | |
{ | |
typedef typename Range::value_type value_type; | |
typedef integer_traits<value_type> integer_traits; | |
// merge range and *iter | |
merge(*iter, range); | |
// collapse all subsequent ranges that can merge with *iter: | |
Iterator i = iter+1; | |
// 1. skip subsequent ranges completely included in *iter | |
while (i != run.end() && i->last <= iter->last) | |
++i; | |
// 2. collapse next range if adjacent or overlapping with *iter | |
if (i != run.end() && i->first-1 <= iter->last) | |
{ | |
iter->last = i->last; | |
++i; | |
} | |
// erase all ranges that were collapsed | |
run.erase(iter+1, i); | |
return true; | |
} | |
return false; | |
} | |
template <typename Char> | |
inline bool | |
range_run<Char>::test(Char val) const | |
{ | |
if (run.empty()) | |
return false; | |
// search the ranges for one that potentially includes val | |
typename storage_type::const_iterator iter = | |
std::upper_bound( | |
run.begin(), run.end(), val, | |
range_compare<range_type>() | |
); | |
// return true if *(iter-1) includes val | |
return iter != run.begin() && includes(*(--iter), val); | |
} | |
template <typename Char> | |
inline void | |
range_run<Char>::swap(range_run& other) | |
{ | |
run.swap(other.run); | |
} | |
template <typename Char> | |
void | |
range_run<Char>::set(range_type const& range) | |
{ | |
BOOST_ASSERT(is_valid(range)); | |
if (run.empty()) | |
{ | |
// the vector is empty, insert 'range' | |
run.push_back(range); | |
return; | |
} | |
// search the ranges for one that potentially includes 'range' | |
typename storage_type::iterator iter = | |
std::upper_bound( | |
run.begin(), run.end(), range, | |
range_compare<range_type>() | |
); | |
if (iter != run.begin()) | |
{ | |
// if *(iter-1) includes 'range', return early | |
if (includes(*(iter-1), range)) | |
{ | |
return; | |
} | |
// if *(iter-1) can merge with 'range', merge them and return | |
if (try_merge(run, iter-1, range)) | |
{ | |
return; | |
} | |
} | |
// if *iter can merge with with 'range', merge them | |
if (iter == run.end() || !try_merge(run, iter, range)) | |
{ | |
// no overlap, insert 'range' | |
run.insert(iter, range); | |
} | |
} | |
template <typename Char> | |
void | |
range_run<Char>::clear(range_type const& range) | |
{ | |
BOOST_ASSERT(is_valid(range)); | |
if (!run.empty()) | |
{ | |
// search the ranges for one that potentially includes 'range' | |
typename storage_type::iterator iter = | |
std::upper_bound( | |
run.begin(), run.end(), range, | |
range_compare<range_type>() | |
); | |
// 'range' starts with or after another range: | |
if (iter != run.begin()) | |
{ | |
typename storage_type::iterator const left_iter = iter-1; | |
// 'range' starts after '*left_iter': | |
if (left_iter->first < range.first) | |
{ | |
// if 'range' is completely included inside '*left_iter': | |
// need to break it apart into two ranges (punch a hole), | |
if (left_iter->last > range.last) | |
{ | |
Char save_last = left_iter->last; | |
left_iter->last = range.first-1; | |
run.insert(iter, range_type(range.last+1, save_last)); | |
return; | |
} | |
// if 'range' contains 'left_iter->last': | |
// truncate '*left_iter' (clip its right) | |
else if (left_iter->last >= range.first) | |
{ | |
left_iter->last = range.first-1; | |
} | |
} | |
// 'range' has the same left bound as '*left_iter': it | |
// must be removed or truncated by the code below | |
else | |
{ | |
iter = left_iter; | |
} | |
} | |
// remove or truncate subsequent ranges that overlap with 'range': | |
typename storage_type::iterator i = iter; | |
// 1. skip subsequent ranges completely included in 'range' | |
while (i != run.end() && i->last <= range.last) | |
++i; | |
// 2. clip left of next range if overlapping with 'range' | |
if (i != run.end() && i->first <= range.last) | |
i->first = range.last+1; | |
// erase all ranges that 'range' contained | |
run.erase(iter, i); | |
} | |
} | |
template <typename Char> | |
inline void | |
range_run<Char>::clear() | |
{ | |
run.clear(); | |
} | |
}}}} | |
#endif |