text: /*=============================================================================
      Copyright (c) 2001-2003 Joel de Guzman
      http://spirit.sourceforge.net/
  
    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)
  =============================================================================*/
  #ifndef BOOST_SPIRIT_RANGE_RUN_HPP
  #define BOOST_SPIRIT_RANGE_RUN_HPP
  
  ///////////////////////////////////////////////////////////////////////////////
  #include <boost/spirit/home/classic/namespace.hpp>
  #include <vector>
  
  ///////////////////////////////////////////////////////////////////////////////
  namespace boost
  {
  namespace spirit
  {
  
  BOOST_SPIRIT_CLASSIC_NAMESPACE_BEGIN
  
  namespace utility
  {
  namespace impl
  {
  
  ///////////////////////////////////////////////////////////////////////////
  //
  //  range class
  //
  //      Implements a closed range of values. This class is used in
  //      the implementation of the range_run class.
  //
  //      { Low level implementation detail }
  //      { Not to be confused with BOOST_SPIRIT_CLASSIC_NS::range }
  //
  ///////////////////////////////////////////////////////////////////////////
  template <typename CharT>
  struct range
  {
  
      range(CharT first, CharT last);
  
      bool is_valid() const;
      bool includes(CharT v) const;
      bool includes(range const& r) const;
      bool overlaps(range const& r) const;
      void merge(range const& r);
  
      CharT first;
      CharT last;
  };
  
  //////////////////////////////////
  template <typename CharT>
  struct range_char_compare
  {
  
      bool operator()(range<CharT> const& x, const CharT y) const
      {
          return x.first < y;
      }
  
      bool operator()(const CharT x, range<CharT> const& y) const
      {
          return x < y.first;
      }
  
      // This additional operator is required for the checked STL shipped
      // with VC8 testing the ordering of the iterators passed to the
      // std::lower_bound algo this range_char_compare<> predicate is passed
      // to.
      bool operator()(range<CharT> const& x, range<CharT> const& y) const
      {
          return x.first < y.first;
      }
  };
  
  //////////////////////////////////
  template <typename CharT>
  struct range_compare
  {
  
      bool operator()(range<CharT> const& x, range<CharT> const& y) const
      {
          return x.first < y.first;
      }
  };
  
  ///////////////////////////////////////////////////////////////////////////
  //
  //  range_run
  //
  //      An implementation of a sparse bit (boolean) set. The set uses
  //      a sorted vector of disjoint ranges. This class implements the
  //      bare minimum essentials from which the full range of set
  //      operators can be implemented. The set is constructed from
  //      ranges. Internally, adjacent or overlapping ranges are
  //      coalesced.
  //
  //      range_runs are very space-economical in situations where there
  //      are lots of ranges and a few individual disjoint values.
  //      Searching is O(log n) where n is the number of ranges.
  //
  //      { Low level implementation detail }
  //
  ///////////////////////////////////////////////////////////////////////////
  template <typename CharT>
  class range_run
  {
  
    public:
      typedef range<CharT> range_t;
      typedef std::vector<range_t> run_t;
      typedef typename run_t::iterator iterator;
      typedef typename run_t::const_iterator const_iterator;
  
      void swap(range_run& rr);
      bool test(CharT v) const;
      void set(range_t const& r);
      void clear(range_t const& r);
      void clear();
  
      const_iterator begin() const;
      const_iterator end() const;
  
    private:
      void merge(iterator iter, range_t const& r);
  
      run_t run;
  };
  
  } // namespace impl
  } // namespace utility
  
  BOOST_SPIRIT_CLASSIC_NAMESPACE_END
  
  } // namespace spirit
  } // namespace boost
  
  #endif
  
  #include <boost/spirit/home/classic/utility/impl/chset/range_run.ipp>
  