// file      : xsd/cxx/tree/containers.hxx
// author    : Boris Kolpackov <boris@codesynthesis.com>
// copyright : Copyright (c) 2005-2006 Code Synthesis Tools CC
// license   : GNU GPL v2 + exceptions; see accompanying LICENSE file

#ifndef XSD_CXX_TREE_CONTAINERS_HXX
#define XSD_CXX_TREE_CONTAINERS_HXX


#include <string>
#include <vector>
#include <ostream>
#include <memory>    // std::auto_ptr
#include <algorithm> // std::equal, std::lexicographical_compare

#include <xsd/cxx/xml/dom/elements.hxx>

#include <xsd/cxx/tree/elements.hxx>

namespace xsd
{
  namespace cxx
  {
    namespace tree
    {
      //
      //
      template <typename X>
      class optional
      {
      public:
        explicit
        optional (flags f = 0, type* c = 0)
            : flags_ (f), container_ (c)
        {
        }

        explicit
        optional (X const& y, flags f = 0, type* c = 0)
            : flags_ (f), container_ (c)
        {
          set (y);
        }

        optional (optional const& y, flags f = 0, type* c = 0)
            : flags_ (f), container_ (c)
        {
          if (y)
            set (*y);
        }

        /*
        template <typename Y>
        optional (optional<Y> const& y)
        {
        }
        */

        optional&
        operator= (X const& y)
        {
          if (x_.get () == &y)
            return *this;

          set (y);

          return *this;
        }

        optional&
        operator= (optional const& y)
        {
          if (this == &y)
            return *this;

          if (y)
            set (*y);
          else
            reset ();

          return *this;
        }

        /*
        template <typename Y>
        optional_iterator&
        operator= (optional_iterator<Y> const& y)
        {
          return *this;
        }
        */

        // Pointer-like interface.
        //
      public:
        X const*
        operator-> () const
        {
          return x_.get ();
        }

        X*
        operator-> ()
        {
          return x_.get ();
        }

        X const&
        operator* () const
        {
          return get ();
        }

        X&
        operator* ()
        {
          return get ();
        }

        typedef void (optional::*bool_convertible) ();

        operator bool_convertible () const
        {
          return present () ? &optional::reset : 0;
        }

        // Get/set interface.
        //
      public:
        bool
        present () const
        {
          return x_.get () != 0;
        }

        X const&
        get () const
        {
          return *x_;
        }

        X&
        get ()
        {
          return *x_;
        }

        void
        set (X const& y)
        {
          // We always do a fresh copy because X may not be y's
          // dynamic type.
          //
          x_ = traits<X>::clone (y, flags_, container_);
        }

        void
        set (std::auto_ptr<X> y)
        {
          if (y.get () == 0)
            reset ();
          else
          {
            if (traits<X>::same_container (*y, container_))
              x_ = y;
            else
              set (*y);
          }
        }

        void
        reset ()
        {
          x_.reset ();
        }

      private:
        template <typename>
        friend class optional;

      private:
        flags flags_;
        type* container_;
        std::auto_ptr<X> x_;
      };

      // See containers.ixx for operator<< (basic_ostream, optional)
      //

      // Comparison operators.
      //

      template <typename X>
      inline bool
      operator== (optional<X> const& a, optional<X> const& b)
      {
        return !a || !b ? a == b : *a == *b;
      }

      template <typename X>
      inline bool
      operator!= (optional<X> const& a, optional<X> const& b)
      {
        return !(a == b);
      }

      template <typename X>
      inline bool
      operator< (optional<X> const& a, optional<X> const& b)
      {
        return a && (!b || *a < *b);
      }

      template <typename X>
      inline bool
      operator> (optional<X> const& a, optional<X> const& b)
      {
        return b < a;
      }

      template <typename X>
      inline bool
      operator<= (optional<X> const& a, optional<X> const& b)
      {
        return !(a > b);
      }

      template <typename X>
      inline bool
      operator>= (optional<X> const& a, optional<X> const& b)
      {
        return !(a < b);
      }


