1 /*=============================================================================
2 Copyright (c) 2001-2003 Joel de Guzman
3 http://spirit.sourceforge.net/
5 Use, modification and distribution is subject to the Boost Software
6 License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
7 http://www.boost.org/LICENSE_1_0.txt)
8 =============================================================================*/
9 #ifndef BOOST_XPRESSIVE_SPIRIT_RANGE_RUN_HPP_EAN_10_04_2005
10 #define BOOST_XPRESSIVE_SPIRIT_RANGE_RUN_HPP_EAN_10_04_2005
12 ///////////////////////////////////////////////////////////////////////////////
15 ///////////////////////////////////////////////////////////////////////////////
16 namespace boost { namespace xpressive { namespace detail
19 ///////////////////////////////////////////////////////////////////////////
23 // Implements a closed range of values. This class is used in
24 // the implementation of the range_run class.
26 // { Low level implementation detail }
27 // { Not to be confused with spirit::range }
29 ///////////////////////////////////////////////////////////////////////////
30 template<typename Char>
33 range(Char first, Char last);
35 bool is_valid() const;
36 bool includes(Char v) const;
37 bool includes(range const &r) const;
38 bool overlaps(range const &r) const;
39 void merge(range const &r);
45 //////////////////////////////////
46 template<typename Char>
49 bool operator()(range<Char> const &x, range<Char> const &y) const
51 return x.first_ < y.first_;
55 ///////////////////////////////////////////////////////////////////////////
59 // An implementation of a sparse bit (boolean) set. The set uses
60 // a sorted vector of disjoint ranges. This class implements the
61 // bare minimum essentials from which the full range of set
62 // operators can be implemented. The set is constructed from
63 // ranges. Internally, adjacent or overlapping ranges are
66 // range_runs are very space-economical in situations where there
67 // are lots of ranges and a few individual disjoint values.
68 // Searching is O(log n) where n is the number of ranges.
70 // { Low level implementation detail }
72 ///////////////////////////////////////////////////////////////////////////
73 template<typename Char>
76 typedef range<Char> range_type;
77 typedef std::vector<range_type> run_type;
78 typedef typename run_type::iterator iterator;
79 typedef typename run_type::const_iterator const_iterator;
81 void swap(range_run& rr);
83 bool test(Char v) const;
84 template<typename Traits>
85 bool test(Char v, Traits const &tr) const;
86 void set(range_type const &r);
87 void clear(range_type const &r);
90 const_iterator begin() const;
91 const_iterator end() const;
94 void merge(iterator iter, range_type const &r);
99 }}} // namespace boost::xpressive::detail