[Boost-commit] svn:boost r55534 - in trunk/boost/spirit: home/karma/char home/qi/char home/qi/char/detail home/support/char_set include

Subject: [Boost-commit] svn:boost r55534 - in trunk/boost/spirit: home/karma/char home/qi/char home/qi/char/detail home/support/char_set include
From: hartmut.kaiser_at_[hidden]
Date: 2009-08-11 23:07:40

Author: hkaiser
Date: 2009-08-11 23:07:38 EDT (Tue, 11 Aug 2009)
New Revision: 55534
URL: http://svn.boost.org/trac/boost/changeset/55534

Log:
Spirit: added character range and character set generators
Added:
   trunk/boost/spirit/home/support/char_set/
   trunk/boost/spirit/home/support/char_set/basic_chset.hpp   (contents, props changed)
   trunk/boost/spirit/home/support/char_set/range.hpp   (contents, props changed)
   trunk/boost/spirit/home/support/char_set/range_functions.hpp   (contents, props changed)
   trunk/boost/spirit/home/support/char_set/range_run.hpp   (contents, props changed)
   trunk/boost/spirit/home/support/char_set/range_run_impl.hpp   (contents, props changed)
   trunk/boost/spirit/include/karma_char_.hpp   (contents, props changed)
Removed:
   trunk/boost/spirit/home/qi/char/detail/
Text files modified: 
   trunk/boost/spirit/home/karma/char/char.hpp       |   200 +++++++++++++++++++++++++++++++++++++-- 
   trunk/boost/spirit/home/karma/char/char_class.hpp |     4                                         
   trunk/boost/spirit/home/qi/char/char.hpp          |     6                                         
   3 files changed, 192 insertions(+), 18 deletions(-)

Modified: trunk/boost/spirit/home/karma/char/char.hpp
==============================================================================
--- trunk/boost/spirit/home/karma/char/char.hpp	(original)
+++ trunk/boost/spirit/home/karma/char/char.hpp	2009-08-11 23:07:38 EDT (Tue, 11 Aug 2009)
@@ -15,6 +15,7 @@
 #include <boost/spirit/home/support/info.hpp>
 #include <boost/spirit/home/support/char_class.hpp>
 #include <boost/spirit/home/support/detail/get_encoding.hpp>
+#include <boost/spirit/home/support/char_set/basic_chset.hpp>
 #include <boost/spirit/home/karma/domain.hpp>
 #include <boost/spirit/home/karma/meta_compiler.hpp>
 #include <boost/spirit/home/karma/delimit_out.hpp>
@@ -48,6 +49,14 @@
         >
     > : mpl::true_ {};
 
+    template <typename CharEncoding, typename A0, typename A1>
+    struct use_terminal<karma::domain
+      , terminal_ex<
+            tag::char_code<tag::char_, CharEncoding>    // enables char_('a','z')
+          , fusion::vector2<A0, A1>
+        >
+    > : mpl::true_ {};
+
     template <typename CharEncoding>                    // enables *lazy* char_('x'), char_("x")
     struct use_lazy_terminal<
         karma::domain
@@ -106,9 +115,8 @@
         static bool generate(OutputIterator& sink, Context&, Delimiter const& d
           , Attribute const& attr)
         {
-            return 
-                karma::detail::generate_to(sink, attr, char_encoding(), Tag()) &&
-                karma::delimit_out(sink, d);       // always do post-delimiting
+            return karma::detail::generate_to(sink, attr, char_encoding(), Tag()) &&
+                   karma::delimit_out(sink, d);       // always do post-delimiting
         }
 
         // any_char has no attribute attached, it needs to have been
@@ -192,6 +200,144 @@
     };
 
     ///////////////////////////////////////////////////////////////////////////
