/*============================================================================= | |
Copyright (c) 2001-2003 Joel de Guzman | |
http://spirit.sourceforge.net/ | |
Use, modification and distribution is subject to 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) | |
=============================================================================*/ | |
#ifndef BOOST_SPIRIT_RANGE_RUN_IPP | |
#define BOOST_SPIRIT_RANGE_RUN_IPP | |
/////////////////////////////////////////////////////////////////////////////// | |
#include <algorithm> // for std::lower_bound | |
#include <boost/spirit/home/classic/core/assert.hpp> // for BOOST_SPIRIT_ASSERT | |
#include <boost/spirit/home/classic/utility/impl/chset/range_run.hpp> | |
#include <boost/spirit/home/classic/debug.hpp> | |
#include <boost/limits.hpp> | |
/////////////////////////////////////////////////////////////////////////////// | |
namespace boost { namespace spirit { | |
BOOST_SPIRIT_CLASSIC_NAMESPACE_BEGIN | |
namespace utility { namespace impl { | |
/////////////////////////////////////////////////////////////////////// | |
// | |
// range class implementation | |
// | |
/////////////////////////////////////////////////////////////////////// | |
template <typename CharT> | |
inline range<CharT>::range(CharT first_, CharT last_) | |
: first(first_), last(last_) {} | |
////////////////////////////////// | |
template <typename CharT> | |
inline bool | |
range<CharT>::is_valid() const | |
{ return first <= last; } | |
////////////////////////////////// | |
template <typename CharT> | |
inline bool | |
range<CharT>::includes(range const& r) const | |
{ return (first <= r.first) && (last >= r.last); } | |
////////////////////////////////// | |
template <typename CharT> | |
inline bool | |
range<CharT>::includes(CharT v) const | |
{ return (first <= v) && (last >= v); } | |
////////////////////////////////// | |
template <typename CharT> | |
inline bool | |
range<CharT>::overlaps(range const& r) const | |
{ | |
CharT decr_first = | |
first == (std::numeric_limits<CharT>::min)() ? first : first-1; | |
CharT incr_last = | |
last == (std::numeric_limits<CharT>::max)() ? last : last+1; | |
return (decr_first <= r.last) && (incr_last >= r.first); | |
} | |
////////////////////////////////// | |
template <typename CharT> | |
inline void | |
range<CharT>::merge(range const& r) | |
{ | |
first = (std::min)(first, r.first); | |
last = (std::max)(last, r.last); | |
} | |
/////////////////////////////////////////////////////////////////////// | |
// | |
// range_run class implementation | |
// | |
/////////////////////////////////////////////////////////////////////// | |
template <typename CharT> | |
inline bool | |
range_run<CharT>::test(CharT v) const | |
{ | |
if (!run.empty()) | |
{ | |
const_iterator iter = | |
std::lower_bound( | |
run.begin(), run.end(), v, | |
range_char_compare<CharT>() | |
); | |
if (iter != run.end() && iter->includes(v)) | |
return true; | |
if (iter != run.begin()) | |
return (--iter)->includes(v); | |
} | |
return false; | |
} | |
////////////////////////////////// | |
template <typename CharT> | |
inline void | |
range_run<CharT>::swap(range_run& rr) | |
{ run.swap(rr.run); } | |
////////////////////////////////// | |
template <typename CharT> | |
void | |
range_run<CharT>::merge(iterator iter, range<CharT> const& r) | |
{ | |
iter->merge(r); | |
iterator i = iter + 1; | |
while (i != run.end() && iter->overlaps(*i)) | |
iter->merge(*i++); | |
run.erase(iter+1, i); | |
} | |
////////////////////////////////// | |
template <typename CharT> | |
void | |
range_run<CharT>::set(range<CharT> const& r) | |
{ | |
BOOST_SPIRIT_ASSERT(r.is_valid()); | |
if (!run.empty()) | |
{ | |
iterator iter = | |
std::lower_bound( | |
run.begin(), run.end(), r, | |
range_compare<CharT>() | |
); | |
if ((iter != run.end() && iter->includes(r)) || | |
((iter != run.begin()) && (iter - 1)->includes(r))) | |
return; | |
if (iter != run.begin() && (iter - 1)->overlaps(r)) | |
merge(--iter, r); | |
else if (iter != run.end() && iter->overlaps(r)) | |
merge(iter, r); | |
else | |
run.insert(iter, r); | |
} | |
else | |
{ | |
run.push_back(r); | |
} | |
} | |
////////////////////////////////// | |
template <typename CharT> | |
void | |
range_run<CharT>::clear(range<CharT> const& r) | |
{ | |
BOOST_SPIRIT_ASSERT(r.is_valid()); | |
if (!run.empty()) | |
{ | |
iterator iter = | |
std::lower_bound( | |
run.begin(), run.end(), r, | |
range_compare<CharT>() | |
); | |
iterator left_iter; | |
if ((iter != run.begin()) && | |
(left_iter = (iter - 1))->includes(r.first)) | |
{ | |
if (left_iter->last > r.last) | |
{ | |
CharT save_last = left_iter->last; | |
left_iter->last = r.first-1; | |
run.insert(iter, range<CharT>(r.last+1, save_last)); | |
return; | |
} | |
else | |
{ | |
left_iter->last = r.first-1; | |
} | |
} | |
iterator i = iter; | |
while (i != run.end() && r.includes(*i)) | |
i++; | |
if (i != run.end() && i->includes(r.last)) | |
i->first = r.last+1; | |
run.erase(iter, i); | |
} | |
} | |
////////////////////////////////// | |
template <typename CharT> | |
inline void | |
range_run<CharT>::clear() | |
{ run.clear(); } | |
////////////////////////////////// | |
template <typename CharT> | |
inline typename range_run<CharT>::const_iterator | |
range_run<CharT>::begin() const | |
{ return run.begin(); } | |
////////////////////////////////// | |
template <typename CharT> | |
inline typename range_run<CharT>::const_iterator | |
range_run<CharT>::end() const | |
{ return run.end(); } | |
}} // namespace utility::impl | |
BOOST_SPIRIT_CLASSIC_NAMESPACE_END | |
}} // namespace boost::spirit | |
#endif |