Boost logo

Boost-Commit :

Subject: [Boost-commit] svn:boost r60767 - in trunk/libs/spirit/example/scheme: . detail
From: joel_at_[hidden]
Date: 2010-03-22 10:19:32


Author: djowel
Date: 2010-03-22 10:19:31 EDT (Mon, 22 Mar 2010)
New Revision: 60767
URL: http://svn.boost.org/trac/boost/changeset/60767

Log:
best implementation so far. done.
Text files modified:
   trunk/libs/spirit/example/scheme/detail/utree_detail1.hpp | 30 +------
   trunk/libs/spirit/example/scheme/detail/utree_detail2.hpp | 154 +++++++++++++++++++-------------------
   trunk/libs/spirit/example/scheme/sexpr.hpp | 19 ----
   trunk/libs/spirit/example/scheme/utree.hpp | 135 ++++++++++++++++++++++++++++-------
   trunk/libs/spirit/example/scheme/utree_test.cpp | 3
   5 files changed, 194 insertions(+), 147 deletions(-)

Modified: trunk/libs/spirit/example/scheme/detail/utree_detail1.hpp
==============================================================================
--- trunk/libs/spirit/example/scheme/detail/utree_detail1.hpp (original)
+++ trunk/libs/spirit/example/scheme/detail/utree_detail1.hpp 2010-03-22 10:19:31 EDT (Mon, 22 Mar 2010)
@@ -21,25 +21,6 @@
     struct index_impl;
 
     ///////////////////////////////////////////////////////////////////////////
- // Our utree can store these types. This enum tells us what type
- // of data is stored in utree's discriminated union.
- ///////////////////////////////////////////////////////////////////////////
- struct utree_type
- {
- enum info
- {
- nil_type,
- bool_type,
- int_type,
- double_type,
- string_type,
- binary_type,
- list_type,
- reference_type
- };
- };
-
- ///////////////////////////////////////////////////////////////////////////
     // 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
@@ -99,7 +80,10 @@
                 / sizeof(char);
 
         static std::size_t const
- small_string_size = buff_size-(sizeof(char)*2);
+ small_string_size = buff_size-sizeof(char);
+
+ static std::size_t const
+ max_string_len = small_string_size - 1;
 
         struct heap_store
         {
@@ -113,10 +97,8 @@
             heap_store heap;
         };
 
- utree_type::info get_type() const;
- void set_type(utree_type::info t);
- int get_subtype() const;
- void set_subtype(int t);
+ int get_type() const;
+ void set_type(int t);
         bool is_heap_allocated() const;
 
         std::size_t size() const;

Modified: trunk/libs/spirit/example/scheme/detail/utree_detail2.hpp
==============================================================================
--- trunk/libs/spirit/example/scheme/detail/utree_detail2.hpp (original)
+++ trunk/libs/spirit/example/scheme/detail/utree_detail2.hpp 2010-03-22 10:19:31 EDT (Mon, 22 Mar 2010)
@@ -19,29 +19,19 @@
         return buff[small_string_size];
     }
 
- inline utree_type::info fast_string::get_type() const
+ inline int fast_string::get_type() const
     {
- return static_cast<utree_type::info>((info() & 0x0F) >> 1);
+ return info() >> 1;
     }
 
- inline void fast_string::set_type(utree_type::info t)
+ inline void fast_string::set_type(int t)
     {
- info() = (static_cast<char>(t) << 1) | (info() & 0xF1);
- }
-
- inline int fast_string::get_subtype() const
- {
- return info() >> 4;
- }
-
- inline void fast_string::set_subtype(int t)
- {
- info() = (t << 4) | (info() & 0x0F);
+ info() = (t << 1) | (info() & 1);
     }
 
     inline bool fast_string::is_heap_allocated() const
     {
- return info() & 0x01;
+ return info() & 1;
     }
 
     inline std::size_t fast_string::size() const
@@ -49,7 +39,7 @@
         if (is_heap_allocated())
             return heap.size;
         else
