text: /*=============================================================================
      Copyright (c) 2001-2011 Joel de Guzman
      Copyright (c) 2001-2011 Hartmut Kaiser
      Copyright (c)      2011 Bryce Lelbach
  
      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_DETAIL2)
  #define BOOST_SPIRIT_UTREE_DETAIL2
  
  #if defined(BOOST_MSVC)
  # pragma warning(push)
  # pragma warning(disable: 4800)
  #endif
  
  #include <boost/type_traits/remove_pointer.hpp>
  #include <boost/type_traits/is_pointer.hpp>
  #include <boost/utility/enable_if.hpp>
  #include <boost/throw_exception.hpp>
  #include <boost/iterator/iterator_traits.hpp>
  
  namespace boost { namespace spirit { namespace detail
  {
      inline char& fast_string::info()
      {
          return buff[small_string_size];
      }
  
      inline char fast_string::info() const
      {
          return buff[small_string_size];
      }
  
      inline int fast_string::get_type() const
      {
          return info() >> 1;
      }
  
      inline void fast_string::set_type(int t)
      {
          info() = (t << 1) | (info() & 1);
      }
  
      inline short fast_string::tag() const
      {
          return (int(buff[small_string_size-2]) << 8) + (unsigned char)buff[small_string_size-1];
      }
  
      inline void fast_string::tag(short tag)
      {
          buff[small_string_size-2] = tag >> 8;
          buff[small_string_size-1] = tag & 0xff;
      }
  
      inline bool fast_string::is_heap_allocated() const
      {
          return info() & 1;
      }
  
      inline std::size_t fast_string::size() const
      {
          if (is_heap_allocated())
              return heap.size;
          else
              return max_string_len - buff[max_string_len];
      }
  
      inline char const* fast_string::str() const
      {
          if (is_heap_allocated())
              return heap.str;
          else
              return buff;
      }
  
      template <typename Iterator>
      inline void fast_string::construct(Iterator f, Iterator l)
      {
          unsigned const size = l-f;
          char* str;
          if (size < max_string_len)
          {
              // 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[max_string_len] = static_cast<char>(max_string_len - size);
              info() &= ~0x1;
          }
          else
          {
              // else, store it in the heap
              str = new char[size + 1]; // add one for the null char
              heap.str = str;
              heap.size = size;
              info() |= 0x1;
          }
          for (std::size_t i = 0; i != size; ++i)
          {
              *str++ = *f++;
          }
          *str = '\0'; // add the null char
      }
  
      inline void fast_string::swap(fast_string& other)
      {
          std::swap(*this, other);
      }
  
      inline void fast_string::free()
      {
          if (is_heap_allocated())
          {
              delete [] heap.str;
          }
      }
  
      inline void fast_string::copy(fast_string const& other)
      {
          construct(other.str(), other.str() + other.size());
      }
  
      inline void fast_string::initialize()
      {
          for (std::size_t i = 0; i != buff_size / (sizeof(long)/sizeof(char)); ++i)
              lbuff[i] = 0;
      }
  
      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), prev(0) {}
  
          node_iterator(list::node* node, list::node* prev)
            : node(node), prev(prev) {}
  
      private:
  
          friend class boost::iterator_core_access;
          friend class boost::spirit::utree;
          friend struct boost::spirit::detail::list;
  
          void increment()
          {
              if (node != 0) // not at end
              {
                  prev = node;
                  node = node->next;
              }
          }
  
          void decrement()
          {
              if (prev != 0) // not at begin
              {
                  node = prev;
                  prev = prev->prev;
              }
          }
  
          bool equal(node_iterator const& other) const
          {
              return node == other.node;
          }
  
          typename node_iterator::reference dereference() const
          {
              return node->val;
          }
  
          list::node* node;
          list::node* prev;
      };
  
      template <typename Value>
      class list::node_iterator<boost::reference_wrapper<Value> >
        : public boost::iterator_facade<
              node_iterator<boost::reference_wrapper<Value> >
            , boost::reference_wrapper<Value>
            , boost::bidirectional_traversal_tag>
      {
      public:
  
          node_iterator()
            : node(0), prev(0), curr(nil_node) {}
  
          node_iterator(list::node* node, list::node* prev)
            : node(node), prev(prev), curr(node ? node->val : nil_node) {}
  
      private:
  
          friend class boost::iterator_core_access;
          friend class boost::spirit::utree;
          friend struct boost::spirit::detail::list;
  
          void increment()
          {
              if (node != 0) // not at end
              {
                  prev = node;
                  node = node->next;
                  curr = boost::ref(node ? node->val : nil_node);
              }
          }
  
          void decrement()
          {
              if (prev != 0) // not at begin
              {
                  node = prev;
                  prev = prev->prev;
                  curr = boost::ref(node ? node->val : nil_node);
              }
          }
  
          bool equal(node_iterator const& other) const
          {
              return node == other.node;
          }
  
          typename node_iterator::reference dereference() const
          {
              return curr;
          }
  
          list::node* node;
          list::node* prev;
  
          static Value nil_node;
          mutable boost::reference_wrapper<Value> curr;
      };
  
      template <typename Value>
      Value list::node_iterator<boost::reference_wrapper<Value> >::nil_node = Value();
  
      inline void list::free()
      {
          node* p = first;
          while (p != 0)
          {
              node* next = p->next;
              delete p;
              p = next;
          }
      }
  
      inline void list::copy(list const& other)
      {
          node* p = other.first;
          while (p != 0)
          {
              push_back(p->val);
              p = p->next;
          }
      }
  
      inline void list::default_construct()
      {
          first = last = 0;
          size = 0;
      }
  
      template <typename T, typename Iterator>
      inline void list::insert(T const& val, Iterator pos)
      {
          if (!pos.node)
          {
              push_back(val);
              return;
          }
  
          detail::list::node* new_node =
              new detail::list::node(val, pos.node, pos.node->prev);
  
          if (pos.node->prev)
              pos.node->prev->next = new_node;
          else
              first = new_node;
  
          pos.node->prev = new_node;
          ++size;
      }
  
      template <typename T>
      inline void list::push_front(T const& val)
      {
          detail::list::node* new_node;
          if (first == 0)
          {
              new_node = new detail::list::node(val, 0, 0);
              first = last = new_node;
              ++size;
          }
          else
          {
              new_node = new detail::list::node(val, first, first->prev);
              first->prev = new_node;
              first = new_node;
              ++size;
          }
      }
  
      template <typename T>
      inline void list::push_back(T const& val)
      {
          if (last == 0)
              push_front(val);
          else {
              detail::list::node* new_node =
                  new detail::list::node(val, last->next, last);
              last->next = new_node;
              last = new_node;
              ++size;
          }
      }
  
      inline void list::pop_front()
      {
          BOOST_ASSERT(size != 0);
          if (first == last) // there's only one item
          {
              delete first;
              size = 0;
              first = last = 0;
          }
          else
          {
              node* np = first;
              first = first->next;
              first->prev = 0;
              delete np;
              --size;
          }
      }
  
      inline void list::pop_back()
      {
          BOOST_ASSERT(size != 0);
          if (first == last) // there's only one item
          {
              delete first;
              size = 0;
              first = last = 0;
          }
          else
          {
              node* np = last;
              last = last->prev;
              last->next = 0;
              delete np;
              --size;
          }
      }
  
      inline list::node* list::erase(node* pos)
      {
          BOOST_ASSERT(pos != 0);
          if (pos == first)
          {
              pop_front();
              return first;
          }
          else if (pos == last)
          {
              pop_back();
              return 0;
          }
          else
          {
              node* next(pos->next);
              pos->unlink();
              delete pos;
              --size;
              return next;
          }
      }
  
      ///////////////////////////////////////////////////////////////////////////
      // simple binder for binary visitation (we don't want to bring in the big guns)
      template <typename F, typename X>
      struct bind_impl
      {
          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);
      }
  
      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>,
                  typename UTreeX::const_iterator,
                  typename UTreeX::iterator>::type
              iterator;
  
              typedef boost::iterator_range<iterator> list_range;
              typedef utree_type type;
  
              switch (x.get_type())
              {
                  default:
                      BOOST_THROW_EXCEPTION(
                          bad_type_exception("corrupt utree type", x.get_type()));
                      break;
  
                  case type::invalid_type:
                      return f(invalid);
  
                  case type::nil_type:
                      return f(nil);
  
                  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, 0), iterator(0, x.l.last)));
  
                  case type::range_type:
                      return f(list_range(iterator(x.r.first, 0), iterator(0, x.r.last)));
  
                  case type::string_type:
                      return f(utf8_string_range_type(x.s.str(), x.s.size()));
  
                  case type::string_range_type:
                      return f(utf8_string_range_type(x.sr.first, x.sr.last));
  
                  case type::symbol_type:
                      return f(utf8_symbol_range_type(x.s.str(), x.s.size()));
  
                  case type::binary_type:
                      return f(binary_range_type(x.s.str(), x.s.size()));
  
                  case type::reference_type:
                      return apply(*x.p, f);
  
                  case type::any_type:
                      return f(any_ptr(x.v.p, x.v.i));
  
                  case type::function_type:
                      return f(*x.pf);
              }
          }
  
          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>,
                  typename UTreeX::const_iterator,
                  typename UTreeX::iterator>::type
              iterator;
  
              typedef boost::iterator_range<iterator> list_range;
              typedef utree_type type;
  
              switch (x.get_type())
              {
                  default:
                      BOOST_THROW_EXCEPTION(
                          bad_type_exception("corrupt utree type", x.get_type()));
                      break;
  
                  case type::invalid_type:
                      return visit_impl::apply(y, detail::bind(f, invalid));
  
                  case type::nil_type:
                      return visit_impl::apply(y, detail::bind(f, nil));
  
                  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, 0), 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, 0), iterator(0, x.r.last))));
  
                  case type::string_type:
                      return visit_impl::apply(y, detail::bind(
                          f, utf8_string_range_type(x.s.str(), x.s.size())));
  
                  case type::string_range_type:
                      return visit_impl::apply(y, detail::bind(
                          f, utf8_string_range_type(x.sr.first, x.sr.last)));
  
                  case type::symbol_type:
                      return visit_impl::apply(y, detail::bind(
                          f, utf8_symbol_range_type(x.s.str(), x.s.size())));
  
                  case type::binary_type:
                      return visit_impl::apply(y, detail::bind(
                          f, binary_range_type(x.s.str(), x.s.size())));
  
                  case type::reference_type:
                      return apply(*x.p, y, f);
  
                  case type::any_type:
                      return visit_impl::apply(
                          y, detail::bind(f, any_ptr(x.v.p, x.v.i)));
  
                  case type::function_type:
                      return visit_impl::apply(y, detail::bind(f, *x.pf));
              }
          }
      };
  
      struct index_impl
      {
          static utree& apply(utree& ut, std::size_t i)
          {
              switch (ut.get_type())
              {
                  case utree_type::reference_type:
                      return apply(ut.deref(), i);
                  case utree_type::range_type:
                      return apply(ut.r.first, i);
                  case utree_type::list_type:
                      return apply(ut.l.first, i);
                  default:
                      BOOST_THROW_EXCEPTION(
                          bad_type_exception
                              ("index operation performed on non-list utree type",
                               ut.get_type()));
              }
          }
  
          static utree const& apply(utree const& ut, std::size_t i)
          {
              switch (ut.get_type())
              {
                  case utree_type::reference_type:
                      return apply(ut.deref(), i);
                  case utree_type::range_type:
                      return apply(ut.r.first, i);
                  case utree_type::list_type:
                      return apply(ut.l.first, i);
                  default:
                      BOOST_THROW_EXCEPTION(
                          bad_type_exception
                              ("index operation performed on non-list utree type",
                               ut.get_type()));
              }
          }
  
          static utree& apply(list::node* node, std::size_t i)
          {
              for (; i > 0; --i)
                  node = node->next;
              return node->val;
          }
  
          static utree const& apply(list::node const* node, std::size_t i)
          {
              for (; i > 0; --i)
                  node = node->next;
              return node->val;
          }
      };
  }}}
  
  namespace boost { namespace spirit
  {
      template <typename F>
      stored_function<F>::stored_function(F f)
        : f(f)
      {
      }
  
      template <typename F>
      stored_function<F>::~stored_function()
      {
      }
  
      template <typename F>
      utree stored_function<F>::operator()(utree const& env) const
      {
          return f(env);
      }
  
      template <typename F>
      utree stored_function<F>::operator()(utree& env) const
      {
          return f(env);
      }
  
      template <typename F>
      function_base*
      stored_function<F>::clone() const
      {
          return new stored_function<F>(f);
      }
  
      template <typename F>
      referenced_function<F>::referenced_function(F& f)
        : f(f)
      {
      }
  
      template <typename F>
      referenced_function<F>::~referenced_function()
      {
      }
  
      template <typename F>
      utree referenced_function<F>::operator()(utree const& env) const
      {
          return f(env);
      }
  
      template <typename F>
      utree referenced_function<F>::operator()(utree& env) const
      {
          return f(env);
      }
  
      template <typename F>
      function_base*
      referenced_function<F>::clone() const
      {
          return new referenced_function<F>(f);
      }
  
      inline utree::utree(utree::invalid_type)
      {
          s.initialize();
          set_type(type::invalid_type);
      }
  
      inline utree::utree(utree::nil_type)
      {
          s.initialize();
          set_type(type::nil_type);
      }
  
      inline utree::utree(bool b_)
      {
          s.initialize();
          b = b_;
          set_type(type::bool_type);
      }
  
      inline utree::utree(char c)
      {
          s.initialize();
          // char constructs a single element string
          s.construct(&c, &c+1);
          set_type(type::string_type);
      }
  
      inline utree::utree(unsigned int i_)
      {
          s.initialize();
          i = i_;
          set_type(type::int_type);
      }
  
      inline utree::utree(int i_)
      {
          s.initialize();
          i = i_;
          set_type(type::int_type);
      }
  
      inline utree::utree(double d_)
      {
          s.initialize();
          d = d_;
          set_type(type::double_type);
      }
  
      inline utree::utree(char const* str)
      {
          s.initialize();
          s.construct(str, str + strlen(str));
          set_type(type::string_type);
      }
  
      inline utree::utree(char const* str, std::size_t len)
      {
          s.initialize();
          s.construct(str, str + len);
          set_type(type::string_type);
      }
  
      inline utree::utree(std::string const& str)
      {
          s.initialize();
          s.construct(str.begin(), str.end());
          set_type(type::string_type);
      }
  
      template <typename Base, utree_type::info type_>
      inline utree::utree(basic_string<Base, type_> const& bin)
      {
          s.initialize();
          s.construct(bin.begin(), bin.end());
          set_type(type_);
      }
  
      inline utree::utree(boost::reference_wrapper<utree> ref)
      {
          s.initialize();
          p = ref.get_pointer();
          set_type(type::reference_type);
      }
  
      inline utree::utree(any_ptr const& p)
      {
          s.initialize();
          v.p = p.p;
          v.i = p.i;
          set_type(type::any_type);
      }
  
      inline utree::utree(function_base const& pf_)
      {
          s.initialize();
          pf = pf_.clone();
          set_type(type::function_type);
      }
  
      inline utree::utree(function_base* pf_)
      {
          s.initialize();
          pf = pf_;
          set_type(type::function_type);
      }
  
      template <typename Iter>
      inline utree::utree(boost::iterator_range<Iter> r)
      {
          s.initialize();
  
          assign(r.begin(), r.end());
      }
  
      inline utree::utree(range r, shallow_tag)
      {
          s.initialize();
          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)
      {
          s.initialize();
          this->r.first = r.begin().node;
          this->r.last = r.end().prev;
          set_type(type::range_type);
      }
  
      inline utree::utree(utf8_string_range_type const& str, shallow_tag)
      {
          s.initialize();
          this->sr.first = str.begin();
          this->sr.last = str.end();
          set_type(type::string_range_type);
      }
  
      inline utree::utree(utree const& other)
      {
          s.initialize();
          copy(other);
      }
  
      inline utree::~utree()
      {
          free();
      }
  
      inline utree& utree::operator=(utree const& other)
      {
          if (this != &other)
          {
              free();
              copy(other);
          }
          return *this;
      }
  
      inline utree& utree::operator=(nil_type)
      {
          free();
          set_type(type::nil_type);
          return *this;
      }
  
      inline utree& utree::operator=(bool b_)
      {
          free();
          b = b_;
          set_type(type::bool_type);
          return *this;
      }
  
      inline utree& utree::operator=(char c)
      {
          // char constructs a single element string
          free();
          s.construct(&c, &c+1);
          set_type(type::string_type);
          return *this;
      }
  
      inline utree& utree::operator=(unsigned int i_)
      {
          free();
          i = i_;
          set_type(type::int_type);
          return *this;
      }
  
      inline utree& utree::operator=(int i_)
      {
          free();
          i = i_;
          set_type(type::int_type);
          return *this;
      }
  
      inline utree& utree::operator=(double d_)
      {
          free();
          d = d_;
          set_type(type::double_type);
          return *this;
      }
  
      inline utree& utree::operator=(char const* s_)
      {
          free();
          s.construct(s_, s_ + strlen(s_));
          set_type(type::string_type);
          return *this;
      }
  
      inline utree& utree::operator=(std::string const& s_)
      {
          free();
          s.construct(s_.begin(), s_.end());
          set_type(type::string_type);
          return *this;
      }
  
      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_);
          return *this;
      }
  
      inline utree& utree::operator=(boost::reference_wrapper<utree> ref)
      {
          free();
          p = ref.get_pointer();
          set_type(type::reference_type);
          return *this;
      }
  
      inline utree& utree::operator=(any_ptr const& p)
      {
          free();
          v.p = p.p;
          v.i = p.i;
          set_type(type::any_type);
          return *this;
      }
  
      inline utree& utree::operator=(function_base const& pf_)
      {
          free();
          pf = pf_.clone();
          set_type(type::function_type);
          return *this;
      }
  
      inline utree& utree::operator=(function_base* pf_)
      {
          free();
          pf = pf_;
          set_type(type::function_type);
          return *this;
      }
  
      template <typename Iter>
      inline utree& utree::operator=(boost::iterator_range<Iter> r)
      {
          free();
          assign(r.begin(), r.end());
          return *this;
      }
  
      template <typename F>
      typename boost::result_of<F(utree const&)>::type
      inline utree::visit(utree const& x, F f)
      {
          return detail::visit_impl<utree const>::apply(x, f);
      }
  
      template <typename F>
      typename boost::result_of<F(utree&)>::type
      inline utree::visit(utree& x, F f)
      {
          return detail::visit_impl<utree>::apply(x, f);
      }
  
      template <typename F>
      typename boost::result_of<F(utree const&, utree const&)>::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 boost::result_of<F(utree const&, utree&)>::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 boost::result_of<F(utree&, utree const&)>::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 boost::result_of<F(utree&, utree&)>::type
      inline utree::visit(utree& x, utree& y, F f)
      {
          return detail::visit_impl<utree, utree>::apply(x, y, f);
      }
  
      inline utree::reference get(utree::reference ut, utree::size_type i)
      { return detail::index_impl::apply(ut, i); }
  
      inline utree::const_reference
      get(utree::const_reference ut, utree::size_type i)
      { return detail::index_impl::apply(ut, i); }
  
      template <typename T>
      inline void utree::push_front(T const& val)
      {
          if (get_type() == type::reference_type)
              return p->push_front(val);
  
          ensure_list_type("push_front()");
          l.push_front(val);
      }
  
      template <typename T>
      inline void utree::push_back(T const& val)
      {
          if (get_type() == type::reference_type)
              return p->push_back(val);
  
          ensure_list_type("push_back()");
          l.push_back(val);
      }
  
      template <typename T>
      inline utree::iterator utree::insert(iterator pos, T const& val)
      {
          if (get_type() == type::reference_type)
              return p->insert(pos, val);
  
          ensure_list_type("insert()");
          if (!pos.node)
          {
              l.push_back(val);
              return utree::iterator(l.last, l.last->prev);
          }
          l.insert(val, pos);
          return utree::iterator(pos.node->prev, pos.node->prev->prev);
      }
  
      template <typename T>
      inline void utree::insert(iterator pos, std::size_t n, T const& val)
      {
          if (get_type() == type::reference_type)
              return p->insert(pos, n, val);
  
          ensure_list_type("insert()");
          for (std::size_t i = 0; i != n; ++i)
              insert(pos, val);
      }
  
      template <typename Iterator>
      inline void utree::insert(iterator pos, Iterator first, Iterator last)
      {
          if (get_type() == type::reference_type)
              return p->insert(pos, first, last);
  
          ensure_list_type("insert()");
          while (first != last)
              insert(pos, *first++);
      }
  
      template <typename Iterator>
      inline void utree::assign(Iterator first, Iterator last)
      {
          if (get_type() == type::reference_type)
              return p->assign(first, last);
  
          clear();
          set_type(type::list_type);
  
          while (first != last)
          {
              push_back(*first);
              ++first;
          }
      }
  
      inline void utree::clear()
      {
          if (get_type() == type::reference_type)
              return p->clear();
  
          // clear will always make this an invalid type
          free();
          set_type(type::invalid_type);
      }
  
      inline void utree::pop_front()
      {
          if (get_type() == type::reference_type)
              return p->pop_front();
          if (get_type() != type::list_type)
              BOOST_THROW_EXCEPTION(
                  bad_type_exception
                      ("pop_front() called on non-list utree type",
                       get_type()));
  
          l.pop_front();
      }
  
      inline void utree::pop_back()
      {
          if (get_type() == type::reference_type)
              return p->pop_back();
          if (get_type() != type::list_type)
              BOOST_THROW_EXCEPTION(
                  bad_type_exception
                      ("pop_back() called on non-list utree type",
                       get_type()));
  
          l.pop_back();
      }
  
      inline utree::iterator utree::erase(iterator pos)
      {
          if (get_type() == type::reference_type)
              return p->erase(pos);
          if (get_type() != type::list_type)
              BOOST_THROW_EXCEPTION(
                  bad_type_exception
                      ("erase() called on non-list utree type",
                       get_type()));
  
          detail::list::node* np = l.erase(pos.node);
          return iterator(np, np?np->prev:l.last);
      }
  
      inline utree::iterator utree::erase(iterator first, iterator last)
      {
          if (get_type() == type::reference_type)
              return p->erase(first, last);
  
          if (get_type() != type::list_type)
              BOOST_THROW_EXCEPTION(
                  bad_type_exception
                      ("erase() called on non-list utree type",
                       get_type()));
          while (first != last)
              erase(first++);
          return last;
      }
  
      inline utree::iterator utree::begin()
      {
          if (get_type() == type::reference_type)
              return p->begin();
          else if (get_type() == type::range_type)
              return iterator(r.first, 0);
  
          // otherwise...
          ensure_list_type("begin()");
          return iterator(l.first, 0);
      }
  
      inline utree::iterator utree::end()
      {
          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("end()");
          return iterator(0, l.last);
      }
  
      inline utree::ref_iterator utree::ref_begin()
      {
          if (get_type() == type::reference_type)
              return p->ref_begin();
          else if (get_type() == type::range_type)
              return ref_iterator(r.first, 0);
  
          // otherwise...
          ensure_list_type("ref_begin()");
          return ref_iterator(l.first, 0);
      }
  
      inline utree::ref_iterator utree::ref_end()
      {
          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("ref_end()");
          return ref_iterator(0, l.last);
      }
  
      inline utree::const_iterator utree::begin() const
      {
          if (get_type() == type::reference_type)
              return ((utree const*)p)->begin();
          if (get_type() == type::range_type)
              return const_iterator(r.first, 0);
  
          // otherwise...
          if (get_type() != type::list_type)
              BOOST_THROW_EXCEPTION(
                  bad_type_exception
                      ("begin() called on non-list utree type",
                       get_type()));
  
          return const_iterator(l.first, 0);
      }
  
      inline utree::const_iterator utree::end() const
      {
          if (get_type() == type::reference_type)
              return ((utree const*)p)->end();
          if (get_type() == type::range_type)
              return const_iterator(0, r.first);
  
          // otherwise...
          if (get_type() != type::list_type)
              BOOST_THROW_EXCEPTION(
                  bad_type_exception
                      ("end() called on non-list utree type",
                       get_type()));
  
          return const_iterator(0, l.last);
      }
  
      inline bool utree::empty() const
      {
          type::info t = get_type();
          if (t == type::reference_type)
              return ((utree const*)p)->empty();
  
          if (t == type::range_type)
              return r.first == 0;
          if (t == type::list_type)
              return l.size == 0;
  
          return t == type::nil_type || t == type::invalid_type;
      }
  
      inline std::size_t utree::size() const
      {
          type::info t = get_type();
          if (t == type::reference_type)
              return ((utree const*)p)->size();
  
          if (t == type::range_type)
          {
              // FIXME: O(n), and we have the room to store the size of a range
              // in the union if we compute it when assigned/constructed.
              std::size_t size = 0;
              detail::list::node* n = r.first;
              while (n)
              {
                  n = n->next;
                  ++size;
              }
              return size;
          }
          if (t == type::list_type)
              return l.size;
  
          if (t == type::string_type)
              return s.size();
  
          if (t == type::symbol_type)
              return s.size();
  
          if (t == type::binary_type)
              return s.size();
  
          if (t == type::string_range_type)
              return sr.last - sr.first;
  
          if (t != type::nil_type)
              BOOST_THROW_EXCEPTION(
                  bad_type_exception
                      ("size() called on non-list and non-string utree type",
                       get_type()));
  
          return 0;
      }
  
      inline utree_type::info utree::which() const
      {
          return get_type();
      }
  
      inline utree& utree::front()
      {
          if (get_type() == type::reference_type)
              return p->front();
          if (get_type() == type::range_type)
          {
              if (!r.first)
                  BOOST_THROW_EXCEPTION(
                      empty_exception("front() called on empty utree range"));
              return r.first->val;
          }
  
          // otherwise...
          if (get_type() != type::list_type)
              BOOST_THROW_EXCEPTION(
                  bad_type_exception
                      ("front() called on non-list utree type", get_type()));
          else if (!l.first)
              BOOST_THROW_EXCEPTION(
                  empty_exception("front() called on empty utree list"));
  
          return l.first->val;
      }
  
      inline utree& utree::back()
      {
          if (get_type() == type::reference_type)
              return p->back();
          if (get_type() == type::range_type)
          {
              if (!r.last)
                  BOOST_THROW_EXCEPTION(
                      empty_exception("back() called on empty utree range"));
              return r.last->val;
          }
  
          // otherwise...
          if (get_type() != type::list_type)
              BOOST_THROW_EXCEPTION(
                  bad_type_exception
                      ("back() called on non-list utree type", get_type()));
          else if (!l.last)
              BOOST_THROW_EXCEPTION(
                  empty_exception("back() called on empty utree list"));
  
          return l.last->val;
      }
  
      inline utree const& utree::front() const
      {
          if (get_type() == type::reference_type)
              return ((utree const*)p)->front();
          if (get_type() == type::range_type)
          {
              if (!r.first)
                  BOOST_THROW_EXCEPTION(
                      empty_exception("front() called on empty utree range"));
              return r.first->val;
          }
  
          // otherwise...
          if (get_type() != type::list_type)
              BOOST_THROW_EXCEPTION(
                  bad_type_exception
                      ("front() called on non-list utree type", get_type()));
          else if (!l.first)
              BOOST_THROW_EXCEPTION(
                  empty_exception("front() called on empty utree list"));
  
          return l.first->val;
      }
  
      inline utree const& utree::back() const
      {
          if (get_type() == type::reference_type)
              return ((utree const*)p)->back();
          if (get_type() == type::range_type)
          {
              if (!r.last)
                  BOOST_THROW_EXCEPTION(
                      empty_exception("back() called on empty utree range"));
              return r.last->val;
          }
  
          // otherwise...
          if (get_type() != type::list_type)
              BOOST_THROW_EXCEPTION(
                  bad_type_exception
                      ("back() called on non-list utree type", get_type()));
          else if (!l.last)
              BOOST_THROW_EXCEPTION(
                  empty_exception("back() called on empty utree list"));
  
          return l.last->val;
      }
  
      inline void utree::swap(utree& other)
      {
          s.swap(other.s);
      }
  
      inline utree::type::info utree::get_type() const
      {
          // the fast string holds the type info
          return static_cast<utree::type::info>(s.get_type());
      }
  
      inline void utree::set_type(type::info t)
      {
          // the fast string holds the type info
          s.set_type(t);
      }
  
      inline void utree::ensure_list_type(char const* failed_in)
      {
          type::info t = get_type();
          if (t == type::invalid_type)
          {
              set_type(type::list_type);
              l.default_construct();
          }
          else if (get_type() != type::list_type)
          {
              std::string msg = failed_in;
              msg += "called on non-list and non-invalid utree type";
              BOOST_THROW_EXCEPTION(bad_type_exception(msg.c_str(), get_type()));
          }
      }
  
      inline void utree::free()
      {
          switch (get_type())
          {
              case type::binary_type:
              case type::symbol_type:
              case type::string_type:
                  s.free();
                  break;
              case type::list_type:
                  l.free();
                  break;
              case type::function_type:
                  delete pf;
                  break;
              default:
                  break;
          };
          s.initialize();
      }
  
      inline void utree::copy(utree const& other)
      {
          set_type(other.get_type());
          switch (other.get_type())
          {
              default:
                  BOOST_THROW_EXCEPTION(
                      bad_type_exception("corrupt utree type", other.get_type()));
                  break;
              case type::invalid_type:
              case type::nil_type:
                  s.tag(other.s.tag());
                  break;
              case type::bool_type:
                  b = other.b;
                  s.tag(other.s.tag());
                  break;
              case type::int_type:
                  i = other.i;
                  s.tag(other.s.tag());
                  break;
              case type::double_type:
                  d = other.d;
                  s.tag(other.s.tag());
                  break;
              case type::reference_type:
                  p = other.p;
                  s.tag(other.s.tag());
                  break;
              case type::any_type:
                  v = other.v;
                  s.tag(other.s.tag());
                  break;
              case type::range_type:
                  r = other.r;
                  s.tag(other.s.tag());
                  break;
              case type::string_range_type:
                  sr = other.sr;
                  s.tag(other.s.tag());
                  break;
              case type::function_type:
                  pf = other.pf->clone();
                  s.tag(other.s.tag());
                  break;
              case type::string_type:
              case type::symbol_type:
              case type::binary_type:
                  s.copy(other.s);
                  s.tag(other.s.tag());
                  break;
              case type::list_type:
                  l.copy(other.l);
                  s.tag(other.s.tag());
                  break;
          }
      }
  
      template <typename T>
      struct is_iterator_range
        : boost::mpl::false_
      {};
  
      template <typename Iterator>
      struct is_iterator_range<boost::iterator_range<Iterator> >
        : boost::mpl::true_
      {};
  
      template <typename To>
      struct utree_cast
      {
          typedef To result_type;
  
          template <typename From>
          To dispatch(From const& val, boost::mpl::true_) const
          {
              return To(val); // From is convertible to To
          }
  
          template <typename From>
          To dispatch(From const&, boost::mpl::false_) const
          {
              // From is NOT convertible to To !!!
              throw std::bad_cast();
              return To();
          }
  
          template <typename From>
          To operator()(From const& val) const
          {
              // boost::iterator_range has a templated constructor, accepting
              // any argument and hence any type is 'convertible' to it.
              typedef typename boost::mpl::eval_if<
                  is_iterator_range<To>
                , boost::is_same<From, To>, boost::is_convertible<From, To>
              >::type is_convertible;
              return dispatch(val, is_convertible());
          }
      };
  
      template <typename T>
      struct utree_cast<T*>
      {
          typedef T* result_type;
  
          template <typename From>
          T* operator()(From const&) const
          {
              // From is NOT convertible to T !!!
              throw std::bad_cast();
              return 0;
          }
  
          T* operator()(any_ptr const& p) const
          {
              return p.get<T*>();
          }
      };
  
      template <typename T>
      inline T utree::get() const
      {
          return utree::visit(*this, utree_cast<T>());
      }
  
      inline utree& utree::deref()
      {
          return (get_type() == type::reference_type) ? *p : *this;
      }
  
      inline utree const& utree::deref() const
      {
          return (get_type() == type::reference_type) ? *p : *this;
      }
  
      inline short utree::tag() const
      {
          return s.tag();
      }
  
      inline void utree::tag(short tag)
      {
          s.tag(tag);
      }
  
      inline utree utree::eval(utree const& env) const
      {
          if (get_type() == type::reference_type)
              return deref().eval(env);
  
          if (get_type() != type::function_type)
              BOOST_THROW_EXCEPTION(
                  bad_type_exception(
                      "eval() called on non-function utree type", get_type()));
          return (*pf)(env);
      }
  
      inline utree utree::eval(utree& env) const
      {
          if (get_type() == type::reference_type)
              return deref().eval(env);
  
          if (get_type() != type::function_type)
              BOOST_THROW_EXCEPTION(
                  bad_type_exception(
                      "eval() called on non-function utree type", get_type()));
          return (*pf)(env);
      }
  
      inline utree utree::operator() (utree const& env) const
      {
          return eval(env);
      }
  
      inline utree utree::operator() (utree& env) const
      {
          return eval(env);
      }
  }}
  
  #if defined(BOOST_MSVC)
  # pragma warning(pop)
  #endif
  #endif
  