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_HPP_EAN_10_04_2005
Chris@16: #define BOOST_XPRESSIVE_SPIRIT_RANGE_RUN_HPP_EAN_10_04_2005
Chris@16: 
Chris@16: ///////////////////////////////////////////////////////////////////////////////
Chris@16: #include <vector>
Chris@16: 
Chris@16: ///////////////////////////////////////////////////////////////////////////////
Chris@16: namespace boost { namespace xpressive { namespace detail
Chris@16: {
Chris@16: 
Chris@16: ///////////////////////////////////////////////////////////////////////////
Chris@16: //
Chris@16: //  range class
Chris@16: //
Chris@16: //      Implements a closed range of values. This class is used in
Chris@16: //      the implementation of the range_run class.
Chris@16: //
Chris@16: //      { Low level implementation detail }
Chris@16: //      { Not to be confused with spirit::range }
Chris@16: //
Chris@16: ///////////////////////////////////////////////////////////////////////////
Chris@16: template<typename Char>
Chris@16: struct range
Chris@16: {
Chris@16:     range(Char first, Char last);
Chris@16: 
Chris@16:     bool is_valid() const;
Chris@16:     bool includes(Char v) const;
Chris@16:     bool includes(range const &r) const;
Chris@16:     bool overlaps(range const &r) const;
Chris@16:     void merge(range const &r);
Chris@16: 
Chris@16:     Char first_;
Chris@16:     Char last_;
Chris@16: };
Chris@16: 
Chris@16: //////////////////////////////////
Chris@16: template<typename Char>
Chris@16: struct range_compare
Chris@16: {
Chris@16:     bool operator()(range<Char> const &x, range<Char> const &y) const
Chris@16:     {
Chris@16:         return x.first_ < y.first_;
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: ///////////////////////////////////////////////////////////////////////////
Chris@16: //
Chris@16: //  range_run
Chris@16: //
Chris@16: //      An implementation of a sparse bit (boolean) set. The set uses
Chris@16: //      a sorted vector of disjoint ranges. This class implements the
Chris@16: //      bare minimum essentials from which the full range of set
Chris@16: //      operators can be implemented. The set is constructed from
Chris@16: //      ranges. Internally, adjacent or overlapping ranges are
Chris@16: //      coalesced.
Chris@16: //
Chris@16: //      range_runs are very space-economical in situations where there
Chris@16: //      are lots of ranges and a few individual disjoint values.
Chris@16: //      Searching is O(log n) where n is the number of ranges.
Chris@16: //
Chris@16: //      { Low level implementation detail }
Chris@16: //
Chris@16: ///////////////////////////////////////////////////////////////////////////
Chris@16: template<typename Char>
Chris@16: struct range_run
Chris@16: {
Chris@16:     typedef range<Char> range_type;
Chris@16:     typedef std::vector<range_type> run_type;
Chris@16:     typedef typename run_type::iterator iterator;
Chris@16:     typedef typename run_type::const_iterator const_iterator;
Chris@16: 
Chris@16:     void swap(range_run& rr);
Chris@16:     bool empty() const;
Chris@16:     bool test(Char v) const;
Chris@16:     template<typename Traits>
Chris@16:     bool test(Char v, Traits const &tr) const;
Chris@16:     void set(range_type const &r);
Chris@16:     void clear(range_type const &r);
Chris@16:     void clear();
Chris@16: 
Chris@16:     const_iterator begin() const;
Chris@16:     const_iterator end() const;
Chris@16: 
Chris@16: private:
Chris@16:     void merge(iterator iter, range_type const &r);
Chris@16: 
Chris@16:     run_type run_;
Chris@16: };
Chris@16: 
Chris@16: }}} // namespace boost::xpressive::detail
Chris@16: 
Chris@16: #endif
Chris@16: