| /*============================================================================= |
| 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 <vector> |
| |
| #include <boost/spirit/home/classic/namespace.hpp> |
| |
| /////////////////////////////////////////////////////////////////////////////// |
| 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; |
| }; |
| |
| }} |
| |
| BOOST_SPIRIT_CLASSIC_NAMESPACE_END |
| |
| }} // namespace BOOST_SPIRIT_CLASSIC_NS::utility::impl |
| |
| #endif |
| |
| #include <boost/spirit/home/classic/utility/impl/chset/range_run.ipp> |