- return small_string_size - buff[small_string_size - 1];
+ return max_string_len - buff[small_string_size - 1];
     }
 
     inline char const* fast_string::str() const
@@ -70,13 +60,11 @@
             // if it fits, store it in-situ; small_string_size minus the length
             // of the string is placed in buff[small_string_size - 1]
             str = buff;
- buff[small_string_size - 1] = small_string_size - size;
+ buff[small_string_size - 1] = max_string_len - size;
             info() &= ~0x1;
         }
         else
         {
- BOOST_ASSERT(size < 200);
-
             // else, store it in the heap
             str = new char[size + 1]; // add one for the null char
             heap.str = str;
@@ -355,14 +343,16 @@
         template <typename T>
         bool operator()(const T& a, const T& b) const
         {
- // This code works for lists and strings as well
+ // This code works for lists
             return a == b;
         }
 
- template <typename Base>
- bool operator()(binary<Base> const& a, binary<Base> const& b) const
+ template <typename Base, utree_type::info type_>
+ bool operator()(
+ basic_string<Base, type_> const& a,
+ basic_string<Base, type_> const& b) const
         {
- return false;
+ return static_cast<Base const&>(a) == static_cast<Base const&>(b);
         }
 
         bool operator()(nil, nil) const
@@ -399,15 +389,16 @@
         template <typename T>
         bool operator()(const T& a, const T& b) const
         {
- // This code works for lists and strings as well
+ // This code works for lists
             return a < b;
         }
 
- template <typename Base>
- bool operator()(binary<Base> const& a, binary<Base> const& b) const
+ template <typename Base, utree_type::info type_>
+ bool operator()(
+ basic_string<Base, type_> const& a,
+ basic_string<Base, type_> const& b) const
         {
- BOOST_ASSERT(false);
- return false; // no less than comparison for binary
+ return static_cast<Base const&>(a) < static_cast<Base const&>(b);
         }
 
         bool operator()(nil, nil) const
@@ -440,54 +431,48 @@
             out << (b ? "true" : "false");
         }
 
- template <typename Base>
- void operator()(binary<Base> b) const
+ void operator()(binary_range const& b) const
         {
             out << "b";
             out.width(2);
             out.fill('0');
 
- typedef typename Base::const_iterator iterator;
+ typedef binary_range::const_iterator iterator;
             for (iterator i = b.begin(); i != b.end(); ++i)
                 out << std::hex << int((unsigned char)*i);
             out << std::dec;
         }
 
- template <typename Range> // for lists
- void print_string_or_list(Range range, boost::mpl::false_) const
+ void operator()(utf8_string_range const& str) const
         {
- typedef typename Range::const_iterator iterator;
- (*this)('(');
- for (iterator i = range.begin(); i != range.end(); ++i)
- {
- if (i != range.begin())
- (*this)(' ');
- scheme::utree::visit(*i, *this);
- }
- (*this)(')');
+ typedef utf8_string_range::const_iterator iterator;
+ iterator i = str.begin();
+ out << '"';
+ for (; i != str.end(); ++i)
+ out << *i;
+ out << '"';
         }
 
- template <typename Range> // for strings
- void print_string_or_list(Range range, boost::mpl::true_) const
+ void operator()(utf8_symbol_range const& str) const
         {
- typedef typename Range::const_iterator iterator;
- iterator i = range.begin();
- bool const is_symbol = *i == '\0'; // a 0 byte at the beginning signifies a symbol
- if (!is_symbol)
- out << '"';
- else
- ++i;
- for (; i != range.end(); ++i)
+ typedef utf8_symbol_range::const_iterator iterator;
+ iterator i = str.begin();
+ for (; i != str.end(); ++i)
                 out << *i;
- if (!is_symbol)
- out << '"';
         }
 
         template <typename Iterator>
         void operator()(boost::iterator_range<Iterator> const& range) const
         {
- // This code works for both strings and lists
- print_string_or_list(range, boost::is_pointer<Iterator>());
+ typedef typename boost::iterator_range<Iterator>::const_iterator iterator;
+ (*this)('(');
+ for (iterator i = range.begin(); i != range.end(); ++i)
+ {
+ if (i != range.begin())
+ (*this)(' ');
+ scheme::utree::visit(*i, *this);
+ }
+ (*this)(')');
         }
     };
 
