[Boost-commit] svn:boost r61479 - in trunk/libs/spirit/example/scheme: scheme test/utree utree utree/detail

Subject: [Boost-commit] svn:boost r61479 - in trunk/libs/spirit/example/scheme: scheme test/utree utree utree/detail
From: joel_at_[hidden]
Date: 2010-04-21 22:39:04

Author: djowel
Date: 2010-04-21 22:39:03 EDT (Wed, 21 Apr 2010)
New Revision: 61479
URL: http://svn.boost.org/trac/boost/changeset/61479

Log:
added utree shallow ranges
Text files modified: 
   trunk/libs/spirit/example/scheme/scheme/compiler.hpp            |     2                                         
   trunk/libs/spirit/example/scheme/scheme/interpreter.hpp         |     2                                         
   trunk/libs/spirit/example/scheme/test/utree/utree_test.cpp      |    21 +++++                                   
   trunk/libs/spirit/example/scheme/utree/detail/utree_detail1.hpp |     9 ++                                      
   trunk/libs/spirit/example/scheme/utree/detail/utree_detail2.hpp |   139 +++++++++++++++++++++++++++++++++++---- 
   trunk/libs/spirit/example/scheme/utree/operators.hpp            |    33 +++++++--                               
   trunk/libs/spirit/example/scheme/utree/utree.hpp                |    31 ++++++--                                
   7 files changed, 203 insertions(+), 34 deletions(-)

Modified: trunk/libs/spirit/example/scheme/scheme/compiler.hpp
==============================================================================
--- trunk/libs/spirit/example/scheme/scheme/compiler.hpp	(original)
+++ trunk/libs/spirit/example/scheme/scheme/compiler.hpp	2010-04-21 22:39:03 EDT (Wed, 21 Apr 2010)
@@ -352,7 +352,7 @@
             return function();
         }
 
-        function operator()(polymorphic_function_base const& pf) const
+        function operator()(function_base const& pf) const
         {
             // Can't reach here. Surely, at this point, we don't have
             // utree functions yet. The utree AST should be pure data.

Modified: trunk/libs/spirit/example/scheme/scheme/interpreter.hpp
==============================================================================
--- trunk/libs/spirit/example/scheme/scheme/interpreter.hpp	(original)
+++ trunk/libs/spirit/example/scheme/scheme/interpreter.hpp	2010-04-21 22:39:03 EDT (Wed, 21 Apr 2010)
@@ -98,7 +98,7 @@
 
         template <typename F>
         function(F const& f)
-          : f(polymorphic_function<F>(f))
+          : f(stored_function<F>(f))
         {
         }
 

Modified: trunk/libs/spirit/example/scheme/test/utree/utree_test.cpp
==============================================================================
--- trunk/libs/spirit/example/scheme/test/utree/utree_test.cpp	(original)
+++ trunk/libs/spirit/example/scheme/test/utree/utree_test.cpp	2010-04-21 22:39:03 EDT (Wed, 21 Apr 2010)
@@ -265,9 +265,28 @@
 
     {
         // test functions
-        utree f = scheme::polymorphic_function<one_two_three>();
+        utree f = scheme::stored_function<one_two_three>();
         f.eval(scheme::args_type());
     }
 
+    {
+        // shallow ranges
+        utree val;
+        val.push_back(1);
+        val.push_back(2);
+        val.push_back(3);
+        val.push_back(4);
+
+        utree::iterator i = val.begin(); ++i;
+        utree alias(utree::range(i, val.end()), scheme::shallow);
+
+        check(alias, "( 2 3 4 )");
+        BOOST_TEST(alias.size() == 3);
+        BOOST_TEST(alias.front() == 2);
+        BOOST_TEST(alias.back() == 4);
+        BOOST_TEST(!alias.empty());
+        BOOST_TEST(alias[1] == 3);
+    }
+
     return boost::report_errors();
 }

