meow

Description

一個不需要, 也不建議先compile成obj files的templates.

Tip	README.html is more beautiful.

File Tree

meowpp/ C++ templates

utility.h some useful functions, stringPringf() , stringReplace , cstringEndWith , debugPrintf() , messagePrintf() , constant PI , noEPS() , normalize() , denormalize , ratioMapping , inRange() , squ() , average()
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
- DisjointSet.h class DisjointSet
- Heaps.h class MergeableHeap
- KD_Tree.h class KD_Tree
- SplayTree.h class SplayTree
oo/
- Register_Implement.h class RegisterInterface , class ImplementInterface

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	階層式的訊息輸出
noEPS	(double value, double eps = 1e-9)	double	如果abs(輸入的數值) < eps, 則回傳0, 否則回傳輸入的數值
normalize	(double lower, double upper, double value)	double	(value - lower) / (upper - lower)
denormalize	(double lower, double upper, double ratio)	double	lower + (upper - lower) * ratio
ratioMapping	(double l1, double u1, double m1, double l2, double u2)	double	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
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 來加權平均

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

階層式的訊息輸出

noEPS

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

double

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

normalize

(double lower, double upper,
double value)

double

(value - lower) / (upper - lower)

denormalize

(double lower, double upper,
double ratio)

double

lower + (upper - lower) * ratio

ratioMapping

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

double

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

inRange<T>

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

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

squ<T>

(T const& x)

x * x

average<T>

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

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

average<T>

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

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

Note	stringReplace() 不是用什麼好方法寫的因此執行效率很低請別虐待它. 額外附贈一個 const double PI = 3.141592653589......

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:: ImplementInterface/RegisterInterface (C++ Class)

Description

Assume there is a problem which can be solved by different algorithms. Then you can write multiple classes to approach this problem.
Now if you want to decide which algorithm to use in runtime, you can just approach this case by a simple way:

Let all the problem-solving classes inherit from class ImplementInterface<T> , and call the constructure with giving identify (type T ) .
Create an object, type RegisterInterface<T> , and register all your implement class to it by call regImplement(pointer to the class).
Select which implement class you want by call getImplement(identify) , which will return the pointer to the corresponding class.

meow:: DisjointSet (C++ class)

Description

DisjointSet is a lighting data structure that maintain N numbers from 0 to N-1 with methods below:

Const?	Name	Parameters	Return Type	Time Complexity	Description
const	root	(size_t number)	size_t	very fast	Return the group id of the number given
const	size	()	size_t	very fast	Return N
	reset	(size_t N)	void	very fast	Clean and initalize
	merge	(size_t number1, size_t number2)	size_t	very fast	Union the group contains number1 and the group contains number2. Return the merged group id

Const?

Name

Parameters

Return Type

Time Complexity

Description

const

root

(size_t number)

size_t

very fast

Return the group id of the number given

const

size

()

size_t

very fast

Return N

reset

(size_t N)

void

very fast

Clean and initalize

merge

(size_t number1,
size_t number2)

size_t

very fast

Union the group contains number1 and the group contains number2. Return the merged group id

Note	very fast means that you can consider it as constant time.

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

Description

MergeableHeap is a kind of maximum-heap with a special method merge, which will merge another MergeableHeap into itself in O(logN) time.

Template Request

Key should has operator<

Support methods

N ← number of elements in the heap
M ← number of elements in the other heap if need

Const?	Name	Parameters	Return Type	Time Complexity	Description
	operator=	(MergeableHeap const&)	*this	O(N)	Copy operator.
	moveTo	(MergeableHeap*)	void	O(M)	Transform the this→data to the heap specified in parameters
const	top	()	Element	O(1)	Return the maximum element in the heap.
const	size	()	size_t	O(1)	Return the number of elements in the heap.
const	empty	()	bool	O(1)	Return whether the heap is empty or not.
	push	(Element)	void	O(log N)	Add a element into the heap
	pop	()	void	O(log N)	Delete the maximum element from the heap
	merge	(MergeableHeap*)	void	O(log M)	Merge the specified MergeableHeap(with size=M) into itself
	clear	()	void	O(N)	Delete all elements from the heap

Const?

Name

Parameters

Return Type

Time Complexity

Description

operator=

(MergeableHeap const&)

*this

O(N)

Copy operator.

moveTo

(MergeableHeap*)

void

O(M)

Transform the this→data to the heap specified in parameters

const

top

()

Element

O(1)

Return the maximum element in the heap.

const

size

()

size_t

O(1)

Return the number of elements in the heap.

const

empty

()

bool

O(1)

Return whether the heap is empty or not.