@@ -499,38 +484,44 @@
         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 boost::iterator_range<string_type> string_range;
- typedef detail::utree_type type;
+ typedef utree_type type;
 
             switch (x.get_type())
             {
                 default:
                     BOOST_ASSERT(false); // can't happen
+
                 case type::nil_type:
                     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)));
+
                 case type::string_type:
- return f(string_range(x.s.str(), x.s.str() + x.s.size()));
+ return f(utf8_string_range(x.s.str(), x.s.size()));
+
+ case type::symbol_type:
+ return f(utf8_symbol_range(x.s.str(), x.s.size()));
+
                 case type::binary_type:
                     return f(binary_range(x.s.str(), x.s.size()));
+
                 case type::reference_type:
                     return apply(*x.p, f);
             }
@@ -541,42 +532,49 @@
         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 boost::iterator_range<string_type> string_range;
- typedef detail::utree_type type;
+ typedef utree_type type;
 
             switch (x.get_type())
             {
                 default:
                     BOOST_ASSERT(false); // can't happen
+
                 case type::nil_type:
                     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))));
+
                 case type::string_type:
                     return visit_impl::apply(y, detail::bind(
- f, string_range(x.s.str(), x.s.str() + x.s.size())));
+ f, utf8_string_range(x.s.str(), x.s.size())));
+
+ case type::symbol_type:
+ return visit_impl::apply(y, detail::bind(
+ f, utf8_symbol_range(x.s.str(), x.s.size())));
+
                 case type::binary_type:
                     return visit_impl::apply(y, detail::bind(
                         f, binary_range(x.s.str(), x.s.size())));
+
                 case type::reference_type:
                     return apply(*x.p, y, f);
             }
@@ -646,11 +644,11 @@
         set_type(type::string_type);
     }
 
- template <typename Base>
- inline utree::utree(binary<Base> const& bin)
+ template <typename Base, utree_type::info type_>
+ inline utree::utree(basic_string<Base, type_> const& bin)
     {
         s.construct(bin.begin(), bin.end());
- set_type(type::binary_type);
+ set_type(type_);
     }
 
     inline utree::utree(boost::reference_wrapper<utree> ref)
@@ -727,12 +725,12 @@
         return *this;
     }
 
- template <typename Base>
- inline utree& utree::operator=(binary<Base> const& bin)
+ template <typename Base, utree_type::info type_>
+ inline utree& utree::operator=(basic_string<Base, type_> const& bin)
     {
         free();
         s.construct(bin.begin(), bin.end());
- set_type(type::binary_type);
+ set_type(type_);
         return *this;
     }
 
@@ -1039,7 +1037,7 @@
     inline utree::type::info utree::get_type() const
     {
         // the fast string holds the type info
- return s.get_type();
+ return static_cast<utree::type::info>(s.get_type());
     }
 
     inline void utree::set_type(type::info t)
@@ -1066,6 +1064,7 @@
         switch (get_type())
         {
             case type::binary_type:
+ case type::symbol_type:
             case type::string_type:
                 s.free();
                 break;
@@ -1097,6 +1096,7 @@
                 p = other.p;
                 break;
             case type::string_type:
+ case type::symbol_type:
             case type::binary_type:
                 s.copy(other.s);
                 break;

Modified: trunk/libs/spirit/example/scheme/sexpr.hpp
==============================================================================
--- trunk/libs/spirit/example/scheme/sexpr.hpp (original)
+++ trunk/libs/spirit/example/scheme/sexpr.hpp 2010-03-22 10:19:31 EDT (Mon, 22 Mar 2010)
@@ -75,20 +75,6 @@
             }
         };
 