      // Sequence.
      //

      // Test whether X is a C++ fundamental type.
      //
      template <typename X>
      struct fundamental_p
      {
        static bool const r = false;
      };

      // byte
      //
      template <>
      struct fundamental_p<signed char>
      {
        static bool const r = true;
      };

      template <>
      struct fundamental_p<unsigned char>
      {
        static bool const r = true;
      };

      // short
      //
      template <>
      struct fundamental_p<short>
      {
        static bool const r = true;
      };

      template <>
      struct fundamental_p<unsigned short>
      {
        static bool const r = true;
      };

      // int
      //
      template <>
      struct fundamental_p<int>
      {
        static bool const r = true;
      };

      template <>
      struct fundamental_p<unsigned int>
      {
        static bool const r = true;
      };

      // long
      //
      template <>
      struct fundamental_p<long>
      {
        static bool const r = true;
      };

      template <>
      struct fundamental_p<unsigned long>
      {
        static bool const r = true;
      };

      template <>
      struct fundamental_p<long long>
      {
        static bool const r = true;
      };

      template <>
      struct fundamental_p<unsigned long long>
      {
        static bool const r = true;
      };

      // bool
      //
      template <>
      struct fundamental_p<bool>
      {
        static bool const r = true;
      };

      // float
      //
      template <>
      struct fundamental_p<float>
      {
        static bool const r = true;
      };

      template <>
      struct fundamental_p<double>
      {
        static bool const r = true;
      };

      template <>
      struct fundamental_p<long double>
      {
        static bool const r = true;
      };


      //@@ Complete emulation of std sequence.
      //

      template <typename X, bool fundamental = fundamental_p<X>::r>
      class sequence;


      // Specialization for complex types.
      //

      // Seven years since 1998, Sun still uses raw pointers for
      // iterators. Sun, what a pathetic company you are!
      //
      template <typename I>
      struct iterator_to_value
      {
        typedef typename I::value_type r;
      };

      template <typename I>
      struct iterator_to_value<I*>
      {
        typedef I r;
      };

      template <typename I>
      struct iterator_adapter
      {
        typedef I base_iterator;
        typedef typename iterator_to_value<I>::r::value value;
        typedef value& reference;
        typedef value* pointer;

        explicit
        iterator_adapter (I const& i)
            : i_ (i)
        {
        }

        // Allow iterator to const_iterator conversion.
        //
        template <typename J>
        iterator_adapter (iterator_adapter<J> const& j)
            : i_ (j.base ())
        {
        }

      public:
        reference
        operator* () const
        {
          return **i_;
        }

        pointer
        operator-> () const
        {
          return i_->get ();
        }

      public:
        I const&
        base () const
        {
          return i_;
        }

      public:
        iterator_adapter&
        operator++ ()
        {
          ++i_;
          return *this;
        }

        iterator_adapter
        operator++ (int)
        {
          iterator_adapter r (*this);
          ++i_;
          return r;
        }

        iterator_adapter&
        operator-- ()
        {
          --i_;
          return *this;
        }

        iterator_adapter
        operator-- (int)
        {
          iterator_adapter r (*this);
          --i_;
          return r;
        }

      private:
        I i_;
      };

      // Note: We use different types for left- and right-hand-side
      // arguments to allow comparison between iterator and const_iterator.
      //

      template <typename I, typename J>
      inline bool
      operator== (iterator_adapter<I> const& i, iterator_adapter<J> const& j)
      {
        return i.base () == j.base ();
      }

      template <typename I, typename J>
      inline bool
      operator!= (iterator_adapter<I> const& i, iterator_adapter<J> const& j)
      {
        return i.base () != j.base ();
      }

      template <typename I, typename J>
      inline typename iterator_adapter<I>::base_iterator::difference_type
      operator- (iterator_adapter<I> const& i, iterator_adapter<I> const& j)
      {
        return i.base () - j.base ();
      }

