]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | /*============================================================================= |
2 | Copyright (c) 2001-2003 Joel de Guzman | |
3 | http://spirit.sourceforge.net/ | |
4 | ||
5 | Distributed under the Boost Software License, Version 1.0. (See accompanying | |
6 | file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) | |
7 | =============================================================================*/ | |
8 | #ifndef BOOST_SPIRIT_RANGE_RUN_HPP | |
9 | #define BOOST_SPIRIT_RANGE_RUN_HPP | |
10 | ||
11 | /////////////////////////////////////////////////////////////////////////////// | |
12 | #include <vector> | |
13 | ||
14 | #include <boost/spirit/home/classic/namespace.hpp> | |
15 | ||
16 | /////////////////////////////////////////////////////////////////////////////// | |
17 | namespace boost { namespace spirit { | |
18 | ||
19 | BOOST_SPIRIT_CLASSIC_NAMESPACE_BEGIN | |
20 | ||
21 | namespace utility { namespace impl { | |
22 | ||
23 | /////////////////////////////////////////////////////////////////////////// | |
24 | // | |
25 | // range class | |
26 | // | |
27 | // Implements a closed range of values. This class is used in | |
28 | // the implementation of the range_run class. | |
29 | // | |
30 | // { Low level implementation detail } | |
31 | // { Not to be confused with BOOST_SPIRIT_CLASSIC_NS::range } | |
32 | // | |
33 | /////////////////////////////////////////////////////////////////////////// | |
34 | template <typename CharT> | |
35 | struct range { | |
36 | ||
37 | range(CharT first, CharT last); | |
38 | ||
39 | bool is_valid() const; | |
40 | bool includes(CharT v) const; | |
41 | bool includes(range const& r) const; | |
42 | bool overlaps(range const& r) const; | |
43 | void merge(range const& r); | |
44 | ||
45 | CharT first; | |
46 | CharT last; | |
47 | }; | |
48 | ||
49 | ////////////////////////////////// | |
50 | template <typename CharT> | |
51 | struct range_char_compare { | |
52 | ||
53 | bool operator()(range<CharT> const& x, const CharT y) const | |
54 | { return x.first < y; } | |
55 | ||
56 | bool operator()(const CharT x, range<CharT> const& y) const | |
57 | { return x < y.first; } | |
58 | ||
59 | // This additional operator is required for the checked STL shipped | |
60 | // with VC8 testing the ordering of the iterators passed to the | |
61 | // std::lower_bound algo this range_char_compare<> predicate is passed | |
62 | // to. | |
63 | bool operator()(range<CharT> const& x, range<CharT> const& y) const | |
64 | { return x.first < y.first; } | |
65 | }; | |
66 | ||
67 | ////////////////////////////////// | |
68 | template <typename CharT> | |
69 | struct range_compare { | |
70 | ||
71 | bool operator()(range<CharT> const& x, range<CharT> const& y) const | |
72 | { return x.first < y.first; } | |
73 | }; | |
74 | ||
75 | /////////////////////////////////////////////////////////////////////////// | |
76 | // | |
77 | // range_run | |
78 | // | |
79 | // An implementation of a sparse bit (boolean) set. The set uses | |
80 | // a sorted vector of disjoint ranges. This class implements the | |
81 | // bare minimum essentials from which the full range of set | |
82 | // operators can be implemented. The set is constructed from | |
83 | // ranges. Internally, adjacent or overlapping ranges are | |
84 | // coalesced. | |
85 | // | |
86 | // range_runs are very space-economical in situations where there | |
87 | // are lots of ranges and a few individual disjoint values. | |
88 | // Searching is O(log n) where n is the number of ranges. | |
89 | // | |
90 | // { Low level implementation detail } | |
91 | // | |
92 | /////////////////////////////////////////////////////////////////////////// | |
93 | template <typename CharT> | |
94 | class range_run { | |
95 | ||
96 | public: | |
97 | ||
98 | typedef range<CharT> range_t; | |
99 | typedef std::vector<range_t> run_t; | |
100 | typedef typename run_t::iterator iterator; | |
101 | typedef typename run_t::const_iterator const_iterator; | |
102 | ||
103 | void swap(range_run& rr); | |
104 | bool test(CharT v) const; | |
105 | void set(range_t const& r); | |
106 | void clear(range_t const& r); | |
107 | void clear(); | |
108 | ||
109 | const_iterator begin() const; | |
110 | const_iterator end() const; | |
111 | ||
112 | private: | |
113 | ||
114 | void merge(iterator iter, range_t const& r); | |
115 | ||
116 | run_t run; | |
117 | }; | |
118 | ||
119 | }} | |
120 | ||
121 | BOOST_SPIRIT_CLASSIC_NAMESPACE_END | |
122 | ||
123 | }} // namespace BOOST_SPIRIT_CLASSIC_NS::utility::impl | |
124 | ||
125 | #endif | |
126 | ||
127 | #include <boost/spirit/home/classic/utility/impl/chset/range_run.ipp> |