push

(Element)

void

O(log N)

Add a element into the heap

pop

()

void

O(log N)

Delete the maximum element from the heap

merge

(MergeableHeap*)

void

O(log M)

Merge the specified MergeableHeap(with size=M) into itself

clear

()

void

O(N)

Delete all elements from the heap

Warning

Consider there are two MergeableHeap A and B.
B will become empty after you call A.merge(&B).
The data in B will override by data in A and A will become empty after you call A.moveTo(&B)

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

Description

KD_Tree is K-dimension tree, which is a dictionary(key→value). Where the type if key is a K-dimension vector .

Template Request

Keys should has operator[] to allow the KD_Tree access the k-dimensions
Key should has operator*, operator+

Support Methods

N ← numbers of element in the kd-tree
K ← dimensions
Keys is the tyepname of the vector
Key is the typename of the element in the vector
Value is the typename of value

Const?	Name	Parameters	Return Type	Time Complexity	Description
const	root	(size_t number)	size_t	very fast
	insert	(Key const& k, Value v)	void	O(1)	Insert a pair (k→v)
	build	()	void	O(KN logN)	Build the data structure(the insert() method will not build the data structure immediately)
const	query	(Keys const& point, int k)	Value	O(kN ^1-1/k )	Using Euclidean-Distance to find the k-nearest neighbor from point . And return the corrosponding value
const	query	(Keys const& point, int k)	std::vector<Value>	O(kN ^1-1/k )	Using Euclidean-Distance to find all the x-nearest neighbor from point , where x ⇐ k. And return an array of all the corrosponding value.
	clear	()	O(1)	Clear all data

Const?

Name

Parameters

Return Type

Time Complexity

Description

const

root

(size_t number)

size_t

very fast

insert

(Key const& k, Value v)

void

O(1)

Insert a pair (k→v)

build

()

void

O(KN logN)

Build the data structure(the insert() method will not build the data structure immediately)

const

query

(Keys const& point, int k)

Value

O(kN ^1-1/k )

Using Euclidean-Distance to find the k-nearest neighbor from point . And return the corrosponding value

const

query

(Keys const& point, int k)

std::vector<Value>

O(kN ^1-1/k )

Using Euclidean-Distance to find all the x-nearest neighbor from point , where x ⇐ k. And return an array of all the corrosponding value.

clear

()

O(1)

Clear all data

Note	O(kN ^1-1/k ) is reference from wiki. query() and rangeQuery() will run build() first if you called insert() before call them. And build() is very slow, so you should not use this class as a dynamic tree

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

Description

Like std::map, SplayTree is an dictionary(key→value). But it has some extra method, such as split(), merge(), keyOffset().

Data Type

Key is the tyepname of the key
Value is the typename of value
`SplayTree<Key, Value>:: Element ` is a typename which contain (key→value). It has some methods below:
- ->first ` a constant reference to `Key
- ->second a reference to Value
- operator==, operator!= compare function, check if the two Element is pointer to the same (key→value)

Template Request

Key should has operator<, operator+

Support Methods

N ← numbers of element in the SplayTree
M ← numbers of element in another SplayTree

Const?	Name	Parameters	Return Type	Time Complexity	Description
	operator=	(SplayTree const&)	*this	O(N)	copy operator
	moveTo	(SplayTree* t)	void	O(M)	Transform the data in this to t
const	lowerBound	(Key k)	Element	O(logN)	Find the smallest (key→value) which k <= key and return
const	upperBound	(Key k)	Element	O(logN)	Find the smallest (key→value) which k < key and return
const	rLowerBound	(Key k)	Element	O(logN)	Find the largest (key→value) which key <= k and return
const	rUpperBound	(Key k)	Element	O(logN)	Find the largest (key→value) which key < k and return
const	find	(Key k)	Element	O(logN)	Find the element (key→value) which key == k and return
const	order	(size_t k)	Element	O(logN)	Find the k-th small element. note that k start from zero like a normal C/C++ array.
const	first	()	Element	O(logN)	Return the smallest element
const	last	()	Element	O(logN)	Return the largest element
const	end	()	Element	O(1)	Return an empty element(it can be use to check if find() is successful)
const	size	()	size_t	O(1)	Return number of elements in the tree
const	empty	()	bool	O(1)	Return whether the tree is empty
	clear	()	void	O(N)	Clear
	keyOffset	(Key offset)	void	O(1)	Let all the keys in the tree plus offset
	insert	(Key k, Value v)	bool	O(logN)	Insert an element. If the tree already has an element with same key, return false.
	erase	(Key k)	bool	O(logN)	Erase an element from the tree with given key. Return false if the element not found.
	operator[]	(Key k)	Value	O(logN)	Like find() , but it will insert an element automatic if the corrosponding element not found
	splitOut	(Key const& upper_bound, SplayTree* out)	void	O(log N)	Split out all the elements with key larger than upper_bound and store then into out
	mergeAfter	(SplayTree* t)	bool	O(logN + logM)	If not all of the elements in this are smaller than elements in t, return false , else merge t into itself and return true.
	merge	(SplayTree* t)	bool	O(logN + logM)	If all of the elements in this are smaller than elements in t or all of the elements in this larger than elements in t , merge t into itself and return true. Else return false

