From 04e55aa4560f597373ca58c29f57fe6c98d11a50 Mon Sep 17 00:00:00 2001 From: cathook Date: Fri, 25 Apr 2014 01:53:47 +0800 Subject: add BIT --- Makefile | 2 + README.asciidoc | 164 +++++++++++- README.html | 538 ++++++++++++++++++++++++++++++++++++++- _test/meowpp.cpp | 92 +++++-- _test/meowpp.h | 64 +++++ _test/meowpp_BinaryIndexTree.cpp | 54 ++++ _test/meowpp_Colors.cpp | 124 +++++++++ _test/meowpp_DisjointSet.cpp | 79 ++++++ _test/meowpp_KD_Tree.cpp | 186 ++++++++++++++ _test/meowpp_MergeableHeap.cpp | 71 ++++++ _test/meowpp_SegmentTree.cpp | 154 +++++++++++ _test/meowpp_SplayTree.cpp | 503 ++++++++++++++++++++++++++++++++++++ footer.asciidoc | 12 + meowpp/dsa/BinaryIndexTree.h | 69 +++++ meowpp/dsa/BinaryIndexTree.hpp | 44 ++++ meowpp/dsa/SplayTree.h | 52 ++-- meowpp/dsa/SplayTree.hpp | 467 ++++++++++++++++----------------- 17 files changed, 2357 insertions(+), 318 deletions(-) create mode 100644 _test/meowpp.h create mode 100644 _test/meowpp_BinaryIndexTree.cpp create mode 100644 _test/meowpp_Colors.cpp create mode 100644 _test/meowpp_DisjointSet.cpp create mode 100644 _test/meowpp_KD_Tree.cpp create mode 100644 _test/meowpp_MergeableHeap.cpp create mode 100644 _test/meowpp_SegmentTree.cpp create mode 100644 _test/meowpp_SplayTree.cpp create mode 100644 meowpp/dsa/BinaryIndexTree.h create mode 100644 meowpp/dsa/BinaryIndexTree.hpp diff --git a/Makefile b/Makefile index 1bb75c5..ffb91b5 100644 --- a/Makefile +++ b/Makefile @@ -25,8 +25,10 @@ $(TEST)/meowpp: $(TEST)/meowpp.o \ $(TEST)/meowpp_DisjointSet.o \ $(TEST)/meowpp_KD_Tree.o \ $(TEST)/meowpp_SegmentTree.o \ + $(TEST)/meowpp_BinaryIndexTree.o \ $(TEST)/meowpp_MergeableHeap.o \ $(TEST)/meowpp_SplayTree.o \ + $(TEST)/meowpp_SplayTree_Range.o \ $(TEST)/meowpp_VP_Tree.o \ $(CXX) -o $@ $(CXXFLAGS) $^ diff --git a/README.asciidoc b/README.asciidoc index 1d25b02..3617440 100644 --- a/README.asciidoc +++ b/README.asciidoc @@ -456,8 +456,6 @@ bool `cmp`)|Vectors |const|size|()|size_t|O(1)| 回傳資料數 |const|size|()|bool|O(1)| 回傳是否為空 ||clear|()|void|O(N)| 清空資料 -||keyOffset|(Key const& `delta`)|void|O(1) -|將所有Element的Key同加上 `delta` ||insert|(Key const& `key`, + Value const& `value`)|bool|O(logN) |檢查是否已有Element的Key 為 `key`, 若有則回傳 `false` , 否則將 @@ -466,6 +464,8 @@ Value const& `value`)|bool|O(logN) ||erase|(Key const& `key`)|bool|O(logN) |檢查是否已有Element的Key 為 `key`, 若有則刪除之, 並回傳 `true`, 否則則回傳 `false` +||keyOffset|(Key const& `delta`)|void|O(1) +|將所有Element的Key同加上 `delta` ||operator[]|(Key const& `key`)|Value&|O(logN) |檢查是否已有Element的Key 為 `key`, 若有則回傳相對應的Value的Reference 否則先執行 `insert(key, Value())` 再回傳相對應的Reference @@ -546,6 +546,154 @@ Value const& `delta`) ''' +=== 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 用來當作回傳資料的媒介 +** 重定義 `operator->()` 到 `std::pair*` +** 重定義 `operator*()` 到 `std::pair&` +** 有 `operator==` , `operator!=`, `operator=` 可用 +** 可以直接用 `(*e).second = some_value` 來改變SplayTree_Range中的資料 + +==== 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` 所擁有的資料數 +|const|lowerBound|(Key const& `k`)|Element|O(logN) +|找出第一個(最小的) Element且 `k` <= 它的 Key, 並且回傳之. +找不到的話回傳 `this->end()` +|const|lowerBound|(Key const& `k`)|Element|O(logN) +|找出第一個(最小的) Element且 `k` < 它的 Key, 並且回傳之. +找不到的話回傳 `this->end()` +|const|lowerBound|(Key const& `k`)|Element|O(logN) +|找出第一個(最小的) Element且 `k` >= 它的 Key, 並且回傳之. +找不到的話回傳 `this->end()` +|const|lowerBound|(Key const& `k`)|Element|O(logN) +|找出第一個(最小的) Element且 `k` > 它的 Key, 並且回傳之. +找不到的話回傳 `this->end()` +|const|find|(Key const& `k`)|Element|O(logN) +|找出 Key= `k` 的Elemenet 並回傳. 找不到的話回傳 `this->end()` +|const|query|()|Value|O(1) +|回傳整棵樹的區間Value +|const|query|(Key const& `first` , + +Key const& `last`)|Value|O(logN) +|找出key介於 `first` + +~ `last` 的區間Value +|const|order|(size_t `ord`)|Element|O(logN) +|將Elements依照Key由小到大排序, 回傳第 `ord` 個Element (由0算起). +其中如果 `ord` > N - 1, 則會回傳 `this->last()` +|const|first|(size_t `ord`)|Element|O(logN) +|回傳Key最小的Element, 如果SplayTree_Range為空, 則回傳 `this->end()` +|const|last|(size_t `ord`)|Element|O(logN) +|回傳Key最大的Element, 如果SplayTree_Range為空, 則回傳 `this->end()` +|const|end|()|Element|O(1) +|回傳一個指向NULL的Element, 以供 `find` , `order` , `first` +, `last` 等判斷是否有找到相對應的Element +|const|size|()|size_t|O(1)| 回傳資料數 +|const|size|()|bool|O(1)| 回傳是否為空 +||clear|()|void|O(N)| 清空資料 +||insert|(Key const& `key`, + +Value const& `value`)|bool|O(logN) +|檢查是否已有Element的Key 為 `key`, 若有則回傳 `false` , 否則將 +一個 (Key -> Value) = (`key` -> `value`)的Element加入, 並回傳 `true` +將所有Element的Key同加上 `delta` +||erase|(Key const& `key`)|bool|O(logN) +|檢查是否已有Element的Key 為 `key`, 若有則刪除之, 並回傳 `true`, +否則則回傳 `false` +||keyOffset|(Key const& `delta`)|void|O(1) +|將所有Element的Key同加上 `delta` +||valueOffset|(Value const& `delta`)|void|O(1) +|將所有Element的value同加上 `delta` +||valueOverride|(Value const& `vaule`)|void|O(1) +|將所有Element的value同變成 `value` +||operator[]|(Key const& `key`)|Value&|O(logN) +|檢查是否已有Element的Key 為 `key`, 若有則回傳相對應的Value的Reference +否則先執行 `insert(key, Value())` 再回傳相對應的Reference +||splitOut|(Key const& `upper_bound`, + +SplayTree_Range* `tree2`)|void +|O(logN) + O(M) +|將 `tree2` 清空, 再將所有Key > `upper_bound` 的Element都丟到 `tree2` +||mergeAfter|(SplayTree_Range* `tree2`)|void|O(logN) + O(logM) +|檢查是否 `this` 中的 Key 都小於 `tree2` 中的Key, 是的話把 `tree2` +中的 Element 都搬到 `this` , 同時清空 `tree2` , 回傳 `true`. 否則 +回傳 `false` +||merge|(SplayTree_Range* `tree2`)|void|O(logN) + O(logM) +|檢查是否 `this` 中的 Key 都小於 `tree2` 中的Key 或者 +是否 `this` 中的 Key 都大於 `tree2` 中的Key, 是的話把 `tree2` +中的 Element 都搬到 `this` , 同時清空 `tree2` , 回傳 `true`. 否則 +回傳 `false` +|===================================================================== + +[NOTE] +======================================== +* 假設現在有兩個SplayTree_Range `A` 和 `B`, 則: +** 執行 `B.moveTo(&A)` 後 `B` 會變成空的, `A` 原本擁有的資料也會覆蓋掉 +** 執行 `A.merge(&B)` 或 `A.mergeAfter(&B)` 後 +如果檢查發現確實可以merge, 則之後 `B` 會變成空的 +======================================== + +''' + + +=== meow:: *BinaryIndexTree* (C++ class) +==== Description +極度簡化版的 `SegmentTree` 已無法區間操作, 區間詢問的區間開頭也一定要 +在 `index=0` 的地方 + +==== Template Class Operators Request +[options="header",width="70%",cols="1>m,1<,3

-

keyOffset

-

(Key const& delta)

-

void

-

O(1)

-

將所有Element的Key同加上 delta

- - -

insert

(Key const& key,
Value const& value)

@@ -2150,6 +2142,14 @@ Value const& value)

+

keyOffset

+

(Key const& delta)

+

void

+

O(1)

+

將所有Element的Key同加上 delta

+ + +

operator[]

(Key const& key)

Value&

@@ -2397,6 +2397,508 @@ Value const& delta)

+
+

meow:: SplayTree_Range<Key, Value> (C++ class)

+
+

Description

+

SplayTree_Range 是一種神乎其技的資料結構, 維護一堆 Key→Value. 並且支援 +一些 std::map 難以快速實踐的操作, 如 split , merge , keyOffset

+
+
+

Template Class Operators Request

+ +++++++ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
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

( )

建構子

+
+
+

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中的資料 +

      +
      • +
    +
    • +
+
+
+

Support Methods

+
    +
  • +

    +N ← this 中擁有的資料數 +

    +
    • +
  • +

    +M ← tree2 中擁有的資料數 +

    +
    • +
+ +++++++ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
Const?Name Parameters Return_Type Time_Complexity Description

moveTo

(SplayTree_Range* tree2)

void

O(M)

將 this 的資料複寫到 tree2 上面, 同時清空自己, +時間複雜度中的M是 tree2 所擁有的資料數

const

lowerBound

(Key const& k)

Element

O(logN)

找出第一個(最小的) Element且 k ⇐ 它的 Key, 並且回傳之. +找不到的話回傳 this->end()

const

lowerBound

(Key const& k)

Element

O(logN)

找出第一個(最小的) Element且 k < 它的 Key, 並且回傳之. +找不到的話回傳 this->end()

const

lowerBound

(Key const& k)

Element

O(logN)

找出第一個(最小的) Element且 k >= 它的 Key, 並且回傳之. +找不到的話回傳 this->end()

const

lowerBound

(Key const& k)

Element

O(logN)

找出第一個(最小的) Element且 k > 它的 Key, 並且回傳之. +找不到的話回傳 this->end()

const

find

(Key const& k)

Element

O(logN)

找出 Key= k 的Elemenet 並回傳. 找不到的話回傳 this->end()

const

query

()

Value

O(1)

回傳整棵樹的區間Value

const

query

(Key const& first ,
+Key const& last)

Value

O(logN)

找出key介於 first
+~ last 的區間Value

const

order

(size_t ord)

Element

O(logN)

