diff options
Diffstat (limited to '3rdParty/Boost/src/boost/spirit/home/classic/utility/impl/chset')
4 files changed, 698 insertions, 0 deletions
diff --git a/3rdParty/Boost/src/boost/spirit/home/classic/utility/impl/chset/basic_chset.hpp b/3rdParty/Boost/src/boost/spirit/home/classic/utility/impl/chset/basic_chset.hpp new file mode 100644 index 0000000..ace6501 --- /dev/null +++ b/3rdParty/Boost/src/boost/spirit/home/classic/utility/impl/chset/basic_chset.hpp @@ -0,0 +1,107 @@ +/*============================================================================= + Copyright (c) 2001-2003 Joel de Guzman + Copyright (c) 2001-2003 Daniel Nuffer + 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_BASIC_CHSET_HPP +#define BOOST_SPIRIT_BASIC_CHSET_HPP + +/////////////////////////////////////////////////////////////////////////////// +#include <bitset> +#include <climits> +#include <boost/spirit/home/classic/utility/impl/chset/range_run.hpp> +#include <boost/spirit/home/classic/namespace.hpp> + +namespace boost { namespace spirit { + +BOOST_SPIRIT_CLASSIC_NAMESPACE_BEGIN + + /////////////////////////////////////////////////////////////////////////// + // + // basic_chset: basic character set implementation using range_run + // + /////////////////////////////////////////////////////////////////////////// + template <typename CharT> + class basic_chset + { + public: + basic_chset(); + basic_chset(basic_chset const& arg_); + + bool test(CharT v) const; + void set(CharT from, CharT to); + void set(CharT c); + void clear(CharT from, CharT to); + void clear(CharT c); + void clear(); + + void inverse(); + void swap(basic_chset& x); + + basic_chset& operator|=(basic_chset const& x); + basic_chset& operator&=(basic_chset const& x); + basic_chset& operator-=(basic_chset const& x); + basic_chset& operator^=(basic_chset const& x); + + private: utility::impl::range_run<CharT> rr; + }; + + #if (CHAR_BIT == 8) + + /////////////////////////////////////////////////////////////////////////// + // + // basic_chset: specializations for 8 bit chars using std::bitset + // + /////////////////////////////////////////////////////////////////////////// + template <typename CharT> + class basic_chset_8bit { + + public: + basic_chset_8bit(); + basic_chset_8bit(basic_chset_8bit const& arg_); + + bool test(CharT v) const; + void set(CharT from, CharT to); + void set(CharT c); + void clear(CharT from, CharT to); + void clear(CharT c); + void clear(); + + void inverse(); + void swap(basic_chset_8bit& x); + + basic_chset_8bit& operator|=(basic_chset_8bit const& x); + basic_chset_8bit& operator&=(basic_chset_8bit const& x); + basic_chset_8bit& operator-=(basic_chset_8bit const& x); + basic_chset_8bit& operator^=(basic_chset_8bit const& x); + + private: std::bitset<256> bset; + }; + + ///////////////////////////////// + template <> + class basic_chset<char> + : public basic_chset_8bit<char> {}; + + ///////////////////////////////// + template <> + class basic_chset<signed char> + : public basic_chset_8bit<signed char> {}; + + ///////////////////////////////// + template <> + class basic_chset<unsigned char> + : public basic_chset_8bit<unsigned char> {}; + +#endif + +BOOST_SPIRIT_CLASSIC_NAMESPACE_END + +}} // namespace BOOST_SPIRIT_CLASSIC_NS + +#endif + +#include <boost/spirit/home/classic/utility/impl/chset/basic_chset.ipp> diff --git a/3rdParty/Boost/src/boost/spirit/home/classic/utility/impl/chset/basic_chset.ipp b/3rdParty/Boost/src/boost/spirit/home/classic/utility/impl/chset/basic_chset.ipp new file mode 100644 index 0000000..e7d9272 --- /dev/null +++ b/3rdParty/Boost/src/boost/spirit/home/classic/utility/impl/chset/basic_chset.ipp @@ -0,0 +1,246 @@ +/*============================================================================= + Copyright (c) 2001-2003 Joel de Guzman + Copyright (c) 2001-2003 Daniel Nuffer + http://spirit.sourceforge.net/ + + Use, modification and distribution is subject to 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_BASIC_CHSET_IPP +#define BOOST_SPIRIT_BASIC_CHSET_IPP + +/////////////////////////////////////////////////////////////////////////////// +#include <bitset> +#include <boost/spirit/home/classic/utility/impl/chset/basic_chset.hpp> + +/////////////////////////////////////////////////////////////////////////////// +namespace boost { namespace spirit { + +BOOST_SPIRIT_CLASSIC_NAMESPACE_BEGIN + +/////////////////////////////////////////////////////////////////////////////// +// +// basic_chset: character set implementation +// +/////////////////////////////////////////////////////////////////////////////// +template <typename CharT> +inline basic_chset<CharT>::basic_chset() {} + +////////////////////////////////// +template <typename CharT> +inline basic_chset<CharT>::basic_chset(basic_chset const& arg_) +: rr(arg_.rr) {} + +////////////////////////////////// +template <typename CharT> +inline bool +basic_chset<CharT>::test(CharT v) const +{ return rr.test(v); } + +////////////////////////////////// +template <typename CharT> +inline void +basic_chset<CharT>::set(CharT from, CharT to) +{ rr.set(utility::impl::range<CharT>(from, to)); } + +////////////////////////////////// +template <typename CharT> +inline void +basic_chset<CharT>::set(CharT c) +{ rr.set(utility::impl::range<CharT>(c, c)); } + +////////////////////////////////// +template <typename CharT> +inline void +basic_chset<CharT>::clear(CharT from, CharT to) +{ rr.clear(utility::impl::range<CharT>(from, to)); } + +////////////////////////////////// +template <typename CharT> +inline void +basic_chset<CharT>::clear() +{ rr.clear(); } + +///////////////////////////////// +template <typename CharT> +inline void +basic_chset<CharT>::inverse() +{ + basic_chset inv; + inv.set( + (std::numeric_limits<CharT>::min)(), + (std::numeric_limits<CharT>::max)() + ); + inv -= *this; + swap(inv); +} + +///////////////////////////////// +template <typename CharT> +inline void +basic_chset<CharT>::swap(basic_chset& x) +{ rr.swap(x.rr); } + +///////////////////////////////// +template <typename CharT> +inline basic_chset<CharT>& +basic_chset<CharT>::operator|=(basic_chset<CharT> const& x) +{ + typedef typename utility::impl::range_run<CharT>::const_iterator const_iterator; + for (const_iterator iter = x.rr.begin(); iter != x.rr.end(); ++iter) + rr.set(*iter); + return *this; +} + +///////////////////////////////// +template <typename CharT> +inline basic_chset<CharT>& +basic_chset<CharT>::operator&=(basic_chset<CharT> const& x) +{ + basic_chset inv; + inv.set( + (std::numeric_limits<CharT>::min)(), + (std::numeric_limits<CharT>::max)() + ); + inv -= x; + *this -= inv; + return *this; +} + +///////////////////////////////// +template <typename CharT> +inline basic_chset<CharT>& +basic_chset<CharT>::operator-=(basic_chset<CharT> const& x) +{ + typedef typename utility::impl::range_run<CharT>::const_iterator const_iterator; + for (const_iterator iter = x.rr.begin(); iter != x.rr.end(); ++iter) + rr.clear(*iter); + return *this; +} + +///////////////////////////////// +template <typename CharT> +inline basic_chset<CharT>& +basic_chset<CharT>::operator^=(basic_chset<CharT> const& x) +{ + basic_chset bma = x; + bma -= *this; + *this -= x; + *this |= bma; + return *this; +} + +#if (CHAR_BIT == 8) + +/////////////////////////////////////////////////////////////////////////////// +// +// basic_chset: specializations for 8 bit chars using std::bitset +// +/////////////////////////////////////////////////////////////////////////////// +template <typename CharT> +inline basic_chset_8bit<CharT>::basic_chset_8bit() {} + +///////////////////////////////// +template <typename CharT> +inline basic_chset_8bit<CharT>::basic_chset_8bit(basic_chset_8bit const& arg_) +: bset(arg_.bset) {} + +///////////////////////////////// +template <typename CharT> +inline bool +basic_chset_8bit<CharT>::test(CharT v) const +{ return bset.test((unsigned char)v); } + +///////////////////////////////// +template <typename CharT> +inline void +basic_chset_8bit<CharT>::set(CharT from, CharT to) +{ + for (int i = from; i <= to; ++i) + bset.set((unsigned char)i); +} + +///////////////////////////////// +template <typename CharT> +inline void +basic_chset_8bit<CharT>::set(CharT c) +{ bset.set((unsigned char)c); } + +///////////////////////////////// +template <typename CharT> +inline void +basic_chset_8bit<CharT>::clear(CharT from, CharT to) +{ + for (int i = from; i <= to; ++i) + bset.reset((unsigned char)i); +} + +///////////////////////////////// +template <typename CharT> +inline void +basic_chset_8bit<CharT>::clear(CharT c) +{ bset.reset((unsigned char)c); } + +///////////////////////////////// +template <typename CharT> +inline void +basic_chset_8bit<CharT>::clear() +{ bset.reset(); } + +///////////////////////////////// +template <typename CharT> +inline void +basic_chset_8bit<CharT>::inverse() +{ bset.flip(); } + +///////////////////////////////// +template <typename CharT> +inline void +basic_chset_8bit<CharT>::swap(basic_chset_8bit& x) +{ std::swap(bset, x.bset); } + +///////////////////////////////// +template <typename CharT> +inline basic_chset_8bit<CharT>& +basic_chset_8bit<CharT>::operator|=(basic_chset_8bit const& x) +{ + bset |= x.bset; + return *this; +} + +///////////////////////////////// +template <typename CharT> +inline basic_chset_8bit<CharT>& +basic_chset_8bit<CharT>::operator&=(basic_chset_8bit const& x) +{ + bset &= x.bset; + return *this; +} + +///////////////////////////////// +template <typename CharT> +inline basic_chset_8bit<CharT>& +basic_chset_8bit<CharT>::operator-=(basic_chset_8bit const& x) +{ + bset &= ~x.bset; + return *this; +} + +///////////////////////////////// +template <typename CharT> +inline basic_chset_8bit<CharT>& +basic_chset_8bit<CharT>::operator^=(basic_chset_8bit const& x) +{ + bset ^= x.bset; + return *this; +} + +#endif + +BOOST_SPIRIT_CLASSIC_NAMESPACE_END + +}} // namespace boost::spirit + +#endif + 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> diff --git a/3rdParty/Boost/src/boost/spirit/home/classic/utility/impl/chset/range_run.ipp b/3rdParty/Boost/src/boost/spirit/home/classic/utility/impl/chset/range_run.ipp new file mode 100644 index 0000000..ede1567 --- /dev/null +++ b/3rdParty/Boost/src/boost/spirit/home/classic/utility/impl/chset/range_run.ipp @@ -0,0 +1,218 @@ +/*============================================================================= + Copyright (c) 2001-2003 Joel de Guzman + http://spirit.sourceforge.net/ + + Use, modification and distribution is subject to 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_IPP +#define BOOST_SPIRIT_RANGE_RUN_IPP + +/////////////////////////////////////////////////////////////////////////////// +#include <algorithm> // for std::lower_bound +#include <boost/spirit/home/classic/core/assert.hpp> // for BOOST_SPIRIT_ASSERT +#include <boost/spirit/home/classic/utility/impl/chset/range_run.hpp> +#include <boost/spirit/home/classic/debug.hpp> +#include <boost/limits.hpp> + +/////////////////////////////////////////////////////////////////////////////// +namespace boost { namespace spirit { + +BOOST_SPIRIT_CLASSIC_NAMESPACE_BEGIN + + namespace utility { namespace impl { + + /////////////////////////////////////////////////////////////////////// + // + // range class implementation + // + /////////////////////////////////////////////////////////////////////// + template <typename CharT> + inline range<CharT>::range(CharT first_, CharT last_) + : first(first_), last(last_) {} + + ////////////////////////////////// + template <typename CharT> + inline bool + range<CharT>::is_valid() const + { return first <= last; } + + ////////////////////////////////// + template <typename CharT> + inline bool + range<CharT>::includes(range const& r) const + { return (first <= r.first) && (last >= r.last); } + + ////////////////////////////////// + template <typename CharT> + inline bool + range<CharT>::includes(CharT v) const + { return (first <= v) && (last >= v); } + + ////////////////////////////////// + template <typename CharT> + inline bool + range<CharT>::overlaps(range const& r) const + { + CharT decr_first = + first == (std::numeric_limits<CharT>::min)() ? first : first-1; + CharT incr_last = + last == (std::numeric_limits<CharT>::max)() ? last : last+1; + + return (decr_first <= r.last) && (incr_last >= r.first); + } + + ////////////////////////////////// + template <typename CharT> + inline void + range<CharT>::merge(range const& r) + { + first = (std::min)(first, r.first); + last = (std::max)(last, r.last); + } + + /////////////////////////////////////////////////////////////////////// + // + // range_run class implementation + // + /////////////////////////////////////////////////////////////////////// + template <typename CharT> + inline bool + range_run<CharT>::test(CharT v) const + { + if (!run.empty()) + { + const_iterator iter = + std::lower_bound( + run.begin(), run.end(), v, + range_char_compare<CharT>() + ); + + if (iter != run.end() && iter->includes(v)) + return true; + if (iter != run.begin()) + return (--iter)->includes(v); + } + return false; + } + + ////////////////////////////////// + template <typename CharT> + inline void + range_run<CharT>::swap(range_run& rr) + { run.swap(rr.run); } + + ////////////////////////////////// + template <typename CharT> + void + range_run<CharT>::merge(iterator iter, range<CharT> const& r) + { + iter->merge(r); + iterator i = iter + 1; + + while (i != run.end() && iter->overlaps(*i)) + iter->merge(*i++); + + run.erase(iter+1, i); + } + + ////////////////////////////////// + template <typename CharT> + void + range_run<CharT>::set(range<CharT> const& r) + { + BOOST_SPIRIT_ASSERT(r.is_valid()); + if (!run.empty()) + { + iterator iter = + std::lower_bound( + run.begin(), run.end(), r, + range_compare<CharT>() + ); + + if ((iter != run.end() && iter->includes(r)) || + ((iter != run.begin()) && (iter - 1)->includes(r))) + return; + + if (iter != run.begin() && (iter - 1)->overlaps(r)) + merge(--iter, r); + + else if (iter != run.end() && iter->overlaps(r)) + merge(iter, r); + + else + run.insert(iter, r); + } + else + { + run.push_back(r); + } + } + + ////////////////////////////////// + template <typename CharT> + void + range_run<CharT>::clear(range<CharT> const& r) + { + BOOST_SPIRIT_ASSERT(r.is_valid()); + if (!run.empty()) + { + iterator iter = + std::lower_bound( + run.begin(), run.end(), r, + range_compare<CharT>() + ); + + iterator left_iter; + + if ((iter != run.begin()) && + (left_iter = (iter - 1))->includes(r.first)) + { + if (left_iter->last > r.last) + { + CharT save_last = left_iter->last; + left_iter->last = r.first-1; + run.insert(iter, range<CharT>(r.last+1, save_last)); + return; + } + else + { + left_iter->last = r.first-1; + } + } + + iterator i = iter; + while (i != run.end() && r.includes(*i)) + i++; + if (i != run.end() && i->includes(r.last)) + i->first = r.last+1; + run.erase(iter, i); + } + } + + ////////////////////////////////// + template <typename CharT> + inline void + range_run<CharT>::clear() + { run.clear(); } + + ////////////////////////////////// + template <typename CharT> + inline typename range_run<CharT>::const_iterator + range_run<CharT>::begin() const + { return run.begin(); } + + ////////////////////////////////// + template <typename CharT> + inline typename range_run<CharT>::const_iterator + range_run<CharT>::end() const + { return run.end(); } + + }} // namespace utility::impl + +BOOST_SPIRIT_CLASSIC_NAMESPACE_END + +}} // namespace boost::spirit + +#endif |