+    // char range generator
+    template <typename CharEncoding, typename Tag>
+    struct char_range
+      : primitive_generator<char_range<CharEncoding, Tag> >
+    {
+        typedef typename CharEncoding::char_type char_type;
+        typedef CharEncoding char_encoding;
+
+        char_range(char_type from, char_type to)
+          : from(spirit::char_class::convert<char_encoding>::to(Tag(), from))
+          , to(spirit::char_class::convert<char_encoding>::to(Tag(), to)) 
+        {}
+
+        // A char_('a', 'z') which has an associated attribute emits it only if 
+        // it matches the character range, otherwise it fails.
+        template <
+            typename OutputIterator, typename Context, typename Delimiter
+          , typename Attribute>
+        bool generate(OutputIterator& sink, Context&, Delimiter const& d
+          , Attribute const& attr) const
+        {
+            // fail if attribute doesn't belong to character range
+            if ((char_type(attr) < from) || (to < char_type(attr)))
+                return false;
+
+            return karma::detail::generate_to(sink, attr) &&
+                   karma::delimit_out(sink, d);    // always do post-delimiting
+        }
+
+        // A char_('a', 'z') without any associated attribute fails compiling
+        template <typename OutputIterator, typename Context, typename Delimiter>
+        bool generate(OutputIterator&, Context&, Delimiter const&
+          , unused_type) const
+        {
+            BOOST_SPIRIT_ASSERT_MSG(false
+              , char_range_not_usable_without_attribute, ());
+            return false;
+        }
+
+        template <typename CharParam, typename Context>
+        bool test(CharParam ch, Context&) const
+        {
+            return !(char_type(ch) < from) && !(to < char_type(ch));
+        }
+
+        template <typename Context>
+        info what(Context& /*context*/) const
+        {
+            info result("char-range", char_encoding::toucs4(from));
+            boost::get<std::string&>(result.value) += '-';
+            boost::get<std::string&>(result.value) += to_utf8(char_encoding::toucs4(to));
+            return result;
+        }
+
+        char_type from, to;
+    };
+
+    ///////////////////////////////////////////////////////////////////////////
+    // character set generator
+    template <typename CharEncoding, typename Tag>
+    struct char_set
+      : primitive_generator<char_set<CharEncoding, Tag> >
+    {
+        typedef typename CharEncoding::char_type char_type;
+        typedef CharEncoding char_encoding;
+
+        template <typename String>
+        char_set(String const& str)
+        {
+            typedef typename traits::char_type_of<String>::type in_type;
+
+            BOOST_SPIRIT_ASSERT_MSG((
+                (sizeof(char_type) == sizeof(in_type))
+            ), cannot_convert_string, (String));
+
+            typedef spirit::char_class::convert<char_encoding> convert_type;
+
+            char_type const* definition =
+                (char_type const*)traits::get_c_string(str);
+            char_type ch = convert_type::to(Tag(), *definition++);
+            while (ch)
+            {
+                char_type next = convert_type::to(Tag(), *definition++);
+                if (next == '-')
+                {
+                    next = convert_type::to(Tag(), *definition++);
+                    if (next == 0)
+                    {
+                        chset.set(ch);
+                        chset.set('-');
+                        break;
+                    }
+                    chset.set(ch, next);
+                }
+                else
+                {
+                    chset.set(ch);
+                }
+                ch = next;
+            }
+        }
+
+        // A char_("a-z") which has an associated attribute emits it only if 
+        // it matches the character set, otherwise it fails.
+        template <
+            typename OutputIterator, typename Context, typename Delimiter
+          , typename Attribute>
+        bool generate(OutputIterator& sink, Context&, Delimiter const& d
+          , Attribute const& attr) const
+        {
+            // fail if attribute doesn't belong to character set
+            if (!chset.test(char_type(attr)))
+                return false;
+
+            return karma::detail::generate_to(sink, attr) &&
+                   karma::delimit_out(sink, d);    // always do post-delimiting
+        }
+
+        // A char_("a-z") without any associated attribute fails compiling
+        template <typename OutputIterator, typename Context, typename Delimiter>
+        bool generate(OutputIterator&, Context&, Delimiter const&
+          , unused_type) const
+        {
+            BOOST_SPIRIT_ASSERT_MSG(false
+              , char_set_not_usable_without_attribute, ());
+            return false;
+        }
+
+        template <typename Context>
+        info what(Context& /*context*/) const
+        {
+            return info("char-set");
+        }
+
+        support::detail::basic_chset<char_type> chset;
+    };
+
+    ///////////////////////////////////////////////////////////////////////////
     // Generator generators: make_xxx function (objects)
     ///////////////////////////////////////////////////////////////////////////
     namespace detail
