ceph/src/boost/libs/xpressive/include/boost/xpressive/detail/utility/chset/range_run.hpp

   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