Description

一個不需要, 也不應該先compile成obj files的templates.

Links

File Tree

meowpp/ C++ templates

  • utility.h some useful functions, stringPringf() , stringReplace() , cstringEndWith() , debugPrintf() , messagePrintf() , filenameCompare()

  • Usage.h class Usage

  • colors/ Color splces and transformer

    • RGB.h class RGBi , class RGBf

    • YUV.h class YUVi , class YUVf , RGB_to_YUV() , YUV_to_RGB()

    • HSL.h class HSLf , RGB_to_HSL() , HSL_to_RGB() , YUV_to_HSL() , HSL_to_YUV()

    • HSV.h class HSVf , RGB_to_HSV() , HSV_to_RGB() , YUV_to_HSV() , HSV_to_YUV() , HSL_to_HSV() , HSV_to_HSL()

  • dsa/ Data Structures and Algorithms

    • BinaryIndexTree.h class BinaryIndexTree<Vector, Scalar>

    • DisjointSet.h class DisjointSet

    • Heaps.h class MergeableHeap<Element>

    • KD_Tree.h class KD_Tree<Vector, Scalar>

    • SegemenTree.h class SegmentTree<Value>

    • SplayTree.h class SplayTree<Key, Value>

    • SplayTree_Range.h class SplayTree_Range<Key, Value>

    • VP_Tree.h class VP_Tree<Vector, Scalar>

  • geo/

    • Vector2D.h Vector2D<Scalar>

    • Vector3D.h Vector3D<Scalar>

  • math/

    • utility.h some useful functions, constant PI , noEPS() , normalize() , denormalize() , ratioMapping() , inRange() , squ() , average()

    • LinearTransformation.h LinearTransformation<Scalar>

    • LinearTransformations.h Rotation3D<Scalar>

    • Matrix.h Matrix<Entry>

    • Transformation.h Transformation<Scalar>

    • Transformations.h BallProjection<Scalar>, PhotoProjection<Scalar>

  • oo/

    • ObjBase.h class ObjBase

    • ObjSelector.h class ObjBase<size_t id>

    • Properties.h class Properties

Structures/Classes/Functions

meow:: Functios in utility.h

Name Parameters Return_Type Description

stringPrintf

(char const * fmt, …)

std::string

Format print to C++ string and return it

stringReplace

(std::string str,
std::string const& from,
std::string const& to)

std::string

Return a string like str, but all from be replaced by to

cstringEndWith

(char const* str,
int n, …)

bool

Return whether str is end with one of the c-string you specify in the parameters or not

debugPrintf

(char const* fmt, …)

void

Print debug message (file name, line number, …etc) when DEBUG is defined

messagePrintf

(int level_change,
char const* fmt, …)

void

階層式的訊息輸出

filenameCompare

(std::string const& f1, std::string const& f2)

void

依照 a0.txt < a1.txt < a2.txt < a10.txt 的字串比較方法比較字串
Note

  • stringReplace() 不是用什麼好方法寫的因此執行效率很低請別虐待它.

meow:: Usage (C++ Class)

Description

Usage 是用來分析argc, argv和輸出usage document的class. argc, argv的部份, 有以下規則

  • -c 其中 c 可以代換成正常的一個字元的字符, 這種選像要嘛就是 有設置 , 不然就是 沒設置

  • -c <value> 附加一個value, 這種選項可以是選擇性 ,即要設定與否都可以, 反之則一定要設定. 另外可以給定value的預設值以及哪些value是可接受的

  • <value> 其他, 一律視為process arguments