Modified: trunk/libs/spirit/example/scheme/utree/detail/utree_detail1.hpp
==============================================================================
--- trunk/libs/spirit/example/scheme/utree/detail/utree_detail1.hpp	(original)
+++ trunk/libs/spirit/example/scheme/utree/detail/utree_detail1.hpp	2010-04-21 22:39:03 EDT (Wed, 21 Apr 2010)
@@ -56,6 +56,15 @@
     };
 
     ///////////////////////////////////////////////////////////////////////////
+    // A range of utree(s) using an iterator range (begin/end) of node(s)
+    ///////////////////////////////////////////////////////////////////////////
+    struct range
+    {
+        list::node* first;
+        list::node* last;
+    };
+
+    ///////////////////////////////////////////////////////////////////////////
     // Our POD fast string. This implementation is very primitive and is not
     // meant to be used stand-alone. This is the internal data representation
     // of strings in our utree. This is deliberately a POD to allow it to be

Modified: trunk/libs/spirit/example/scheme/utree/detail/utree_detail2.hpp
==============================================================================
--- trunk/libs/spirit/example/scheme/utree/detail/utree_detail2.hpp	(original)
+++ trunk/libs/spirit/example/scheme/utree/detail/utree_detail2.hpp	2010-04-21 22:39:03 EDT (Wed, 21 Apr 2010)
@@ -182,7 +182,7 @@
             return node == other.node;
         }
 
-        reference dereference() const
+        typename node_iterator::reference dereference() const
         {
             return node->val;
         }
@@ -240,7 +240,7 @@
             return node == other.node;
         }
 
-        reference dereference() const
+        typename node_iterator::reference dereference() const
         {
             return curr;
         }
@@ -450,6 +450,9 @@
                 case type::list_type:
                     return f(list_range(iterator(x.l.first), iterator(0, x.l.last)));
 
+                case type::range_type:
+                    return f(list_range(iterator(x.r.first), iterator(0, x.r.last)));
+
                 case type::string_type:
                     return f(utf8_string_range(x.s.str(), x.s.size()));
 
@@ -503,6 +506,11 @@
                         y, detail::bind<F, list_range>(f,
                         list_range(iterator(x.l.first), iterator(0, x.l.last))));
 
+                case type::range_type:
+                    return visit_impl::apply(
+                        y, detail::bind<F, list_range>(f,
+                        list_range(iterator(x.r.first), iterator(0, x.r.last))));
+
                 case type::string_type:
                     return visit_impl::apply(y, detail::bind(
                         f, utf8_string_range(x.s.str(), x.s.size())));
@@ -546,27 +554,27 @@
 namespace scheme
 {
     template <typename F>
-    polymorphic_function<F>::polymorphic_function(F f)
+    stored_function<F>::stored_function(F f)
       : f(f)
     {
     }
 
     template <typename F>
-    polymorphic_function<F>::~polymorphic_function()
+    stored_function<F>::~stored_function()
     {
     };
 
     template <typename F>
-    utree polymorphic_function<F>::operator()(args_type args) const
+    utree stored_function<F>::operator()(args_type args) const
     {
         return f(args);
     }
 
     template <typename F>
-    polymorphic_function_base*
-    polymorphic_function<F>::clone() const
+    function_base*
+    stored_function<F>::clone() const
     {
-        return new polymorphic_function<F>(*this);
+        return new stored_function<F>(*this);
     }
 
     inline utree::utree()
@@ -626,8 +634,8 @@
     }
 
     template <typename F>
-    inline utree::utree(polymorphic_function<F> const& pf)
-      : pf(new polymorphic_function<F>(pf))
+    inline utree::utree(stored_function<F> const& pf)
+      : pf(new stored_function<F>(pf))
     {
         set_type(type::function_type);
     }
@@ -639,6 +647,20 @@
         assign(r.begin(), r.end());
     }
 
+    inline utree::utree(range r, shallow_tag)
+    {
+        this->r.first = r.begin().node;
+        this->r.last = r.end().prev;
+        set_type(type::range_type);
+    }
+
+    inline utree::utree(const_range r, shallow_tag)
+    {
+        this->r.first = r.begin().node;
+        this->r.last = r.end().prev;
+        set_type(type::range_type);
+    }
+
     inline utree::utree(utree const& other)
     {
         copy(other);
@@ -725,10 +747,10 @@
     }
 
     template <typename F>
