123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218 |
- /*=============================================================================
- 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
|