ceph/src/boost/boost/spirit/home/classic/utility/impl/chset/range_run.hpp

   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>