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 operator ()boost::spirit::utility::impl::range_char_compare53 bool operator()(range<CharT> const& x, const CharT y) const 54 { return x.first < y; } 55 operator ()boost::spirit::utility::impl::range_char_compare56 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. operator ()boost::spirit::utility::impl::range_char_compare63 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 operator ()boost::spirit::utility::impl::range_compare71 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> 128