將Elements依照Key由小到大排序, 回傳第 ord 個Element (由0算起). +其中如果 ord > N - 1, 則會回傳 this->last()

const

first

(size_t ord)

Element

O(logN)

回傳Key最小的Element, 如果SplayTree_Range為空, 則回傳 this->end()

const

last

(size_t ord)

Element

O(logN)

回傳Key最大的Element, 如果SplayTree_Range為空, 則回傳 this->end()

const

end

()

Element

O(1)

回傳一個指向NULL的Element, 以供 find , order , first +, last 等判斷是否有找到相對應的Element

const

size

()

size_t

O(1)

回傳資料數

const

size

()

bool

O(1)

回傳是否為空

clear

()

void

O(N)

清空資料

insert

(Key const& key,
+Value const& value)

bool

O(logN)

檢查是否已有Element的Key 為 key, 若有則回傳 false , 否則將 +一個 (Key → Value) = (key → value)的Element加入, 並回傳 true +將所有Element的Key同加上 delta

erase

(Key const& key)

bool

O(logN)

檢查是否已有Element的Key 為 key, 若有則刪除之, 並回傳 true, +否則則回傳 false

keyOffset

(Key const& delta)

void

O(1)

將所有Element的Key同加上 delta

valueOffset

(Value const& delta)

void

O(1)

將所有Element的value同加上 delta

valueOverride

(Value const& vaule)

void

O(1)

將所有Element的value同變成 value

operator[]

(Key const& key)

Value&

O(logN)

檢查是否已有Element的Key 為 key, 若有則回傳相對應的Value的Reference +否則先執行 insert(key, Value()) 再回傳相對應的Reference

splitOut

(Key const& upper_bound,
+SplayTree_Range* tree2)

void

O(logN) + O(M)

將 tree2 清空, 再將所有Key > upper_bound 的Element都丟到 tree2

mergeAfter

(SplayTree_Range* tree2)

void

O(logN) + O(logM)

檢查是否 this 中的 Key 都小於 tree2 中的Key, 是的話把 tree2 +中的 Element 都搬到 this , 同時清空 tree2 , 回傳 true. 否則 +回傳 false

merge

(SplayTree_Range* tree2)

void

O(logN) + O(logM)

檢查是否 this 中的 Key 都小於 tree2 中的Key 或者 +是否 this 中的 Key 都大於 tree2 中的Key, 是的話把 tree2 +中的 Element 都搬到 this , 同時清空 tree2 , 回傳 true. 否則 +回傳 false

+
+ + + +
+
Note
+		 +
    +
  • +

    +假設現在有兩個SplayTree_Range A 和 B, 則: +

    +
      +
    • +

      +執行 B.moveTo(&A) 後 B 會變成空的, A 原本擁有的資料也會覆蓋掉 +

      +
      • +
    • +

      +執行 A.merge(&B) 或 A.mergeAfter(&B) 後 +如果檢查發現確實可以merge, 則之後 B 會變成空的 +

      +
      • +
    +
    • +
+
+
+
+
+
+
+

meow:: BinaryIndexTree<Value> (C++ class)

+
+

Description

+

極度簡化版的 SegmentTree 已無法區間操作, 區間詢問的區間開頭也一定要 +在 index=0 的地方

+
+
+

Template Class Operators Request

+ +++++++ + + + + + + + + + + + + + + + + + + + +
Const?Typename Operator Parameters Return_Type Description

const

Value

operator+

(Value n)

Value

合併用(類似 +SegmentTree 的 +operator| )

+
+
+

Support Methods

+
    +
  • +

    +N ← this 中擁有的資料數 +

    +
    • +
+ +++++++ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
Const?Name Parameters Return_Type Time_Complexity Description

reset

(size_t size, Value const& value)

void

O(size)

將資料長度刷成 N = size 且每一個元素都是 value

update

(size_t index, Value const& value)

void

O(logN)

將第 index (從零開始算) 多加上 value

const

query

(size_t index)

void

O(logN)

詢問 0~index 的區間值

+
+ + + +
+
Note
+		 +
    +
  • +

    +一般來說只能用在維護區間總和, 維護區間最大值只有在特殊情況才可以, 即 +針對每個元素, 每次 update() 的值一定會大於等於原本的值 +

    +
    • +
  • +

    +若要用區間最大值 , 則 Value 的 operator+ 要寫成 std::max(...) +

    +
    • +
+
+
+
+
+
@@ -2443,6 +2945,24 @@ width:70%;

0.516

codepad

+ +

SplayTree + SegmentTree

+

Shuffling_cards

+

NTU-OJ +SPOJ

+

Accept/TLE

+

6.910/---

+

codepad

+ + +

SplayTree + BinaryIndexTree

+

Shuffling_cards

+

NTU-OJ +SPOJ

+

Accept/Accept

+

5.480/44.35

+

codepad

