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///////////////////////////////////////////////////////////////////////////////
17namespace boost { namespace spirit {
18
19BOOST_SPIRIT_CLASSIC_NAMESPACE_BEGIN
20
21namespace 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
121BOOST_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>
128

source code of boost/libs/spirit/include/boost/spirit/home/classic/utility/impl/chset/range_run.hpp