/*=============================================================================

    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_HPP_EAN_10_04_2005

#define BOOST_XPRESSIVE_SPIRIT_RANGE_RUN_HPP_EAN_10_04_2005



///////////////////////////////////////////////////////////////////////////////

#include <vector>



///////////////////////////////////////////////////////////////////////////////

namespace boost { namespace xpressive { namespace detail

{



///////////////////////////////////////////////////////////////////////////

//

//  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 spirit::range }

//

///////////////////////////////////////////////////////////////////////////

template<typename Char>

struct range

{

    range(Char first, Char last);



    bool is_valid() const;

    bool includes(Char v) const;

    bool includes(range const &r) const;

    bool overlaps(range const &r) const;

    void merge(range const &r);



    Char first_;

    Char last_;

};



//////////////////////////////////

template<typename Char>

struct range_compare

{

    bool operator()(range<Char> const &x, range<Char> 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 Char>

struct range_run

{

    typedef range<Char> range_type;

    typedef std::vector<range_type> run_type;

    typedef typename run_type::iterator iterator;

    typedef typename run_type::const_iterator const_iterator;



    void swap(range_run& rr);

    bool empty() const;

    bool test(Char v) const;

    template<typename Traits>

    bool test(Char v, Traits const &traits) const;

    void set(range_type const &r);

    void clear(range_type const &r);

    void clear();



    const_iterator begin() const;

    const_iterator end() const;



private:

    void merge(iterator iter, range_type const &r);



    run_type run_;

};



}}} // namespace boost::xpressive::detail



#endif