@@ -201,7 +347,6 @@
         {
             static bool const lower =
                 has_modifier<Modifiers, tag::char_code_base<tag::lower> >::value;
-
             static bool const upper =
                 has_modifier<Modifiers, tag::char_code_base<tag::upper> >::value;
 
@@ -250,7 +395,6 @@
     {
         static bool const lower =
             has_modifier<Modifiers, tag::char_code<tag::lower, CharEncoding> >::value;
-
         static bool const upper =
             has_modifier<Modifiers, tag::char_code<tag::upper, CharEncoding> >::value;
 
@@ -277,16 +421,19 @@
     {
         static bool const lower =
             has_modifier<Modifiers, tag::char_code<tag::lower, CharEncoding> >::value;
-
         static bool const upper =
             has_modifier<Modifiers, tag::char_code<tag::upper, CharEncoding> >::value;
 
-        typedef literal_char<
-            typename spirit::detail::get_encoding<
-                Modifiers, CharEncoding, lower || upper>::type
-          , typename detail::get_casetag<Modifiers, lower || upper>::type
-          , false
-        > result_type;
+        typedef typename spirit::detail::get_encoding<
+            Modifiers, CharEncoding, lower || upper>::type encoding;
+        typedef typename detail::get_casetag<
+            Modifiers, lower || upper>::type tag;
+
+        typedef typename mpl::if_<
+            traits::is_string<A0>
+          , char_set<encoding, tag>
+          , literal_char<encoding, tag, false>
+        >::type result_type;
 
         template <typename Terminal>
         result_type operator()(Terminal const& term, unused_type) const
@@ -306,7 +453,6 @@
     {
         static bool const lower =
             has_modifier<Modifiers, tag::char_code<tag::lower, CharEncoding> >::value;
-
         static bool const upper =
             has_modifier<Modifiers, tag::char_code<tag::upper, CharEncoding> >::value;
 
@@ -324,6 +470,34 @@
         }
     };
 
+    // char_('a', 'z')
+    template <typename CharEncoding, typename Modifiers, typename A0, typename A1>
+    struct make_primitive<
+        terminal_ex<
+            tag::char_code<tag::char_, CharEncoding>
+          , fusion::vector2<A0, A1>
+        >
+      , Modifiers>
+    {
+        static bool const lower =
+            has_modifier<Modifiers, tag::char_code<tag::lower, CharEncoding> >::value;
+        static bool const upper =
+            has_modifier<Modifiers, tag::char_code<tag::upper, CharEncoding> >::value;
+
+        typedef char_range<
+            typename spirit::detail::get_encoding<
+                Modifiers, CharEncoding, lower || upper>::type
+          , typename detail::get_casetag<Modifiers, lower || upper>::type
+        > result_type;
+
+        template <typename Terminal>
+        result_type operator()(Terminal const& term, unused_type) const
+        {
+            return result_type(fusion::at_c<0>(term.args)
+              , fusion::at_c<1>(term.args));
+        }
+    };
+
 }}}   // namespace boost::spirit::karma
 
 #endif

Modified: trunk/boost/spirit/home/karma/char/char_class.hpp
==============================================================================
--- trunk/boost/spirit/home/karma/char/char_class.hpp	(original)
+++ trunk/boost/spirit/home/karma/char/char_class.hpp	2009-08-11 23:07:38 EDT (Tue, 11 Aug 2009)
@@ -77,8 +77,8 @@
 
         // char_class shouldn't be used without any associated attribute
         template <typename OutputIterator, typename Context, typename Delimiter>
