<!DOCTYPE html>
<html lang="en">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<meta name="generator" content="AsciiDoc 8.6.7">
<title>meow</title>
<style type="text/css">
/*
* AsciiDoc 'volnitsky' theme for xhtml11 and html5 backends.
* Based on css from http://volnitsky.com, which was in turn based on default
* theme from AsciiDoc
*
* FIXME: The styling is still a bit rough in places.
*
*/
/* Default font. */
body {
font-family: Georgia,"Times New Roman",Times,serif;
}
/* Title font. */
h1, h2, h3, h4, h5, h6,
div.title, caption.title,
thead, p.table.header,
#toctitle,
#author, #revnumber, #revdate, #revremark,
#footer {
font-family: Candara,Arial,sans-serif;
}
#toc a {
border-bottom: 1px dotted #999999;
color: #3A3A4D !important;
text-decoration: none !important;
}
#toc a:hover {
border-bottom: 1px solid #6D4100;
color: #6D4100 !important;
text-decoration: none !important;
}
a { color: #666688; text-decoration: none; border-bottom: 1px dotted #666688; }
a:visited { color: #615FA0; border-bottom: 1px dotted #615FA0; }
a:hover { color: #6D4100; border-bottom: 1px solid #6D4100; }
em {
font-style: italic;
color: #444466;
}
strong {
font-weight: bold;
color: #444466;
}
h1, h2, h3, h4, h5, h6 {
color: #666688;
margin-bottom: 0.5em;
line-height: 1.3;
letter-spacing:+0.15em;
}
h1, h2, h3 { border-bottom: 2px solid #ccd; }
h2 { padding-top: 0.5em; }
h3 { float: left; }
h3 + * { clear: left; }
div.sectionbody {
margin-left: 0;
}
hr {
border: 1px solid #444466;
}
p {
margin-top: 0.5em;
margin-bottom: 0.5em;
}
ul, ol, li > p {
margin-top: 0;
}
pre {
padding: 0;
margin: 0;
}
#author {
color: #444466;
font-weight: bold;
font-size: 1.1em;
}
#footer {
font-size: small;
border-top: 2px solid silver;
padding-top: 0.5em;
margin-top: 4.0em;
}
#footer-text {
float: left;
padding-bottom: 0.5em;
}
#footer-badges {
float: right;
padding-bottom: 0.5em;
}
#preamble {
margin-top: 1.5em;
margin-bottom: 1.5em;
}
div.tableblock, div.imageblock, div.exampleblock, div.verseblock,
div.quoteblock, div.literalblock, div.listingblock, div.sidebarblock,
div.admonitionblock {
margin-top: 1.5em;
margin-bottom: 1.5em;
}
div.admonitionblock {
margin-top: 2.5em;
margin-bottom: 2.5em;
}
div.content { /* Block element content. */
padding: 0;
}
/* Block element titles. */
div.title, caption.title {
color: #444466;
font-weight: bold;
text-align: left;
margin-top: 1.0em;
margin-bottom: 0.5em;
}
div.title + * {
margin-top: 0;
}
td div.title:first-child {
margin-top: 0.0em;
}
div.content div.title:first-child {
margin-top: 0.0em;
}
div.content + div.title {
margin-top: 0.0em;
}
div.sidebarblock > div.content {
background: #ffffee;
border: 1px solid silver;
padding: 0.5em;
}
div.listingblock > div.content {
border: 1px solid silver;
background: #f4f4f4;
padding: 0.5em;
}
div.quoteblock {
padding-left: 2.0em;
margin-right: 10%;
}
div.quoteblock > div.attribution {
padding-top: 0.5em;
text-align: right;
}
div.verseblock {
padding-left: 2.0em;
margin-right: 10%;
}
div.verseblock > pre.content {
font-family: inherit;
}
div.verseblock > div.attribution {
padding-top: 0.75em;
text-align: left;
}
/* DEPRECATED: Pre version 8.2.7 verse style literal block. */
div.verseblock + div.attribution {
text-align: left;
}
div.admonitionblock .icon {
vertical-align: top;
font-size: 1.1em;
font-weight: bold;
text-decoration: underline;
color: #444466;
padding-right: 0.5em;
}
div.admonitionblock td.content {
padding-left: 0.5em;
border-left: 2px solid silver;
}
div.exampleblock > div.content {
border-left: 2px solid silver;
padding: 0.5em;
}
div.imageblock div.content { padding-left: 0; }
span.image img { border-style: none; }
a.image:visited { color: white; }
dl {
margin-top: 0.8em;
margin-bottom: 0.8em;
}
dt {
margin-top: 0.5em;
margin-bottom: 0;
font-style: normal;
color: #444466;
}
dd > *:first-child {
margin-top: 0.1em;
}
ul, ol {
list-style-position: outside;
}
ol.arabic {
list-style-type: decimal;
}
ol.loweralpha {
list-style-type: lower-alpha;
}
ol.upperalpha {
list-style-type: upper-alpha;
}
ol.lowerroman {
list-style-type: lower-roman;
}
ol.upperroman {
list-style-type: upper-roman;
}
div.compact ul, div.compact ol,
div.compact p, div.compact p,
div.compact div, div.compact div {
margin-top: 0.1em;
margin-bottom: 0.1em;
}
div.tableblock > table {
border: 3px solid #444466;
}
thead {
font-weight: bold;
color: #444466;
}
tfoot {
font-weight: bold;
}
td > div.verse {
white-space: pre;
}
p.table {
margin-top: 0;
}
/* Because the table frame attribute is overriden by CSS in most browsers. */
div.tableblock > table[frame="void"] {
border-style: none;
}
div.tableblock > table[frame="hsides"] {
border-left-style: none;
border-right-style: none;
}
div.tableblock > table[frame="vsides"] {
border-top-style: none;
border-bottom-style: none;
}
div.hdlist {
margin-top: 0.8em;
margin-bottom: 0.8em;
}
div.hdlist tr {
padding-bottom: 15px;
}
dt.hdlist1.strong, td.hdlist1.strong {
font-weight: bold;
}
td.hdlist1 {
vertical-align: top;
font-style: normal;
padding-right: 0.8em;
color: #444466;
}
td.hdlist2 {
vertical-align: top;
}
div.hdlist.compact tr {
margin: 0;
padding-bottom: 0;
}
.comment {
background: yellow;
}
@media print {
#footer-badges { display: none; }
}
#toctitle {
color: #666688;
font-size: 1.2em;
font-weight: bold;
margin-top: 1.0em;
margin-bottom: 0.1em;
}
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; }
body {
margin: 1em 5%;
max-width: 55em;
padding-left: 0;
}
.monospaced, tt, div.listingblock > div.content {
font-family: Consolas, "Andale Mono", "Courier New", monospace;
color: #004400;
background: #e4e4e4;
max-width: 80em;
line-height: 1.2em;
border-radius: 4px;
-moz-border-radius: 4px;
-webkit-border-radius: 4px;
}
.paragraph p {
line-height: 1.5em;
margin-top: 1em;
}
.paragraph p, li, dd, .content { max-width: 100%; }
.admonitionblock { max-width: 95%; }
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 div.ulist > ul > li {
color: #ccd ;
}
div.sectionbody div.ulist > ul > li div.ulist > ul > li > * {
color: black ;
}
em {
font-style: normal ! important;
font-weight: bold ! important;
color: #662222 ! important;
letter-spacing:+0.08em ! important;
}
/*
* html5 specific
*
* */
table.tableblock {
margin-top: 1.0em;
margin-bottom: 1.5em;
}
thead, p.tableblock.header {
font-weight: bold;
color: #666688;
}
p.tableblock {
margin-top: 0;
}
table.tableblock {
border-width: 3px;
border-spacing: 0px;
border-style: solid;
border-color: #444466;
border-collapse: collapse;
}
th.tableblock, td.tableblock {
border-width: 1px;
padding: 4px;
border-style: solid;
border-color: #444466;
}
table.tableblock.frame-topbot {
border-left-style: hidden;
border-right-style: hidden;
}
table.tableblock.frame-sides {
border-top-style: hidden;
border-bottom-style: hidden;
}
table.tableblock.frame-none {
border-style: hidden;
}
th.tableblock.halign-left, td.tableblock.halign-left {
text-align: left;
}
th.tableblock.halign-center, td.tableblock.halign-center {
text-align: center;
}
th.tableblock.halign-right, td.tableblock.halign-right {
text-align: right;
}
th.tableblock.valign-top, td.tableblock.valign-top {
vertical-align: top;
}
th.tableblock.valign-middle, td.tableblock.valign-middle {
vertical-align: middle;
}
th.tableblock.valign-bottom, td.tableblock.valign-bottom {
vertical-align: bottom;
}
@media screen {
body {
max-width: 50em; /* approximately 80 characters wide */
margin-left: 16em;
}
#toc {
position: fixed;
top: 0;
left: 0;
bottom: 0;
width: 13em;
padding: 0.5em;
padding-bottom: 1.5em;
margin: 0;
overflow: auto;
border-right: 3px solid #f8f8f8;
background-color: white;
}
#toc .toclevel1 {
margin-top: 0.5em;
}
#toc .toclevel2 {
margin-top: 0.25em;
display: list-item;
color: #aaaaaa;
}
#toctitle {
margin-top: 0.5em;
}
}
</style>
<script type="text/javascript">
/*<+'])');
// Function that scans the DOM tree for header elements (the DOM2
// nodeIterator API would be a better technique but not supported by all
// browsers).
var iterate = function (el) {
for (var i = el.firstChild; i != null; i = i.nextSibling) {
if (i.nodeType == 1 /* Node.ELEMENT_NODE */) {
var mo = re.exec(i.tagName);
if (mo && (i.getAttribute("class") || i.getAttribute("className")) != "float") {
result[result.length] = new TocEntry(i, getText(i), mo[1]-1);
}
iterate(i);
}
}
}
iterate(el);
return result;
}
var toc = document.getElementById("toc");
if (!toc) {
return;
}
// Delete existing TOC entries in case we're reloading the TOC.
var tocEntriesToRemove = [];
var i;
for (i = 0; i < toc.childNodes.length; i++) {
var entry = toc.childNodes[i];
if (entry.nodeName.toLowerCase() == 'div'
&& entry.getAttribute("class")
&& entry.getAttribute("class").match(/^toclevel/))
tocEntriesToRemove.push(entry);
}
for (i = 0; i < tocEntriesToRemove.length; i++) {
toc.removeChild(tocEntriesToRemove[i]);
}
// Rebuild TOC entries.
var entries = tocEntries(document.getElementById("content"), toclevels);
for (var i = 0; i < entries.length; ++i) {
var entry = entries[i];
if (entry.element.id == "")
entry.element.id = "_toc_" + i;
var a = document.createElement("a");
a.href = "#" + entry.element.id;
a.appendChild(document.createTextNode(entry.text));
var div = document.createElement("div");
div.appendChild(a);
div.className = "toclevel" + entry.toclevel;
toc.appendChild(div);
}
if (entries.length == 0)
toc.parentNode.removeChild(toc);
},
/////////////////////////////////////////////////////////////////////
// Footnotes generator
/////////////////////////////////////////////////////////////////////
/* Based on footnote generation code from:
* http://www.brandspankingnew.net/archive/2005/07/format_footnote.html
*/
footnotes: function () {
// Delete existing footnote entries in case we're reloading the footnodes.
var i;
var noteholder = document.getElementById("footnotes");
if (!noteholder) {
return;
}
var entriesToRemove = [];
for (i = 0; i < noteholder.childNodes.length; i++) {
var entry = noteholder.childNodes[i];
if (entry.nodeName.toLowerCase() == 'div' && entry.getAttribute("class") == "footnote")
entriesToRemove.push(entry);
}
for (i = 0; i < entriesToRemove.length; i++) {
noteholder.removeChild(entriesToRemove[i]);
}
// Rebuild footnote entries.
var cont = document.getElementById("content");
var spans = cont.getElementsByTagName("span");
var refs = {};
var n = 0;
for (i=0; i<spans.length; i++) {
if (spans[i].className == "footnote") {
n++;
var note = spans[i].getAttribute("data-note");
if (!note) {
// Use [\s\S] in place of . so multi-line matches work.
// Because JavaScript has no s (dotall) regex flag.
note = spans[i].innerHTML.match(/\s*\[([\s\S]*)]\s*/)[1];
spans[i].innerHTML =
"[<a id='_footnoteref_" + n + "' href='#_footnote_" + n +
"' title='View footnote' class='footnote'>" + n + "</a>]";
spans[i].setAttribute("data-note", note);
}
noteholder.innerHTML +=
"<div class='footnote' id='_footnote_" + n + "'>" +
"<a href='#_footnoteref_" + n + "' title='Return to text'>" +
n + "</a>. " + note + "</div>";
var id =spans[i].getAttribute("id");
if (id != null) refs["#"+id] = n;
}
}
if (n == 0)
noteholder.parentNode.removeChild(noteholder);
else {
// Process footnoterefs.
for (i=0; i<spans.length; i++) {
if (spans[i].className == "footnoteref") {
var href = spans[i].getElementsByTagName("a")[0].getAttribute("href");
href = href.match(/#.*/)[0]; // Because IE return full URL.
n = refs[href];
spans[i].innerHTML =
"[<a href='#_footnote_" + n +
"' title='View footnote' class='footnote'>" + n + "</a>]";
}
}
}
},
install: function(toclevels) {
var timerId;
function reinstall() {
asciidoc.footnotes();
if (toclevels) {
asciidoc.toc(toclevels);
}
}
function reinstallAndRemoveTimer() {
clearInterval(timerId);
reinstall();
}
timerId = setInterval(reinstall, 500);
if (document.addEventListener)
document.addEventListener("DOMContentLoaded", reinstallAndRemoveTimer, false);
else
window.onload = reinstallAndRemoveTimer;
}
}
asciidoc.install(2);
/*]]>*/
</script>
</head>
<body class="article" style="max-width:70em">
<div id="header">
<h1>meow</h1>
<div id="toc">
<div id="toctitle">Table of Contents</div>
<noscript><p><b>JavaScript must be enabled in your browser to display the table of contents.</b></p></noscript>
</div>
</div>
<div id="content">
<div class="sect1">
<h2 id="_description">Description</h2>
<div class="sectionbody">
<div class="paragraph"><p>一個不需要, 也不應該先compile成obj files的templates.</p></div>
<div class="ulist"><div class="title">Links</div><ul>
<li>
<p>
<a href="https://github.com/cathook/meow">GitHub</a>
</p>
</li>
<li>
<p>
<a href="http://www.csie.ntu.edu.tw/~b01902109/readme/template_meow/README.html">README.html</a>
</p>
</li>
<li>
<p>
<a href="https://github.com/cathook/meow/archive/master.zip">Download</a>
</p>
</li>
</ul></div>
</div>
</div>
<div class="sect1">
<h2 id="_file_tree">File Tree</h2>
<div class="sectionbody">
<div class="sect2">
<h3 id="_strong_meowpp_strong_c_templates"><strong>meowpp/</strong> C++ templates</h3>
<div class="ulist"><ul>
<li>
<p>
<strong>utility.h</strong> some useful functions,
<span class="monospaced">stringPringf()</span> , <span class="monospaced">stringReplace()</span> , <span class="monospaced">cstringEndWith()</span> ,
<span class="monospaced">debugPrintf()</span> , <span class="monospaced">messagePrintf()</span> , <span class="monospaced">constant PI</span> ,
<span class="monospaced">noEPS()</span> , <span class="monospaced">normalize()</span> , <span class="monospaced">denormalize()</span> ,
<span class="monospaced">ratioMapping()</span> , <span class="monospaced">inRange()</span> , <span class="monospaced">squ()</span> , <span class="monospaced">average()</span>
</p>
</li>
<li>
<p>
<strong>Usage.h</strong> <span class="monospaced">class Usage</span>
</p>
</li>
<li>
<p>
<strong>colors/</strong> Color splces and transformer
</p>
<div class="ulist"><ul>
<li>
<p>
<strong>RGB.h</strong> <span class="monospaced">class RGBi</span> , <span class="monospaced">class RGBf</span>
</p>
</li>
<li>
<p>
<strong>YUV.h</strong> <span class="monospaced">class YUVi</span> , <span class="monospaced">class YUVf</span> , <span class="monospaced">RGB_to_YUV()</span> , <span class="monospaced">YUV_to_RGB()</span>
</p>
</li>
<li>
<p>
<strong>HSL.h</strong> <span class="monospaced">class HSLf</span> , <span class="monospaced">RGB_to_HSL()</span> , <span class="monospaced">HSL_to_RGB()</span> ,
<span class="monospaced">YUV_to_HSL()</span> , <span class="monospaced">HSL_to_YUV()</span>
</p>
</li>
<li>
<p>
<strong>HSV.h</strong> <span class="monospaced">class HSVf</span> , <span class="monospaced">RGB_to_HSV()</span> , <span class="monospaced">HSV_to_RGB()</span> ,
<span class="monospaced">YUV_to_HSV()</span> , <span class="monospaced">HSV_to_YUV()</span> ,
<span class="monospaced">HSL_to_HSV()</span> , <span class="monospaced">HSV_to_HSL()</span>
</p>
</li>
</ul></div>
</li>
<li>
<p>
<strong>dsa/</strong> Data Structures and Algorithms
</p>
<div class="ulist"><ul>
<li>
<p>
<strong>BinaryIndexTree.h</strong> <span class="monospaced">class BinaryIndexTree<Vector, Scalar></span>
</p>
</li>
<li>
<p>
<strong>DisjointSet.h</strong> <span class="monospaced">class DisjointSet</span>
</p>
</li>
<li>
<p>
<strong>Heaps.h</strong> <span class="monospaced">class MergeableHeap<Element></span>
</p>
</li>
<li>
<p>
<strong>KD_Tree.h</strong> <span class="monospaced">class KD_Tree<Vector, Scalar></span>
</p>
</li>
<li>
<p>
<strong>SegemenTree.h</strong> <span class="monospaced">class SegmentTree<Value></span>
</p>
</li>
<li>
<p>
<strong>SplayTree.h</strong> <span class="monospaced">class SplayTree<Key, Value></span>
</p>
</li>
<li>
<p>
<strong>SplayTree_Range.h</strong> <span class="monospaced">class SplayTree_Range<Key, Value></span>
</p>
</li>
<li>
<p>
<strong>VP_Tree.h</strong> <span class="monospaced">class VP_Tree<Vector, Scalar></span>
</p>
</li>
</ul></div>
</li>
<li>
<p>
<strong>oo/</strong>
</p>
<div class="ulist"><ul>
<li>
<p>
<strong>Register_Implement.h</strong> <span class="monospaced">class RegisterInterface</span> ,
<span class="monospaced">class ImplementInterface</span>
</p>
</li>
</ul></div>
</li>
</ul></div>
</div>
</div>
</div>
<div class="sect1">
<h2 id="_structures_classes_functions">Structures/Classes/Functions</h2>
<div class="sectionbody">
<div class="sect2">
<h3 id="_meow_strong_functios_strong_in_utility_h">meow:: <strong>Functios</strong> in utility.h</h3>
<table class="tableblock frame-all grid-rows"
style="
width:100%;
">
<col style="width:5%;">
<col style="width:29%;">
<col style="width:5%;">
<col style="width:58%;">
<thead>
<tr>
<th class="tableblock halign-right valign-top" >Name </th>
<th class="tableblock halign-left valign-top" > Parameters </th>
<th class="tableblock halign-left valign-top" > Return_Type </th>
<th class="tableblock halign-left valign-top" > Description</th>
</tr>
</thead>
<tbody>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>stringPrintf</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(char const * <span class="monospaced">fmt</span>, …)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">std::string</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Format print to C++ string and return it</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>stringReplace</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(std::string <span class="monospaced">str</span>,<br></p>
<p class="tableblock">std::string const& <span class="monospaced">from</span>,<br></p>
<p class="tableblock">std::string const& <span class="monospaced">to</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">std::string</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Return a string like <span class="monospaced">str</span>, but all <span class="monospaced">from</span> be replaced by <span class="monospaced">to</span></p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>cstringEndWith</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(char const* <span class="monospaced">str</span>,<br>
int <span class="monospaced">n</span>, …)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">bool</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Return whether <span class="monospaced">str</span> is end with one of the c-string you specify in
the parameters or not</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>debugPrintf</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(char const* <span class="monospaced">fmt</span>, …)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Print debug message (file name, line number, …etc) when <span class="monospaced">DEBUG</span> is
defined</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>messagePrintf</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(int <span class="monospaced">level_change</span>,<br>
char const* <span class="monospaced">fmt</span>, …)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">階層式的訊息輸出</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>noEPS</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(double <span class="monospaced">value</span>, double <span class="monospaced">eps</span> = 1e-9)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">double</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">如果abs(輸入的數值) < eps, 則回傳0, 否則回傳輸入的數值</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>normalize</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(double <span class="monospaced">lower</span>, double <span class="monospaced">upper</span>, <br>
double value)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">double</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock"><span class="monospaced">(value - lower) / (upper - lower)</span></p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>denormalize</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(double <span class="monospaced">lower</span>, double <span class="monospaced">upper</span>,
<br>
double <span class="monospaced">ratio</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">double</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock"><span class="monospaced">lower + (upper - lower) * ratio</span></p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>ratioMapping</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(double <span class="monospaced">l1</span>, double <span class="monospaced">u1</span>,
<br>
double <span class="monospaced">m1</span>, double <span class="monospaced">l2</span>,<br>
double <span class="monospaced">u2</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">double</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock"><span class="monospaced">denormalize(l2, u2, normalize(l1, u1, m1))</span></p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>inRange<T></strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(T const& <span class="monospaced">mn</span>, T const& <span class="monospaced">mx</span>, <br>
T const& <span class="monospaced">v</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">T</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock"><span class="monospaced">std::max(mn, std::min(mx, v))</span></p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>squ<T></strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(T const& <span class="monospaced">x</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">T</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock"><span class="monospaced">x * x</span></p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>average<T></strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(T const& <span class="monospaced">beg</span>, T const& <span class="monospaced">end</span>, <br>
double <span class="monospaced">sigs</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">T</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">只將 <span class="monospaced">sigs</span> 個標準差以內的數據拿來取平均</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>average<T></strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(T const& <span class="monospaced">beg</span>, T const& <span class="monospaced">end</span>,
<br>
T const& <span class="monospaced">p</span>, double <span class="monospaced">sigs</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">T</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">同上, 不過這次用 <span class="monospaced">p</span> 來加權平均</p></td>
</tr>
</tbody>
</table>
<div class="admonitionblock">
<table><tr>
<td class="icon">
<div class="title">Note</div>
</td>
<td class="content">
<div class="ulist"><ul>
<li>
<p>
<span class="monospaced">stringReplace()</span> 不是用什麼好方法寫的因此執行效率很低請別虐待它.
</p>
</li>
<li>
<p>
額外附贈一個 <span class="monospaced">const double PI = 3.141592653589......</span>
</p>
</li>
</ul></div>
</td>
</tr></table>
</div>
<hr>
</div>
<div class="sect2">
<h3 id="_meow_strong_usage_strong_c_class">meow:: <strong>Usage</strong> (C++ Class)</h3>
<div class="sect3">
<h4 id="_description_2">Description</h4>
<div class="paragraph"><p><span class="monospaced">Usage</span> 是用來分析argc, argv和輸出usage document的class.
argc, argv的部份, 有以下規則</p></div>
<div class="ulist"><ul>
<li>
<p>
<span class="monospaced">-c</span> 其中 <span class="monospaced">c</span> 可以代換成正常的一個字元的字符,
這種選像要嘛就是 <strong>有設置</strong> , 不然就是 <strong>沒設置</strong>
</p>
</li>
<li>
<p>
<span class="monospaced">-c <value></span> 附加一個value, 這種選項可以是選擇性 ,即要設定與否都可以,
反之則一定要設定. 另外可以給定value的預設值以及哪些value是可接受的
</p>
</li>
<li>
<p>
<span class="monospaced"><value></span> 其他, 一律視為process arguments
</p>
</li>
</ul></div>
</div>
<div class="sect3">
<h4 id="_methods">Methods</h4>
<div class="ulist"><ul>
<li>
<p>
<span class="monospaced">Usage(String const& _name)</span><br>
建構子, 所有說明文字中 <strong><name></strong> 都會被代換成 <span class="monospaced">_name</span>
</p>
</li>
<li>
<p>
<span class="monospaced">Usage()</span><br>
建構子, <span class="monospaced">_name</span> 自動取為 " <strong>nobody</strong> "
</p>
</li>
<li>
<p>
<span class="monospaced">import(Usage const& usage)</span><br>
將另一個usage的設定匯入, 回傳成功與否 <strong>(bool)</strong>
</p>
</li>
<li>
<p>
<span class="monospaced">update(Usage const& usage)</span><br>
將另一個usage分析argc,argv出來的資料拿來用, 回傳成功與否 <strong>(bool)</strong>
</p>
</li>
<li>
<p>
<span class="monospaced">addOption(unsigned char option, String const& description)</span><br>
新增一個不接額外選項的參數, 並附上說明文字, 回傳成功與否 <strong>(bool)</strong>
</p>
</li>
<li>
<p>
<span class="monospaced">addOption(unsigned char option, String const& description,
String const& value_type, String const& value_default, bool must)</span><br>
新增一個有額外選項的參數, 並附上說明文字, 額外選項的型別跟預設值.
說明文字中所有的" <strong><types></strong> "將會被取代指定的型別, 其中 <span class="monospaced">must</span> 代表
" <strong>是否一定要設定此參數</strong> " , 回傳表成功與否 <strong>(bool)</strong>
</p>
</li>
<li>
<p>
<span class="monospaced">addOptionValueAccept(unsigned char option,
String const& value, String const& description)</span><br>
針對某個option, 新增一個可接受的額外選項 (如果某個option從頭到尾都
沒有新增可接受的選項, 則視為不限制), 回傳成功與否 <strong>(bool)</strong>
</p>
</li>
<li>
<p>
<span class="monospaced">hasOptionSetup(unsigned char option)</span><br>
回傳是否有此選項 <strong>(bool)</strong>
</p>
</li>
<li>
<p>
<span class="monospaced">getOptionValuesCount(unsigned char option)</span><br>
回傳此參數被設置了幾次 <strong>(size_t)</strong> , 只對有接額外參數的有效
</p>
</li>
<li>
<p>
<span class="monospaced">getOptionValue(unsigned char option, size_t index)</span><br>
回傳第`index`個額外選項 <strong>(String)</strong>
</p>
</li>
<li>
<p>
<span class="monospaced">getProcArgsCount()</span><br>
回傳有多少個Process Arguments <strong>(size_t)</strong>
</p>
</li>
<li>
<p>
<span class="monospaced">getProcArg(size_t index)</span><br>
取得第`index`個Process Argument <strong>(String)</strong>
</p>
</li>
<li>
<p>
<span class="monospaced">getProcArgs()</span><br>
回傳一個陣列, 包含所有Process Arguments <strong>(Strings)</strong>
</p>
</li>
<li>
<p>
<span class="monospaced">addUsageBegin(String const& des)</span><br>
新增一段usage document於每個選項逐條說明之前
</p>
</li>
<li>
<p>
<span class="monospaced">addUsageEnd (String const& des)</span> <br>
新增一段usage document於每個選項逐條說明之後
</p>
</li>
<li>
<p>
<span class="monospaced">String getUsage()</span><br>
回傳usage document <strong>(String)</strong>
</p>
</li>
<li>
<p>
<span class="monospaced">setArguments(int argc, char** argv, String* errmsg)</span><br>
輸入argv, argc, 回傳是否沒有錯誤發生 <strong>(bool)</strong> , 其中如果有錯誤發生,
且 <span class="monospaced">errmsg != NULL</span> 則會將錯誤訊息寫入之
</p>
</li>
</ul></div>
<div class="admonitionblock">
<table><tr>
<td class="icon">
<div class="title">Note</div>
</td>
<td class="content">
<div class="ulist"><ul>
<li>
<p>
<span class="monospaced">String</span> 是 <span class="monospaced">std::string</span> .
</p>
</li>
<li>
<p>
<span class="monospaced">Strings</span> 是 <span class="monospaced">std::vector< std::string> ></span>.
</p>
</li>
<li>
<p>
如果沒有寫回傳什麼, 就是回傳 <span class="monospaced">void</span>
</p>
</li>
</ul></div>
</td>
</tr></table>
</div>
<hr>
</div>
</div>
<div class="sect2">
<h3 id="_meow_strong_implementinterface_registerinterface_strong_c_class">meow:: <strong>ImplementInterface/RegisterInterface</strong> (C++ Class)</h3>
<div class="sect3">
<h4 id="_description_3">Description</h4>
<div class="paragraph"><p>Assume there is a problem which can be solved by different algorithms.
Then you can write multiple classes to approach this problem.<br>
Now if you want to decide which algorithm to use in runtime, you can just
approach this case by a simple way:</p></div>
<div class="ulist"><ul>
<li>
<p>
Let all the problem-solving classes inherit from
<span class="monospaced">class ImplementInterface<T></span> , and call the constructure with giving
<span class="monospaced">identify</span> (type <span class="monospaced">T</span> ) .
</p>
</li>
<li>
<p>
Create an class inherit from <span class="monospaced">RegisterInterface<T></span> ,
and register all your implement class to it by call
<span class="monospaced">regImplement(pointer to the class)</span>.
</p>
</li>
<li>
<p>
Select which implement class you want by call
<span class="monospaced">getImplement(identify)</span> , which will return the pointer
to the corresponding class.
</p>
</li>
</ul></div>
<hr>
</div>
</div>
<div class="sect2">
<h3 id="_meow_strong_disjointset_strong_c_class">meow:: <strong>DisjointSet</strong> (C++ class)</h3>
<div class="sect3">
<h4 id="_description_4">Description</h4>
<div class="paragraph"><p><span class="monospaced">DisjointSet</span> 是個<strong>輕量級Data Dtructure</strong>, 用來維護一堆互斥集的資訊.
相關資料可參考
<a href="http://www.csie.ntnu.edu.tw/~u91029/DisjointSets.html">演算法筆記</a></p></div>
</div>
<div class="sect3">
<h4 id="_support_methods">Support Methods</h4>
<table class="tableblock frame-all grid-rows"
style="
width:100%;
">
<col style="width:2%;">
<col style="width:8%;">
<col style="width:18%;">
<col style="width:8%;">
<col style="width:8%;">
<col style="width:54%;">
<thead>
<tr>
<th class="tableblock halign-right valign-top" >Const?</th>
<th class="tableblock halign-right valign-top" >Name </th>
<th class="tableblock halign-left valign-top" > Parameters </th>
<th class="tableblock halign-left valign-top" > Return_Type</th>
<th class="tableblock halign-center valign-top" > Time_Complexity</th>
<th class="tableblock halign-left valign-top" > Description</th>
</tr>
</thead>
<tbody>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>root</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(size_t <span class="monospaced">number</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">size_t</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">very fast</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">回傳 <span class="monospaced">number</span> 所在的 <strong>集合的編號</strong> (0~N-1)</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>size</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">()</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">size_t</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">very fast</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">回傳 <strong>總集合大小</strong></p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>reset</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(size_t <span class="monospaced">N</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(N)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">清空, 並且設定總集合大小為 <span class="monospaced">N</span></p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>merge</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(size_t <span class="monospaced">number1</span>,<br>
size_t <span class="monospaced">number2</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">size_t</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">very fast</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">將 <span class="monospaced">number1</span> 所在的集合 跟 <span class="monospaced">number2</span> 所在的集合 <strong>合併</strong>,
並回傳合併後新的集合的編號</p></td>
</tr>
</tbody>
</table>
<div class="admonitionblock">
<table><tr>
<td class="icon">
<div class="title">Note</div>
</td>
<td class="content">
<div class="ulist"><ul>
<li>
<p>
<strong>very fast</strong> 表示它算的真的超級快, 可以視為常數時間.
</p>
</li>
<li>
<p>
預設值所有 <span class="monospaced">number</span> 所在的集合的編號就是 <span class="monospaced">number</span> 本身,
即沒有任兩個數在同一個set裡面
</p>
</li>
</ul></div>
</td>
</tr></table>
</div>
<hr>
</div>
</div>
<div class="sect2">
<h3 id="_meow_strong_mergeableheap_lt_element_gt_strong_c_class">meow:: <strong>MergeableHeap<Element></strong> (C++ class)</h3>
<div class="sect3">
<h4 id="_description_5">Description</h4>
<div class="paragraph"><p>一個用 <strong>左偏樹</strong> 實作的 <strong>Maximum-Heap</strong> , 除了原本heap有的功能外,
還支援 <span class="monospaced">merge</span>, <span class="monospaced">split</span> 等功能</p></div>
</div>
<div class="sect3">
<h4 id="_template_class_operators_request">Template Class Operators Request</h4>
<table class="tableblock frame-all grid-rows"
style="
width:70%;
">
<col style="width:3%;">
<col style="width:3%;">
<col style="width:10%;">
<col style="width:17%;">
<col style="width:10%;">
<col style="width:53%;">
<thead>
<tr>
<th class="tableblock halign-right valign-top" >Const?</th>
<th class="tableblock halign-left valign-top" >Typename</th>
<th class="tableblock halign-left valign-top" > Operator </th>
<th class="tableblock halign-left valign-top" > Parameters </th>
<th class="tableblock halign-left valign-top" > Return_Type</th>
<th class="tableblock halign-left valign-top" > Description</th>
</tr>
</thead>
<tbody>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Element</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong>operator<</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(Element <span class="monospaced">v</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">bool</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">大小比較</p></td>
</tr>
</tbody>
</table>
</div>
<div class="sect3">
<h4 id="_support_methods_2">Support Methods</h4>
<div class="ulist"><ul>
<li>
<p>
N ← <span class="monospaced">this</span> 中擁有的資料數
</p>
</li>
</ul></div>
<table class="tableblock frame-all grid-rows"
style="
width:100%;
">
<col style="width:2%;">
<col style="width:5%;">
<col style="width:19%;">
<col style="width:8%;">
<col style="width:8%;">
<col style="width:55%;">
<thead>
<tr>
<th class="tableblock halign-right valign-top" >Const?</th>
<th class="tableblock halign-right valign-top" >Name </th>
<th class="tableblock halign-left valign-top" > Parameters </th>
<th class="tableblock halign-left valign-top" > Return_Type</th>
<th class="tableblock halign-center valign-top" > Time_Complexity</th>
<th class="tableblock halign-left valign-top" > Description</th>
</tr>
</thead>
<tbody>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>moveTo</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(MergeableHeap* <span class="monospaced">h</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(M)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">將 <span class="monospaced">this</span> 的資料複寫到 <span class="monospaced">h</span> 上面, 同時清空自己,
時間複雜度中的M是 <span class="monospaced">h</span> 所擁有的資料數</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>top</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">()</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Element const&</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(1)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">回傳最大的那個 <span class="monospaced">Element</span></p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>size</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">()</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">size_t</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(1)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">回傳 <span class="monospaced">this</span> 中擁有的資料數</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>empty</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">()</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">bool</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(1)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">回傳 <span class="monospaced">this</span> 是否為空</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>push</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(Element const& <span class="monospaced">e</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">將 <span class="monospaced">e</span> 加入</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>pop</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">()</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">將最大的 <span class="monospaced">Element</span> 移除</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>clear</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">()</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(N)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">將資料清空</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>merge</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(MergeableHeap* <span class="monospaced">heap2</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN+logM)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">將 <span class="monospaced">heap2</span> 的資料統統加到 <span class="monospaced">this</span> 中, 並且清空 <span class="monospaced">heap2</span>
時間複雜度中的M是 <span class="monospaced">heap2</span> 的資料數</p></td>
</tr>
</tbody>
</table>
<div class="admonitionblock">
<table><tr>
<td class="icon">
<div class="title">Warning</div>
</td>
<td class="content">
<div class="ulist"><ul>
<li>
<p>
假設現在有兩個MergeableHeap <span class="monospaced">A</span> 和 <span class="monospaced">B</span>, 則:
</p>
<div class="ulist"><ul>
<li>
<p>
執行 <span class="monospaced">A.merge(&B)</span> 後 <span class="monospaced">B</span> 會變成空的
</p>
</li>
<li>
<p>
執行 <span class="monospaced">B.moveTo(&A)</span> 後 <span class="monospaced">B</span> 會變成空的, <span class="monospaced">A</span> 原本擁有的資料也會覆蓋掉
</p>
</li>
</ul></div>
</li>
</ul></div>
</td>
</tr></table>
</div>
<hr>
</div>
</div>
<div class="sect2">
<h3 id="_meow_strong_vp_tree_lt_vector_scalar_gt_strong_c_class">meow:: <strong>VP_Tree<Vector, Scalar></strong> (C++ class)</h3>
<div class="sect3">
<h4 id="_description_6">Description</h4>
<div class="paragraph"><p><span class="monospaced">VP_Tree</span> 用來維護由 <strong>N個K維度向量所成的集合</strong>,
並可於該set中查找 <strong>前i個離給定向量最接近的向量</strong>.<br>
不像 <span class="monospaced">KD_Tree</span> 二分樹每次都選擇一個維度去分, 分成小的跟大的,
<span class="monospaced">VP_Tree</span> 每次選一個點, 將資料分成 離這個點近的, 跟離這個點遠的.
至於怎麼選呢…., 嘛還沒研究, 先random</p></div>
<div class="ulist"><div class="title">參考資料連結:</div><ul>
<li>
<p>
<a href="http://stevehanov.ca/blog/index.php?id=130">link</a>
</p>
</li>
<li>
<p>
<a href="http://pnylab.com/pny/papers/vptree/vptree">link</a>
</p>
</li>
</ul></div>
</div>
<div class="sect3">
<h4 id="_template_class_operators_request_2">Template Class Operators Request</h4>
<table class="tableblock frame-all grid-rows"
style="
width:70%;
">
<col style="width:3%;">
<col style="width:3%;">
<col style="width:10%;">
<col style="width:17%;">
<col style="width:10%;">
<col style="width:53%;">
<thead>
<tr>
<th class="tableblock halign-right valign-top" >Const?</th>
<th class="tableblock halign-left valign-top" >Typename</th>
<th class="tableblock halign-left valign-top" > Operator </th>
<th class="tableblock halign-left valign-top" > Parameters </th>
<th class="tableblock halign-left valign-top" > Return_Type</th>
<th class="tableblock halign-left valign-top" > Description</th>
</tr>
</thead>
<tbody>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Vector</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong>operator[]</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(size_t <span class="monospaced">n</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Scalar</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">取得第 <span class="monospaced">n</span> 維度量</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Vector</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong>operator=</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(Vector <span class="monospaced">v</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Vector&</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">copy operator</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Vector</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong>operator<</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(Vector <span class="monospaced">v</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">bool</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">權重比較</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Scalar</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong><em>Scalar</em></strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(int <span class="monospaced">n</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Scalar</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">建構子,
其中一定<span class="monospaced">n=0 or 4</span></p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Scalar</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong>operator*</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(Scalar <span class="monospaced">s</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Scalar</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">相乘</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Scalar</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong>operator+</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(Scalar <span class="monospaced">s</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Scalar</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">相加</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Scalar</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong>operator-</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(Scalar <span class="monospaced">s</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Scalar</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">相差</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Scalar</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong>operator-</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">( )</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Scalar</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">取負號</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Scalar</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong>operator<</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(Scalar <span class="monospaced">s</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">bool</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">大小比較</p></td>
</tr>
</tbody>
</table>
</div>
<div class="sect3">
<h4 id="_custom_type_definitions">Custom Type Definitions</h4>
<div class="ulist"><ul>
<li>
<p>
<span class="monospaced">Vectors</span> ← <span class="monospaced">std::vector<Vector></span>
</p>
</li>
</ul></div>
</div>
<div class="sect3">
<h4 id="_support_methods_3">Support Methods</h4>
<div class="ulist"><ul>
<li>
<p>
N ← <span class="monospaced">this</span> 中擁有的資料數
</p>
</li>
<li>
<p>
D ← <span class="monospaced">this</span> 資料維度
</p>
</li>
</ul></div>
<table class="tableblock frame-all grid-rows"
style="
width:100%;
">
<col style="width:2%;">
<col style="width:8%;">
<col style="width:18%;">
<col style="width:8%;">
<col style="width:8%;">
<col style="width:54%;">
<thead>
<tr>
<th class="tableblock halign-right valign-top" >Const?</th>
<th class="tableblock halign-right valign-top" >Name </th>
<th class="tableblock halign-left valign-top" > Parameters </th>
<th class="tableblock halign-left valign-top" > Return_Type</th>
<th class="tableblock halign-center valign-top" > Time_Complexity</th>
<th class="tableblock halign-left valign-top" > Description</th>
</tr>
</thead>
<tbody>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>insert</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(Vector const& <span class="monospaced">v</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(1)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">將向量 <span class="monospaced">v</span> 加到set中</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>erase</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(Vector const& <span class="monospaced">v</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">bool</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(N)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">將向量 <span class="monospaced">v</span> 從set中移除, <em><sub>TODO:可以再優化</sub></em></p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>build</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">()</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(KN logN) or O(1)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">檢查距上一次 <span class="monospaced">build()</span> 至今是否有 <span class="monospaced">insert/erase</span> 被呼叫,
若有, 重新建樹, 否則不做事</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>forceBuild</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">()</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(KN logN)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">重新建樹</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>query</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(Vector const& <span class="monospaced">v</span>,<br>
size_t <span class="monospaced">i</span>,<br>
bool <span class="monospaced">cmp</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Vectors</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN) <sub>Expected</sub></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">於set中找尋距離 <span class="monospaced">v</span> 前 <span class="monospaced">i</span> 近的向量, 並依照由近而遠的順序排序.
如果有兩個向量 <span class="monospaced">v1</span>,<span class="monospaced">v2</span> 距離一樣, 且 <span class="monospaced">cmp</span> 為 <span class="monospaced">true</span> , 則直接依照
<span class="monospaced">v1 < v2</span> 來決定誰在前面. 最後回傳一陣列包含所有解.</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>clear</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">()</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(1)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">清空所有資料</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>reset</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(size_t <span class="monospaced">dimension</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">size_t</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(1)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">清空所有資料並且指定維度為 <span class="monospaced">max(1, dimension)</span> 並且回傳指定後的維度</p></td>
</tr>
</tbody>
</table>
<div class="admonitionblock">
<table><tr>
<td class="icon">
<div class="title">Note</div>
</td>
<td class="content">
<div class="ulist"><ul>
<li>
<p>
實測結果發覺, 維度小的時候, 比起中規中矩的 <span class="monospaced">KD_Tree</span>, <span class="monospaced">VP_Tree</span> 有
<em>randomp</em> 於其中, 因此時間複雜度只是期望值 <em>O(logN)</em> 但是測資大到
一定程度, <span class="monospaced">KD_Tree</span> 效率會一整個大幅掉下, 但 <span class="monospaced">VP_Tree</span> 幾乎不受影響
</p>
</li>
<li>
<p>
<em>TODO</em> <span class="monospaced">insert()</span>, <span class="monospaced">erase()</span> 算是未完成功能
</p>
</li>
</ul></div>
</td>
</tr></table>
</div>
<hr>
</div>
</div>
<div class="sect2">
<h3 id="_meow_strong_kd_tree_lt_vector_scalar_gt_strong_c_class">meow:: <strong>KD_Tree<Vector, Scalar></strong> (C++ class)</h3>
<div class="sect3">
<h4 id="_description_7">Description</h4>
<div class="paragraph"><p><span class="monospaced">KD_Tree</span> 全名k-dimension tree, 用來維護由 <strong>N個K維度向量所成的集合</strong>,
並可於該set中查找 <strong>前i個離給定向量最接近的向量</strong></p></div>
</div>
<div class="sect3">
<h4 id="_template_class_operators_request_3">Template Class Operators Request</h4>
<table class="tableblock frame-all grid-rows"
style="
width:70%;
">
<col style="width:3%;">
<col style="width:3%;">
<col style="width:10%;">
<col style="width:17%;">
<col style="width:10%;">
<col style="width:53%;">
<thead>
<tr>
<th class="tableblock halign-right valign-top" >Const?</th>
<th class="tableblock halign-left valign-top" >Typename</th>
<th class="tableblock halign-left valign-top" > Operator </th>
<th class="tableblock halign-left valign-top" > Parameters </th>
<th class="tableblock halign-left valign-top" > Return_Type</th>
<th class="tableblock halign-left valign-top" > Description</th>
</tr>
</thead>
<tbody>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Vector</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong>operator[]</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(size_t <span class="monospaced">n</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Scalar</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">取得第 <span class="monospaced">n</span> 維度量</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Vector</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong>operator<</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(Vector <span class="monospaced">v</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">bool</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">權重比較</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Scalar</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong>operator*</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(Scalar <span class="monospaced">s</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Scalar</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">相乘</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Scalar</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong>operator+</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(Scalar <span class="monospaced">s</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Scalar</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">相加</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Scalar</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong>operator-</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(Scalar <span class="monospaced">s</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Scalar</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">相差</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Scalar</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong>operator<</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(Scalar <span class="monospaced">s</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">bool</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">大小比較</p></td>
</tr>
</tbody>
</table>
</div>
<div class="sect3">
<h4 id="_custom_type_definitions_2">Custom Type Definitions</h4>
<div class="ulist"><ul>
<li>
<p>
<span class="monospaced">Vectors</span> ← <span class="monospaced">std::vector<Vector></span>
</p>
</li>
</ul></div>
</div>
<div class="sect3">
<h4 id="_support_methods_4">Support Methods</h4>
<div class="ulist"><ul>
<li>
<p>
N ← <span class="monospaced">this</span> 中擁有的資料數
</p>
</li>
<li>
<p>
K ← <span class="monospaced">this</span> 資料維度
</p>
</li>
</ul></div>
<table class="tableblock frame-all grid-rows"
style="
width:100%;
">
<col style="width:2%;">
<col style="width:8%;">
<col style="width:18%;">
<col style="width:8%;">
<col style="width:8%;">
<col style="width:54%;">
<thead>
<tr>
<th class="tableblock halign-right valign-top" >Const?</th>
<th class="tableblock halign-right valign-top" >Name </th>
<th class="tableblock halign-left valign-top" > Parameters </th>
<th class="tableblock halign-left valign-top" > Return_Type</th>
<th class="tableblock halign-center valign-top" > Time_Complexity</th>
<th class="tableblock halign-left valign-top" > Description</th>
</tr>
</thead>
<tbody>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>insert</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(Vector const& <span class="monospaced">v</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(1)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">將向量 <span class="monospaced">v</span> 加到set中</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>erase</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(Vector const& <span class="monospaced">v</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">bool</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(N)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">將向量 <span class="monospaced">v</span> 從set中移除, <em><sub>TODO:可以再優化</sub></em></p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>build</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">()</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(KN logN) or O(1)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">檢查距上一次 <span class="monospaced">build()</span> 至今是否有 <span class="monospaced">insert/erase</span> 被呼叫,
若有, 重新建樹, 否則不做事</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>forceBuild</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">()</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(KN logN)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">重新建樹</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>query</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(Vector const& <span class="monospaced">v</span>,<br>
size_t <span class="monospaced">i</span>,<br>
bool <span class="monospaced">cmp</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Vectors</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(KN <sup>1-1/K</sup> )</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">於set中找尋距離 <span class="monospaced">v</span> 前 <span class="monospaced">i</span> 近的向量, 並依照由近而遠的順序排序.
如果有兩個向量 <span class="monospaced">v1</span>,<span class="monospaced">v2</span> 距離一樣, 且 <span class="monospaced">cmp</span> 為 <span class="monospaced">true</span> , 則直接依照
<span class="monospaced">v1 < v2</span> 來決定誰在前面. 最後回傳一陣列包含所有解.</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>clear</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">()</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(1)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">清空所有資料</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>reset</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(size_t <span class="monospaced">dimension</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(1)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">清空所有資料並且指定維度為 <span class="monospaced">dimension</span></p></td>
</tr>
</tbody>
</table>
<div class="admonitionblock">
<table><tr>
<td class="icon">
<div class="title">Note</div>
</td>
<td class="content">
<div class="ulist"><ul>
<li>
<p>
此資料結構只有在 N >> 2 <sup>K</sup> 時才比較有優勢,
當 K 逐漸變大時, 所花時間會跟暴搜沒兩樣
</p>
</li>
</ul></div>
</td>
</tr></table>
</div>
<hr>
</div>
</div>
<div class="sect2">
<h3 id="_meow_strong_splaytree_lt_key_value_gt_strong_c_class">meow:: <strong>SplayTree<Key, Value></strong> (C++ class)</h3>
<div class="sect3">
<h4 id="_description_8">Description</h4>
<div class="paragraph"><p><span class="monospaced">SplayTree</span> 是一種神乎其技的資料結構, 維護一堆 Key→Value . 並且支援
一些 <span class="monospaced">std::map</span> 難以快速實踐的操作, 如 <span class="monospaced">split</span> , <span class="monospaced">merge</span> , <span class="monospaced">keyOffset</span></p></div>
</div>
<div class="sect3">
<h4 id="_template_class_operators_request_4">Template Class Operators Request</h4>
<table class="tableblock frame-all grid-rows"
style="
width:70%;
">
<col style="width:3%;">
<col style="width:3%;">
<col style="width:10%;">
<col style="width:17%;">
<col style="width:10%;">
<col style="width:53%;">
<thead>
<tr>
<th class="tableblock halign-right valign-top" >Const?</th>
<th class="tableblock halign-left valign-top" >Typename</th>
<th class="tableblock halign-left valign-top" > Operator</th>
<th class="tableblock halign-left valign-top" > Parameters </th>
<th class="tableblock halign-left valign-top" > Return_Type</th>
<th class="tableblock halign-left valign-top" > Description</th>
</tr>
</thead>
<tbody>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Key</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong>operator+</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(Key <span class="monospaced">k</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Key</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">相加</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Key</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong>operator<</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(Key <span class="monospaced">k</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">bool</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">大小比較</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Key</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong><em>Key</em></strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(int <span class="monospaced">n</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock"></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">建構子, <span class="monospaced">n</span> 永遠是0</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Value</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong><em>Value</em></strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">( )</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock"></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">建構子</p></td>
</tr>
</tbody>
</table>
</div>
<div class="sect3">
<h4 id="_custom_type_definitions_3">Custom Type Definitions</h4>
<div class="ulist"><ul>
<li>
<p>
<span class="monospaced">Element</span> → 用來當作回傳資料的媒介
</p>
<div class="ulist"><ul>
<li>
<p>
重定義 <span class="monospaced">operator->()</span> 到 <span class="monospaced">std::pair<Key const&, Value&>*</span>
</p>
</li>
<li>
<p>
重定義 <span class="monospaced">operator*()</span> 到 <span class="monospaced">std::pair<Key const&, Value&>&</span>
</p>
</li>
<li>
<p>
有 <span class="monospaced">operator==</span> , <span class="monospaced">operator!=</span>, <span class="monospaced">operator=</span> 可用
</p>
</li>
<li>
<p>
可以直接用 <span class="monospaced">(*e).second = some_value</span> 來改變SplayTree中的資料
</p>
</li>
</ul></div>
</li>
</ul></div>
</div>
<div class="sect3">
<h4 id="_support_methods_5">Support Methods</h4>
<div class="ulist"><ul>
<li>
<p>
N ← <span class="monospaced">this</span> 中擁有的資料數
</p>
</li>
<li>
<p>
M ← <span class="monospaced">tree2</span> 中擁有的資料數
</p>
</li>
</ul></div>
<table class="tableblock frame-all grid-rows"
style="
width:100%;
">
<col style="width:2%;">
<col style="width:8%;">
<col style="width:18%;">
<col style="width:8%;">
<col style="width:8%;">
<col style="width:54%;">
<thead>
<tr>
<th class="tableblock halign-right valign-top" >Const?</th>
<th class="tableblock halign-right valign-top" >Name </th>
<th class="tableblock halign-left valign-top" > Parameters </th>
<th class="tableblock halign-left valign-top" > Return_Type</th>
<th class="tableblock halign-center valign-top" > Time_Complexity</th>
<th class="tableblock halign-left valign-top" > Description</th>
</tr>
</thead>
<tbody>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>moveTo</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(SplayTree* <span class="monospaced">tree2</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(M)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">將 <span class="monospaced">this</span> 的資料複寫到 <span class="monospaced">tree2</span> 上面, 同時清空自己,
時間複雜度中的M是 <span class="monospaced">tree2</span> 所擁有的資料數</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>lowerBound</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(Key const& <span class="monospaced">k</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Element</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">找出第一個(最小的) Element且 <span class="monospaced">k</span> ⇐ 它的 Key, 並且回傳之.
找不到的話回傳 <span class="monospaced">this->end()</span></p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>lowerBound</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(Key const& <span class="monospaced">k</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Element</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">找出第一個(最小的) Element且 <span class="monospaced">k</span> < 它的 Key, 並且回傳之.
找不到的話回傳 <span class="monospaced">this->end()</span></p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>lowerBound</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(Key const& <span class="monospaced">k</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Element</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">找出第一個(最小的) Element且 <span class="monospaced">k</span> >= 它的 Key, 並且回傳之.
找不到的話回傳 <span class="monospaced">this->end()</span></p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>lowerBound</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(Key const& <span class="monospaced">k</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Element</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">找出第一個(最小的) Element且 <span class="monospaced">k</span> > 它的 Key, 並且回傳之.
找不到的話回傳 <span class="monospaced">this->end()</span></p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>find</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(Key const& <span class="monospaced">k</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Element</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">找出 Key= <span class="monospaced">k</span> 的Elemenet 並回傳. 找不到的話回傳 <span class="monospaced">this->end()</span></p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>order</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(size_t <span class="monospaced">ord</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Element</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">將Elements依照Key由小到大排序, 回傳第 <span class="monospaced">ord</span> 個Element (由0算起).
其中如果 <span class="monospaced">ord</span> > N - 1, 則會回傳 <span class="monospaced">this->last()</span></p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>first</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(size_t <span class="monospaced">ord</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Element</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">回傳Key最小的Element, 如果SplayTree為空, 則回傳 <span class="monospaced">this->end()</span></p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>last</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(size_t <span class="monospaced">ord</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Element</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">回傳Key最大的Element, 如果SplayTree為空, 則回傳 <span class="monospaced">this->end()</span></p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>end</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">()</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Element</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(1)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">回傳一個指向NULL的Element, 以供 <span class="monospaced">find</span> , <span class="monospaced">order</span> , <span class="monospaced">first</span>
, <span class="monospaced">last</span> 等判斷是否有找到相對應的Element</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>size</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">()</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">size_t</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(1)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">回傳資料數</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>size</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">()</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">bool</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(1)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">回傳是否為空</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>clear</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">()</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(N)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">清空資料</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>insert</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(Key const& <span class="monospaced">key</span>,<br>
Value const& <span class="monospaced">value</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">bool</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">檢查是否已有Element的Key 為 <span class="monospaced">key</span>, 若有則回傳 <span class="monospaced">false</span> , 否則將
一個 (Key → Value) = (<span class="monospaced">key</span> → <span class="monospaced">value</span>)的Element加入, 並回傳 <span class="monospaced">true</span>
將所有Element的Key同加上 <span class="monospaced">delta</span></p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>erase</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(Key const& <span class="monospaced">key</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">bool</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">檢查是否已有Element的Key 為 <span class="monospaced">key</span>, 若有則刪除之, 並回傳 <span class="monospaced">true</span>,
否則則回傳 <span class="monospaced">false</span></p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>keyOffset</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(Key const& <span class="monospaced">delta</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(1)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">將所有Element的Key同加上 <span class="monospaced">delta</span></p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>operator[]</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(Key const& <span class="monospaced">key</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Value&</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">檢查是否已有Element的Key 為 <span class="monospaced">key</span>, 若有則回傳相對應的Value的Reference
否則先執行 <span class="monospaced">insert(key, Value())</span> 再回傳相對應的Reference</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>splitOut</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(Key const& <span class="monospaced">upper_bound</span>,<br>
SplayTree* <span class="monospaced">tree2</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN) + O(M)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">將 <span class="monospaced">tree2</span> 清空, 再將所有Key > <span class="monospaced">upper_bound</span> 的Element都丟到 <span class="monospaced">tree2</span></p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>mergeAfter</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(SplayTree* <span class="monospaced">tree2</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN) + O(logM)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">檢查是否 <span class="monospaced">this</span> 中的 Key 都小於 <span class="monospaced">tree2</span> 中的Key, 是的話把 <span class="monospaced">tree2</span>
中的 Element 都搬到 <span class="monospaced">this</span> , 同時清空 <span class="monospaced">tree2</span> , 回傳 <span class="monospaced">true</span>. 否則
回傳 <span class="monospaced">false</span></p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>merge</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(SplayTree* <span class="monospaced">tree2</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN) + O(logM)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">檢查是否 <span class="monospaced">this</span> 中的 Key 都小於 <span class="monospaced">tree2</span> 中的Key 或者
是否 <span class="monospaced">this</span> 中的 Key 都大於 <span class="monospaced">tree2</span> 中的Key, 是的話把 <span class="monospaced">tree2</span>
中的 Element 都搬到 <span class="monospaced">this</span> , 同時清空 <span class="monospaced">tree2</span> , 回傳 <span class="monospaced">true</span>. 否則
回傳 <span class="monospaced">false</span></p></td>
</tr>
</tbody>
</table>
<div class="admonitionblock">
<table><tr>
<td class="icon">
<div class="title">Note</div>
</td>
<td class="content">
<div class="ulist"><ul>
<li>
<p>
假設現在有兩個SplayTree <span class="monospaced">A</span> 和 <span class="monospaced">B</span>, 則:
</p>
<div class="ulist"><ul>
<li>
<p>
執行 <span class="monospaced">B.moveTo(&A)</span> 後 <span class="monospaced">B</span> 會變成空的, <span class="monospaced">A</span> 原本擁有的資料也會覆蓋掉
</p>
</li>
<li>
<p>
執行 <span class="monospaced">A.merge(&B)</span> 或 <span class="monospaced">A.mergeAfter(&B)</span> 後
如果檢查發現確實可以merge, 則之後 <span class="monospaced">B</span> 會變成空的
</p>
</li>
</ul></div>
</li>
</ul></div>
</td>
</tr></table>
</div>
<hr>
</div>
</div>
<div class="sect2">
<h3 id="_meow_strong_segmenttree_lt_value_gt_strong_c_class">meow:: <strong>SegmentTree<Value></strong> (C++ class)</h3>
<div class="sect3">
<h4 id="_description_9">Description</h4>
<div class="paragraph"><p>維護一個陣列, 並且讓user可以有區間查詢, 區間修改的小東東</p></div>
</div>
<div class="sect3">
<h4 id="_template_class_operators_request_5">Template Class Operators Request</h4>
<table class="tableblock frame-all grid-rows"
style="
width:70%;
">
<col style="width:3%;">
<col style="width:3%;">
<col style="width:10%;">
<col style="width:17%;">
<col style="width:10%;">
<col style="width:53%;">
<thead>
<tr>
<th class="tableblock halign-right valign-top" >Const?</th>
<th class="tableblock halign-left valign-top" >Typename</th>
<th class="tableblock halign-left valign-top" > Operator </th>
<th class="tableblock halign-left valign-top" > Parameters </th>
<th class="tableblock halign-left valign-top" >Return_Type</th>
<th class="tableblock halign-left valign-top" > Description</th>
</tr>
</thead>
<tbody>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Value</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong>operator+</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(Value <span class="monospaced">v</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Value</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">相加(位移)</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Value</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong>operator*</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(size_t <span class="monospaced">n</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Value</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">每個Value都一樣,
長為 <span class="monospaced">n</span> 的區間的值</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Value</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong>operator|</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(Value <span class="monospaced">v</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Value</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">區間合併後的值</p></td>
</tr>
</tbody>
</table>
<div class="ulist"><ul>
<li>
<p>
若要維護區間最小值, 即每次都是詢問範圍 <span class="monospaced">[a, b]</span> 的最小值, 則可以定義
</p>
<div class="ulist"><ul>
<li>
<p>
<span class="monospaced">operator+</span> 為 <em>回傳相加值</em>
</p>
</li>
<li>
<p>
<span class="monospaced">operator*</span> 為 <em>回傳*this</em>
</p>
</li>
<li>
<p>
<span class="monospaced">operator|</span> 為 <em>回傳std::min(*this, v)</em>
</p>
</li>
</ul></div>
</li>
<li>
<p>
若要維護區間最總和, 即每次都是詢問範圍 <span class="monospaced">[a, b]</span> 的總和, 則可以定義
</p>
<div class="ulist"><ul>
<li>
<p>
<span class="monospaced">operator+</span> 為 <em>回傳相加值</em>
</p>
</li>
<li>
<p>
<span class="monospaced">operator*</span> 為 <em>回傳(*this) * n</em>
</p>
</li>
<li>
<p>
<span class="monospaced">operator|</span> 為 <em>回傳相加值</em>
</p>
</li>
</ul></div>
</li>
</ul></div>
</div>
<div class="sect3">
<h4 id="_support_methods_6">Support Methods</h4>
<div class="ulist"><ul>
<li>
<p>
N ← <span class="monospaced">this</span> 所維護的陣列長度
</p>
</li>
</ul></div>
<table class="tableblock frame-all grid-rows"
style="
width:100%;
">
<col style="width:2%;">
<col style="width:5%;">
<col style="width:19%;">
<col style="width:8%;">
<col style="width:8%;">
<col style="width:55%;">
<thead>
<tr>
<th class="tableblock halign-right valign-top" >Const?</th>
<th class="tableblock halign-right valign-top" >Name </th>
<th class="tableblock halign-left valign-top" > Parameters </th>
<th class="tableblock halign-left valign-top" > Return_Type</th>
<th class="tableblock halign-center valign-top" > Time_Complexity</th>
<th class="tableblock halign-left valign-top" > Description</th>
</tr>
</thead>
<tbody>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>reset</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(size_t <span class="monospaced">size</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(1)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">將資料清空且設定維護範圍是 <span class="monospaced">0~size - 1</span> 其中時間複雜度確切多少未知
要看 <span class="monospaced">std::vector::resize()</span> 的效率</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>query</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(ssize_t <span class="monospaced">first</span>,<br>
ssize_t <span class="monospaced">last</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Value</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">回傳區間 <span class="monospaced">[first,last]</span> (邊界都含) 的區間值</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>override</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(ssize_t <span class="monospaced">first</span>,<br>
ssize_t <span class="monospaced">last</span>,<br>
Value const& <span class="monospaced">value</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">將區間 <span class="monospaced">[first,last]</span> 全部都設定成 <span class="monospaced">value</span></p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>offset</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(ssize_t <span class="monospaced">first</span>,<br>
ssize_t <span class="monospaced">last</span>,<br>
Value const& <span class="monospaced">delta</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">將區間 <span class="monospaced">[first,last]</span> 全部都加上 <span class="monospaced">delta</span></p></td>
</tr>
</tbody>
</table>
<hr>
</div>
</div>
<div class="sect2">
<h3 id="_meow_strong_splaytree_range_lt_key_value_gt_strong_c_class">meow:: <strong>SplayTree_Range<Key, Value></strong> (C++ class)</h3>
<div class="sect3">
<h4 id="_description_10">Description</h4>
<div class="paragraph"><p><span class="monospaced">SplayTree_Range</span> 是一種神乎其技的資料結構, 維護一堆 Key→Value. 並且支援
一些 <span class="monospaced">std::map</span> 難以快速實踐的操作, 如 <span class="monospaced">split</span> , <span class="monospaced">merge</span> , <span class="monospaced">keyOffset</span></p></div>
</div>
<div class="sect3">
<h4 id="_template_class_operators_request_6">Template Class Operators Request</h4>
<table class="tableblock frame-all grid-rows"
style="
width:70%;
">
<col style="width:3%;">
<col style="width:3%;">
<col style="width:10%;">
<col style="width:17%;">
<col style="width:10%;">
<col style="width:53%;">
<thead>
<tr>
<th class="tableblock halign-right valign-top" >Const?</th>
<th class="tableblock halign-left valign-top" >Typename</th>
<th class="tableblock halign-left valign-top" > Operator</th>
<th class="tableblock halign-left valign-top" > Parameters </th>
<th class="tableblock halign-left valign-top" > Return_Type</th>
<th class="tableblock halign-left valign-top" > Description</th>
</tr>
</thead>
<tbody>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Key</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong>operator+</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(Key <span class="monospaced">k</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Key</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">相加</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Key</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong>operator<</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(Key <span class="monospaced">k</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">bool</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">大小比較</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Key</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong><em>Key</em></strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(int <span class="monospaced">n</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock"></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">建構子, <span class="monospaced">n</span> 永遠是0</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Value</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong><em>Value</em></strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">( )</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock"></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">建構子</p></td>
</tr>
</tbody>
</table>
</div>
<div class="sect3">
<h4 id="_custom_type_definitions_4">Custom Type Definitions</h4>
<div class="ulist"><ul>
<li>
<p>
<span class="monospaced">Element</span> → 用來當作回傳資料的媒介
</p>
<div class="ulist"><ul>
<li>
<p>
重定義 <span class="monospaced">operator->()</span> 到 <span class="monospaced">std::pair<Key const&, Value&>*</span>
</p>
</li>
<li>
<p>
重定義 <span class="monospaced">operator*()</span> 到 <span class="monospaced">std::pair<Key const&, Value&>&</span>
</p>
</li>
<li>
<p>
有 <span class="monospaced">operator==</span> , <span class="monospaced">operator!=</span>, <span class="monospaced">operator=</span> 可用
</p>
</li>
<li>
<p>
可以直接用 <span class="monospaced">(*e).second = some_value</span> 來改變SplayTree_Range中的資料
</p>
</li>
</ul></div>
</li>
</ul></div>
</div>
<div class="sect3">
<h4 id="_support_methods_7">Support Methods</h4>
<div class="ulist"><ul>
<li>
<p>
N ← <span class="monospaced">this</span> 中擁有的資料數
</p>
</li>
<li>
<p>
M ← <span class="monospaced">tree2</span> 中擁有的資料數
</p>
</li>
</ul></div>
<table class="tableblock frame-all grid-rows"
style="
width:100%;
">
<col style="width:2%;">
<col style="width:8%;">
<col style="width:18%;">
<col style="width:8%;">
<col style="width:8%;">
<col style="width:54%;">
<thead>
<tr>
<th class="tableblock halign-right valign-top" >Const?</th>
<th class="tableblock halign-right valign-top" >Name </th>
<th class="tableblock halign-left valign-top" > Parameters </th>
<th class="tableblock halign-left valign-top" > Return_Type</th>
<th class="tableblock halign-center valign-top" > Time_Complexity</th>
<th class="tableblock halign-left valign-top" > Description</th>
</tr>
</thead>
<tbody>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>moveTo</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(SplayTree_Range* <span class="monospaced">tree2</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(M)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">將 <span class="monospaced">this</span> 的資料複寫到 <span class="monospaced">tree2</span> 上面, 同時清空自己,
時間複雜度中的M是 <span class="monospaced">tree2</span> 所擁有的資料數</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>lowerBound</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(Key const& <span class="monospaced">k</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Element</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">找出第一個(最小的) Element且 <span class="monospaced">k</span> ⇐ 它的 Key, 並且回傳之.
找不到的話回傳 <span class="monospaced">this->end()</span></p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>lowerBound</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(Key const& <span class="monospaced">k</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Element</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">找出第一個(最小的) Element且 <span class="monospaced">k</span> < 它的 Key, 並且回傳之.
找不到的話回傳 <span class="monospaced">this->end()</span></p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>lowerBound</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(Key const& <span class="monospaced">k</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Element</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">找出第一個(最小的) Element且 <span class="monospaced">k</span> >= 它的 Key, 並且回傳之.
找不到的話回傳 <span class="monospaced">this->end()</span></p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>lowerBound</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(Key const& <span class="monospaced">k</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Element</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">找出第一個(最小的) Element且 <span class="monospaced">k</span> > 它的 Key, 並且回傳之.
找不到的話回傳 <span class="monospaced">this->end()</span></p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>find</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(Key const& <span class="monospaced">k</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Element</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">找出 Key= <span class="monospaced">k</span> 的Elemenet 並回傳. 找不到的話回傳 <span class="monospaced">this->end()</span></p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>query</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">()</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Value</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(1)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">回傳整棵樹的區間Value</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>query</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(Key const& <span class="monospaced">first</span> ,<br>
Key const& <span class="monospaced">last</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Value</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">找出key介於 <span class="monospaced">first</span> <br>
~ <span class="monospaced">last</span> 的區間Value</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>order</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(size_t <span class="monospaced">ord</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Element</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">將Elements依照Key由小到大排序, 回傳第 <span class="monospaced">ord</span> 個Element (由0算起).
其中如果 <span class="monospaced">ord</span> > N - 1, 則會回傳 <span class="monospaced">this->last()</span></p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>first</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(size_t <span class="monospaced">ord</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Element</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">回傳Key最小的Element, 如果SplayTree_Range為空, 則回傳 <span class="monospaced">this->end()</span></p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>last</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(size_t <span class="monospaced">ord</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Element</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">回傳Key最大的Element, 如果SplayTree_Range為空, 則回傳 <span class="monospaced">this->end()</span></p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>end</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">()</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Element</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(1)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">回傳一個指向NULL的Element, 以供 <span class="monospaced">find</span> , <span class="monospaced">order</span> , <span class="monospaced">first</span>
, <span class="monospaced">last</span> 等判斷是否有找到相對應的Element</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>size</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">()</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">size_t</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(1)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">回傳資料數</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>size</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">()</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">bool</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(1)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">回傳是否為空</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>clear</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">()</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(N)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">清空資料</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>insert</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(Key const& <span class="monospaced">key</span>,<br>
Value const& <span class="monospaced">value</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">bool</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">檢查是否已有Element的Key 為 <span class="monospaced">key</span>, 若有則回傳 <span class="monospaced">false</span> , 否則將
一個 (Key → Value) = (<span class="monospaced">key</span> → <span class="monospaced">value</span>)的Element加入, 並回傳 <span class="monospaced">true</span>
將所有Element的Key同加上 <span class="monospaced">delta</span></p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>erase</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(Key const& <span class="monospaced">key</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">bool</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">檢查是否已有Element的Key 為 <span class="monospaced">key</span>, 若有則刪除之, 並回傳 <span class="monospaced">true</span>,
否則則回傳 <span class="monospaced">false</span></p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>keyOffset</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(Key const& <span class="monospaced">delta</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(1)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">將所有Element的Key同加上 <span class="monospaced">delta</span></p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>valueOffset</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(Value const& <span class="monospaced">delta</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(1)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">將所有Element的value同加上 <span class="monospaced">delta</span></p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>valueOverride</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(Value const& <span class="monospaced">vaule</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(1)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">將所有Element的value同變成 <span class="monospaced">value</span></p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>operator[]</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(Key const& <span class="monospaced">key</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Value&</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">檢查是否已有Element的Key 為 <span class="monospaced">key</span>, 若有則回傳相對應的Value的Reference
否則先執行 <span class="monospaced">insert(key, Value())</span> 再回傳相對應的Reference</p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>splitOut</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(Key const& <span class="monospaced">upper_bound</span>,<br>
SplayTree_Range* <span class="monospaced">tree2</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN) + O(M)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">將 <span class="monospaced">tree2</span> 清空, 再將所有Key > <span class="monospaced">upper_bound</span> 的Element都丟到 <span class="monospaced">tree2</span></p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>mergeAfter</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(SplayTree_Range* <span class="monospaced">tree2</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN) + O(logM)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">檢查是否 <span class="monospaced">this</span> 中的 Key 都小於 <span class="monospaced">tree2</span> 中的Key, 是的話把 <span class="monospaced">tree2</span>
中的 Element 都搬到 <span class="monospaced">this</span> , 同時清空 <span class="monospaced">tree2</span> , 回傳 <span class="monospaced">true</span>. 否則
回傳 <span class="monospaced">false</span></p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>merge</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(SplayTree_Range* <span class="monospaced">tree2</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN) + O(logM)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">檢查是否 <span class="monospaced">this</span> 中的 Key 都小於 <span class="monospaced">tree2</span> 中的Key 或者
是否 <span class="monospaced">this</span> 中的 Key 都大於 <span class="monospaced">tree2</span> 中的Key, 是的話把 <span class="monospaced">tree2</span>
中的 Element 都搬到 <span class="monospaced">this</span> , 同時清空 <span class="monospaced">tree2</span> , 回傳 <span class="monospaced">true</span>. 否則
回傳 <span class="monospaced">false</span></p></td>
</tr>
</tbody>
</table>
<div class="admonitionblock">
<table><tr>
<td class="icon">
<div class="title">Note</div>
</td>
<td class="content">
<div class="ulist"><ul>
<li>
<p>
假設現在有兩個SplayTree_Range <span class="monospaced">A</span> 和 <span class="monospaced">B</span>, 則:
</p>
<div class="ulist"><ul>
<li>
<p>
執行 <span class="monospaced">B.moveTo(&A)</span> 後 <span class="monospaced">B</span> 會變成空的, <span class="monospaced">A</span> 原本擁有的資料也會覆蓋掉
</p>
</li>
<li>
<p>
執行 <span class="monospaced">A.merge(&B)</span> 或 <span class="monospaced">A.mergeAfter(&B)</span> 後
如果檢查發現確實可以merge, 則之後 <span class="monospaced">B</span> 會變成空的
</p>
</li>
</ul></div>
</li>
</ul></div>
</td>
</tr></table>
</div>
<hr>
</div>
</div>
<div class="sect2">
<h3 id="_meow_strong_binaryindextree_lt_value_gt_strong_c_class">meow:: <strong>BinaryIndexTree<Value></strong> (C++ class)</h3>
<div class="sect3">
<h4 id="_description_11">Description</h4>
<div class="paragraph"><p>極度簡化版的 <span class="monospaced">SegmentTree</span> 已無法區間操作, 區間詢問的區間開頭也一定要
在 <span class="monospaced">index=0</span> 的地方</p></div>
</div>
<div class="sect3">
<h4 id="_template_class_operators_request_7">Template Class Operators Request</h4>
<table class="tableblock frame-all grid-rows"
style="
width:70%;
">
<col style="width:3%;">
<col style="width:3%;">
<col style="width:10%;">
<col style="width:17%;">
<col style="width:10%;">
<col style="width:53%;">
<thead>
<tr>
<th class="tableblock halign-right valign-top" >Const?</th>
<th class="tableblock halign-left valign-top" >Typename</th>
<th class="tableblock halign-left valign-top" > Operator </th>
<th class="tableblock halign-left valign-top" > Parameters </th>
<th class="tableblock halign-left valign-top" > Return_Type</th>
<th class="tableblock halign-left valign-top" > Description</th>
</tr>
</thead>
<tbody>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Value</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong>operator+</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(Value <span class="monospaced">n</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Value</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">合併用(類似
<span class="monospaced">SegmentTree</span> 的
operator| )</p></td>
</tr>
</tbody>
</table>
</div>
<div class="sect3">
<h4 id="_support_methods_8">Support Methods</h4>
<div class="ulist"><ul>
<li>
<p>
N ← <span class="monospaced">this</span> 中擁有的資料數
</p>
</li>
</ul></div>
<table class="tableblock frame-all grid-rows"
style="
width:100%;
">
<col style="width:2%;">
<col style="width:8%;">
<col style="width:18%;">
<col style="width:8%;">
<col style="width:8%;">
<col style="width:54%;">
<thead>
<tr>
<th class="tableblock halign-right valign-top" >Const?</th>
<th class="tableblock halign-right valign-top" >Name </th>
<th class="tableblock halign-left valign-top" > Parameters </th>
<th class="tableblock halign-left valign-top" > Return_Type</th>
<th class="tableblock halign-center valign-top" > Time_Complexity</th>
<th class="tableblock halign-left valign-top" > Description</th>
</tr>
</thead>
<tbody>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>reset</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(size_t <span class="monospaced">size</span>, Value const& <span class="monospaced">value</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(<span class="monospaced">size</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">將資料長度刷成 <span class="monospaced">N = size</span> 且每一個元素都是 <span class="monospaced">value</span></p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>update</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(size_t <span class="monospaced">index</span>, Value const& <span class="monospaced">value</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">將第 <span class="monospaced">index</span> (從零開始算) 多加上 <span class="monospaced">value</span></p></td>
</tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>query</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(size_t <span class="monospaced">index</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">詢問 <span class="monospaced">0~index</span> 的區間值</p></td>
</tr>
</tbody>
</table>
<div class="admonitionblock">
<table><tr>
<td class="icon">
<div class="title">Note</div>
</td>
<td class="content">
<div class="ulist"><ul>
<li>
<p>
一般來說只能用在維護區間總和, 維護區間最大值只有在特殊情況才可以, 即
<em>針對每個元素, 每次 update() 的值一定會大於等於原本的值</em>
</p>
</li>
<li>
<p>
若要用區間最大值 , 則 <span class="monospaced">Value</span> 的 <span class="monospaced">operator+</span> 要寫成 <span class="monospaced">std::max(...)</span>
</p>
</li>
</ul></div>
</td>
</tr></table>
</div>
<hr>
</div>
</div>
</div>
</div>
<div class="sect1">
<h2 id="_test">Test</h2>
<div class="sectionbody">
<div class="sect2">
<h3 id="_acm_相關題目">ACM 相關題目</h3>
<table class="tableblock frame-all grid-rows"
style="
width:70%;
">
<col style="width:21%;">
<col style="width:21%;">
<col style="width:28%;">
<col style="width:7%;">
<col style="width:7%;">
<col style="width:14%;">
<thead>
<tr>
<th class="tableblock halign-left valign-top" > Name </th>
<th class="tableblock halign-left valign-top" > Problem </th>
<th class="tableblock halign-center valign-top" > Link </th>
<th class="tableblock halign-center valign-top" > Status </th>
<th class="tableblock halign-left valign-top" > Time </th>
<th class="tableblock halign-center valign-top" > source</th>
</tr>
</thead>
<tbody>
<tr>
<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong>KD_Tree</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock"><em>Retrenchment</em></p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock"><a href="http://acm.csie.org/ntujudge/problem.php?id=1971">NTU-OJ</a>
<a href="https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4052">ACM-ICPC Live</a></p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">Accept</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">0.083/0.083</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock monospaced"><a href="http://codepad.org/U85ruse5">codepad</a></p></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong>VP_Tree</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock"><em>Retrenchment</em></p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock"><a href="http://acm.csie.org/ntujudge/problem.php?id=1971">NTU-OJ</a>
<a href="https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4052">ACM-ICPC Live</a></p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">Accept</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">0.516/0.516</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock monospaced"><a href="http://codepad.org/03dW6ZHV">codepad</a></p></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong>SplayTree + SegmentTree</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock"><em>Shuffling_cards</em></p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock"><a href="http://acm.csie.org/ntujudge/problem.php?id=1353">NTU-OJ</a>
<a href="http://www.spoj.com/problems/SHUFFLEK/">SPOJ</a></p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">Accept/TLE</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">6.910/---</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock monospaced"><a href="http://codepad.org/yUeiVZc0">codepad</a></p></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong>SplayTree + BinaryIndexTree</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock"><em>Shuffling_cards</em></p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock"><a href="http://acm.csie.org/ntujudge/problem.php?id=1353">NTU-OJ</a>
<a href="http://www.spoj.com/problems/SHUFFLEK/">SPOJ</a></p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock">Accept/Accept</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">5.480/44.35</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock monospaced"><a href="http://codepad.org/GAWjEtmq">codepad</a></p></td>
</tr>
</tbody>
</table>
</div>
</div>
</div>
<div class="sect1">
<h2 id="_bug_report_contact">Bug Report / Contact</h2>
<div class="sectionbody">
<div class="ulist"><ul>
<li>
<p>
E-Mail: cat.hook31894 ~在~ gmail.com
</p>
</li>
</ul></div>
</div>
</div>
</div>
<div id="footnotes"><hr></div>
<div id="footer">
<div id="footer-text">
Last updated 2014-04-25 02:30:36 CST
</div>
</div>
</body>
</html>
