...

1 files changed, 0 insertions, 261 deletions

diff --git a/meowpp/dsa/SplayTree_Range.h b/meowpp/dsa/SplayTree_Range.h
deleted file mode 100644
index 0abdc24..0000000
--- a/meowpp/dsa/SplayTree_Range.h
+++ /dev/null
@@ -1,261 +0,0 @@
-#ifndef   dsa_SplayTree_Range_h__
-#define   dsa_SplayTree_Range_h__
-
-#include <cstdlib>
-
-#include <utility>
-
-#include "../math/utility.h"
-
-namespace meow{
-  //#
-  //#=== meow:: *SplayTree_Range<Key, Value>* (C++ class)
-  //#==== Description
-  //#  `SplayTree_Range` 是一種神乎其技的資料結構, 維護一堆 Key->Value. 並且支援
-  //#  一些 `std::map` 難以快速實踐的操作, 如 `split` , `merge` , `keyOffset`
-  //#
-  //#==== Template Class Operators Request
-  //#[options="header",width="70%",cols="1>m,1<,3<s,5<,3<,15<",grid="rows"]
-  //#|=====================================================================
-  //#|Const?|Typename| Operator| Parameters  | Return_Type| Description
-  //#|const |Key     |operator+|(Key    `k`) | Key        | 相加
-  //#|const |Key     |operator<|(Key    `k`) | bool       | 大小比較
-  //#|      |Key     |'Key'    |(int    `n`) |            | 建構子, `n` 永遠是0
-  //#|      |Value   | 'Value' |(          ) |            | 建構子
-  //#|=====================================================================
-  //#
-  template<class Key, class Value>
-  class SplayTree_Range{
-    private:
-      struct Node{
-        Key    _key;
-        Key    _keyOffset;
-        Value  _value;
-        Value  _valueOffset;
-        Value  _range;
-        bool   _same;
-        size_t _size;
-        Node*  _parent;
-        Node*  _child[2];
-        //
-        Node(Key const& __key, Value const& __value);
-        //
-        void keyOffset  (Key   const& __delta);
-        void valueUpdate(Value const& __delta, bool __over);
-        void syncDown() const;
-        void syncUp  () const;
-      };
-      //
-      Node* _root;
-      //
-      void        connect(Node const* __parent, size_t __left_right,
-                          Node const* __child) const;
-      Node const* splay  (Node const* __node) const;
-      //
-      void  clear(Node* __node);
-      Node*   dup(Node* __node);
-      //
-      Node const* findKey   (Node const* __node, Key const& __key    ) const;
-      Node const* findMinMax(Node const* __node, bool       __minimum) const;
-      Node const* findOrder (Node const* __node, size_t     __order  ) const;
-      //
-      void  split(Node* __root, Node** __left, Node** __right);
-      Node* merge(              Node*  __left, Node*  __right);
-    public:
-      //#==== Custom Type Definitions
-      //#
-      //# * `Element` -> 用來當作回傳資料的媒介
-      //# ** 重定義 `operator->()` 到 `std::pair<Key const&, Value&>*` 
-      //# ** 重定義 `operator*()` 到 `std::pair<Key const&, Value&>&` 
-      //# ** 有 `operator==` , `operator!=`, `operator=` 可用
-      //# ** 可以直接用 `(*e).second = some_value` 來改變SplayTree_Range中的資料
-      //#
-      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_Range();
-      SplayTree_Range(SplayTree_Range const& __tree2);
-      ~SplayTree_Range();
-      SplayTree_Range& operator=(SplayTree_Range const& __tree2);
-      //
-      //#==== Support Methods
-      //#
-      //# * N <- `this` 中擁有的資料數
-      //# * M <- `tree2` 中擁有的資料數
-      //#
-      //#[options="header",width="100%",cols="1>m,3>s,7<,3<,3^,20<",grid="rows"]
-      //#|=====================================================================
-      //#|Const?|Name | Parameters   | Return_Type| Time_Complexity| Description
-
-
-      //#||moveTo|(SplayTree_Range* `tree2`)|void|O(M)
-      //#|將 `this` 的資料複寫到 `tree2` 上面, 同時清空自己, 
-      //# 時間複雜度中的M是 `tree2` 所擁有的資料數
-      void moveTo(SplayTree_Range* __tree2);
-
-
-      //#|const|lowerBound|(Key const& `k`)|Element|O(logN)
-      //#|找出第一個(最小的) Element且 `k` <= 它的 Key, 並且回傳之.
-      //# 找不到的話回傳 `this->end()`
-      Element lowerBound(Key const& __key) const;
-
-
-      //#|const|lowerBound|(Key const& `k`)|Element|O(logN)
-      //#|找出第一個(最小的) Element且 `k` < 它的 Key, 並且回傳之.
-      //# 找不到的話回傳 `this->end()`
-      Element upperBound(Key const& __key) const;
-
-
-      //#|const|lowerBound|(Key const& `k`)|Element|O(logN)
-      //#|找出第一個(最小的) Element且 `k` >= 它的 Key, 並且回傳之.
-      //# 找不到的話回傳 `this->end()`
-      Element rLowerBound(Key const& __key) const;
-
-
-      //#|const|lowerBound|(Key const& `k`)|Element|O(logN)
-      //#|找出第一個(最小的) Element且 `k` > 它的 Key, 並且回傳之.
-      //# 找不到的話回傳 `this->end()`
-      Element rUpperBound(Key const& __key) const;
-
-
-      //#|const|find|(Key const& `k`)|Element|O(logN)
-      //#|找出 Key= `k` 的Elemenet 並回傳. 找不到的話回傳 `this->end()`
-      Element find(Key const& __key) const;
-      
-      
-      //#|const|query|()|Value|O(1)
-      //#|回傳整棵樹的區間Value
-      Value query() const;
-      
-      
-      //#|const|query|(Key const& `first` ,\Key const& `last`)|Value|O(logN)
-      //#|找出key介於 `first` \~ `last` 的區間Value
-      Value query(Key const& __first, Key const& __last) const;
-
-
-      //#|const|order|(size_t `ord`)|Element|O(logN)
-      //#|將Elements依照Key由小到大排序, 回傳第 `ord` 個Element (由0算起).
-      //# 其中如果 `ord` > N - 1, 則會回傳 `this->last()`
-      Element order(size_t __order) const;
-
-
-      //#|const|first|(size_t `ord`)|Element|O(logN)
-      //#|回傳Key最小的Element, 如果SplayTree_Range為空, 則回傳 `this->end()`
-      Element first() const;
-
-
-      //#|const|last|(size_t `ord`)|Element|O(logN)
-      //#|回傳Key最大的Element, 如果SplayTree_Range為空, 則回傳 `this->end()`
-      Element last() const;
-
-
-      //#|const|end|()|Element|O(1)
-      //#|回傳一個指向NULL的Element, 以供 `find` , `order` , `first`
-      //# , `last` 等判斷是否有找到相對應的Element
-      Element end() const;
-
-
-      //#|const|size|()|size_t|O(1)| 回傳資料數
-      size_t size() const;
-
-
-      //#|const|size|()|bool|O(1)| 回傳是否為空
-      bool empty() const;
-
-
-      //#||clear|()|void|O(N)| 清空資料
-      void clear();
-
-
-      //#||insert|(Key const& `key`,\Value const& `value`)|bool|O(logN)
-      //#|檢查是否已有Element的Key 為 `key`, 若有則回傳 `false` , 否則將
-      //# 一個 (Key -> Value) = (`key` -> `value`)的Element加入, 並回傳 `true`
-      //# 將所有Element的Key同加上 `delta`
-      bool insert(Key const& __key, Value const& __value);
-
-
-      //#||erase|(Key const& `key`)|bool|O(logN)
-      //#|檢查是否已有Element的Key 為 `key`, 若有則刪除之, 並回傳 `true`,
-      //# 否則則回傳 `false`
-      bool erase(Key const& __key);
-
-
-      //#||keyOffset|(Key const& `delta`)|void|O(1)
-      //#|將所有Element的Key同加上 `delta`
-      void keyOffset(Key const& __delta);
-      
-      
-      //#||valueOffset|(Value const& `delta`)|void|O(1)
-      //#|將所有Element的value同加上 `delta`
-      void valueOffset(Value const& __delta);
-      
-      
-      //#||valueOverride|(Value const& `vaule`)|void|O(1)
-      //#|將所有Element的value同變成 `value`
-      void valueOverride(Value const& __value);
-
-
-      //#||operator[]|(Key const& `key`)|Value&|O(logN)
-      //#|檢查是否已有Element的Key 為 `key`, 若有則回傳相對應的Value的Reference
-      //# 否則先執行 `insert(key, Value())` 再回傳相對應的Reference
-      Value& operator[](Key const& __key);
-
-
-      //#||splitOut|(Key const& `upper_bound`,\SplayTree_Range* `tree2`)|void
-      //#|O(logN) + O(M)
-      //#|將 `tree2` 清空, 再將所有Key > `upper_bound` 的Element都丟到 `tree2`
-      void splitOut(Key const& __upper_bound, SplayTree_Range* __right);
-
-
-      //#||mergeAfter|(SplayTree_Range* `tree2`)|void|O(logN) + O(logM)
-      //#|檢查是否 `this` 中的 Key 都小於 `tree2` 中的Key, 是的話把 `tree2` 
-      //# 中的 Element 都搬到 `this` , 同時清空 `tree2` , 回傳 `true`. 否則
-      //# 回傳 `false`
-      bool mergeAfter(SplayTree_Range* __tree2);
-
-
-      //#||merge|(SplayTree_Range* `tree2`)|void|O(logN) + O(logM)
-      //#|檢查是否 `this` 中的 Key 都小於 `tree2` 中的Key 或者
-      //# 是否 `this` 中的 Key 都大於 `tree2` 中的Key, 是的話把 `tree2` 
-      //# 中的 Element 都搬到 `this` , 同時清空 `tree2` , 回傳 `true`. 否則
-      //# 回傳 `false`
-      bool merge(SplayTree_Range* __tree2);
-
-
-      //#|=====================================================================
-  };
-  //#
-  //#[NOTE]
-  //#========================================
-  //# * 假設現在有兩個SplayTree_Range `A` 和 `B`,  則:
-  //# ** 執行 `B.moveTo(&A)` 後 `B` 會變成空的, `A` 原本擁有的資料也會覆蓋掉
-  //# ** 執行 `A.merge(&B)` 或 `A.mergeAfter(&B)` 後
-  //#    如果檢查發現確實可以merge, 則之後 `B` 會變成空的
-  //#========================================
-  //#
-  //# '''
-  //#
-}
-
-#include "SplayTree_Range.hpp"
-
-#endif // dsa_SplayTree_Range_h__