-        static bool generate(OutputIterator& sink, Context&, Delimiter const& d, 
-            unused_type const&)
+        static bool generate(OutputIterator&, Context&, Delimiter const&
+          , unused_type const&)
         {
             BOOST_SPIRIT_ASSERT_MSG(false
               , char_class_not_usable_without_attribute, ());

Modified: trunk/boost/spirit/home/qi/char/char.hpp
==============================================================================
--- trunk/boost/spirit/home/qi/char/char.hpp	(original)
+++ trunk/boost/spirit/home/qi/char/char.hpp	2009-08-11 23:07:38 EDT (Tue, 11 Aug 2009)
@@ -15,9 +15,9 @@
 #include <boost/spirit/home/support/string_traits.hpp>
 #include <boost/spirit/home/support/info.hpp>
 #include <boost/spirit/home/support/detail/get_encoding.hpp>
+#include <boost/spirit/home/support/char_set/basic_chset.hpp>
 #include <boost/spirit/home/qi/char/char_parser.hpp>
 #include <boost/spirit/home/qi/char/char_class.hpp>
-#include <boost/spirit/home/qi/char/detail/basic_chset.hpp>
 #include <boost/spirit/home/qi/meta_compiler.hpp>
 #include <boost/spirit/home/qi/auxiliary/lazy.hpp>
 #include <boost/fusion/include/at.hpp>
@@ -291,7 +291,7 @@
             return info("char-set");
         }
 
-        detail::basic_chset<char_type> chset;
+        support::detail::basic_chset<char_type> chset;
     };
 
     template <typename CharEncoding>
@@ -350,7 +350,7 @@
             return info("no-case-char-set");
         }
 
-        detail::basic_chset<char_type> chset;
+        support::detail::basic_chset<char_type> chset;
     };
 
     ///////////////////////////////////////////////////////////////////////////