-    utree& utree::operator=(polymorphic_function<F> const& pf)
+    utree& utree::operator=(stored_function<F> const& pf)
     {
         free();
-        pf = new polymorphic_function<F>(pf);
+        pf = new stored_function<F>(pf);
         set_type(type::function_type);
         return *this;
     }
@@ -738,6 +760,7 @@
     {
         free();
         assign(r.begin(), r.end());
+        return *this;
     }
 
     template <typename F>
@@ -786,6 +809,10 @@
     {
         if (get_type() == type::reference_type)
             return (*p)[i];
+        else if (get_type() == type::range_type)
+            return detail::index_impl::apply(r.first, i);
+
+        // otherwise...
         BOOST_ASSERT(get_type() == type::list_type && size() > i);
         return detail::index_impl::apply(l.first, i);
     }
@@ -794,6 +821,10 @@
     {
         if (get_type() == type::reference_type)
             return (*(utree const*)p)[i];
+        else if (get_type() == type::range_type)
+            return detail::index_impl::apply(r.first, i);
+
+        // otherwise...
         BOOST_ASSERT(get_type() == type::list_type && size() > i);
         return detail::index_impl::apply(l.first, i);
     }
@@ -911,6 +942,10 @@
     {
         if (get_type() == type::reference_type)
             return p->begin();
+        else if (get_type() == type::range_type)
+            return iterator(r.first);
+
+        // otherwise...
         ensure_list_type();
         return iterator(l.first);
     }
@@ -919,6 +954,10 @@
     {
         if (get_type() == type::reference_type)
             return p->end();
+        else if (get_type() == type::range_type)
+            return iterator(0, r.first);
+
+        // otherwise...
         ensure_list_type();
         return iterator(0, l.last);
     }
@@ -927,6 +966,10 @@
     {
         if (get_type() == type::reference_type)
             return p->ref_begin();
+        else if (get_type() == type::range_type)
+            return ref_iterator(r.first);
+
+        // otherwise...
         ensure_list_type();
         return ref_iterator(l.first);
     }
@@ -935,6 +978,10 @@
     {
         if (get_type() == type::reference_type)
             return p->ref_end();
+        else if (get_type() == type::range_type)
+            return ref_iterator(0, r.first);
+
+        // otherwise...
         ensure_list_type();
         return ref_iterator(0, l.last);
     }
@@ -943,6 +990,10 @@
     {
         if (get_type() == type::reference_type)
             return ((utree const*)p)->begin();
+        else if (get_type() == type::range_type)
+            return const_iterator(r.first);
+
+        // otherwise...
         BOOST_ASSERT(get_type() == type::list_type);
         return const_iterator(l.first);
     }
@@ -951,6 +1002,10 @@
     {
         if (get_type() == type::reference_type)
             return ((utree const*)p)->end();
+        else if (get_type() == type::range_type)
+            return const_iterator(0, r.first);
+
+        // otherwise...
         BOOST_ASSERT(get_type() == type::list_type);
         return const_iterator(0, l.last);
     }
