123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102 |
- /*=============================================================================
- 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 &tr) 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
|