Added: trunk/boost/spirit/home/support/char_set/basic_chset.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/spirit/home/support/char_set/basic_chset.hpp	2009-08-11 23:07:38 EDT (Tue, 11 Aug 2009)
@@ -0,0 +1,249 @@
+/*=============================================================================
+    Copyright (c) 2001-2009 Joel de Guzman
+    Copyright (c) 2001-2009 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_APRIL_17_2008
+#define BOOST_SPIRIT_BASIC_CHSET_APRIL_17_2008
+
+#if defined(_MSC_VER)
+#pragma once
+#endif
+
+///////////////////////////////////////////////////////////////////////////////
+#include <bitset>
+#include <climits> 
+#include <boost/spirit/home/support/char_set/range_run.hpp>
+
+namespace boost { namespace spirit { namespace support { namespace detail
+{
+    ///////////////////////////////////////////////////////////////////////////
+    //
+    //  basic_chset: basic character set implementation using range_run
+    //
+    ///////////////////////////////////////////////////////////////////////////
+    template <typename Char>
+    struct basic_chset
+    {
+        basic_chset() {}
+        basic_chset(basic_chset const& arg_)
+          : rr(arg_.rr) {}
+
+        bool
+        test(Char v) const
+        {
+            return rr.test(v);
+        }
+
+        void
+        set(Char from, Char to)
+        {
+            rr.set(range<Char>(from, to));
+        }
+
+        void
+        set(Char c)
+        {
+            rr.set(range<Char>(c, c));
+        }
+
+        void
+        clear(Char from, Char to)
+        {
+            rr.clear(range<Char>(from, to));
+        }
+
+        void
+        clear(Char c)
+        {
+            rr.clear(range<Char>(c, c));
+        }
+
+        void
+        clear()
+        {
+            rr.clear();
+        }
+
+        void
+        inverse()
+        {
+            basic_chset inv;
+            inv.set(
+                (std::numeric_limits<Char>::min)(),
+                (std::numeric_limits<Char>::max)()
+            );
+            inv -= *this;
+            swap(inv);
+        }
+
+        void
+        swap(basic_chset& x)
+        {
+            rr.swap(x.rr);
+        }
+
+
+        basic_chset&
+        operator|=(basic_chset const& x)
+        {
+            typedef typename range_run<Char>::const_iterator const_iterator;
+            for (const_iterator iter = x.rr.begin(); iter != x.rr.end(); ++iter)
+                rr.set(*iter);
+            return *this;
+        }
+
+        basic_chset&
+        operator&=(basic_chset const& x)
+        {
+            basic_chset inv;
+            inv.set(
+                (std::numeric_limits<Char>::min)(),
+                (std::numeric_limits<Char>::max)()
+            );
+            inv -= x;
+            *this -= inv;
+            return *this;
+        }
+
+        basic_chset&
+        operator-=(basic_chset const& x)
+        {
+            typedef typename range_run<Char>::const_iterator const_iterator;
+            for (const_iterator iter = x.rr.begin(); iter != x.rr.end(); ++iter)
+                rr.clear(*iter);
+            return *this;
+        }
+
+        basic_chset&
+        operator^=(basic_chset const& x)
+        {
+            basic_chset bma = x;
+            bma -= *this;
+            *this -= x;
+            *this |= bma;
+            return *this;
+        }
+
+        private: range_run<Char> rr;
+    };
+
+#if (CHAR_BIT == 8)
+
+    ///////////////////////////////////////////////////////////////////////////
+    //
+    //  basic_chset: specializations for 8 bit chars using std::bitset
+    //
+    ///////////////////////////////////////////////////////////////////////////
+    template <typename Char>
+    struct basic_chset_8bit
+    {
+        basic_chset_8bit() {}
+        basic_chset_8bit(basic_chset_8bit const& arg_)
+          : bset(arg_.bset) {}
+
+        bool
+        test(Char v) const
+        {
+            return bset.test((unsigned char)v);
+        }
+
+        void
+        set(Char from, Char to)
+        {
+            for (int i = from; i <= to; ++i)
+                bset.set((unsigned char)i);
+        }
+
+        void
+        set(Char c)
+        {
+            bset.set((unsigned char)c);
+        }
+
+        void
+        clear(Char from, Char to)
+        {
+            for (int i = from; i <= to; ++i)
+                bset.reset((unsigned char)i);
+        }
+
+        void
+        clear(Char c)
+        {
+            bset.reset((unsigned char)c);
+        }
+
+        void
+        clear()
+        {
+            bset.reset();
+        }
+
+        void
+        inverse()
+        {
+            bset.flip();
+        }
+
+        void
+        swap(basic_chset_8bit& x)
+        {
+            std::swap(bset, x.bset);
+        }
+
+        basic_chset_8bit&
+        operator|=(basic_chset_8bit const& x)
+        {
+            bset |= x.bset;
+            return *this;
+        }
+
+        basic_chset_8bit&
+        operator&=(basic_chset_8bit const& x)
+        {
+            bset &= x.bset;
+            return *this;
+        }
+
+        basic_chset_8bit&
+        operator-=(basic_chset_8bit const& x)
+        {
+            bset &= ~x.bset;
+            return *this;
+        }
+
+        basic_chset_8bit&
+        operator^=(basic_chset_8bit const& x)
+        {
+            bset ^= x.bset;
+            return *this;
+        }
+
+        private: std::bitset<256> bset;
+    };
+
+    /////////////////////////////////
+    template <>
+    struct basic_chset<char>
+      : basic_chset_8bit<char> {};
+
+    /////////////////////////////////
+    template <>
+    struct basic_chset<signed char>
+      : basic_chset_8bit<signed char> {};
+
+    /////////////////////////////////
+    template <>
+    struct basic_chset<unsigned char>
+      : basic_chset_8bit<unsigned char> {};
+
+#endif // #if (CHAR_BIT == 8)
+
+}}}}
+
+#endif
+

Added: trunk/boost/spirit/home/support/char_set/range.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/spirit/home/support/char_set/range.hpp	2009-08-11 23:07:38 EDT (Tue, 11 Aug 2009)
@@ -0,0 +1,32 @@
+/*=============================================================================
+    Copyright (c) 2001-2009 Joel de Guzman
+
+    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)
+==============================================================================*/
+#if !defined(BOOST_SPIRIT_RANGE_MAY_16_2006_0720_PM)
+#define BOOST_SPIRIT_RANGE_MAY_16_2006_0720_PM
+
+#if defined(_MSC_VER)
+#pragma once
+#endif
+
+namespace boost { namespace spirit { namespace support { namespace detail
+{
+    ///////////////////////////////////////////////////////////////////////////
+    //  A closed range (first, last)
+    ///////////////////////////////////////////////////////////////////////////
+    template <typename T>
+    struct range
+    {
+        typedef T value_type;
+
+        range() : first(), last() {}
+        range(T first, T last) : first(first), last(last) {}
+
+        T first;
+        T last;
+    };
+}}}}
+
+#endif