+
@@ -2464,7 +2984,7 @@ E-Mail: cat.hook31894 ~在~ gmail.com
diff --git a/_test/meowpp.cpp b/_test/meowpp.cpp index e03edaa..805f459 100644 --- a/_test/meowpp.cpp +++ b/_test/meowpp.cpp @@ -1,32 +1,72 @@ -#include "dsa/KD_Tree.h" -#include "Usage.h" +#include "meowpp.h" -bool testColors(){ -} -bool testDisjointSet(){ -} -bool testMergeableHeap(){ -} +#include +#include +#include + +//////////////////////////// +meow::Usage usg("meowpp"), usg2; +int count = 0; +TestFunctions tests; +//////////////////////// int main(int argc, char** argv){ - Usage usg("meowpp"), usg2; - usg .addOption('h', "Display this help document"); - usg2.addOption('t', - "Test the i-th part of the meowpp and then quit", - "", "", - false); + //srand(time(NULL)); + usg.addOption('h', "Display this help document"); + usg.addUsageBegin(" is a little test program to check whether" + "the data structures in the template is correct by" + "random generate lots of data to test"); + usg.addUsageEnd ("zzzzzzzzzzzzzzz...."); + usg.import(usg2); - KD_Tree(); - KD_Tree(size_t _dimension); - ~KD_Tree(); - // - void insert(Keys const& key, Value value); - void build(); - // - Value query (Keys const& point, int k) const; - Values rangeQuery(Keys const& point, int k) const; - // - void clear(); - void reset(size_t _dimension); + std::string err; + if(usg.setArguments(argc, argv, &err) == false){ + printf("%s\n\n%s\n", err.c_str(), usg.getUsage().c_str()); + return 1; + }else if(usg.hasOptionSetup('h')){ + printf("%s", usg.getUsage().c_str()); + return 0; + }else{ + usg2.update(usg); + if(usg2.getOptionValuesCount('t') > 0){ + for(int i = 0, I = usg2.getOptionValuesCount('t'); i < I; i++){ + int id = atoi(usg2.getOptionValue('t', i).c_str()); + TestFunction* f = (TestFunction*)tests.getImplement(id); + if(f->run() == false){ + printf("error occure on %s\n", f->name().c_str()); + return 1; + }else{ + printf("%s success\n", f->name().c_str()); + } + } + }else{ + std::vector ids = tests.getIdentifys(); + while(true){ + for(int i = 0, I = ids.size(); i < I; i++){ + TestFunction* f = (TestFunction*)tests.getImplement(i); + printf(" %d) %s\n", ids[i], f->name().c_str()); + } + printf("please select(EOF to quit): "); + int id; + if(!~scanf("%d", &id)){ + break; + } + printf("\n"); + TestFunction* f = (TestFunction*)tests.getImplement(id); + if(f == NULL){ + printf("Bad value!\n\n"); + continue; + } + if(f->run() == false){ + printf("error occure on %s\n\n", f->name().c_str()); + return 1; + }else{ + printf("%s success\n\n", f->name().c_str()); + } + } + printf("\n"); + } + return 0; + } return 0; } diff --git a/_test/meowpp.h b/_test/meowpp.h new file mode 100644 index 0000000..ca6c224 --- /dev/null +++ b/_test/meowpp.h @@ -0,0 +1,64 @@ +#ifndef __meowpp_h__ +#define __meowpp_h__ + +#include "Usage.h" +#include "utility.h" +#include "colors/RGB.h" +#include "colors/YUV.h" +#include "colors/HSL.h" +#include "colors/HSV.h" +#include "dsa/DisjointSet.h" +#include "dsa/KD_Tree.h" +#include "dsa/VP_Tree.h" +#include "dsa/SegmentTree.h" +#include "dsa/BinaryIndexTree.h" +#include "dsa/MergeableHeap.h" +#include "dsa/SplayTree.h" +#include "dsa/SplayTree_Range.h" +#include "oo/Register_Implement.h" + +extern meow::Usage usg, usg2; +extern int count; +////////////////////////////////// +class TestFunctions: public meow::RegisterInterface{ + public: + TestFunctions(): RegisterInterface(){ + usg2.addOption('t', + "Specify which part of the template to test", + "name", "", + false); + } + bool regImplement(meow::ImplementInterface* imp, + std::string const& str){ + usg2.addOptionValueAccept('t', + meow::stringPrintf("%d", imp->identify()), + str); + return RegisterInterface::regImplement(imp); + } +}; +extern TestFunctions tests; +//////////////////////// +class TestFunction: public meow::ImplementInterface{ + private: + std::string _name; + public: + TestFunction(std::string const& __name): + ImplementInterface(count++), _name("testing code about " + __name){ + tests.regImplement(this, _name); + } + virtual ~TestFunction(){ } + virtual bool run() = 0; + std::string name() const{ return _name; } +}; +//////////////////////// + +#define concat(a,b) a##b +#define TEST(a) \ +class Test_##a: public TestFunction{ \ + public: \ + Test_##a(): TestFunction(#a){ } \ + bool run();\ +} __test_##a; bool Test_##a::run() + + +#endif // meowpp_h__ diff --git a/_test/meowpp_BinaryIndexTree.cpp b/_test/meowpp_BinaryIndexTree.cpp new file mode 100644 index 0000000..3841a84 --- /dev/null +++ b/_test/meowpp_BinaryIndexTree.cpp @@ -0,0 +1,54 @@ +#include "meowpp.h" + +#include + +static int N = 100000; + +static std::vector array; + +inline int sum(int k){ + int x = 0; + for(int i = 0; i <= k; i++){ + x += array[i]; + } + return x; +} + +static meow::BinaryIndexTree bit; + +TEST(BinaryIndexTree){ + size_t tMe = 0, tBi = 0, t0; + for(int z = 0; z < 10; z++){ + meow::messagePrintf(1, "test %d", z); + bit.reset(N, 0); + array.clear(); + array.resize(N, 0); + + int NN = rand() % 10000; + for(int i = 0; i < NN; i++){ + int index = rand() % N; + if(rand() & 1){ + int val = rand() % 1000; + t0 = clock(); array[i] += val; tMe += clock() - t0; + t0 = clock(); bit.update(i, val); tBi += clock() - t0; + }else{ + if(sum(index) != bit.query(index)){ + meow::messagePrintf(-1, "range-sum query fail"); + return false; + } + } + } + int s = 0; + for(int i = 0; i < N; i++){ + s += array[i]; + if(s != bit.query(i)){ + meow::messagePrintf(-1, "range-sum query fail"); + return false; + } + } + meow::messagePrintf(-1, "ok %.3f/%.3f", + tBi * 1.0 / CLOCKS_PER_SEC, + tMe * 1.0 / CLOCKS_PER_SEC); + } + return true; +}; diff --git a/_test/meowpp_Colors.cpp b/_test/meowpp_Colors.cpp new file mode 100644 index 0000000..847f838 --- /dev/null +++ b/_test/meowpp_Colors.cpp @@ -0,0 +1,124 @@ +#include "meowpp.h" + +TEST(Colors){ + meow::RGBf rgb, rgb2; + meow::YUVf yuv, yuv2; + meow::HSLf hsl, hsl2; + meow::HSVf hsv, hsv2; + bool ok = true; + double eps; + eps = 1e-8; + meow::messagePrintf(1, "rgb ---> hsl ---> rgb ---> hsl (eps = %e)", eps); + for(int i = 0; ok && i < 100000; i++){ + rgb.r(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, rgb.rMin(), rgb.rMax())); + rgb.g(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, rgb.gMin(), rgb.gMax())); + rgb.b(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, rgb.bMin(), rgb.bMax())); + meow::RGB_to_HSL(rgb , &hsl ); + meow::HSL_to_RGB(hsl , &rgb2); + meow::RGB_to_HSL(rgb2, &hsl2); + if(meow::noEPS(rgb.r() - rgb2.r(), eps) != 0 || + meow::noEPS(rgb.g() - rgb2.g(), eps) != 0 || + meow::noEPS(rgb.b() - rgb2.b(), eps) != 0) ok = false; + if(meow::noEPS(hsl.h() - hsl2.h(), eps) != 0 || + meow::noEPS(hsl.s() - hsl2.s(), eps) != 0 || + meow::noEPS(hsl.l() - hsl2.l(), eps) != 0) ok = false; + } + if(ok) meow::messagePrintf(-1, "ok!"); + else{ meow::messagePrintf(-1, "fail"); return false; } + // + eps = 1e-8; + meow::messagePrintf(1, "rgb ---> hsv ---> rgb ---> hsv (eps = %e)", eps); + for(int i = 0; ok && i < 100000; i++){ + rgb.r(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, rgb.rMin(), rgb.rMax())); + rgb.g(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, rgb.gMin(), rgb.gMax())); + rgb.b(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, rgb.bMin(), rgb.bMax())); + meow::RGB_to_HSV(rgb , &hsv ); + meow::HSV_to_RGB(hsv , &rgb2); + meow::RGB_to_HSV(rgb2, &hsv2); + if(meow::noEPS(rgb.r() - rgb2.r(), eps) != 0 || + meow::noEPS(rgb.g() - rgb2.g(), eps) != 0 || + meow::noEPS(rgb.b() - rgb2.b(), eps) != 0) ok = false; + if(meow::noEPS(hsv.h() - hsv2.h(), eps) != 0 || + meow::noEPS(hsv.s() - hsv2.s(), eps) != 0 || + meow::noEPS(hsv.v() - hsv2.v(), eps) != 0) ok = false; + } + if(ok) meow::messagePrintf(-1, "ok!"); + else{ meow::messagePrintf(-1, "fail"); return false; } + // + /* + eps = 1e-3; + meow::messagePrintf(1, "yuv ---> hsl ---> yuv ---> hsl"); + for(int i = 0; ok && i < 100000; i++){ + yuv.y(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, yuv.yMin(), yuv.yMax())); + yuv.u(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, yuv.uMin(), yuv.uMax())); + yuv.v(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, yuv.vMin(), yuv.vMax())); + meow::YUV_to_HSL(yuv , &hsl ); + meow::HSL_to_YUV(hsl , &yuv2); + meow::YUV_to_HSL(yuv2, &hsl2); + if(meow::noEPS(yuv.y() - yuv2.y(), eps) != 0 || + meow::noEPS(yuv.u() - yuv2.u(), eps) != 0 || + meow::noEPS(yuv.v() - yuv2.v(), eps) != 0) ok = false; + if(meow::noEPS(hsl.h() - hsl2.h(), eps) != 0 || + meow::noEPS(hsl.s() - hsl2.s(), eps) != 0 || + meow::noEPS(hsl.l() - hsl2.l(), eps) != 0) ok = false; + } + if(ok) meow::messagePrintf(-1, "ok!"); + else{ meow::messagePrintf(-1, "fail"); return false; } + // */ + /* + meow::messagePrintf(1, "yuv ---> hsv ---> yuv ---> hsv"); + for(int i = 0; ok && i < 100000; i++){ + yuv.y(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, yuv.yMin(), yuv.yMax())); + yuv.u(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, yuv.uMin(), yuv.uMax())); + yuv.v(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, yuv.vMin(), yuv.vMax())); + meow::YUV_to_HSV(yuv , &hsv ); + meow::HSV_to_YUV(hsv , &yuv2); + meow::YUV_to_HSV(yuv2, &hsv2); + if(meow::noEPS(yuv.y() - yuv2.y(), eps) != 0 || + meow::noEPS(yuv.u() - yuv2.u(), eps) != 0 || + meow::noEPS(yuv.v() - yuv2.v(), eps) != 0) ok = false; + if(meow::noEPS(hsv.h() - hsv2.h(), eps) != 0 || + meow::noEPS(hsv.s() - hsv2.s(), eps) != 0 || + meow::noEPS(hsv.v() - hsv2.v(), eps) != 0) ok = false; + } + if(ok) meow::messagePrintf(-1, "ok!"); + else{ meow::messagePrintf(-1, "fail"); return false; } + // */ + eps = 1e-3; + meow::messagePrintf(1, "rgb ---> yuv ---> rgb ---> yuv (eps = %e)", eps); + for(int i = 0; ok && i < 100000; i++){ + rgb.r(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, rgb.rMin(), rgb.rMax())); + rgb.g(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, rgb.gMin(), rgb.gMax())); + rgb.b(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, rgb.bMin(), rgb.bMax())); + meow::RGB_to_YUV(rgb , &yuv ); + meow::YUV_to_RGB(yuv , &rgb2); + meow::RGB_to_YUV(rgb2, &yuv2); + if(meow::noEPS(rgb.r() - rgb2.r(), eps) != 0 || + meow::noEPS(rgb.g() - rgb2.g(), eps) != 0 || + meow::noEPS(rgb.b() - rgb2.b(), eps) != 0) ok = false; + if(meow::noEPS(yuv.y() - yuv2.y(), eps) != 0 || + meow::noEPS(yuv.u() - yuv2.u(), eps) != 0 || + meow::noEPS(yuv.v() - yuv2.v(), eps) != 0) ok = false; + } + if(ok) meow::messagePrintf(-1, "ok!"); + else{ meow::messagePrintf(-1, "fail"); return false; } + eps = 1e-8; + meow::messagePrintf(1, "hsl ---> hsv ---> hsl ---> hsv (eps = %e)", eps); + for(int i = 0; ok && i < 100000; i++){ + hsl.h(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, hsl.hMin(), hsl.hMax())); + hsl.s(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, hsl.sMin(), hsl.sMax())); + hsl.l(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, hsl.lMin(), hsl.lMax())); + meow::HSL_to_HSV(hsl , &hsv ); + meow::HSV_to_HSL(hsv , &hsl2); + meow::HSL_to_HSV(hsl2, &hsv2); + if(meow::noEPS(hsl.h() - hsl2.h(), eps) != 0 || + meow::noEPS(hsl.s() - hsl2.s(), eps) != 0 || + meow::noEPS(hsl.l() - hsl2.l(), eps) != 0) ok = false; + if(meow::noEPS(hsv.h() - hsv2.h(), eps) != 0 || + meow::noEPS(hsv.s() - hsv2.s(), eps) != 0 || + meow::noEPS(hsv.v() - hsv2.v(), eps) != 0) ok = false; + } + if(ok) meow::messagePrintf(-1, "ok!"); + else{ meow::messagePrintf(-1, "fail"); return false; } + return true; +}; diff --git a/_test/meowpp_DisjointSet.cpp b/_test/meowpp_DisjointSet.cpp new file mode 100644 index 0000000..b871c4d --- /dev/null +++ b/_test/meowpp_DisjointSet.cpp @@ -0,0 +1,79 @@ +#include "meowpp.h" + +#include + +TEST(DisjointSet){ + int N = 10000000; + meow::DisjointSet dsj(N); + + meow::messagePrintf(1, "merge(0, 1) merge(0, 2) merge(0, 3) ... (N = %d)", N); + for(int i = 1; i < N; i++){ + dsj.merge(0, i); + } + int root = dsj.root(0); + for(int i = 1; i < N; i++){ + if(root != dsj.root(i)){ + meow::messagePrintf(-1, "fail"); + return false; + } + } + meow::messagePrintf(-1, "ok"); + // + + dsj.reset(N); + meow::messagePrintf(1, "merge(0, 1) merge(1, 2) merge(2, 3) ... (N = %d)", N); + for(int i = 1; i < N; i++){ + dsj.merge(i - 1, i); + } + root = dsj.root(0); + for(int i = 1; i < N; i++){ + if(root != dsj.root(i)){ + meow::messagePrintf(-1, "fail"); + return false; + } + } + meow::messagePrintf(-1, "ok"); + // + + int M = 1000; + N = 1000000; + dsj.reset(N); + std::vector used(N, -1); + std::vector nums[M]; + + meow::messagePrintf(1, "random test (N = %d)", N); + for(int i = 0; i < N / 10; i++){ + int grp = rand() % M; + int who; + while(used[who = rand() % N] != -1); + nums[grp].push_back(who); + used[who] = grp; + } + meow::messagePrintf(0, "data created"); + for(int i = 0; i < M; i++){ + for(int k = 0; k < 100; k++){ + int j1 = rand() % nums[i].size(); + int j2 = rand() % nums[i].size(); + dsj.merge(nums[i][j1], nums[i][j2]); + } + for(size_t j = 1; j < nums[i].size(); j++){ + dsj.merge(nums[i][0], nums[i][j]); + } + } + for(int i = 0; i < N; i++){ + bool ok = false; + if(used[i] == -1 && dsj.root(i) == i){ + ok = true; + }else{ + if(dsj.root(i) == dsj.root(nums[used[i]][0])){ + ok = true; + } + } + if(!ok){ + meow::messagePrintf(-1, "fail"); + return false; + } + } + meow::messagePrintf(-1, "ok"); + return true; +}; diff --git a/_test/meowpp_KD_Tree.cpp b/_test/meowpp_KD_Tree.cpp new file mode 100644 index 0000000..dcbda5f --- /dev/null +++ b/_test/meowpp_KD_Tree.cpp @@ -0,0 +1,186 @@ +#include "meowpp.h" + +#include + +#include +#include +#include +#include +#include + +static int N = 10000; +static int D = 5; + +static double dist2(std::vector const& v1, std::vector const& v2){ + double ret = 0; + for(int i = 0; i < D; i++){ + ret += meow::squ(v1[i] - v2[i]); + } + return ret; +} + +static std::vector< std::vector > data; +static std::vector< double > dist; +static std::vector< int > order; + + +struct Answer{ + double dist; + int id; + Answer(double _dist, int _id): dist(_dist), id(_id){ } + bool operator<(Answer const& b) const{ + if(dist != b.dist) return (dist < b.dist); + return (id < b.id); + } +}; + + +static void find(std::vector const& v, int k){ + std::priority_queue qu; + for(int i = 0; i < k; i++){ + qu.push(Answer(dist2(v, data[i]), i)); + } + for(int i = k; i < N; i++){ + qu.push(Answer(dist2(v, data[i]), i)); + qu.pop(); + } + order.resize(k); + for(int i = qu.size() - 1; i >= 0; i--){ + order[i] = qu.top().id; + qu.pop(); + } +} + +static std::vector v; + +static bool sf(const int& a, const int& b){ + if(dist[a] != dist[b]) + return (dist[a] < dist[b]); + return (a < b); +} + +static void show(std::vector const& ask, std::vector kd, std::vector me, int k){ + if(N <= 30 && D <= 3){ + printf("\nData:\n"); + for(int i = 0; i < N; i++){ + printf(" %2d) <", i); + for(int j = 0; j < D; j++){ + printf("%.7f", data[i][j]); + if(j < D - 1) printf(", "); + else printf(">"); + } + printf("\n"); + } + printf("Ask <"); + for(int j = 0; j < D; j++){ + printf("%.7f", ask[j]); + if(j < D - 1) printf(", "); + else printf(">"); + } + printf("\n"); + printf("MyAnswer: "); + for(int i = 0; i < k; i++) printf("%d ", me[i]); + printf("\n"); + printf("KdAnswer: "); + for(int i = 0; i < k; i++) printf("%d ", kd[i]); + printf("\n"); + order.resize(N); + dist .resize(N); + for(int i = 0; i < N; i++){ + dist [i] = dist2(ask, data[i]); + order[i] = i; + } + std::sort(order.begin(), order.end(), sf); + printf("Sorted:\n"); + for(int i = 0; i < N; i++){ + printf(" %2d) <", order[i]); + for(int j = 0; j < D; j++){ + printf("%.7f", data[order[i]][j]); + if(j < D - 1) printf(", "); + else printf(">"); + } + printf(" ((%.7f))", dist[order[i]]); + printf("\n"); + } + } +} + +struct Node{ + std::vector v; + int id; + double& operator[](size_t d) { return v[d]; } + double operator[](size_t d) const { return v[d]; } + bool operator<(Node const& n) const{ return (id < n.id); } +}; + +TEST(KD_Tree){ + + int t0, t1, t2; + + meow::KD_Tree tree(D); + + meow::messagePrintf(1, "Create data (N = %d, D = %d)", N, D); + data.resize(N); + for(int i = 0; i < N; i++){ + data[i].resize(D); + Node nd; + nd.v.resize(D); + nd.id = i; + for(int j = 0; j < D; j++){ + data[i][j] = 12345.0 * (1.0 * rand() / RAND_MAX - 0.3); + nd[j] = data[i][j]; + } + tree.insert(nd); + } + meow::messagePrintf(-1, "ok"); + meow::messagePrintf(1, "build"); + t0 = clock(); + tree.build(); + meow::messagePrintf(-1, "ok, %.3f seconds", (clock() - t0) * 1.0 / CLOCKS_PER_SEC); + + meow::messagePrintf(1, "query..."); + v.resize(D); + meow::KD_Tree::Vectors ret; + int id; + for(int k = 1; k <= std::min(100, N); k++){ + meow::messagePrintf(1, "range k = %d", k); + t1 = t2 = 0; + for(int i = 0; i < 10; i++){ + Node nd; + nd.v.resize(D); + for(int d = 0; d < D; d++){ + v[d] = 12345.0 * (1.0 * rand() / RAND_MAX - 0.3); + nd[d] = v[d]; + } + t0 = clock(); + tree.build(); + ret = tree.query(nd, k, true); + t1 += clock() - t0; + + t0 = clock(); + find(v, k); + t2 += clock() - t0; + if(ret.size() != std::min(k, N)){ + meow::messagePrintf(-1, "(%d)query fail, size error", i); + meow::messagePrintf(-1, "fail"); + return false; + } + for(int kk = 1; kk <= k; kk++){ + if(order[kk - 1] != ret[kk - 1].id){ + //show(v, ret, order, k); + meow::messagePrintf(-1, "(%d)query fail", i); + meow::messagePrintf(-1, "fail"); + return false; + } + } + } + meow::messagePrintf(-1, "ok %.3f/%.3f", + t1 * 1.0 / CLOCKS_PER_SEC, + t2 * 1.0 / CLOCKS_PER_SEC + ); + } + meow::messagePrintf(-1, "ok"); + + + return true; +}; diff --git a/_test/meowpp_MergeableHeap.cpp b/_test/meowpp_MergeableHeap.cpp new file mode 100644 index 0000000..c4814da --- /dev/null +++ b/_test/meowpp_MergeableHeap.cpp @@ -0,0 +1,71 @@ +#include "meowpp.h" + +#include +#include +#include + + +TEST(MergeableHeap){ + int N = 10; + std::vector > nhp; + std::vector > mhp; + for(int i = 0; i < 10; i++){ + int MM = 5000 + rand() % 10000; + meow::messagePrintf(1, "%d-th test (M = %5d)", i, MM); + nhp.clear(); nhp.resize(N); + mhp.clear(); mhp.resize(N); + int tn = 0, tm = 0, t0; + for(int j = 0; j < MM; j++){ + if((rand() & 3) == 0){ + int a = rand() % N; + int num = rand(); + t0 = clock(); nhp[a].push(num); tn += clock() - t0; + t0 = clock(); mhp[a].push(num); tm += clock() - t0; + }else if(rand() & 1){ + int a = rand() % N; + t0 = clock(); + if(!nhp[a].empty()) nhp[a].pop(); + tn += clock() - t0; + t0 = clock(); + if(!mhp[a].empty()) mhp[a].pop(); + tm += clock() - t0; + }else{ + int a = rand() % N, b = rand() % N; + if(b == a) b = (b + 1) % N; + t0 = clock(); + for( ; !nhp[b].empty(); nhp[b].pop()){ + nhp[a].push(nhp[b].top()); + } + tn += clock() - t0; + t0 = clock(); + mhp[a].merge(&mhp[b]); + tm += clock() - t0; + } + } + bool ok = true; + for(int j = 0; j < N; j++){ + while(!nhp[j].empty() && !mhp[j].empty()){ + if(nhp[j].top() != mhp[j].top()){ + ok = false; + break; + } + nhp[j].pop(); + mhp[j].pop(); + } + if(mhp[j].empty() != nhp[j].empty()){ + ok = false; + } + if(ok == false) break; + } + ok = true; + if(!ok){ + meow::messagePrintf(-1, "fail"); + return false; + }else{ + meow::messagePrintf(-1, "ok %.3f/%.3f", + tm * 1.0 / CLOCKS_PER_SEC, + tn * 1.0 / CLOCKS_PER_SEC ); + } + } + return true; +}; diff --git a/_test/meowpp_SegmentTree.cpp b/_test/meowpp_SegmentTree.cpp new file mode 100644 index 0000000..777ca9d --- /dev/null +++ b/_test/meowpp_SegmentTree.cpp @@ -0,0 +1,154 @@ +#include "meowpp.h" + +#include +#include + +struct RangeMax{ + int value; + // + RangeMax(){} + RangeMax(int _value): value(_value){ } + RangeMax(RangeMax const& b): value(b.value){ } + // + RangeMax operator*(size_t n) const{ return RangeMax(value); } + RangeMax operator|(RangeMax const& b) const{ return RangeMax(std::max(value, b.value)); } + RangeMax operator+(RangeMax const& b) const{ return RangeMax(b.value + value); } + bool operator==(RangeMax const& b) const{ return (value == b.value); } +}; +struct RangeSum{ + int value; + // + RangeSum(){} + RangeSum(int _value): value(_value){ } + RangeSum(RangeSum const& b): value(b.value){ } + // + RangeSum operator*(size_t n) const{ return RangeSum(n * value); } + RangeSum operator|(RangeSum const& b) const{ return RangeSum(value + b.value); } + RangeSum operator+(RangeSum const& b) const{ return RangeSum(b.value + value); } + bool operator==(RangeSum const& b) const{ return (value == b.value); } +}; + +meow::SegmentTree s_max; +meow::SegmentTree s_sum; + +static int N = 1000000; + +std::vector array; + +void override(int a, int b, int c){ + for(int i = a; i <= b; i++) + array[i] = c; +} +void offset(int a, int b, int c){ + for(int i = a; i <= b; i++) + array[i] += c; +} +int bmax(int a, int b){ + int ret = array[a]; + for(int i = a + 1; i <= b; i++) + ret = std::max(ret, array[i]); + return ret; +} +int bsum(int a, int b){ + int sum = 0; + for(int i = a; i <= b; i++) + sum += array[i]; + return sum; +} + +void show(){ + if(N <= 20){ + printf("\n"); + printf("Me : "); + for(int i = 0; i < N; i++){ + printf("%4d ", array[i]); + } + printf("\n"); + printf("Sum: "); + for(int i = 0; i < N; i++){ + printf("%4d ", s_sum.query(i, i).value); + } + printf("\n"); + printf("Max: "); + for(int i = 0; i < N; i++){ + printf("%4d ", s_max.query(i, i).value); + } + printf("\n"); + } +} + +TEST(SegmentTree){ + s_max.reset(N); + s_sum.reset(N); + s_max.override(0, N - 1, RangeMax(0)); + s_sum.override(0, N - 1, RangeSum(0)); + array.resize(N, 0); + + for(int z = 0; z < 10; z++){ + meow::messagePrintf(1, "test %d", z); + int tMe = 0, tSeg = 0, t0; + int NN = 1 + rand() % 100; + for(int i = 0; i < NN; i++){ + int a = rand() % N; + int b = rand() % (N - a) + a; + int k = rand() % 20000 - 10000; + bool over = (rand() % 2 == 1); + if(over){ + t0 = clock(); + s_max.override(a, b, RangeMax(k)); + s_sum.override(a, b, RangeSum(k)); + tSeg += clock() - t0; + t0 = clock(); + override(a, b, k); + tMe += clock() - t0; + }else{ + t0 = clock(); + s_max.offset(a, b, RangeMax(k)); + s_sum.offset(a, b, RangeSum(k)); + tSeg = clock() - t0; + t0 = clock(); + offset(a, b, k); + tMe += clock() - t0; + } + /* + printf("\n"); + printf("%s %d~%d with %d", over ? "override" : "offset", a, b, k); + show(); + printf("max:"); s_max.print(); + printf("sum:"); s_sum.print(); + // */ + } + NN = 1 + rand() % 100; + for(int i = 0; i < NN; i++){ + int a = rand() % N; + int b = rand() % (N - a) + a; + + t0 = clock(); + RangeMax m(s_max.query(a, b)); + RangeSum s(s_sum.query(a, b)); + tSeg += clock() - t0; + t0 = clock(); + int mm = bmax(a, b); + int ss = bsum(a, b); + tMe += clock() - t0; + if(m.value != mm){ + printf("ask %d~%d, me %d/%d seg %d/%d\n", a, b, mm, ss, m.value, s.value); + meow::messagePrintf(-1, "range-max query fail"); + return false; + } + if(s.value != ss){ + printf("ask %d~%d, max/sum = me %d/%d seg %d/%d\n", a, b, mm, ss, m.value, s.value); + meow::messagePrintf(-1, "range-sum query fail"); + return false; + } + } + meow::messagePrintf(-1, "ok, %.3f/%.3f", + 1.0 * tSeg / CLOCKS_PER_SEC, + 1.0 * tMe / CLOCKS_PER_SEC); + s_max.reset(N); + s_sum.reset(N); + array.clear(); + array.resize(N, 0); + } + return true; +}; diff --git a/_test/meowpp_SplayTree.cpp b/_test/meowpp_SplayTree.cpp new file mode 100644 index 0000000..0d1e2f2 --- /dev/null +++ b/_test/meowpp_SplayTree.cpp @@ -0,0 +1,503 @@ +#include "meowpp.h" + +#include +#include +#include +#include + +static int N; + +static bool detail_fg; + +typedef typename std::map :: iterator IterN; +typedef typename std::map ::reverse_iterator IterR; +typedef typename meow::SplayTree::Element IterS; + +static std::vector< std::map > normal; +static std::vector > splay; + +static void show(bool fg = false){ + if(fg){ + for(int i = 0; i < N; i++){ + printf("normal %d-%lu: ", i, normal[i].size()); + for(IterN it = normal[i].begin(); it != normal[i].end(); it++){ + printf("%d/%.2f ", it->first, it->second); + } + printf("\n"); + printf("splay %d-%lu: ", i, splay[i].size()); + bool bye = false; + for(int j = 0; j < splay[i].size(); j++){ + IterS it = splay[i].order(j); + printf("%d/%.2f ", it->first, it->second); + } + printf("\n"); + } + printf("\n"); + } +} + +static bool lowerBound(int i, int key, size_t* tN, size_t* tS){ + size_t t0; + detail_fg && printf("============= lowerBound(%d, %d)\n", i, key); + t0 = clock(); IterS b = splay [i].lowerBound (key); (*tS) += clock() - t0; + t0 = clock(); IterN a = normal[i].lower_bound(key); (*tN) += clock() - t0; + detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n", + (a == normal[i].end()) ? 0 : a->first, + (b == splay[i].end()) ? 0 : b->first, + (a == normal[i].end()) ? 0 : a->second, + (b == splay[i].end()) ? 0 : b->second); + show(detail_fg); + if((a == normal[i].end()) != (b == splay[i].end())) return false; + if( a == normal[i].end()) return true; + return (a->first == b->first && a->second == b->second); +} +static bool upperBound(int i, int key, size_t* tN, size_t* tS){ + size_t t0; + detail_fg && printf("============= upperBound(%d, %d)\n", i, key); + t0 = clock(); IterS b = splay [i].upperBound (key); (*tS) += clock() - t0; + t0 = clock(); IterN a = normal[i].upper_bound(key); (*tN) += clock() - t0; + detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n", + (a == normal[i].end()) ? 0 : a->first, + (b == splay [i].end()) ? 0 : b->first, + (a == normal[i].end()) ? 0 : a->second, + (b == splay [i].end()) ? 0 : b->second); + show(detail_fg); + if((a == normal[i].end()) != (b == splay[i].end())) return false; + if( a == normal[i].end()) return true; + return (a->first == b->first && a->second == b->second); +} +static bool rLowerBound(int i, int key, size_t* tN, size_t* tS){ + size_t t0; + detail_fg && printf("============= rLowerBound(%d, %d)\n", i, key); + t0 = clock(); IterS b = splay [i].rLowerBound(key); (*tS) += clock() - t0; + t0 = clock(); + IterN a, z; + if(normal[i].size() == 0 || normal[i].begin()->first > key){ + a = normal[i].end(); + }else{ + for(a = normal[i].begin(), z = a, z++; z != normal[i].end(); z++, a++){ + if(z->first > key){ + break; + } + } + } + detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n", + (a == normal[i].end()) ? 0 : a->first, + (b == splay[i].end()) ? 0 : b->first, + (a == normal[i].end()) ? 0 : a->second, + (b == splay[i].end()) ? 0 : b->second); + show(detail_fg); + if((a == normal[i].end()) != (b == splay[i].end())) return false; + if( a == normal[i].end()) return true; + return (a->first == b->first && a->second == b->second); +} +static bool rUpperBound(int i, int key, size_t* tN, size_t* tS){ + size_t t0; + detail_fg && printf("============= rUpperBound(%d, %d)\n", i, key); + t0 = clock(); IterS b = splay [i].rUpperBound(key); (*tS) += clock() - t0; + t0 = clock(); + IterN a, z; + if(normal[i].begin() == normal[i].end()){ + a = normal[i].end(); + }else{ + if(normal[i].begin()->first >= key) a = normal[i].end(); + else{ + for(a = normal[i].begin(), z = a, z++; z != normal[i].end(); a++, z++){ + if(z->first >= key) + break; + } + } + } + detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n", + (a == normal[i].end()) ? 0 : a->first, + (b == splay[i].end()) ? 0 : b->first, + (a == normal[i].end()) ? 0 : a->second, + (b == splay[i].end()) ? 0 : b->second); + show(detail_fg); + if((a == normal[i].end()) != (b == splay[i].end())) return false; + if( a == normal[i].end()) return true; + return (a->first == b->first && a->second == b->second); +} +static bool find(int i, int key, size_t* tN, size_t* tS){ + size_t t0; + detail_fg && printf("============= find(%d, %d)\n", i, key); + t0 = clock(); IterS b = splay [i].find(key); (*tS) += clock() - t0; + t0 = clock(); IterN a = normal[i].find(key); (*tN) += clock() - t0; + detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n", + (a == normal[i].end()) ? 0 : a->first, + (b == splay[i].end()) ? 0 : b->first, + (a == normal[i].end()) ? 0 : a->second, + (b == splay[i].end()) ? 0 : b->second); + show(detail_fg); + if((a == normal[i].end()) != (b == splay[i].end())) return false; + if( a == normal[i].end()) return true; + return (a->first == b->first && a->second == b->second); +} +static bool order(int i, int order, size_t* tN, size_t* tS){ + size_t t0; + detail_fg && printf("============= order(%d, %d)\n", i, order); + t0 = clock(); IterS b = splay[i].order(order); (*tS) += clock() - t0; + t0 = clock(); + IterN a = normal[i].begin(); + for(int k = 0; k < order; k++) a++; + (*tN) += clock() - t0; + detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n", + (a == normal[i].end()) ? 0 : a->first, + (b == splay[i].end()) ? 0 : b->first, + (a == normal[i].end()) ? 0 : a->second, + (b == splay[i].end()) ? 0 : b->second); + show(detail_fg); + if((a == normal[i].end()) != (b == splay[i].end())) return false; + if( a == normal[i].end()) return true; + return (a->first == b->first && a->second == b->second); +} +static bool first_last(int i, size_t* tN, size_t* tS){ + size_t t0; + detail_fg && printf("============= first_last(%d)\n", i); + IterN a; + t0 = clock(); IterS b = splay[i].first (); (*tS) += clock() - t0; + t0 = clock(); a = normal[i].begin(); (*tN) += clock() - t0; + detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n", + (a == normal[i].end()) ? 0 : a->first, + (b == splay[i].end()) ? 0 : b->first, + (a == normal[i].end()) ? 0 : a->second, + (b == splay[i].end()) ? 0 : b->second); + if((a == normal[i].end()) != (b == splay[i].end())) return false; + if( a == normal[i].end()); + else{ + if((a->first == b->first && a->second == b->second) == false){ + return false; + } + } + t0 = clock(); b = splay[i].last (); (*tS) += clock() - t0; + t0 = clock(); IterR r = normal[i].rbegin(); (*tN) += clock() - t0; + detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n", + (r == normal[i].rend()) ? 0 : r->first, + (b == splay[i].end()) ? 0 : b->first, + (r == normal[i].rend()) ? 0 : r->second, + (b == splay[i].end()) ? 0 : b->second); + if((r == normal[i].rend()) != (b == splay[i].end())) return false; + if(r == normal[i].rend()); + else{ + if((r->first == b->first && r->second == b->second) == false){ + return false; + } + } + return true; +} +static bool insert(int i, int key, double val, size_t* tN, size_t* tS){ + size_t t0; + if(rand() & 1){ + t0 = clock(); splay [i].insert(key, val); (*tS) += clock() - t0; + t0 = clock(); normal[i].insert(std::pair(key, val)); (*tN) += clock() - t0; + }else{ + t0 = clock(); splay [i][key] = val; (*tS) += clock() - t0; + t0 = clock(); normal[i][key] = val; (*tN) += clock() - t0; + } + detail_fg && printf("============= insert(%d, %d)\n", i, key); + show(detail_fg); + return true; +} +static bool split(int i, int j, int key, size_t* tN, size_t* tS){ + size_t t0; + if(i == j){ + return true; + } + detail_fg && printf("============= split(%d, %d, %d)\n", i, j, key); + t0 = clock(); splay[i].splitOut(key, &splay[j]); *tS += clock() - t0; + t0 = clock(); + normal[j].clear(); + for(IterN it; (it = normal[i].upper_bound(key)) != normal[i].end(); ){ + normal[j].insert(*it); + normal[i].erase(it); + } + *tN += clock() - t0; + show(detail_fg); + return true; +} +static bool merge(int i, int j, int key, size_t* tN, size_t* tS){ + size_t t0; + if(i == j){ + return true; + } + if(rand() & 1){ + t0 = clock(); + if(splay[i].size() > 0) + while(splay[j].size() > 0 && + splay[j].first()->first <= splay[i].last()->first){ + splay[j].erase(splay[j].first()->first); + } + *tS += clock() - t0; + t0 = clock(); + if(normal[i].size() > 0) + while(normal[j].size() > 0 && + normal[j].begin()->first <= normal[i].rbegin()->first) + normal[j].erase(normal[j].begin()); + *tN += clock() - t0; + } + t0 = clock(); splay[i].merge(&splay[j]); *tS += clock() - t0; + t0 = clock(); + if(normal[i].size() == 0 || normal[j].size() == 0 || + normal[i].rbegin()->first < normal[j].begin()->first || + normal[j].rbegin()->first < normal[i].begin()->first + ){ + for(IterN it = normal[j].begin(); it != normal[j].end(); it++){ + normal[i].insert(*it); + } + normal[j].clear(); + } + *tN += clock() - t0; + detail_fg && printf("============= merge(%d, %d)\n", i, j, key); + show(detail_fg); + return true; +} +static bool erase(int i, int key, size_t* tN, size_t* tS){ + size_t t0; + detail_fg && printf("============= erase(%d, %d)\n", i, key); + t0 = clock(); splay[i].erase(key); (*tS) += clock() - t0; + t0 = clock(); normal[i].erase(key); (*tN) += clock() - t0; + show(detail_fg); + return true; +} +static bool keyOffset(int i, int delta, size_t* tN, size_t* tS){ + size_t t0; + detail_fg && printf("============= keyOffset(%d, %d)\n", i, delta); + t0 = clock(); splay[i].keyOffset(delta); (*tS) += clock() - t0; + t0 = clock(); + std::map tmp = normal[i]; + normal[i].clear(); + for(IterN it = tmp.begin(); it != tmp.end(); it++){ + normal[i].insert(std::pair(it->first + delta, it->second)); + } + (*tN) += clock() - t0; + show(detail_fg); + return true; +} +/* +static bool valueOffset(int i, double delta, size_t* tN, size_t* tS){ + size_t t0; + detail_fg && printf("============= valueOffset(%d, %f)\n", i, delta); + t0 = clock(); splay[i].valueOffset(delta); (*tS) += clock() - t0; + t0 = clock(); + for(IterN it = normal[i].begin(); it != normal[i].end(); it++){ + it->second += delta; + } + (*tN) += clock() - t0; + show(detail_fg); + return true; +} +// */ +static bool copy(int i, int j, size_t* tN, size_t* tS){ + size_t t0; + detail_fg && printf("copy(%d, %d)\n", i, j); + t0 = clock(); splay[i] = splay[j]; (*tS) += clock() - t0; + t0 = clock(); normal[i] = normal[j]; (*tN) += clock() - t0; + show(detail_fg); + return true; +} + +static bool check(){ + for(int i = 0; i < N; i++){ + if(normal[i].size() != splay[i].size()) return false; + int j = 0; + for(IterN it = normal[i].begin(); it != normal[i].end(); it++, j++){ + if(it->first != splay[i].order(j)->first || + it->second != splay[i].order(j)->second) + return false; + } + } + return true; +} + +TEST(SplayTree){ + detail_fg = false; + N = 5; + for(int i = 0; i < 10; i++){ + normal.clear(); + splay .clear(); + normal.resize(N); + splay .resize(N); + size_t tn = 0, tm = 0; + int op = 1 + rand() % 2000000; + meow::messagePrintf(1, "%d-th test, N = %d, op = %7d", i, N, op); + while(op--){ + int wh = rand() % 60; + int i1 = rand() % N, i2, k = rand() % 60; + while((i2 = rand() % N) == i1); + switch(wh){ + case 0: + if(lowerBound(i1, k, &tn, &tm) == false){ + meow::messagePrintf(-1, "fail(%s)", "lowerBound"); + //for(int z = 0; z < N; z++){ splay[z].print(); } + show(true); + return false; + } + break; + case 1: + if(rUpperBound(i1, k, &tn, &tm) == false){ + meow::messagePrintf(-1, "fail(%s)", "rUpperBound"); + //for(int z = 0; z < N; z++){ splay[z].print(); } + show(true); + return false; + } + break; + case 2: + if(rLowerBound(i1, k, &tn, &tm) == false){ + meow::messagePrintf(-1, "fail(%s)", "rLowerBound"); + //for(int z = 0; z < N; z++){ splay[z].print(); } + show(true); + return false; + } + break; + case 3: + if(upperBound(i1, k, &tn, &tm) == false){ + meow::messagePrintf(-1, "fail(%s)", "upperBound"); + //for(int z = 0; z < N; z++){ splay[z].print(); } + show(true); + return false; + } + break; + case 4: + case 5: + case 6: + if(find(i1, k, &tn, &tm) == false){ + meow::messagePrintf(-1, "fail(%s)", "find"); + //for(int z = 0; z < N; z++){ splay[z].print(); } + show(true); + return false; + } + break; + case 7: + case 8: + case 9: + if(normal[i1].size() > 0){ + if(order(i1, rand() % normal[i1].size(), &tn, &tm) == false){ + meow::messagePrintf(-1, "fail(%s)", "order"); + //for(int z = 0; z < N; z++){ splay[z].print(); } + show(true); + return false; + } + break; + } + case 10: + if(first_last(i1, &tn, &tm) == false){ + meow::messagePrintf(-1, "fail(%s)", "first_last"); + //for(int z = 0; z < N; z++){ splay[z].print(); } + show(true); + return false; + } + break; + case 11: + case 12: + case 13: + case 14: + case 15: + case 16: + case 17: + case 18: + case 19: + case 20: + if(insert(i1, k, rand() * 1.0 / RAND_MAX * 50, &tn, &tm) == false){ + meow::messagePrintf(-1, "fail(%s)", "insert"); + //for(int z = 0; z < N; z++){ splay[z].print(); } + show(true); + return false; + } + break; + case 21: + case 22: + case 23: + case 24: + case 25: + case 26: + if(split(i1, i2, k, &tn, &tm) == false){ + meow::messagePrintf(-1, "fail(%s)", "split"); + //for(int z = 0; z < N; z++){ splay[z].print(); } + show(true); + return false; + } + break; + case 27: + case 28: + case 29: + case 30: + case 31: + case 32: + case 33: + case 34: + case 35: + case 36: + if(merge(i1, i2, k, &tn, &tm) == false){ + meow::messagePrintf(-1, "fail(%s)", "merge"); + //for(int z = 0; z < N; z++){ splay[z].print(); } + show(true); + return false; + } + break; + case 37: + case 38: + case 39: + case 40: + if(erase(i1, k, &tn, &tm) == false){ + meow::messagePrintf(-1, "fail(%s)", "erase"); + //for(int z = 0; z < N; z++){ splay[z].print(); } + show(true); + return false; + } + break; + case 41: + case 42: + case 43: + case 44: + case 45: + case 46: + case 47: + case 48: + case 49: + if(keyOffset(i1, ((rand() & 2) - 1) * k, &tn, &tm) == false){ + meow::messagePrintf(-1, "fail(%s)", "keyOffset"); + //for(int z = 0; z < N; z++){ splay[z].print(); } + show(true); + return false; + } + break; + case 50: + case 51: + case 52: + if(copy(i1, i2, &tn, &tm) == false){ + meow::messagePrintf(-1, "fail(%s)", "copy"); + //for(int z = 0; z < N; z++){ splay[z].print(); } + show(true); + return false; + } + break; + case 53: + case 54: + case 55: + case 56: + case 57: + case 58: + case 59: + op++; + /* + if(valueOffset(i1, 1.0 * rand() / RAND_MAX * 100, &tn, &tm) == false){ + meow::messagePrintf(-1, "fail(%s)", "valueOffset"); + //for(int z = 0; z < N; z++){ splay[z].print(); } + show(true); + return false; + } + break; + // */ + } + } + if(!check()){ + meow::messagePrintf(-1, "fail"); + show(true); + return false; + } + meow::messagePrintf(-1, "ok %.3f/%.3f", + tm * 1.0 / CLOCKS_PER_SEC, + tn * 1.0 / CLOCKS_PER_SEC); + } + return true; +}; diff --git a/footer.asciidoc b/footer.asciidoc index a6301ee..18c6751 100644 --- a/footer.asciidoc +++ b/footer.asciidoc @@ -16,6 +16,18 @@ https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&pag | Accept | 0.516 | http://codepad.org/03dW6ZHV[codepad] +| SplayTree + SegmentTree | 'Shuffling_cards' | +http://acm.csie.org/ntujudge/problem.php?id=1353[NTU-OJ] +http://www.spoj.com/problems/SHUFFLEK/[SPOJ] +| Accept/TLE | 6.910/--- | http://codepad.org/yUeiVZc0[codepad] + +| SplayTree + BinaryIndexTree | 'Shuffling_cards' | +http://acm.csie.org/ntujudge/problem.php?id=1353[NTU-OJ] +http://www.spoj.com/problems/SHUFFLEK/[SPOJ] +|Accept/Accept|5.480/44.35| http://codepad.org/GAWjEtmq[codepad] + + + |======================================================================= diff --git a/meowpp/dsa/BinaryIndexTree.h b/meowpp/dsa/BinaryIndexTree.h new file mode 100644 index 0000000..4b1b23a --- /dev/null +++ b/meowpp/dsa/BinaryIndexTree.h @@ -0,0 +1,69 @@ +#ifndef __BinaryIndexTree_H__ +#define __BinaryIndexTree_H__ + +namespace meow{ + //# + //#=== meow:: *BinaryIndexTree* (C++ class) + //#==== Description + //# 極度簡化版的 `SegmentTree` 已無法區間操作, 區間詢問的區間開頭也一定要 + //# 在 `index=0` 的地方 + //# + //#==== Template Class Operators Request + //#[options="header",width="70%",cols="1>m,1<,3 + class BinaryIndexTree{ + private: + std::vector _array; + public: + BinaryIndexTree(); + BinaryIndexTree(size_t __size, Value const& __value); + BinaryIndexTree(BinaryIndexTree const& __tree2); + + //#==== Support Methods + //# + //# * N <- `this` 中擁有的資料數 + //# + //#[options="header",width="100%",cols="1>m,3>s,7<,3<,3^,20<",grid="rows"] + //#|===================================================================== + //#|Const?|Name | Parameters | Return_Type| Time_Complexity| Description + + + //#||reset|(size_t `size`, Value const& `value`)|void|O(`size`) + //#|將資料長度刷成 `N = size` 且每一個元素都是 `value` + void reset(size_t __size, Value const& __value); + + + //#||update|(size_t `index`, Value const& `value`)|void|O(logN) + //#|將第 `index` (從零開始算) 多加上 `value` + void update( size_t __index, Value const& __value); + + + //#|const|query|(size_t `index`)|void|O(logN) + //#|詢問 `0~index` 的區間值 + Value query (ssize_t __index) const; + + + //#|===================================================================== + }; + //# + //#[NOTE] + //#======================================== + //# * 一般來說只能用在維護區間總和, 維護區間最大值只有在特殊情況才可以, 即 + //# '針對每個元素, 每次 update() 的值一定會大於等於原本的值' + //# * 若要用區間最大值 , 則 `Value` 的 `operator+` 要寫成 `std::max(...)` + //#======================================== + //# + //# ''' +} + +#include "BinaryIndexTree.hpp" + +#endif // BinaryIndexTree_H__ + diff --git a/meowpp/dsa/BinaryIndexTree.hpp b/meowpp/dsa/BinaryIndexTree.hpp new file mode 100644 index 0000000..e7e146a --- /dev/null +++ b/meowpp/dsa/BinaryIndexTree.hpp @@ -0,0 +1,44 @@ + +namespace meow{ + template + inline + BinaryIndexTree::BinaryIndexTree(): + _array(0){ + } + template + inline + BinaryIndexTree::BinaryIndexTree(size_t __size, Value const& __value): + _array(__size, __value){ + } + template + inline + BinaryIndexTree::BinaryIndexTree(BinaryIndexTree const& __tree2): + _array(__tree2._array){ + } + // + template + inline void + BinaryIndexTree::reset(size_t __size, Value const& __init){ + _array.clear(); + _array.resize(__size, __init); + } + // + template + inline void + BinaryIndexTree::update(size_t __index, Value const& __value){ + __index++; + for( ; __index <= _array.size(); __index += (__index & -__index)){ + _array[__index - 1] = _array[__index - 1] + __value; + } + } + template + inline Value + BinaryIndexTree::query(ssize_t __index) const{ + __index = std::min(__index + 1, (ssize_t)_array.size()); + Value ret(0); + for( ; 0 < __index; __index -= (__index & -__index)){ + ret = ret + _array[__index - 1]; + } + return ret; + } +} diff --git a/meowpp/dsa/SplayTree.h b/meowpp/dsa/SplayTree.h index 69b204e..38cbe7f 100644 --- a/meowpp/dsa/SplayTree.h +++ b/meowpp/dsa/SplayTree.h @@ -29,31 +29,27 @@ namespace meow{ Value _value; size_t _size; Node* _parent; - Node* _lChild; - Node* _rChild; + Node* _child[2]; // Node(Key const& __key, Value const& __value); + // + void keyOffset(Key const& __delta); + void syncDown() const; + void syncUp () const; }; // 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 const* setRoot(Node* __node) const; - // - Node* clear (Node* __node); - Node* dup (Node* __node); + void connect(Node const* __parent, size_t __left_right, + Node const* __child) const; + Node const* splay (Node const* __node) const; // - void rotate( Node* __parent, Node* __child) const; - void rotate(Node* __grand, Node* __parent, Node* __child) const; - Node* splay(Node* __node) const; + void clear(Node* __node); + Node* dup(Node* __node); // - Node* findKey (Node* __node, Key const& __key) const; - Node* findMinMax(Node* __node, bool minimum ) const; - Node* findOrder (Node* __node, size_t __order ) const; + 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); @@ -114,13 +110,13 @@ namespace meow{ //#|const|lowerBound|(Key const& `k`)|Element|O(logN) //#|找出第一個(最小的) Element且 `k` <= 它的 Key, 並且回傳之. //# 找不到的話回傳 `this->end()` - Element lowerBound(Key const& __key) const; + 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; + Element upperBound(Key const& __key) const; //#|const|lowerBound|(Key const& `k`)|Element|O(logN) @@ -163,22 +159,17 @@ namespace meow{ //#|const|size|()|size_t|O(1)| 回傳資料數 - size_t size() const; + size_t size() const; //#|const|size|()|bool|O(1)| 回傳是否為空 - bool empty() const; + bool empty() const; //#||clear|()|void|O(N)| 清空資料 void clear(); - //#||keyOffset|(Key const& `delta`)|void|O(1) - //#|將所有Element的Key同加上 `delta` - void keyOffset(Key const& __delta); - - //#||insert|(Key const& `key`,\Value const& `value`)|bool|O(logN) //#|檢查是否已有Element的Key 為 `key`, 若有則回傳 `false` , 否則將 //# 一個 (Key -> Value) = (`key` -> `value`)的Element加入, 並回傳 `true` @@ -192,6 +183,11 @@ namespace meow{ bool erase(Key const& __key); + //#||keyOffset|(Key const& `delta`)|void|O(1) + //#|將所有Element的Key同加上 `delta` + void keyOffset(Key const& __delta); + + //#||operator[]|(Key const& `key`)|Value&|O(logN) //#|檢查是否已有Element的Key 為 `key`, 若有則回傳相對應的Value的Reference //# 否則先執行 `insert(key, Value())` 再回傳相對應的Reference @@ -217,8 +213,8 @@ namespace meow{ //# 中的 Element 都搬到 `this` , 同時清空 `tree2` , 回傳 `true`. 否則 //# 回傳 `false` bool merge(SplayTree* __tree2); - // - // + + void print() const; //#|===================================================================== }; diff --git a/meowpp/dsa/SplayTree.hpp b/meowpp/dsa/SplayTree.hpp index 77331ef..de08f63 100644 --- a/meowpp/dsa/SplayTree.hpp +++ b/meowpp/dsa/SplayTree.hpp @@ -1,200 +1,154 @@ namespace meow{ + ///////////////////////////// **# Node #** ///////////////////////// + //////////////////// **# Node -- Constructure #** ////////////////// template - inline SplayTree::Node::Node(Key const& __key, - Value const& __value): - _key(__key), - _keyOffset(0), - _value(__value), - _size(1), - _parent(NULL), - _lChild(NULL), - _rChild(NULL){ } - // + inline + SplayTree::Node::Node(Key const& __key, Value const& __value): + _key(__key), _keyOffset(0), _value(__value){ + _size = 1; + _parent = NULL; + _child[0] = NULL; + _child[1] = NULL; + } + //////////////////////// **# Node -- Offset #** //////////////////// template inline void - SplayTree::offsetAdd(Node* __node, Key const& __delta) const{ - __node->_key = __node->_key + __delta; - __node->_keyOffset = __node->_keyOffset + __delta; + SplayTree::Node::keyOffset(Key const& __delta){ + _key = _key + __delta; + _keyOffset = _keyOffset + __delta; } + //////////////////////// **# Node -- sync #** ////////////////////// template inline void - SplayTree::sizeUpdate(Node* __node) const{ - if(__node != NULL){ - __node->_size = 1; - if(__node->_lChild != NULL) __node->_size += __node->_lChild->_size; - if(__node->_rChild != NULL) __node->_size += __node->_rChild->_size; + SplayTree::Node::syncDown() const{ + for(size_t i = 0; i < 2; i++){ + if(_child[i] == NULL) continue; + _child[i]->keyOffset(_keyOffset); } + ((Node*)this)->_keyOffset = Key(0); } template inline void - SplayTree::offsetDown(Node* __node) const{ - if(__node->_lChild != NULL) offsetAdd(__node->_lChild, __node->_keyOffset); - if(__node->_rChild != NULL) offsetAdd(__node->_rChild, __node->_keyOffset); - __node->_keyOffset = Key(0); + SplayTree::Node::syncUp() const{ + ((Node*)this)->_size = 1; + for(size_t i = 0; i < 2; i++){ + if(_child[i] == NULL) continue; + ((Node*)this)->_size += _child[i]->_size; + } } - // + ////////////////////////// **# SplayTree #** /////////////////////// + ///////////////////// **# connection, splay #** //////////////////// template inline void - SplayTree::connectLChild(Node* __parent, Node* __child) const{ - if(__parent != NULL) __parent->_lChild = __child; - if(__child != NULL) __child ->_parent = __parent; + SplayTree::connect(Node const* __parent, size_t __left_right, + Node const* __child) const{ + Node* parent = (Node*)__parent; + Node* child = (Node*)__child; + if(parent != NULL) parent->_child[__left_right] = child; + if(child != NULL) child ->_parent = parent; } template - inline void - SplayTree::connectRChild(Node* __parent, Node* __child) const{ - if(__parent != NULL) __parent->_rChild = __child; - if(__child != NULL) __child ->_parent = __parent; + inline typename SplayTree::Node const* + SplayTree::splay(Node const* __node) const{ + if(__node != NULL && __node->_parent != NULL){ + for(const Node *g_grand, *grand, *parent, *child = __node; ; ){ + g_grand = (grand = parent = child->_parent)->_parent; + size_t pc = (parent->_child[0] == child ? 0 : 1); + connect(parent, pc, child->_child[!pc]); + connect(child , !pc, parent); + if(g_grand != NULL){ + g_grand = (grand = g_grand)->_parent; + size_t gp = (grand->_child[0] == parent ? 0 : 1); + Node const* who = (pc == gp ? parent : child); + connect(grand, gp, who->_child[!gp]); + connect(who , !gp, grand); + grand->syncUp(); + } + parent->syncUp(); + child ->syncUp(); + if(g_grand == NULL){ + connect(NULL, 0, child); + break; + } + connect(g_grand, (g_grand->_child[0] == grand ? 0 : 1), child); + } + } + return (((SplayTree*)this)->_root = (Node*)__node); } - // + ///////////////////////// **# clear, dup #** /////////////////////// template - inline typename SplayTree::Node* + inline void SplayTree::clear(Node* __node){ - if(__node != NULL){ - clear(__node->_lChild); - clear(__node->_rChild); - delete __node; - } - return NULL; + if(__node == NULL) return ; + clear(__node->_child[0]); + clear(__node->_child[1]); + delete __node; } template inline typename SplayTree::Node* SplayTree::dup(Node* __node){ if(__node == NULL) return NULL; - offsetDown(__node); + __node->syncDown(); Node* node = new Node(__node->_key, __node->_value); - connectLChild(node, dup(__node->_lChild)); - connectRChild(node, dup(__node->_rChild)); - sizeUpdate(node); + connect(node, 0, dup(__node->_child[0])); + connect(node, 1, dup(__node->_child[1])); + node->syncUp(); return node; } + /////////////////////////// **# find #** /////////////////////////// template inline typename SplayTree::Node const* - SplayTree::setRoot(Node* __node) const{ - connectLChild(NULL, (((SplayTree*)this)->_root = __node)); - return _root; - } - // - template - inline void - SplayTree::rotate(Node* __parent, Node* __child) const{ - if(__parent->_lChild == __child){ - connectLChild(__parent, __child->_rChild); - connectRChild(__child , __parent); - }else{ - connectRChild(__parent, __child->_lChild); - connectLChild(__child , __parent); - } - sizeUpdate(__parent); - sizeUpdate(__child ); - } - template - inline void - SplayTree::rotate(Node* __grand, - Node* __parent, - Node* __child) const{ - if(__grand->_lChild == __parent){ - if(__parent->_lChild == __child){ - connectLChild(__grand , __parent->_rChild); - connectLChild(__parent, __child ->_rChild); - connectRChild(__child , __parent); - connectRChild(__parent, __grand ); - }else{ - connectRChild(__parent, __child->_lChild); - connectLChild(__grand , __child->_rChild); - connectLChild(__child, __parent); - connectRChild(__child, __grand ); - } - }else if(__grand->_rChild == __parent){ - if(__parent->_rChild == __child){ - connectRChild(__grand , __parent->_lChild); - connectRChild(__parent, __child ->_lChild); - connectLChild(__child , __parent); - connectLChild(__parent, __grand ); - }else{ - connectRChild(__grand , __child->_lChild); - connectLChild(__parent, __child->_rChild); - connectLChild(__child, __grand ); - connectRChild(__child, __parent); - } - } - sizeUpdate(__grand ); - sizeUpdate(__parent); - sizeUpdate(__child ); - } - template - inline typename SplayTree::Node* - SplayTree::splay(Node* __node) const{ - if(__node == NULL) return NULL; - for(Node *parent, *grand, *child = __node; child->_parent != NULL; ){ - parent = child ->_parent; - grand = parent->_parent; - if(grand == NULL){ - rotate(parent, child); - break; - }else{ - Node* g_grand = grand->_parent; - rotate(grand, parent, child); - if(g_grand == NULL) break; - if(g_grand->_lChild == grand) connectLChild(g_grand, child); - else connectRChild(g_grand, child); - } - } - sizeUpdate(__node); - return __node; - } - template - inline typename SplayTree::Node* - SplayTree::findKey(Node* __node, Key const& __key) const{ - Node* ret = __node; + SplayTree::findKey(Node const* __node, Key const& __key) const{ + Node const* ret = __node; while(__node != NULL){ - offsetDown(__node); + __node->syncDown(); ret = __node; if(!(__key < __node->_key)){ if(!(__node->_key< __key)) break; - __node = __node->_rChild; + __node = __node->_child[1]; }else{ - __node = __node->_lChild; + __node = __node->_child[0]; } } return ret; } template - inline typename SplayTree::Node* - SplayTree::findMinMax(Node* __node, bool minimum) const{ - Node* ret = __node; - while(__node != NULL){ - offsetDown(__node); + inline typename SplayTree::Node const* + SplayTree::findMinMax(Node const* __node, bool __minimum) const{ + Node const* ret = __node; + for(int i = __minimum ? 0 : 1; __node != NULL; __node = __node->_child[i]){ + __node->syncDown(); ret = __node; - __node = (minimum ? __node->_lChild : __node->_rChild); } return ret; } template - inline typename SplayTree::Node* - SplayTree::findOrder(Node* __node, size_t __order) const{ - Node* ret = __node; + inline typename SplayTree::Node const* + SplayTree::findOrder(Node const* __node, size_t __order) const{ + Node const* ret = __node; while(__node != NULL){ - offsetDown(__node); + __node->syncDown(); ret = __node; - size_t ord = 1 + (__node->_lChild == NULL ? 0 : __node->_lChild->_size); + size_t ord = 1 + (__node->_child[0]==NULL ? 0:__node->_child[0]->_size); if (ord == __order) return ret; - else if(ord < __order){ __node = __node->_rChild; __order -= ord; } - else { __node = __node->_lChild; } + else if(ord < __order){ __node = __node->_child[1]; __order -= ord; } + else { __node = __node->_child[0]; } } return ret; } + /////////////////////// **# split, merge #** /////////////////////// template inline void SplayTree::split(Node* __root, Node** __left, Node** __right){ if(__root == NULL){ *__left = NULL; *__right = NULL; return ; } - offsetDown(__root); + __root->syncDown(); *__left = __root; - *__right = __root->_rChild; + *__right = __root->_child[1]; if(*__right != NULL){ - (*__left )->_rChild = NULL; - (*__right)->_parent = NULL; - sizeUpdate(*__left); + (*__left )->_child[1] = NULL; + (*__right)->_parent = NULL; + (*__left )->syncUp(); } } template @@ -202,11 +156,12 @@ namespace meow{ SplayTree::merge(Node* __left, Node* __right){ if(__left == NULL) return __right; if(__right == NULL) return __left ; - offsetDown(__left); - connectRChild(__left, __right); - sizeUpdate(__left); + __left->syncDown(); + connect(__left, 1, __right); + __left->syncUp(); return __left; } + // template inline void SplayTree::print(Node* __now, int __depth) const{ if(__now == NULL) return ; @@ -215,12 +170,12 @@ namespace meow{ (long long unsigned)__now, __now->_size, (long long unsigned)__now->_parent, - (long long unsigned)__now->_lChild, - (long long unsigned)__now->_rChild); - print(__now->_lChild, __depth + 1); - print(__now->_rChild, __depth + 1); + (long long unsigned)__now->_child[0], + (long long unsigned)__now->_child[1]); + print(__now->_child[0], __depth + 1); + print(__now->_child[1], __depth + 1); } - // + ///////////////////////// **# Element ##* ////////////////////////// template inline void SplayTree::Element::reset(Node* __node){ _node = __node; @@ -228,25 +183,36 @@ namespace meow{ if(__node == NULL) _entry = NULL; else _entry = new Entry(__node->_key, __node->_value); } + // template - inline SplayTree::Element::Element(): - _entry(NULL), _node(NULL){ } + inline + SplayTree::Element::Element(): + _entry(NULL), _node(NULL){ + } template - inline SplayTree::Element::Element(Node* __node): - _entry(NULL), _node(NULL){ reset(__node); } + inline + SplayTree::Element::Element(Node* __node): + _entry(NULL), _node(NULL){ + reset(__node); + } template - inline SplayTree::Element::Element(Element const& __element2): - _entry(NULL), _node(NULL){ reset(__element2._node); } + inline + SplayTree::Element::Element(Element const& __element2): + _entry(NULL), _node(NULL){ + reset(__element2._node); + } template - inline SplayTree::Element::~Element(){ delete _entry; } - // + inline + SplayTree::Element::~Element(){ + delete _entry; + } template inline typename SplayTree::Element& SplayTree::Element::operator=(Element const& __e2){ reset(__e2._node); return *this; } - // + //////////////////// **# Element operations #** //////////////////// template inline typename SplayTree::Element::Entry* SplayTree::Element::operator->(){ return _entry; } @@ -264,181 +230,186 @@ namespace meow{ SplayTree::Element::operator!=(Element const& __e2) const{ return (_node != __e2._node); } - // + /////// **# Splay tree constructure/destructure/copy oper #** ////// template - inline SplayTree::SplayTree(): _root(NULL){ } + inline + SplayTree::SplayTree(): _root(NULL){ + } template - inline SplayTree::SplayTree(SplayTree const& __tree2): - _root(NULL){ setRoot(dup(__tree2._root)); } + inline + SplayTree::SplayTree(SplayTree const& __tree2): _root(NULL){ + _root = dup((Node*)(__tree2._root)); + } template - inline SplayTree::~SplayTree(){ clear(_root); } + inline + SplayTree::~SplayTree(){ + clear(_root); + } template inline SplayTree& SplayTree::operator=(SplayTree const& __tree2){ clear(_root); - setRoot(dup(__tree2._root)); + _root = dup((Node*)(__tree2._root)); return *this; } - // + template + inline void + SplayTree::moveTo(SplayTree* __tree2){ + __tree2->clear(); + __tree2->_root = _root; + _root = NULL; + } + //////////////////////// **# Bounding #** ////////////////////////// template inline typename SplayTree::Element SplayTree::lowerBound(Key const& __key) const{ - SplayTree* me = (SplayTree*)this; - setRoot(splay(findKey(me->_root, __key))); + splay(findKey(_root, __key)); if(_root == NULL || !(_root->_key < __key)) return Element(_root); - if(_root->_rChild == NULL) return Element(NULL); - setRoot(splay(findMinMax(me->_root->_rChild, true))); + if(_root->_child[1] == NULL) return Element(NULL); + splay(findMinMax(_root->_child[1], true)); return Element(_root); } template inline typename SplayTree::Element SplayTree::upperBound(Key const& __key) const{ - SplayTree* me = (SplayTree*)this; - setRoot(splay(findKey(me->_root, __key))); + splay(findKey(_root, __key)); if(_root == NULL || __key < _root->_key) return Element(_root); - if(_root->_rChild == NULL) return Element(NULL); - setRoot(splay(findMinMax(me->_root->_rChild, true))); + if(_root->_child[1] == NULL) return Element(NULL); + splay(findMinMax(_root->_child[1], true)); return Element(_root); } template inline typename SplayTree::Element SplayTree::rLowerBound(Key const& __key) const{ - SplayTree* me = (SplayTree*)this; - setRoot(splay(findKey(me->_root, __key))); + splay(findKey(_root, __key)); if(_root == NULL || !(__key < _root->_key)) return Element(_root); - if(_root->_lChild == NULL){ - return NULL; - } - setRoot(splay(findMinMax(me->_root->_lChild, false))); + if(_root->_child[0] == NULL) return Element(NULL); + splay(findMinMax(_root->_child[0], false)); return Element(_root); } template inline typename SplayTree::Element SplayTree::rUpperBound(Key const& __key) const{ - SplayTree* me = (SplayTree*)this; - setRoot(splay(findKey(me->_root, __key))); + splay(findKey(_root, __key)); if(_root == NULL || _root->_key < __key) return Element(_root); - if(_root->_lChild == NULL) return Element(NULL); - setRoot(splay(findMinMax(me->_root->_lChild, false))); + if(_root->_child[0] == NULL) return Element(NULL); + splay(findMinMax(_root->_child[0], false)); return Element(_root); } + ////////////// **# find / order / first / last / end #** //////////// template inline typename SplayTree::Element SplayTree::find(Key const& __key) const{ - SplayTree* me = (SplayTree*)this; - setRoot(splay(findKey(me->_root, __key))); - if(_root != NULL && _root->_key == __key) return Element(_root); + splay(findKey(_root, __key)); + if(_root != NULL && !(__key < _root->_key) && !(_root->_key < __key)){ + return Element(_root); + } return Element(NULL); } template inline typename SplayTree::Element SplayTree::order(size_t __order) const{ - SplayTree* me = (SplayTree*)this; - setRoot(splay(findOrder(me->_root, __order + 1))); + if(_root == NULL || __order >= _root->_size) return Element(NULL); + splay(findOrder(_root, __order + 1)); return Element(_root); } template inline typename SplayTree::Element SplayTree::first() const{ - SplayTree* me = (SplayTree*)this; - setRoot(splay(findMinMax(me->_root, true))); + splay(findMinMax(_root, true)); return Element(_root); } template inline typename SplayTree::Element SplayTree::last() const{ - SplayTree* me = (SplayTree*)this; - setRoot(splay(findMinMax(me->_root, false))); + splay(findMinMax(_root, false)); return Element(_root); } template inline typename SplayTree::Element SplayTree::end() const{ return Element(NULL); } + //////////////////// **# size, empty, clear #** //////////////////// template inline size_t SplayTree::size() const{ return (_root == NULL ? 0 : _root->_size); } template - inline bool SplayTree::empty() const{ return (size() == 0); } + inline bool SplayTree::empty() const{ + return (size() == 0); + } // template inline void SplayTree::clear(){ clear(_root); _root = NULL; } - template - inline void SplayTree::keyOffset(Key const& __delta){ - if(_root != NULL){ - offsetAdd(_root, __delta); - } - } + ////////////// **# insert, erase, keyOffset, oper[] #** //////////// template inline bool SplayTree::insert(Key const& __key, Value const& __value){ if(_root == NULL){ - setRoot(new Node(__key, __value)); - return true; - } - Node* parent = findKey(_root, __key); - Node* new_node; - if(parent->_key < __key){ - connectRChild(parent, new_node = new Node(__key, __value)); - sizeUpdate(parent); - }else if(__key < parent->_key){ - connectLChild(parent, new_node = new Node(__key, __value)); - sizeUpdate(parent); + _root = new Node(__key, __value); }else{ - setRoot(splay(parent)); - return false; + Node* parent = (Node*)findKey(_root, __key); + if(!(parent->_key < __key) && !(__key < parent->_key)){ + splay(parent); + return false; + } + Node* new_node = new Node(__key, __value); + connect(parent, (parent->_key < __key ? 1 : 0), new_node); + parent->syncUp(); + splay(new_node); } - setRoot(splay(new_node)); return true; } template inline bool SplayTree::erase(Key const& __key){ if(_root == NULL) return false; - Node* body = findKey(_root, __key); + Node* body = (Node*)findKey(_root, __key); if(body->_key < __key || __key < body->_key){ - setRoot(splay(body)); + splay(body); return false; } Node* ghost; - if(body->_rChild == NULL){ - ghost = body->_lChild; - if(ghost != NULL) offsetDown(ghost); + if(body->_child[1] == NULL){ + ghost = body->_child[0]; + if(ghost != NULL) ghost->syncDown(); }else{ - ghost = findMinMax(body->_rChild, true); - connectLChild(ghost, body->_lChild); - if(ghost != body->_rChild){ - connectLChild(ghost->_parent, ghost->_rChild); - connectRChild(ghost, body->_rChild); - for(Node* acestor = ghost->_parent; - acestor != ghost; - acestor = acestor->_parent){ - sizeUpdate(acestor); - } + ghost = (Node*)findMinMax(body->_child[1], true); + connect(ghost, 0, body->_child[0]); + if(ghost != body->_child[1]){ + connect(ghost->_parent, 0, ghost->_child[1]); + connect(ghost, 1, body->_child[1]); + for(Node* a = ghost->_parent; a != ghost; a = a->_parent) + a->syncUp(); } - sizeUpdate(ghost); - } - if(body->_parent != NULL && body->_parent->_lChild == body){ - connectLChild(body->_parent, ghost); - }else{ - connectRChild(body->_parent, ghost); + ghost->syncUp(); } - setRoot(splay(ghost != NULL ? ghost : body->_parent)); + Node* parent = body->_parent; + connect(parent, parent != NULL && parent->_child[0] == body ? 0 : 1, + ghost); + delete body; + splay(ghost != NULL ? ghost : parent); return true; } template + inline void SplayTree::keyOffset(Key const& __delta){ + if(_root != NULL){ + _root->keyOffset(__delta); + } + } + template inline Value& SplayTree::operator[](Key const& __key){ if(find(__key) == end()) insert(__key, Value()); - return find(__key)->second; + return _root->_value; } + /////////////////////// **# split, merge #** /////////////////////// template inline void SplayTree::splitOut(Key const& __upper_bound, SplayTree* __right){ __right->clear(); - if(rLowerBound(__upper_bound) != Element(NULL)){ + if(rLowerBound(__upper_bound) != end()){ split(_root, &_root, &(__right->_root)); }else{ __right->_root = _root; @@ -450,7 +421,7 @@ namespace meow{ SplayTree::mergeAfter(SplayTree* __tree2){ if(_root == NULL || __tree2->_root == NULL || last()->first < __tree2->first()->first){ - setRoot(merge(_root, __tree2->_root)); + _root = merge(_root, __tree2->_root); __tree2->_root = NULL; return true; } @@ -459,16 +430,13 @@ namespace meow{ template inline bool SplayTree::merge(SplayTree* __tree2){ - if(_root == NULL || __tree2->_root == NULL){ - setRoot(merge(_root, __tree2->_root)); + if(_root == NULL || __tree2->_root == NULL || + last()->first < __tree2->first()->first){ + _root = merge(_root, __tree2->_root); + }else if(__tree2->last()->first < first()->first){ + _root = merge(__tree2->_root, _root); }else{ - if(last()->first < __tree2->first()->first){ - setRoot(merge(_root, __tree2->_root)); - }else if(__tree2->last()->first < first()->first){ - setRoot(merge(__tree2->_root, _root)); - }else{ - return false; - } + return false; } __tree2->_root = NULL; return true; @@ -478,12 +446,5 @@ namespace meow{ SplayTree::print() const{ print(_root, 0); } - template - inline void - SplayTree::moveTo(SplayTree* __tree2){ - __tree2->clear(); - __tree2->_root = _root; - _root = NULL; - } } -- cgit v1.2.3