Methods

  • Usage(String const& _name)
    建構子, 所有說明文字中 <name> 都會被代換成 _name

  • Usage()
    建構子, _name 自動取為 " nobody "

  • import(Usage const& usage)
    將另一個usage的設定匯入, 回傳成功與否 (bool)

  • update(Usage const& usage)
    將另一個usage分析argc,argv出來的資料拿來用, 回傳成功與否 (bool)

  • addOption(unsigned char option, String const& description)
    新增一個不接額外選項的參數, 並附上說明文字, 回傳成功與否 (bool)

  • addOption(unsigned char option, String const& description, String const& value_type, String const& value_default, bool must)
    新增一個有額外選項的參數, 並附上說明文字, 額外選項的型別跟預設值. 說明文字中所有的" <types> "將會被取代指定的型別, 其中 must 代表 " 是否一定要設定此參數 " , 回傳表成功與否 (bool)

  • addOptionValueAccept(unsigned char option, String const& value, String const& description)
    針對某個option, 新增一個可接受的額外選項 (如果某個option從頭到尾都 沒有新增可接受的選項, 則視為不限制), 回傳成功與否 (bool)

  • hasOptionSetup(unsigned char option)
    回傳是否有此選項 (bool)

  • getOptionValuesCount(unsigned char option)
    回傳此參數被設置了幾次 (size_t) , 只對有接額外參數的有效

  • getOptionValue(unsigned char option, size_t index)
    回傳第`index`個額外選項 (String)

  • getProcArgsCount()
    回傳有多少個Process Arguments (size_t)

  • getProcArg(size_t index)
    取得第`index`個Process Argument (String)

  • getProcArgs()
    回傳一個陣列, 包含所有Process Arguments (Strings)

  • addUsageBegin(String const& des)
    新增一段usage document於每個選項逐條說明之前

  • addUsageEnd (String const& des)
    新增一段usage document於每個選項逐條說明之後

  • String getUsage()
    回傳usage document (String)

  • setArguments(int argc, char** argv, String* errmsg)
    輸入argv, argc, 回傳是否沒有錯誤發生 (bool) , 其中如果有錯誤發生, 且 errmsg != NULL 則會將錯誤訊息寫入之

Note

  • String 是 std::string .

  • Strings 是 std::vector< std::string> >.

  • 如果沒有寫回傳什麼, 就是回傳 void

meow:: DisjointSet (C++ class)

Description

DisjointSet 是個輕量級Data Dtructure, 用來維護一堆互斥集的資訊. 相關資料可參考 演算法筆記

Support Methods

Const? Name Parameters Return_Type Time_Complexity Description

const

root

(size_t number)

size_t

very fast

回傳 number 所在的 集合的編號 (0~N-1)

const

size

()

size_t

very fast

回傳 總集合大小

reset

(size_t N)

void

O(N)

清空, 並且設定總集合大小為 N

merge

(size_t number1,
size_t number2)

size_t

very fast

將 number1 所在的集合 跟 number2 所在的集合 合併, 並回傳合併後新的集合的編號
Note

  • very fast 表示它算的真的超級快, 可以視為常數時間.

  • 預設值所有 number 所在的集合的編號就是 number 本身, 即沒有任兩個數在同一個set裡面

meow:: MergeableHeap<Element> (C++ class)

Description

一個用 左偏樹 實作的 Maximum-Heap , 除了原本heap有的功能外, 還支援 merge, split 等功能

Template Class Operators Request

Const? Typename Operator Parameters Return_Type Description

const

Element

operator<

(Element v)

bool

大小比較

Support Methods

  • N ← this 中擁有的資料數

Const? Name Parameters Return_Type Time_Complexity Description

moveTo

(MergeableHeap* h)

void

O(M)

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

const

top

()

Element const&

O(1)

回傳最大的那個 Element

const

size

()

size_t

O(1)

回傳 this 中擁有的資料數

const

empty

()

bool

O(1)

回傳 this 是否為空

push

(Element const& e)

void

O(logN)

將 e 加入

pop

()

void

O(logN)

將最大的 Element 移除

clear

()

void

O(N)

將資料清空

merge

(MergeableHeap* heap2)

void

O(logN+logM)

將 heap2 的資料統統加到 this 中, 並且清空 heap2 時間複雜度中的M是 heap2 的資料數
Warning

  • 假設現在有兩個MergeableHeap A 和 B, 則:

    • 執行 A.merge(&B) 後 B 會變成空的

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

meow:: VP_Tree<Vector, Scalar> (C++ class)

Description

VP_Tree 用來維護由 N個K維度向量所成的集合, 並可於該set中查找 前i個離給定向量最接近的向量.
不像 KD_Tree 二分樹每次都選擇一個維度去分, 分成小的跟大的, VP_Tree 每次選一個點, 將資料分成 離這個點近的, 跟離這個點遠的. 至於怎麼選呢…., 嘛還沒研究, 先random

參考資料連結:

Template Class Operators Request

Const? Typename Operator Parameters Return_Type Description

const

Vector

operator[]

(size_t n)

Scalar

取得第 n 維度量

const

Vector

operator=

(Vector v)

Vector&

copy operator

const

Vector

operator<

(Vector v)

bool

權重比較

const

Scalar

Scalar

(int n)

Scalar

建構子, 其中一定n=0 or 4

const

Scalar

operator*

(Scalar s)

Scalar

相乘

const

Scalar

operator+

(Scalar s)

Scalar

相加

const

Scalar

operator-

(Scalar s)

Scalar

相差

const

Scalar

operator-

( )

Scalar

取負號

const

Scalar

operator<

(Scalar s)

bool

大小比較

Custom Type Definitions

  • Vectors ← std::vector<Vector>

Support Methods

  • N ← this 中擁有的資料數

  • D ← this 資料維度

Const? Name Parameters Return_Type Time_Complexity Description

insert

(Vector const& v)

void

O(1)

將向量 v 加到set中

erase

(Vector const& v)

bool

O(N)

將向量 v 從set中移除, TODO:可以再優化

build

()

void

O(KN logN) or O(1)

檢查距上一次 build() 至今是否有 insert/erase 被呼叫, 若有, 重新建樹, 否則不做事

forceBuild

()

void

O(KN logN)

重新建樹

const

query

(Vector const& v,
size_t i,
bool cmp)

Vectors

O(logN) Expected

於set中找尋距離 v 前 i 近的向量, 並依照由近而遠的順序排序. 如果有兩個向量 v1,v2 距離一樣, 且 cmp 為 true , 則直接依照 v1 < v2 來決定誰在前面. 最後回傳一陣列包含所有解.

clear

()

void

O(1)

清空所有資料

reset

(size_t dimension)

size_t

O(1)

清空所有資料並且指定維度為 max(1, dimension) 並且回傳指定後的維度
Note

  • 實測結果發覺, 維度小的時候, 比起中規中矩的 KD_Tree, VP_Tree 有 randomp 於其中, 因此時間複雜度只是期望值 O(logN) 但是測資大到 一定程度, KD_Tree 效率會一整個大幅掉下, 但 VP_Tree 幾乎不受影響

  • TODO insert(), erase() 算是未完成功能

meow:: KD_Tree<Vector, Scalar> (C++ class)

Description

KD_Tree 全名k-dimension tree, 用來維護由 N個K維度向量所成的集合, 並可於該set中查找 前i個離給定向量最接近的向量

Template Class Operators Request

Const? Typename Operator Parameters Return_Type Description

const

Vector

operator[]

(size_t n)

Scalar

取得第 n 維度量

const

Vector

operator<

(Vector v)

bool

權重比較

const

Scalar

operator*

(Scalar s)

Scalar

相乘

const

Scalar

operator+

(Scalar s)

Scalar

相加

const

Scalar

operator-

(Scalar s)

Scalar

相差

const

Scalar

operator<

(Scalar s)

bool

大小比較

Custom Type Definitions

  • Vectors ← std::vector<Vector>

Support Methods

  • N ← this 中擁有的資料數

  • K ← this 資料維度

Const? Name Parameters Return_Type Time_Complexity Description

insert

(Vector const& v)

void

O(1)

將向量 v 加到set中

erase

(Vector const& v)

bool

O(N)

將向量 v 從set中移除, TODO:可以再優化

build

()

void

O(KN logN) or O(1)

檢查距上一次 build() 至今是否有 insert/erase 被呼叫, 若有, 重新建樹, 否則不做事

forceBuild

()

void

O(KN logN)

重新建樹

const

query

(Vector const& v,
size_t i,
bool cmp)

Vectors

O(KN 1-1/K )

於set中找尋距離 v 前 i 近的向量, 並依照由近而遠的順序排序. 如果有兩個向量 v1,v2 距離一樣, 且 cmp 為 true , 則直接依照 v1 < v2 來決定誰在前面. 最後回傳一陣列包含所有解.

clear

()

void

O(1)

清空所有資料

reset

