/*=============================================================================
    Copyright (c) 2001-2010 Joel de Guzman
    Copyright (c) 2001-2010 Hartmut Kaiser

    Distributed under the Boost Software License, Version 1.0. (See accompanying
    file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
=============================================================================*/
#if !defined(BOOST_SPIRIT_UTREE)
#define BOOST_SPIRIT_UTREE

#include <cstddef>
#include <algorithm>
#include <string>
#include <ostream>
#include <typeinfo>

#include <boost/assert.hpp>
#include <boost/noncopyable.hpp>
#include <boost/iterator/iterator_facade.hpp>
#include <boost/range/iterator_range.hpp>
#include <boost/type_traits/remove_pointer.hpp>
#include <boost/type_traits/is_polymorphic.hpp>
#include <boost/utility/enable_if.hpp>
#include <boost/ref.hpp>

#include <utree/detail/utree_detail1.hpp>

#if defined(BOOST_MSVC)
# pragma warning(push)
# pragma warning(disable: 4804)
# pragma warning(disable: 4805)
# pragma warning(disable: 4244)
#endif

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,
            string_range_type,
            symbol_type,
            binary_type,
            list_type,
            range_type,
            reference_type,
            any_type,
            function_type
        };
    };

    ///////////////////////////////////////////////////////////////////////////
    // The nil type
    ///////////////////////////////////////////////////////////////////////////
    struct nil {};

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

    ///////////////////////////////////////////////////////////////////////////
    // Our function type
    ///////////////////////////////////////////////////////////////////////////
    class utree;
    class scope;

    struct function_base
    {
        virtual ~function_base() {};
        virtual utree operator()(scope const& env) const = 0;
        virtual function_base* clone() const = 0;
    };

    template <typename F>
    struct stored_function : function_base
    {
        F f;
        stored_function(F f = F());
        virtual ~stored_function();
        virtual utree operator()(scope const& env) const;
        virtual function_base* clone() const;
    };

    ///////////////////////////////////////////////////////////////////////////
    // Shallow tag. Instructs utree to hold an iterator_range
    // as-is without deep copying the range.
    ///////////////////////////////////////////////////////////////////////////
    struct shallow_tag {};
    shallow_tag const shallow = {};

    ///////////////////////////////////////////////////////////////////////////
    // A void* plus type_info
    ///////////////////////////////////////////////////////////////////////////
    class any_ptr
    {
    public:

        template <typename Ptr>
        typename boost::disable_if<
            boost::is_polymorphic<
                typename boost::remove_pointer<Ptr>::type>,
            Ptr>::type
        get() const
        {
            if (*i == typeid(Ptr))
            {
                return static_cast<Ptr>(p);
            }
            throw std::bad_cast();
        }

        template <typename T>
        any_ptr(T* p)
          : p(p), i(&typeid(T*))
        {}

        friend bool operator==(any_ptr const& a, any_ptr const& b)
        {
            return (a.p == b.p) && (*a.i == *b.i);
        }

    private:

        // constructor is private
        any_ptr(void* p, std::type_info const* i)
          : p(p), i(i) {}

        template <typename UTreeX, typename UTreeY>
        friend struct detail::visit_impl;

        friend class utree;

        void* p;
        std::type_info const* i;
    };

    ///////////////////////////////////////////////////////////////////////////
    // The main utree (Universal Tree) class
    // The utree is a hierarchical, dynamic type that can store:
    //  - a nil
    //  - a bool
    //  - an integer
    //  - a double
    //  - a string
    //  - a string range
    //  - a symbol (identifier)
    //  - binary data
    //  - a (doubly linked) list of utree
    //  - an iterator_range of list::iterator
    //  - a reference to a utree
    //  - a pointer or reference to any type
    //  - a function
    //
    // The utree has minimal memory footprint. The data structure size is
    // 16 bytes on a 32-bit platform. Being a container of itself, it can
    // represent tree structures.
    ///////////////////////////////////////////////////////////////////////////
    class utree
    {
    public:

        typedef utree value_type;
        typedef detail::list::node_iterator<utree> iterator;
        typedef detail::list::node_iterator<utree const> const_iterator;
        typedef detail::list::node_iterator<boost::reference_wrapper<utree> >
            ref_iterator;
        typedef utree& reference;
        typedef utree const& const_reference;
        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();
        utree(bool b);
        utree(char c);
        utree(unsigned int i);
        utree(int i);
        utree(double d);
        utree(char const* str);
        utree(char const* str, std::size_t len);
        utree(std::string const& str);
        utree(boost::reference_wrapper<utree> ref);
        utree(any_ptr const& p);

        template <typename Iter>
        utree(boost::iterator_range<Iter> r);
        utree(range r, shallow_tag);
        utree(const_range r, shallow_tag);
        utree(utf8_string_range const& str, shallow_tag);

        template <typename F>
        utree(stored_function<F> const& pf);

        template <typename Base, utree_type::info type_>
        utree(basic_string<Base, type_> const& str);

        utree(utree const& other);
        ~utree();

        utree& operator=(utree const& other);
        utree& operator=(bool b);
        utree& operator=(unsigned int i);
        utree& operator=(int i);
        utree& operator=(double d);
        utree& operator=(char const* s);
        utree& operator=(std::string const& s);
        utree& operator=(boost::reference_wrapper<utree> ref);

        template <typename F>
        utree& operator=(stored_function<F> const& pf);

        template <typename Iter>
        utree& operator=(boost::iterator_range<Iter> r);

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

        template <typename F>
        typename F::result_type
        static visit(utree& x, F f);

        template <typename F>
        typename F::result_type
        static visit(utree const& x, utree const& y, F f);

        template <typename F>
        typename F::result_type
        static visit(utree& x, utree const& y, F f);

        template <typename F>
        typename F::result_type
        static visit(utree const& x, utree& y, F f);

        template <typename F>
        typename F::result_type
        static visit(utree& x, utree& y, F f);

        template <typename T>
        void push_back(T const& val);

        template <typename T>
        void push_front(T const& val);

        template <typename T>
        iterator insert(iterator pos, T const& x);

        template <typename T>
        void insert(iterator pos, std::size_t, T const& x);

        template <typename Iter>
        void insert(iterator pos, Iter first, Iter last);

        template <typename Iter>
        void assign(Iter first, Iter last);

        void clear();
        void pop_front();
        void pop_back();
        iterator erase(iterator pos);
        iterator erase(iterator first, iterator last);

        utree& front();
        utree& back();
        utree const& front() const;
        utree const& back() const;

        utree& operator[](std::size_t i);
        utree const& operator[](std::size_t i) const;

        void swap(utree& other);

        iterator begin();
        iterator end();
        const_iterator begin() const;
        const_iterator end() const;

        ref_iterator ref_begin();
        ref_iterator ref_end();

        bool empty() const;
        std::size_t size() const;

        utree_type::info which() const;

        template <typename T>
        T get() const;

        utree& deref();
        utree const& deref() const;

        short tag() const;
        void tag(short tag);

        utree eval(scope const& env) const;

    private:

        typedef utree_type type;

        template <typename UTreeX, typename UTreeY>
        friend struct detail::visit_impl;
        friend struct detail::index_impl;

        template <typename T>
        friend struct detail::get_impl;

        type::info get_type() const;
        void set_type(type::info t);
        void ensure_list_type();
        void free();
        void copy(utree const& other);

        union
        {
            detail::fast_string s;
            detail::list l;
            detail::range r;
            detail::string_range sr;
            detail::void_ptr v;
            bool b;
            int i;
            double d;
            utree* p;
            function_base* pf;
        };
    };

    ///////////////////////////////////////////////////////////////////////////
    // The scope
    ///////////////////////////////////////////////////////////////////////////
    class scope : public boost::iterator_range<utree*>
    {
    public:

        scope(utree* first = 0,
            utree* last = 0,
            scope const* parent = 0)
          : boost::iterator_range<utree*>(first, last),
            parent(parent),
            depth(parent? parent->depth + 1 : 0)
        {}

        scope const* outer() const { return parent; }
        int level() const { return depth; }

    private:

        scope const* parent;
        int depth;
    };
}

#if defined(BOOST_MSVC)
# pragma warning(pop)
#endif

#include <utree/detail/utree_detail2.hpp>

// $$$ move this in its own file $$$
namespace scheme { namespace utree_functions
{
    ///////////////////////////////////////////////////////////////////////////
    // Extra functions
    ///////////////////////////////////////////////////////////////////////////
    inline utree rest(utree& x)
    {
        utree::iterator i = x.begin(); ++i;
        return utree(utree::range(i, x.end()), shallow);
    }

    inline utree rest(utree const& x)
    {
        utree::const_iterator i = x.begin(); ++i;
        return utree(utree::const_range(i, x.end()), shallow);
    }
}}

#endif