@@ -959,7 +1014,9 @@
     {
         if (get_type() == type::reference_type)
             return ((utree const*)p)->empty();
-        if (get_type() == type::list_type)
+        else if (get_type() == type::range_type)
+            return r.first == 0;
+        else if (get_type() == type::list_type)
             return l.size == 0;
         BOOST_ASSERT(get_type() == type::nil_type);
         return true;
@@ -968,9 +1025,24 @@
     inline std::size_t utree::size() const
     {
         if (get_type() == type::reference_type)
+        {
             return ((utree const*)p)->size();
-        if (get_type() == type::list_type)
+        }
+        else if (get_type() == type::range_type)
+        {
+            std::size_t size = 0;
+            detail::list::node* n = r.first;
+            while (n)
+            {
+                n = n->next;
+                ++size;
+            }
+            return size;
+        }
+        else if (get_type() == type::list_type)
+        {
             return l.size;
+        }
         BOOST_ASSERT(get_type() == type::nil_type);
         return 0;
     }
@@ -983,7 +1055,16 @@
     inline utree& utree::front()
     {
         if (get_type() == type::reference_type)
+        {
             return p->front();
+        }
+        else if (get_type() == type::range_type)
+        {
+            BOOST_ASSERT(r.first != 0);
+            return r.first->val;
+        }
+
+        // otherwise...
         BOOST_ASSERT(get_type() == type::list_type && l.first != 0);
         return l.first->val;
     }
@@ -991,7 +1072,16 @@
     inline utree& utree::back()
     {
         if (get_type() == type::reference_type)
+        {
             return p->back();
+        }
+        else if (get_type() == type::range_type)
+        {
+            BOOST_ASSERT(r.last != 0);
+            return r.last->val;
+        }
+
+        // otherwise...
         BOOST_ASSERT(get_type() == type::list_type && l.last != 0);
         return l.last->val;
     }
@@ -999,7 +1089,16 @@
     inline utree const& utree::front() const
     {
         if (get_type() == type::reference_type)
+        {
             return ((utree const*)p)->front();
+        }
+        else if (get_type() == type::range_type)
+        {
+            BOOST_ASSERT(r.first != 0);
+            return r.first->val;
+        }
+
+        // otherwise...
         BOOST_ASSERT(get_type() == type::list_type && l.first != 0);
         return l.first->val;
     }
@@ -1007,7 +1106,16 @@
     inline utree const& utree::back() const
     {
         if (get_type() == type::reference_type)
+        {
             return ((utree const*)p)->back();
+        }
+        else if (get_type() == type::range_type)
+        {
+            BOOST_ASSERT(r.last != 0);
+            return r.last->val;
+        }
+
+        // otherwise...
         BOOST_ASSERT(get_type() == type::list_type && l.last != 0);
         return l.last->val;
     }
@@ -1081,6 +1189,9 @@
             case type::reference_type:
                 p = other.p;
                 break;
+            case type::range_type:
+                r = other.r;
+                break;
             case type::function_type:
                 pf = other.pf->clone();
                 break;

Modified: trunk/libs/spirit/example/scheme/utree/operators.hpp
==============================================================================
--- trunk/libs/spirit/example/scheme/utree/operators.hpp	(original)
+++ trunk/libs/spirit/example/scheme/utree/operators.hpp	2010-04-21 22:39:03 EDT (Wed, 21 Apr 2010)
@@ -13,6 +13,7 @@
 # pragma warning(disable: 4805)
 #endif
 
+#include <exception>
 #include <utree/utree.hpp>
 #include <boost/preprocessor/cat.hpp>
 #include <boost/type_traits/is_arithmetic.hpp>
@@ -20,6 +21,24 @@
 
 namespace scheme
 {
+    struct utree_exception : std::exception {};
+
+    struct illegal_arithmetic_operation : utree_exception
+    {
+        virtual const char* what() const throw()
+        {
+            return "utree: Illegal arithmetic operation.";
+        }
+    };
+
+    struct illegal_integral_operation : utree_exception
+    {
+        virtual const char* what() const throw()
+        {
+            return "utree: Illegal integral operation.";
+        }
+    };
+
     // Relational operators
     bool operator==(utree const& a, utree const& b);
     bool operator<(utree const& a, utree const& b);
@@ -99,7 +118,7 @@
             return true;
         }
 
-        bool operator()(polymorphic_function_base const& a, polymorphic_function_base const& b) const
+        bool operator()(function_base const& a, function_base const& b) const
         {
             return false; // just don't allow comparison of functions
         }
@@ -151,7 +170,7 @@
             return false; // no less than comparison for nil
         }
 
-        bool operator()(polymorphic_function_base const& a, polymorphic_function_base const& b) const
+        bool operator()(function_base const& a, function_base const& b) const
         {
             BOOST_ASSERT(false);
             return false; // no less than comparison of functions
@@ -225,7 +244,7 @@
             (*this)(')');
         }
 
-        void operator()(polymorphic_function_base const& pf) const
+        void operator()(function_base const& pf) const
         {
             return (*this)("<function>");
         }
