/*=============================================================================
    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.first, 0); // begin();
        }
        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