boost/xpressive/detail/utility/chset/range_run.ipp
/*=============================================================================
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_XPRESSIVE_SPIRIT_RANGE_RUN_IPP
#define BOOST_XPRESSIVE_SPIRIT_RANGE_RUN_IPP
///////////////////////////////////////////////////////////////////////////////
#include <algorithm> // for std::lower_bound
#include <boost/limits.hpp>
#include <boost/assert.hpp>
#include <boost/xpressive/detail/utility/chset/range_run.hpp>
///////////////////////////////////////////////////////////////////////////////
namespace boost { namespace xpressive { namespace detail
{
///////////////////////////////////////////////////////////////////////
//
// range class implementation
//
///////////////////////////////////////////////////////////////////////
template<typename Char>
inline range<Char>::range(Char first, Char last)
: first_(first)
, last_(last)
{
}
//////////////////////////////////
template<typename Char>
inline bool range<Char>::is_valid() const
{
return this->first_ <= this->last_;
}
//////////////////////////////////
template<typename Char>
inline bool range<Char>::includes(range<Char> const &r) const
{
return (this->first_ <= r.first_) && (this->last_ >= r.last_);
}
//////////////////////////////////
template<typename Char>
inline bool range<Char>::includes(Char v) const
{
return (this->first_ <= v) && (this->last_ >= v);
}
//////////////////////////////////
template<typename Char>
inline bool range<Char>::overlaps(range<Char> const &r) const
{
Char decr_first = (std::min)(this->first_, Char(this->first_-1));
Char incr_last = (std::max)(this->last_, Char(this->last_+1));
return (decr_first <= r.last_) && (incr_last >= r.first_);
}
//////////////////////////////////
template<typename Char>
inline void range<Char>::merge(range<Char> const &r)
{
this->first_ = (std::min)(this->first_, r.first_);
this->last_ = (std::max)(this->last_, r.last_);
}
///////////////////////////////////////////////////////////////////////
//
// range_run class implementation
//
///////////////////////////////////////////////////////////////////////
template<typename Char>
inline bool range_run<Char>::empty() const
{
return this->run_.empty();
}
template<typename Char>
inline bool range_run<Char>::test(Char v) const
{
if(this->run_.empty())
{
return false;
}
const_iterator iter = std::lower_bound(
this->run_.begin()
, this->run_.end()
, range<Char>(v, v)
, range_compare<Char>()
);
return (iter != this->run_.end() && iter->includes(v))
|| (iter != this->run_.begin() && (--iter)->includes(v));
}
template<typename Char>
template<typename Traits>
inline bool range_run<Char>::test(Char v, Traits const &traits) const
{
const_iterator begin = this->run_.begin();
const_iterator end = this->run_.end();
for(; begin != end; ++begin)
{
if(traits.in_range_nocase(begin->first_, begin->last_, v))
{
return true;
}
}
return false;
}
//////////////////////////////////
template<typename Char>
inline void range_run<Char>::swap(range_run<Char> &rr)
{
this->run_.swap(rr.run_);
}
//////////////////////////////////
template<typename Char>
void range_run<Char>::merge(iterator iter, range<Char> const &r)
{
BOOST_ASSERT(iter != this->run_.end());
iter->merge(r);
iterator i = iter;
while(++i != this->run_.end() && iter->overlaps(*i))
{
iter->merge(*i);
}
this->run_.erase(++iter, i);
}
//////////////////////////////////
template<typename Char>
void range_run<Char>::set(range<Char> const &r)
{
BOOST_ASSERT(r.is_valid());
if(!this->run_.empty())
{
iterator iter = std::lower_bound(this->run_.begin(), this->run_.end(), r, range_compare<Char>());
if((iter != this->run_.end() && iter->includes(r)) ||
(iter != this->run_.begin() && (iter - 1)->includes(r)))
{
return;
}
else if(iter != this->run_.begin() && (iter - 1)->overlaps(r))
{
this->merge(--iter, r);
}
else if(iter != this->run_.end() && iter->overlaps(r))
{
this->merge(iter, r);
}
else
{
this->run_.insert(iter, r);
}
}
else
{
this->run_.push_back(r);
}
}
//////////////////////////////////
template<typename Char>
void range_run<Char>::clear(range<Char> const &r)
{
BOOST_ASSERT(r.is_valid());
if(!this->run_.empty())
{
iterator iter = std::lower_bound(this->run_.begin(), this->run_.end(), r, range_compare<Char>());
iterator left_iter;
if((iter != this->run_.begin()) &&
(left_iter = (iter - 1))->includes(r.first_))
{
if(left_iter->last_ > r.last_)
{
Char save_last = left_iter->last_;
left_iter->last_ = r.first_-1;
this->run_.insert(iter, range<Char>(r.last_+1, save_last));
return;
}
else
{
left_iter->last_ = r.first_-1;
}
}
iterator i = iter;
for(; i != this->run_.end() && r.includes(*i); ++i) {}
if(i != this->run_.end() && i->includes(r.last_))
{
i->first_ = r.last_+1;
}
this->run_.erase(iter, i);
}
}
//////////////////////////////////
template<typename Char>
inline void range_run<Char>::clear()
{
this->run_.clear();
}
//////////////////////////////////
template<typename Char>
inline typename range_run<Char>::const_iterator range_run<Char>::begin() const
{
return this->run_.begin();
}
//////////////////////////////////
template<typename Char>
inline typename range_run<Char>::const_iterator range_run<Char>::end() const
{
return this->run_.end();
}
}}} // namespace boost::xpressive::detail
#endif