@@ -288,7 +307,7 @@
         template <typename A, typename B>
         utree dispatch(A const&, B const&, boost::mpl::false_) const
         {
-            // $$$ Throw exception here? $$$
+            throw illegal_arithmetic_operation();
             return utree(); // cannot apply to non-arithmetic types
         }
 
@@ -311,7 +330,7 @@
         template <typename A>
         utree dispatch(A const&, boost::mpl::false_) const
         {
-            // $$$ Throw exception here? $$$
+            throw illegal_arithmetic_operation();
             return utree(); // cannot apply to non-arithmetic types
         }
 
@@ -337,7 +356,7 @@
         template <typename A, typename B>
         utree dispatch(A const&, B const&, boost::mpl::false_) const
         {
-            // $$$ Throw exception here? $$$
+            throw illegal_integral_operation();
             return utree(); // cannot apply to non-integral types
         }
 
@@ -360,7 +379,7 @@
         template <typename A>
         utree dispatch(A const&, boost::mpl::false_) const
         {
-            // $$$ Throw exception here? $$$
+            throw illegal_integral_operation();
             return utree(); // cannot apply to non-integral types
         }
 

Modified: trunk/libs/spirit/example/scheme/utree/utree.hpp
==============================================================================
--- trunk/libs/spirit/example/scheme/utree/utree.hpp	(original)
+++ trunk/libs/spirit/example/scheme/utree/utree.hpp	2010-04-21 22:39:03 EDT (Wed, 21 Apr 2010)
@@ -45,6 +45,7 @@
             symbol_type,
             binary_type,
             list_type,
+            range_type,
             reference_type,
             function_type
         };
@@ -136,24 +137,31 @@
     class utree;
     typedef boost::iterator_range<utree const*> args_type;
 
-    struct polymorphic_function_base
+    struct function_base
     {
-        virtual ~polymorphic_function_base() {};
+        virtual ~function_base() {};
         virtual utree operator()(args_type args) const = 0;
-        virtual polymorphic_function_base* clone() const = 0;
+        virtual function_base* clone() const = 0;
     };
 
     template <typename F>
-    struct polymorphic_function : polymorphic_function_base
+    struct stored_function : function_base
     {
         F f;
-        polymorphic_function(F f = F());
-        virtual ~polymorphic_function();
+        stored_function(F f = F());
+        virtual ~stored_function();
         virtual utree operator()(args_type args) const;
-        virtual polymorphic_function_base* clone() const;
+        virtual function_base* clone() const;
     };
 
     ///////////////////////////////////////////////////////////////////////////
+    // Shallow tag. Instructs utree to hold an iterator_range
+    // as-is without deep copying the range.
+    ///////////////////////////////////////////////////////////////////////////
+    struct shallow_tag {};
+    shallow_tag const shallow = {};
+
+    ///////////////////////////////////////////////////////////////////////////
     // The main utree (Universal Tree) class
     // The utree is a hierarchical, dynamic type that can store:
     //  - a nil
@@ -199,9 +207,11 @@
 
         template <typename Iter>
         utree(boost::iterator_range<Iter> r);
+        utree(range r, shallow_tag);
+        utree(const_range r, shallow_tag);
 
         template <typename F>
-        utree(polymorphic_function<F> const& pf);
+        utree(stored_function<F> const& pf);
 
         template <typename Base, utree_type::info type_>
         utree(basic_string<Base, type_> const& bin);
@@ -219,7 +229,7 @@
         utree& operator=(boost::reference_wrapper<utree> ref);
 
         template <typename F>
-        utree& operator=(polymorphic_function<F> const& pf);
+        utree& operator=(stored_function<F> const& pf);
 
         template <typename Iter>
         utree& operator=(boost::iterator_range<Iter> r);
@@ -330,11 +340,12 @@
         {
             detail::fast_string s;
             detail::list l;
+            detail::range r;
             bool b;
             int i;
             double d;
             utree* p;
-            polymorphic_function_base* pf;
+            function_base* pf;
         };
     };
 }