]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | /*============================================================================= |
2 | Copyright (c) 2001-2003 Joel de Guzman | |
3 | http://spirit.sourceforge.net/ | |
4 | ||
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 | |
11 | ||
12 | /////////////////////////////////////////////////////////////////////////////// | |
13 | #include <vector> | |
14 | ||
15 | /////////////////////////////////////////////////////////////////////////////// | |
16 | namespace boost { namespace xpressive { namespace detail | |
17 | { | |
18 | ||
19 | /////////////////////////////////////////////////////////////////////////// | |
20 | // | |
21 | // range class | |
22 | // | |
23 | // Implements a closed range of values. This class is used in | |
24 | // the implementation of the range_run class. | |
25 | // | |
26 | // { Low level implementation detail } | |
27 | // { Not to be confused with spirit::range } | |
28 | // | |
29 | /////////////////////////////////////////////////////////////////////////// | |
30 | template<typename Char> | |
31 | struct range | |
32 | { | |
33 | range(Char first, Char last); | |
34 | ||
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); | |
40 | ||
41 | Char first_; | |
42 | Char last_; | |
43 | }; | |
44 | ||
45 | ////////////////////////////////// | |
46 | template<typename Char> | |
47 | struct range_compare | |
48 | { | |
49 | bool operator()(range<Char> const &x, range<Char> const &y) const | |
50 | { | |
51 | return x.first_ < y.first_; | |
52 | } | |
53 | }; | |
54 | ||
55 | /////////////////////////////////////////////////////////////////////////// | |
56 | // | |
57 | // range_run | |
58 | // | |
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 | |
64 | // coalesced. | |
65 | // | |
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. | |
69 | // | |
70 | // { Low level implementation detail } | |
71 | // | |
72 | /////////////////////////////////////////////////////////////////////////// | |
73 | template<typename Char> | |
74 | struct range_run | |
75 | { | |
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; | |
80 | ||
81 | void swap(range_run& rr); | |
82 | bool empty() const; | |
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); | |
88 | void clear(); | |
89 | ||
90 | const_iterator begin() const; | |
91 | const_iterator end() const; | |
92 | ||
93 | private: | |
94 | void merge(iterator iter, range_type const &r); | |
95 | ||
96 | run_type run_; | |
97 | }; | |
98 | ||
99 | }}} // namespace boost::xpressive::detail | |
100 | ||
101 | #endif | |
102 |