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;
};
};
}