utility/chset/range_run.hpp

0001 /*=============================================================================
0002     Copyright (c) 2001-2003 Joel de Guzman
0003     http://spirit.sourceforge.net/
0004
0005     Use, modification and distribution is subject to the Boost Software
0006     License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0007     http://www.boost.org/LICENSE_1_0.txt)
0008 =============================================================================*/
0009 #ifndef BOOST_XPRESSIVE_SPIRIT_RANGE_RUN_HPP_EAN_10_04_2005
0010 #define BOOST_XPRESSIVE_SPIRIT_RANGE_RUN_HPP_EAN_10_04_2005
0011
0012 ///////////////////////////////////////////////////////////////////////////////
0013 #include <vector>
0014
0015 ///////////////////////////////////////////////////////////////////////////////
0016 namespace boost { namespace xpressive { namespace detail
0017 {
0018
0019 ///////////////////////////////////////////////////////////////////////////
0020 //
0021 //  range class
0022 //
0023 //      Implements a closed range of values. This class is used in
0024 //      the implementation of the range_run class.
0025 //
0026 //      { Low level implementation detail }
0027 //      { Not to be confused with spirit::range }
0028 //
0029 ///////////////////////////////////////////////////////////////////////////
0030 template<typename Char>
0031 struct range
0032 {
0033     range(Char first, Char last);
0034
0035     bool is_valid() const;
0036     bool includes(Char v) const;
0037     bool includes(range const &r) const;
0038     bool overlaps(range const &r) const;
0039     void merge(range const &r);
0040
0041     Char first_;
0042     Char last_;
0043 };
0044
0045 //////////////////////////////////
0046 template<typename Char>
0047 struct range_compare
0048 {
0049     bool operator()(range<Char> const &x, range<Char> const &y) const
0050     {
0051         return x.first_ < y.first_;
0052     }
0053 };
0054
0055 ///////////////////////////////////////////////////////////////////////////
0056 //
0057 //  range_run
0058 //
0059 //      An implementation of a sparse bit (boolean) set. The set uses
0060 //      a sorted vector of disjoint ranges. This class implements the
0061 //      bare minimum essentials from which the full range of set
0062 //      operators can be implemented. The set is constructed from
0063 //      ranges. Internally, adjacent or overlapping ranges are
0064 //      coalesced.
0065 //
0066 //      range_runs are very space-economical in situations where there
0067 //      are lots of ranges and a few individual disjoint values.
0068 //      Searching is O(log n) where n is the number of ranges.
0069 //
0070 //      { Low level implementation detail }
0071 //
0072 ///////////////////////////////////////////////////////////////////////////
0073 template<typename Char>
0074 struct range_run
0075 {
0076     typedef range<Char> range_type;
0077     typedef std::vector<range_type> run_type;
0078     typedef typename run_type::iterator iterator;
0079     typedef typename run_type::const_iterator const_iterator;
0080
0081     void swap(range_run& rr);
0082     bool empty() const;
0083     bool test(Char v) const;
0084     template<typename Traits>
0085     bool test(Char v, Traits const &tr) const;
0086     void set(range_type const &r);
0087     void clear(range_type const &r);
0088     void clear();
0089
0090     const_iterator begin() const;
0091     const_iterator end() const;
0092
0093 private:
0094     void merge(iterator iter, range_type const &r);
0095
0096     run_type run_;
0097 };
0098
0099 }}} // namespace boost::xpressive::detail
0100
0101 #endif
0102