From d5052f1c296dddf51b3e83d59bf3e3c1952cb2d0 Mon Sep 17 00:00:00 2001 From: cathook Date: Sun, 1 Jun 2014 13:56:57 +0800 Subject: big chnage --- README.html | 2637 ++++++++++++++++------------------------------------------- 1 file changed, 719 insertions(+), 1918 deletions(-) (limited to 'README.html') diff --git a/README.html b/README.html index 26b5af2..cef1c4f 100644 --- a/README.html +++ b/README.html @@ -61,6 +61,13 @@ h1, h2, h3, h4, h5, h6 { letter-spacing:+0.15em; } +h1 { font-size: 7ex; } +h2 { font-size: 5ex; } +h3 { font-size: 4ex; } +h4 { font-size: 3ex; } +h5 { font-size: 2ex; } +h6 { font-size: 2ex; } + h1, h2, h3 { border-bottom: 2px solid #ccd; } h2 { padding-top: 0.5em; } h3 { float: left; } @@ -83,6 +90,11 @@ ul, ol, li > p { margin-top: 0; } +ul { + margin-left: 1em; + padding-left: 1em; +} + pre { padding: 0; margin: 0; @@ -139,6 +151,7 @@ div.title, caption.title { text-align: left; margin-top: 1.0em; margin-bottom: 0.5em; + margin-left: 1em; } div.title + * { margin-top: 0; @@ -164,6 +177,7 @@ div.listingblock > div.content { border: 1px solid silver; background: #f4f4f4; padding: 0.5em; + margin-left: 2em; } div.quoteblock { @@ -325,9 +339,9 @@ div.hdlist.compact tr { div.toclevel1, div.toclevel2, div.toclevel3, div.toclevel4 { margin-top: 0; margin-bottom: 0; } div.toclevel1 { margin-top: 0.3em; margin-left: 0; font-size: 1.0em; } -div.toclevel2 { margin-top: 0.25em; margin-left: 2em; font-size: 0.9em; } -div.toclevel3 { margin-left: 4em; font-size: 0.8em; } -div.toclevel4 { margin-left: 6em; font-size: 0.8em; } +div.toclevel2 { margin-top: 0.25em; margin-left: 1em; font-size: 0.9em; } +div.toclevel3 { margin-left: 2em; font-size: 0.8em; } +div.toclevel4 { margin-left: 3em; font-size: 0.8em; } body { margin: 1em 5%; @@ -350,6 +364,7 @@ body { .paragraph p { line-height: 1.5em; margin-top: 1em; + margin-left: 2em; } .paragraph p, li, dd, .content { max-width: 100%; } @@ -359,10 +374,11 @@ div.sectionbody div.ulist > ul > li { list-style-type: square; color: #aaa; } - div.sectionbody div.ulist > ul > li > * { - color: black; - /*font-size: 50%;*/ - } + +div.sectionbody div.ulist > ul > li > * { + color: black; + /*font-size: 50%;*/ +} div.sectionbody div.ulist > ul > li div.ulist > ul > li { @@ -388,6 +404,7 @@ em { table.tableblock { margin-top: 1.0em; margin-bottom: 1.5em; + margin-left: 2em; } thead, p.tableblock.header { font-weight: bold; @@ -669,7 +686,7 @@ install: function(toclevels) { } } -asciidoc.install(2); +asciidoc.install(4); /*]]>*/ @@ -709,2282 +726,1061 @@ asciidoc.install(2);

File Tree

-

meowpp/ C++ templates

+

LaTex/

+

LaTex 相關模板

+
+
Makefile
+

環境變數:

  • -utility.h some useful functions, - stringPringf() , stringReplace() , cstringEndWith() , - debugPrintf() , messagePrintf() , filenameCompare() +SOURCE = source.tex 設定 LaTex 源碼檔名

  • -Usage.h class Usage +TARGET = output 設定生出來的 pdf 檔名

    • -
  • -

    -colors/ Color splces and transformer -

    +
+
+ + + +
+
Note
+		TARGET 不需要給副檔名
+
+

targets:

  • -RGB.h class RGBi , class RGBf +all 生成 <TARGET>.pdf

  • -YUV.h class YUVi , class YUVf , RGB_to_YUV() , YUV_to_RGB() +view 用kde-open 把輸出結果開起來(如有需要會先重新編譯)

  • -HSL.h class HSLf , RGB_to_HSL() , HSL_to_RGB() , - YUV_to_HSL() , HSL_to_YUV() +clean 清除

  • -HSV.h class HSVf , RGB_to_HSV() , HSV_to_RGB() , - YUV_to_HSV() , HSV_to_YUV() , - HSL_to_HSV() , HSV_to_HSL() +two 編譯兩次, 如果有目錄的話可能會需要用到

- -
  • -

    -dsa/ Data Structures and Algorithms -

    +
    • +
    +
    source.tex
    +

    內容為一些我自己定義的設定, 參數設置等等. 另外還有用寫在註解裡面的小筆記

    +
    +
    +
    +

    asciidoc/

    +

    一些關於asciidoc的example與編譯設定

    +
    +
    Makefile
    +

    編譯asciidoc用的, 裡面有兩個環境變數:

    • -BinaryIndexTree.h class BinaryIndexTree<Vector, Scalar> +ASCIIDOC_SOURCE: 指定原始碼, 預設為 example.txt

    • -DisjointSet.h class DisjointSet +ASCIIDOC_OUTPUT: 輸出的檔名, 預設為 output.html

      • +
    +

    另外還有一個target:

    +
    +
    +
    $(ASCIIDOC_OUTPUT): $(ASCIIDOC_SOURCE)
    +
    +
    +
    +

    cppMakefile/

    +
    Description

    這是一個簡單的 GNU makefile for C++ project +類似AutoTool等工具, 不過又更簡化了, 操作方法是利用GNUMakefile裡的targets +當作指令, 生出一個targets檔, 以後鍵入 make all 就會自動把所有targets都 +編譯出來.

    +
    Commands

    • -Heaps.h class MergeableHeap<Element> +make init
      +初始化, 設定完之後所在位置會多幾個資料夾如下

      -
      • +

      • -KD_Tree.h class KD_Tree<Vector, Scalar> +bin/ 放編譯出來的執行檔

      • -SegemenTree.h class SegmentTree<Value> +dep/ dependency相關資料, 內容會自動生成, 不用理它

      • -SplayTree.h class SplayTree<Key, Value> +inc/ 自定義的include file放置位置

      • -SplayTree_Range.h class SplayTree_Range<Key, Value> +src/ source code放置位置

      • -VP_Tree.h class VP_Tree<Vector, Scalar> +obj/ obj file放置位置, 會自動生成, 不用理它

    • -geo/ +make new NAME=<name> [OBJS=<OBJ_FILES> LIBS=<LIBRARIES>]
      +新增一個target, 須給定目標名 , 並且此Makefile會假定 main() { ... } 放在 +src/<name>.cpp 而最終輸出會是 bin/<name> .
      +關於 OBJS= 與 LIBS= 參考下面說明 +

      +
      • +
    • +

      +make add NAME=<name> [OBJS=<OBJ_FILES> LIBS=<LIBRARIES>]
      +針對target為 <name> 的目標新增需要的 <OBJ_FILES> , 與 <LIBRARIES>. +<LIBRARIES> 的部份會用 pkg-config 去解讀, 例如 <LIBRARIES> 為 +opencv lapackpp 則link時會被以下指令展開
      +pkg-config --libs opencv lapackpp
      +而 <OBJ_FILES> 的部份則只需要給 name 就好, 不需要有完整個 pathname, 例如 +例如 <OBJ_FILES> 是 a b c 則此makefile會視為

      • -Vector2D.h Vector2D<Scalar> +source code: src/a.cpp src/b.cpp src/c.cpp

      • -Vector3D.h Vector3D<Scalar> +obj file: obj/a.o obj/b.o obj/c.o

    • -math/ +make del NAME=<name> [OBJS=<OBJ_FILES> LIBS=<LIBRARIES>]
      +與 add相反, 嘗試將指定target所需的<OBJ_FILES>'和<LIBRARIES>'移除

      -
        +

      • -utility.h some useful functions, - constant PI , - noEPS() , normalize() , denormalize() , - ratioMapping() , inRange() , squ() , average() +make clean
        +將 bin/ dep/ obj/* 清除, 有時候覺得dependency怪怪的 +時可以嘗試執行此指令

        • +
      +
      + + + +
      +
      Note
      +      		其中整個project到底有哪些obj file會完全依照 src/ 裡面有哪些 .cpp 檔決定
      +
      +
      +
      GNUMakefile
      +

      就是一個 Makefile, 不過裡面有些東西是 GNU-make only的

      +
      +
      +
      GNUMakefile.dependency.bash
      +

      產生 dependency檔用的

      +
      +
    +
    +

    doxygen/

    +

    doxygen 相關設定

    +
    +
    Makefile
    +

    編譯doxygen document的Makefile, 裡面只有一個target: document, +另外有兩個環境變數:

    +

    • -LinearTransformation.h LinearTransformation<Scalar> +DOXYGEN_RUN_PATH: 指定doxygen執行的pwd, 預設為 pwd

    • -LinearTransformations.h Rotation3D<Scalar> +DOXYGEN_CONFIG: 指定config檔放在哪裡, 預設為 pwd

      • +
    +
    +
    +
    config
    +

    設置, 以下幾點個人覺得比較重要的

    +
    +
    +
    
+#---------------------------------------------------------------------------
+# Project related configuration options
+#---------------------------------------------------------------------------
+DOXYFILE_ENCODING      = UTF-8
+PROJECT_NAME           = "Templates -- Meow"
+PROJECT_NUMBER         = 1.1.2
+PROJECT_BRIEF          = 不能, 也不應該先編譯成obj-file的templates
+PROJECT_LOGO           = $(config_path)/logo.png
+OUTPUT_DIRECTORY       = doc
+CREATE_SUBDIRS         = NO
+OUTPUT_LANGUAGE        = English
+TAB_SIZE               = 2
+
+#---------------------------------------------------------------------------
+# Build related configuration options
+#---------------------------------------------------------------------------
+EXTRACT_ALL            = YES
+EXTRACT_STATIC         = YES
+EXTRACT_LOCAL_CLASSES  = NO
+EXTRACT_LOCAL_CLASSES  = YES
+FORCE_LOCAL_INCLUDES   = YES
+
+#---------------------------------------------------------------------------
+# configuration options related to the input files
+#---------------------------------------------------------------------------
+INPUT                  = meowpp
+INPUT_ENCODING         = UTF-8
+FILE_PATTERNS          =
+RECURSIVE              = YES
+
+#---------------------------------------------------------------------------
+# configuration options related to the HTML output
+#---------------------------------------------------------------------------
+GENERATE_HTML          = YES
+HTML_OUTPUT            = html
+HTML_FILE_EXTENSION    = .html
+HTML_HEADER            = $(config_path)/header.html
+HTML_FOOTER            = $(config_path)/footer.html
+HTML_STYLESHEET        = $(config_path)/stylesheet.css
+HTML_EXTRA_STYLESHEET  = $(config_path)/custom.css
+HTML_EXTRA_FILES       =
+HTML_COLORSTYLE_HUE    = 120
+HTML_COLORSTYLE_SAT    = 36
+HTML_COLORSTYLE_GAMMA  = 166
+DISABLE_INDEX          = YES
+GENERATE_TREEVIEW      = YES
+FORMULA_FONTSIZE       = 11
+SEARCHENGINE           = NO
+
+#---------------------------------------------------------------------------
+# configuration options related to the LaTeX output
+#---------------------------------------------------------------------------
+GENERATE_LATEX         = YES
+LATEX_CMD_NAME         = xelatex
+PAPER_TYPE             = letter
+HIDE_UNDOC_RELATIONS   = NO
+UML_LOOK               = YES
+EXTRA_PACKAGES         =
+LATEX_HEADER           = $(config_path)/header.tex
+LATEX_FOOTER           = $(config_path)/footer.tex
+
+#---------------------------------------------------------------------------
+# Configuration options related to the dot tool
+#---------------------------------------------------------------------------
+CALL_GRAPH             = YES
+CALLER_GRAPH           = YES
    +
    + + + +
    +
    Note
    +    		config 中 $(config_path) 是一個環境變數, 代表這個configure file所在位置 +呼叫asciidoc時必須有設置這個環境變數
    +
    +
    +
    +
    header.html
    +

    HTML output 的開頭 +沒有更動

    +
    +
    +
    footer.html
    +

    HTML output 的結尾 +沒有更動

    +
    +
    +
    logo.png
    +

    就是logo

    +
    +
    +
    stylesheet.css
    +

    HTML output 的css樣式, 我把他改成暗色系了

    +

    以下是更動的地方:

    +
    +
    +
    body, table, div, p, dl {
+        font: 400 14px/19px Roboto,sans-serif,monospace;
+}
+
+.title {
+        line-height: 100%;
+        font-size: 200%;
+        margin :  0px;
+        padding: 0px;
+        border : 0px;
+}
+
+dt {
+        color: #999999;
+        font-style:italic;
+}
+
+div.qindex, div.navtab{
+        background-color: #2B3F26;
+}
+
+a {
+        color: #5D77AC;
+}
+
+.contents a:visited {
+        color: #7695D2;
+}
+
+a.code, a.code:visited {
+        color: #7695D2;
+}
+
+a.codeRef, a.codeRef:visited {
+        color: #7695D2;
+}
+
+pre.fragment {
+        background-color: #0B0C0D;
+        border-radius: 4px;
+        -moz-border-radius: 4px;
+        -webkit-border-top-left-radius: 4px;
+}
+
+div.fragment {
+        background-color: #0B0C0D;
+        border-radius: 4px;
+        -moz-border-radius: 4px;
+        -webkit-border-top-left-radius: 4px;
+}
+
+div.line {
+        font-family: 'courier new', monospace, fixed;
+        color: #CCCCCC;
+        font-size: 14px;
+        min-height: 14px;
+}
+
+span.lineno {
+        background-color: #181818;
+}
+span.lineno a {
+        background-color: #3B3838;
+}
+
+span.lineno a:hover {
+        background-color: #6B6868;
+}
+
+body {
+        background-color: #212131;
+        color: #DDFFDD;
+}
+
+span.keyword {
+        color: #00A000
+}
+
+span.keywordtype {
+        color: #907050
+}
+
+span.comment {
+        color: #808080
+}
+
+table.memberdecls {
+        border-top-color: #111111;
+}
+
+.memTemplItemLeft, .memTemplItemRight, .memTemplParams {
+        background-color: #192322;
+}
+
+.mdescLeft, .mdescRight {
+        color: #CCCCCC;
+}
+
+.memTemplParams {
+        color: #7695D2;
+}
+
+.memtemplate {
+        color: #7695D2;
+}
+
+.memproto, dl.reflist dt {
+        color: #758575;
+        text-shadow: 0px 1px 1px rgba(0, 0, 0, 0.95);
+        /* background-image:url('nav_f.png'); */
+        background-color: #181C28;
+}
+
+.memdoc, dl.reflist dd {
+        /* background-image:url('nav_g.png'); */
+        background-color: #131923;
+}
+
+.params .paramdir {
+        color:#A0AA00;
+}
+
+.directory tr.even {
+        background-color: #272838;
+}
+
+.directory .levels span {
+        color: #5D77AC;
+}
+
+div.header
+{
+        /* background-image:url('nav_h.png'); */
+        /* background-repeat:repeat-x; */
+        background-color: #290A1C;
+        padding: 0px;
+        margin : 0px;
+        border : 0px;
+        margin-top: 10px;
+        border-bottom: 1px solid #AA0000;/*#C4CFE5;*/
+}
+
+div.headertitle
+{
+        padding: 5px;
+        margin : 0px;
+        border : 0px;
+}
+
+#projectname
+{
+        font: 400% Tahoma, Arial,sans-serif,monospace;
+}
+
+div.toc h3 {
+        color: #7695D2;
+}
+
    +
    +
    +
    custom.css
    +

    HTML output 的css樣式, 在這邊設定的話連 navtree 等都可以設定.
    +另外這個檔案的檔名不能是 navtree.css , 不知道是不是bug.

    +
    +
    +
    header.tex
    +

    LaTex output 的開頭

    +
    +
    +
    header.tex
    +

    LaTex output 的結尾

    +
    +
    +
    stylesheet.sty
    +

    LaTex 的樣式設定

    +
    +
    +
    +

    meowpp/

    +

    meow for C++ templates

    +
    +
    Self.h
    +

    包含一個具有 Copy On Write 技術的 class 而且有實作 by reference , +基本上就是改良C\+\+原本的 reference 機制, 原本的 reference 只能在宣告的時候 +指定參照指向的變數, +而這邊則可以動態改變

    +
    +
    +
    Usage.h
    +

    方便user製作還算精美的 usage document 並且利用 getopt() 實作讀入參數與分析

    +
    +
    +
    utility.h
    +

    一些不知道要歸類到哪的小functions

    +
    +
    +

    colors/

    +

    一些 color space 以及這些space的 transformate function 都放在這資料夾下

    +
    + + + +
    +
    Note
    +    		目前transformation function的準確率還很低, 有待以後加強
    +
    +
    +
    Color3_Space.h
    +

    class Color3_Space<T> Channel Number = 3 的 Color Space 的共通 Base class

    +
    +
    +
    RGB_Space.h
    +

    Channel分別是

    +

    • -Matrix.h Matrix<Entry> +Red

    • -Transformation.h Transformation<Scalar> +Green

    • -Transformations.h BallProjection<Scalar>, PhotoProjection<Scalar> +Blue

    - +
    Classes

    • -oo/ +meow::RGBi_Space 用 int 存資料, 每個channel數值合法範圍是 0~255

      -
        +

      • -ObjBase.h class ObjBase +meow::RGBf_Space 用 double 存資料, 每個channel數值合法範圍是 0.0~1.0

        • +
      +
      Functions

      • -ObjSelector.h class ObjBase<size_t id> +meow::colorTransformation(in, *out) for

        -
        • +

        • -Properties.h class Properties +RGBi_Space ←→ RGBf_Space

    -
    -
    -
    -

    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
    -    		 +
    +
    YUV_Space.h
    +

    Channel分別是

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

      • -
    -
    -
    -
    -
    -
    -

    meow:: Usage (C++ Class)

    -
    -

    Description

    -

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

    -

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

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

      • +
    +
    Classes

    • -<value> 其他, 一律視為process arguments +meow::YUVf_Space 用 double 存資料, 每個channel數值合法範圍是 0~1.0

    -
    -
    -

    Methods

    -
      +
      Functions

      • -Usage(String const& _name)
        -建構子, 所有說明文字中 <name> 都會被代換成 _name +meow::colorTransformation(in, *out) for

        -
        • +

        • -Usage()
          -建構子, _name 自動取為 " nobody " +YUVf_Space ←→ RGBi_Space

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

          • +
        + +
      +
    +
    +
    HSL_Space.h
    +

    Channel分別是

    +

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

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

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

      • +
    +
    Classes

    • -addOptionValueAccept(unsigned char option, -String const& value, String const& description)
      -針對某個option, 新增一個可接受的額外選項 (如果某個option從頭到尾都 -沒有新增可接受的選項, 則視為不限制), 回傳成功與否 (bool) +meow::HSLf_Space 用 double 存資料, 每個channel數值合法範圍是 0~1.0

      • +
    +
    Functions

    • -hasOptionSetup(unsigned char option)
      -回傳是否有此選項 (bool) +meow::colorTransformation(in, *out) for

      -
      • +

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

      • -getOptionValue(unsigned char option, size_t index)
        -回傳第`index`個額外選項 (String) +HSLf_Space ←→ RGBf_Space

      • -getProcArgsCount()
        -回傳有多少個Process Arguments (size_t) +HSLf_Space ←→ YUVf_Space

        • +
      + +
    +
    +
    +
    HSV_Space.h
    +

    Channel分別是

    +

    • -getProcArg(size_t index)
      -取得第`index`個Process Argument (String) +H 色調

    • -getProcArgs()
      -回傳一個陣列, 包含所有Process Arguments (Strings) +S 飽和度

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

      • +
    +
    Classes

    • -addUsageEnd (String const& des)
      -新增一段usage document於每個選項逐條說明之後 +meow::HSVf_Space 用 double 存資料, 每個channel數值合法範圍是 0~1.0

      • +
    +
    Functions

    • -String getUsage()
      -回傳usage document (String) +meow::colorTransformation(in, *out) for

      -
      • +

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

        • -
      -
      - - - -
      -
      Note
      -      		 -

      • -String 是 std::string . +HSVf_Space ←→ RGBf_Space

      • -Strings 是 std::vector< std::string> >. +HSVf_Space ←→ YUVf_Space

      • -如果沒有寫回傳什麼, 就是回傳 void +HSVf_Space ←→ HSLf_Space

      -
      -
      -
      -
    + +
    -
    -

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

      dsa/

      +

      包含一些資料結構

      +
      +
      BinaryIndexTree.h
      +

      極度簡化的 SegmentTree 已無區間更新的操作.

      +
      Classes

      • -very fast 表示它算的真的超級快, 可以視為常數時間. +meow::BinaryIndexTree<Value>

        • +
      +
      +
      +
      DisjointSet.h
      +

      用來維護一堆互斥集的資訊.

      +
      Classes

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

      -
    -
    -
    -
    -
    -
    -

    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

    -
      +
      +
      HashTable.h
      +

      就是傳說中的HashTable

      +
      Classes

      • -N ← this 中擁有的資料數 +meow::HashTableList<Data, HashFunc>

      - ------- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
      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
      -      		 -
        +
      +
      +
      KD_Tree.h
      +

      查詢第k近鄰居用的

      +
      Classes

      • -假設現在有兩個MergeableHeap A 和 B, 則: +meow::KD_Tree<Vector>

        -
          + +
        +
      +
      +
      MergeableHeap.h
      +

      可合併Heap

      +
      Classes

      • -執行 A.merge(&B) 後 B 會變成空的 +meow::MergeableHeap<Element>

        • +
      +
      +
      +
      SegmentTree.h
      +

      線段樹 +.Classes +* meow::SegmentTree<Value>

      +
      +
      +
      SplayTree.h
      +

      伸展樹, 比一般平衡樹稍強的東東 +* meow::SplayTree<Key, Value> +* meow::SplayTree_Range<Key, Value>

      +
      +
      +
      VP_Tree.h
      +

      查詢第k近鄰居用的

      +
      Classes

      • -執行 B.moveTo(&A) 後 B 會變成空的, A 原本擁有的資料也會覆蓋掉 +meow::VP_Tree<Vector>

      - -
      -
      -
      -
    -
    -

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

    -

    Description

    -

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

    -
    參考資料連結:
      +

      geo/

      +

      計算幾何相關, 算是從math中特化出來的

      +
      +
      Vectors.h
      +

      實作上不是用陣列, 是直接宣告2到3個變數分別存x, y (,z)

      +
      Classes

      • -link +meow::Vector2D<Scalar>

      • -link +meow::Vector3D<Scalar>

      +
    -

    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

    區間合併後的值

    -
      +

      math/

      +
      +
      utility.h
      +

      數學相關的小 function 雜七雜八的不知道歸類何處

      +
      Functions

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

        -
          +

        • -operator+ 為 回傳相加值 +normalize()

        • -operator* 為 回傳*this +denormalize()

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

          • -
        +
      • +

        +inRange() +

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

        -
          + +
        • +

          +cub() +

          +

        • -operator+ 為 回傳相加值 +average()

        • -operator* 為 回傳(*this) * n +average()

        • -operator| 為 回傳相加值 +tAbs()

        +
        Constants
          +
        • +

          +PI +

      -
      -

      Support Methods

      -
        +
        +
        Matrix.h
        +
        Classes

        • -N ← this 所維護的陣列長度 +meow::Matrix<Entry>

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

      -
        +
        +
        Vector.h
        +

        實作上將 Matrix 重新包裝

        +
        Classes

        • -Element → 用來當作回傳資料的媒介 +meow::Vector<Scalar>

          -
            + +
          +
        +
        +
        Transformation.h
        +

        各種轉換的 Base Class, 這裡所謂的 Transformation 形式上不一定要是 Linear, +但原則上都是 input a vector, output a vector 其中input/output的dimension可以 +不同.

        +
        Classes

        • -重定義 operator->() 到 std::pair<Key const&, Value&>* +meow::Transformation<Scalar>

          • +
        +
        +
        +
        Transformations.h
        +

        包含各種 Non-Linear transformation

        +
        Classes

        • -重定義 operator*() 到 std::pair<Key const&, Value&>& +meow::BallProjection<Scalar>

        • -有 operator== , operator!=, operator= 可用 +meow::PhotoProjection<Scalar>

          • +
        +
        +
        +
        LinearTransformation.h
        +

        各種 LinearTransformation 的Base Class, 繼承自 meow::Transformation

        +
        Classes

        • -可以直接用 (*e).second = some_value 來改變SplayTree_Range中的資料 +meow::LinearTransformation<Scalar>

        +
        +
        +
        LinearTransformations.h
        +

        各種 Linear Transformation

        +
        Classes
          +
        • +

          +meow::Rotation3D<Scalar> +

        -
        -

        Support Methods

        -
          +
          +
          methods.h
          +

          一些數學方法

          +
          Functions

          • -N ← this 中擁有的資料數 +ransac()

          • -M ← tree2 中擁有的資料數 +levenbergMarquardt()

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

          oo/

          +

          物件相關

          +
          +
          ObjBase.h
          +
          Classes

          • -假設現在有兩個SplayTree_Range A 和 B, 則: +meow::ObjBase

            -
              + +
            +
          +
          +
          ObjTypes.h
          +
          Classes

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

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

            • -
          - -
          -
          -
          -
          -
          -
        -
        -

        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 中擁有的資料數 +meow::ObjSizeT

          • -
        - ------- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
        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() 的值一定會大於等於原本的值 +meow::ObjDouble

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

        -
        -
        +
        +
        ObjArray.h
        +
        Classes
          +
        • +

          +meow::ObjArray +

          +
          • +
        +
        +
        ObjDictionary.h
        +
        Classes
          +
        • +

          +meow::ObjDictionary +

          +
          • +
        -
        -

        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
        -        		 -
          +
          +
          ObjSelector.h
          +
          Classes

          • -額外附贈一個 const double PI = 3.141592653589...... +meow::ObjSelector<SID>

          -
        -
        +
        @@ -3064,6 +1860,11 @@ width:70%; E-Mail: cat.hook31894 ~在~ gmail.com

        +
      • +

        +GitHub +

        +
      @@ -3071,7 +1872,7 @@ E-Mail: cat.hook31894 ~在~ gmail.com
      -- cgit v1.2.3