- struct push_symbol
- {
- template <typename S, typename C>
- struct result { typedef void type; };
-
- void operator()(std::string& utf8, char ch) const
- {
- if (utf8.size() == 0)
- utf8 += '\0'; // mark a symbol with prefix 0
- // (a 0 byte at the beginning signifies a symbol)
- utf8 += ch;
- }
- };
-
         struct push_esc
         {
             template <typename S, typename C>
@@ -146,7 +132,6 @@
         {
             real_parser<double, strict_real_policies<double> > strict_double;
             uint_parser<unsigned char, 16, 2, 2> hex2;
- function<detail::push_symbol> push_symbol;
 
             start = atom | list;
 
@@ -160,7 +145,7 @@
                     ;
 
             char const* exclude = " ();\"\0-\31\127";
- symbol = +lexeme[~char_(exclude)] [push_symbol(_val, _1)];
+ symbol = lexeme[+(~char_(exclude))];
 
             number = strict_double [_val = _1]
                     | lexeme[no_case["0x"] >> hex] [_val = _1]
@@ -173,7 +158,7 @@
 
         rule<Iterator, white_space<Iterator>, utree()> start, list;
         rule<Iterator, utree()> atom, number;
- rule<Iterator, std::string()> symbol;
+ rule<Iterator, utf8_symbol()> symbol;
         rule<Iterator, binary_string()> byte_str;
         scheme::string<Iterator> string;
     };

Modified: trunk/libs/spirit/example/scheme/utree.hpp
==============================================================================
--- trunk/libs/spirit/example/scheme/utree.hpp (original)
+++ trunk/libs/spirit/example/scheme/utree.hpp 2010-03-22 10:19:31 EDT (Mon, 22 Mar 2010)
@@ -23,10 +23,105 @@
 
 namespace scheme
 {
+ ///////////////////////////////////////////////////////////////////////////
+ // Our utree can store these types. This enum tells us what type
+ // of data is stored in utree's discriminated union.
+ ///////////////////////////////////////////////////////////////////////////
+ struct utree_type
+ {
+ enum info
+ {
+ nil_type,
+ bool_type,
+ int_type,
+ double_type,
+ string_type,
+ symbol_type,
+ binary_type,
+ list_type,
+ reference_type
+ };
+ };
+
+ ///////////////////////////////////////////////////////////////////////////
+ // The nil type
+ ///////////////////////////////////////////////////////////////////////////
     struct nil {};
 
- template <typename Base>
- struct binary;
+ ///////////////////////////////////////////////////////////////////////////
+ // A typed string with parametric Base storage. The storage can be any
+ // range or (stl container) of chars.
+ ///////////////////////////////////////////////////////////////////////////
+ template <typename Base, utree_type::info type_>
+ struct basic_string : Base
+ {
+ static utree_type::info const type = type_;
+
+ basic_string()
+ : Base() {}
+
+ basic_string(Base const& base)
+ : Base(base) {}
+
+ template <typename Iterator>
+ basic_string(Iterator bits, std::size_t len)
+ : Base(bits, bits + len) {}
+
+ template <typename Iterator>
+ basic_string(Iterator first, Iterator last)
+ : Base(first, last) {}
+
+ basic_string& operator=(basic_string const& other)
+ {
+ Base::operator=(other);
+ return *this;
+ }
+
+ basic_string& operator=(Base const& other)
+ {
+ Base::operator=(other);
+ return *this;
+ }
+ };
+
+ ///////////////////////////////////////////////////////////////////////////
+ // Binary string
+ ///////////////////////////////////////////////////////////////////////////
+ typedef basic_string<
+ boost::iterator_range<char const*>,
+ utree_type::binary_type>
+ binary_range;
+
+ typedef basic_string<
+ std::string,
+ utree_type::binary_type>
+ binary_string;
+
+ ///////////////////////////////////////////////////////////////////////////
+ // Our UTF-8 string
+ ///////////////////////////////////////////////////////////////////////////
+ typedef basic_string<
+ boost::iterator_range<char const*>,
+ utree_type::string_type>
+ utf8_string_range;
+
+ typedef basic_string<
+ std::string,
+ utree_type::string_type>
+ utf8_string;
+
+ ///////////////////////////////////////////////////////////////////////////
+ // Our UTF-8 symbol (for identifiers)
+ ///////////////////////////////////////////////////////////////////////////
+ typedef basic_string<
+ boost::iterator_range<char const*>,
+ utree_type::symbol_type>
+ utf8_symbol_range;
+
+ typedef basic_string<
+ std::string,
+ utree_type::symbol_type>
+ utf8_symbol;
 
     ///////////////////////////////////////////////////////////////////////////
     // The main utree (Universal Tree) class
@@ -36,6 +131,7 @@
     // - an integer
     // - a double
     // - a string
+ // - a symbol (identifier)
     // - binary data
     // - a (doubly linked) list of utree
     // - a reference to a utree
@@ -56,6 +152,9 @@
         typedef std::ptrdiff_t difference_type;
         typedef std::size_t size_type;
 
+ typedef boost::iterator_range<iterator> range;
+ typedef boost::iterator_range<const_iterator> const_range;
+
         utree();
         explicit utree(bool b);
         explicit utree(unsigned int i);
@@ -64,11 +163,11 @@
         explicit utree(char const* str);
         explicit utree(char const* str, std::size_t len);
         explicit utree(std::string const& str);
-
- template <typename Base>
- explicit utree(binary<Base> const& bin);
         explicit utree(boost::reference_wrapper<utree> ref);
 
+ template <typename Base, utree_type::info type_>
+ explicit utree(basic_string<Base, type_> const& bin);
+
         utree(utree const& other);
         ~utree();
 
@@ -79,11 +178,11 @@
         utree& operator=(double d);
         utree& operator=(char const* s);
         utree& operator=(std::string const& s);
-
- template <typename Base>
- utree& operator=(binary<Base> const& bin);
         utree& operator=(boost::reference_wrapper<utree> ref);
 
+ template <typename Base, utree_type::info type_>
+ utree& operator=(basic_string<Base, type_> const& bin);
+
         template <typename F>
         typename F::result_type
         static visit(utree const& x, F f);
@@ -152,7 +251,7 @@
 
     private:
 
- typedef detail::utree_type type;
+ typedef utree_type type;
 
         template <typename UTreeX, typename UTreeY>
         friend struct detail::visit_impl;
@@ -186,24 +285,6 @@
     bool operator<=(utree const& a, utree const& b);
     bool operator>=(utree const& a, utree const& b);
     std::ostream& operator<<(std::ostream& out, utree const& x);
-
- template <typename Base>
- struct binary : Base
- {
- binary()
- : Base() {}
-
- template <typename Iterator>
- binary(Iterator bits, std::size_t len)
- : Base(bits, bits + len) {}
-
- template <typename Iterator>
- binary(Iterator first, Iterator last)
- : Base(first, last) {}
- };
-
- typedef binary<boost::iterator_range<char const*> > binary_range;
- typedef binary<std::string> binary_string;
 }
 
 #include "detail/utree_detail2.hpp"

Modified: trunk/libs/spirit/example/scheme/utree_test.cpp
==============================================================================
--- trunk/libs/spirit/example/scheme/utree_test.cpp (original)
+++ trunk/libs/spirit/example/scheme/utree_test.cpp 2010-03-22 10:19:31 EDT (Mon, 22 Mar 2010)
@@ -5,7 +5,6 @@
 int main()
 {
     using scheme::utree;
- using scheme::ulist;
     using ::detail::println;
 
     {
@@ -68,7 +67,7 @@
         println(std::cout, val);
         val3.swap(val);
         println(std::cout, val);
- val.push_back("Ba Ba Black Sheep");
+ val.push_back("another string");
         println(std::cout, val);
         val.pop_front();
         println(std::cout, val);


Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk