support/char_set/range_run.hpp

0001 /*=============================================================================
0002     Copyright (c) 2001-2011 Joel de Guzman
0003
0004     Distributed under the Boost Software License, Version 1.0. (See accompanying
0005     file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
0006 ==============================================================================*/
0007 #if !defined(BOOST_SPIRIT_RANGE_RUN_MAY_16_2006_0801_PM)
0008 #define BOOST_SPIRIT_RANGE_RUN_MAY_16_2006_0801_PM
0009
0010 #if defined(_MSC_VER)
0011 #pragma once
0012 #endif
0013
0014 #include <boost/spirit/home/support/char_set/range.hpp>
0015 #include <vector>
0016
0017 namespace boost { namespace spirit { namespace support { namespace detail
0018 {
0019     ///////////////////////////////////////////////////////////////////////////
0020     //  range_run
0021     //
0022     //      An implementation of a sparse bit (boolean) set. The set uses
0023     //      a sorted vector of disjoint ranges. This class implements the
0024     //      bare minimum essentials from which the full range of set
0025     //      operators can be implemented. The set is constructed from
0026     //      ranges. Internally, adjacent or overlapping ranges are
0027     //      coalesced.
0028     //
0029     //      range_runs are very space-economical in situations where there
0030     //      are lots of ranges and a few individual disjoint values.
0031     //      Searching is O(log n) where n is the number of ranges.
0032     //
0033     //      { Low level interface }
0034     ///////////////////////////////////////////////////////////////////////////
0035     template <typename Char>
0036     class range_run
0037     {
0038     public:
0039
0040         typedef range<Char> range_type;
0041         typedef std::vector<range_type> storage_type;
0042
0043         void swap(range_run& other);
0044         bool test(Char v) const;
0045         void set(range_type const& range);
0046         void clear(range_type const& range);
0047         void clear();
0048
0049     private:
0050
0051         storage_type run;
0052     };
0053 }}}}
0054
0055 #include <boost/spirit/home/support/char_set/range_run_impl.hpp>
0056 #endif