      template <typename X>
      class sequence<X, false>
      {
        // This is a dangerously destructive automatic pointer. We are going
        // to use it in a controlled environment to save us a lot of coding.
        //
        struct ptr
        {
          typedef X value;

          ~ptr ()
          {
            reset ();
          }

          explicit
          ptr (X* x = 0)
              : x_ (x)
          {
          }

          ptr (ptr const& y)
              : x_ (y.x_)
          {
            // Yes, hostile takeover.
            //
            y.x_ = 0;
          }

          ptr&
          operator= (ptr const& y)
          {
            if (this != &y)
            {
              // Yes, hostile takeover.
              //
              reset (y.x_);
              y.x_ = 0;
            }

            return *this;
          }

        public:
          X&
          operator* () const
          {
            return *get ();
          }

          X*
          get () const
          {
            return x_;
          }

        private:
          void
          reset (X* x = 0)
          {
            delete x_;
            x_ = x;
          }

        private:
          mutable X* x_;
        };

        typedef std::vector<ptr> base_sequence;
        typedef typename base_sequence::iterator base_iterator;
        typedef typename base_sequence::const_iterator base_const_iterator;

      public:
        typedef X        value_type;
        typedef X*       pointer;
        typedef X const* const_pointer;
        typedef X&       reference;
        typedef X const& const_reference;

        typedef
        iterator_adapter<typename base_sequence::iterator>
        iterator;

        typedef
        iterator_adapter<typename base_sequence::const_iterator>
        const_iterator;

        typedef
        iterator_adapter<typename base_sequence::reverse_iterator>
        reverse_iterator;

        typedef
        iterator_adapter<typename base_sequence::const_reverse_iterator>
        const_reverse_iterator;

        typedef typename base_sequence::size_type       size_type;
        typedef typename base_sequence::difference_type difference_type;
        typedef typename base_sequence::allocator_type  allocator_type;

      public:
        explicit
        sequence (flags f = 0, type* c = 0)
            : flags_ (f | flags::not_root), container_ (c)
        {
        }

        sequence (sequence const& v, flags f = 0, type* c = 0)
            : flags_ (f | flags::not_root), container_ (c), v_ (v.size ())
        {
          base_iterator di (v_.begin ()), de (v_.end ());
          base_const_iterator si (v.v_.begin ()), se (v.v_.end ());

          for (; si != se && di != de; ++si, ++di)
          {
            // We have no ptr_ref.
            ptr p (traits<X>::clone (**si, flags_, container_).release ());
            *di = p;
          }
        }

        sequence&
        operator= (sequence const& v)
        {
          if (this == &v)
            return *this;

          v_.assign (v.v_.size (), ptr ());

          base_iterator di (v_.begin ()), de (v_.end ());
          base_const_iterator si (v.v_.begin ()), se (v.v_.end ());

          for (; si != se && di != de; ++si, ++di)
          {
            // We have no ptr_ref.
            ptr p (traits<X>::clone (**si, flags_, container_).release ());
            *di = p;
          }

          return *this;
        }

      public:
        size_type
        size () const
        {
          return v_.size ();
        }

        size_type
        max_size () const
        {
          return v_.max_size ();
        }

        size_type
        capacity () const
        {
          return v_.capacity ();
        }

        bool
        empty () const
        {
          return v_.empty ();
        }

        void
        reserve (size_type n)
        {
          return v_.reserve (n);
        }

      public:
        const_iterator
        begin () const
        {
          return const_iterator (v_.begin ());
        }

        const_iterator
        end () const
        {
          return const_iterator (v_.end ());
        }

        iterator
        begin ()
        {
          return iterator (v_.begin ());
        }

        iterator
        end ()
        {
          return iterator (v_.end ());
        }

        // reverse
        //

        const_reverse_iterator
        rbegin () const
        {
          return const_reverse_iterator (v_.rbegin ());
        }

        const_reverse_iterator
        rend () const
        {
          return const_reverse_iterator (v_.rend ());
        }