Added: trunk/boost/spirit/home/support/char_set/range_functions.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/spirit/home/support/char_set/range_functions.hpp	2009-08-11 23:07:38 EDT (Tue, 11 Aug 2009)
@@ -0,0 +1,98 @@
+/*=============================================================================
+    Copyright (c) 2001-2009 Joel de Guzman
+
+    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)
+==============================================================================*/
+#if !defined(BOOST_SPIRIT_RANGE_FUNCTIONS_MAY_16_2006_0720_PM)
+#define BOOST_SPIRIT_RANGE_FUNCTIONS_MAY_16_2006_0720_PM
+
+#if defined(_MSC_VER)
+#pragma once
+#endif
+
+#include <boost/integer_traits.hpp>
+
+namespace boost { namespace spirit { namespace support { namespace detail
+{
+    template <typename Range>
+    inline bool
+    is_valid(Range const& range)
+    {
+        // test for valid ranges
+        return range.first <= range.last;
+    }
+
+    template <typename Range>
+    inline bool
+    includes(Range const& range, Range const& other)
+    {
+        // see if two ranges intersect
+        return (range.first <= other.first) && (range.last >= other.last);
+    }
+
+    template <typename Range>
+    inline bool
+    includes(Range const& range, typename Range::value_type val)
+    {
+        // see if val is in range
+        return (range.first <= val) && (range.last >= val);
+    }
+
+    template <typename Range>
+    inline bool
+    can_merge(Range const& range, Range const& other)
+    {
+        // see if a 'range' overlaps, or is adjacent to
+        // another range 'other', so we can merge them
+
+        typedef typename Range::value_type value_type;
+        typedef integer_traits<value_type> integer_traits;
+
+        value_type decr_first =
+            range.first == integer_traits::const_min
+            ? range.first : range.first-1;
+
+        value_type incr_last =
+            range.last == integer_traits::const_max
+            ? range.last : range.last+1;
+
+        return (decr_first <= other.last) && (incr_last >= other.first);
+    }
+
+    template <typename Range>
+    inline void
+    merge(Range& result, Range const& other)
+    {
+        // merge two ranges
+        if (result.first > other.first)
+            result.first = other.first;
+        if (result.last < other.last)
+            result.last = other.last;
+    }
+
+    template <typename Range>
+    struct range_compare
+    {
+        // compare functor with a value or another range
+
+        typedef typename Range::value_type value_type;
+
+        bool operator()(Range const& x, const value_type y) const
+        {
+            return x.first < y;
+        }
+
+        bool operator()(value_type const x, Range const& y) const
+        {
+            return x < y.first;
+        }
+
+        bool operator()(Range const& x, Range const& y) const
+        {
+            return x.first < y.first;
+        }
+    };
+}}}}
+
+#endif