Const?

Name

Parameters

Return Type

Time Complexity

Description

operator=

(SplayTree const&)

*this

O(N)

copy operator

moveTo

(SplayTree* t)

void

O(M)

Transform the data in this to t

const

lowerBound

(Key k)

Element

O(logN)

Find the smallest (key→value) which k <= key and return

const

upperBound

(Key k)

Element

O(logN)

Find the smallest (key→value) which k < key and return

const

rLowerBound

(Key k)

Element

O(logN)

Find the largest (key→value) which key <= k and return

const

rUpperBound

(Key k)

Element

O(logN)

Find the largest (key→value) which key < k and return

const

find

(Key k)

Element

O(logN)

Find the element (key→value) which key == k and return

const

order

(size_t k)

Element

O(logN)

Find the k-th small element. note that k start from zero like a normal C/C++ array.

const

first

()

Element

O(logN)

Return the smallest element

const

last

()

Element

O(logN)

Return the largest element

const

end

()

Element

O(1)

Return an empty element(it can be use to check if find() is successful)

const

size

()

size_t

O(1)

Return number of elements in the tree

const

empty

()

bool

O(1)

Return whether the tree is empty

clear

()

void

O(N)

Clear

keyOffset

(Key offset)

void

O(1)

Let all the keys in the tree plus offset

insert

(Key k, Value v)

bool

O(logN)

Insert an element. If the tree already has an element with same key, return false.

erase

(Key k)

bool

O(logN)

Erase an element from the tree with given key. Return false if the element not found.

operator[]

(Key k)

Value

O(logN)

Like find() , but it will insert an element automatic if the corrosponding element not found

splitOut

(Key const& upper_bound,
SplayTree* out)

void

O(log N)

Split out all the elements with key larger than upper_bound and store then into out

mergeAfter

(SplayTree* t)

bool

O(logN + logM)

If not all of the elements in this are smaller than elements in t, return false , else merge t into itself and return true.

merge

(SplayTree* t)

bool

O(logN + logM)

If all of the elements in this are smaller than elements in t or all of the elements in this larger than elements in t , merge t into itself and return true. Else return false

Warning

Consider there are two SplayTree A and B.
B will become empty after you call A.mergeAfter(&B) or A.merge(&B) successful.
The data in B will override by data in A and A will become empty after you call A.moveTo(&B)

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

Description

SegmentTree is a data structure that can maintain an array, and support range update , range query

Template Request

Value should has
- operator+(Value) offset
- operator|(Value) merge two nodes
- operator*(size_t) ??

For example, if you want to maintain range minimum

Value::operator+(Value v2) will be this->realValue + v2.realValue
Value::operator|(Value v2) will be std::min(this->realValue, v2.realValue)
Value::operator*(size_t n) will be this->realValue

If you want to maintain range sum

Value::operator+(Value v2) will be this->realValue + v2.realValue
Value::operator|(Value v2) will be this->realValue + v2.realValue)
Value::operator*(size_t n) will be this->realValue * n

Support methods

N ← array size

Const?	Name	Parameters	Return Type	Time Complexity	Description
	reset	(size_t N)	void	O(1)	Clear and reset the array size to N (from 0 to N - 1)
const	query	(ssize_t first, ssize_t last)	Value	O(logN)	Range query
	override	(ssize_t first, ssize_t last, Value const& __value)	void	O(logN)	Let the element in the array index from __first to __last be __value
	offset	(ssize_t first, ssize_t last, Value const& __value)	void	O(logN)	Let the element in the array index from __first to __last plus __value

Const?

Name

Parameters

Return Type

Time Complexity

Description

reset

(size_t N)

void

O(1)

Clear and reset the array size to N (from 0 to N - 1)

const

query

(ssize_t first, ssize_t last)

Value

O(logN)

Range query

override

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

void

O(logN)

Let the element in the array index from __first to __last be __value

offset

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

void

O(logN)

Let the element in the array index from __first to __last plus __value