1 files changed, 103 insertions, 0 deletions
diff --git a/meowpp/dsa/SplayTree.h b/meowpp/dsa/SplayTree.h
new file mode 100644
index 0000000..78b54f6
--- /dev/null
+++ b/meowpp/dsa/SplayTree.h
@@ -0,0 +1,103 @@
+#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__