(size_t dimension)

void

O(1)

清空所有資料並且指定維度為 dimension
Note

  • 此資料結構只有在 N >> 2 K 時才比較有優勢, 當 K 逐漸變大時, 所花時間會跟暴搜沒兩樣

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

Description

SplayTree 是一種神乎其技的資料結構, 維護一堆 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中的資料

Support Methods

  • N ← this 中擁有的資料數

  • M ← tree2 中擁有的資料數

Const? Name Parameters Return_Type Time_Complexity Description

moveTo

(SplayTree* 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

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為空, 則回傳 this->end()

const

last

(size_t ord)

Element

O(logN)

回傳Key最大的Element, 如果SplayTree為空, 則回傳 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

operator[]

(Key const& key)

Value&

O(logN)

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

splitOut

(Key const& upper_bound,
SplayTree* tree2)

void

O(logN) + O(M)

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

mergeAfter

(SplayTree* tree2)

void

O(logN) + O(logM)

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

merge

(SplayTree* tree2)

void

O(logN) + O(logM)

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

  • 假設現在有兩個SplayTree A 和 B, 則:

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

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

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

Description

維護一個陣列, 並且讓user可以有區間查詢, 區間修改的小東東

Template Class Operators Request

Const? Typename Operator Parameters Return_Type Description

const

Value

operator+

(Value v)

Value

相加(位移)

const

Value

operator*

(size_t n)

Value

每個Value都一樣, 長為 n 的區間的值

const

Value

operator|

(Value v)

Value

區間合併後的值

  • 若要維護區間最小值, 即每次都是詢問範圍 [a, b] 的最小值, 則可以定義

    • operator+ 為 回傳相加值

    • operator* 為 回傳*this

    • operator| 為 回傳std::min(*this, v)

  • 若要維護區間最總和, 即每次都是詢問範圍 [a, b] 的總和, 則可以定義

    • operator+ 為 回傳相加值

    • operator* 為 回傳(*this) * n

    • operator| 為 回傳相加值

Support Methods

  • N ← this 所維護的陣列長度

Const? Name Parameters Return_Type Time_Complexity Description

reset

(size_t size)

void

O(1)

將資料清空且設定維護範圍是 0~size - 1 其中時間複雜度確切多少未知 要看 std::vector::resize() 的效率

const

query

(ssize_t first,
ssize_t last)

Value

O(logN)

回傳區間 [first,last] (邊界都含) 的區間值

override

(ssize_t first,
ssize_t last,
Value const& value)

void

O(logN)

將區間 [first,last] 全部都設定成 value

offset

(ssize_t first,
ssize_t last,
Value const& delta)

void

O(logN)

將區間 [first,last] 全部都加上 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(...)

meow:: Functios in math/utility.h

Name Parameters Return_Type Description

noEPS<T>

(T value, T eps = 1e-9)

T

如果abs(輸入的數值) < eps, 則回傳0, 否則回傳輸入的數值

normalize<T>

(T lower, T upper,
T value)

T

(value - lower) / (upper - lower)

denormalize<T>

(T lower, T upper,
T ratio)

T

lower + (upper - lower) * ratio

ratioMapping<T>

(T l1, T u1,
T m1, T l2,
T u2)

T

denormalize(l2, u2, normalize(l1, u1, m1))

inRange<T>

(T const& mn, T const& mx,
T const& v)

T

std::max(mn, std::min(mx, v))

squ<T>

(T const& x)

T

x * x

cub<T>

(T const& x)

T

x * x * x

average<T>

(T const& beg, T const& end,
double sigs)

T

只將 sigs 個標準差以內的數據拿來取平均

average<T>

(T const& beg, T const& end,
T const& p, double sigs)

T

同上, 不過這次用 p 來加權平均
Note

  • 額外附贈一個 const double PI = 3.141592653589......

Test

ACM 相關題目

Name Problem Link Status Time source

KD_Tree

Retrenchment

NTU-OJ ACM-ICPC Live

Accept

0.083/0.083

codepad

VP_Tree

Retrenchment

NTU-OJ ACM-ICPC Live

Accept

0.516/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

Bug Report / Contact

  • E-Mail: cat.hook31894 ~在~ gmail.com