Mercurial > hg > Papers > 2024 > matac-master
changeset 46:9baf70df56fa
copy algo
| author | matac42 <matac@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Mon, 29 Jan 2024 13:41:22 +0900 |
| parents | f23602aa6fd8 |
| children | 49c1503c9176 |
| files | Paper/chapter/code.tex Paper/fig/copy_algo2.drawio Paper/fig/copy_algo3.drawio Paper/fig/copy_algo3.png Paper/fig/copy_algo4.drawio Paper/fig/copy_algo4.png Paper/fig/rbtree_def.drawio Paper/fig/rbtree_def.png Paper/master_paper.lol Paper/master_paper.pdf Paper/master_paper.tex Paper/src/CopyRedBlackTree.cbc Paper/src/CopyRedBlackTree.h Paper/src/TreeCopy.h TODO.md mindmaps/gears_fs_db.mm |
| diffstat | 16 files changed, 1344 insertions(+), 156 deletions(-) [+] |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/Paper/chapter/code.tex Mon Jan 29 13:41:22 2024 +0900 @@ -0,0 +1,4 @@ +\appendix +\chapter{CopyRedBlackTreeのソースコード} + +\lstinputlisting[label=src:CopyRedBlackTree.cbc, caption=CopyRedBlackTreeの実装]{src/CopyRedBlackTree.cbc}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/Paper/fig/copy_algo2.drawio Mon Jan 29 13:41:22 2024 +0900 @@ -0,0 +1,642 @@ +<mxfile host="65bd71144e"> + <diagram id="a_BoNS6LpnhUvPD0RD9g" name="Page-1"> + <mxGraphModel dx="1398" dy="1093" grid="1" gridSize="10" guides="1" tooltips="1" connect="1" arrows="1" fold="1" page="1" pageScale="1" pageWidth="827" pageHeight="1169" math="0" shadow="0"> + <root> + <mxCell id="0"/> + <mxCell id="1" parent="0"/> + <mxCell id="206" value="" style="rounded=0;whiteSpace=wrap;html=1;fillColor=none;strokeWidth=2;" vertex="1" parent="1"> + <mxGeometry x="620" y="1717.5" width="240" height="352.5" as="geometry"/> + </mxCell> + <mxCell id="195" value="" style="rounded=0;whiteSpace=wrap;html=1;fillColor=none;strokeWidth=2;" vertex="1" parent="1"> + <mxGeometry x="360" y="1717.5" width="220" height="322.5" as="geometry"/> + </mxCell> + <mxCell id="191" value="" style="rounded=0;whiteSpace=wrap;html=1;fillColor=none;strokeWidth=2;strokeColor=#000000;" vertex="1" parent="1"> + <mxGeometry x="90" y="1717.5" width="230" height="280" as="geometry"/> + </mxCell> + <mxCell id="5" style="edgeStyle=none;html=1;" edge="1" parent="1" source="2" target="4"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="2" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" vertex="1" parent="1"> + <mxGeometry x="70" y="270" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="3" value="Start" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1"> + <mxGeometry x="50" y="240" width="60" height="30" as="geometry"/> + </mxCell> + <mxCell id="7" value="" style="edgeStyle=none;html=1;" edge="1" parent="1" source="4" target="6"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="4" value="leftDown" style="rounded=0;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="140" y="250" width="120" height="60" as="geometry"/> + </mxCell> + <mxCell id="9" style="edgeStyle=orthogonalEdgeStyle;html=1;exitX=0;exitY=0.5;exitDx=0;exitDy=0;entryX=0;entryY=0.75;entryDx=0;entryDy=0;" edge="1" parent="1" source="6" target="4"> + <mxGeometry relative="1" as="geometry"> + <Array as="points"> + <mxPoint x="120" y="385"/> + <mxPoint x="120" y="295"/> + </Array> + </mxGeometry> + </mxCell> + <mxCell id="10" value="Yes" style="edgeLabel;html=1;align=center;verticalAlign=middle;resizable=0;points=[];" vertex="1" connectable="0" parent="9"> + <mxGeometry x="0.0215" y="-1" relative="1" as="geometry"> + <mxPoint as="offset"/> + </mxGeometry> + </mxCell> + <mxCell id="13" style="edgeStyle=orthogonalEdgeStyle;html=1;exitX=1;exitY=0.5;exitDx=0;exitDy=0;entryX=0;entryY=0.5;entryDx=0;entryDy=0;" edge="1" parent="1" source="6" target="12"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="14" value="No" style="edgeLabel;html=1;align=center;verticalAlign=middle;resizable=0;points=[];" vertex="1" connectable="0" parent="13"> + <mxGeometry x="-0.2571" y="-2" relative="1" as="geometry"> + <mxPoint as="offset"/> + </mxGeometry> + </mxCell> + <mxCell id="6" value="left exist?" style="ellipse;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="140" y="360" width="120" height="50" as="geometry"/> + </mxCell> + <mxCell id="16" value="No" style="edgeStyle=orthogonalEdgeStyle;html=1;exitX=1;exitY=0.5;exitDx=0;exitDy=0;" edge="1" parent="1" source="12" target="15"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="18" value="Yes" style="edgeStyle=orthogonalEdgeStyle;html=1;exitX=0.5;exitY=0;exitDx=0;exitDy=0;entryX=0.5;entryY=1;entryDx=0;entryDy=0;" edge="1" parent="1" source="12" target="17"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="12" value="right exist?" style="ellipse;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="330" y="360" width="120" height="50" as="geometry"/> + </mxCell> + <mxCell id="22" style="edgeStyle=orthogonalEdgeStyle;html=1;exitX=0.5;exitY=1;exitDx=0;exitDy=0;entryX=0.5;entryY=0;entryDx=0;entryDy=0;" edge="1" parent="1" source="15" target="21"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="15" value="up" style="rounded=0;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="533" y="355" width="120" height="60" as="geometry"/> + </mxCell> + <mxCell id="19" style="edgeStyle=orthogonalEdgeStyle;html=1;exitX=0;exitY=0.5;exitDx=0;exitDy=0;entryX=1;entryY=0.5;entryDx=0;entryDy=0;" edge="1" parent="1" source="17" target="4"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="17" value="rightDown" style="rounded=0;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="330" y="250" width="120" height="60" as="geometry"/> + </mxCell> + <mxCell id="27" style="edgeStyle=orthogonalEdgeStyle;html=1;entryX=0.5;entryY=1;entryDx=0;entryDy=0;" edge="1" parent="1" source="21" target="12"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="28" value="No" style="edgeLabel;html=1;align=center;verticalAlign=middle;resizable=0;points=[];" vertex="1" connectable="0" parent="27"> + <mxGeometry x="-0.2087" y="-4" relative="1" as="geometry"> + <mxPoint as="offset"/> + </mxGeometry> + </mxCell> + <mxCell id="32" style="edgeStyle=orthogonalEdgeStyle;html=1;exitX=0.5;exitY=1;exitDx=0;exitDy=0;entryX=0.5;entryY=0;entryDx=0;entryDy=0;" edge="1" parent="1" source="21" target="30"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="33" value="Yes" style="edgeLabel;html=1;align=center;verticalAlign=middle;resizable=0;points=[];" vertex="1" connectable="0" parent="32"> + <mxGeometry x="-0.37" y="-4" relative="1" as="geometry"> + <mxPoint as="offset"/> + </mxGeometry> + </mxCell> + <mxCell id="21" value="right copied?" style="ellipse;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="533" y="450" width="120" height="50" as="geometry"/> + </mxCell> + <mxCell id="35" style="edgeStyle=orthogonalEdgeStyle;html=1;entryX=1;entryY=0.5;entryDx=0;entryDy=0;" edge="1" parent="1" source="30" target="15"> + <mxGeometry relative="1" as="geometry"> + <Array as="points"> + <mxPoint x="703" y="565"/> + <mxPoint x="703" y="385"/> + </Array> + </mxGeometry> + </mxCell> + <mxCell id="37" value="No" style="edgeLabel;html=1;align=center;verticalAlign=middle;resizable=0;points=[];" vertex="1" connectable="0" parent="35"> + <mxGeometry x="-0.83" y="2" relative="1" as="geometry"> + <mxPoint as="offset"/> + </mxGeometry> + </mxCell> + <mxCell id="39" style="edgeStyle=orthogonalEdgeStyle;html=1;exitX=0.5;exitY=1;exitDx=0;exitDy=0;entryX=0.5;entryY=0;entryDx=0;entryDy=0;" edge="1" parent="1" source="30" target="38"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="40" value="Yes" style="edgeLabel;html=1;align=center;verticalAlign=middle;resizable=0;points=[];" vertex="1" connectable="0" parent="39"> + <mxGeometry x="-0.17" y="-4" relative="1" as="geometry"> + <mxPoint as="offset"/> + </mxGeometry> + </mxCell> + <mxCell id="30" value="root?" style="ellipse;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="533" y="540" width="120" height="50" as="geometry"/> + </mxCell> + <mxCell id="42" style="edgeStyle=orthogonalEdgeStyle;html=1;exitX=0.5;exitY=1;exitDx=0;exitDy=0;entryX=0.5;entryY=0;entryDx=0;entryDy=0;" edge="1" parent="1" source="38" target="41"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="43" value="Yes" style="edgeLabel;html=1;align=center;verticalAlign=middle;resizable=0;points=[];" vertex="1" connectable="0" parent="42"> + <mxGeometry x="-0.16" y="1" relative="1" as="geometry"> + <mxPoint as="offset"/> + </mxGeometry> + </mxCell> + <mxCell id="44" style="edgeStyle=orthogonalEdgeStyle;html=1;entryX=0.5;entryY=1;entryDx=0;entryDy=0;" edge="1" parent="1" source="38" target="12"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="46" value="No" style="edgeLabel;html=1;align=center;verticalAlign=middle;resizable=0;points=[];" vertex="1" connectable="0" parent="44"> + <mxGeometry x="-0.9277" y="-4" relative="1" as="geometry"> + <mxPoint as="offset"/> + </mxGeometry> + </mxCell> + <mxCell id="38" value="copied?" style="ellipse;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="533" y="630" width="120" height="50" as="geometry"/> + </mxCell> + <mxCell id="41" value="swap" style="rounded=0;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="533" y="720" width="120" height="60" as="geometry"/> + </mxCell> + <mxCell id="87" style="edgeStyle=orthogonalEdgeStyle;html=1;entryX=0;entryY=0.5;entryDx=0;entryDy=0;" edge="1" parent="1" source="48" target="51"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="48" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" vertex="1" parent="1"> + <mxGeometry x="910" y="445" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="49" value="Start" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1"> + <mxGeometry x="890" y="415" width="60" height="30" as="geometry"/> + </mxCell> + <mxCell id="50" value="" style="edgeStyle=none;html=1;" edge="1" parent="1" source="51" target="56"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="51" value="leftDown" style="rounded=0;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="1010" y="425" width="120" height="60" as="geometry"/> + </mxCell> + <mxCell id="85" style="edgeStyle=orthogonalEdgeStyle;html=1;exitX=0;exitY=0.5;exitDx=0;exitDy=0;entryX=0;entryY=0.5;entryDx=0;entryDy=0;" edge="1" parent="1" source="56" target="51"> + <mxGeometry relative="1" as="geometry"> + <Array as="points"> + <mxPoint x="970" y="625"/> + <mxPoint x="970" y="455"/> + </Array> + </mxGeometry> + </mxCell> + <mxCell id="86" value="Yes" style="edgeLabel;html=1;align=center;verticalAlign=middle;resizable=0;points=[];" vertex="1" connectable="0" parent="85"> + <mxGeometry x="-0.7453" relative="1" as="geometry"> + <mxPoint x="12" as="offset"/> + </mxGeometry> + </mxCell> + <mxCell id="91" style="edgeStyle=orthogonalEdgeStyle;html=1;" edge="1" parent="1" source="56" target="59"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="92" value="No" style="edgeLabel;html=1;align=center;verticalAlign=middle;resizable=0;points=[];" vertex="1" connectable="0" parent="91"> + <mxGeometry x="-0.9095" y="1" relative="1" as="geometry"> + <mxPoint as="offset"/> + </mxGeometry> + </mxCell> + <mxCell id="56" value="left exist?" style="ellipse;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="1010" y="600" width="120" height="50" as="geometry"/> + </mxCell> + <mxCell id="96" style="edgeStyle=orthogonalEdgeStyle;html=1;entryX=1;entryY=0.5;entryDx=0;entryDy=0;" edge="1" parent="1" source="59" target="63"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="98" value="Yes" style="edgeLabel;html=1;align=center;verticalAlign=middle;resizable=0;points=[];" vertex="1" connectable="0" parent="96"> + <mxGeometry x="-0.2757" y="-2" relative="1" as="geometry"> + <mxPoint x="1" as="offset"/> + </mxGeometry> + </mxCell> + <mxCell id="97" style="edgeStyle=orthogonalEdgeStyle;html=1;" edge="1" parent="1" source="59" target="61"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="99" value="No" style="edgeLabel;html=1;align=center;verticalAlign=middle;resizable=0;points=[];" vertex="1" connectable="0" parent="97"> + <mxGeometry x="-0.5619" relative="1" as="geometry"> + <mxPoint x="1" as="offset"/> + </mxGeometry> + </mxCell> + <mxCell id="59" value="right exist?" style="ellipse;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="1200" y="285" width="120" height="50" as="geometry"/> + </mxCell> + <mxCell id="60" style="edgeStyle=orthogonalEdgeStyle;html=1;exitX=0.5;exitY=1;exitDx=0;exitDy=0;entryX=0.5;entryY=0;entryDx=0;entryDy=0;" edge="1" parent="1" source="61" target="68"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="61" value="up" style="rounded=0;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="1403" y="280" width="120" height="60" as="geometry"/> + </mxCell> + <mxCell id="82" style="edgeStyle=orthogonalEdgeStyle;html=1;" edge="1" parent="1" source="63" target="51"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="63" value="rightDown" style="rounded=0;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="1010" y="280" width="120" height="60" as="geometry"/> + </mxCell> + <mxCell id="64" style="edgeStyle=orthogonalEdgeStyle;html=1;entryX=0.5;entryY=1;entryDx=0;entryDy=0;" edge="1" parent="1" source="68" target="59"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="65" value="No" style="edgeLabel;html=1;align=center;verticalAlign=middle;resizable=0;points=[];" vertex="1" connectable="0" parent="64"> + <mxGeometry x="-0.2087" y="-4" relative="1" as="geometry"> + <mxPoint as="offset"/> + </mxGeometry> + </mxCell> + <mxCell id="66" style="edgeStyle=orthogonalEdgeStyle;html=1;exitX=0.5;exitY=1;exitDx=0;exitDy=0;entryX=0.5;entryY=0;entryDx=0;entryDy=0;" edge="1" parent="1" source="68" target="73"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="67" value="Yes" style="edgeLabel;html=1;align=center;verticalAlign=middle;resizable=0;points=[];" vertex="1" connectable="0" parent="66"> + <mxGeometry x="-0.37" y="-4" relative="1" as="geometry"> + <mxPoint as="offset"/> + </mxGeometry> + </mxCell> + <mxCell id="68" value="right copied?" style="ellipse;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="1403" y="430" width="120" height="50" as="geometry"/> + </mxCell> + <mxCell id="71" style="edgeStyle=orthogonalEdgeStyle;html=1;exitX=0.5;exitY=1;exitDx=0;exitDy=0;entryX=0.5;entryY=0;entryDx=0;entryDy=0;" edge="1" parent="1" source="73" target="78"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="72" value="Yes" style="edgeLabel;html=1;align=center;verticalAlign=middle;resizable=0;points=[];" vertex="1" connectable="0" parent="71"> + <mxGeometry x="-0.17" y="-4" relative="1" as="geometry"> + <mxPoint as="offset"/> + </mxGeometry> + </mxCell> + <mxCell id="89" style="edgeStyle=orthogonalEdgeStyle;html=1;exitX=1;exitY=0.5;exitDx=0;exitDy=0;entryX=1;entryY=0.5;entryDx=0;entryDy=0;" edge="1" parent="1" source="73" target="61"> + <mxGeometry relative="1" as="geometry"> + <Array as="points"> + <mxPoint x="1580" y="535"/> + <mxPoint x="1580" y="310"/> + </Array> + </mxGeometry> + </mxCell> + <mxCell id="90" value="No" style="edgeLabel;html=1;align=center;verticalAlign=middle;resizable=0;points=[];" vertex="1" connectable="0" parent="89"> + <mxGeometry x="-0.9057" y="3" relative="1" as="geometry"> + <mxPoint as="offset"/> + </mxGeometry> + </mxCell> + <mxCell id="73" value="root?" style="ellipse;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="1403" y="510" width="120" height="50" as="geometry"/> + </mxCell> + <mxCell id="74" style="edgeStyle=orthogonalEdgeStyle;html=1;exitX=0.5;exitY=1;exitDx=0;exitDy=0;entryX=0.5;entryY=0;entryDx=0;entryDy=0;" edge="1" parent="1" source="78" target="79"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="75" value="Yes" style="edgeLabel;html=1;align=center;verticalAlign=middle;resizable=0;points=[];" vertex="1" connectable="0" parent="74"> + <mxGeometry x="-0.16" y="1" relative="1" as="geometry"> + <mxPoint as="offset"/> + </mxGeometry> + </mxCell> + <mxCell id="76" style="edgeStyle=orthogonalEdgeStyle;html=1;entryX=0.5;entryY=1;entryDx=0;entryDy=0;" edge="1" parent="1" source="78" target="59"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="77" value="No" style="edgeLabel;html=1;align=center;verticalAlign=middle;resizable=0;points=[];" vertex="1" connectable="0" parent="76"> + <mxGeometry x="-0.9277" y="-4" relative="1" as="geometry"> + <mxPoint as="offset"/> + </mxGeometry> + </mxCell> + <mxCell id="78" value="copied?" style="ellipse;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="1403" y="600" width="120" height="50" as="geometry"/> + </mxCell> + <mxCell id="95" style="edgeStyle=orthogonalEdgeStyle;html=1;exitX=0.5;exitY=1;exitDx=0;exitDy=0;entryX=0.85;entryY=0.5;entryDx=0;entryDy=0;entryPerimeter=0;" edge="1" parent="1" source="79" target="93"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="79" value="swap" style="rounded=0;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="1403" y="710" width="120" height="60" as="geometry"/> + </mxCell> + <mxCell id="93" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" vertex="1" parent="1"> + <mxGeometry x="1453" y="810" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="94" value="End" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1"> + <mxGeometry x="1433" y="830" width="60" height="30" as="geometry"/> + </mxCell> + <mxCell id="135" style="edgeStyle=orthogonalEdgeStyle;html=1;exitX=1;exitY=0.5;exitDx=0;exitDy=0;entryX=0;entryY=0.5;entryDx=0;entryDy=0;" edge="1" parent="1" source="133" target="134"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="136" value="Yes" style="edgeLabel;html=1;align=center;verticalAlign=middle;resizable=0;points=[];" vertex="1" connectable="0" parent="135"> + <mxGeometry x="-0.5665" relative="1" as="geometry"> + <mxPoint as="offset"/> + </mxGeometry> + </mxCell> + <mxCell id="142" style="edgeStyle=orthogonalEdgeStyle;html=1;exitX=0.5;exitY=0;exitDx=0;exitDy=0;entryX=0.5;entryY=1;entryDx=0;entryDy=0;" edge="1" parent="1" source="133" target="141"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="143" value="No" style="edgeLabel;html=1;align=center;verticalAlign=middle;resizable=0;points=[];" vertex="1" connectable="0" parent="142"> + <mxGeometry x="0.2567" y="-2" relative="1" as="geometry"> + <mxPoint as="offset"/> + </mxGeometry> + </mxCell> + <mxCell id="133" value="left exist?" style="ellipse;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="921" y="1247.5" width="120" height="50" as="geometry"/> + </mxCell> + <mxCell id="137" style="edgeStyle=orthogonalEdgeStyle;html=1;exitX=0.5;exitY=1;exitDx=0;exitDy=0;entryX=0.5;entryY=1;entryDx=0;entryDy=0;" edge="1" parent="1" source="134" target="133"> + <mxGeometry relative="1" as="geometry"> + <Array as="points"> + <mxPoint x="1161" y="1337.5"/> + <mxPoint x="981" y="1337.5"/> + </Array> + </mxGeometry> + </mxCell> + <mxCell id="134" value="leftDown" style="rounded=0;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="1101" y="1242.5" width="120" height="60" as="geometry"/> + </mxCell> + <mxCell id="145" style="edgeStyle=orthogonalEdgeStyle;html=1;exitX=1;exitY=0.5;exitDx=0;exitDy=0;" edge="1" parent="1" source="141" target="144"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="146" value="Yes" style="edgeLabel;html=1;align=center;verticalAlign=middle;resizable=0;points=[];" vertex="1" connectable="0" parent="145"> + <mxGeometry x="-0.7176" y="2" relative="1" as="geometry"> + <mxPoint as="offset"/> + </mxGeometry> + </mxCell> + <mxCell id="150" style="edgeStyle=orthogonalEdgeStyle;html=1;exitX=0.5;exitY=0;exitDx=0;exitDy=0;entryX=0;entryY=0.5;entryDx=0;entryDy=0;" edge="1" parent="1" source="141" target="149"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="151" value="No" style="edgeLabel;html=1;align=center;verticalAlign=middle;resizable=0;points=[];" vertex="1" connectable="0" parent="150"> + <mxGeometry x="-0.8182" y="3" relative="1" as="geometry"> + <mxPoint as="offset"/> + </mxGeometry> + </mxCell> + <mxCell id="141" value="right exist?" style="ellipse;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="921" y="1157.5" width="120" height="50" as="geometry"/> + </mxCell> + <mxCell id="147" style="edgeStyle=orthogonalEdgeStyle;html=1;exitX=1;exitY=0.5;exitDx=0;exitDy=0;entryX=0.5;entryY=1;entryDx=0;entryDy=0;" edge="1" parent="1" source="144" target="133"> + <mxGeometry relative="1" as="geometry"> + <Array as="points"> + <mxPoint x="1241" y="1182.5"/> + <mxPoint x="1241" y="1337.5"/> + <mxPoint x="981" y="1337.5"/> + </Array> + </mxGeometry> + </mxCell> + <mxCell id="144" value="rightDown" style="rounded=0;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="1101" y="1152.5" width="120" height="60" as="geometry"/> + </mxCell> + <mxCell id="153" style="edgeStyle=orthogonalEdgeStyle;html=1;exitX=1;exitY=0.5;exitDx=0;exitDy=0;entryX=0;entryY=0.5;entryDx=0;entryDy=0;" edge="1" parent="1" source="149" target="152"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="149" value="up" style="rounded=0;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="1100" y="1020" width="120" height="60" as="geometry"/> + </mxCell> + <mxCell id="155" style="edgeStyle=orthogonalEdgeStyle;html=1;entryX=0.742;entryY=0.25;entryDx=0;entryDy=0;entryPerimeter=0;" edge="1" parent="1" source="152" target="141"> + <mxGeometry relative="1" as="geometry"> + <Array as="points"> + <mxPoint x="1343" y="1120"/> + <mxPoint x="1010" y="1120"/> + </Array> + </mxGeometry> + </mxCell> + <mxCell id="156" value="No" style="edgeLabel;html=1;align=center;verticalAlign=middle;resizable=0;points=[];" vertex="1" connectable="0" parent="155"> + <mxGeometry x="-0.8984" y="4" relative="1" as="geometry"> + <mxPoint x="-4" y="1" as="offset"/> + </mxGeometry> + </mxCell> + <mxCell id="158" value="Yes" style="edgeStyle=orthogonalEdgeStyle;html=1;exitX=1;exitY=0.5;exitDx=0;exitDy=0;entryX=0;entryY=0.5;entryDx=0;entryDy=0;" edge="1" parent="1" source="152" target="157"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="152" value="right copied?" style="ellipse;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="1283" y="1025" width="120" height="50" as="geometry"/> + </mxCell> + <mxCell id="159" style="edgeStyle=orthogonalEdgeStyle;html=1;exitX=1;exitY=0.5;exitDx=0;exitDy=0;entryX=0.5;entryY=0;entryDx=0;entryDy=0;" edge="1" parent="1" source="157" target="149"> + <mxGeometry relative="1" as="geometry"> + <Array as="points"> + <mxPoint x="1610" y="1050"/> + <mxPoint x="1610" y="1010"/> + <mxPoint x="1160" y="1010"/> + </Array> + </mxGeometry> + </mxCell> + <mxCell id="160" value="No" style="edgeLabel;html=1;align=center;verticalAlign=middle;resizable=0;points=[];" vertex="1" connectable="0" parent="159"> + <mxGeometry x="-0.9611" relative="1" as="geometry"> + <mxPoint as="offset"/> + </mxGeometry> + </mxCell> + <mxCell id="162" style="edgeStyle=orthogonalEdgeStyle;html=1;" edge="1" parent="1" source="157" target="161"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="163" value="Yes" style="edgeLabel;html=1;align=center;verticalAlign=middle;resizable=0;points=[];" vertex="1" connectable="0" parent="162"> + <mxGeometry x="-0.7904" y="1" relative="1" as="geometry"> + <mxPoint as="offset"/> + </mxGeometry> + </mxCell> + <mxCell id="157" value="root?" style="ellipse;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="1453" y="1025" width="120" height="50" as="geometry"/> + </mxCell> + <mxCell id="164" style="edgeStyle=orthogonalEdgeStyle;html=1;" edge="1" parent="1" source="161"> + <mxGeometry relative="1" as="geometry"> + <mxPoint x="1010" y="1150" as="targetPoint"/> + <Array as="points"> + <mxPoint x="1340" y="1183"/> + <mxPoint x="1340" y="1120"/> + <mxPoint x="1010" y="1120"/> + </Array> + </mxGeometry> + </mxCell> + <mxCell id="165" value="No" style="edgeLabel;html=1;align=center;verticalAlign=middle;resizable=0;points=[];" vertex="1" connectable="0" parent="164"> + <mxGeometry x="-0.9312" y="-2" relative="1" as="geometry"> + <mxPoint x="-1" as="offset"/> + </mxGeometry> + </mxCell> + <mxCell id="167" style="edgeStyle=orthogonalEdgeStyle;html=1;exitX=0.5;exitY=1;exitDx=0;exitDy=0;entryX=0.5;entryY=0;entryDx=0;entryDy=0;" edge="1" parent="1" source="161" target="166"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="168" value="Yes" style="edgeLabel;html=1;align=center;verticalAlign=middle;resizable=0;points=[];" vertex="1" connectable="0" parent="167"> + <mxGeometry x="-0.3699" y="2" relative="1" as="geometry"> + <mxPoint as="offset"/> + </mxGeometry> + </mxCell> + <mxCell id="161" value="copied?" style="ellipse;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="1453" y="1157.5" width="120" height="50" as="geometry"/> + </mxCell> + <mxCell id="174" style="edgeStyle=orthogonalEdgeStyle;html=1;exitX=0.5;exitY=1;exitDx=0;exitDy=0;" edge="1" parent="1" source="166" target="172"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="166" value="swap" style="rounded=0;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="1453" y="1242.5" width="120" height="60" as="geometry"/> + </mxCell> + <mxCell id="171" style="edgeStyle=orthogonalEdgeStyle;html=1;" edge="1" parent="1" source="169" target="133"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="169" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" vertex="1" parent="1"> + <mxGeometry x="870" y="1262.5" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="170" value="Start" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1"> + <mxGeometry x="850" y="1230" width="60" height="30" as="geometry"/> + </mxCell> + <mxCell id="172" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" vertex="1" parent="1"> + <mxGeometry x="1503" y="1360" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="173" value="End" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1"> + <mxGeometry x="1483" y="1380" width="60" height="30" as="geometry"/> + </mxCell> + <mxCell id="175" value="leftDown" style="rounded=0;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="150" y="1757.5" width="120" height="60" as="geometry"/> + </mxCell> + <mxCell id="198" style="edgeStyle=orthogonalEdgeStyle;html=1;exitX=0;exitY=0.5;exitDx=0;exitDy=0;entryX=1;entryY=0.25;entryDx=0;entryDy=0;startArrow=none;startFill=0;endArrow=classic;endFill=1;" edge="1" parent="1" source="176" target="191"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="176" value="rightDown" style="rounded=0;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="414" y="1757.5" width="120" height="60" as="geometry"/> + </mxCell> + <mxCell id="213" style="edgeStyle=orthogonalEdgeStyle;html=1;exitX=0.5;exitY=1;exitDx=0;exitDy=0;entryX=0.5;entryY=0;entryDx=0;entryDy=0;startArrow=none;startFill=0;endArrow=classic;endFill=1;" edge="1" parent="1" source="177" target="212"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="177" value="up" style="rounded=0;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="680" y="1757.5" width="120" height="60" as="geometry"/> + </mxCell> + <mxCell id="184" style="edgeStyle=orthogonalEdgeStyle;html=1;exitX=0;exitY=0;exitDx=0;exitDy=0;entryX=0.145;entryY=1;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;startArrow=classic;startFill=1;" edge="1" parent="1" source="178" target="175"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="186" style="edgeStyle=orthogonalEdgeStyle;html=1;exitX=1;exitY=0;exitDx=0;exitDy=0;entryX=0.854;entryY=0.977;entryDx=0;entryDy=0;entryPerimeter=0;startArrow=none;startFill=0;endArrow=classic;endFill=1;" edge="1" parent="1" source="178" target="175"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="238" value="Yes" style="edgeLabel;html=1;align=center;verticalAlign=middle;resizable=0;points=[];fontColor=#000000;" vertex="1" connectable="0" parent="186"> + <mxGeometry x="-0.7643" relative="1" as="geometry"> + <mxPoint as="offset"/> + </mxGeometry> + </mxCell> + <mxCell id="229" style="edgeStyle=orthogonalEdgeStyle;html=1;startArrow=none;startFill=0;endArrow=classic;endFill=1;entryX=-0.002;entryY=0.698;entryDx=0;entryDy=0;entryPerimeter=0;" edge="1" parent="1" source="178" target="195"> + <mxGeometry relative="1" as="geometry"> + <Array as="points"/> + </mxGeometry> + </mxCell> + <mxCell id="230" value="No" style="edgeLabel;html=1;align=center;verticalAlign=middle;resizable=0;points=[];" vertex="1" connectable="0" parent="229"> + <mxGeometry x="-0.8407" relative="1" as="geometry"> + <mxPoint as="offset"/> + </mxGeometry> + </mxCell> + <mxCell id="178" value="left exist?" style="ellipse;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="150" y="1917.5" width="120" height="50" as="geometry"/> + </mxCell> + <mxCell id="187" style="edgeStyle=orthogonalEdgeStyle;html=1;entryX=0;entryY=0.5;entryDx=0;entryDy=0;startArrow=none;startFill=0;endArrow=classic;endFill=1;" edge="1" parent="1" source="181" target="178"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="181" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;strokeColor=#FF8000;" vertex="1" parent="1"> + <mxGeometry x="100" y="1932.5" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="182" value="Start" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;fontColor=#FF8000;" vertex="1" parent="1"> + <mxGeometry x="80" y="1902.5" width="60" height="30" as="geometry"/> + </mxCell> + <mxCell id="196" style="edgeStyle=orthogonalEdgeStyle;html=1;startArrow=none;startFill=0;endArrow=classic;endFill=1;" edge="1" parent="1" source="188" target="176"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="197" value="Yes" style="edgeLabel;html=1;align=center;verticalAlign=middle;resizable=0;points=[];" vertex="1" connectable="0" parent="196"> + <mxGeometry x="-0.6463" y="1" relative="1" as="geometry"> + <mxPoint as="offset"/> + </mxGeometry> + </mxCell> + <mxCell id="223" style="edgeStyle=orthogonalEdgeStyle;html=1;entryX=0.003;entryY=0.64;entryDx=0;entryDy=0;entryPerimeter=0;startArrow=none;startFill=0;endArrow=classic;endFill=1;" edge="1" parent="1" source="188" target="206"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="224" value="No" style="edgeLabel;html=1;align=center;verticalAlign=middle;resizable=0;points=[];" vertex="1" connectable="0" parent="223"> + <mxGeometry x="-0.7763" y="-1" relative="1" as="geometry"> + <mxPoint as="offset"/> + </mxGeometry> + </mxCell> + <mxCell id="188" value="right exist?" style="ellipse;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="414" y="1917.5" width="120" height="50" as="geometry"/> + </mxCell> + <mxCell id="199" style="edgeStyle=orthogonalEdgeStyle;html=1;entryX=0;entryY=0.25;entryDx=0;entryDy=0;startArrow=none;startFill=0;endArrow=classic;endFill=1;" edge="1" parent="1" source="192" target="191"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="192" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;fontColor=#007FFF;strokeColor=#007FFF;" vertex="1" parent="1"> + <mxGeometry x="20" y="1777.5" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="193" value="Start" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;fontColor=#007FFF;" vertex="1" parent="1"> + <mxGeometry y="1752.5" width="60" height="30" as="geometry"/> + </mxCell> + <mxCell id="200" value="leftDown" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1"> + <mxGeometry x="170" y="1680" width="60" height="30" as="geometry"/> + </mxCell> + <mxCell id="205" style="edgeStyle=orthogonalEdgeStyle;html=1;startArrow=none;startFill=0;endArrow=classic;endFill=1;" edge="1" parent="1" source="203" target="188"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="203" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;strokeColor=#FF8000;" vertex="1" parent="1"> + <mxGeometry x="370" y="1932.5" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="204" value="Start" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;fontColor=#FF8000;" vertex="1" parent="1"> + <mxGeometry x="350" y="1907.5" width="60" height="30" as="geometry"/> + </mxCell> + <mxCell id="211" style="edgeStyle=orthogonalEdgeStyle;html=1;entryX=0;entryY=0.5;entryDx=0;entryDy=0;startArrow=none;startFill=0;endArrow=classic;endFill=1;exitX=0.589;exitY=0.988;exitDx=0;exitDy=0;exitPerimeter=0;" edge="1" parent="1" source="209" target="177"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="209" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;strokeColor=#FF8000;" vertex="1" parent="1"> + <mxGeometry x="630" y="1777.5" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="210" value="Start" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;fontColor=#FF8000;" vertex="1" parent="1"> + <mxGeometry x="610" y="1752.5" width="60" height="30" as="geometry"/> + </mxCell> + <mxCell id="216" style="edgeStyle=orthogonalEdgeStyle;html=1;entryX=0.5;entryY=0;entryDx=0;entryDy=0;startArrow=none;startFill=0;endArrow=classic;endFill=1;" edge="1" parent="1" source="212" target="215"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="217" value="Yes" style="edgeLabel;html=1;align=center;verticalAlign=middle;resizable=0;points=[];" vertex="1" connectable="0" parent="216"> + <mxGeometry x="-0.3697" y="-4" relative="1" as="geometry"> + <mxPoint x="4" y="4" as="offset"/> + </mxGeometry> + </mxCell> + <mxCell id="218" style="edgeStyle=orthogonalEdgeStyle;html=1;startArrow=none;startFill=0;endArrow=classic;endFill=1;" edge="1" parent="1" source="212"> + <mxGeometry relative="1" as="geometry"> + <mxPoint x="580" y="1865" as="targetPoint"/> + </mxGeometry> + </mxCell> + <mxCell id="237" value="No" style="edgeLabel;html=1;align=center;verticalAlign=middle;resizable=0;points=[];fontColor=#000000;" vertex="1" connectable="0" parent="218"> + <mxGeometry x="-0.7491" y="-2" relative="1" as="geometry"> + <mxPoint as="offset"/> + </mxGeometry> + </mxCell> + <mxCell id="212" value="right copied?" style="ellipse;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="680" y="1840" width="120" height="50" as="geometry"/> + </mxCell> + <mxCell id="219" style="edgeStyle=orthogonalEdgeStyle;html=1;entryX=1;entryY=0.5;entryDx=0;entryDy=0;startArrow=none;startFill=0;endArrow=classic;endFill=1;" edge="1" parent="1" source="215" target="177"> + <mxGeometry relative="1" as="geometry"> + <Array as="points"> + <mxPoint x="830" y="1943"/> + <mxPoint x="830" y="1788"/> + </Array> + </mxGeometry> + </mxCell> + <mxCell id="220" value="No" style="edgeLabel;html=1;align=center;verticalAlign=middle;resizable=0;points=[];" vertex="1" connectable="0" parent="219"> + <mxGeometry x="-0.6661" y="1" relative="1" as="geometry"> + <mxPoint x="-19" y="6" as="offset"/> + </mxGeometry> + </mxCell> + <mxCell id="222" value="Yes" style="edgeStyle=orthogonalEdgeStyle;html=1;entryX=0.5;entryY=0;entryDx=0;entryDy=0;startArrow=none;startFill=0;endArrow=classic;endFill=1;" edge="1" parent="1" source="215" target="221"> + <mxGeometry x="-0.1667" relative="1" as="geometry"> + <mxPoint as="offset"/> + </mxGeometry> + </mxCell> + <mxCell id="215" value="root?" style="ellipse;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="680" y="1917.5" width="120" height="50" as="geometry"/> + </mxCell> + <mxCell id="226" style="edgeStyle=orthogonalEdgeStyle;html=1;exitX=0.5;exitY=1;exitDx=0;exitDy=0;entryX=0.5;entryY=0;entryDx=0;entryDy=0;startArrow=none;startFill=0;endArrow=classic;endFill=1;" edge="1" parent="1" source="221" target="225"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="227" value="Yes" style="edgeLabel;html=1;align=center;verticalAlign=middle;resizable=0;points=[];" vertex="1" connectable="0" parent="226"> + <mxGeometry x="-0.6889" y="-1" relative="1" as="geometry"> + <mxPoint as="offset"/> + </mxGeometry> + </mxCell> + <mxCell id="228" style="edgeStyle=orthogonalEdgeStyle;html=1;exitX=0;exitY=0.5;exitDx=0;exitDy=0;startArrow=none;startFill=0;endArrow=classic;endFill=1;" edge="1" parent="1" source="221"> + <mxGeometry relative="1" as="geometry"> + <mxPoint x="580" y="2023" as="targetPoint"/> + </mxGeometry> + </mxCell> + <mxCell id="233" value="No" style="edgeLabel;html=1;align=center;verticalAlign=middle;resizable=0;points=[];" vertex="1" connectable="0" parent="228"> + <mxGeometry x="-0.7681" y="-1" relative="1" as="geometry"> + <mxPoint as="offset"/> + </mxGeometry> + </mxCell> + <mxCell id="221" value="copied?" style="ellipse;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="680" y="1997.5" width="120" height="50" as="geometry"/> + </mxCell> + <mxCell id="236" style="edgeStyle=orthogonalEdgeStyle;html=1;entryX=0.515;entryY=0.352;entryDx=0;entryDy=0;entryPerimeter=0;fontColor=#007FFF;startArrow=none;startFill=0;endArrow=classic;endFill=1;" edge="1" parent="1" source="225" target="234"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="225" value="swap" style="rounded=0;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="680" y="2100" width="120" height="60" as="geometry"/> + </mxCell> + <mxCell id="231" value="rightDown" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1"> + <mxGeometry x="435" y="1680" width="60" height="30" as="geometry"/> + </mxCell> + <mxCell id="232" value="up" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1"> + <mxGeometry x="705" y="1680" width="60" height="30" as="geometry"/> + </mxCell> + <mxCell id="234" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;strokeColor=#007FFF;strokeWidth=2;fontColor=#FF8000;" vertex="1" parent="1"> + <mxGeometry x="730" y="2190" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="235" value="End" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;strokeWidth=2;fontColor=#007FFF;" vertex="1" parent="1"> + <mxGeometry x="710" y="2200" width="60" height="30" as="geometry"/> + </mxCell> + <mxCell id="239" value="" style="ellipse;whiteSpace=wrap;html=1;strokeColor=#000000;strokeWidth=1;fontColor=#000000;fillColor=default;" vertex="1" parent="1"> + <mxGeometry x="70" y="2090" width="70" height="30" as="geometry"/> + </mxCell> + <mxCell id="240" value="" style="rounded=0;whiteSpace=wrap;html=1;strokeColor=#000000;strokeWidth=1;fontColor=#000000;fillColor=default;" vertex="1" parent="1"> + <mxGeometry x="70" y="2140" width="70" height="30" as="geometry"/> + </mxCell> + <mxCell id="241" value="CodeGear" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;strokeWidth=1;fontColor=#000000;" vertex="1" parent="1"> + <mxGeometry x="150" y="2140" width="60" height="30" as="geometry"/> + </mxCell> + <mxCell id="242" value="Conditional branch" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;strokeWidth=1;fontColor=#000000;" vertex="1" parent="1"> + <mxGeometry x="150" y="2090" width="110" height="30" as="geometry"/> + </mxCell> + <mxCell id="243" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;strokeColor=#FF8000;" vertex="1" parent="1"> + <mxGeometry x="95" y="2190" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="244" value="Phase starting point" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;strokeWidth=1;fontColor=#000000;" vertex="1" parent="1"> + <mxGeometry x="150" y="2185" width="110" height="30" as="geometry"/> + </mxCell> + </root> + </mxGraphModel> + </diagram> +</mxfile> \ No newline at end of file
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/Paper/fig/copy_algo3.drawio Mon Jan 29 13:41:22 2024 +0900 @@ -0,0 +1,215 @@ +<mxfile host="65bd71144e"> + <diagram id="p-B8z-Vdb0gE9XzKJtCj" name="Page-1"> + <mxGraphModel dx="653" dy="286" grid="1" gridSize="10" guides="1" tooltips="1" connect="1" arrows="1" fold="1" page="1" pageScale="1" pageWidth="827" pageHeight="1169" math="0" shadow="0"> + <root> + <mxCell id="0"/> + <mxCell id="1" parent="0"/> + <mxCell id="2" value="" style="rounded=0;whiteSpace=wrap;html=1;fillColor=none;strokeWidth=2;" vertex="1" parent="1"> + <mxGeometry x="620" y="1717.5" width="240" height="352.5" as="geometry"/> + </mxCell> + <mxCell id="3" value="" style="rounded=0;whiteSpace=wrap;html=1;fillColor=none;strokeWidth=2;" vertex="1" parent="1"> + <mxGeometry x="360" y="1717.5" width="220" height="322.5" as="geometry"/> + </mxCell> + <mxCell id="4" value="" style="rounded=0;whiteSpace=wrap;html=1;fillColor=none;strokeWidth=2;strokeColor=#000000;" vertex="1" parent="1"> + <mxGeometry x="90" y="1717.5" width="230" height="280" as="geometry"/> + </mxCell> + <mxCell id="5" value="leftDown" style="rounded=0;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="150" y="1757.5" width="120" height="60" as="geometry"/> + </mxCell> + <mxCell id="6" style="edgeStyle=orthogonalEdgeStyle;html=1;exitX=0;exitY=0.5;exitDx=0;exitDy=0;entryX=1;entryY=0.25;entryDx=0;entryDy=0;startArrow=none;startFill=0;endArrow=classic;endFill=1;" edge="1" parent="1" source="7" target="4"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="7" value="rightDown" style="rounded=0;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="414" y="1757.5" width="120" height="60" as="geometry"/> + </mxCell> + <mxCell id="8" style="edgeStyle=orthogonalEdgeStyle;html=1;exitX=0.5;exitY=1;exitDx=0;exitDy=0;entryX=0.5;entryY=0;entryDx=0;entryDy=0;startArrow=none;startFill=0;endArrow=classic;endFill=1;" edge="1" parent="1" source="9" target="38"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="9" value="up" style="rounded=0;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="680" y="1757.5" width="120" height="60" as="geometry"/> + </mxCell> + <mxCell id="10" style="edgeStyle=orthogonalEdgeStyle;html=1;exitX=0;exitY=0;exitDx=0;exitDy=0;entryX=0.145;entryY=1;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;startArrow=classic;startFill=1;" edge="1" parent="1" source="15" target="5"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="11" style="edgeStyle=orthogonalEdgeStyle;html=1;exitX=1;exitY=0;exitDx=0;exitDy=0;entryX=0.854;entryY=0.977;entryDx=0;entryDy=0;entryPerimeter=0;startArrow=none;startFill=0;endArrow=classic;endFill=1;" edge="1" parent="1" source="15" target="5"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="12" value="Yes" style="edgeLabel;html=1;align=center;verticalAlign=middle;resizable=0;points=[];fontColor=#000000;" vertex="1" connectable="0" parent="11"> + <mxGeometry x="-0.7643" relative="1" as="geometry"> + <mxPoint as="offset"/> + </mxGeometry> + </mxCell> + <mxCell id="13" style="edgeStyle=orthogonalEdgeStyle;html=1;startArrow=none;startFill=0;endArrow=classic;endFill=1;entryX=-0.002;entryY=0.698;entryDx=0;entryDy=0;entryPerimeter=0;" edge="1" parent="1" source="15" target="3"> + <mxGeometry relative="1" as="geometry"> + <Array as="points"/> + </mxGeometry> + </mxCell> + <mxCell id="14" value="No" style="edgeLabel;html=1;align=center;verticalAlign=middle;resizable=0;points=[];" vertex="1" connectable="0" parent="13"> + <mxGeometry x="-0.8407" relative="1" as="geometry"> + <mxPoint as="offset"/> + </mxGeometry> + </mxCell> + <mxCell id="15" value="left exist?" style="ellipse;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="150" y="1917.5" width="120" height="50" as="geometry"/> + </mxCell> + <mxCell id="16" style="edgeStyle=orthogonalEdgeStyle;html=1;entryX=0;entryY=0.5;entryDx=0;entryDy=0;startArrow=none;startFill=0;endArrow=classic;endFill=1;" edge="1" parent="1" source="17" target="15"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="17" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;strokeColor=#FF8000;" vertex="1" parent="1"> + <mxGeometry x="100" y="1932.5" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="18" value="Start" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;fontColor=#FF8000;" vertex="1" parent="1"> + <mxGeometry x="80" y="1902.5" width="60" height="30" as="geometry"/> + </mxCell> + <mxCell id="19" style="edgeStyle=orthogonalEdgeStyle;html=1;startArrow=none;startFill=0;endArrow=classic;endFill=1;" edge="1" parent="1" source="23" target="7"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="20" value="Yes" style="edgeLabel;html=1;align=center;verticalAlign=middle;resizable=0;points=[];" vertex="1" connectable="0" parent="19"> + <mxGeometry x="-0.6463" y="1" relative="1" as="geometry"> + <mxPoint as="offset"/> + </mxGeometry> + </mxCell> + <mxCell id="21" style="edgeStyle=orthogonalEdgeStyle;html=1;entryX=0.003;entryY=0.64;entryDx=0;entryDy=0;entryPerimeter=0;startArrow=none;startFill=0;endArrow=classic;endFill=1;" edge="1" parent="1" source="23" target="2"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="22" value="No" style="edgeLabel;html=1;align=center;verticalAlign=middle;resizable=0;points=[];" vertex="1" connectable="0" parent="21"> + <mxGeometry x="-0.7763" y="-1" relative="1" as="geometry"> + <mxPoint as="offset"/> + </mxGeometry> + </mxCell> + <mxCell id="23" value="right exist?" style="ellipse;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="414" y="1917.5" width="120" height="50" as="geometry"/> + </mxCell> + <mxCell id="24" style="edgeStyle=orthogonalEdgeStyle;html=1;entryX=0;entryY=0.25;entryDx=0;entryDy=0;startArrow=none;startFill=0;endArrow=classic;endFill=1;" edge="1" parent="1" source="25" target="4"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="25" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;fontColor=#007FFF;strokeColor=#007FFF;" vertex="1" parent="1"> + <mxGeometry x="20" y="1777.5" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="26" value="Start" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;fontColor=#007FFF;" vertex="1" parent="1"> + <mxGeometry y="1752.5" width="60" height="30" as="geometry"/> + </mxCell> + <mxCell id="27" value="LeftDown" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1"> + <mxGeometry x="170" y="1680" width="60" height="30" as="geometry"/> + </mxCell> + <mxCell id="28" style="edgeStyle=orthogonalEdgeStyle;html=1;startArrow=none;startFill=0;endArrow=classic;endFill=1;" edge="1" parent="1" source="29" target="23"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="29" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;strokeColor=#FF8000;" vertex="1" parent="1"> + <mxGeometry x="370" y="1932.5" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="30" value="Start" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;fontColor=#FF8000;" vertex="1" parent="1"> + <mxGeometry x="350" y="1907.5" width="60" height="30" as="geometry"/> + </mxCell> + <mxCell id="31" style="edgeStyle=orthogonalEdgeStyle;html=1;entryX=0;entryY=0.5;entryDx=0;entryDy=0;startArrow=none;startFill=0;endArrow=classic;endFill=1;exitX=0.589;exitY=0.988;exitDx=0;exitDy=0;exitPerimeter=0;" edge="1" parent="1" source="32" target="9"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="32" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;strokeColor=#FF8000;" vertex="1" parent="1"> + <mxGeometry x="630" y="1777.5" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="33" value="Start" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;fontColor=#FF8000;" vertex="1" parent="1"> + <mxGeometry x="610" y="1752.5" width="60" height="30" as="geometry"/> + </mxCell> + <mxCell id="34" style="edgeStyle=orthogonalEdgeStyle;html=1;entryX=0.5;entryY=0;entryDx=0;entryDy=0;startArrow=none;startFill=0;endArrow=classic;endFill=1;" edge="1" parent="1" source="38" target="42"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="35" value="Yes" style="edgeLabel;html=1;align=center;verticalAlign=middle;resizable=0;points=[];" vertex="1" connectable="0" parent="34"> + <mxGeometry x="-0.3697" y="-4" relative="1" as="geometry"> + <mxPoint x="4" y="4" as="offset"/> + </mxGeometry> + </mxCell> + <mxCell id="36" style="edgeStyle=orthogonalEdgeStyle;html=1;startArrow=none;startFill=0;endArrow=classic;endFill=1;" edge="1" parent="1" source="38"> + <mxGeometry relative="1" as="geometry"> + <mxPoint x="580" y="1865" as="targetPoint"/> + </mxGeometry> + </mxCell> + <mxCell id="37" value="No" style="edgeLabel;html=1;align=center;verticalAlign=middle;resizable=0;points=[];fontColor=#000000;" vertex="1" connectable="0" parent="36"> + <mxGeometry x="-0.7491" y="-2" relative="1" as="geometry"> + <mxPoint as="offset"/> + </mxGeometry> + </mxCell> + <mxCell id="38" value="right copied?" style="ellipse;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="680" y="1840" width="120" height="50" as="geometry"/> + </mxCell> + <mxCell id="39" style="edgeStyle=orthogonalEdgeStyle;html=1;entryX=1;entryY=0.5;entryDx=0;entryDy=0;startArrow=none;startFill=0;endArrow=classic;endFill=1;" edge="1" parent="1" source="42" target="9"> + <mxGeometry relative="1" as="geometry"> + <Array as="points"> + <mxPoint x="830" y="1943"/> + <mxPoint x="830" y="1788"/> + </Array> + </mxGeometry> + </mxCell> + <mxCell id="40" value="No" style="edgeLabel;html=1;align=center;verticalAlign=middle;resizable=0;points=[];" vertex="1" connectable="0" parent="39"> + <mxGeometry x="-0.6661" y="1" relative="1" as="geometry"> + <mxPoint x="-19" y="6" as="offset"/> + </mxGeometry> + </mxCell> + <mxCell id="41" value="Yes" style="edgeStyle=orthogonalEdgeStyle;html=1;entryX=0.5;entryY=0;entryDx=0;entryDy=0;startArrow=none;startFill=0;endArrow=classic;endFill=1;" edge="1" parent="1" source="42" target="47"> + <mxGeometry x="-0.1667" relative="1" as="geometry"> + <mxPoint as="offset"/> + </mxGeometry> + </mxCell> + <mxCell id="42" value="is root?" style="ellipse;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="680" y="1917.5" width="120" height="50" as="geometry"/> + </mxCell> + <mxCell id="43" style="edgeStyle=orthogonalEdgeStyle;html=1;exitX=0.5;exitY=1;exitDx=0;exitDy=0;entryX=0.5;entryY=0;entryDx=0;entryDy=0;startArrow=none;startFill=0;endArrow=classic;endFill=1;" edge="1" parent="1" source="47" target="49"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="44" value="Yes" style="edgeLabel;html=1;align=center;verticalAlign=middle;resizable=0;points=[];" vertex="1" connectable="0" parent="43"> + <mxGeometry x="-0.6889" y="-1" relative="1" as="geometry"> + <mxPoint as="offset"/> + </mxGeometry> + </mxCell> + <mxCell id="45" style="edgeStyle=orthogonalEdgeStyle;html=1;exitX=0;exitY=0.5;exitDx=0;exitDy=0;startArrow=none;startFill=0;endArrow=classic;endFill=1;" edge="1" parent="1" source="47"> + <mxGeometry relative="1" as="geometry"> + <mxPoint x="580" y="2023" as="targetPoint"/> + </mxGeometry> + </mxCell> + <mxCell id="46" value="No" style="edgeLabel;html=1;align=center;verticalAlign=middle;resizable=0;points=[];" vertex="1" connectable="0" parent="45"> + <mxGeometry x="-0.7681" y="-1" relative="1" as="geometry"> + <mxPoint as="offset"/> + </mxGeometry> + </mxCell> + <mxCell id="47" value="copied?" style="ellipse;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="680" y="1997.5" width="120" height="50" as="geometry"/> + </mxCell> + <mxCell id="48" style="edgeStyle=orthogonalEdgeStyle;html=1;entryX=0.515;entryY=0.352;entryDx=0;entryDy=0;entryPerimeter=0;fontColor=#007FFF;startArrow=none;startFill=0;endArrow=classic;endFill=1;" edge="1" parent="1" source="49" target="52"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="49" value="swap" style="rounded=0;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="680" y="2100" width="120" height="60" as="geometry"/> + </mxCell> + <mxCell id="50" value="RightDown" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1"> + <mxGeometry x="435" y="1680" width="60" height="30" as="geometry"/> + </mxCell> + <mxCell id="51" value="Up" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1"> + <mxGeometry x="705" y="1680" width="60" height="30" as="geometry"/> + </mxCell> + <mxCell id="52" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;strokeColor=#007FFF;strokeWidth=2;fontColor=#FF8000;" vertex="1" parent="1"> + <mxGeometry x="730" y="2190" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="53" value="End" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;strokeWidth=2;fontColor=#007FFF;" vertex="1" parent="1"> + <mxGeometry x="710" y="2200" width="60" height="30" as="geometry"/> + </mxCell> + <mxCell id="54" value="" style="ellipse;whiteSpace=wrap;html=1;strokeColor=#000000;strokeWidth=1;fontColor=#000000;fillColor=default;" vertex="1" parent="1"> + <mxGeometry x="90" y="2090" width="70" height="30" as="geometry"/> + </mxCell> + <mxCell id="55" value="" style="rounded=0;whiteSpace=wrap;html=1;strokeColor=#000000;strokeWidth=1;fontColor=#000000;fillColor=default;" vertex="1" parent="1"> + <mxGeometry x="90" y="2140" width="70" height="30" as="geometry"/> + </mxCell> + <mxCell id="56" value="CodeGear" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;strokeWidth=1;fontColor=#000000;" vertex="1" parent="1"> + <mxGeometry x="170" y="2140" width="60" height="30" as="geometry"/> + </mxCell> + <mxCell id="57" value="Conditional branch" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;strokeWidth=1;fontColor=#000000;" vertex="1" parent="1"> + <mxGeometry x="170" y="2090" width="110" height="30" as="geometry"/> + </mxCell> + <mxCell id="58" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;strokeColor=#FF8000;" vertex="1" parent="1"> + <mxGeometry x="115" y="2190" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="59" value="Phase starting point" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;strokeWidth=1;fontColor=#000000;" vertex="1" parent="1"> + <mxGeometry x="170" y="2185" width="110" height="30" as="geometry"/> + </mxCell> + </root> + </mxGraphModel> + </diagram> +</mxfile> \ No newline at end of file
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/Paper/fig/copy_algo4.drawio Mon Jan 29 13:41:22 2024 +0900 @@ -0,0 +1,80 @@ +<mxfile host="65bd71144e"> + <diagram id="NWhsmsWKpHYXijNByeQC" name="Page-1"> + <mxGraphModel dx="894" dy="699" grid="1" gridSize="10" guides="1" tooltips="1" connect="1" arrows="1" fold="1" page="1" pageScale="1" pageWidth="827" pageHeight="1169" math="0" shadow="0"> + <root> + <mxCell id="0"/> + <mxCell id="1" parent="0"/> + <mxCell id="9" style="edgeStyle=none;html=1;exitX=0;exitY=1;exitDx=0;exitDy=0;" edge="1" parent="1" source="2" target="3"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="12" value="leftDown" style="edgeLabel;html=1;align=center;verticalAlign=middle;resizable=0;points=[];" vertex="1" connectable="0" parent="9"> + <mxGeometry x="0.0124" relative="1" as="geometry"> + <mxPoint as="offset"/> + </mxGeometry> + </mxCell> + <mxCell id="10" style="edgeStyle=none;html=1;exitX=1;exitY=1;exitDx=0;exitDy=0;endArrow=none;endFill=0;" edge="1" parent="1" source="2" target="4"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="2" value="3" style="ellipse;whiteSpace=wrap;html=1;aspect=fixed;" vertex="1" parent="1"> + <mxGeometry x="160" y="120" width="40" height="40" as="geometry"/> + </mxCell> + <mxCell id="11" style="edgeStyle=none;html=1;exitX=0;exitY=1;exitDx=0;exitDy=0;" edge="1" parent="1" source="3" target="5"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="13" value="leftDown" style="edgeLabel;html=1;align=center;verticalAlign=middle;resizable=0;points=[];" vertex="1" connectable="0" parent="11"> + <mxGeometry x="-0.0132" y="2" relative="1" as="geometry"> + <mxPoint as="offset"/> + </mxGeometry> + </mxCell> + <mxCell id="3" value="2" style="ellipse;whiteSpace=wrap;html=1;aspect=fixed;" vertex="1" parent="1"> + <mxGeometry x="100" y="200" width="40" height="40" as="geometry"/> + </mxCell> + <mxCell id="4" value="4" style="ellipse;whiteSpace=wrap;html=1;aspect=fixed;" vertex="1" parent="1"> + <mxGeometry x="220" y="200" width="40" height="40" as="geometry"/> + </mxCell> + <mxCell id="5" value="1" style="ellipse;whiteSpace=wrap;html=1;aspect=fixed;" vertex="1" parent="1"> + <mxGeometry x="40" y="280" width="40" height="40" as="geometry"/> + </mxCell> + <mxCell id="14" value="" style="rounded=0;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="300" y="160" width="120" height="160" as="geometry"/> + </mxCell> + <mxCell id="16" value="" style="rounded=0;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="440" y="160" width="120" height="160" as="geometry"/> + </mxCell> + <mxCell id="17" value="nodeStack" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1"> + <mxGeometry x="330" y="125" width="60" height="30" as="geometry"/> + </mxCell> + <mxCell id="18" value="toStack" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1"> + <mxGeometry x="470" y="125" width="60" height="30" as="geometry"/> + </mxCell> + <mxCell id="19" value="" style="shape=flexArrow;endArrow=classic;html=1;width=6.4;endSize=6.072;endWidth=9.28;" edge="1" parent="1"> + <mxGeometry width="50" height="50" relative="1" as="geometry"> + <mxPoint x="130" y="300" as="sourcePoint"/> + <mxPoint x="80" y="299.6" as="targetPoint"/> + </mxGeometry> + </mxCell> + <mxCell id="20" value="tree-&gt;current" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1"> + <mxGeometry x="130" y="285" width="80" height="30" as="geometry"/> + </mxCell> + <mxCell id="21" value="3" style="rounded=0;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="300" y="290" width="120" height="30" as="geometry"/> + </mxCell> + <mxCell id="22" value="2" style="rounded=0;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="300" y="260" width="120" height="30" as="geometry"/> + </mxCell> + <mxCell id="23" value="3" style="rounded=0;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="440" y="290" width="120" height="30" as="geometry"/> + </mxCell> + <mxCell id="24" value="fromTree" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1"> + <mxGeometry x="50" y="130" width="60" height="30" as="geometry"/> + </mxCell> + <mxCell id="25" value="1" style="rounded=0;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="440" y="230" width="120" height="30" as="geometry"/> + </mxCell> + <mxCell id="26" value="2" style="rounded=0;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="440" y="260" width="120" height="30" as="geometry"/> + </mxCell> + </root> + </mxGraphModel> + </diagram> +</mxfile> \ No newline at end of file
--- a/Paper/fig/rbtree_def.drawio Sun Jan 28 15:52:08 2024 +0900 +++ b/Paper/fig/rbtree_def.drawio Mon Jan 29 13:41:22 2024 +0900 @@ -1,122 +1,145 @@ <mxfile host="65bd71144e"> <diagram id="PxV3Z1aBI1mM_MlTBdEj" name="Page-1"> - <mxGraphModel dx="229" dy="647" grid="1" gridSize="10" guides="1" tooltips="1" connect="1" arrows="1" fold="1" page="1" pageScale="1" pageWidth="827" pageHeight="1169" math="0" shadow="0"> + <mxGraphModel dx="1799" dy="760" grid="1" gridSize="10" guides="1" tooltips="1" connect="1" arrows="1" fold="1" page="1" pageScale="1" pageWidth="827" pageHeight="1169" math="0" shadow="0"> <root> <mxCell id="0"/> <mxCell id="1" parent="0"/> - <mxCell id="9" style="edgeStyle=none;html=1;entryX=0.55;entryY=1;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;" edge="1" parent="1" source="2" target="4"> + <mxCell id="9" style="edgeStyle=none;html=1;entryX=0.55;entryY=1;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;" parent="1" source="2" target="4" edge="1"> <mxGeometry relative="1" as="geometry"/> </mxCell> - <mxCell id="10" style="edgeStyle=none;html=1;entryX=0.45;entryY=0.7;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;" edge="1" parent="1" source="2" target="3"> + <mxCell id="10" style="edgeStyle=none;html=1;entryX=0.45;entryY=0.7;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;" parent="1" source="2" target="3" edge="1"> <mxGeometry relative="1" as="geometry"/> </mxCell> - <mxCell id="2" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" vertex="1" parent="1"> + <mxCell id="2" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" parent="1" vertex="1"> <mxGeometry x="360" y="107.5" width="20" height="20" as="geometry"/> </mxCell> - <mxCell id="11" style="edgeStyle=none;html=1;entryX=0.7;entryY=0.5;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;" edge="1" parent="1" source="3" target="8"> + <mxCell id="11" style="edgeStyle=none;html=1;entryX=0.7;entryY=0.5;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;" parent="1" source="3" target="8" edge="1"> <mxGeometry relative="1" as="geometry"/> </mxCell> - <mxCell id="12" style="edgeStyle=none;html=1;entryX=0.4;entryY=0.7;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;" edge="1" parent="1" source="3" target="5"> + <mxCell id="12" style="edgeStyle=none;html=1;entryX=0.4;entryY=0.7;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;" parent="1" source="3" target="5" edge="1"> <mxGeometry relative="1" as="geometry"/> </mxCell> - <mxCell id="3" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" vertex="1" parent="1"> + <mxCell id="3" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" parent="1" vertex="1"> <mxGeometry x="390" y="147.5" width="20" height="20" as="geometry"/> </mxCell> - <mxCell id="4" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" vertex="1" parent="1"> + <mxCell id="4" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" parent="1" vertex="1"> <mxGeometry x="330" y="147.5" width="20" height="20" as="geometry"/> </mxCell> - <mxCell id="5" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" vertex="1" parent="1"> + <mxCell id="5" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" parent="1" vertex="1"> <mxGeometry x="420" y="187.5" width="20" height="20" as="geometry"/> </mxCell> - <mxCell id="8" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" vertex="1" parent="1"> + <mxCell id="8" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" parent="1" vertex="1"> <mxGeometry x="360" y="187.5" width="20" height="20" as="geometry"/> </mxCell> - <mxCell id="41" style="edgeStyle=none;html=1;entryX=0.55;entryY=1;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;" edge="1" parent="1" source="43" target="47"> + <mxCell id="41" style="edgeStyle=none;html=1;entryX=0.55;entryY=1;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;" parent="1" source="43" target="47" edge="1"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="42" style="edgeStyle=none;html=1;entryX=0.45;entryY=0.7;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;" parent="1" source="43" target="46" edge="1"> <mxGeometry relative="1" as="geometry"/> </mxCell> - <mxCell id="42" style="edgeStyle=none;html=1;entryX=0.45;entryY=0.7;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;" edge="1" parent="1" source="43" target="46"> + <mxCell id="43" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" parent="1" vertex="1"> + <mxGeometry x="110" y="105" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="44" style="edgeStyle=none;html=1;entryX=0.7;entryY=0.5;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;" parent="1" source="46" target="53" edge="1"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="45" style="edgeStyle=none;html=1;entryX=0.4;entryY=0.7;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;" parent="1" source="46" target="50" edge="1"> <mxGeometry relative="1" as="geometry"/> </mxCell> - <mxCell id="43" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" vertex="1" parent="1"> - <mxGeometry x="70" y="95" width="20" height="20" as="geometry"/> + <mxCell id="46" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" parent="1" vertex="1"> + <mxGeometry x="140" y="145" width="20" height="20" as="geometry"/> </mxCell> - <mxCell id="44" style="edgeStyle=none;html=1;entryX=0.7;entryY=0.5;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;" edge="1" parent="1" source="46" target="53"> - <mxGeometry relative="1" as="geometry"/> - </mxCell> - <mxCell id="45" style="edgeStyle=none;html=1;entryX=0.4;entryY=0.7;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;" edge="1" parent="1" source="46" target="50"> + <mxCell id="86" style="edgeStyle=none;html=1;entryX=0.6;entryY=0.55;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;" edge="1" parent="1" source="47" target="85"> <mxGeometry relative="1" as="geometry"/> </mxCell> - <mxCell id="46" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" vertex="1" parent="1"> - <mxGeometry x="100" y="135" width="20" height="20" as="geometry"/> + <mxCell id="47" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" parent="1" vertex="1"> + <mxGeometry x="10" y="145" width="20" height="20" as="geometry"/> </mxCell> - <mxCell id="47" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" vertex="1" parent="1"> - <mxGeometry x="40" y="135" width="20" height="20" as="geometry"/> + <mxCell id="50" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" parent="1" vertex="1"> + <mxGeometry x="170" y="185" width="20" height="20" as="geometry"/> </mxCell> - <mxCell id="48" style="edgeStyle=none;html=1;endArrow=none;endFill=0;" edge="1" parent="1" source="50" target="52"> + <mxCell id="53" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" parent="1" vertex="1"> + <mxGeometry x="110" y="185" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="58" style="edgeStyle=orthogonalEdgeStyle;html=1;entryX=0.503;entryY=0.347;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;curved=1;dashed=1;" parent="1" source="54" target="43" edge="1"> <mxGeometry relative="1" as="geometry"/> </mxCell> - <mxCell id="49" style="edgeStyle=none;html=1;entryX=0.3;entryY=0.95;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;" edge="1" parent="1" source="50" target="51"> + <mxCell id="54" value="root" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" parent="1" vertex="1"> + <mxGeometry x="170" y="80" width="30" height="30" as="geometry"/> + </mxCell> + <mxCell id="61" style="edgeStyle=orthogonalEdgeStyle;curved=1;html=1;dashed=1;endArrow=none;endFill=0;" parent="1" source="56" target="50" edge="1"> <mxGeometry relative="1" as="geometry"/> </mxCell> - <mxCell id="50" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" vertex="1" parent="1"> - <mxGeometry x="130" y="175" width="20" height="20" as="geometry"/> - </mxCell> - <mxCell id="51" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" vertex="1" parent="1"> - <mxGeometry x="160" y="215" width="20" height="20" as="geometry"/> + <mxCell id="56" value="current" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" parent="1" vertex="1"> + <mxGeometry x="220" y="155" width="50" height="30" as="geometry"/> </mxCell> - <mxCell id="52" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" vertex="1" parent="1"> - <mxGeometry x="100" y="215" width="20" height="20" as="geometry"/> + <mxCell id="66" style="edgeStyle=orthogonalEdgeStyle;curved=1;html=1;entryX=0.704;entryY=0.481;entryDx=0;entryDy=0;entryPerimeter=0;dashed=1;endArrow=none;endFill=0;" parent="1" source="63" target="2" edge="1"> + <mxGeometry relative="1" as="geometry"/> </mxCell> - <mxCell id="53" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" vertex="1" parent="1"> - <mxGeometry x="70" y="175" width="20" height="20" as="geometry"/> + <mxCell id="63" value="grandparent" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" parent="1" vertex="1"> + <mxGeometry x="450" y="82.5" width="80" height="30" as="geometry"/> </mxCell> - <mxCell id="58" style="edgeStyle=orthogonalEdgeStyle;html=1;entryX=0.503;entryY=0.347;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;curved=1;dashed=1;" edge="1" parent="1" source="54" target="43"> + <mxCell id="67" style="edgeStyle=orthogonalEdgeStyle;curved=1;html=1;dashed=1;endArrow=none;endFill=0;" parent="1" source="64" target="3" edge="1"> <mxGeometry relative="1" as="geometry"/> </mxCell> - <mxCell id="54" value="root" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1"> - <mxGeometry x="160" y="70" width="30" height="30" as="geometry"/> + <mxCell id="64" value="parent" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" parent="1" vertex="1"> + <mxGeometry x="475" y="117.5" width="50" height="30" as="geometry"/> </mxCell> - <mxCell id="60" style="edgeStyle=orthogonalEdgeStyle;curved=1;html=1;entryX=0.586;entryY=0.347;entryDx=0;entryDy=0;entryPerimeter=0;dashed=1;endArrow=none;endFill=0;" edge="1" parent="1" source="55" target="46"> + <mxCell id="68" style="edgeStyle=orthogonalEdgeStyle;curved=1;html=1;dashed=1;endArrow=none;endFill=0;" parent="1" source="65" target="5" edge="1"> <mxGeometry relative="1" as="geometry"/> </mxCell> - <mxCell id="55" value="previous" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1"> - <mxGeometry x="174" y="105" width="60" height="30" as="geometry"/> + <mxCell id="65" value="current" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" parent="1" vertex="1"> + <mxGeometry x="490" y="157.5" width="55" height="30" as="geometry"/> + </mxCell> + <mxCell id="70" value="Parent RedBlackTree" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" parent="1" vertex="1"> + <mxGeometry x="100" y="40" width="120" height="30" as="geometry"/> </mxCell> - <mxCell id="61" style="edgeStyle=orthogonalEdgeStyle;curved=1;html=1;dashed=1;endArrow=none;endFill=0;" edge="1" parent="1" source="56" target="50"> + <mxCell id="71" value="When rotating" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" parent="1" vertex="1"> + <mxGeometry x="385" y="40" width="90" height="30" as="geometry"/> + </mxCell> + <mxCell id="73" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" vertex="1" parent="1"> + <mxGeometry x="180" y="105" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="90" style="edgeStyle=orthogonalEdgeStyle;curved=1;html=1;dashed=1;endArrow=none;endFill=0;" edge="1" parent="1" source="74" target="73"> <mxGeometry relative="1" as="geometry"/> </mxCell> - <mxCell id="56" value="current" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1"> - <mxGeometry x="200" y="145" width="50" height="30" as="geometry"/> + <mxCell id="74" value="newNode" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1"> + <mxGeometry x="230" y="80" width="50" height="30" as="geometry"/> </mxCell> - <mxCell id="62" style="edgeStyle=orthogonalEdgeStyle;curved=1;html=1;entryX=0.642;entryY=0.292;entryDx=0;entryDy=0;entryPerimeter=0;dashed=1;endArrow=none;endFill=0;" edge="1" parent="1" source="57" target="51"> + <mxCell id="76" style="edgeStyle=none;html=1;entryX=0.66;entryY=0.8;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;" edge="1" parent="1" source="75" target="47"> <mxGeometry relative="1" as="geometry"/> </mxCell> - <mxCell id="57" value="newNode" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1"> - <mxGeometry x="220" y="185" width="60" height="30" as="geometry"/> + <mxCell id="75" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" vertex="1" parent="1"> + <mxGeometry x="40" y="105" width="20" height="20" as="geometry"/> </mxCell> - <mxCell id="66" style="edgeStyle=orthogonalEdgeStyle;curved=1;html=1;entryX=0.704;entryY=0.481;entryDx=0;entryDy=0;entryPerimeter=0;dashed=1;endArrow=none;endFill=0;" edge="1" parent="1" source="63" target="2"> + <mxCell id="77" style="edgeStyle=none;html=1;entryX=0.45;entryY=0.7;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;" edge="1" parent="1" target="81"> + <mxGeometry relative="1" as="geometry"> + <mxPoint x="50" y="115" as="sourcePoint"/> + </mxGeometry> + </mxCell> + <mxCell id="79" style="edgeStyle=none;html=1;entryX=0.7;entryY=0.5;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;" edge="1" parent="1" source="81" target="83"> <mxGeometry relative="1" as="geometry"/> </mxCell> - <mxCell id="63" value="grandparent" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1"> - <mxGeometry x="450" y="82.5" width="80" height="30" as="geometry"/> - </mxCell> - <mxCell id="67" style="edgeStyle=orthogonalEdgeStyle;curved=1;html=1;dashed=1;endArrow=none;endFill=0;" edge="1" parent="1" source="64" target="3"> + <mxCell id="80" style="edgeStyle=none;html=1;entryX=0.4;entryY=0.7;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;" edge="1" parent="1" source="81" target="82"> <mxGeometry relative="1" as="geometry"/> </mxCell> - <mxCell id="64" value="parent" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1"> - <mxGeometry x="475" y="117.5" width="50" height="30" as="geometry"/> + <mxCell id="81" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" vertex="1" parent="1"> + <mxGeometry x="70" y="145" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="82" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" vertex="1" parent="1"> + <mxGeometry x="100" y="185" width="20" height="20" as="geometry"/> </mxCell> - <mxCell id="68" style="edgeStyle=orthogonalEdgeStyle;curved=1;html=1;dashed=1;endArrow=none;endFill=0;" edge="1" parent="1" source="65" target="5"> + <mxCell id="83" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" vertex="1" parent="1"> + <mxGeometry x="40" y="185" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="85" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" vertex="1" parent="1"> + <mxGeometry x="-20" y="185" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="88" style="edgeStyle=orthogonalEdgeStyle;html=1;entryX=0.6;entryY=0.45;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;curved=1;dashed=1;" edge="1" parent="1" source="87" target="75"> <mxGeometry relative="1" as="geometry"/> </mxCell> - <mxCell id="65" value="operation node" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1"> - <mxGeometry x="465" y="157.5" width="90" height="30" as="geometry"/> - </mxCell> - <mxCell id="70" value="Parent RedBlackTree" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1"> - <mxGeometry x="100" y="40" width="120" height="30" as="geometry"/> - </mxCell> - <mxCell id="71" value="When rotating" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1"> - <mxGeometry x="385" y="40" width="90" height="30" as="geometry"/> + <mxCell id="87" value="previous" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1"> + <mxGeometry x="85" y="80" width="50" height="30" as="geometry"/> </mxCell> </root> </mxGraphModel>
--- a/Paper/master_paper.lol Sun Jan 28 15:52:08 2024 +0900 +++ b/Paper/master_paper.lol Mon Jan 29 13:41:22 2024 +0900 @@ -8,5 +8,5 @@ \contentsline {lstlisting}{\numberline {3.7}RedBlackTreeの実装の型定義}{16}{}% \contentsline {lstlisting}{\numberline {3.8}Nodeの型定義}{17}{}% \contentsline {lstlisting}{\numberline {5.1}実行するCodeGearの切り替えのコード}{30}{}% -\contentsline {lstlisting}{\numberline {6.1}CopyRedBlackTreeの実装}{31}{}% -\contentsline {lstlisting}{\numberline {6.2}CopyRedBlackTreeのアルゴリズム}{33}{}% +\contentsline {lstlisting}{\numberline {6.1}Tree Interfaceの使用定義(Copy追加後)}{31}{}% +\contentsline {lstlisting}{\numberline {6.2}RedBlackTreeの実装の型定義(Copy追加後)}{31}{}%
--- a/Paper/master_paper.tex Sun Jan 28 15:52:08 2024 +0900 +++ b/Paper/master_paper.tex Mon Jan 29 13:41:22 2024 +0900 @@ -396,11 +396,12 @@ 2〜7行目はRedBlackTreeが持つノードを表しており， それぞれのノードの役割は図\ref{fig:rbtree-def}のように示される． rootはRedBlackTreeの全てのノードを参照できる親ツリーのルートノードを指す． -読み込み中のノードはcurrentで指されており，currentの親ノードをprevious， -追加するノードをnewNodeで表している． +読み込み中のノードはcurrentで指されており，追加するノードをnewNodeで表している． +previousは木を操作する以前の木を保持するノードであり， +これにより非破壊的な操作を可能とする． また，RedBlackTreeは挿入，更新，削除の際に木の回転操作を行う． -その際，起点のノードに対して親のノードをparent，祖父母のノードをgrandparentで指す． -8行目のnodeStackは木の操作をする際に使用するスタックである． +その際，起点のノード(current)に対して親のノードをparent，祖父母のノードをgrandparentで指す． +8行目のnodeStackは木の操作時，木を辿るために使用するスタックである． 9行目のfindNodeNextはfindNode CodeGearを実行後，次に実行するCodeGearを保持する． 10行目のresultはノードを探索する際のノードの比較結果を保持する． @@ -414,6 +415,8 @@ また，3〜7行目よりleft，rightで子のNodeのポインタを持つことによって木構造を構築し， enum ColorでRedBlackTreeとして必要なノードの色を表現していることがわかる． +\section{ALLOCATE} + \chapter{GearsFileSystem} ファイルシステムはOSにおいてユーザーやアプリケーションが使用するファイルや @@ -768,8 +771,6 @@ - - \chapter{CopyRedBlackTreeの実装} データのバックアップやレプリケーション，GCの機能を実装するためには， @@ -777,29 +778,77 @@ GearsOSのファイルシステムにおいて，データは全てRedBlackTreeに格納される． しかしながら，現状のRedBlackTreeには木をコピーする機能が無い． よって，RedBlackTreeに木のコピー機能を実装する必要がある． +CopyRedBlackTreeの実装について述べる． -\lstinputlisting[label=src:CopyRedBlackTree.cbc, caption=CopyRedBlackTreeの実装]{src/CopyRedBlackTree.cbc} +\section{Tree InterfaceのCopy API} + +CopyRedBlackはTree InterfaceのAPIの1つとして実装した． +ソースコード\ref{src:TreeCopy.h}にCopy APIを追加したTree Interfaceの仕様定義を示す． + +\lstinputlisting[label=src:TreeCopy.h, caption=Tree Interfaceの使用定義(Copy追加後)]{src/TreeCopy.h} + +10行目にcopy()が追加されており，inputDataGearは\emph{\_\_code} nextのみとしている． +これにより， +\texttt{goto tree->copy(next);}といった記述でRedBlackTreeのコピーを行うことができる． +次にRedBlackTreeの実装の型定義をソースコード\ref{src:CopyRedBlackTree.h}に示す． +9，12行目にある通り，コピー時に使用するtoStackを1つと +木のコピーが完了しているかどうかを示すcopiedフラグを追加している． +今回の実装ではStackを2つ使用する． +追加したtoStackの他に，元からRedBlackTreeの操作に使用しているnodeStackを用いる． +これらのStackはdataとしてNode構造体のポインタを持つ． + +\lstinputlisting[label=src:CopyRedBlackTree.h, caption=RedBlackTreeの実装の型定義(Copy追加後)]{src/CopyRedBlackTree.h} + +% \lstinputlisting[label=src:CopyRedBlackTree.cbc, caption=CopyRedBlackTreeの実装]{src/CopyRedBlackTree.cbc} \section{コピーのアルゴリズム} - - -\lstinputlisting[label=src:CopyRedBlackTree.cbc, caption=CopyRedBlackTreeのアルゴリズム]{src/copyAlgorithm.cbc} +コピーは2つのStackを使用し，left方向から深さ優先でRedBlackTreeのノードをリーフ方向に降りながら行う． +図\ref{fig:TreeAndStack}にコピー時のある地点でのコピー元の木と2つのStackの状態を例示する． +leftDownを2回行い，\texttt{tree->current}がkeyが1のノードを指している． +この時，木を辿るためのnodeStackは\texttt{tree->current}以前に辿った3と2のノードが積まれている． +toStackにはコピー元の木のノードとkey，value，colorの値が同じでアドレスが異なるノードが積まれている． +ノードは辿った際にコピーを行いtoStackへと積むため，すでに辿った3，2，1のノードが積まれている． +葉ノードまでたどり着いた時やleft，rightがすでに辿ったノードだった場合はupでroot方向に戻る． +その際は，\texttt{tree->current}を親ノードに付け替え，nodeStackとtoStackを1回popする． +toStackは新規にアロケートした子ノードと親ノードを接続したり， +すでにノードをアロケートしているかどうかを判断するなど， +コピー先の木を操作したり状態を確認したりするために必要である． +例えば，upする場合はコピー元のrightノードの存在を確認し， +toStackのtopをみてすでにrightノードを新規にアロケートしているかを見ることで， +さらにupするかどうかを判断するなどがある． \begin{figure}[ht] \begin{center} - \includegraphics[width=160mm]{fig/copy_algo.png} + \includegraphics[width=150mm]{fig/copy_algo4.png} \end{center} - \caption{Copyのアルゴリズム} - \label{fig:CopyAlgo} + \caption{コピー元のTreeと2つのStackの状態の例} + \label{fig:TreeAndStack} \end{figure} -\section{Stackの使用に関して} -\section{証明のしやすさについて} +図\ref{fig:CopyCGTransition}にCopy時のCodeGearの大まかな遷移を示す． +四角ノードがCodeGear，丸ノードが遷移条件を表す． +それらを囲む四角はCodeGearの遷移をLeftDown，RightDown，Upの3つのフェーズに区切ったもので， +図を簡略化するためのものである． +フェーズの四角に矢印が向くと，フェーズが持つStart(オレンジで示される箇所)から遷移が始まる． +青のStart，EndはCopyの始めと終わりである． +実際にはleftDownなどはleftDown1，leftDown2のような複数のCodeGearで構成され， +それぞれでStackの操作やアロケート，ノードの存在確認を行う． +Upはすでに木全体を辿ったかどうかを判定し， +辿っていた場合はswap CodeGearへ遷移を行う． +swapはコピー元の木とコピー先の木を入れ替える． +これはCopying GCにおけるFrom領域とTo領域を入れ替える操作を想定している． - +\begin{figure}[ht] + \begin{center} + \includegraphics[width=160mm]{fig/copy_algo3.png} + \end{center} + \caption{Copy時のCodeGearの大まかな遷移} + \label{fig:CopyCGTransition} +\end{figure} -% TODO: バックアップのフローを図にしたい +\section{コピーの実装の詳細} + \chapter{まとめと今後の課題}
--- a/Paper/src/CopyRedBlackTree.cbc Sun Jan 28 15:52:08 2024 +0900 +++ b/Paper/src/CopyRedBlackTree.cbc Mon Jan 29 13:41:22 2024 +0900 @@ -1,93 +1,242 @@ __code copyRedBlackTree(struct RedBlackTree* tree) { - tree->current = tree->root; - struct Stack* nodeStack = tree->nodeStack; - struct Node* oldNode = tree->current; - struct Node* newNode = tree->newNode; - tree->previous = newNode; - newNode = oldNode; - goto nodeStack->push((union Data*)newNode, leftDown); -} + printf("copyRedBlackTree\n"); -__code leftDown(struct RedBlackTree* tree, struct Stack* inputStack, struct Stack* outputStack) { - struct Node* newNode = &ALLOCATE(context, Node)->Node; - newNode->key = tree->current->key; - // newNode->value = tree->current->value; - newNode->value = (union Data*)new Integer(); - ((Integer*)newNode->value)->value = ((Integer*)tree->current->value)->value; - newNode->color = tree->current->color; - newNode->right = tree->current->right; - struct Stack* nodeStack = tree->nodeStack; - printf("leftDown\n"); - goto nodeStack->push(newNode, leftDown1); -} + tree->current = tree->root; + tree->copied = 0; -__code leftDown1(struct RedBlackTree* tree, struct Stack* inputStack, struct Stack* outputStack) { - struct Stack* nodeStack = tree->nodeStack; - printf("leftDown1\n"); - if (tree->current->left) { - goto leftDown(tree->current->left, inputStack, outputStack); - } else if (tree->current->right) { - goto rightDown(tree->current->right, inputStack, outputStack); - } else { - goto nodeStack->pop(up); - } -} - -__code rightDown(struct RedBlackTree* tree, struct Stack* inputStack, struct Stack* outputStack) { + struct Stack* toStack = tree->toStack; struct Node* newNode = &ALLOCATE(context, Node)->Node; newNode->key = tree->current->key; newNode->value = (union Data*)new Integer(); ((Integer*)newNode->value)->value = ((Integer*)tree->current->value)->value; newNode->color = tree->current->color; - newNode->right = tree->current->right; - tree->current = tree->current->right; - struct Stack* nodeStack = tree->nodeStack; - printf("rightDown\n"); - goto nodeStack->push(newNode, leftDown); + + goto toStack->push(newNode, leftDown); +} + +// +// leftDown*() +// current->leftがある場合、コピーしてから降りる。 +// ない場合はrightを見に行く(rightDown) +// + +__code leftDown(struct RedBlackTree* tree) { + printf("leftDown\n"); + struct Stack* toStack = tree->toStack; + + goto toStack->get(leftDown1); } -__code up(struct Node* node, struct RedBlackTree* tree, struct Stack* inputStack, struct Stack* outputStack) { +__code leftDown1(struct RedBlackTree* tree, struct Stack* stack) { + printf("leftDown1\n"); + + if (tree->current->left == NULL) { + goto rightDown(); + } + + struct Stack* toStack = tree->toStack; + struct Node* newNode = &ALLOCATE(context, Node)->Node; + struct Node* data = (Node*)(stack->data); + newNode->key = tree->current->left->key; + newNode->value = (union Data*)new Integer(); + ((Integer*)newNode->value)->value = ((Integer*)tree->current->left->value)->value; + newNode->color = tree->current->left->color; + + if(data) { + data->left = newNode; + } + + // 新規leftノードをpushしている + goto toStack->push(newNode, leftDown2); +} + +// 実際にDownする +__code leftDown2(struct RedBlackTree* tree) { + printf("leftDown2\n"); struct Stack* nodeStack = tree->nodeStack; - struct Node* newNode = tree->newNode; - printf("up\n"); - if (node->left) { - tree->current = node->right; - node->left = newNode; - goto nodeStack->push((union Data*)node, rightDown); - } else { - node->right = newNode; - newNode = node; - goto nodeStack->isEmpty(popWhenNoEmpty, popWhenEmpty); + struct Node* oldNode = tree->current; + + tree->current = tree->current->left; + + goto nodeStack->push((union Data*)oldNode, leftDown3); +} + +__code leftDown3(struct RedBlackTree* tree) { + printf("leftDown3\n"); + struct Stack* nodeStack = tree->nodeStack; + + if (tree->current) { + goto leftDown(tree); + } else if (tree->current == NULL) { + goto nodeStack->pop(leftDown4); } } -// upするときにstackの情報を元にcurrentを付け替えないといけないのでは？ -__code up1(struct Node* node, struct RedBlackTree* tree, struct Stack* inputStack, struct Stack* outputStack) { +__code leftDown4(struct RedBlackTree* tree, struct Stack* stack) { + printf("leftDown4\n"); + struct Node* data = (Node*)(stack->data); + + tree->current = data; + + goto up(); +} + +__code rightDown(struct RedBlackTree* tree) { + printf("rightDown\n"); struct Stack* nodeStack = tree->nodeStack; - printf("up1\n"); - goto nodeStack->pop(up2); + + goto nodeStack->isEmpty(rightDownWhenNoEmpty, rightDownWhenEmpty); +} + +__code rightDownWhenNoEmpty(struct RedBlackTree* tree) { + printf("rightDownWhenNoEmpty\n"); + struct Stack* toStack = tree->toStack; + + goto toStack->get(rightDown1); +} + +__code rightDownWhenEmpty(struct RedBlackTree* tree) { + printf("rightDownWhenEmpty\n"); + struct Stack* toStack = tree->toStack; + + tree->copied = 1; + + goto toStack->get(rightDown1); } -__code up2(struct Node* node, struct RedBlackTree* tree, struct Stack* inputStack, struct Stack* outputStack) { - printf("up2\n"); - tree->current->right = node->right; - goto up(tree, inputStack, outputStack); +__code rightDown1(struct RedBlackTree* tree, struct Stack* stack) { + printf("rightDown1\n"); + + if (tree->current->right == NULL) { + goto up(); + } + + struct Stack* toStack = tree->toStack; + struct Node* newNode = &ALLOCATE(context, Node)->Node; + struct Node* data = (Node*)(stack->data); + newNode->key = tree->current->right->key; + newNode->value = (union Data*)new Integer(); + ((Integer*)newNode->value)->value = ((Integer*)tree->current->right->value)->value; + newNode->color = tree->current->right->color; + + if(data) { + data->right = newNode; + } + + goto toStack->push(newNode, rightDown2); +} + +// 実際にDownする +__code rightDown2(struct RedBlackTree* tree) { + printf("rightDown2\n"); + struct Stack* nodeStack = tree->nodeStack; + struct Node* oldNode = tree->current; + + tree->current = tree->current->right; + + goto nodeStack->push((union Data*)oldNode, rightDown3); +} + +__code rightDown3(struct RedBlackTree* tree) { + printf("rightDown3\n"); + struct Stack* toStack = tree->toStack; + if (tree->current) { + goto leftDown(tree, toStack); + } else { + goto toStack->pop2(rightDown); + } } -__code popWhenEmpty(struct Node* node, struct RedBlackTree* tree, struct Stack* inputStack, struct Stack* outputStack, __code next(...)) { - // treeの入れ替え - struct Tree* newTree = new Tree(); - struct RedBlackTree* newRedBlackTree = new RedBlackTree(); - newTree->tree = (union Data*)newRedBlackTree; - newRedBlackTree->root = tree->newNode; - newRedBlackTree->current = tree->newNode; - tree = newRedBlackTree; - printf("popWhenEmpty\n"); - goto next(...); +// +// upしつつright見つつ +// NULLからのup +// nodeStackが空だったらtreeの入れ替えへ +// +__code up(struct RedBlackTree* tree) { + printf("up\n"); + struct Stack* nodeStack = tree->nodeStack; + + goto nodeStack->pop(up1); +} + +__code up1(struct RedBlackTree* tree, struct Stack* stack) { + printf("up1\n"); + struct Stack* toStack = tree->toStack; + struct Node* data = (Node*)(stack->data); + + tree->current = data; + + if (tree->current == NULL) { + goto swap(tree); + } + + goto toStack->pop(up2); +} + +// rightを見てさらにupするか考える +__code up2(struct RedBlackTree* tree) { + printf("up2\n"); + struct Stack* toStack = tree->toStack; + + if (tree->current->right) { + // toStackのtopにrightがあればup(すでにコピー済みなので) + // それがNULLならup3(rightDown)(そこからupしてきたのでNULLであるということはまだコピーできていないということになる(leftからのupをしたということ)) + goto up4(tree); + } + + goto toStack->pop(up); +} + +__code up4(struct RedBlackTree* tree) { + printf("up4\n"); + struct Stack* toStack = tree->toStack; + + goto toStack->get(up0); } -__code popWhenNoEmpty(struct Node* node, struct RedBlackTree* tree, struct Stack* inputStack, struct Stack* outputStack) { +__code up0(struct RedBlackTree* tree, struct Stack* stack) { + printf("up0\n"); + struct Node* toTree = (Node*)(stack->data); + + if (toTree->right) { + goto up(tree); + } else { + goto up3(tree); + } + +} + +__code up3(struct RedBlackTree* tree) { + printf("up3\n"); struct Stack* nodeStack = tree->nodeStack; - printf("popWhenNoEmpty\n"); - goto nodeStack->pop(up1); + + // nodeStack->isEmptyはupの最初にやるべき処理 + goto nodeStack->isEmpty(rightDown, swap); +} + +__code swap(struct RedBlackTree* tree) { + printf("swap\n"); + if (tree->copied) { + goto swap1(tree); + } + goto rightDown(tree); +} + +__code swap1(struct RedBlackTree* tree) { + printf("swap1\n"); + struct Stack* toStack = tree->toStack; + goto toStack->pop(swap2); +} + +__code swap2(struct RedBlackTree* tree, struct Stack* stack, __code next(...)) { + printf("swap2\n"); + struct Node* toTree = (Node*)(stack->data); + struct RedBlackTree* newRedBlackTree = new RedBlackTree(); + newRedBlackTree->root = toTree; + newRedBlackTree->current = toTree; + tree = newRedBlackTree; + + printf("copied\n"); + + goto next(...); } \ No newline at end of file
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/Paper/src/CopyRedBlackTree.h Mon Jan 29 13:41:22 2024 +0900 @@ -0,0 +1,13 @@ +typedef struct RedBlackTree <> impl Tree { + struct Node* root; + struct Node* current; // reading node of original tree; + struct Node* previous; // parent of reading node of original tree; + struct Node* newNode; // writing node of new tree; + struct Node* parent; + struct Node* grandparent; + struct Stack* nodeStack; + struct Stack* toStack; + __code findNodeNext(...); + int result; + int copied; +} RedBlackTree; \ No newline at end of file
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/Paper/src/TreeCopy.h Mon Jan 29 13:41:22 2024 +0900 @@ -0,0 +1,9 @@ +typedef struct Tree<> { + union Data* tree; + struct Node* node; + __code put(Impl* tree, Type* node, __code next(...)); + __code get(Impl* tree, Type* node, __code next(...)); + __code remove(Impl* tree, Type* node, __code next(...)); + __code copy(Impl* tree, __code next(...)); + __code next(...); +} Tree; \ No newline at end of file
--- a/TODO.md Sun Jan 28 15:52:08 2024 +0900 +++ b/TODO.md Mon Jan 29 13:41:22 2024 +0900 @@ -8,10 +8,10 @@ - [x] レプリケーションの説明 - [x] Nodeの説明 -- [ ] 4章 +- [x] stackの説明ある？(Nodeを積むよという話) +- [x] RedBlackTree構造の説明間違っているので修正 - [ ] DGMによる分散ファイルシステム - [ ] ALLOCの説明 -- [ ] RedBlackTree構造の説明間違っている - [ ] 実装の説明 - [ ] 評価 - [ ] まとめ
--- a/mindmaps/gears_fs_db.mm Sun Jan 28 15:52:08 2024 +0900 +++ b/mindmaps/gears_fs_db.mm Mon Jan 29 13:41:22 2024 +0900 @@ -482,7 +482,7 @@ <node TEXT="gotoによる軽量継続" ID="ID_726882949" CREATED="1703307895880" MODIFIED="1703307911540"/> <node TEXT="CodeGearの記述例" ID="ID_1731637915" CREATED="1703307784821" MODIFIED="1703307887307"/> </node> -<node TEXT="信頼性の保証を目的としたGearsOS" ID="ID_1315567458" CREATED="1701692210913" MODIFIED="1703311040671"> +<node TEXT="信頼性の保証を目的としたGearsOS" FOLDED="true" ID="ID_1315567458" CREATED="1701692210913" MODIFIED="1703311040671"> <node TEXT="3種類のGearsOS" ID="ID_1326415213" CREATED="1703309744902" MODIFIED="1703309750565"> <node TEXT="Gears Agda" ID="ID_1385168402" CREATED="1705044105795" MODIFIED="1705044111649"/> <node TEXT="Gears OS" ID="ID_1367848198" CREATED="1705044112079" MODIFIED="1705044114581"/> @@ -569,7 +569,7 @@ <node TEXT="RedBlackTreeのトランザクション" ID="ID_1088328123" CREATED="1701696247760" MODIFIED="1702112463420" HGAP_QUANTITY="14.75 pt" VSHIFT_QUANTITY="3.75 pt"/> </node> </node> -<node TEXT="GearsFileSystemにおけるGCとレプリケーション" ID="ID_1092227909" CREATED="1701690558237" MODIFIED="1705569492385" HGAP_QUANTITY="16.25 pt" VSHIFT_QUANTITY="-1.5 pt"> +<node TEXT="GearsFileSystemにおけるGCとレプリケーション" FOLDED="true" ID="ID_1092227909" CREATED="1701690558237" MODIFIED="1705569492385" HGAP_QUANTITY="16.25 pt" VSHIFT_QUANTITY="-1.5 pt"> <node TEXT="ファイルシステムの信頼性" FOLDED="true" ID="ID_200982245" CREATED="1704630258973" MODIFIED="1706091519737"> <node TEXT="信頼性に関する追加機能" ID="ID_1574949535" CREATED="1704630312069" MODIFIED="1704630320377"/> <node TEXT="GCやレプリケーションの機能がない" ID="ID_878946385" CREATED="1704630323433" MODIFIED="1704632961588"/> @@ -694,6 +694,10 @@ <node TEXT="Tree InterfaceのAPIにCopyを追加する" ID="ID_535524915" CREATED="1705735678228" MODIFIED="1705735715335"/> <node TEXT="RedBlackTreeのコピーとして実装する" ID="ID_878630835" CREATED="1706417169892" MODIFIED="1706417179625"/> </node> +<node TEXT="copyの使用方法" ID="ID_712774381" CREATED="1706429162944" MODIFIED="1706429182896"/> +<node TEXT="アルゴリズム" ID="ID_1706301205" CREATED="1706424874581" MODIFIED="1706424880284"/> +<node TEXT="それぞれのCodeGearの説明" ID="ID_1262953034" CREATED="1706424910753" MODIFIED="1706424918004"/> +<node TEXT="コード説明" ID="ID_1503273394" CREATED="1706424889067" MODIFIED="1706424905285"/> </node> <node TEXT="評価" ID="ID_1053436711" CREATED="1702112499515" MODIFIED="1702112509004"> <node TEXT="信頼性" ID="ID_1221084016" CREATED="1702289777950" MODIFIED="1702289781581"> @@ -716,7 +720,7 @@ <node TEXT="分散ファイルシステムのトポロジー形成" ID="ID_1837705741" CREATED="1704631962837" MODIFIED="1704631974676"/> <node TEXT="Christieを用いている" ID="ID_703384422" CREATED="1704631982827" MODIFIED="1704631995001"/> </node> -<node TEXT="バックアップやGCのタイミング" POSITION="left" ID="ID_1968325106" CREATED="1705995867783" MODIFIED="1705995947002"> +<node TEXT="バックアップやGCのタイミング" FOLDED="true" POSITION="left" ID="ID_1968325106" CREATED="1705995867783" MODIFIED="1705995947002"> <node TEXT="木の操作の度にGCしていては効率が悪い" ID="ID_1270257607" CREATED="1705995886579" MODIFIED="1705995983113"> <node TEXT="システムの状態によって処理を切り替える" ID="ID_835268540" CREATED="1705995987307" MODIFIED="1705995998232"/> <node TEXT="メモリがこれくらい使われている" ID="ID_708465587" CREATED="1705996000486" MODIFIED="1705996008587"/> @@ -737,7 +741,7 @@ </node> </node> </node> -<node TEXT="レプリケーション手法" POSITION="left" ID="ID_1667606869" CREATED="1705990967981" MODIFIED="1705990975745"> +<node TEXT="レプリケーション手法" FOLDED="true" POSITION="left" ID="ID_1667606869" CREATED="1705990967981" MODIFIED="1705990975745"> <node TEXT="bin log" ID="ID_1578494368" CREATED="1705990975951" MODIFIED="1705990978180"/> <node TEXT="WAL" ID="ID_173341311" CREATED="1705991115261" MODIFIED="1705991117448"> <node TEXT="Write Ahead Logging" ID="ID_885834048" CREATED="1705991256045" MODIFIED="1705991267446"/>