From 80287716c14f2c48464c5f5309ee71606cf96ba2 Mon Sep 17 00:00:00 2001 From: cathook Date: Sun, 1 Jun 2014 14:08:30 +0800 Subject: ... --- meowpp/dsa/SplayTree_Range.h | 261 ------------------------------------------- 1 file changed, 261 deletions(-) delete mode 100644 meowpp/dsa/SplayTree_Range.h 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 - -#include - -#include "../math/utility.h" - -namespace meow{ - //# - //#=== meow:: *SplayTree_Range* (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 - 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*` - //# ** 重定義 `operator*()` 到 `std::pair&` - //# ** 有 `operator==` , `operator!=`, `operator=` 可用 - //# ** 可以直接用 `(*e).second = some_value` 來改變SplayTree_Range中的資料 - //# - class Element{ - private: - typedef std::pair 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__ -- cgit v1.2.3