Added: trunk/boost/spirit/home/support/char_set/range_run.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/spirit/home/support/char_set/range_run.hpp	2009-08-11 23:07:38 EDT (Tue, 11 Aug 2009)
@@ -0,0 +1,56 @@
+/*=============================================================================
+    Copyright (c) 2001-2009 Joel de Guzman
+
+    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)
+==============================================================================*/
+#if !defined(BOOST_SPIRIT_RANGE_RUN_MAY_16_2006_0801_PM)
+#define BOOST_SPIRIT_RANGE_RUN_MAY_16_2006_0801_PM
+
+#if defined(_MSC_VER)
+#pragma once
+#endif
+
+#include <boost/spirit/home/support/char_set/range.hpp>
+#include <vector>
+
+namespace boost { namespace spirit { namespace support { namespace detail
+{
+    ///////////////////////////////////////////////////////////////////////////
+    //  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 interface }
+    ///////////////////////////////////////////////////////////////////////////
+    template <typename Char>
+    class range_run
+    {
+    public:
+
+        typedef range<Char> range_type;
+        typedef std::vector<range_type> storage_type;
+
+        void swap(range_run& other);
+        bool test(Char v) const;
+        void set(range_type const& range);
+        void clear(range_type const& range);
+        void clear();
+
+    private:
+
+        storage_type run;
+    };
+}}}}
+
+#include <boost/spirit/home/support/char_set/range_run_impl.hpp>
+#endif

