#ifndef   SplayTree_h__
#define   SplayTree_h__

#include "utility.h"

namespace meow{
  template<class Key, class Value>
  class SplayTree{
    private:
      struct Node{
        Key    _key;
        Key    _keyOffset;
        Value  _value;
        size_t _size;
        Node*  _parent;
        Node*  _lChild;
        Node*  _rChild;
        //
        Node(Key const& __key, Value const& __value);
      };
      //
      Node* _root;
      //
      void offsetAdd    (Node* __node, Key const& __delta) const;
      void offsetDown   (Node* __node                    ) const;
      void sizeUpdate   (Node* __node                    ) const;
      void connectLChild(Node* __parent, Node* __child   ) const;
      void connectRChild(Node* __parent, Node* __child   ) const;
      //
      Node* clear(Node* __node);
      Node* dup  (Node* __node);
      //
      void rotate(               Node* __parent, Node* __child) const;
      void rotate(Node* __grand, Node* __parent, Node* __child) const;
      Node* splay(Node* __node) const;
      //
      Node* findKey   (Node* __node, Key const& __key) const;
      Node* findMinMax(Node* __node, bool minimum    ) const;
      Node* findOrder (Node* __node, size_t __order  ) const;
      //
      void  split(Node* __root, Node** __left, Node** __right);
      Node* merge(              Node*  __left, Node*  __right);
      //
      void print(Node* __now, int __depth) const;
    public:
      class Element{
        private:
          typedef std::pair<Key const&, Value&> Entry;
          Entry* _entry;
          Node * _node;
          //
          void reset(Node* __node);
        public:
          Element();
          Element(Node* __node);
          Element(Element const& __iterator2);
          ~Element();
          //
          Element& operator=(Element const& __e2);
          //
          Entry* operator->();
          Entry& operator *();
          //
          bool operator==(Element const& __e2) const;
          bool operator!=(Element const& __e2) const;
      };
      //
      SplayTree();
      SplayTree(SplayTree const& __tree2);
      ~SplayTree();
      //
      SplayTree& operator=(SplayTree const& __tree2);
      void moveTo(SplayTree* __tree2);
      //
      Element  lowerBound(Key const& __key) const;
      Element  upperBound(Key const& __key) const;
      Element rLowerBound(Key const& __key) const;
      Element rUpperBound(Key const& __key) const;
      Element find (Key const& __key) const;
      Element order(size_t __order  ) const;
      Element first(                ) const;
      Element last (                ) const;
      Element   end(                ) const;
      //
      size_t  size() const;
      bool   empty() const;
      //
      void   clear();
      void   keyOffset(Key const& __delta);
      bool   insert      (Key const& __key, Value const& __value);
      bool   erase       (Key const& __key);
      Value& operator[](Key const& __key);
      void   splitOut(Key const& __upper_bound, SplayTree* __right);
      bool   mergeAfter(SplayTree* __tree2);
      bool   merge     (SplayTree* __tree2);
      //
      void print() const;
  };
}

#include "SplayTree.hpp"

#endif // SplayTree_h__