diff options
Diffstat (limited to '3rdParty/Boost/src/boost/spirit/home/classic/utility/impl/chset/range_run.hpp')
-rw-r--r-- | 3rdParty/Boost/src/boost/spirit/home/classic/utility/impl/chset/range_run.hpp | 127 |
1 files changed, 127 insertions, 0 deletions
diff --git a/3rdParty/Boost/src/boost/spirit/home/classic/utility/impl/chset/range_run.hpp b/3rdParty/Boost/src/boost/spirit/home/classic/utility/impl/chset/range_run.hpp new file mode 100644 index 0000000..579bcae --- /dev/null +++ b/3rdParty/Boost/src/boost/spirit/home/classic/utility/impl/chset/range_run.hpp @@ -0,0 +1,127 @@ +/*============================================================================= + Copyright (c) 2001-2003 Joel de Guzman + http://spirit.sourceforge.net/ + + Distributed under the Boost Software License, Version 1.0. (See accompanying + file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) +=============================================================================*/ +#ifndef BOOST_SPIRIT_RANGE_RUN_HPP +#define BOOST_SPIRIT_RANGE_RUN_HPP + +/////////////////////////////////////////////////////////////////////////////// +#include <vector> + +#include <boost/spirit/home/classic/namespace.hpp> + +/////////////////////////////////////////////////////////////////////////////// +namespace boost { namespace spirit { + +BOOST_SPIRIT_CLASSIC_NAMESPACE_BEGIN + +namespace utility { namespace impl { + + /////////////////////////////////////////////////////////////////////////// + // + // range class + // + // Implements a closed range of values. This class is used in + // the implementation of the range_run class. + // + // { Low level implementation detail } + // { Not to be confused with BOOST_SPIRIT_CLASSIC_NS::range } + // + /////////////////////////////////////////////////////////////////////////// + template <typename CharT> + struct range { + + range(CharT first, CharT last); + + bool is_valid() const; + bool includes(CharT v) const; + bool includes(range const& r) const; + bool overlaps(range const& r) const; + void merge(range const& r); + + CharT first; + CharT last; + }; + + ////////////////////////////////// + template <typename CharT> + struct range_char_compare { + + bool operator()(range<CharT> const& x, const CharT y) const + { return x.first < y; } + + bool operator()(const CharT x, range<CharT> const& y) const + { return x < y.first; } + + // This additional operator is required for the checked STL shipped + // with VC8 testing the ordering of the iterators passed to the + // std::lower_bound algo this range_char_compare<> predicate is passed + // to. + bool operator()(range<CharT> const& x, range<CharT> const& y) const + { return x.first < y.first; } + }; + + ////////////////////////////////// + template <typename CharT> + struct range_compare { + + bool operator()(range<CharT> const& x, range<CharT> const& y) const + { return x.first < y.first; } + }; + + /////////////////////////////////////////////////////////////////////////// + // + // range_run + // + // An implementation of a sparse bit (boolean) set. The set uses + // a sorted vector of disjoint ranges. This class implements the + // bare minimum essentials from which the full range of set + // operators can be implemented. The set is constructed from + // ranges. Internally, adjacent or overlapping ranges are + // coalesced. + // + // range_runs are very space-economical in situations where there + // are lots of ranges and a few individual disjoint values. + // Searching is O(log n) where n is the number of ranges. + // + // { Low level implementation detail } + // + /////////////////////////////////////////////////////////////////////////// + template <typename CharT> + class range_run { + + public: + + typedef range<CharT> range_t; + typedef std::vector<range_t> run_t; + typedef typename run_t::iterator iterator; + typedef typename run_t::const_iterator const_iterator; + + void swap(range_run& rr); + bool test(CharT v) const; + void set(range_t const& r); + void clear(range_t const& r); + void clear(); + + const_iterator begin() const; + const_iterator end() const; + + private: + + void merge(iterator iter, range_t const& r); + + run_t run; + }; + +}} + +BOOST_SPIRIT_CLASSIC_NAMESPACE_END + +}} // namespace BOOST_SPIRIT_CLASSIC_NS::utility::impl + +#endif + +#include <boost/spirit/home/classic/utility/impl/chset/range_run.ipp> |