Added: trunk/boost/spirit/home/support/char_set/range_run_impl.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/spirit/home/support/char_set/range_run_impl.hpp	2009-08-11 23:07:38 EDT (Tue, 11 Aug 2009)
@@ -0,0 +1,189 @@
+/*=============================================================================
+    Copyright (c) 2001-2009 Joel de Guzman
+
+    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)
+==============================================================================*/
+#if !defined(BOOST_SPIRIT_RANGE_RUN_MAY_16_2006_0807_PM)
+#define BOOST_SPIRIT_RANGE_RUN_MAY_16_2006_0807_PM
+
+#if defined(_MSC_VER)
+#pragma once
+#endif
+
+#include <boost/spirit/home/support/char_set/range_functions.hpp>
+#include <boost/assert.hpp>
+#include <boost/integer_traits.hpp>
+#include <algorithm>
+
+namespace boost { namespace spirit { namespace support { namespace detail
+{
+    template <typename Run, typename Iterator, typename Range>
+    inline bool
+    try_merge(Run& run, Iterator iter, Range const& range)
+    {
+        // if *iter intersects with, or is adjacent to, 'range'...
+        if (can_merge(*iter, range))
+        {
+            typedef typename Range::value_type value_type;
+            typedef integer_traits<value_type> integer_traits;
+
+            // merge range and *iter
+            merge(*iter, range);
+
+            // collapse all subsequent ranges that can merge with *iter:
+            Iterator i = iter+1;
+            // 1. skip subsequent ranges completely included in *iter
+            while (i != run.end() && i->last <= iter->last)
+                ++i;
+            // 2. collapse next range if adjacent or overlapping with *iter
+            if (i != run.end() && i->first-1 <= iter->last)
+            {
+                iter->last = i->last;
+                ++i;
+            }
+
+            // erase all ranges that were collapsed
+            run.erase(iter+1, i);
+            return true;
+        }
+        return false;
+    }
+
+    template <typename Char>
+    inline bool
+    range_run<Char>::test(Char val) const
+    {
+        if (run.empty())
+            return false;
+
+        // search the ranges for one that potentially includes val
+        typename storage_type::const_iterator iter =
+            std::upper_bound(
+                run.begin(), run.end(), val,
+                range_compare<range_type>()
+            );
+
+        // return true if *(iter-1) includes val
+        return iter != run.begin() && includes(*(--iter), val);
+    }
+
+    template <typename Char>
+    inline void
+    range_run<Char>::swap(range_run& other)
+    {
+        run.swap(other.run);
+    }
+
+    template <typename Char>
+    void
+    range_run<Char>::set(range_type const& range)
+    {
+        BOOST_ASSERT(is_valid(range));
+        if (run.empty())
+        {
+            // the vector is empty, insert 'range'
+            run.push_back(range);
+            return;
+        }
+
+        // search the ranges for one that potentially includes 'range'
+        typename storage_type::iterator iter =
+            std::upper_bound(
+                run.begin(), run.end(), range,
+                range_compare<range_type>()
+            );
+
+        if (iter != run.begin())
+        {
+            // if *(iter-1) includes 'range', return early
+            if (includes(*(iter-1), range))
+            {
+                return;
+            }
+
+            // if *(iter-1) can merge with 'range', merge them and return
+            if (try_merge(run, iter-1, range))
+            {
+                return;
+            }
+        }
+
+        // if *iter can merge with with 'range', merge them
+        if (iter == run.end() || !try_merge(run, iter, range))
+        {
+            // no overlap, insert 'range'
+            run.insert(iter, range);
+        }
+    }
+
+    template <typename Char>
+    void
+    range_run<Char>::clear(range_type const& range)
+    {
+        BOOST_ASSERT(is_valid(range));
+        if (!run.empty())
+        {
+            // search the ranges for one that potentially includes 'range'
+            typename storage_type::iterator iter =
+                std::upper_bound(
+                    run.begin(), run.end(), range,
+                    range_compare<range_type>()
+                );
+
+            // 'range' starts with or after another range:
+            if (iter != run.begin())
+            {
+                typename storage_type::iterator const left_iter = iter-1;
+
+                // 'range' starts after '*left_iter':
+                if (left_iter->first < range.first)
+                {
+                    // if 'range' is completely included inside '*left_iter':
+                    // need to break it apart into two ranges (punch a hole),
+                    if (left_iter->last > range.last)
+                    {
+                        Char save_last = left_iter->last;
+                        left_iter->last = range.first-1;
+                        run.insert(iter, range_type(range.last+1, save_last));
+                        return;
+                    }
+                    // if 'range' contains 'left_iter->last':
+                    // truncate '*left_iter' (clip its right)
+                    else if (left_iter->last >= range.first)
+                    {
+                        left_iter->last = range.first-1;
+                    }
+                }
+
+                // 'range' has the same left bound as '*left_iter': it
+                // must be removed or truncated by the code below
+                else
+                {
+                    iter = left_iter;
+                }
+            }
+
+            // remove or truncate subsequent ranges that overlap with 'range':
+            typename storage_type::iterator i = iter;
+            // 1. skip subsequent ranges completely included in 'range'
+            while (i != run.end() && i->last <= range.last)
+                ++i;
+            // 2. clip left of next range if overlapping with 'range'
+            if (i != run.end() && i->first <= range.last)
+                i->first = range.last+1;
+
+            // erase all ranges that 'range' contained
+            run.erase(iter, i);
+        }
+    }
+
+    template <typename Char>
+    inline void
+    range_run<Char>::clear()
+    {
+        run.clear();
+    }
+}}}}
+
+#endif

Added: trunk/boost/spirit/include/karma_char_.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/spirit/include/karma_char_.hpp	2009-08-11 23:07:38 EDT (Tue, 11 Aug 2009)
@@ -0,0 +1,18 @@
+/*=============================================================================
+    Copyright (c) 2001-2009 Joel de Guzman
+    Copyright (c) 2001-2009 Hartmut Kaiser
+    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_INCLUDE_KARMA_CHAR_
+#define BOOST_SPIRIT_INCLUDE_KARMA_CHAR_
+
+#if defined(_MSC_VER)
+#pragma once
+#endif
+
+#include <boost/spirit/home/karma/char/char.hpp>
+
+#endif