Subject: [Boost-commit] svn:boost r60280 - trunk/libs/spirit/example/qi/scheme
From: joel_at_[hidden]
Date: 2010-03-07 04:08:02
Author: djowel
Date: 2010-03-07 04:08:00 EST (Sun, 07 Mar 2010)
New Revision: 60280
URL: http://svn.boost.org/trac/boost/changeset/60280
Log:
utree
Added:
trunk/libs/spirit/example/qi/scheme/utree.hpp (contents, props changed)
trunk/libs/spirit/example/qi/scheme/utree_test.cpp (contents, props changed)
Text files modified:
trunk/libs/spirit/example/qi/scheme/sexpr.hpp | 4 ++--
1 files changed, 2 insertions(+), 2 deletions(-)
Modified: trunk/libs/spirit/example/qi/scheme/sexpr.hpp
==============================================================================
--- trunk/libs/spirit/example/qi/scheme/sexpr.hpp (original)
+++ trunk/libs/spirit/example/qi/scheme/sexpr.hpp 2010-03-07 04:08:00 EST (Sun, 07 Mar 2010)
@@ -22,10 +22,10 @@
namespace scheme
{
- using boost::spirit::qi::grammar;
- using boost::spirit::qi::rule;
using boost::spirit::unicode::char_;
using boost::spirit::unicode::space;
+ using boost::spirit::qi::grammar;
+ using boost::spirit::qi::rule;
using boost::spirit::qi::eol;
using boost::spirit::qi::_val;
using boost::spirit::qi::_r1;
Added: trunk/libs/spirit/example/qi/scheme/utree.hpp
==============================================================================
--- (empty file)
+++ trunk/libs/spirit/example/qi/scheme/utree.hpp 2010-03-07 04:08:00 EST (Sun, 07 Mar 2010)
@@ -0,0 +1,1121 @@
+/*=============================================================================
+ Copyright (c) 2001-2010 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_UTREE)
+#define BOOST_SPIRIT_UTREE
+
+#include <cstddef>
+#include <algorithm>
+#include <string>
+#include <boost/assert.hpp>
+#include <boost/noncopyable.hpp>
+#include <boost/iterator/iterator_facade.hpp>
+#include <boost/range/iterator_range.hpp>
+
+#if defined(BOOST_MSVC)
+# pragma warning(push)
+# pragma warning(disable: 4804) // unsafe mix of type 'const bool' and type 'const int' in operation
+# pragma warning(disable: 4805) // unsafe mix of type 'const bool' and type 'const int' in operation
+#endif
+
+namespace scheme { namespace detail
+{
+ template <typename UTreeX, typename UTreeY>
+ struct visit_impl;
+ struct index_impl;
+
+ // Our utree can store these types. This enum tells us what type
+ // of data is stored in the discriminated union.
+ struct utree_type
+ {
+ enum info
+ {
+ nil_type,
+ bool_type,
+ int_type,
+ double_type,
+ small_string_type,
+ heap_string_type,
+ list_type
+ };
+ };
+
+ // 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
+ // placed in a union. This POD fast string specifically utilizes
+ // (sizeof(double) * 2) - 2 * sizeof(char) (14 bytes in a 32 bit system).
+ // Two extra bytes are used by utree to store management info.
+ //
+ // It is a const string (i.e. immutable). It stores the characters directly
+ // if possible and only uses the heap if the string does not fit. Null
+ // characters are allowed, making it suitable to encode raw binary. The
+ // string length is encoded in the first byte if the string is placed in-situ,
+ // else, the length plus a pointer to the string in the heap are stored.
+
+ struct fast_string // Keep this a POD!
+ {
+ static std::size_t const
+ buff_size = (sizeof(double)*2)/sizeof(char);
+
+ static std::size_t const
+ small_string_size = buff_size-(sizeof(char)*2);
+
+ struct heap_store
+ {
+ char* str;
+ std::size_t size;
+ };
+
+ union
+ {
+ char buff[buff_size];
+ heap_store heap;
+ };
+
+ utree_type::info get_type() const
+ {
+ return static_cast<utree_type::info>(buff[small_string_size]);
+ }
+
+ void set_type(utree_type::info t)
+ {
+ buff[small_string_size] = static_cast<char>(t);
+ }
+
+ std::size_t size() const
+ {
+ BOOST_ASSERT(get_type() == utree_type::small_string_type
+ || get_type() == utree_type::heap_string_type);
+
+ if (get_type() == utree_type::small_string_type)
+ return this->buff[0];
+ else
+ return this->heap.size;
+ }
+
+ char const* str() const
+ {
+ BOOST_ASSERT(get_type() == utree_type::small_string_type
+ || get_type() == utree_type::heap_string_type);
+
+ if (get_type() == utree_type::small_string_type)
+ return this->buff + 1;
+ else
+ return this->heap.str;
+ }
+
+ template <typename Iterator>
+ void construct(Iterator f, Iterator l)
+ {
+ unsigned const size = (l-f)+1;
+ char* str;
+ if (size <= small_string_size)
+ {
+ // if it fits, store it in-situ; the first byte
+ // is the length of the string.
+ str = this->buff + 1;
+ this->buff[0] = size;
+ set_type(utree_type::small_string_type);
+ }
+ else
+ {
+ // else, store it in the heap
+ str = new char[size];
+ this->heap.str = str;
+ this->heap.size = size;
+ set_type(utree_type::heap_string_type);
+ }
+ for (int i = 0; i != size; ++i)
+ *str++ = *f++;
+ }
+
+ void swap(fast_string& other)
+ {
+ fast_string temp = other;
+ other = *this;
+ *this = temp;
+ }
+
+ void free()
+ {
+ if (get_type() == utree_type::heap_string_type)
+ {
+ delete [] this->heap.str;
+ this->heap.str = 0;
+ }
+ }
+
+ void copy(fast_string const& other)
+ {
+ construct(other.str(), other.str() + other.size());
+ }
+ };
+
+ // Our POD double linked list. Straightforward implementation.
+ // This implementation is very primitive and is not meant to be
+ // used stand-alone. This is the internal data representation
+ // of lists in our utree.
+ struct list // keep this a POD!
+ {
+ struct node;
+
+ template <typename Value>
+ class node_iterator;
+
+ void free();
+ void copy(list const& other);
+ void default_construct()
+ {
+ this->first = this->last = 0;
+ this->size = 0;
+ }
+
+ template <typename T>
+ void insert_before(T const& val, node* node);
+
+ template <typename T>
+ void insert_after(T const& val, node* node);
+
+ template <typename T>
+ void push_front(T const& val);
+
+ template <typename T>
+ void push_back(T const& val);
+
+ void pop_front();
+ void pop_back();
+ node* erase(node* pos);
+
+ node* first;
+ node* last;
+ std::size_t size;
+ };
+}}
+
+namespace scheme
+{
+ class utree
+ {
+ public:
+
+ typedef utree value_type;
+ typedef detail::list::node_iterator<utree> iterator;
+ typedef detail::list::node_iterator<utree const> const_iterator;
+ typedef utree& reference;
+ typedef utree const& const_reference;
+ typedef std::ptrdiff_t difference_type;
+ typedef std::size_t size_type;
+
+ struct nil {};
+
+ utree() { set_type(type::nil_type); }
+ explicit utree(bool b) : b(b) { set_type(type::bool_type); }
+ explicit utree(unsigned i) : i(i) { set_type(type::int_type); }
+ explicit utree(int i) : i(i) { set_type(type::int_type); }
+ explicit utree(double d) : d(d) { set_type(type::double_type); }
+ explicit utree(char const* str) { s.construct(str, str+strlen(str)); }
+ explicit utree(std::string const& str) { s.construct(str.begin(), str.end()); }
+
+ template <typename F>
+ typename F::result_type
+ static visit(utree const& x, F f);
+
+ template <typename F>
+ typename F::result_type
+ static visit(utree& x, F f);
+
+ template <typename F>
+ typename F::result_type
+ static visit(utree const& x, utree const& y, F f);
+
+ template <typename F>
+ typename F::result_type
+ static visit(utree& x, utree const& y, F f);
+
+ template <typename F>
+ typename F::result_type
+ static visit(utree const& x, utree& y, F f);
+
+ template <typename F>
+ typename F::result_type
+ static visit(utree& x, utree& y, F f);
+
+ utree(utree const& other) { copy(*this, other); }
+ ~utree() { free(*this); }
+
+ utree& operator=(utree const& other);
+
+ utree& operator=(bool b);
+ utree& operator=(unsigned i);
+ utree& operator=(int i);
+ utree& operator=(double d);
+ utree& operator=(char const* s);
+ utree& operator=(std::string const& s);
+
+ template <typename T>
+ void push_back(T const& val);
+
+ template <typename T>
+ void push_front(T const& val);
+
+ template <typename T>
+ iterator insert(iterator pos, T const& x);
+
+ template <typename T>
+ void insert(iterator pos, std::size_t, T const& x);
+
+ template <typename Iter>
+ void insert(iterator pos, Iter first, Iter last);
+
+ template <typename Iter>
+ void assign(Iter first, Iter last);
+
+ void clear();
+ void pop_front();
+ void pop_back();
+ iterator erase(iterator pos);
+ iterator erase(iterator first, iterator last);
+
+ utree& front();
+ utree& back();
+ utree const& front() const;
+ utree const& back() const;
+
+ utree& operator[](std::size_t i);
+ utree const& operator[](std::size_t i) const;
+
+ void swap(utree& other);
+
+ iterator begin();
+ iterator end();
+ const_iterator begin() const;
+ const_iterator end() const;
+
+ bool empty() const;
+ std::size_t size() const;
+
+ private:
+
+ typedef detail::utree_type type;
+
+ template <typename UTreeX, typename UTreeY>
+ friend struct detail::visit_impl;
+ friend struct detail::index_impl;
+ friend struct ulist;
+
+ type::info get_type() const
+ {
+ // the fast string holds the type info
+ return s.get_type();
+ }
+
+ void set_type(type::info t)
+ {
+ // the fast string holds the type info
+ s.set_type(t);
+ }
+
+ void ensure_list_type();
+
+ static void free(utree& x);
+ static void copy(utree& x, utree const& other);
+
+ struct construct_list {};
+
+ utree(construct_list)
+ {
+ l.default_construct();
+ set_type(type::list_type);
+ }
+
+ union
+ {
+ detail::fast_string s;
+ detail::list l;
+ bool b;
+ int i;
+ double d;
+ };
+ };
+
+ std::ostream& operator<<(std::ostream& out, utree const& val);
+
+ bool operator==(utree const& a, utree const& b);
+ bool operator<(utree const& a, utree const& b);
+ std::ostream& operator<<(std::ostream& out, utree const& val);
+
+ inline bool operator!=(utree const& a, utree const& b)
+ {
+ return !(a == b);
+ }
+
+ inline bool operator>(utree const& a, utree const& b)
+ {
+ return b < a;
+ }
+
+ inline bool operator<=(utree const& a, utree const& b)
+ {
+ return !(b < a);
+ }
+
+ inline bool operator>=(utree const& a, utree const& b)
+ {
+ return !(a < b);
+ }
+
+ struct ulist : utree
+ {
+ ulist() : utree(construct_list()) {}
+ };
+}
+
+namespace scheme { namespace detail
+{
+ struct list::node : boost::noncopyable
+ {
+ template <typename T>
+ node(T const& val, node* next, node* prev)
+ : val(val), next(next), prev(prev) {}
+
+ void unlink()
+ {
+ prev->next = next;
+ next->prev = prev;
+ }
+
+ utree val;
+ node* next;
+ node* prev;
+ };
+
+ template <typename Value>
+ class list::node_iterator
+ : public boost::iterator_facade<
+ node_iterator<Value>
+ , Value
+ , boost::bidirectional_traversal_tag
+ >
+ {
+ public:
+
+ node_iterator()
+ : node(0) {}
+
+ explicit node_iterator(list::node* p)
+ : node(p) {}
+
+ private:
+
+ friend class boost::iterator_core_access;
+ friend class utree;
+
+ void increment() { node = node->next; }
+ void decrement() { node = node->prev; }
+
+ bool equal(node_iterator const& other) const
+ {
+ return this->node == other.node;
+ }
+
+ utree& dereference() const { return node->val; }
+ list::node* node;
+ };
+
+ inline void list::free()
+ {
+ node* p = this->first;
+ while (p != this->last)
+ {
+ node* next = p->next;
+ delete p;
+ p = next;
+ }
+ this->first = this->last = 0;
+ this->size = 0;
+ }
+
+ inline void list::copy(list const& other)
+ {
+ this->first = this->last = 0;
+ node* p = other.first;
+ while (p != 0)
+ {
+ this->push_back(p->val);
+ p = p->next;
+ }
+ }
+
+ template <typename T>
+ inline void list::insert_before(T const& val, node* np)
+ {
+ node* new_node = new node(val, np, np->prev);
+ if (np->prev)
+ np->prev->next = new_node;
+ else
+ this->first = new_node;
+ np->prev = new_node;
+ ++this->size;
+ }
+
+ template <typename T>
+ inline void list::insert_after(T const& val, node* np)
+ {
+ node* new_node = new node(val, np->next, np);
+ if (np->next)
+ np->next->prev = new_node;
+ else
+ this->last = new_node;
+ np->next = new_node;
+ ++this->size;
+ }
+
+ template <typename T>
+ inline void list::push_front(T const& val)
+ {
+ detail::list::node* new_node;
+ if (this->first == 0)
+ {
+ new_node = new detail::list::node(val, 0, 0);
+ this->first = this->last = new_node;
+ ++this->size;
+ }
+ else
+ {
+ this->insert_before(val, this->first);
+ }
+ }
+
+ template <typename T>
+ inline void list::push_back(T const& val)
+ {
+ if (this->last == 0)
+ this->push_front(val);
+ else
+ this->insert_after(val, this->last);
+ }
+
+ inline void list::pop_front()
+ {
+ node* np = this->first;
+ this->first = this->first->next;
+ this->first->prev = 0;
+ delete np;
+ --this->size;
+ }
+
+ inline void list::pop_back()
+ {
+ node* np = this->last;
+ this->last = this->last->prev;
+ this->last->next = 0;
+ delete np;
+ --this->size;
+ }
+
+ inline list::node* list::erase(node* pos)
+ {
+ if (pos == this->first)
+ {
+ this->pop_front();
+ return this->first;
+ }
+ else if (pos == this->last)
+ {
+ this->pop_back();
+ return 0;
+ }
+ else
+ {
+ node* next(pos->next);
+ pos->unlink();
+ delete pos;
+ --this->size;
+ return next;
+ }
+ }
+
+ template <typename F, typename X>
+ struct bind_impl // simple binder for binary visitation (we don't want to bring in the big guns)
+ {
+ typedef typename F::result_type result_type;
+ X& x; // always by reference
+ F f;
+ bind_impl(F f, X& x) : x(x), f(f) {}
+
+ template <typename Y>
+ typename F::result_type operator()(Y& y) const
+ {
+ return f(x, y);
+ }
+
+ template <typename Y>
+ typename F::result_type operator()(Y const& y) const
+ {
+ return f(x, y);
+ }
+ };
+
+ template <typename F, typename X>
+ bind_impl<F, X const> bind(F f, X const& x)
+ {
+ return bind_impl<F, X const>(f, x);
+ }
+
+ template <typename F, typename X>
+ bind_impl<F, X> bind(F f, X& x)
+ {
+ return bind_impl<F, X>(f, x);
+ }
+
+ struct utree_print
+ {
+ typedef void result_type;
+ std::ostream& out;
+ utree_print(std::ostream& out)
+ : out(out) {}
+
+ void operator()(utree::nil) const
+ {
+ out << "nil";
+ }
+
+ template <typename T>
+ void operator()(T val) const
+ {
+ out << val;
+ }
+
+ void operator()(bool b) const
+ {
+ out << (b?"true":"false");
+ }
+
+ void operator()(char const* s) const
+ {
+ out << '"' << s << '"';
+ }
+
+ template <typename Iterator>
+ void operator()(boost::iterator_range<Iterator> const& range) const
+ {
+ out << '[';
+ for (typename boost::iterator_range<Iterator>::const_iterator
+ i = range.begin(); i != range.end(); ++i)
+ {
+ if (i != range.begin())
+ out << ',';
+ out << *i;
+ }
+ out << ']';
+ }
+ };
+
+ struct utree_is_equal
+ {
+ typedef bool result_type;
+
+ template <typename A, typename B>
+ bool dispatch(const A&, const B&, boost::mpl::false_) const
+ {
+ return false; // cannot compare different types by default
+ }
+
+ template <typename A, typename B>
+ bool dispatch(const A& a, const B& b, boost::mpl::true_) const
+ {
+ return a == b; // for arithmetic types
+ }
+
+ template <typename A, typename B>
+ bool operator()(const A& a, const B& b) const
+ {
+ return dispatch(a, b,
+ boost::mpl::and_<boost::is_arithmetic<A>, boost::is_arithmetic<B> >());
+ }
+
+ template <typename T>
+ bool operator()(const T& a, const T& b) const
+ {
+ return a == b;
+ }
+
+ bool operator()(utree::nil, utree::nil) const
+ {
+ return true;
+ }
+
+ bool operator()(char const* a, char const* b) const
+ {
+ return strcmp(a, b) == 0; // $$$ use utf8 comparison here! $$$
+ }
+ };
+
+ struct utree_is_less_than
+ {
+ typedef bool result_type;
+
+ template <typename A, typename B>
+ bool dispatch(const A&, const B&, boost::mpl::false_) const
+ {
+ return false; // cannot compare different types by default
+ }
+
+ template <typename A, typename B>
+ bool dispatch(const A& a, const B& b, boost::mpl::true_) const
+ {
+ return a < b; // for arithmetic types
+ }
+
+ template <typename A, typename B>
+ bool operator()(const A& a, const B& b) const
+ {
+ return dispatch(a, b,
+ boost::mpl::and_<boost::is_arithmetic<A>, boost::is_arithmetic<B> >());
+ }
+
+ template <typename T>
+ bool operator()(const T& a, const T& b) const
+ {
+ return a < b;
+ }
+
+ bool operator()(utree::nil, utree::nil) const
+ {
+ BOOST_ASSERT(false);
+ return false; // no less than comparison for nil
+ }
+
+ bool operator()(char const* a, char const* b) const
+ {
+ return strcmp(a, b) < 0; // $$$ use utf8 comparison here! $$$
+ }
+ };
+
+ template <typename UTreeX, typename UTreeY = UTreeX>
+ struct visit_impl
+ {
+ template <typename F>
+ typename F::result_type
+ static apply(UTreeX& x, F f) // single dispatch
+ {
+ typedef typename
+ boost::mpl::if_<boost::is_const<UTreeX>, char const*, char*>::type
+ string_type;
+
+ typedef typename
+ boost::mpl::if_<boost::is_const<UTreeX>,
+ typename UTreeX::const_iterator,
+ typename UTreeX::iterator>::type
+ iterator;
+
+ typedef boost::iterator_range<iterator> list_range;
+ typedef detail::utree_type type;
+
+ switch (x.get_type())
+ {
+ case type::nil_type:
+ typename UTreeX::nil arg;
+ return f(arg);
+ case type::bool_type:
+ return f(x.b);
+ case type::int_type:
+ return f(x.i);
+ case type::double_type:
+ return f(x.d);
+ case type::list_type:
+ return f(list_range(iterator(x.l.first), iterator(0)));
+ default:
+ return f(string_type(x.s.str()));
+ }
+ }
+
+ template <typename F>
+ typename F::result_type
+ static apply(UTreeX& x, UTreeY& y, F f) // double dispatch
+ {
+ typedef typename
+ boost::mpl::if_<boost::is_const<UTreeX>, char const*, char*>::type
+ string_type;
+
+ typedef typename
+ boost::mpl::if_<boost::is_const<UTreeX>,
+ typename UTreeX::const_iterator,
+ typename UTreeX::iterator>::type
+ iterator;
+
+ typedef boost::iterator_range<iterator> list_range;
+ typedef detail::utree_type type;
+
+ switch (x.get_type())
+ {
+ case type::nil_type:
+ typename UTreeX::nil x_;
+ return visit_impl::apply(y, detail::bind(f, x_));
+ case type::bool_type:
+ return visit_impl::apply(y, detail::bind(f, x.b));
+ case type::int_type:
+ return visit_impl::apply(y, detail::bind(f, x.i));
+ case type::double_type:
+ return visit_impl::apply(y, detail::bind(f, x.d));
+ case type::list_type:
+ return visit_impl::apply(
+ y, detail::bind<F, list_range>(f,
+ list_range(iterator(x.l.first), iterator(0))));
+ default:
+ return visit_impl::apply(y, detail::bind(f, string_type(x.s.str())));
+ }
+ }
+ };
+
+ struct index_impl
+ {
+ static utree& apply(detail::list::node* node, std::size_t i)
+ {
+ for (; i > 0; --i)
+ node = node->next;
+ return node->val;
+ }
+
+ static utree const& apply(detail::list::node const* node, std::size_t i)
+ {
+ for (; i > 0; --i)
+ node = node->next;
+ return node->val;
+ }
+ };
+}}
+
+namespace scheme
+{
+ inline utree& utree::operator=(utree const& other)
+ {
+ if (this != &other)
+ {
+ free(*this);
+ copy(*this, other);
+ }
+ return *this;
+ }
+
+ inline utree& utree::operator=(bool b_)
+ {
+ free(*this);
+ b = b_;
+ set_type(type::bool_type);
+ return *this;
+ }
+
+ inline utree& utree::operator=(unsigned i_)
+ {
+ free(*this);
+ i = i_;
+ set_type(type::int_type);
+ return *this;
+ }
+
+ inline utree& utree::operator=(int i_)
+ {
+ free(*this);
+ i = i_;
+ set_type(type::int_type);
+ return *this;
+ }
+
+ inline utree& utree::operator=(double d_)
+ {
+ free(*this);
+ d = d_;
+ set_type(type::double_type);
+ return *this;
+ }
+
+ inline utree& utree::operator=(char const* s)
+ {
+ free(*this);
+ this->s.construct(s, s + strlen(s));
+ return *this;
+ }
+
+ inline utree& utree::operator=(std::string const& s)
+ {
+ free(*this);
+ this->s.construct(s.begin(), s.end());
+ return *this;
+ }
+
+ template <typename F>
+ typename F::result_type
+ inline utree::visit(utree const& x, F f)
+ {
+ return detail::visit_impl<utree const>::apply(x, f);
+ }
+
+ template <typename F>
+ typename F::result_type
+ inline utree::visit(utree& x, F f)
+ {
+ return detail::visit_impl<utree>::apply(x, f);
+ }
+
+ template <typename F>
+ typename F::result_type
+ inline utree::visit(utree const& x, utree const& y, F f)
+ {
+ return detail::visit_impl<utree const, utree const>::apply(x, y, f);
+ }
+
+ template <typename F>
+ typename F::result_type
+ inline utree::visit(utree const& x, utree& y, F f)
+ {
+ return detail::visit_impl<utree const, utree>::apply(x, y, f);
+ }
+
+ template <typename F>
+ typename F::result_type
+ inline utree::visit(utree& x, utree const& y, F f)
+ {
+ return detail::visit_impl<utree, utree const>::apply(x, y, f);
+ }
+
+ template <typename F>
+ typename F::result_type
+ inline utree::visit(utree& x, utree& y, F f)
+ {
+ return detail::visit_impl<utree, utree>::apply(x, y, f);
+ }
+
+ inline utree& utree::operator[](std::size_t i)
+ {
+ BOOST_ASSERT(this->get_type() == type::list_type && this->size() > i);
+ return detail::index_impl::apply(l.first, i);
+ }
+
+ inline utree const& utree::operator[](std::size_t i) const
+ {
+ BOOST_ASSERT(this->get_type() == type::list_type && this->size() > i);
+ return detail::index_impl::apply(l.first, i);
+ }
+
+ inline std::ostream& operator<<(std::ostream& out, utree const& val)
+ {
+ utree::visit(val, detail::utree_print(out));
+ return out;
+ }
+
+ inline bool operator==(utree const& a, utree const& b)
+ {
+ return utree::visit(a, b, detail::utree_is_equal());
+ }
+
+ inline bool operator<(utree const& a, utree const& b)
+ {
+ return utree::visit(a, b, detail::utree_is_less_than());
+ }
+
+ inline void utree::ensure_list_type()
+ {
+ if (this->get_type() == type::nil_type)
+ {
+ this->set_type(type::list_type);
+ this->l.first = this->l.last = 0;
+ this->l.size = 0;
+ }
+ else
+ {
+ BOOST_ASSERT(this->get_type() == type::list_type);
+ }
+ }
+
+ template <typename T>
+ inline void utree::push_front(T const& val)
+ {
+ ensure_list_type();
+ this->l.push_front(val);
+ }
+
+ template <typename T>
+ inline void utree::push_back(T const& val)
+ {
+ ensure_list_type();
+ this->l.push_back(val);
+ }
+
+ template <typename T>
+ inline utree::iterator utree::insert(iterator pos, T const& val)
+ {
+ ensure_list_type();
+ this->l.insert_before(val, pos.node);
+ return utree::iterator(pos.node->prev);
+ }
+
+
+ template <typename T>
+ inline void utree::insert(iterator pos, std::size_t n, T const& val)
+ {
+ for (std::size_t i = 0; i != n; ++i)
+ this->insert(pos, val);
+ }
+
+ template <typename Iter>
+ inline void utree::insert(iterator pos, Iter first, Iter last)
+ {
+ ensure_list_type();
+ while (first != last)
+ this->l.insert_before(*first++, pos.node);
+ }
+
+ template <typename Iter>
+ inline void utree::assign(Iter first, Iter last)
+ {
+ ensure_list_type();
+ clear();
+ while (first != last)
+ this->push_back(*first++);
+ }
+
+ inline void utree::clear()
+ {
+ BOOST_ASSERT(this->get_type() == type::list_type);
+ free(*this);
+ }
+
+ inline void utree::pop_front()
+ {
+ BOOST_ASSERT(this->get_type() == type::list_type);
+ this->l.pop_front();
+ }
+
+ inline void utree::pop_back()
+ {
+ BOOST_ASSERT(this->get_type() == type::list_type);
+ this->l.pop_back();
+ }
+
+ inline utree::iterator utree::erase(iterator pos)
+ {
+ BOOST_ASSERT(this->get_type() == type::list_type);
+ return iterator(this->l.erase(pos.node));
+ }
+
+ inline utree::iterator utree::erase(iterator first, iterator last)
+ {
+ while (first != last)
+ this->erase(first++);
+ return last;
+ }
+
+ inline utree::iterator utree::begin()
+ {
+ BOOST_ASSERT(this->get_type() == type::list_type);
+ return iterator(l.first);
+ }
+
+ inline utree::iterator utree::end()
+ {
+ BOOST_ASSERT(this->get_type() == type::list_type);
+ return iterator(l.last);
+ }
+
+ inline utree::const_iterator utree::begin() const
+ {
+ BOOST_ASSERT(this->get_type() == type::list_type);
+ return const_iterator(l.first);
+ }
+
+ inline utree::const_iterator utree::end() const
+ {
+ BOOST_ASSERT(this->get_type() == type::list_type);
+ return const_iterator(l.last);
+ }
+
+ inline bool utree::empty() const
+ {
+ BOOST_ASSERT(this->get_type() == type::list_type);
+ return l.first == l.last;
+ }
+
+ inline std::size_t utree::size() const
+ {
+ BOOST_ASSERT(this->get_type() == type::list_type);
+ return this->l.size;
+ }
+
+ inline utree& utree::front()
+ {
+ BOOST_ASSERT(this->get_type() == type::list_type && this->l.first != 0);
+ return this->l.first->val;
+ }
+
+ inline utree& utree::back()
+ {
+ BOOST_ASSERT(this->get_type() == type::list_type && this->l.last != 0);
+ return this->l.last->val;
+ }
+
+ inline utree const& utree::front() const
+ {
+ BOOST_ASSERT(this->get_type() == type::list_type && this->l.first != 0);
+ return this->l.first->val;
+ }
+
+ inline utree const& utree::back() const
+ {
+ BOOST_ASSERT(this->get_type() == type::list_type && this->l.last != 0);
+ return this->l.last->val;
+ }
+
+
+ inline void utree::free(utree& x)
+ {
+ switch (x.get_type())
+ {
+ default:
+ break;
+ case type::heap_string_type:
+ x.s.free();
+ break;
+ case type::list_type:
+ x.l.free();
+ break;
+ };
+ }
+
+ inline void utree::copy(utree& x, utree const& other)
+ {
+ x.set_type(other.get_type());
+ switch (other.get_type())
+ {
+ case type::nil_type:
+ break;
+ case type::bool_type:
+ x.b = other.b;
+ break;
+ case type::int_type:
+ x.i = other.i;
+ break;
+ case type::double_type:
+ x.d = other.d;
+ break;
+ case type::small_string_type:
+ case type::heap_string_type:
+ x.s.copy(other.s);
+ break;
+ case type::list_type:
+ x.l.copy(other.l);
+ break;
+ }
+ }
+
+ inline void utree::swap(utree& other)
+ {
+ this->s.swap(other.s);
+ }
+}
+
+#endif
Added: trunk/libs/spirit/example/qi/scheme/utree_test.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/spirit/example/qi/scheme/utree_test.cpp 2010-03-07 04:08:00 EST (Sun, 07 Mar 2010)
@@ -0,0 +1,135 @@
+#include "utree.hpp"
+#include <iostream>
+
+int main()
+{
+ using scheme::utree;
+ using scheme::ulist;
+
+ {
+ // test the size
+ std::cout << sizeof(scheme::utree) << std::endl;
+ }
+
+ {
+ utree val;
+ std::cout << val << std::endl;
+ }
+
+ {
+ utree val(true);
+ std::cout << val << std::endl;
+ }
+
+ {
+ utree val(123);
+ std::cout << val << std::endl;
+ }
+
+ {
+ utree val(123.456);
+ std::cout << val << std::endl;
+ }
+
+ {
+ utree val("Hello, World");
+ std::cout << val << std::endl;
+ utree val2;
+ val2 = val;
+ std::cout << val2 << std::endl;
+ utree val3("Hello, World. Chuckie is back!!!");
+ val = val3;
+ std::cout << val << std::endl;
+ }
+
+ {
+ utree val;
+ val.push_back(123);
+ val.push_back("Chuckie");
+ utree val2;
+ val2.push_back(123.456);
+ val2.push_back("Mah Doggie");
+ val.push_back(val2);
+ std::cout << val << std::endl;
+ std::cout << val.front() << std::endl;
+
+ utree val3;
+ val3.swap(val);
+ std::cout << val << std::endl;
+ val3.swap(val);
+ std::cout << val << std::endl;
+ val.push_back("Ba Ba Black Sheep");
+ std::cout << val << std::endl;
+ val.pop_front();
+ std::cout << val << std::endl;
+ utree::iterator i = val.begin();
+ ++++i;
+ val.insert(i, "Right in the middle");
+ BOOST_ASSERT(val.size() == 4);
+ std::cout << val << std::endl;
+ val.pop_back();
+ std::cout << val << std::endl;
+ BOOST_ASSERT(val.size() == 3);
+ val.erase(val.end());
+ std::cout << val << std::endl;
+ BOOST_ASSERT(val.size() == 2);
+
+ val.insert(val.begin(), val2.begin(), val2.end());
+ std::cout << val << std::endl;
+ }
+
+ {
+ utree a, b;
+ BOOST_ASSERT(a == b);
+ a = 123;
+ BOOST_ASSERT(a != b);
+ b = 123;
+ BOOST_ASSERT(a == b);
+ a = 100.00;
+ BOOST_ASSERT(a < b);
+
+ b = a = ulist();
+ BOOST_ASSERT(a == b);
+ a.push_back(1);
+ a.push_back("two");
+ a.push_back(3.0);
+ b.push_back(1);
+ b.push_back("two");
+ b.push_back(3.0);
+ BOOST_ASSERT(a == b);
+ b.push_back(4);
+ BOOST_ASSERT(a != b);
+ BOOST_ASSERT(a < b);
+ }
+
+ {
+ ulist a;
+ a.push_back(1);
+ a.push_back(2);
+ a.push_back(3);
+ a.push_back(4);
+ a.push_back(5);
+ a.push_back(6);
+ a.push_back(7);
+ a.push_back(8);
+ a.push_back(9);
+ a.push_back(10);
+ a.push_back(11);
+ a.push_back(12);
+
+ BOOST_ASSERT(a[0] == utree(1));
+ BOOST_ASSERT(a[1] == utree(2));
+ BOOST_ASSERT(a[2] == utree(3));
+ BOOST_ASSERT(a[3] == utree(4));
+ BOOST_ASSERT(a[4] == utree(5));
+ BOOST_ASSERT(a[5] == utree(6));
+ BOOST_ASSERT(a[6] == utree(7));
+ BOOST_ASSERT(a[7] == utree(8));
+ BOOST_ASSERT(a[8] == utree(9));
+ BOOST_ASSERT(a[9] == utree(10));
+ BOOST_ASSERT(a[10] == utree(11));
+ BOOST_ASSERT(a[11] == utree(12));
+ }
+
+ return 0;
+}