Chris@16: /*=============================================================================
Chris@16:     Copyright (c) 2001-2003 Joel de Guzman
Chris@16:     http://spirit.sourceforge.net/
Chris@16: 
Chris@16:     Use, modification and distribution is subject to the Boost Software
Chris@16:     License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
Chris@16:     http://www.boost.org/LICENSE_1_0.txt)
Chris@16: =============================================================================*/
Chris@16: #ifndef BOOST_XPRESSIVE_SPIRIT_RANGE_RUN_IPP
Chris@16: #define BOOST_XPRESSIVE_SPIRIT_RANGE_RUN_IPP
Chris@16: 
Chris@16: ///////////////////////////////////////////////////////////////////////////////
Chris@16: #include <algorithm> // for std::lower_bound
Chris@16: #include <boost/limits.hpp>
Chris@16: #include <boost/assert.hpp>
Chris@16: #include <boost/xpressive/detail/utility/chset/range_run.hpp>
Chris@16: 
Chris@16: ///////////////////////////////////////////////////////////////////////////////
Chris@16: namespace boost { namespace xpressive { namespace detail
Chris@16: {
Chris@16: 
Chris@16: ///////////////////////////////////////////////////////////////////////
Chris@16: //
Chris@16: //  range class implementation
Chris@16: //
Chris@16: ///////////////////////////////////////////////////////////////////////
Chris@16: template<typename Char>
Chris@16: inline range<Char>::range(Char first, Char last)
Chris@16:   : first_(first)
Chris@16:   , last_(last)
Chris@16: {
Chris@16: }
Chris@16: 
Chris@16: //////////////////////////////////
Chris@16: template<typename Char>
Chris@16: inline bool range<Char>::is_valid() const
Chris@16: {
Chris@16:     return this->first_ <= this->last_;
Chris@16: }
Chris@16: 
Chris@16: //////////////////////////////////
Chris@16: template<typename Char>
Chris@16: inline bool range<Char>::includes(range<Char> const &r) const
Chris@16: {
Chris@16:     return (this->first_ <= r.first_) && (this->last_ >= r.last_);
Chris@16: }
Chris@16: 
Chris@16: //////////////////////////////////
Chris@16: template<typename Char>
Chris@16: inline bool range<Char>::includes(Char v) const
Chris@16: {
Chris@16:     return (this->first_ <= v) && (this->last_ >= v);
Chris@16: }
Chris@16: 
Chris@16: //////////////////////////////////
Chris@16: template<typename Char>
Chris@16: inline bool range<Char>::overlaps(range<Char> const &r) const
Chris@16: {
Chris@16:     Char decr_first = (std::min)(this->first_, Char(this->first_-1));
Chris@16:     Char incr_last = (std::max)(this->last_, Char(this->last_+1));
Chris@16: 
Chris@16:     return (decr_first <= r.last_) && (incr_last >= r.first_);
Chris@16: }
Chris@16: 
Chris@16: //////////////////////////////////
Chris@16: template<typename Char>
Chris@16: inline void range<Char>::merge(range<Char> const &r)
Chris@16: {
Chris@16:     this->first_ = (std::min)(this->first_, r.first_);
Chris@16:     this->last_ = (std::max)(this->last_, r.last_);
Chris@16: }
Chris@16: 
Chris@16: ///////////////////////////////////////////////////////////////////////
Chris@16: //
Chris@16: //  range_run class implementation
Chris@16: //
Chris@16: ///////////////////////////////////////////////////////////////////////
Chris@16: template<typename Char>
Chris@16: inline bool range_run<Char>::empty() const
Chris@16: {
Chris@16:     return this->run_.empty();
Chris@16: }
Chris@16: 
Chris@16: template<typename Char>
Chris@16: inline bool range_run<Char>::test(Char v) const
Chris@16: {
Chris@16:     if(this->run_.empty())
Chris@16:     {
Chris@16:         return false;
Chris@16:     }
Chris@16: 
Chris@16:     const_iterator iter = std::lower_bound(
Chris@16:         this->run_.begin()
Chris@16:       , this->run_.end()
Chris@16:       , range<Char>(v, v)
Chris@16:       , range_compare<Char>()
Chris@16:     );
Chris@16: 
Chris@16:     return (iter != this->run_.end() && iter->includes(v))
Chris@16:         || (iter != this->run_.begin() && (--iter)->includes(v));
Chris@16: }
Chris@16: 
Chris@16: template<typename Char>
Chris@16: template<typename Traits>
Chris@16: inline bool range_run<Char>::test(Char v, Traits const &tr) const
Chris@16: {
Chris@16:     const_iterator begin = this->run_.begin();
Chris@16:     const_iterator end = this->run_.end();
Chris@16: 
Chris@16:     for(; begin != end; ++begin)
Chris@16:     {
Chris@16:         if(tr.in_range_nocase(begin->first_, begin->last_, v))
Chris@16:         {
Chris@16:             return true;
Chris@16:         }
Chris@16:     }
Chris@16:     return false;
Chris@16: }
Chris@16: 
Chris@16: //////////////////////////////////
Chris@16: template<typename Char>
Chris@16: inline void range_run<Char>::swap(range_run<Char> &rr)
Chris@16: {
Chris@16:     this->run_.swap(rr.run_);
Chris@16: }
Chris@16: 
Chris@16: //////////////////////////////////
Chris@16: template<typename Char>
Chris@16: void range_run<Char>::merge(iterator iter, range<Char> const &r)
Chris@16: {
Chris@16:     BOOST_ASSERT(iter != this->run_.end());
Chris@16:     iter->merge(r);
Chris@16: 
Chris@16:     iterator i = iter;
Chris@16:     while(++i != this->run_.end() && iter->overlaps(*i))
Chris@16:     {
Chris@16:         iter->merge(*i);
Chris@16:     }
Chris@16: 
Chris@16:     this->run_.erase(++iter, i);
Chris@16: }
Chris@16: 
Chris@16: //////////////////////////////////
Chris@16: template<typename Char>
Chris@16: void range_run<Char>::set(range<Char> const &r)
Chris@16: {
Chris@16:     BOOST_ASSERT(r.is_valid());
Chris@16:     if(!this->run_.empty())
Chris@16:     {
Chris@16:         iterator iter = std::lower_bound(this->run_.begin(), this->run_.end(), r, range_compare<Char>());
Chris@16: 
Chris@16:         if((iter != this->run_.end() && iter->includes(r)) ||
Chris@16:            (iter != this->run_.begin() && (iter - 1)->includes(r)))
Chris@16:         {
Chris@16:             return;
Chris@16:         }
Chris@16:         else if(iter != this->run_.begin() && (iter - 1)->overlaps(r))
Chris@16:         {
Chris@16:             this->merge(--iter, r);
Chris@16:         }
Chris@16:         else if(iter != this->run_.end() && iter->overlaps(r))
Chris@16:         {
Chris@16:             this->merge(iter, r);
Chris@16:         }
Chris@16:         else
Chris@16:         {
Chris@16:             this->run_.insert(iter, r);
Chris@16:         }
Chris@16:     }
Chris@16:     else
Chris@16:     {
Chris@16:         this->run_.push_back(r);
Chris@16:     }
Chris@16: }
Chris@16: 
Chris@16: //////////////////////////////////
Chris@16: template<typename Char>
Chris@16: void range_run<Char>::clear(range<Char> const &r)
Chris@16: {
Chris@16:     BOOST_ASSERT(r.is_valid());
Chris@16:     if(!this->run_.empty())
Chris@16:     {
Chris@16:         iterator iter = std::lower_bound(this->run_.begin(), this->run_.end(), r, range_compare<Char>());
Chris@16:         iterator left_iter;
Chris@16: 
Chris@16:         if((iter != this->run_.begin()) &&
Chris@16:            (left_iter = (iter - 1))->includes(r.first_))
Chris@16:         {
Chris@16:             if(left_iter->last_ > r.last_)
Chris@16:             {
Chris@16:                 Char save_last = left_iter->last_;
Chris@16:                 left_iter->last_ = r.first_-1;
Chris@16:                 this->run_.insert(iter, range<Char>(r.last_+1, save_last));
Chris@16:                 return;
Chris@16:             }
Chris@16:             else
Chris@16:             {
Chris@16:                 left_iter->last_ = r.first_-1;
Chris@16:             }
Chris@16:         }
Chris@16: 
Chris@16:         iterator i = iter;
Chris@16:         for(; i != this->run_.end() && r.includes(*i); ++i) {}
Chris@16:         if(i != this->run_.end() && i->includes(r.last_))
Chris@16:         {
Chris@16:             i->first_ = r.last_+1;
Chris@16:         }
Chris@16:         this->run_.erase(iter, i);
Chris@16:     }
Chris@16: }
Chris@16: 
Chris@16: //////////////////////////////////
Chris@16: template<typename Char>
Chris@16: inline void range_run<Char>::clear()
Chris@16: {
Chris@16:     this->run_.clear();
Chris@16: }
Chris@16: 
Chris@16: //////////////////////////////////
Chris@16: template<typename Char>
Chris@16: inline typename range_run<Char>::const_iterator range_run<Char>::begin() const
Chris@16: {
Chris@16:     return this->run_.begin();
Chris@16: }
Chris@16: 
Chris@16: //////////////////////////////////
Chris@16: template<typename Char>
Chris@16: inline typename range_run<Char>::const_iterator range_run<Char>::end() const
Chris@16: {
Chris@16:     return this->run_.end();
Chris@16: }
Chris@16: 
Chris@16: }}} // namespace boost::xpressive::detail
Chris@16: 
Chris@16: #endif