        reverse_iterator
        rbegin ()
        {
          return reverse_iterator (v_.rbegin ());
        }

        reverse_iterator
        rend ()
        {
          return reverse_iterator (v_.rend ());
        }

      public:
        X&
        operator[] (size_type n)
        {
          return *(v_[n]);
        }

        X const&
        operator[] (size_type n) const
        {
          return *(v_[n]);
        }

        X&
        at (size_type n)
        {
          return *(v_.at (n));
        }

        X const&
        at (size_type n) const
        {
          return *(v_.at (n));
        }

        X&
        front ()
        {
          return *(v_.front ());
        }

        X const&
        front () const
        {
          return *(v_.front ());
        }

        X&
        back ()
        {
          return *(v_.back ());
        }

        X const&
        back () const
        {
          return *(v_.back ());
        }

      public:
        void
        push_back (X const& x)
        {
          v_.push_back (
            ptr (traits<X>::clone (x, flags_, container_).release ()));
        }

        void
        push_back (std::auto_ptr<X> x)
        {
          if (traits<X>::same_container (*x, container_))
            v_.push_back (ptr (x.release ()));
          else
            push_back (*x);
        }


        void
        pop_back ()
        {
          v_.pop_back ();
        }

        iterator
        insert (iterator position, X const& x)
        {
          return iterator (
            v_.insert (
              position.base (),
              ptr (traits<X>::clone (x, flags_, container_).release ())));
        }

        iterator
        erase (iterator position)
        {
          return iterator (v_.erase (position.base ()));
        }

        void
        clear ()
        {
          v_.clear ();
        }

        void
        swap (sequence& x)
        {
          v_.swap (x.v_);
        }

      public:

        // This c-tors are used only in xsd:list mapping. Individual
        // items of the list have no DOM association. Therefore I
        // clear keep_dom from flags.
        //

        template <typename C>
        explicit
        sequence (xml::dom::element<C> const& e, flags f, type* c)
            : flags_ ((f & ~flags::keep_dom) | flags::not_root),
              container_ (c)
        {
          init (e.value (), &e);
        }

        template <typename C>
        explicit
        sequence (xml::dom::attribute<C> const& a, flags f, type* c)
            : flags_ ((f & ~flags::keep_dom) | flags::not_root),
              container_ (c)
        {
          xml::dom::element<C> e (a.element ());
          init (a.value (), &e);
        }

        template <typename C>
        sequence (std::basic_string<C> const& s,
                  xml::dom::element<C> const* e,
                  flags f,
                  type* c)
            : flags_ ((f & ~flags::keep_dom) | flags::not_root),
              container_ (c)
        {
          init (s, e);
        }

      private:
        template <typename C>
        void
        init (std::basic_string<C> const& s,
              xml::dom::element<C> const* parent)
        {
          // Note that according to the spec the separator is exactly
          // one space (0x20). This makes our life much easier.
          //

          for (std::size_t i (0), j (s.find (C (' ')));;)
          {
            if (j != std::basic_string<C>::npos)
            {
              if (parent)
                push_back (
                  traits<X>::create (
                    std::basic_string<C> (s, i, j - i),
                    *parent,
                    flags_,
                    container_));
              else
                push_back (
                  traits<X>::create (
                    std::basic_string<C> (s, i, j - i), flags_, container_));

              i = j + 1;
              j = s.find (C (' '), i);
            }
            else
            {
              // Last element.
              if (parent)
                push_back (
                  traits<X>::create (
                    std::basic_string<C> (s, i),
                    *parent,
                    flags_,
                    container_));
              else
                push_back (
                  traits<X>::create (
                    std::basic_string<C> (s, i), flags_, container_));

              break;
            }
          }
        }

      private:
        flags flags_;
        type* container_;
        base_sequence v_;
      };


      // Specialization for built-in types.
      //
      template <typename X>
      class sequence<X, true>: public std::vector<X>
      {
        typedef std::vector<X> base_sequence;

        /*
      public:
        typedef typename base_sequence::value_type      value_type;
        typedef typename base_sequence::pointer         pointer;
        typedef typename base_sequence::const_pointer   const_pointer;
        typedef typename base_sequence::reference       reference;
        typedef typename base_sequence::const_reference const_reference;

        typedef typename base_sequence::iterator iterator;
        typedef typename base_sequence::const_iterator const_iterator;

        typedef typename base_sequence::reverse_iterator reverse_iterator;
        typedef typename base_sequence::const_reverse_iterator const_reverse_iterator;

        typedef typename base_sequence::size_type       size_type;
        typedef typename base_sequence::difference_type difference_type;
        typedef typename base_sequence::allocator_type  allocator_type;
        */

      public:
        explicit
        sequence (flags = 0, type* = 0)
        {
        }

        sequence (sequence const& s, flags = 0, type* = 0)
            : base_sequence (s)
        {
        }

      public:
        template <typename C>
        explicit
        sequence (xml::dom::element<C> const& e, flags, type*)
        {
          init (e.value (), &e);
        }

        template <typename C>
        explicit
        sequence (xml::dom::attribute<C> const& a, flags, type*)
        {
          xml::dom::element<C> e (a.element ());
          init (a.value (), &e);
        }

        template <typename C>
        sequence (std::basic_string<C> const& s,
                  xml::dom::element<C> const* parent,
                  flags,
                  type*)
        {
          init (s, parent);
        }

      private:
        template <typename C>
        void
        init (std::basic_string<C> const& s,
              xml::dom::element<C> const* parent)
        {
          // Note that according to the spec the separator is exactly
          // one space (0x20). This makes our life much easier.
          //

          for (std::size_t i (0), j (s.find (C (' ')));;)
          {
            if (j != std::basic_string<C>::npos)
            {
              if (parent)
                push_back (
                  traits<X>::create (
                    std::basic_string<C> (s, i, j - i), *parent, 0, 0));
              else
                push_back (
                  traits<X>::create (
                    std::basic_string<C> (s, i, j - i), 0, 0));

              i = j + 1;
              j = s.find (C (' '), i);
            }
            else
            {
              // Last element.
              if (parent)
                push_back (
                  traits<X>::create (
                    std::basic_string<C> (s, i), *parent, 0, 0));
              else
                push_back (
                  traits<X>::create (
                    std::basic_string<C> (s, i), 0, 0));

              break;
            }
          }
        }
      };

      template <typename C, typename X, bool fund>
      std::basic_ostream<C>&
      operator<< (std::basic_ostream<C>& os, sequence<X, fund> const& v)
      {
        for (typename sequence<X, fund>::const_iterator
               b (v.begin ()), e (v.end ()), i (b); i != e; ++i)
        {
          if (i != b)
            os << C (' ');

          os << *i;
        }

        return os;
      }


      // Comparison operators.
      //

      template <typename X>
      inline bool
      operator== (sequence<X> const& a, sequence<X> const& b)
      {
        return (a.size () == b.size ()
                && std::equal (a.begin (), a.end (), b.begin ()));
      }

      template <typename X>
      inline bool
      operator!= (sequence<X> const& a, sequence<X> const& b)
      {
        return !(a == b);
      }

      template <typename X>
      inline bool
      operator< (sequence<X> const& a, sequence<X> const& b)
      {
        return std::lexicographical_compare (a.begin (), a.end (),
                                             b.begin (), b.end ());
      }

      template <typename X>
      inline bool
      operator> (sequence<X> const& a, sequence<X> const& b)
      {
        return b < a;
      }

      template <typename X>
      inline bool
      operator<= (sequence<X> const& a, sequence<X> const& b)
      {
        return !(a > b);
      }

      template <typename X>
      inline bool
      operator>= (sequence<X> const& a, sequence<X> const& b)
      {
        return !(a < b);
      }
    }
  }
}

#endif  // XSD_CXX_TREE_CONTAINERS_HXX

#include <xsd/cxx/tree/containers.ixx>
