# HG changeset patch # User tatsuki # Date 1485237232 -32400 # Node ID da6a6eba893d2a94dd0a96188d1524587b43647e # Parent 99d965c02c457746885bc4358fa60427b6c6c454 commit diff -r 99d965c02c45 -r da6a6eba893d abstract.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/abstract.tex Tue Jan 24 14:53:52 2017 +0900 @@ -0,0 +1,3 @@ +\begin{abstract} +アブストラクトを書く +\end{abstract} diff -r 99d965c02c45 -r da6a6eba893d abstract_eng.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/abstract_eng.tex Tue Jan 24 14:53:52 2017 +0900 @@ -0,0 +1,18 @@ +\begin{abstract_eng} +Users of the Wev services is increasing by the diffusion of smartphone and tablet pc. +However it caused the webserver down. +Therefore, scalability is the important software factor for Web services today. +Scalability in distributed system is able to increase performance linearly when just added new node to system. +In order to provide scalability to Web services, database must have scalability. + +For study of scalable database, we are designing and developing a database Jungle which has non-destructive tree structure. +Non-destructive tree structure dose not destruct the data when data editing by creating new tree. + +In this paper, we implemented persistent and distributed database on jungle. +Distributed data on Jungle is developed by using Alice which is parallel distributed framework. +We confirm the data distribution between the server nodes on Jungle with our cluster system. +Also, we developed simple bulletinboard system with Jungle and key-value store database Cassandra. +We compared response time of Jungle and Cassandra using simple bulletinboard. +As a result, Jungle got better performance than Cassandra. + +\end{abstract_eng} diff -r 99d965c02c45 -r da6a6eba893d appendix.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/appendix.tex Tue Jan 24 14:53:52 2017 +0900 @@ -0,0 +1,10 @@ +\chapter*{発表履歴} +\addcontentsline{toc}{chapter}{発表文献} + +\begin{itemize} +\item{Java による授業向け画面共有システムの設計と実装, 大城信康, 谷成雄(琉球大学), 河野真治(琉球大学), オープンソースカンファレンス2011 Okinawa, Sep, 2011} +\item{Continuation based C の GCC 4.6 上の実装について,\\ 大城信康, 河野真治(琉球大学), \\ 第53回プログラミング・シンポジウム, Jan, 2012} +\item{GraphDB 入門 TinkerPop の使い方,\\大城信康, 玉城将士(琉球大学),\\第15回 Java Kuche, Sep, 2012} +\item{ディペンダブルシステムのための木構造を用いた合意形成データベースの提案と実装,\\ 大城信康, 河野真治(琉球大学), 玉城将士(琉球大学), 永山 辰巳(株式会社 Symphony),\\ 情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS), May, 2013} +\item{Data Segment の分散データベースへの応用, \\ 大城信康, 杉本優(琉球大学), 河野真治(琉球大学), \\ 日本ソフトウェア科学会30回大会 (2013年度) 講演論文集, Sep, 2013} +\end{itemize} diff -r 99d965c02c45 -r da6a6eba893d chapter1.tex --- a/chapter1.tex Tue Jan 17 18:47:09 2017 +0900 +++ b/chapter1.tex Tue Jan 24 14:53:52 2017 +0900 @@ -17,7 +17,7 @@ 部分について考察する。 本章ではまず破壊的木構造と、非破壊的木構造の説明をし、その後Jungleの提供しているAPIについて述べる。 -\subsection{破壊的木構造} +\section{破壊的木構造} 破壊的木構造の編集は, 木構造で保持しているデータを直接書き換えることで行う。 図\ref{fig:destractive}は破壊的木構造のにおけるデータ編集を表している。 @@ -30,12 +30,12 @@ \end{figure} 破壊的木構造は、編集を行う際に木のロックを掛ける必要がある。 -この時、データを受け取ろうと木を走査するスレッドは書き換えの終了を待つ必要があり、閲覧者が -いる場合は木の走査が終わるまで書き換えを待たなければならない。 +この時、データを受け取ろうと木を走査するスレッドは書き換えの終了を待つ必要があり、 +閲覧者がいる場合は木の走査が終わるまで書き換えを待たなければならない。 -\subsection{非破壊的木構造} -、データの編集を一度生成した木を上書きせず、ルートから編集を行うノードまでコピーを行い新しく木構造を構築し、そのルートをアトミックに入れ替えることで行う(図\ref{fig:nondestractive})。 -その際、編集に関係ないノードは参照を行い、複製元の木と共有する(図\ref{fig:nondestractive}の例ではノード1 、3、 4は編集に関係ないためノードAから参照を行い、過去の木と共有を行っている)。 +\section{非破壊的木構造} +データの編集を一度生成した木を上書きせず、ルートから編集を行うノードまでコピーを行い新しく木構造を構築し、そのルートをアトミックに入れ替えることで行う(図\ref{fig:nondestractive})。 +その際、編集に関係ないノードは参照を行い、複製元の木と共有する(図\ref{fig:nondestractive}の例ではノード1・3・4は編集に関係ないためノードAから参照を行い、過去の木と共有を行っている)。 \begin{figure}[htpb] \begin{center} @@ -47,9 +47,8 @@ 非破壊的木構造においてデータのロックが必要となる部分は、木のコピーを作り終えた後に ルートノードを更新するときだけである。 -データ編集を行っている間ロックが必要な破壊的木構造に比べ、編集中においてもデータの読み込みが -可能である。 -しかし、書き込み時の手間は大きくなる。 +データ編集を行っている間ロックが必要な破壊的木構造に比べ、編集中においてもデータの読み込みが可能であるが、 +書き込み時の手間は大きくなる。 \begin{figure}[htpb] \begin{center} @@ -59,10 +58,10 @@ \end{center} \end{figure} -\subsection{NodePath} +\section{NodePath} Jungleでは、木のノードの位置を{\tt NodePath}クラスを使って表す。 -{\tt NodePath}クラスはルートノードからスタートし、対象のノードまでの経路を、数字を用いて指し示すことで対象のノードの場所を表す。また、ルートノードは例外として-1と表記される。 -{\tt NodePath}クラスが{\tt < -1,1,2,3>} を表している際の例を図\ref{NodePath}に記す。 +{\tt NodePath}クラスはルートノードからスタートし、対象のノードまでの経路を数字を用いて指し示す。また、ルートノードは例外として-1と表記される。 +{\tt NodePath}クラスを用いて{\tt< -1,1,2,3>}を表している際の例を図\ref{NodePath}に記す。 \begin{figure}[htpb] \begin{center} @@ -72,10 +71,31 @@ \end{center} \end{figure} +\section{Either} +Jungleは、失敗する可能性のある関数では返り値を{ \tt Either}に包んで返す。 +AにはのError、Bには処理に成功した際の返り値の型が入る。 +Eitherは、AかBどちらかの値しか持たない。 +以下にEitherクラスが提供しているAPI(表\ref{EitherAPI})を記す。 +\begin{table}[htb] +\begin{center} +\caption{Eitherに実装されているAPI} +\begin{tabular}{|p{15em}|p{24em}|} \hline +{\tt boolean isA()} & EitherがAを持っているかどうかを調べる。持っている場合trueを返す。\\ \hline +{\tt boolean isB()} & EitherがBを持っているかどうかを調べる。持っている場合trueを返す。\\ \hline +{\tt A a()} & Aの値を取得する。\\ \hline +{\tt B b()} & Bの値を取得する。\\ \hline +\end{tabular} +\label{EitherAPI} +\end{center} +\end{table} -\subsection{木の生成} +{\tt Either}は、{\tt isA()}を用いて関数が{\tt Error}を返していないかを調べる。 +{\tt Error}でない場合は{\tt b()}で関数の返り値を取得する。 + + +\section{木の生成} 初めにJungleにおける木の生成について述べる。 -Jungleは複数の木を、名前を利用して管理しており、名前を利用することで作成・編集・削除を行う。 +Jungleは複数の木構造を、名前を利用して作成・編集・削除を行い管理している。 以下にJungleクラスが提供している木の生成・管理を行うAPI(表\ref{jungleAPI})を記す。 \begin{table}[htb] @@ -90,7 +110,7 @@ \end{table} -\subsection{JungleTree} +\section{JungleTree} Jungleは複数の木の集合で出来ている。 ユーザーは、この木に対して検索や編集を行う。 以下にJungleTreeクラスが提供しているAPI(表\ref{JungleTreeAPI})を記す @@ -101,9 +121,9 @@ {\tt TreeNode getRootNode()} &木のルートノードを取得する。 \\ \hline {\tt long revision()} & 木のバーションを取得する。初めは0から始まり、木への変更がCommitされる度に1上昇する。 \\ \hline {\tt JungleTreeEditor getJungleTreeEditor()} & 木へ変更を加えるEditorを取得する。\\ \hline -{\tt Either getOldTree(long revision)} & 引数で指定したrevisionの木を取得する。 \\ \hline +{\tt Either getOldTree(long revision)} & 引数で指定したint revisionに等しいバージョンの木を取得する。 \\ \hline {\tt InterfaceTraverser getTraverser()} & 木の検索を行うTraverserを取得する。 \\ \hline -{\tt Either getNodeOfPath(NodePath path)} & {\tt NodePathで指定した位置値なるノードを取得する。} \\ \hline +{\tt Either getNodeOfPath(NodePath path)} & {\tt NodePathで指定した位置と値なるノードを取得する。} \\ \hline {\tt NodePath getNodePath(TreeNode node)} & 引数で渡したノードの位置を表す{\tt NodePath}を返す。\\ \hline \end{tabular} \label{JungleTreeAPI} @@ -111,30 +131,8 @@ \end{table} -\subsection{Either} -Jungleは、失敗する可能性のある関数では返り値を{ \tt Either}に包んで返す。 -AにはのErrorを、Bには処理に成功した際に入る値が入る。 -Eitherは、AかBどちらかの値しか持たない。 -以下にEitherクラスが提供しているAPI(表\ref{EitherAPI})を記す。 -\begin{table}[htb] -\begin{center} -\caption{Eitherに実装されているAPI} -\begin{tabular}{|p{15em}|p{24em}|} \hline -{\tt boolean isA()} & EitherがAを持っているかどうかを調べる。持っている場合trueを返す。\\ \hline -{\tt boolean isB()} & EitherがBを持っているかどうかを調べる。持っている場合trueを返す。\\ \hline -{\tt A a()} Aの値を取得する。& \\ \hline -{\tt B b()} Bの値を取得する。& \\ \hline -\end{tabular} -\label{EitherAPI} -\end{center} -\end{table} - -{\tt Either}は、{\tt isA()}を用いて関数が{\tt Error}を返していないかを調べる。 -{\tt Error}でない場合は{\tt b()}で関数の返り値を取得する。 - - -\subsection{TreeNode} -Jungleが保持している木は、複数のノードの集合で出来ている。 +\section{TreeNode} +Jungleの木構造は、複数のノードの集合で出来ている。 ノードは、自身の子のListと属性名と属性値の組でデータを持つ。 ノードに対するアクセスは、表\ref{TreeNodeAPI}に記述されているAPIを用いて行われる。 @@ -150,7 +148,7 @@ \end{table} Childrenクラスは表\ref{Children}に記述されたAPIを、Attributeクラスは表\ref{Attribute}に記述されたAPIを提供する。 -これらを利用しノードの子供や、保持する値にアクセスする。 +これらを利用しノードが保持している値や、子供にアクセスする。 \begin{table}[htbH] \begin{center} \caption{Childrenに実装されているAPI} @@ -163,11 +161,6 @@ \end{table} -関数{\tt children.at(int num)}が返す{\tt Either\textless Error,TreeNode\textgreater} オブジェクトは、{\tt isA() }で{\tt Error}かどうかをチェックすることができる。 -{\tt Error}でない場合は{\tt b()}で{\tt TreeNode}オブジェクトを取り出すことができる。 - - - \begin{table}[htbH] \begin{center} @@ -188,25 +181,25 @@ Children children = root.getChildren(); Either either = children.at(2); if (either.isA()) - throw new IOException(); + return either.a(); TreeNode child = either.b(); Attribute attribute = child.getAttribute(); String value = attribute.getString("name"); \end{lstlisting} \begin{enumerate} - \item Jungleから名前を指定して木を取得する。 + \item Jungleから名前が{\tt "TreeName"}の木を取得する。 \item 取得した木のルートノードを取得する。 - \item 木のルートノードから{\tt Children}型の子ノードを取得する。 - \item 変数{\tt children}から2番目の子供を取得する。 - \item 2番目の子供が取得できたかを調べる。 - \item 取得できていなかった場合{\tt Exception}を投げる。 - \item 取得に成功していた場合、{\tt either}から子ノードを受け取る。 + \item 木のルートノードから{\tt Children}を取得する。 + \item 3で取得した{\tt Children}から2番目の子供を取得する。 + \item 関数{\tt Either.isA()}を用いて、2番目の子供が取得できたかを調べる。 + \item 取得できていなかった場合{\tt Either.a()}でErrorを返す。 + \item 取得に成功していた場合、{\tt Either.b()}で子ノードを取得する。 \item 取得した子ノードから{\tt Attribute}クラスを取得する。 - \item 取得した{\tt attribute}から属性名 {\tt name}がペアの値を取得する。 + \item 取得した{\tt attribute}から属性名 {\tt name}とペアの属性値を取得する。 \end{enumerate} -\subsection{木の編集API} +\section{木の編集API} Jungleの木の編集は{\tt JungleTreeEditor}クラスを用いて行われる。 {\tt JungleTreeEditor}クラスには編集を行うために、表\ref{editor}で定義されているAPIが実装されている。 @@ -215,17 +208,17 @@ \caption{Editorに実装されているAPI} \begin{tabular}{|p{15em}|p{24em}|} \hline {\tt Either addNewChildAt( NodePath path, int pos)} & - 変数{\tt path}で指定した場所にある、ノードの子供の変数{\tt pos}で指定した位置子ノードを追加する\\ \hline + 変数{\tt path}で指定した場所にあるノードの、変数{\tt pos}で指定した位置に子ノードを追加する\\ \hline {\tt Either deleteChildAt( NodePath path,int pos)} & - 変数{\tt path}で指定した場所にある、ノードの子供の変数{\tt pos}で指定した位置の子ノードを削除する。 \\ \hline + 変数{\tt path}で指定した場所にあるノードの、変数{\tt pos}で指定した位置の子ノードを削除する。 \\ \hline {\tt Either putAttribute( NodePath path,String key,ByteBuffer value)} & 変数{\tt path}で指定した場所にあるノードに、属性名 変数{\tt key} 属性値 変数{\tt value} のペアで値を挿入する。 \\ \hline {\tt Either< Error, JungleTreeEditor> deleteAttribute( NodePath path,String key)}& - 変数{\tt path}で指定した場所にあるノードが持つ、属性名 変数{\tt key}とペアで保存されているデータを削除する。\\ \hline + 変数{\tt path}で指定した場所にあるノードが持つ、属性名 変数{\tt key}とペアで保存されている属性値を削除する。\\ \hline {\tt Either moveChild( NodePath path,int num,String move)} & - 変数{\tt path}で指定した場所にある、ノードの変数{\tt num}で指定された位置の子供を変数{\tt move}の方向に移動させる。 \\ \hline + 変数{\tt path}で指定した場所にあるノードの、変数{\tt num}で指定された位置の子供を変数{\tt move}の方向に移動させる。 \\ \hline {\tt Either pushPop()} & - ルートノードの上に新しいルートノードを追加する。線形の木を作る際に使用することで計算量をO(n)からO(1)にできる。\\ \hline + ルートノードの上に新しいルートノードを追加する。線形の木を作る際に使用することで木の変更の手間をO(n)からO(1)にできる。\\ \hline {\tt Either success()} & 木へ行った変更をコミットする。自分が編集を行っていた間に、他のJungleTreeEditorクラスによって木が更新されていた場合、コミットは失敗する。 \\ \hline \end{tabular} @@ -246,7 +239,7 @@ DefaultNodePath editNodePath = new DefaultNodePath(); Either either = editor.addNewChildAt(editNodePath, 0); if (either.isA()) - throw new IllegalStateException(); + return either.a(); editor = either.b(); editor.success(); \end{lstlisting} @@ -256,7 +249,7 @@ \item 次に変更するノードの場所を示す、{\tt NodePath}クラスを作成する。 \item 関数{\tt editor.addNewChildAt()}を用いて、変数{\tt path}で指定したノードの子供の0番目に子ノードを追加する。 \item 返り値の変数{\tt either}が{\tt Error}クラスを保持していないか(編集に失敗していないか)を確認する。 - \item {\tt Error}クラスを保持していた場合{\tt Exception}を投げる。 + \item {\tt Error}クラスを保持していた場合{\tt Either.a()}でErrorを返す。 \item 編集に成功していた場合、編集後木を持った、{\tt JungleTreeEditor}クラスを取得する。 \item 取得した{\tt JungleTreeEditor}クラスを用いて木の変更をコミットする。 \end{enumerate} @@ -265,17 +258,17 @@ これらのAPIにより、Jungleは木構造を格納、編集する機能を持っている。 -\subsection{検索APIの実装} +\section{検索APIの実装} これまでに紹介したAPIにより、Jungleは木構造を構築できるようになった。 しかし、木に問い合わせを行う検索APIが実装されていなかったため、属性名 {\tt key} 属性値 {\tt value}の組で検索を行うAPIの実装を、木の走査を行う{\tt Traverser}クラス内に、lambda式を用いて行った。 以下に検索を行う関数{\tt find}の定義を記述する。 \begin{lstlisting}[frame=lrbt,label=query,numbers=left] -public Iterator find(Query query, - String key, String searchValue); +public Iterator find(Query query, String key, String searchValue); \end{lstlisting} -関数{\tt find}は引数に、{\tt Query query}、{\tt String key}、{\tt String value}の3つの引数を取り、条件に一致したノードの{\tt Iterator}インタフェースを返す。 -第1引数には、探索の条件を記述する関数{\tt boolean comdition(TreeNode)}を定義した{\tt Interface Query}を。 -第2、第3引数の、{\tt String key、String value}はIndexを用いた絞込みに使用する。{\tt 関数find}の使用例を以下に記す + +関数{\tt find}は、第一引数には、探索の条件を記述する関数{\tt boolean comdition(TreeNode)}を定義した{\tt Query}を。 +第二、第三引数には、Indexを用いた絞込に使用する{\tt String key、String value}を取り、条件に一致したノードの{\tt Iterator}を返す。 +{\tt 関数find}の使用例を以下に記す \begin{lstlisting}[frame=lrbt,label=find,numbers=left] InterfaceTraverser traverser = tree.getTraverser(true); @@ -304,20 +297,19 @@ このコードの結果として、{\tt ryukyu}に所属する、名前が{\tt kanagawa}のデータが入ったノードが取得できる。 -\subsection{Indexの実装} +\section{Indexの実装} Jungleには、検索の際に使用するIndexが無かったため、実装を行った。 -Jungleは、非破壊的木構造というデータ構造上、過去の版の木構造を全て保持しているため、全ての版に独立したIndexが必要となる。 -そのため、前の版のIndexを破壊すること無く、Indexを更新する必要があった。 -既存のTreeMapでは、一度Indexの複製を行った後更新する必要があったため、Indexの更新オーダーがO(n)となっていた。 -よって、非破壊TreeMapを自作し、それを用いてIndexの実装を行った。 +Jungleは、非破壊的木構造というデータ構造上、過去の版の木構造を全て保持している。 +よって、全ての版に独立したIndexが必要となるため、前の版のIndexを破壊すること無く、Indexを更新する必要があった。 +既存のTreeMapでは、一度Indexの複製を行ない、その後更新する必要があったため、Indexの更新オーダーがO(n)となっていた。 +その問題を解決するため、非破壊TreeMapを自作し、それを用いてIndexの実装を行った。 このTreeMapは、Jungleと同じようにルートから変更を加えたノードまでの経路の複製を行い、データの更新を行った際、前の版と最大限データを共有した新しいTreeMapを作成する。 Jungleとの違いは、木の回転処理が入ることである。 これにより複数の版全てに対応したIndexをサポートすることが可能になった。 以下にJungleにおけるIndexの型を記述する \begin{lstlisting}[frame=lrbt,label=index,numbers=left] -TreeMap node> index> indexMap +TreeMap node> index> indexMap \end{lstlisting} JungleのIndexは{\tt IndexMap}内に保持されている。 @@ -340,15 +332,15 @@ \begin{enumerate} \item {\tt indexMap}に、今回検索で使用する属性名 {\tt name}を使用して{\tt get("name")}を行う。すると属性名 {\tt name}に対応したIndexが、{\tt Optional}クラスで包まれて返ってくる。 -\item {\tt Optional}オブジェクトに対して、中身を保持しているか(属性名 {\tt name}に対応したIndexをJungleが持っているか)を調べる。 +\item {\tt Optional}オブジェクトに対して、中身を保持しているか(属性名 {\tt name}に対応したIndexを木が持っているか)を調べる。 \item 持っていなかった場合、空の{\tt Iterator}オブジェクトを返す。 \item 持っていた場合、{\tt Optional}オブジェクトからIndexを取得する。 -\item 取得したIndexに、検索で使用する属性値{\tt kanagawa}で{\tt get()}を行う。属性名 {\tt name} 属性値{\tt kanagawa}の値を持つノードのリストが、{\tt Optional}クラスに包まれて返ってくる。 +\item 取得したIndexに、検索で使用する属性値{\tt kanagawa}で{\tt get()}を行う。すると、属性名 {\tt name} 属性値{\tt kanagawa}の値を持つノードのリストが、{\tt Optional}クラスに包まれて返ってくる。 -\item {\tt Optional}オブジェクトに対して中身を保持しているか(属性名 {\tt name} 属性値 {\tt kanagawa}を持つノードをJungleが持っているか)を調べる。 +\item {\tt Optional}オブジェクトに対して中身を保持しているか(属性名 {\tt name} 属性値 {\tt kanagawa}を持つノードを木が持っているか)を調べる。 \item 持っていなかった場合、空の{\tt Iterator}オブジェクトを返す。 @@ -356,80 +348,25 @@ \end{enumerate} -\subsection{Log} - JungleはこれらのAPIにより、木構造を格納、編集、検索する機能を持っている。 - -\begin{comment} -\subsection{NodeOperation} -Jungle による最小のデータ編集は Node の編集を指す. -Node 編集のために API が用意されており, この API は NodeOperation と呼ばれる. -NodeOperation には次の4つの API が用意されている. -\begin{itemize} -\item \verb|addNewChild(NodePath _path, int _pos)|\\ - NodePath で指定された Node に子供となる Node を追加する API である. - pos で指定された番号に子供として追加を行う. - \item \verb|deleteChildAt(NodePath _path, int _pos)|\\ - NodePath と pos により指定される Node を削除する API である. - \item \verb|putAttribute(NodePath _path, String _key, ByteBuffer _value)|\\ - Node に attribute を追加する API である. - NodePath は attribute を追加する Node を指す. - \item \verb|deleteAttribute(NodePath _path, String _key)|\\ - \verb|_key| が示す attribute の削除を行う API である. - NodePath は Node を示す. - \end{itemize} - - NodeOperationはNodePathとセットで扱わなければならず, このセットを - TreeOperationという. - TreeOperationが1つのデータ編集の単位になるが, これはあくまで最小のデータ編集の単位である. - Jungle によるデータの編集はTreeOperationが複数集まった単位でcommitされていく. - このTreeOperationの集まりをTreeOperationLogという. - - \subsection{TreeOperationLog} - Jungle 内部ではTreeOperationは順次ログに積まれていき, 最終的に - commitされることで編集が完了する. - この時, ログに積まれた複数のTreeOperationはTreeOperationLogとして扱われる. - TreeOperationLogの仕様をソースコード\ref{src:treeoperationlog}に示す. - \begin{lstlisting}[frame=lrbt,label=src:treeoperationlog,caption=TreeOperationLogの仕様,numbers=left] - public interface TreeOperationLog extends Iterable +\subsection{Log} +Jungle は、 Editor を用いて木に編集を加える際、使用した API に応じて対応する NodeOperation を作成する。 +NodeOperation は NodePath とペアで扱わなければならず、このペアを TreeOperation という。 +Jungle によるデータの編集は TreeOperation が複数集まった単位で commit されていく. +この TreeOperation の集まりを TreeOperationLog という。 +TreeOperationLogの仕様をソースコード\ref{src:treeoperationlog}に示す. +\begin{lstlisting}[frame=lrbt,label=src:treeoperationlog,caption=TreeOperationLogの仕様,numbers=left] +public interface TreeOperationLog extends Iterable { public TreeOperationLog add(NodePath _p,NodeOperation _op); public TreeOperationLog append(TreeOperationLog _log); public int length(); } \end{lstlisting} -　\verb|Iterable|を継承しているためIteratorによりTreeOperationを取り出せるようになっている. -addやappendメソッドを使ってTreeOperationを積み上げていくことができる. -次にデータ編集により発生するTreeOperationLogの具体的な例を示す(ソースコード\ref{src:treelog}). -\begin{lstlisting}[frame=lrbt,label=src:treelog,caption=トポロジーマネージャーの利用,numbers=left] -[APPEND_CHILD:<-1>:pos:0] -[PUT_ATTRIBUTE:<-1,0>:key:author,value:oshiro] -[PUT_ATTRIBUTE:<-1,0>:key:mes,value:hello] -[PUT_ATTRIBUTE:<-1,0>:key:timestamp,value:0] -\end{lstlisting} -　このログはルートノードに対し子ノードを追加し, 追加した子ノードに attribute を3つ追加する際に出力されるログである(図\ref{fig:treeoperationlog}). +\verb|Iterable|を継承しているためIteratorによりTreeOperationを取り出せるようになっている。 +addやappendメソッドを使ってTreeOperationを積み上げていくことができる。 -大文字の英字は実行した NodeOperation の種類を表す. -\verb|<>| により囲まれている数字は NodePath を示す. -NodePath の表記以降は Node の position や attribute の情報を表している. \newpage -\begin{figure}[htpb] -\begin{center} -\includegraphics[scale=0.7]{figures/treeoperationlog1.pdf} -\caption{TreeOperationLog の具体例} -\label{fig:treeoperationlog} -\end{center} -\end{figure} - -ログの動作を表している図\ref{fig:treeoperationlog}の説明を行う. -まず, \verb|APPEND_CHILD:<-1>:pos:0|によりRoot Nodeの0番目の子供となるNodeの追加を行う. -次に, 追加を行ったNodeに対して\verb|PUT_ATTRIBUTE<-1,0>| により attribute の情報を持たせていく. -attributeの内容に作者の情報を表すauther, メッセージの内容を表すmes, そしてタイムスタンプ -をtimestampとそれぞれキーにすることで追加される. - -以上が掲示板プログラムにおける1つの書き込みで発生する TreeOperationLog である. -\end{comment} -\newpage diff -r 99d965c02c45 -r da6a6eba893d chapter2.tex --- a/chapter2.tex Tue Jan 17 18:47:09 2017 +0900 +++ b/chapter2.tex Tue Jan 24 14:53:52 2017 +0900 @@ -1,27 +1,22 @@ -\chapter{Differential Tree} -前章でも述べたが、Jungleの木の変更の手間は木の形によって異なる。 -特に線形の木を構築した場合は変更の手間がO(n)となってしまう。 -Jungleは、線形の木をO(1)で変更するために、ルートノードを追加していくPushPopの機能を持つ。 -しかし、PushPopではルートノードを追加していくため、図\ref{fig:pushpop}のようにノードの並びが逆順になってしまう。 -ノードを正順で線形の木を構築する際は、PushPopを使用できないため、O(n)で木の編集を行う必要がある。 +\chapter{Differential Jungle Tree} +Jungleの木の変更の手間は木の形によって異なる。 +特に線形の木は、変更の手間がO(n)となってしまう。 +線形の木をO(1)で変更するために、Jungleは、ルートノードを追加していくPushPopの機能を持つ。 +しかし、PushPopはルートノードを追加していくため、図\ref{fig:pushpop}のようにノードの並びが逆順になってしまうため、正順の木を構築する際は、PushPopを使用できない。 \begin{figure}[htpb] \begin{center} -\includegraphics[scale=0.5]{figures/PushPopDemerit.pdf} +\includegraphics[scale=0.3]{figures/PushPopDemerit.pdf} \caption{PushPopの問題点} \label{fig:pushpop} \end{center} \end{figure} -その問題を解決するために、木の編集の手間をO(1)で、正順の木を構築するDifferential Treeの実装を行った。 -本章ではDifferential Treeについて述べる。 +その問題を解決するために、木の編集の手間をO(1)で、正順の木を構築できるDifferential Jungle Treeの実装を行った。 +Differential Jungle Treeは、木のバージョンごとに、自身の末尾のノードを持つ。 \newpage -\section{Differential Treeの設計} -Jungleの木は、過去の木を全て保持している必要があるため、過去の木を破壊することなく編集する必要がある。 -しかし、編集したノードからルートまでの複製を行うと、木の変更の手間はO(n)になってしまう。 -よって、木の複製を行わず過去の木を破壊することなく、木の編集を行う必要がある。 -Differential Treeでは、末尾ノードを使用することで、O(1)での木の編集を可能にした。 +\section{Differential Tree Context} Jungleの木はTreeContextというオブジェクトに自身の木の情報を保持する。 表\ref{TreeContext}にTreeContextが保持するデータを記述する。 @@ -41,14 +36,15 @@ \end{center} \end{table} -TreeContextに、木の末尾ノードを追加したDifferential Tree Contextの実装を行うことで、Differential Treeに末尾ノードを保持させた。 +Differential Jungle Treeでは、現在のバージョンの木構造の末尾ノード保持することが可能な DifferentialTreeContext 作成した。 \section{末尾ノードを使用した木の編集} -Differential Treeの木の編集は、Default Treeと同じようにEditorを使用して行う。 -Default Treeとの違いは、Default TreeのEditorは、木の編集を行った後、木の複製を行い過去の木を保持するのに対して、Differential TreeのEditorは、Sub Treeを保持しており、そのSub Treeに対して破壊的に編集を行う。 +Differential Jungle Treeの木の編集は、Default Jungle Treeと同じようにEditorを使用して行う。 +違いは、Default Jungle TreeのEditorは、木の編集を行った後、木の複製を行い過去の木を保持するのに対して、Differential Jungle TreeのEditorは、Sub Treeを保持しており、そのSub Treeに対して破壊的に編集を行う。 そして、Commitを行う際に、構築したSub Treeを末尾ノードにAppendすることで木の編集を行う。 そうすることで、木の複製を行う必要が無いため、木の変更の手間はO(1)で行える。 + また、Differential TreeはSub Treeに対する変更しか行えないため、一度Commitした木に対して変更は行えない。 図\ref{fig:EditDifTree}にDifferential Treeの編集の流れを記述する。 @@ -67,11 +63,49 @@ \item Commitを行い、Treeの末尾ノードにSub TreeをAppendする。 \end{enumerate} -また、Differential TreeのIndexのアップデートは、Sub Treeの中身をIndexに追加するだけで良い。 +また、Differential TreeのIndexのアップデートは、Commit 時に Sub Treeの中身をIndexに追加するだけで良い。 + + +\section{Differential Jungle Treeの整合性} + +Differential Jungle Treeに対する変更が競合した場合、先にCommitを行った方の変更が適応される。 +末尾ノードへのAppendは、破壊的な変更であるため、Commit成功後に行う。 +そうすることで、編集が競合した際の整合性を保っている。 + + +また、Differential Jungle Treeは、木を破壊的に変更する。 +よって、過去の木を取得し、変更を加えた場合、末尾ノードに複数のSub TreeがAppendされてしまい、木の整合性が崩れてしまう。 +その問題を解決するため、Differential Jungle Treeでは、末尾ノードは一つしか子ノードを持つことができない。 + +ソースコード\ref{src:Append}にSub TreeのAppend部分のコードを記述する。 + +\begin{lstlisting}[frame=lrbt,label=src:Append,caption=Sub TreeのAppend部分のコード,numbers=left] +Either appendSubTree(TreeNode subTreeRoot) { + TreeNode appendedNode = treeContext.getEndNode(); + TreeNodeChildren children = appendedNode.getChildren(); + if (children.size() != 0) + return DefaultEither.newA(APPEND_FAILD); + return children.addNewChildAt(0, subTreeRoot); +} +\end{lstlisting} + +ソースコード\ref{src:Append}の解説を行う。 + +\begin{enumerate} +\item 関数{\tt appendSubTree}でSub TreeのAppendを行う。引数にSub Treeのルートを持つ。 +\item TreeContextから末尾ノードを取得する。 +\item 末尾ノードからChildrenを取得する。 +\item 末尾ノードにSub TreeがすでにAppendされているか(子供を持っているか)を調べる。 +\item 他のSub TreeがAppendされている(今編集を行っているのが過去の木)場合、木のAppendは失敗するため、エラーを返す。 +\item そうでない場合、Sub Treeを末尾ノードにAppendする。 +\end{enumerate} + +このように、末尾ノードが複数の子を持つことを禁止することで、過去の木を取得した際の木の整合性を保証している。 \section{Commit Operation} -Default Treeでは、木に対しての変更は、全てメインの木に対する変更であるため、Logに書き出された全ての変更を一回のCommitで行える。 -しかし、Differential Treeの変更は、Editorが保持しているsubTreeに対する変更であるため、適切なタイミングでCommitを行わないと、実際に行われた変更とズレが生じて、正しい木を構築できない。 +Default Jungle Treeでは、木に対しての変更は全てメインの木に対する変更であるため、Logに書き出された全ての変更を一回の Commit で行える。 +しかし、Differential Jungle Treeの変更は、Editorが保持しているsubTreeに対する変更を加えた後、 Commit 時にメインの木にAppendを行っている。 +そのため、適切なタイミングでCommitを行わないと、実際に行われた変更とズレが生じて、正しい木を構築できない。 以下に、Logからの木の構築をする際に、一回のCommitでは適切なDifferential Treeを構築できない例を記す。 \begin{lstlisting}[frame=lrbt,label=src:treelog,caption=適切な木を構築できないLogの例,numbers=left] @@ -86,12 +120,12 @@ NodePath の表記以降は、ノードの position などの情報を表している。 [COMMIT]は、実際の木を構築した際にCommitが行われたタイミングを表す。 -[COMMIT]のタイミングでCommitを行わず、全ての変更を加えた後にCommitを行った場合、図\ref{fig:badDifTreeCreate}のような変更が加えられ、図\ref{fig:badDifTree}のような木が構築される。 -しかし、実際には、図\ref{fig:createGoodDifTree1}、図\ref{fig:createGoodDifTree2}のような変更が加えられ、図\ref{fig:goodDifTree}のような木が構築されている。 +[COMMIT]のタイミングでCommitを行わず、全ての変更を加えた後にCommitを行った場合、Editor 内部の Sub Treeに、図\ref{fig:badDifTreeCreate}のような変更が加えられ、Append後、図\ref{fig:badDifTree}のような木が構築される。 + \begin{figure}[htpb] \begin{center} -\includegraphics[scale=0.5]{figures/badDifTreeCreate.pdf} +\includegraphics[scale=0.45]{figures/badDifTreeCreate.pdf} \caption{適切なタイミングでCommitを行わない木の復元の流れ} \label{fig:badDifTreeCreate} \end{center} @@ -99,75 +133,69 @@ \begin{figure}[htpb] \begin{center} -\includegraphics[scale=0.5]{figures/BadDifTree.pdf} +\includegraphics[scale=0.45]{figures/BadDifTree.pdf} \caption{適切なタイミングでCommitを行わなかった木} \label{fig:badDifTree} \end{center} \end{figure} -\newpage +\clearpage + +しかし、実際には、図\ref{fig:createGoodDifTree1}、図\ref{fig:createGoodDifTree2}のような変更が加えられる。 +以下に、適切に Commit を行った場合の木の編集の流れを記述する。 \begin{figure}[htpb] \begin{center} \includegraphics[scale=0.45]{figures/goodDifTreeCreate1.pdf} -\caption{適切なタイミングでCommitを行なう、木の復元の流れ(1回目のCommit前)} +\caption{適切なタイミングでCommitを行なう、木の復元の流れ(1回目のCommit前、Sub Tree)} \label{fig:createGoodDifTree1} \end{center} \end{figure} + +1. 木からEditorを取得し、Sub Treeのルートノードの0番目に子ノードを追加する。 + +\vspace{0.15in} +2. そして、Commitを行い、1で構築したSub Treeをメインの木にAppendする + \begin{figure}[htpb] \begin{center} \includegraphics[scale=0.45]{figures/goodDifTreeCreate2.pdf} -\caption{適切なタイミングでCommitを行なう、木の復元の流れ(2回目のCommit前)} +\caption{適切なタイミングでCommitを行なう、木の復元の流れ(2回目のCommit前、Sub Tree)} \label{fig:createGoodDifTree2} \end{center} \end{figure} +3. 木からEditorを取得し、Sub Tree のルートノードの0番目に子ノードを追加する。 + +\vspace{0.15in} +4. 続いて、Sub Treeの{\tt <-1, 0>} 番目にあるノードの、0番目の子供にノードを追加する。 + +\vspace{0.15in} +5. 最後に2度目の Commit を行い、Sub Treeをメインの木にAppendする。 + +\vspace{0.15in} + +結果、図\ref{fig:goodDifTree}のような木が構築される。 + \begin{figure}[htpb] \begin{center} -\includegraphics[scale=0.5]{figures/goodDifTree.pdf} -\caption{適切なタイミングでCommitを行なった木} +\includegraphics[scale=0.45]{figures/goodDifTree.pdf} +\caption{適切なタイミングでCommitを行なった木の変更。} \label{fig:goodDifTree} \end{center} \end{figure} -\newpage -Logとして書き出されたTreeOperationから、適切な構造のDifferential Treeを構築するためには適切なタイミングでCommitを行う必要がある。 -この問題を解決するために、CommitのタイミングをLogとして書き出し、適切なタイミングでCommitを行えるようにした。 +このように、Logとして書き出されたTreeOperationから、適切な構造のDifferential Treeを復元するためには、木の構築時と同じタイミングでCommitを行う必要がある。 +そのため、Commitのタイミングを、Logとして書き出し、適切なタイミングでCommitを行えるようにした。 + -\section{末尾ノードへのAppendの整合性} -JungleのTreeは、過去の木を全て保持している。 -Differential Treeは、木を破壊的に変更するため、過去の木に変更を加えた場合木の整合性が崩れてしまうため、過去の木への編集を禁止する必要がある。 -ソースコード\ref{src:Append}にSub TreeのAppend部分のコードを記述する。 -\begin{lstlisting}[frame=lrbt,label=src:Append,caption=Sub TreeのAppend部分のコード,numbers=left] -Either appendSubTree(TreeNode subTreeRoot) { - TreeNode appendedNode = treeContext.getEndNode(); - TreeNodeChildren children = appendedNode.getChildren(); - if (children.size() != 0) - return DefaultEither.newA(APPEND_FAILD); - return children.addNewChildAt(0, subTreeRoot); -} -\end{lstlisting} -以下にソースコード\ref{src:Append}の解説を行う。 -\begin{enumerate} -\item 関数{\tt appendSubTree}でSub TreeのAppendを行う。引数にSub Treeのルートを持つ。 -\item TreeContextから末尾ノードを取得する。 -\item 末尾ノードからChildrenを取得する。 -\item 末尾ノードにSub TreeがすでにAppendされているか(子供を持っているか)を調べる。 -\item 他のSub TreeがAppendされている(今編集を行っているのが過去の木)場合、木のAppendは失敗するため、エラーを返す。 -\item そうでない場合、Sub Treeを末尾ノードにAppendする。 -\end{enumerate} - -このように、過去の木への編集を禁止することで、木の整合性を保証している。 - - -\section{Differential Treeの検索} +\section{Differential Jungle Treeの検索} Differential Treeは、木を破壊的に編集する。 そのため、過去の木から特定の値を持ったノードを取得する際、全てのノードを走破した場合その版の木には無いはずのノードが取得できてしまうことがある。 -そこで、その版の木が持つ末尾ノード以下のSub Treeを検索対象から取り除く、検索を実装した。 +そこで、その版の木が持つ末尾ノード以下のSub Treeを検索対象から除外する検索を実装した。 Indexを使用した検索を行う場合、各版に対応したIndexがあるため、Default Treeと検索の方法は変わらない。 -これらの機能を実装したことにより、Differential Treeは完成した。 diff -r 99d965c02c45 -r da6a6eba893d chapter3.tex --- a/chapter3.tex Tue Jan 17 18:47:09 2017 +0900 +++ b/chapter3.tex Tue Jan 24 14:53:52 2017 +0900 @@ -4,48 +4,314 @@ そこで、ノードの挿入を行うと木のバランスを取る、Red Black Treeの性質を組み込んだRed Black Jungle Treeの実装を行った。 \section{Red Black Tree} -初めにRed Black Treeの説明を行う。 - Red Black Treeは二分探索木の一つで、以下の条件を満たした木のことである。 \begin{enumerate} \item ノードは赤か黒の色を持つ。 -\item ルートノードは黒ノード。 -\item 全ての葉は黒である(空の黒ノードを持つ)。 -\item 赤いノードの子は黒である。 +\item ルートノードの色は黒。 +\item 全ての葉は黒である。 +\item 赤いノードの子は黒色である。 \item 全ての葉からルートまでのパスには、同じ個数の黒いノードがある。 \end{enumerate} -赤黒木は、データの挿入、削除時に、上記の条件を崩さないように木のバランスを取る。 +Red Black Treeは、データの挿入、削除時に、上記の条件を崩さないように木のバランスを取る。 +この条件により、Red Black Treeはデータの検索、削除、探索をO(log n)で行える。 + +\section{Red Black Jungle Treeの作成} +Red Black Jungle Treeを作成するため、Jungleに{\tt createNewRedBlackTree(String treeName, String balanceKey)}を実装した。 +これは、第一引数{\tt treeName}で受け取った名前の、第二引数{\tt balanceKey}とペアになる属性値でバランスを取るRed Black Treeを構築する。 + +またこれ以降の説明で使用するbalanceKeyは、Red Black Jungle Treeを作成する時に設定したkey、BalanceValueは属性名 BalanceKeyとペアの属性値のことである。 -この条件により、赤黒木はデータの検索、削除、探索をO(log n)で行える。 +\section{Red Black Jungle Treeの編集} +Red Black Jungle Treeへノードの追加を行う際は、追加するノードに、木のバランスを取るために必要な属性名 BalanceKeyとそのペアの属性値が必要になる。 +しかし、JungleTreeEditorには、ノードと値を同時に追加するAPIは存在しなかったため、新しく実装した。 +また、Red Black Jungle Treeにおいて、特定の属性名と属性値のペアを持つノードを削除するAPIも同時に実装した。 +表\ref{NewEditorAPI}に新しく実装したAPIを記述する。 + +\begin{table}[htb] +\begin{center} +\caption{新たにJungle Tree Editorに定義したAPI} +\begin{tabular}{|p{15em}|p{24em}|} \hline +{\tt Either addNewChildAndPutAttribute(NodePath path, int pos, String key, ByteBuffer value)} & pathで指定した位置にあるノードのpos番目に、属性名 keyと属性値 valueの組を持つノードを追加する。\\ \hline +{\tt Either deleteChildAt(String Key, ByteBuffer value)} & 木から特定の属性名 keyと属性名 valueを持っているノード検索し、削除する。\\ \hline +\end{tabular} +\label{NewEditorAPI} +\end{center} +\end{table} -\section{Red Black Treeへのデータの挿入} -Red Black Treeへのデータの挿入は、以下の手順で行われる。 +Red Black Jungle Tree Editorは、既存のJungle Tree EditorとくらべてAPIの使い方が異なる。 +具体的にはaddNewChildAtでPathが使われなかったりする。 +表\ref{EditorDifference}にDefault Jungle Tree EditorとRed Black Jungle Tree EditorのAPIの使い方の違いを記述する。 + +\begin{table}[htb] +\begin{center} +\caption{Red Black Jungle TreeとDefault Jungle TreeのAPIの違い} +\begin{tabular}{|p{15em}|p{24em}|} \hline +{\tt Either addNewChildAt(NodePath path, int pos)} & pathとposは使用せず、属性名 balanceKey 属性値 "Default Value"を持ったノードを、Red Black Treeの挿入アルゴリズムに則って挿入し、バランスを取る。 \\ \hline +{\tt Either addNewChildAt(NodePath path, int pos, String key, String value)} & pathとposは使用せず、属性名 key 属性値 valueを持ったノードを、Red Black Treeの挿入アルゴリズムに則って挿入し、バランスを取る。 第二引数にBalanceKey以外の値を渡した場合、バランスが取れない為、ノードの挿入は失敗する。\\ \hline +{\tt Either replaceNewRootNode()} & 赤黒木は、新しくルートを追加する意味が無いので使用しない。実行した場合エラーを返す。\\ \hline +{\tt Either moveChild(NodePath path, int childNum, String move)} & ノードを動かすと木のバランスが崩れるため使用しない。実行した場合エラーを返す。 \\ \hline +\end{tabular} +\label{EditorDifference} +\end{center} +\end{table} + + + +\section{Jungle Red Black Treeへのデータの挿入} +Jungle Red Black Treeへのデータの挿入は、以下の手順で行われる。 \begin{enumerate} -\item 挿入を行うノードと、現在のノードを比較する。 -\item 比較の結果、挿入を行うノードが現在のノードより大きかった場合、右に、小さかった場合左のノードに進む。 +\item 挿入を行うノードのBalanceValueと、現在のノードBalanceValueを比較する。 +\item 比較の結果、大きかった場合右に、小さかった場合左のノードに進む。 \item 挿入を行う場所にたどり着くまで、１・２を繰り返す。 \item 現在の位置に、赤色でノードを挿入する。 +\item 木のバランスを取りながら、ルートまでの経路の複製を行う。その際Defaul Jungle Treeと同じように、変更が加えられないノードへは参照を行い過去の木と最大限共有を行う。 +\end{enumerate} + +Jungle Red Black Treeのバランスは、データ挿入時の状態によって、次の5パターンに分けられる。 + +\subsection{データ挿入時のバランス ケース1} + +\begin{enumerate} +\item ノードを挿入した位置がルート +\end{enumerate} +挿入時上記の条件を満たしている場合、ルートノードの色を黒に変更することで木のバランスを取る。 +ルートノードの色を黒に変更しても、左右のSub Treeの黒の個数が一つ増えるだけなので、Red Black Treeの条件は守られる。 + + +\subsection{データ挿入時のバランス ケース2} +\begin{enumerate} +\item 挿入したノードinsの親ノードBが黒。 +\end{enumerate} + +バランス時、上記の条件を満たしている場合、Red Black Treeの条件は崩れないため、そのまま赤色でノードを挿入して問題はない。%(図\ref{fig:RedBlackTreeInsert1})。 + +%\begin{figure}[htpb] +%\begin{center} +%\includegraphics[scale=0.5]{figures/RedBlackTreeInsert1.pdf} +%\caption{データ挿入時のバランス2} +%\label{fig:RedBlackTreeInsert1} +%\end{center} +%\end{figure} + + +\subsection{データ挿入時のバランス ケース3} +\begin{enumerate} +\item 挿入したノードinsの親の親ノードAが黒。 +\item ノードAの両方の子ノードB・Cが赤。 \end{enumerate} -挿入を行った後は、Red Black Treeの条件を崩さないように、木のバランスを取る。 +バランス時、上記の条件を満たしている場合、ノードB・Cを黒に、ノードAを赤に変更する(図\ref{fig:RedBlackTreeInsert2})。 + +また、本章の図に表記されている四角のノードの色は、Red Black Treeの条件を守られているなら問わず、それ以下の子ノードは省略してあるものとする。 +\begin{figure}[htpb] +\begin{center} +\includegraphics[scale=0.5]{figures/RedBlackTreeInsert2.pdf} +\caption{データ挿入時のバランス3} +\label{fig:RedBlackTreeInsert2} +\end{center} +\end{figure} -Red Black Treeのデータ挿入時のバランスは次の4パターンに分けられる。 +バランス後、ノードAを新しくノードinsとして再帰的に木のバランスを行う。 +この変更は最悪の場合ルートまで続く。 + +\subsection{データ挿入時のバランス ケース4} +\begin{enumerate} +\item 挿入したノードinsの親の親ノードAが黒。 +\item ノードAの、挿入したノード側の子ノードBが赤。 +\item 逆側の子ノードCが黒。 +\item ノードinsがノードBの木の中心側の子。 +\end{enumerate} -\subsection{Red Black Treeへのデータ挿入時のバランス 1} -ノードを挿入した位置がルートだった場合、無条件でノードの色を黒に変更できる。 -ルートノードの色が黒になっても左右のSub Treeの黒の個数が一つ増えるだけなので、Red Black Treeの条件は守られる。 +バランス時、上記の条件を満たしている場合、ノードBを中心に外側に回転処理を行い(\ref{fig:RedBlackTreeInsert3})、次節に記述するバランス5を行う。 +その際、ノードBをinsとして扱う。 + +\begin{figure}[htpb] +\begin{center} +\includegraphics[scale=0.5]{figures/RedBlackTreeInsert3.pdf} +\caption{データ挿入時のバランス4} +\label{fig:RedBlackTreeInsert3} +\end{center} +\end{figure} -また、親が黒色の場合、Red Black Treeの条件は崩れないため、そのまま赤色でノードを挿入して問題はない(図\ref{fig:RedBlackTreeInsert1})。 +\subsection{データ挿入時のバランス ケース5} +\begin{enumerate} +\item 挿入したノードinsの親の親ノードAが黒。 +\item ノードAの、挿入したノード側の子ノードBが赤。 +\item 逆側の子ノードCが黒 +\item ノードinsがノードBの木の外側の子。 +\end{enumerate} + +バランス時、上記の条件を満たしている場合、ノードAを中心に内側に回転処理を行い、回転後ノードAとノードBの色を入れ替える。 \begin{figure}[htpb] \begin{center} -\includegraphics[scale=0.7]{figures/destructive_tree.pdf} -\caption{Red Black Treeへのデータ挿入時のバランス1} -\label{fig:RedBlackTreeInsert1} +\includegraphics[scale=0.5]{figures/RedBlackTreeInsert4.pdf} +\caption{データ挿入時のバランス5} +\label{fig:RedBlackTreeInsert4} +\end{center} +\end{figure} + + +赤黒木は、データ挿入時にこれらの処理を行うことで、木のバランスを取る。 + + +\section{Jungle Red Black Treeのノード削除} +Jungle Red Black Treeのノード削除は、以下の手順で行われる。 + +\begin{enumerate} +\item 削除を行うノードを検索する。 +\item ノードに子が無い場合削除を行う。 +\item 片側に部分木(子ノード)がある場合、ノードを削除した後、部分木のルートを昇格させる。 +\item 両側に部分木(子ノード)がある場合は、左部分木の最大の値を持つノードの値を取得し、削除を行うノードと同じ色に変更した後、置換する。 +\item 昇格させたノードを削除する(ここで削除させるノードは部分木の最大値であるため、子ノードは1つ以下、つまり削除の手順2・3どちらかの手順で削除できる)。 +\item 削除したノードから、木のバランスを取りながら、ルートまでの経路の複製を行う。その際Defaul Jungle Treeと同じように、変更が加えられないノードへは参照を行い過去の木と最大限共有を行う。 +\end{enumerate} + + +RedBlackTreeのバランスは、ノード削除時の状態によって、次の6パターンに分けられる。 +また。これ以降削除対象のノードと置換したノードを、ノードrepと記述する。 +\subsection{データ削除時のバランス ケース1} + +\begin{enumerdte} +\item 削除したノードが赤の場合。 +\end{enumerate} + +上記の条件を満たしている場合、木の経路にある黒ノードの数は変らないためバランスを行う必要はない。 + +\begin{enumerate} +\item 削除したノードが黒。 +\item 削除したノードの子ノードrepが赤。 +\end{enumerate} + +上記の条件を満たしている場合は、、ノードrepを置き換える際に赤から黒に色を変えることで木のバランスを取る。 + +以降、削除したノードの子の色が黒の場合のパターンについて記述する。 +\subsection{データ削除時のバランス ケース2} +\begin{enumerate} +\item ノードrepがルートに置き換えられた。 +\end{enumerate} + +上記の条件を満たしている場合、全ての経路の黒ノード数が1つ減った状態で条件が成立しバランスは終了する。 + +\subsection{データ削除時のバランス ケース3} +\begin{enumerate} +\item 削除したノードが黒。 +\item ノードrepが黒。 +\item ノードA・B・C・D・E・Fが黒。 +\end{enumerate} + +バランス時、上記の条件を満たしている場合、ノードBを赤に変える(図\ref{fig:RedBlackTreeDelete1})。 +そうすることで、ノードB・E・F以下の黒ノードの階層が減って、ノードA以下の木のバランスが回復する。 +その後、Aを新たなノードrepとして木のバランスを行う。 +このバランスは最悪の場合ルートまで続き、ケース2で終了する。 + +\begin{figure}[htpb] +\begin{center} +\includegraphics[scale=0.45]{figures/RedBlackTreeDelete1.pdf} +\caption{データ削除時のバランス3} +\label{fig:RedBlackTreeDelete1} \end{center} \end{figure} + +\subsection{データ削除時のバランス ケース4} +\begin{enumerate} +\item 削除したノードが黒。 +\item ノードrepが黒。 +\item ノードA・C・D・E・Fが黒 +\item ノードBが赤。 +\end{enumerate} + +上記の条件を満たしている場合、ノードAを中心に外側に回転、その後ノードAを赤に、ノードBを黒に変更する(図\ref{fig:RedBlackTreeDelete2})。 +その後、ノードrepを基準に再び木のバランスを行う。 +この時のバランスは、図\ref{fig:RedBlackTreeDelete2}における、ノードEの子供の色に応じてケース5・6・7のどれかに帰着する。 + +\begin{figure}[htpb] +\begin{center} +\includegraphics[scale=0.45]{figures/RedBlackTreeDelete2.pdf} +\caption{データ削除時のバランス4} +\label{fig:RedBlackTreeDelete2} +\end{center} +\end{figure} + +\subsection{データ削除時のバランス ケース5} +\begin{enumerate} +\item 削除したノードが黒。 +\item ノードrepが黒。 +\item ノードB・C・D・E・Fが黒 +\item ノードAが赤。 +\end{enumerate} + +上記の条件を満たしている場合、ノードAを黒に、ノードBを赤に変更する。 +そうすることで、ノードA側の右側のSub Treeの黒の深さを変えることなく、左側のSub Treeの黒の深さが1つ増え、バランスが取れる。 +\begin{figure}[htpb] +\begin{center} +\includegraphics[scale=0.45]{figures/RedBlackTreeDelete3.pdf} +\caption{データ削除時のバランス5} +\label{fig:RedBlackTreeDelete3} +\end{center} +\end{figure} + +\subsection{データ削除時のバランス ケース6} +\begin{enumerate} +\item 削除したノードが黒。 +\item ノードrepが黒。 +\item ノードB・C・D・Fが黒。 +\item ノードEの色が赤。 +\end{enumerate} + +上記の条件を満たしている場合、ノードBを中心に外側に回転、その後、ノードEを黒に、ノードBを赤に変更する。 +そして、データ削除時のバランス ケース7に帰着する。 + +\begin{figure}[htpb] +\begin{center} +\includegraphics[scale=0.45]{figures/RedBlackTreeDelete4.pdf} +\caption{データ削除時のバランス6} +\label{fig:RedBlackTreeDelete4} +\end{center} +\end{figure} + + +\subsection{データ削除時のバランス ケース7} +\begin{enumerate} +\item 削除したノードが黒。 +\item ノードrepが黒。 +\item ノードB・C・Dが黒。 +\item ノードFの色が赤。 +\end{enumerate} + +上記の条件を満たしている場合、ノードAを中心にノードrep側に回転、その後、ノードAとノードBの色を交換し、ノードFを黒にする。 +そうすることで、ノードE・Fの黒の深さを変えること無く、ノードrepの黒の深さを1増やせるため、木のバランスが取れる。 + +\begin{figure}[htpb] +\begin{center} +\includegraphics[scale=0.45]{figures/RedBlackTreeDelete5.pdf} +\caption{データ削除時のバランス7} +\label{fig:RedBlackTreeDelete5} +\end{center} +\end{figure} + +Red Black Jungle Treeは、これらの処理を行うことで、データの挿入・削除時にこれらの処理を行うことで、木のバランスを保っている。 +また、Red Black Jungle Treeは自身の木構造がIndexとしての機能を持つため、木の編集を行った際に別途Indexを構築する必要はない。 + +\section{Jungle Red Black Treeの検索} +Red Black Jungle Treeへの検索は、Red Black Jungle Tree Traverserを用いて行う。 +Red Black Jungle Treeは、Indexを持たないため、Traverser.find(Query query, String balanceKey, String balanceValue)の第二・第三引数は、木を作成する時に設定したbalanceKey・属性名 balanceKeyとペアのbalanceValueを取る。 +balanceKeyを使ったデータの検索は以下の手順で行う。 + +\begin{enumerate} +\item 現在のノードから、findの第二引数で取得した、属性名 BalanceKeyとペアになっている属性値 valueを取得する。 +\item 1で取得した属性値 valueと、findの第三引数で取得したbalanceValueを比較する。 +\item 比較の結果、大きかった場合、右に、小さかった場合左のノードに進む。 +\item 同じ値を持つノードを発見するか、葉にたどり着くまで1~3を繰り返す。 +\item 同じ値を持つノードを発見したら、そのノードを返す。 +\item 葉までたどり着いた場合、その木は対応するノードを持っていないため +\item 5で取得したノードが、第一引数のqueryの条件に一致するか確かめる。 +\item 一致する場合そのノードを返す。 +\end{enumerate} + +これらの実装により、Red Black Jungle Treeは、木の構築・検索の機能を持つ。 diff -r 99d965c02c45 -r da6a6eba893d chapter4.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/chapter4.tex Tue Jan 24 14:53:52 2017 +0900 @@ -0,0 +1,49 @@ +\chapter{Jungleを使ったアプリケーション} +本章では、これまで開発をしたJungleを使用したアプリケーションを記述する。 + + +\section{Jungle Tree ブラウザ} + +Jungleの木に対する変更において、{\tt JungleTreeEditor}クラスを用いる方法はプログラム上では便利だが、手動で変更するのには向いていない。 +よって、組み込みWEBサーバーであるJettyを使用し、Servletとして木の表示と編集を実現した。 + +\subsection{木構造の表示} +JungleTreeブラウザにおいて、Jungle DBはWEBサーバー内に存在し、それから表示に必要なHTMLを生成してブラウザに転送する。 +%図\ref{printNode}は、サーバからデータを送り、ブラウザ上でノードを可視化するまでの流れである。 +この流れは、Jungleの{\tt NodePath}の処理を除けば通常のデータベースのレコードの表示と同等である。 + +編集するノードのパスはURLで記述されている。例えば、 +{\small + \verb! http://localhost/showBoardMessage?! + \verb! bname=Layout&path=-1,0,2! +} +などとなる。 + +以下にJungleTreeブラウザを用いて、ノードを表示するまでの流れを記述する。 +\begin{enumerate} +\item ユーザーは表示したいノードのパスをURLでJungleTreeブラウザに送る。 +\item JungleTreeブラウザは、WEBサーバ内にあるJungleから、対応した木を取得する。 +\item JungleTreブラウザは、パスで指定した位置のノードを木から取得する。 +\item 取得したノードの中身を、JungleTreeブラウザが表示する。 +\end{enumerate} + + +\subsection{Jungle Tree ブラウザを使った木の編集} +%図\ref{JungleEdit}はブラウザを用いたJungleの木の更新の流れである。 +以下にJungle Treeブラウザを用いた木の編集の流れを示す。 +\begin{enumerate} +\item ユーザーはJungleTreeブラウザで編集したいノードを表示するページに移動する 。 +\item ユーザーはJungleTreeブラウザに木の変更要求を送る。 +\item JungleTreeブラウザはWebサーバー内にあるJungleから、対応した木を取得する。 +\item 編集を行う木から、{\tt JungleTreeEditor}クラスを取得し、木の変更を行う。 +\item 木の変更をJungleにコミットする。 +\item 木の変更の結果を表示する。 +\end{enumerate} + +パスを使用することにより、木の変更をRestfulに行うことができるように見えるが、木のパスは特定の木の版に固有のものである。 +ブラウザとWEBサーバは、セッションで結合されており、そのセッションが同じ版の木を編集していれば問題なく成功する。 +ただし、編集し終わった時に、他の編集が割り込んでいたら、その編集は無効となる。 +%この点が既存のRDBとは異なる。 +また巨大な木を操作する時には、Pathを直接URLに含むことはできないので、他の工夫が必要になると考えられる。 +このアプリケーションでは任意の木を取り扱うので、木の大きさの現実的な制限を除けば木の設計の問題はない。 + diff -r 99d965c02c45 -r da6a6eba893d chapter5.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/chapter5.tex Tue Jan 24 14:53:52 2017 +0900 @@ -0,0 +1,156 @@ +\section{HTML Rendering Engine} +HTMLRenderingEngineは、出力するデータが記述されたContents Tree、出力する形式が記述されたLayout Treeの2つの木構造を持ち、これらを参照しながらhtmlのレンダリングを行う。 +またレンダリングする例題は日記を選択した。 + +\subsection{Contents TreeのJungle上での表現} +RenderingEngineではContents Treeに図\ref{contentTree}のように出力するデータを格納した。 + +\begin{figure}[h] +\begin{center} +\includegraphics[scale=0.25]{figures/contentTree.pdf} +\caption{ContentTree} +\label{contentTree} +\end{center} +\end{figure} + + +RootNodeはContentの{\tt title}、日時、レンダリングする時に参照するLayoutTreeのNodeNameを持つ。 +そして子ノードが日記の本文等のデータを持つ。 +表\ref{NodeAttribute}にノードが保持しているContentsの一覧を記述する。 + +\begin{table}[htb] +\begin{center} +\caption{ノードが保持しているContents一覧} +\begin{tabular}{|p{15em}|p{24em}|} \hline +属性名 & 属性値 \\ \hline +component & レンダリングする際に参照するLayoutTreeのNodeName \\ \hline +title & 日記のタイトル \\ \hline +date(rootNode) & 日記の日時 \\ \hline +type & そのノードが保持しているContextType。 text(日記本文) or image(画像データ) \\ \hline +body & 日記の本文 \\ \hline +date(image) & 画像の保存日時 \\ \hline +fileName & 画像の名前 \\ \hline +\end{tabular} +\label{NodeAttribute} +\end{center} +\end{table} + +\subsection{Layout} +htmlの出力形式を定義するLayoutは、複数のComponentからなる。 +表\ref{LayoutTreeTable}に、LayoutTreeの主要要素を記す。 +Layout Treeには図\ref{layoutTree}のようにデータを格納した。 +また、LayoutTreeはノード同士が{\tt NodeName}を用いて参照を行う。 + + +\begin{figure}[h] +\begin{center} +\includegraphics[scale=0.25]{figures/LayoutTree.pdf} +\caption{LayoutTree} +\label{layoutTree} +\end{center} +\end{figure} + + +\begin{table}[htbH] +\begin{center} +\caption{LayoutTreeの主要な要素} +\begin{tabular}{|p{15em}|p{24em}|} \hline +属性名 & 属性値 \\ \hline +NodeName &ノードの名前。ノード同士の参照時に用いられる。例外としてルートノードだけはdisplayinformationという名前を持つ\\ \hline +displayComponent &参照するノードの名前。 \\ \hline +Name &この属性名で取得できる値を持つNodeNameを持つノードを参照する。\\ \hline +use &このノードが、どのContentsに対してのLayoutを持つかを記述するタグ。表\ref{tag}にタグとContentsの対応を記述する。\\ \hline +その他 &css等と同じ様な記述を行う。 例 属性名 {\tt font} 属性値 {\tt fontSize}など \\ \hline +\end{tabular} +\label{LayoutTreeTable} +\end{center} +\end{table} + + +Layout Treeは、ルートノードに属性名 {\tt NodeName} 属性値 {\tt displayinformation} の値を持つ(図\ref{layoutTree}では{\tt Node1}が該当する)。 +ルートノードは、子ノードに複数のComponentを保持する(図\ref{layoutTree}では{\tt Node2}、{\tt Node3}がそれに該当する)。 +{\tt Node2}は、属性名 {\tt use} 属性値 {\tt image}のペアでタグを保持しているため、日記の画像表示に対応する記述が行われている。 +{\tt Node3}は、属性名 {\tt use} 属性値 {\tt text}のペアでタグを保持しているため、日記の本文に対応する記述が行われている。 +表\ref{tag}にタグとContentsの対応を記述する。 + +\begin{table}[htb] +\begin{center} +\caption{tagとcontentsの対応} +\begin{tabular}{|p{15em}|p{24em}|} \hline +tag & content \\ \hline +image & 画像の表示 \\ \hline +cals & table \\ \hline +date & 日付の表示 \\ \hline +text & 日記の本文 \\ \hline +title & 日記のタイトル \\ \hline +\end{tabular} +\label{tag} +\end{center} +\end{table} + + +Layoutが複数のComponentを参照する際は図\ref{multiComponent}のような木構造を構築する(この木はLayoutTreeの一部であり、本来は参照先のノード等が存在している)。 +\begin{figure}[h] +\begin{center} +\includegraphics[scale=0.25]{figures/multiComponent.pdf} +\caption{複数のComponentを参照するLayout} +\label{multiComponent} +\end{center} +\end{figure} + +図\ref{multiComponent}の例では、{\tt diaryMulti@component}は{\tt diaryText@component}と{\tt diaryImage@component}を参照している。 + +以下に図\ref{contentTree}のContentsTree、図\ref{multiComponent}のLayoutTreeの２つを使用した、レンダリングの流れを記述する。 +\begin{enumerate} + +\item ContentsTreeのルートノードは、属性名 {\tt component} 属性値 {\tt Multi@Component}の組を持つので、LayoutTreeの{\tt Node2}を参照する。 + +\item {\tt Node2}は自身のNodeNameしか持たないので、子ノードである{\tt Node3、Node4}に記述されているデータの参照を行う。 + +\item {\tt Node3}は属性名 {\tt displayComponentName} 属性名 {\tt dialyImage@Component}の組を持つため、NodeNameが{\tt dialyImage@Component}のノードを参照している。 + +\item レンダリングエンジンは、参照先のノードに記述されたルールに則ってHtmlを生成する。 + +\item {\tt Node3}は、これ以上データを持たないため、次は{\tt Node4}を参照する。 + +\item {\tt Node4}は属性名 {\tt displayComponentName} 属性名 {\tt dialyText@Component}の組を持つため、NodeNameが{\tt dialyText@Component}のノードを参照している。 + +\item レンダリングエンジンは、参照先のノードに記述されているルールに則ってhtmlを生成する。 + +\end{enumerate} + +(4)、(7)で参照しているノードに関しては、図\ref{layoutTree}の{\tt Node2、Node3}の様な記述が行われている。 + +\subsection{Layout Treeのデータ設計} +Jungleは汎用の木構造を持つので、データベースを特に設計しなくても、あるがままの形で格納することが可能である。 +しかし、設計を行うことでより効率的に木構造を扱うことが可能になる。 +図\ref{goodLayoutTree}、図\ref{badLayoutTree}は同じデータを格納した２つの木の一部である。 + + +\begin{figure}[h] +\begin{center} +\includegraphics[scale=0.25]{figures/goodLayoutTree.pdf} +\caption{コードとギャップのないLayoutの格納方法} +\label{goodLayoutTree} +\end{center} +\end{figure} + +\begin{figure}[h] +\begin{center} +\includegraphics[scale=0.25]{figures/badLayoutTree.pdf} +\caption{コードとギャップのあるLayoutの格納方法} +\label{badLayoutTree} +\end{center} +\end{figure} + + +図\ref{goodLayoutTree}のTreeは、１つのノードにレンダリングに必要な値が全て格納されている。 +そのため、レンダリングを行う際、複数のノードをまたぐ必要が無く、簡潔にコードを書くことができる。 + + + +一方、図\ref{badLayoutTree}の木はレンダリングする際に必要な値が複数ノードに分散されて保存されている。 +そのため、全てのノードを参照し、値を集める処理を行う必要があり、コードの可読性が下がり余計な処理も増えてしまう。 +これより、Jungleの木構造を効率的に扱うためには、設計手法を確率する必要があることがわかる。 + + diff -r 99d965c02c45 -r da6a6eba893d chapter6.tex diff -r 99d965c02c45 -r da6a6eba893d conclusion.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/conclusion.tex Tue Jan 24 14:53:52 2017 +0900 @@ -0,0 +1,12 @@ +\chapter{結論} \label{chapter:conclusion} + +\section{まとめ} +まとめを書く + +\section{今後の課題} + + +\subsection{今後の課題} + + +%\subsection{Treeのバランスの問題} diff -r 99d965c02c45 -r da6a6eba893d figures/.DS_Store Binary file figures/.DS_Store has changed diff -r 99d965c02c45 -r da6a6eba893d figures/BadDifTree.graffle --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/figures/BadDifTree.graffle Tue Jan 24 14:53:52 2017 +0900 @@ -0,0 +1,849 @@ + + + + + ActiveLayerIndex + 0 + ApplicationVersion + + com.omnigroup.OmniGraffle + 139.16.0.171715 + + AutoAdjust + + BackgroundGraphic + + Bounds + {{0, 0}, {559, 783}} + Class + SolidGraphic + ID + 2 + Style + + shadow + + Draws + NO + + stroke + + Draws + NO + + + + BaseZoom + 0 + CanvasOrigin + {0, 0} + ColumnAlign + 1 + ColumnSpacing + 36 + CreationDate + 2017-01-15 19:17:52 +0000 + Creator + sister_clown + DisplayScale + 1.000 cm = 1.000 cm + GraphDocumentVersion + 8 + GraphicsList + + + Bounds + {{184, 62.5}, {125, 46}} + Class + ShapedGraphic + FitText + YES + Flow + Resize + FontInfo + + Font + HiraKakuPro-W3 + Size + 24 + + ID + 206 + Shape + Circle + Style + + fill + + Color + + b + 0.974573 + g + 0.998064 + r + 1 + + Draws + NO + + shadow + + Color + + a + 0.75 + b + 0.94523 + g + 0.987116 + r + 1 + + Draws + NO + + stroke + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuPro-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs48 \cf0 5.Commit} + + TextRelativeArea + {{0, 0}, {1, 1}} + Wrap + NO + + + Bounds + {{404, 26.5}, {64, 82}} + Class + ShapedGraphic + FitText + YES + Flow + Resize + FontInfo + + Font + HiraKakuPro-W3 + Size + 24 + + ID + 205 + Shape + Circle + Style + + fill + + Color + + b + 0.974573 + g + 0.998064 + r + 1 + + Draws + NO + + shadow + + Color + + a + 0.75 + b + 0.94523 + g + 0.987116 + r + 1 + + Draws + NO + + stroke + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuPro-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs48 \cf0 tree\ +ver2} + + TextRelativeArea + {{0, 0}, {1, 1}} + Wrap + NO + + + Class + LineGraphic + Head + + ID + 201 + Info + 2 + + ID + 204 + Points + + {382, 389.99995846484364} + {382, 419.49986944726584} + + Style + + stroke + + HeadArrow + 0 + Join + 0 + Legacy + + TailArrow + 0 + + + Tail + + ID + 197 + Info + 1 + + + + Class + LineGraphic + Head + + ID + 196 + + ID + 203 + Points + + {436, 186.50001949999989} + {436, 207.99998050000011} + + Style + + stroke + + HeadArrow + 0 + Join + 0 + Legacy + + TailArrow + 0 + + + Tail + + ID + 202 + Info + 1 + + + + Bounds + {{396, 108.5}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 202 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs24 \cf0 (root)} + VerticalPad + 0 + + + + Bounds + {{342, 419.49988894726573}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 201 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + VerticalPad + 0 + + + + Class + LineGraphic + Head + + ID + 199 + Info + 2 + + ID + 200 + Points + + {436, 286.00001949999989} + {490, 311.99991946484386} + + Style + + stroke + + HeadArrow + 0 + Join + 0 + Legacy + + TailArrow + 0 + + + Tail + + ID + 196 + Info + 1 + + + + Bounds + {{450, 311.99993896484375}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 199 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + VerticalPad + 0 + + + + Class + LineGraphic + Head + + ID + 197 + Info + 2 + + ID + 198 + Points + + {436, 286.00001949999989} + {382, 311.99991946484386} + + Style + + stroke + + HeadArrow + 0 + Join + 0 + Legacy + + TailArrow + 0 + + + Tail + + ID + 196 + Info + 1 + + + + Bounds + {{342, 311.99993896484375}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 197 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + VerticalPad + 0 + + + + Bounds + {{396, 208}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 196 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs24 \cf0 subTree\ +Root} + VerticalPad + 0 + + + + Class + LineGraphic + ID + 182 + Points + + {195, 147.00003051757812} + {323, 148.00003051757812} + + Style + + stroke + + HeadArrow + FilledArrow + Join + 0 + Legacy + + TailArrow + 0 + + + + + Bounds + {{58, 42}, {64, 82}} + Class + ShapedGraphic + FitText + YES + Flow + Resize + FontInfo + + Font + HiraKakuPro-W3 + Size + 24 + + ID + 180 + Shape + Circle + Style + + fill + + Color + + b + 0.974573 + g + 0.998064 + r + 1 + + Draws + NO + + shadow + + Color + + a + 0.75 + b + 0.94523 + g + 0.987116 + r + 1 + + Draws + NO + + stroke + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuPro-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs48 \cf0 tree\ +ver1} + + TextRelativeArea + {{0, 0}, {1, 1}} + Wrap + NO + + + Bounds + {{49, 108.50003814697266}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 62 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs24 \cf0 (root)} + VerticalPad + 0 + + + + GridInfo + + GuidesLocked + NO + GuidesVisible + YES + HPages + 1 + ImageCounter + 1 + KeepToScale + + Layers + + + Lock + NO + Name + レイヤー 1 + Print + YES + View + YES + + + LayoutInfo + + Animate + NO + circoMinDist + 18 + circoSeparation + 0.0 + layoutEngine + dot + neatoSeparation + 0.0 + twopiSeparation + 0.0 + + LinksVisible + NO + MagnetsVisible + NO + MasterSheets + + ModificationDate + 2017-01-15 19:39:34 +0000 + Modifier + sister_clown + NotesVisible + NO + Orientation + 2 + OriginVisible + NO + PageBreaks + YES + PrintInfo + + NSBottomMargin + + float + 41 + + NSHorizonalPagination + + coded + BAtzdHJlYW10eXBlZIHoA4QBQISEhAhOU051bWJlcgCEhAdOU1ZhbHVlAISECE5TT2JqZWN0AIWEASqEhAFxlwCG + + NSLeftMargin + + float + 18 + + NSPaperSize + + size + {595, 842} + + NSPrintReverseOrientation + + int + 0 + + NSRightMargin + + float + 18 + + NSTopMargin + + float + 18 + + + PrintOnePage + + ReadOnly + NO + RowAlign + 1 + RowSpacing + 36 + SheetTitle + キャンバス 1 + SmartAlignmentGuidesActive + YES + SmartDistanceGuidesActive + YES + UniqueID + 1 + UseEntirePage + + VPages + 1 + WindowInfo + + CurrentSheet + 0 + ExpandedCanvases + + Frame + {{1061, 69}, {693, 925}} + ListView + + OutlineWidth + 142 + RightSidebar + + ShowRuler + + Sidebar + + SidebarWidth + 120 + VisibleRegion + {{0, 0}, {558, 783}} + Zoom + 1 + ZoomValues + + + キャンバス 1 + 1 + 1 + + + + + diff -r 99d965c02c45 -r da6a6eba893d figures/BadDifTree.pdf Binary file figures/BadDifTree.pdf has changed diff -r 99d965c02c45 -r da6a6eba893d figures/BadDifTree.xbb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/figures/BadDifTree.xbb Tue Jan 24 14:53:52 2017 +0900 @@ -0,0 +1,8 @@ +%%Title: ./BadDifTree.pdf +%%Creator: extractbb 20140317 +%%BoundingBox: 0 0 606 593 +%%HiResBoundingBox: 0.000000 0.000000 606.250000 592.500000 +%%PDFVersion: 1.3 +%%Pages: 1 +%%CreationDate: Tue Jan 24 01:10:15 2017 + diff -r 99d965c02c45 -r da6a6eba893d figures/BadTree.xbb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/figures/BadTree.xbb Tue Jan 24 14:53:52 2017 +0900 @@ -0,0 +1,8 @@ +%%Title: ./BadTree.pdf +%%Creator: extractbb 20140317 +%%BoundingBox: 0 0 606 593 +%%HiResBoundingBox: 0.000000 0.000000 606.250000 592.500000 +%%PDFVersion: 1.3 +%%Pages: 1 +%%CreationDate: Mon Jan 16 04:19:44 2017 + diff -r 99d965c02c45 -r da6a6eba893d figures/EditDifferencialTree.graffle --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/figures/EditDifferencialTree.graffle Tue Jan 24 14:53:52 2017 +0900 @@ -0,0 +1,2000 @@ + + + + + ActiveLayerIndex + 0 + ApplicationVersion + + com.omnigroup.OmniGraffle + 139.16.0.171715 + + AutoAdjust + + BackgroundGraphic + + Bounds + {{0, 0}, {1118, 783}} + Class + SolidGraphic + ID + 2 + Style + + shadow + + Draws + NO + + stroke + + Draws + NO + + + + BaseZoom + 0 + CanvasOrigin + {0, 0} + ColumnAlign + 1 + ColumnSpacing + 36 + CreationDate + 2016-12-20 05:28:41 +0000 + Creator + sister_clown + DisplayScale + 1.000 cm = 1.000 cm + GraphDocumentVersion + 8 + GraphicsList + + + Bounds + {{1034.5, 261}, {58, 46}} + Class + ShapedGraphic + FitText + YES + Flow + Resize + FontInfo + + Font + HiraKakuPro-W3 + Size + 24 + + ID + 120 + Shape + Circle + Style + + fill + + Color + + b + 0.974573 + g + 0.998064 + r + 1 + + Draws + NO + + shadow + + Color + + a + 0.75 + b + 0.94523 + g + 0.987116 + r + 1 + + Draws + NO + + stroke + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuPro-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs48 \cf0 \'95\'db\'8e\'9d} + + TextRelativeArea + {{0, 0}, {1, 1}} + Wrap + NO + + + Bounds + {{163.5, 249.74996948242188}, {58, 46}} + Class + ShapedGraphic + FitText + YES + Flow + Resize + FontInfo + + Font + HiraKakuPro-W3 + Size + 24 + + ID + 119 + Shape + Circle + Style + + fill + + Color + + b + 0.974573 + g + 0.998064 + r + 1 + + Draws + NO + + shadow + + Color + + a + 0.75 + b + 0.94523 + g + 0.987116 + r + 1 + + Draws + NO + + stroke + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuPro-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs48 \cf0 \'95\'db\'8e\'9d} + + TextRelativeArea + {{0, 0}, {1, 1}} + Wrap + NO + + + Class + LineGraphic + ID + 118 + Points + + {941.5, 565.50003899999979} + {941.5, 589} + + Style + + stroke + + Color + + b + 0 + g + 0.0381768 + r + 1 + + HeadArrow + 0 + Join + 0 + Legacy + + TailArrow + 0 + + + + + Class + LineGraphic + ID + 117 + Points + + {941.5, 667.00001525878906} + {941.5, 690.49997625878927} + + Style + + stroke + + Color + + b + 0 + g + 0.0381768 + r + 1 + + HeadArrow + 0 + Join + 0 + Legacy + + TailArrow + 0 + + + + + Bounds + {{901.5, 690.49999575878917}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 116 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + stroke + + Color + + b + 0 + g + 0.0381768 + r + 1 + + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs24 \cf0 6} + VerticalPad + 0 + + + + Bounds + {{901.5, 588.99998474121094}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 115 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + stroke + + Color + + b + 0 + g + 0.0381768 + r + 1 + + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs24 \cf0 5\ +(subTreeRoot)} + VerticalPad + 0 + + + + Class + LineGraphic + Head + + ID + 104 + + ID + 114 + Points + + {940.5, 78.000020499999891} + {940.5, 81.499980500000106} + + Style + + stroke + + HeadArrow + FilledArrow + Join + 0 + Legacy + + TailArrow + 0 + + + Tail + + ID + 112 + + + + Class + LineGraphic + ID + 113 + Points + + {972.49873642632531, 36.632198431881321} + {1027.5, 36} + {1018.5, 734} + {981.5, 734} + + Style + + stroke + + HeadArrow + FilledArrow + Join + 0 + Legacy + + TailArrow + 0 + + + Tail + + ID + 112 + + + + Bounds + {{908.5, -4}, {64, 82}} + Class + ShapedGraphic + FitText + YES + Flow + Resize + FontInfo + + Font + HiraKakuPro-W3 + Size + 24 + + ID + 112 + Shape + Circle + Style + + fill + + Color + + b + 0.974573 + g + 0.998064 + r + 1 + + Draws + NO + + shadow + + Color + + a + 0.75 + b + 0.94523 + g + 0.987116 + r + 1 + + Draws + NO + + stroke + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuPro-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs48 \cf0 Tree\ +ver2} + + TextRelativeArea + {{0, 0}, {1, 1}} + Wrap + NO + + + Class + LineGraphic + ID + 111 + Points + + {940.5, 464} + {940.5, 487.49996100000021} + + Style + + stroke + + HeadArrow + 0 + Join + 0 + Legacy + + TailArrow + 0 + + + + + Bounds + {{900.5, 487.49998050000011}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 110 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs24 \cf0 \'82\'53} + VerticalPad + 0 + + + + Class + LineGraphic + ID + 109 + Points + + {941, 362.5} + {941, 385.99996100000021} + + Style + + stroke + + HeadArrow + 0 + Join + 0 + Legacy + + TailArrow + 0 + + + + + Bounds + {{901, 385.99998050000011}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 108 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs24 \cf0 \'82\'52} + VerticalPad + 0 + + + + Class + LineGraphic + ID + 107 + Points + + {940.5, 261} + {940.5, 284.49996100000021} + + Style + + stroke + + HeadArrow + 0 + Join + 0 + Legacy + + TailArrow + 0 + + + + + Bounds + {{900.5, 284.49998050000011}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 106 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs24 \cf0 \'82\'51} + VerticalPad + 0 + + + + Class + LineGraphic + ID + 105 + Points + + {940.5, 159.50001949999989} + {940.5, 182.99998050000011} + + Style + + stroke + + HeadArrow + 0 + Join + 0 + Legacy + + TailArrow + 0 + + + Tail + + ID + 104 + Info + 1 + + + + Bounds + {{900.5, 81.5}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 104 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs24 \cf0 0\ +(root)} + VerticalPad + 0 + + + + Bounds + {{900.5, 183}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 103 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs24 \cf0 1} + VerticalPad + 0 + + + + Bounds + {{691, 150.50003051757812}, {129, 46}} + Class + ShapedGraphic + FitText + YES + Flow + Resize + FontInfo + + Font + HiraKakuPro-W3 + Size + 24 + + ID + 102 + Shape + Circle + Style + + fill + + Color + + b + 0.974573 + g + 0.998064 + r + 1 + + Draws + NO + + shadow + + Color + + a + 0.75 + b + 0.94523 + g + 0.987116 + r + 1 + + Draws + NO + + stroke + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuPro-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs48 \cf0 2. commit} + + TextRelativeArea + {{0, 0}, {1, 1}} + Wrap + NO + + + Class + LineGraphic + ID + 101 + Points + + {678, 252} + {833, 253} + + Style + + stroke + + HeadArrow + FilledArrow + Join + 0 + Legacy + + TailArrow + 0 + + + + + Class + LineGraphic + ID + 100 + Points + + {603.5, 150.50003051757812} + {603.5, 173.99999151757834} + + Style + + stroke + + Color + + b + 0 + g + 0.0381768 + r + 1 + + HeadArrow + 0 + Join + 0 + Legacy + + TailArrow + 0 + + + + + Bounds + {{563.5, 174.00001101757823}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 99 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + stroke + + Color + + b + 0 + g + 0.0381768 + r + 1 + + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs24 \cf0 6} + VerticalPad + 0 + + + + Bounds + {{562.5, -4}, {82, 46}} + Class + ShapedGraphic + FitText + YES + Flow + Resize + FontInfo + + Font + HiraKakuPro-W3 + Size + 24 + + ID + 98 + Shape + Circle + Style + + fill + + Color + + b + 0.974573 + g + 0.998064 + r + 1 + + Draws + NO + + shadow + + Color + + a + 0.75 + b + 0.94523 + g + 0.987116 + r + 1 + + Draws + NO + + stroke + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuPro-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs48 \cf0 Editor} + + TextRelativeArea + {{0, 0}, {1, 1}} + Wrap + NO + + + Bounds + {{563.5, 72.5}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 97 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs24 \cf0 5\ +(subTreeRoot)} + VerticalPad + 0 + + + + Bounds + {{354.5, 144}, {196, 82}} + Class + ShapedGraphic + FitText + YES + Flow + Resize + FontInfo + + Font + HiraKakuPro-W3 + Size + 24 + + ID + 94 + Shape + Circle + Style + + fill + + Color + + b + 0.974573 + g + 0.998064 + r + 1 + + Draws + NO + + shadow + + Color + + a + 0.75 + b + 0.94523 + g + 0.987116 + r + 1 + + Draws + NO + + stroke + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuPro-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs48 \cf0 1. addNewChild\ +(<-1,0>)} + + TextRelativeArea + {{0, 0}, {1, 1}} + Wrap + NO + + + Class + LineGraphic + ID + 93 + Points + + {375, 251} + {530, 252} + + Style + + stroke + + HeadArrow + FilledArrow + Join + 0 + Legacy + + TailArrow + 0 + + + + + Bounds + {{261.5, -4}, {82, 46}} + Class + ShapedGraphic + FitText + YES + Flow + Resize + FontInfo + + Font + HiraKakuPro-W3 + Size + 24 + + ID + 92 + Shape + Circle + Style + + fill + + Color + + b + 0.974573 + g + 0.998064 + r + 1 + + Draws + NO + + shadow + + Color + + a + 0.75 + b + 0.94523 + g + 0.987116 + r + 1 + + Draws + NO + + stroke + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuPro-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs48 \cf0 Editor} + + TextRelativeArea + {{0, 0}, {1, 1}} + Wrap + NO + + + Bounds + {{262.5, 72.5}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 91 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs24 \cf0 5\ +(subTreeRoot)} + VerticalPad + 0 + + + + Class + LineGraphic + Head + + ID + 62 + + ID + 86 + Points + + {65.5, 69.000020499999891} + {65.5, 72.499980500000106} + + Style + + stroke + + HeadArrow + FilledArrow + Join + 0 + Legacy + + TailArrow + 0 + + + Tail + + ID + 82 + + + + Class + LineGraphic + Head + + ID + 68 + Info + 3 + + ID + 84 + Points + + {97.498575632509016, 27.609773467896233} + {147.5, 27} + {146.5, 520} + {105.50001999999989, 517.49998050000011} + + Style + + stroke + + HeadArrow + FilledArrow + Join + 0 + Legacy + + TailArrow + 0 + + + Tail + + ID + 82 + + + + Bounds + {{33.5, -13}, {64, 82}} + Class + ShapedGraphic + FitText + YES + Flow + Resize + FontInfo + + Font + HiraKakuPro-W3 + Size + 24 + + ID + 82 + Shape + Circle + Style + + fill + + Color + + b + 0.974573 + g + 0.998064 + r + 1 + + Draws + NO + + shadow + + Color + + a + 0.75 + b + 0.94523 + g + 0.987116 + r + 1 + + Draws + NO + + stroke + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuPro-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs48 \cf0 Tree\ +ver1} + + TextRelativeArea + {{0, 0}, {1, 1}} + Wrap + NO + + + Class + LineGraphic + ID + 69 + Points + + {65.5, 455} + {65.5, 478.49996100000021} + + Style + + stroke + + HeadArrow + 0 + Join + 0 + Legacy + + TailArrow + 0 + + + + + Bounds + {{25.5, 478.49998050000011}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 68 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs24 \cf0 \'82\'53} + VerticalPad + 0 + + + + Class + LineGraphic + ID + 67 + Points + + {66, 353.5} + {66, 376.99996100000021} + + Style + + stroke + + HeadArrow + 0 + Join + 0 + Legacy + + TailArrow + 0 + + + + + Bounds + {{26, 376.99998050000011}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 66 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs24 \cf0 \'82\'52} + VerticalPad + 0 + + + + Class + LineGraphic + ID + 65 + Points + + {65.5, 252} + {65.5, 275.49996100000021} + + Style + + stroke + + HeadArrow + 0 + Join + 0 + Legacy + + TailArrow + 0 + + + + + Bounds + {{25.5, 275.49998050000011}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 64 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs24 \cf0 \'82\'51} + VerticalPad + 0 + + + + Class + LineGraphic + ID + 63 + Points + + {65.5, 150.50001949999989} + {65.5, 173.99998050000011} + + Style + + stroke + + HeadArrow + 0 + Join + 0 + Legacy + + TailArrow + 0 + + + Tail + + ID + 62 + Info + 1 + + + + Bounds + {{25.5, 72.5}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 62 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs24 \cf0 0\ +(root)} + VerticalPad + 0 + + + + Bounds + {{25.5, 174}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 61 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs24 \cf0 1} + VerticalPad + 0 + + + + GridInfo + + GuidesLocked + NO + GuidesVisible + YES + HPages + 2 + ImageCounter + 1 + KeepToScale + + Layers + + + Lock + NO + Name + レイヤー 1 + Print + YES + View + YES + + + LayoutInfo + + Animate + NO + circoMinDist + 18 + circoSeparation + 0.0 + layoutEngine + dot + neatoSeparation + 0.0 + twopiSeparation + 0.0 + + LinksVisible + NO + MagnetsVisible + NO + MasterSheets + + ModificationDate + 2017-01-15 15:46:13 +0000 + Modifier + sister_clown + NotesVisible + NO + Orientation + 2 + OriginVisible + NO + PageBreaks + YES + PrintInfo + + NSBottomMargin + + float + 41 + + NSHorizonalPagination + + coded + BAtzdHJlYW10eXBlZIHoA4QBQISEhAhOU051bWJlcgCEhAdOU1ZhbHVlAISECE5TT2JqZWN0AIWEASqEhAFxlwCG + + NSLeftMargin + + float + 18 + + NSPaperSize + + size + {595, 842} + + NSPrintReverseOrientation + + int + 0 + + NSRightMargin + + float + 18 + + NSTopMargin + + float + 18 + + + PrintOnePage + + ReadOnly + NO + RowAlign + 1 + RowSpacing + 36 + SheetTitle + キャンバス 1 + SmartAlignmentGuidesActive + YES + SmartDistanceGuidesActive + YES + UniqueID + 1 + UseEntirePage + + VPages + 1 + WindowInfo + + CurrentSheet + 0 + ExpandedCanvases + + Frame + {{352, 248}, {1568, 929}} + ListView + + OutlineWidth + 142 + RightSidebar + + ShowRuler + + Sidebar + + SidebarWidth + 120 + VisibleRegion + {{-158, -4}, {1433, 787}} + Zoom + 1 + ZoomValues + + + キャンバス 1 + 1 + 1 + + + + + diff -r 99d965c02c45 -r da6a6eba893d figures/EditDifferencialTree.pdf Binary file figures/EditDifferencialTree.pdf has changed diff -r 99d965c02c45 -r da6a6eba893d figures/EditDifferencialTree.xbb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/figures/EditDifferencialTree.xbb Tue Jan 24 14:53:52 2017 +0900 @@ -0,0 +1,8 @@ +%%Title: ./EditDifferencialTree.pdf +%%Creator: extractbb 20140317 +%%BoundingBox: 0 0 1338 980 +%%HiResBoundingBox: 0.000000 0.000000 1337.500000 980.000000 +%%PDFVersion: 1.3 +%%Pages: 1 +%%CreationDate: Tue Jan 24 01:10:15 2017 + diff -r 99d965c02c45 -r da6a6eba893d figures/PushPop.graffle --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/figures/PushPop.graffle Tue Jan 24 14:53:52 2017 +0900 @@ -0,0 +1,798 @@ + + + + + ActiveLayerIndex + 0 + ApplicationVersion + + com.omnigroup.OmniGraffle + 139.16.0.171715 + + AutoAdjust + + BackgroundGraphic + + Bounds + {{0, 0}, {559, 783}} + Class + SolidGraphic + ID + 2 + Style + + shadow + + Draws + NO + + stroke + + Draws + NO + + + + BaseZoom + 0 + CanvasOrigin + {0, 0} + ColumnAlign + 1 + ColumnSpacing + 36 + CreationDate + 2016-12-19 22:39:33 +0000 + Creator + sister_clown + DisplayScale + 1.000 cm = 1.000 cm + GraphDocumentVersion + 8 + GraphicsList + + + Class + LineGraphic + Head + + ID + 17 + Info + 2 + + ID + 30 + Points + + {427, 126.00001949999989} + {427, 145.99998050000011} + + Style + + stroke + + Color + + b + 0.0508814 + g + 0 + r + 1 + + HeadArrow + 0 + Join + 0 + Legacy + + TailArrow + 0 + + + Tail + + ID + 22 + Info + 1 + + + + Bounds + {{387, 48}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 22 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + stroke + + Color + + b + 0 + g + 0.0508814 + r + 1 + + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs24 \cf0 (newTree\ +root)} + VerticalPad + 0 + + + + Class + LineGraphic + Head + + ID + 19 + Info + 2 + + ID + 21 + Points + + {427, 322.00001949999989} + {427, 341.99998050000011} + + Style + + stroke + + HeadArrow + 0 + Join + 0 + Legacy + + TailArrow + 0 + + + Tail + + ID + 18 + Info + 1 + + + + Class + LineGraphic + Head + + ID + 18 + + ID + 20 + Points + + {427, 224.00001949999989} + {427, 243.99998050000011} + + Style + + stroke + + HeadArrow + 0 + Join + 0 + Legacy + + TailArrow + 0 + + + Tail + + ID + 17 + Info + 1 + + + + Bounds + {{387, 342}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 19 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + VerticalPad + 0 + + + + Bounds + {{387, 244}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 18 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + VerticalPad + 0 + + + + Bounds + {{387, 146}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 17 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs24 \cf0 (oldTree\ +root)} + VerticalPad + 0 + + + + Bounds + {{170, 94}, {178, 82}} + Class + ShapedGraphic + FitText + YES + Flow + Resize + FontInfo + + Font + HiraKakuPro-W3 + Size + 24 + + ID + 16 + Shape + Circle + Style + + fill + + Color + + b + 0.974573 + g + 0.998064 + r + 1 + + Draws + NO + + shadow + + Color + + a + 0.75 + b + 0.94523 + g + 0.987116 + r + 1 + + Draws + NO + + stroke + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuPro-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs48 \cf0 \'90\'56\'82\'b5\'82\'ad\'83\'6d\'81\'5b\'83\'68\'82\'f0\ +\'92\'c7\'89\'c1\'82\'b7\'82\'e9} + + TextRelativeArea + {{0, 0}, {1, 1}} + Wrap + NO + + + Class + LineGraphic + ID + 15 + Points + + {170, 190} + {365, 190} + + Style + + stroke + + HeadArrow + FilledArrow + Join + 0 + Legacy + + TailArrow + 0 + + + + + Class + LineGraphic + Head + + ID + 7 + Info + 2 + + ID + 14 + Points + + {108, 224.00001949999989} + {108, 243.99998050000011} + + Style + + stroke + + HeadArrow + 0 + Join + 0 + Legacy + + TailArrow + 0 + + + Tail + + ID + 6 + Info + 1 + + + + Class + LineGraphic + Head + + ID + 6 + + ID + 13 + Points + + {108, 126.00001949999989} + {108, 145.99998050000011} + + Style + + stroke + + HeadArrow + 0 + Join + 0 + Legacy + + TailArrow + 0 + + + Tail + + ID + 5 + Info + 1 + + + + Bounds + {{68, 244}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 7 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + VerticalPad + 0 + + + + Bounds + {{68, 146}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 6 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + VerticalPad + 0 + + + + Bounds + {{68, 48}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 5 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs24 \cf0 (root)} + VerticalPad + 0 + + + + GridInfo + + GuidesLocked + NO + GuidesVisible + YES + HPages + 1 + ImageCounter + 1 + KeepToScale + + Layers + + + Lock + NO + Name + レイヤー 1 + Print + YES + View + YES + + + LayoutInfo + + Animate + NO + circoMinDist + 18 + circoSeparation + 0.0 + layoutEngine + dot + neatoSeparation + 0.0 + twopiSeparation + 0.0 + + LinksVisible + NO + MagnetsVisible + NO + MasterSheets + + ModificationDate + 2016-12-19 23:20:54 +0000 + Modifier + sister_clown + NotesVisible + NO + Orientation + 2 + OriginVisible + NO + PageBreaks + YES + PrintInfo + + NSBottomMargin + + float + 41 + + NSHorizonalPagination + + coded + BAtzdHJlYW10eXBlZIHoA4QBQISEhAhOU051bWJlcgCEhAdOU1ZhbHVlAISECE5TT2JqZWN0AIWEASqEhAFxlwCG + + NSLeftMargin + + float + 18 + + NSPaperSize + + size + {595, 842} + + NSPrintReverseOrientation + + int + 0 + + NSRightMargin + + float + 18 + + NSTopMargin + + float + 18 + + + PrintOnePage + + ReadOnly + NO + RowAlign + 1 + RowSpacing + 36 + SheetTitle + キャンバス 1 + SmartAlignmentGuidesActive + YES + SmartDistanceGuidesActive + YES + UniqueID + 1 + UseEntirePage + + VPages + 1 + WindowInfo + + CurrentSheet + 0 + ExpandedCanvases + + Frame + {{651, 212}, {693, 925}} + ListView + + OutlineWidth + 142 + RightSidebar + + ShowRuler + + Sidebar + + SidebarWidth + 120 + VisibleRegion + {{0, 0}, {558, 783}} + Zoom + 1 + ZoomValues + + + キャンバス 1 + 1 + 1 + + + + + diff -r 99d965c02c45 -r da6a6eba893d figures/PushPop.pdf Binary file figures/PushPop.pdf has changed diff -r 99d965c02c45 -r da6a6eba893d figures/PushPop.xbb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/figures/PushPop.xbb Tue Jan 24 14:53:52 2017 +0900 @@ -0,0 +1,8 @@ +%%Title: ./PushPop.pdf +%%Creator: extractbb 20140317 +%%BoundingBox: 0 0 504 470 +%%HiResBoundingBox: 0.000000 0.000000 503.750000 470.000000 +%%PDFVersion: 1.3 +%%Pages: 1 +%%CreationDate: Tue Jan 24 01:10:15 2017 + diff -r 99d965c02c45 -r da6a6eba893d figures/PushPopDemerit.graffle --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/figures/PushPopDemerit.graffle Tue Jan 24 14:53:52 2017 +0900 @@ -0,0 +1,1003 @@ + + + + + ActiveLayerIndex + 0 + ApplicationVersion + + com.omnigroup.OmniGraffle + 139.16.0.171715 + + AutoAdjust + + BackgroundGraphic + + Bounds + {{0, 0}, {559, 783}} + Class + SolidGraphic + ID + 2 + Style + + shadow + + Draws + NO + + stroke + + Draws + NO + + + + BaseZoom + 0 + CanvasOrigin + {0, 0} + ColumnAlign + 1 + ColumnSpacing + 36 + CreationDate + 2016-12-19 22:48:52 +0000 + Creator + sister_clown + DisplayScale + 1.000 cm = 1.000 cm + GraphDocumentVersion + 8 + GraphicsList + + + Class + LineGraphic + ID + 54 + Points + + {513, 229.50002374121073} + {513, 252.99998474121094} + + Style + + stroke + + Color + + b + 0 + g + 0 + r + 1 + + HeadArrow + 0 + Join + 0 + Legacy + + TailArrow + 0 + + + Tail + + ID + 53 + Info + 1 + + + + Bounds + {{473, 151.50000424121083}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 53 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + stroke + + Color + + b + 0 + g + 0 + r + 1 + + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs24 \cf0 3\ +(root)} + VerticalPad + 0 + + + + Class + LineGraphic + ID + 52 + Points + + {513, 331.00000424121083} + {513, 354.49996524121104} + + Style + + stroke + + HeadArrow + 0 + Join + 0 + Legacy + + TailArrow + 0 + + + Tail + + ID + 51 + Info + 1 + + + + Bounds + {{473, 252.99998474121094}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 51 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs24 \cf0 2} + VerticalPad + 0 + + + + Class + LineGraphic + Head + + ID + 48 + Info + 2 + + ID + 50 + Points + + {513, 432.50000424121083} + {513, 455.99996524121104} + + Style + + stroke + + HeadArrow + 0 + Join + 0 + Legacy + + TailArrow + 0 + + + Tail + + ID + 49 + Info + 1 + + + + Bounds + {{473, 354.49998474121094}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 49 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs24 \cf0 1} + VerticalPad + 0 + + + + Bounds + {{473, 455.99998474121094}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 48 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs24 \cf0 0\ +} + VerticalPad + 0 + + + + Class + LineGraphic + ID + 47 + Points + + {417, 190} + {450, 190} + + Style + + stroke + + HeadArrow + FilledArrow + Join + 0 + Legacy + + TailArrow + 0 + + + + + Class + LineGraphic + ID + 46 + Points + + {354, 229.50001949999989} + {354, 252.99998050000011} + + Style + + stroke + + Color + + b + 0 + g + 0.0254588 + r + 1 + + HeadArrow + 0 + Join + 0 + Legacy + + TailArrow + 0 + + + Tail + + ID + 45 + Info + 1 + + + + Bounds + {{314, 151.5}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 45 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + stroke + + Color + + b + 0 + g + 0.0254588 + r + 1 + + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs24 \cf0 2\ +(root)} + VerticalPad + 0 + + + + Class + LineGraphic + Head + + ID + 42 + Info + 2 + + ID + 44 + Points + + {354, 331.00001949999989} + {354, 354.49998050000011} + + Style + + stroke + + HeadArrow + 0 + Join + 0 + Legacy + + TailArrow + 0 + + + Tail + + ID + 43 + Info + 1 + + + + Bounds + {{314, 253}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 43 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs24 \cf0 1} + VerticalPad + 0 + + + + Bounds + {{314, 354.5}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 42 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs24 \cf0 0\ +} + VerticalPad + 0 + + + + Class + LineGraphic + ID + 39 + Points + + {258, 190} + {291, 190} + + Style + + stroke + + HeadArrow + FilledArrow + Join + 0 + Legacy + + TailArrow + 0 + + + + + Class + LineGraphic + Head + + ID + 31 + Info + 2 + + ID + 38 + Points + + {195, 229.50001949999989} + {195, 252.99998050000011} + + Style + + stroke + + Color + + b + 0 + g + 0.0635679 + r + 1 + + HeadArrow + 0 + Join + 0 + Legacy + + TailArrow + 0 + + + Tail + + ID + 37 + Info + 1 + + + + Bounds + {{155, 151.5}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 37 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + stroke + + Color + + b + 0 + g + 0.0635679 + r + 1 + + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs24 \cf0 1\ +(root)} + VerticalPad + 0 + + + + Bounds + {{155, 253}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 31 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs24 \cf0 0\ +} + VerticalPad + 0 + + + + Class + LineGraphic + ID + 15 + Points + + {109, 190} + {142, 190} + + Style + + stroke + + HeadArrow + FilledArrow + Join + 0 + Legacy + + TailArrow + 0 + + + + + Bounds + {{16, 151.5}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 5 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs24 \cf0 0\ +(root)} + VerticalPad + 0 + + + + GridInfo + + GuidesLocked + NO + GuidesVisible + YES + HPages + 1 + ImageCounter + 1 + KeepToScale + + Layers + + + Lock + NO + Name + レイヤー 1 + Print + YES + View + YES + + + LayoutInfo + + Animate + NO + circoMinDist + 18 + circoSeparation + 0.0 + layoutEngine + dot + neatoSeparation + 0.0 + twopiSeparation + 0.0 + + LinksVisible + NO + MagnetsVisible + NO + MasterSheets + + ModificationDate + 2017-01-14 19:38:27 +0000 + Modifier + sister_clown + NotesVisible + NO + Orientation + 2 + OriginVisible + NO + PageBreaks + YES + PrintInfo + + NSBottomMargin + + float + 41 + + NSHorizonalPagination + + coded + BAtzdHJlYW10eXBlZIHoA4QBQISEhAhOU051bWJlcgCEhAdOU1ZhbHVlAISECE5TT2JqZWN0AIWEASqEhAFxlwCG + + NSLeftMargin + + float + 18 + + NSPaperSize + + size + {595, 842} + + NSPrintReverseOrientation + + int + 0 + + NSRightMargin + + float + 18 + + NSTopMargin + + float + 18 + + + PrintOnePage + + ReadOnly + NO + RowAlign + 1 + RowSpacing + 36 + SheetTitle + キャンバス 1 + SmartAlignmentGuidesActive + YES + SmartDistanceGuidesActive + YES + UniqueID + 1 + UseEntirePage + + VPages + 1 + WindowInfo + + CurrentSheet + 0 + ExpandedCanvases + + Frame + {{675, 192}, {693, 925}} + ListView + + OutlineWidth + 142 + RightSidebar + + ShowRuler + + Sidebar + + SidebarWidth + 120 + VisibleRegion + {{0, 0}, {558, 783}} + Zoom + 1 + ZoomValues + + + キャンバス 1 + 1 + 1 + + + + + diff -r 99d965c02c45 -r da6a6eba893d figures/PushPopDemerit.pdf Binary file figures/PushPopDemerit.pdf has changed diff -r 99d965c02c45 -r da6a6eba893d figures/PushPopDemerit.xbb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/figures/PushPopDemerit.xbb Tue Jan 24 14:53:52 2017 +0900 @@ -0,0 +1,8 @@ +%%Title: ./PushPopDemerit.pdf +%%Creator: extractbb 20140317 +%%BoundingBox: 0 0 676 484 +%%HiResBoundingBox: 0.000000 0.000000 676.250000 483.750000 +%%PDFVersion: 1.3 +%%Pages: 1 +%%CreationDate: Tue Jan 24 01:10:15 2017 + diff -r 99d965c02c45 -r da6a6eba893d figures/badDifTreeCreate.graffle --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/figures/badDifTreeCreate.graffle Tue Jan 24 14:53:52 2017 +0900 @@ -0,0 +1,1211 @@ + + + + + ActiveLayerIndex + 0 + ApplicationVersion + + com.omnigroup.OmniGraffle + 139.16.0.171715 + + AutoAdjust + + BackgroundGraphic + + Bounds + {{0, 0}, {1118, 783}} + Class + SolidGraphic + ID + 2 + Style + + shadow + + Draws + NO + + stroke + + Draws + NO + + + + BaseZoom + 0 + CanvasOrigin + {0, 0} + ColumnAlign + 1 + ColumnSpacing + 36 + CreationDate + 2017-01-15 17:02:21 +0000 + Creator + sister_clown + DisplayScale + 1.000 cm = 1.000 cm + GraphDocumentVersion + 8 + GraphicsList + + + Class + LineGraphic + ID + 219 + Points + + {598.25, 233.00003051757812} + {703.25, 232.00003051757812} + + Style + + stroke + + HeadArrow + FilledArrow + Join + 0 + Legacy + + TailArrow + 0 + + + + + Class + LineGraphic + Head + + ID + 217 + Info + 2 + + ID + 218 + Points + + {730, 377.25001949999989} + {730, 406.74993048242209} + + Style + + stroke + + HeadArrow + 0 + Join + 0 + Legacy + + TailArrow + 0 + + + Tail + + ID + 215 + Info + 1 + + + + Bounds + {{690, 406.74994998242198}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 217 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + VerticalPad + 0 + + + + Class + LineGraphic + Head + + ID + 213 + Info + 2 + + ID + 214 + Points + + {784, 273.25008053515614} + {838, 299.24998050000011} + + Style + + stroke + + HeadArrow + 0 + Join + 0 + Legacy + + TailArrow + 0 + + + Tail + + ID + 206 + Info + 1 + + + + Bounds + {{798, 299.25}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 213 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + VerticalPad + 0 + + + + Class + LineGraphic + Head + + ID + 215 + Info + 2 + + ID + 216 + Points + + {784, 273.25008053515614} + {730, 299.24998050000011} + + Style + + stroke + + HeadArrow + 0 + Join + 0 + Legacy + + TailArrow + 0 + + + Tail + + ID + 206 + Info + 1 + + + + Bounds + {{690, 299.25}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 215 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + VerticalPad + 0 + + + + Bounds + {{744, 195.25006103515625}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 206 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs24 \cf0 subTree\ +Root} + VerticalPad + 0 + + + + Bounds + {{648, 118}, {230, 82}} + Class + ShapedGraphic + FitText + YES + Flow + Resize + FontInfo + + Font + HiraKakuPro-W3 + Size + 24 + + ID + 212 + Shape + Circle + Style + + fill + + Color + + b + 0.974573 + g + 0.998064 + r + 1 + + Draws + NO + + shadow + + Color + + a + 0.75 + b + 0.94523 + g + 0.987116 + r + 1 + + Draws + NO + + stroke + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuPro-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs48 \cf0 4. APPEND_CHILD\ +(<-1,0>,0)} + + TextRelativeArea + {{0, 0}, {1, 1}} + Wrap + NO + + + Class + LineGraphic + ID + 209 + Points + + {340.75, 234.75006103515625} + {445.75, 233.75006103515625} + + Style + + stroke + + HeadArrow + FilledArrow + Join + 0 + Legacy + + TailArrow + 0 + + + + + Class + LineGraphic + Head + + ID + 210 + Info + 2 + + ID + 211 + Points + + {517.5, 271.50005001757802} + {571.5, 297.49994998242198} + + Style + + stroke + + HeadArrow + 0 + Join + 0 + Legacy + + TailArrow + 0 + + + Tail + + ID + 207 + Info + 1 + + + + Bounds + {{531.5, 297.49996948242188}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 210 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + VerticalPad + 0 + + + + Class + LineGraphic + Head + + ID + 205 + Info + 2 + + ID + 208 + Points + + {517.5, 271.50005001757802} + {463.5, 297.49994998242198} + + Style + + stroke + + HeadArrow + 0 + Join + 0 + Legacy + + TailArrow + 0 + + + Tail + + ID + 207 + Info + 1 + + + + Bounds + {{423.5, 297.49996948242188}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 205 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + VerticalPad + 0 + + + + Bounds + {{477.5, 193.50003051757812}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 207 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs24 \cf0 subTree\ +Root} + VerticalPad + 0 + + + + Bounds + {{403, 118}, {229, 82}} + Class + ShapedGraphic + FitText + YES + Flow + Resize + FontInfo + + Font + HiraKakuPro-W3 + Size + 24 + + ID + 204 + Shape + Circle + Style + + fill + + Color + + b + 0.974573 + g + 0.998064 + r + 1 + + Draws + NO + + shadow + + Color + + a + 0.75 + b + 0.94523 + g + 0.987116 + r + 1 + + Draws + NO + + stroke + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuPro-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs48 \cf0 3. APPEND_CHILD\ +(<-1>,0)} + + TextRelativeArea + {{0, 0}, {1, 1}} + Wrap + NO + + + Class + LineGraphic + Head + + ID + 185 + Info + 2 + + ID + 186 + Points + + {269, 271.50005001757802} + {269, 300.99998050000011} + + Style + + stroke + + HeadArrow + 0 + Join + 0 + Legacy + + TailArrow + 0 + + + Tail + + ID + 184 + Info + 1 + + + + Bounds + {{229, 301}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 185 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + VerticalPad + 0 + + + + Bounds + {{229, 193.50003051757812}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 184 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs24 \cf0 subTree\ +Root} + VerticalPad + 0 + + + + Bounds + {{68, 118}, {82, 46}} + Class + ShapedGraphic + FitText + YES + Flow + Resize + FontInfo + + Font + HiraKakuPro-W3 + Size + 24 + + ID + 183 + Shape + Circle + Style + + fill + + Color + + b + 0.974573 + g + 0.998064 + r + 1 + + Draws + NO + + shadow + + Color + + a + 0.75 + b + 0.94523 + g + 0.987116 + r + 1 + + Draws + NO + + stroke + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuPro-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs48 \cf0 Editor} + + TextRelativeArea + {{0, 0}, {1, 1}} + Wrap + NO + + + Bounds + {{70, 193.50002288818359}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 182 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs24 \cf0 subTree\ +Root} + VerticalPad + 0 + + + + Bounds + {{165, 118}, {229, 82}} + Class + ShapedGraphic + FitText + YES + Flow + Resize + FontInfo + + Font + HiraKakuPro-W3 + Size + 24 + + ID + 122 + Shape + Circle + Style + + fill + + Color + + b + 0.974573 + g + 0.998064 + r + 1 + + Draws + NO + + shadow + + Color + + a + 0.75 + b + 0.94523 + g + 0.987116 + r + 1 + + Draws + NO + + stroke + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuPro-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs48 \cf0 1. APPEND_CHILD\ +(<-1>,0)} + + TextRelativeArea + {{0, 0}, {1, 1}} + Wrap + NO + + + Class + LineGraphic + ID + 121 + Points + + {165, 233.00003051757812} + {194, 232.00003051757812} + + Style + + stroke + + HeadArrow + FilledArrow + Join + 0 + Legacy + + TailArrow + 0 + + + + + GridInfo + + GuidesLocked + NO + GuidesVisible + YES + HPages + 2 + ImageCounter + 1 + KeepToScale + + Layers + + + Lock + NO + Name + レイヤー 1 + Print + YES + View + YES + + + LayoutInfo + + Animate + NO + circoMinDist + 18 + circoSeparation + 0.0 + layoutEngine + dot + neatoSeparation + 0.0 + twopiSeparation + 0.0 + + LinksVisible + NO + MagnetsVisible + NO + MasterSheets + + ModificationDate + 2017-01-23 16:07:43 +0000 + Modifier + sister_clown + NotesVisible + NO + Orientation + 2 + OriginVisible + NO + PageBreaks + YES + PrintInfo + + NSBottomMargin + + float + 41 + + NSHorizonalPagination + + coded + BAtzdHJlYW10eXBlZIHoA4QBQISEhAhOU051bWJlcgCEhAdOU1ZhbHVlAISECE5TT2JqZWN0AIWEASqEhAFxlwCG + + NSLeftMargin + + float + 18 + + NSPaperSize + + size + {595, 842} + + NSPrintReverseOrientation + + int + 0 + + NSRightMargin + + float + 18 + + NSTopMargin + + float + 18 + + + PrintOnePage + + ReadOnly + NO + RowAlign + 1 + RowSpacing + 36 + SheetTitle + キャンバス 1 + SmartAlignmentGuidesActive + YES + SmartDistanceGuidesActive + YES + UniqueID + 1 + UseEntirePage + + VPages + 1 + WindowInfo + + CurrentSheet + 0 + ExpandedCanvases + + Frame + {{229, 61}, {1691, 1116}} + ListView + + OutlineWidth + 142 + RightSidebar + + ShowRuler + + Sidebar + + SidebarWidth + 120 + VisibleRegion + {{-219, -95}, {1556, 974}} + Zoom + 1 + ZoomValues + + + キャンバス 1 + 1 + 1 + + + + + diff -r 99d965c02c45 -r da6a6eba893d figures/badDifTreeCreate.pdf Binary file figures/badDifTreeCreate.pdf has changed diff -r 99d965c02c45 -r da6a6eba893d figures/badDifTreeCreate.xbb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/figures/badDifTreeCreate.xbb Tue Jan 24 14:53:52 2017 +0900 @@ -0,0 +1,8 @@ +%%Title: ./badDifTreeCreate.pdf +%%Creator: extractbb 20140317 +%%BoundingBox: 0 0 1015 461 +%%HiResBoundingBox: 0.000000 0.000000 1015.000000 461.250000 +%%PDFVersion: 1.3 +%%Pages: 1 +%%CreationDate: Tue Jan 24 01:10:15 2017 + diff -r 99d965c02c45 -r da6a6eba893d figures/destructive_tree.pdf Binary file figures/destructive_tree.pdf has changed diff -r 99d965c02c45 -r da6a6eba893d figures/destructive_tree.xbb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/figures/destructive_tree.xbb Tue Jan 24 14:53:52 2017 +0900 @@ -0,0 +1,8 @@ +%%Title: ./destructive_tree.pdf +%%Creator: extractbb 20140317 +%%BoundingBox: 0 0 404 207 +%%HiResBoundingBox: 0.000000 0.000000 404.000000 207.000000 +%%PDFVersion: 1.4 +%%Pages: 1 +%%CreationDate: Tue Jan 24 01:10:15 2017 + diff -r 99d965c02c45 -r da6a6eba893d figures/goodDifTree.graffle --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/figures/goodDifTree.graffle Tue Jan 24 14:53:52 2017 +0900 @@ -0,0 +1,1292 @@ + + + + + ActiveLayerIndex + 0 + ApplicationVersion + + com.omnigroup.OmniGraffle + 139.16.0.171715 + + AutoAdjust + + BackgroundGraphic + + Bounds + {{0, 0}, {1118, 783}} + Class + SolidGraphic + ID + 2 + Style + + shadow + + Draws + NO + + stroke + + Draws + NO + + + + BaseZoom + 0 + CanvasOrigin + {0, 0} + ColumnAlign + 1 + ColumnSpacing + 36 + CreationDate + 2017-01-15 19:38:41 +0000 + Creator + sister_clown + DisplayScale + 1.000 cm = 1.000 cm + GraphDocumentVersion + 8 + GraphicsList + + + Bounds + {{501, 62.5}, {125, 46}} + Class + ShapedGraphic + FitText + YES + Flow + Resize + FontInfo + + Font + HiraKakuPro-W3 + Size + 24 + + ID + 222 + Shape + Circle + Style + + fill + + Color + + b + 0.974573 + g + 0.998064 + r + 1 + + Draws + NO + + shadow + + Color + + a + 0.75 + b + 0.94523 + g + 0.987116 + r + 1 + + Draws + NO + + stroke + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuPro-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs48 \cf0 5.Commit} + + TextRelativeArea + {{0, 0}, {1, 1}} + Wrap + NO + + + Class + LineGraphic + ID + 221 + Points + + {499.5, 136.0001220703125} + {627.5, 137.0001220703125} + + Style + + stroke + + HeadArrow + FilledArrow + Join + 0 + Legacy + + TailArrow + 0 + + + + + Class + LineGraphic + Head + + ID + 219 + Info + 2 + + ID + 220 + Points + + {691, 601.49981689453125} + {691, 627.49971685937521} + + Style + + stroke + + HeadArrow + 0 + Join + 0 + Legacy + + TailArrow + 0 + + + + + Bounds + {{651, 627.49973635937511}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 219 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + VerticalPad + 0 + + + + Class + LineGraphic + Head + + ID + 217 + Info + 2 + + ID + 218 + Points + + {691, 497.4998779296875} + {691, 523.49977789453146} + + Style + + stroke + + HeadArrow + 0 + Join + 0 + Legacy + + TailArrow + 0 + + + + + Bounds + {{651, 523.49979739453136}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 217 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + VerticalPad + 0 + + + + Bounds + {{659, 26.5}, {64, 82}} + Class + ShapedGraphic + FitText + YES + Flow + Resize + FontInfo + + Font + HiraKakuPro-W3 + Size + 24 + + ID + 216 + Shape + Circle + Style + + fill + + Color + + b + 0.974573 + g + 0.998064 + r + 1 + + Draws + NO + + shadow + + Color + + a + 0.75 + b + 0.94523 + g + 0.987116 + r + 1 + + Draws + NO + + stroke + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuPro-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs48 \cf0 tree\ +ver3} + + TextRelativeArea + {{0, 0}, {1, 1}} + Wrap + NO + + + Class + LineGraphic + Head + + ID + 212 + Info + 2 + + ID + 215 + Points + + {691, 389.99995846484364} + {691, 419.49986944726584} + + Style + + stroke + + HeadArrow + 0 + Join + 0 + Legacy + + TailArrow + 0 + + + Tail + + ID + 208 + Info + 1 + + + + Class + LineGraphic + Head + + ID + 207 + + ID + 214 + Points + + {691, 186.50001949999989} + {691, 207.99998050000011} + + Style + + stroke + + HeadArrow + 0 + Join + 0 + Legacy + + TailArrow + 0 + + + Tail + + ID + 213 + Info + 1 + + + + Bounds + {{651, 108.5}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 213 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs24 \cf0 (root)} + VerticalPad + 0 + + + + Bounds + {{651, 419.49988894726573}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 212 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs24 \cf0 subTreeRoot2} + VerticalPad + 0 + + + + Class + LineGraphic + Head + + ID + 208 + Info + 2 + + ID + 209 + Points + + {691, 286.00001949999989} + {691, 311.99991946484386} + + Style + + stroke + + HeadArrow + 0 + Join + 0 + Legacy + + TailArrow + 0 + + + Tail + + ID + 207 + Info + 1 + + + + Bounds + {{651, 311.99993896484375}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 208 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + VerticalPad + 0 + + + + Bounds + {{651, 208}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 207 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs24 \cf0 subTree\ +Root} + VerticalPad + 0 + + + + Bounds + {{181, 62.5}, {125, 46}} + Class + ShapedGraphic + FitText + YES + Flow + Resize + FontInfo + + Font + HiraKakuPro-W3 + Size + 24 + + ID + 206 + Shape + Circle + Style + + fill + + Color + + b + 0.974573 + g + 0.998064 + r + 1 + + Draws + NO + + shadow + + Color + + a + 0.75 + b + 0.94523 + g + 0.987116 + r + 1 + + Draws + NO + + stroke + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuPro-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs48 \cf0 2.Commit} + + TextRelativeArea + {{0, 0}, {1, 1}} + Wrap + NO + + + Bounds + {{404, 26.5}, {64, 82}} + Class + ShapedGraphic + FitText + YES + Flow + Resize + FontInfo + + Font + HiraKakuPro-W3 + Size + 24 + + ID + 205 + Shape + Circle + Style + + fill + + Color + + b + 0.974573 + g + 0.998064 + r + 1 + + Draws + NO + + shadow + + Color + + a + 0.75 + b + 0.94523 + g + 0.987116 + r + 1 + + Draws + NO + + stroke + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuPro-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs48 \cf0 tree\ +ver2} + + TextRelativeArea + {{0, 0}, {1, 1}} + Wrap + NO + + + Class + LineGraphic + Head + + ID + 196 + + ID + 203 + Points + + {436, 186.50001949999989} + {436, 207.99998050000011} + + Style + + stroke + + HeadArrow + 0 + Join + 0 + Legacy + + TailArrow + 0 + + + Tail + + ID + 202 + Info + 1 + + + + Bounds + {{396, 108.5}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 202 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs24 \cf0 (root)} + VerticalPad + 0 + + + + Class + LineGraphic + Head + + ID + 197 + Info + 2 + + ID + 198 + Points + + {436, 286.00001949999989} + {436, 311.99991946484386} + + Style + + stroke + + HeadArrow + 0 + Join + 0 + Legacy + + TailArrow + 0 + + + Tail + + ID + 196 + Info + 1 + + + + Bounds + {{396, 311.99993896484375}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 197 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + VerticalPad + 0 + + + + Bounds + {{396, 208}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 196 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs24 \cf0 subTree\ +Root} + VerticalPad + 0 + + + + Class + LineGraphic + ID + 182 + Points + + {179.5, 136.0001220703125} + {307.5, 137.0001220703125} + + Style + + stroke + + HeadArrow + FilledArrow + Join + 0 + Legacy + + TailArrow + 0 + + + + + Bounds + {{58, 42}, {64, 82}} + Class + ShapedGraphic + FitText + YES + Flow + Resize + FontInfo + + Font + HiraKakuPro-W3 + Size + 24 + + ID + 180 + Shape + Circle + Style + + fill + + Color + + b + 0.974573 + g + 0.998064 + r + 1 + + Draws + NO + + shadow + + Color + + a + 0.75 + b + 0.94523 + g + 0.987116 + r + 1 + + Draws + NO + + stroke + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuPro-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs48 \cf0 tree\ +ver1} + + TextRelativeArea + {{0, 0}, {1, 1}} + Wrap + NO + + + Bounds + {{49, 108.50003814697266}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 62 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs24 \cf0 (root)} + VerticalPad + 0 + + + + GridInfo + + GuidesLocked + NO + GuidesVisible + YES + HPages + 2 + ImageCounter + 1 + KeepToScale + + Layers + + + Lock + NO + Name + レイヤー 1 + Print + YES + View + YES + + + LayoutInfo + + Animate + NO + circoMinDist + 18 + circoSeparation + 0.0 + layoutEngine + dot + neatoSeparation + 0.0 + twopiSeparation + 0.0 + + LinksVisible + NO + MagnetsVisible + NO + MasterSheets + + ModificationDate + 2017-01-15 19:49:36 +0000 + Modifier + sister_clown + NotesVisible + NO + Orientation + 2 + OriginVisible + NO + PageBreaks + YES + PrintInfo + + NSBottomMargin + + float + 41 + + NSHorizonalPagination + + coded + BAtzdHJlYW10eXBlZIHoA4QBQISEhAhOU051bWJlcgCEhAdOU1ZhbHVlAISECE5TT2JqZWN0AIWEASqEhAFxlwCG + + NSLeftMargin + + float + 18 + + NSPaperSize + + size + {595, 842} + + NSPrintReverseOrientation + + int + 0 + + NSRightMargin + + float + 18 + + NSTopMargin + + float + 18 + + + PrintOnePage + + ReadOnly + NO + RowAlign + 1 + RowSpacing + 36 + SheetTitle + キャンバス 1 + SmartAlignmentGuidesActive + YES + SmartDistanceGuidesActive + YES + UniqueID + 1 + UseEntirePage + + VPages + 1 + WindowInfo + + CurrentSheet + 0 + ExpandedCanvases + + Frame + {{715, 152}, {915, 925}} + ListView + + OutlineWidth + 142 + RightSidebar + + ShowRuler + + Sidebar + + SidebarWidth + 120 + VisibleRegion + {{16, 0}, {780, 783}} + Zoom + 1 + ZoomValues + + + キャンバス 1 + 1 + 1 + + + + + diff -r 99d965c02c45 -r da6a6eba893d figures/goodDifTree.pdf Binary file figures/goodDifTree.pdf has changed diff -r 99d965c02c45 -r da6a6eba893d figures/goodDifTree.xbb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/figures/goodDifTree.xbb Tue Jan 24 14:53:52 2017 +0900 @@ -0,0 +1,8 @@ +%%Title: ./goodDifTree.pdf +%%Creator: extractbb 20140317 +%%BoundingBox: 0 0 858 853 +%%HiResBoundingBox: 0.000000 0.000000 857.500000 852.500000 +%%PDFVersion: 1.3 +%%Pages: 1 +%%CreationDate: Tue Jan 24 01:10:15 2017 + diff -r 99d965c02c45 -r da6a6eba893d figures/goodDifTreeCreate1.graffle --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/figures/goodDifTreeCreate1.graffle Tue Jan 24 14:53:52 2017 +0900 @@ -0,0 +1,543 @@ + + + + + ActiveLayerIndex + 0 + ApplicationVersion + + com.omnigroup.OmniGraffle + 139.16.0.171715 + + AutoAdjust + + BackgroundGraphic + + Bounds + {{0, 0}, {559, 783}} + Class + SolidGraphic + ID + 2 + Style + + shadow + + Draws + NO + + stroke + + Draws + NO + + + + BaseZoom + 0 + CanvasOrigin + {0, 0} + ColumnAlign + 1 + ColumnSpacing + 36 + CreationDate + 2017-01-15 19:30:34 +0000 + Creator + sister_clown + DisplayScale + 1.000 cm = 1.000 cm + GraphDocumentVersion + 8 + GraphicsList + + + Class + LineGraphic + Head + + ID + 185 + Info + 2 + + ID + 186 + Points + + {433, 238.50005001757802} + {433, 267.99998050000011} + + Style + + stroke + + HeadArrow + 0 + Join + 0 + Legacy + + TailArrow + 0 + + + Tail + + ID + 184 + Info + 1 + + + + Bounds + {{393, 268}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 185 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + VerticalPad + 0 + + + + Bounds + {{393, 160.50003051757812}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 184 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs24 \cf0 subTree\ +Root1} + VerticalPad + 0 + + + + Bounds + {{63, 85}, {82, 46}} + Class + ShapedGraphic + FitText + YES + Flow + Resize + FontInfo + + Font + HiraKakuPro-W3 + Size + 24 + + ID + 183 + Shape + Circle + Style + + fill + + Color + + b + 0.974573 + g + 0.998064 + r + 1 + + Draws + NO + + shadow + + Color + + a + 0.75 + b + 0.94523 + g + 0.987116 + r + 1 + + Draws + NO + + stroke + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuPro-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs48 \cf0 Editor} + + TextRelativeArea + {{0, 0}, {1, 1}} + Wrap + NO + + + Bounds + {{65, 160.50002288818359}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 182 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs24 \cf0 subTree\ +Root1} + VerticalPad + 0 + + + + Bounds + {{160, 85}, {229, 82}} + Class + ShapedGraphic + FitText + YES + Flow + Resize + FontInfo + + Font + HiraKakuPro-W3 + Size + 24 + + ID + 122 + Shape + Circle + Style + + fill + + Color + + b + 0.974573 + g + 0.998064 + r + 1 + + Draws + NO + + shadow + + Color + + a + 0.75 + b + 0.94523 + g + 0.987116 + r + 1 + + Draws + NO + + stroke + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuPro-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs48 \cf0 1. APPEND_CHILD\ +(<-1>,0)} + + TextRelativeArea + {{0, 0}, {1, 1}} + Wrap + NO + + + Class + LineGraphic + ID + 121 + Points + + {197, 199.00003051757812} + {352, 200.00003051757812} + + Style + + stroke + + HeadArrow + FilledArrow + Join + 0 + Legacy + + TailArrow + 0 + + + + + GridInfo + + GuidesLocked + NO + GuidesVisible + YES + HPages + 1 + ImageCounter + 1 + KeepToScale + + Layers + + + Lock + NO + Name + レイヤー 1 + Print + YES + View + YES + + + LayoutInfo + + Animate + NO + circoMinDist + 18 + circoSeparation + 0.0 + layoutEngine + dot + neatoSeparation + 0.0 + twopiSeparation + 0.0 + + LinksVisible + NO + MagnetsVisible + NO + MasterSheets + + ModificationDate + 2017-01-15 19:30:46 +0000 + Modifier + sister_clown + NotesVisible + NO + Orientation + 2 + OriginVisible + NO + PageBreaks + YES + PrintInfo + + NSBottomMargin + + float + 41 + + NSHorizonalPagination + + coded + BAtzdHJlYW10eXBlZIHoA4QBQISEhAhOU051bWJlcgCEhAdOU1ZhbHVlAISECE5TT2JqZWN0AIWEASqEhAFxlwCG + + NSLeftMargin + + float + 18 + + NSPaperSize + + size + {595, 842} + + NSPrintReverseOrientation + + int + 0 + + NSRightMargin + + float + 18 + + NSTopMargin + + float + 18 + + + PrintOnePage + + ReadOnly + NO + RowAlign + 1 + RowSpacing + 36 + SheetTitle + キャンバス 1 + SmartAlignmentGuidesActive + YES + SmartDistanceGuidesActive + YES + UniqueID + 1 + UseEntirePage + + VPages + 1 + WindowInfo + + CurrentSheet + 0 + ExpandedCanvases + + Frame + {{675, 192}, {693, 925}} + ListView + + OutlineWidth + 142 + RightSidebar + + ShowRuler + + Sidebar + + SidebarWidth + 120 + VisibleRegion + {{0, 0}, {558, 783}} + Zoom + 1 + ZoomValues + + + キャンバス 1 + 1 + 1 + + + + + diff -r 99d965c02c45 -r da6a6eba893d figures/goodDifTreeCreate1.pdf Binary file figures/goodDifTreeCreate1.pdf has changed diff -r 99d965c02c45 -r da6a6eba893d figures/goodDifTreeCreate1.xbb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/figures/goodDifTreeCreate1.xbb Tue Jan 24 14:53:52 2017 +0900 @@ -0,0 +1,8 @@ +%%Title: ./goodDifTreeCreate1.pdf +%%Creator: extractbb 20140317 +%%BoundingBox: 0 0 515 329 +%%HiResBoundingBox: 0.000000 0.000000 515.000000 328.750000 +%%PDFVersion: 1.3 +%%Pages: 1 +%%CreationDate: Tue Jan 24 01:10:15 2017 + diff -r 99d965c02c45 -r da6a6eba893d figures/goodDifTreeCreate2.graffle --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/figures/goodDifTreeCreate2.graffle Tue Jan 24 14:53:52 2017 +0900 @@ -0,0 +1,832 @@ + + + + + ActiveLayerIndex + 0 + ApplicationVersion + + com.omnigroup.OmniGraffle + 139.16.0.171715 + + AutoAdjust + + BackgroundGraphic + + Bounds + {{0, 0}, {1118, 783}} + Class + SolidGraphic + ID + 2 + Style + + shadow + + Draws + NO + + stroke + + Draws + NO + + + + BaseZoom + 0 + CanvasOrigin + {0, 0} + ColumnAlign + 1 + ColumnSpacing + 36 + CreationDate + 2017-01-15 19:31:32 +0000 + Creator + sister_clown + DisplayScale + 1.000 cm = 1.000 cm + GraphDocumentVersion + 8 + GraphicsList + + + Class + LineGraphic + Head + + ID + 192 + Info + 2 + + ID + 193 + Points + + {691, 304} + {691, 333.49993048242209} + + Style + + stroke + + HeadArrow + 0 + Join + 0 + Legacy + + TailArrow + 0 + + + + + Bounds + {{651, 333.49994998242198}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 192 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + VerticalPad + 0 + + + + Class + LineGraphic + Head + + ID + 190 + Info + 2 + + ID + 191 + Points + + {691, 196.50005001757802} + {691, 225.99998050000011} + + Style + + stroke + + HeadArrow + 0 + Join + 0 + Legacy + + TailArrow + 0 + + + Tail + + ID + 189 + Info + 1 + + + + Bounds + {{651, 226}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 190 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + VerticalPad + 0 + + + + Bounds + {{651, 118.50003051757812}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 189 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs24 \cf0 subTree\ +Root2} + VerticalPad + 0 + + + + Bounds + {{402.5, 43}, {230, 82}} + Class + ShapedGraphic + FitText + YES + Flow + Resize + FontInfo + + Font + HiraKakuPro-W3 + Size + 24 + + ID + 188 + Shape + Circle + Style + + fill + + Color + + b + 0.974573 + g + 0.998064 + r + 1 + + Draws + NO + + shadow + + Color + + a + 0.75 + b + 0.94523 + g + 0.987116 + r + 1 + + Draws + NO + + stroke + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuPro-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs48 \cf0 4. APPEND_CHILD\ +(<-1,0>,0)} + + TextRelativeArea + {{0, 0}, {1, 1}} + Wrap + NO + + + Class + LineGraphic + ID + 187 + Points + + {436, 157.00006103515625} + {616, 157} + + Style + + stroke + + HeadArrow + FilledArrow + Join + 0 + Legacy + + TailArrow + 0 + + + + + Class + LineGraphic + Head + + ID + 185 + Info + 2 + + ID + 186 + Points + + {370, 196.50005001757802} + {370, 225.99998050000011} + + Style + + stroke + + HeadArrow + 0 + Join + 0 + Legacy + + TailArrow + 0 + + + Tail + + ID + 184 + Info + 1 + + + + Bounds + {{330, 226}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 185 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + VerticalPad + 0 + + + + Bounds + {{330, 118.50003051757812}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 184 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs24 \cf0 subTree\ +Root2} + VerticalPad + 0 + + + + Bounds + {{0, 43}, {82, 46}} + Class + ShapedGraphic + FitText + YES + Flow + Resize + FontInfo + + Font + HiraKakuPro-W3 + Size + 24 + + ID + 183 + Shape + Circle + Style + + fill + + Color + + b + 0.974573 + g + 0.998064 + r + 1 + + Draws + NO + + shadow + + Color + + a + 0.75 + b + 0.94523 + g + 0.987116 + r + 1 + + Draws + NO + + stroke + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuPro-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs48 \cf0 Editor} + + TextRelativeArea + {{0, 0}, {1, 1}} + Wrap + NO + + + Bounds + {{2, 118.50002288818359}, {80, 78}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 182 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs24 \cf0 subTree\ +Root2} + VerticalPad + 0 + + + + Bounds + {{82, 43}, {229, 82}} + Class + ShapedGraphic + FitText + YES + Flow + Resize + FontInfo + + Font + HiraKakuPro-W3 + Size + 24 + + ID + 122 + Shape + Circle + Style + + fill + + Color + + b + 0.974573 + g + 0.998064 + r + 1 + + Draws + NO + + shadow + + Color + + a + 0.75 + b + 0.94523 + g + 0.987116 + r + 1 + + Draws + NO + + stroke + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuPro-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs48 \cf0 3. APPEND_CHILD\ +(<-1>,0)} + + TextRelativeArea + {{0, 0}, {1, 1}} + Wrap + NO + + + Class + LineGraphic + ID + 121 + Points + + {115, 157.00006103515625} + {295, 157} + + Style + + stroke + + HeadArrow + FilledArrow + Join + 0 + Legacy + + TailArrow + 0 + + + + + GridInfo + + GuidesLocked + NO + GuidesVisible + YES + HPages + 2 + ImageCounter + 1 + KeepToScale + + Layers + + + Lock + NO + Name + レイヤー 1 + Print + YES + View + YES + + + LayoutInfo + + Animate + NO + circoMinDist + 18 + circoSeparation + 0.0 + layoutEngine + dot + neatoSeparation + 0.0 + twopiSeparation + 0.0 + + LinksVisible + NO + MagnetsVisible + NO + MasterSheets + + ModificationDate + 2017-01-15 19:40:24 +0000 + Modifier + sister_clown + NotesVisible + NO + Orientation + 2 + OriginVisible + NO + PageBreaks + YES + PrintInfo + + NSBottomMargin + + float + 41 + + NSHorizonalPagination + + coded + BAtzdHJlYW10eXBlZIHoA4QBQISEhAhOU051bWJlcgCEhAdOU1ZhbHVlAISECE5TT2JqZWN0AIWEASqEhAFxlwCG + + NSLeftMargin + + float + 18 + + NSPaperSize + + size + {595, 842} + + NSPrintReverseOrientation + + int + 0 + + NSRightMargin + + float + 18 + + NSTopMargin + + float + 18 + + + PrintOnePage + + ReadOnly + NO + RowAlign + 1 + RowSpacing + 36 + SheetTitle + キャンバス 1 + SmartAlignmentGuidesActive + YES + SmartDistanceGuidesActive + YES + UniqueID + 1 + UseEntirePage + + VPages + 1 + WindowInfo + + CurrentSheet + 0 + ExpandedCanvases + + Frame + {{695, 172}, {932, 925}} + ListView + + OutlineWidth + 142 + RightSidebar + + ShowRuler + + Sidebar + + SidebarWidth + 120 + VisibleRegion + {{0, 0}, {797, 783}} + Zoom + 1 + ZoomValues + + + キャンバス 1 + 1 + 1 + + + + + diff -r 99d965c02c45 -r da6a6eba893d figures/goodDifTreeCreate2.pdf Binary file figures/goodDifTreeCreate2.pdf has changed diff -r 99d965c02c45 -r da6a6eba893d figures/goodDifTreeCreate2.xbb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/figures/goodDifTreeCreate2.xbb Tue Jan 24 14:53:52 2017 +0900 @@ -0,0 +1,8 @@ +%%Title: ./goodDifTreeCreate2.pdf +%%Creator: extractbb 20140317 +%%BoundingBox: 0 0 916 464 +%%HiResBoundingBox: 0.000000 0.000000 916.250000 463.750000 +%%PDFVersion: 1.3 +%%Pages: 1 +%%CreationDate: Tue Jan 24 01:10:15 2017 + diff -r 99d965c02c45 -r da6a6eba893d figures/nodepath.pdf Binary file figures/nodepath.pdf has changed diff -r 99d965c02c45 -r da6a6eba893d figures/nodepath.xbb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/figures/nodepath.xbb Tue Jan 24 14:53:52 2017 +0900 @@ -0,0 +1,8 @@ +%%Title: ./nodepath.pdf +%%Creator: extractbb 20140317 +%%BoundingBox: 0 0 315 340 +%%HiResBoundingBox: 0.000000 0.000000 315.000000 340.000000 +%%PDFVersion: 1.3 +%%Pages: 1 +%%CreationDate: Tue Jan 24 01:10:15 2017 + diff -r 99d965c02c45 -r da6a6eba893d figures/non_destructive_edit1.pdf Binary file figures/non_destructive_edit1.pdf has changed diff -r 99d965c02c45 -r da6a6eba893d figures/non_destructive_edit1.xbb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/figures/non_destructive_edit1.xbb Tue Jan 24 14:53:52 2017 +0900 @@ -0,0 +1,8 @@ +%%Title: ./non_destructive_edit1.pdf +%%Creator: extractbb 20140317 +%%BoundingBox: 0 0 462 207 +%%HiResBoundingBox: 0.000000 0.000000 462.000000 207.000000 +%%PDFVersion: 1.4 +%%Pages: 1 +%%CreationDate: Tue Jan 24 01:10:15 2017 + diff -r 99d965c02c45 -r da6a6eba893d figures/non_destructive_edit2.pdf Binary file figures/non_destructive_edit2.pdf has changed diff -r 99d965c02c45 -r da6a6eba893d figures/non_destructive_edit2.xbb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/figures/non_destructive_edit2.xbb Tue Jan 24 14:53:52 2017 +0900 @@ -0,0 +1,8 @@ +%%Title: ./non_destructive_edit2.pdf +%%Creator: extractbb 20140317 +%%BoundingBox: 0 0 470 240 +%%HiResBoundingBox: 0.000000 0.000000 470.000000 240.000000 +%%PDFVersion: 1.4 +%%Pages: 1 +%%CreationDate: Tue Jan 24 01:10:15 2017 + diff -r 99d965c02c45 -r da6a6eba893d figures/non_destructive_edit3.pdf Binary file figures/non_destructive_edit3.pdf has changed diff -r 99d965c02c45 -r da6a6eba893d figures/non_destructive_edit3.xbb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/figures/non_destructive_edit3.xbb Tue Jan 24 14:53:52 2017 +0900 @@ -0,0 +1,8 @@ +%%Title: ./non_destructive_edit3.pdf +%%Creator: extractbb 20140317 +%%BoundingBox: 0 0 511 211 +%%HiResBoundingBox: 0.000000 0.000000 511.000000 211.000000 +%%PDFVersion: 1.4 +%%Pages: 1 +%%CreationDate: Tue Jan 24 01:10:15 2017 + diff -r 99d965c02c45 -r da6a6eba893d figures/non_destructive_edit4.pdf Binary file figures/non_destructive_edit4.pdf has changed diff -r 99d965c02c45 -r da6a6eba893d figures/non_destructive_edit4.xbb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/figures/non_destructive_edit4.xbb Tue Jan 24 14:53:52 2017 +0900 @@ -0,0 +1,8 @@ +%%Title: ./non_destructive_edit4.pdf +%%Creator: extractbb 20140317 +%%BoundingBox: 0 0 505 218 +%%HiResBoundingBox: 0.000000 0.000000 505.000000 218.000000 +%%PDFVersion: 1.4 +%%Pages: 1 +%%CreationDate: Tue Jan 24 01:10:15 2017 + diff -r 99d965c02c45 -r da6a6eba893d figures/non_destructive_merit.pdf Binary file figures/non_destructive_merit.pdf has changed diff -r 99d965c02c45 -r da6a6eba893d figures/non_destructive_merit.xbb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/figures/non_destructive_merit.xbb Tue Jan 24 14:53:52 2017 +0900 @@ -0,0 +1,8 @@ +%%Title: ./non_destructive_merit.pdf +%%Creator: extractbb 20140317 +%%BoundingBox: 0 0 350 301 +%%HiResBoundingBox: 0.000000 0.000000 350.000000 301.000000 +%%PDFVersion: 1.4 +%%Pages: 1 +%%CreationDate: Tue Jan 24 01:10:15 2017 + diff -r 99d965c02c45 -r da6a6eba893d figures/non_destructive_tree.pdf Binary file figures/non_destructive_tree.pdf has changed diff -r 99d965c02c45 -r da6a6eba893d figures/non_destructive_tree.xbb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/figures/non_destructive_tree.xbb Tue Jan 24 14:53:52 2017 +0900 @@ -0,0 +1,8 @@ +%%Title: ./non_destructive_tree.pdf +%%Creator: extractbb 20140317 +%%BoundingBox: 0 0 459 207 +%%HiResBoundingBox: 0.000000 0.000000 459.000000 207.000000 +%%PDFVersion: 1.4 +%%Pages: 1 +%%CreationDate: Tue Jan 24 01:10:15 2017 + diff -r 99d965c02c45 -r da6a6eba893d introduciton.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/introduciton.tex Tue Jan 24 14:53:52 2017 +0900 @@ -0,0 +1,9 @@ +\chapter{序論} +\pagenumbering{arabic} +序論を書く + + +\newpage + +\section{本論文の構成} +論文の構成を書く diff -r 99d965c02c45 -r da6a6eba893d judge.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/judge.tex Tue Jan 24 14:53:52 2017 +0900 @@ -0,0 +1,29 @@ +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%論文審査会委員署名用ページ%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\pagestyle{empty} +\vspace*{5cm} +本論文は、修士(工学)の学位論文として適切であると認める。 +\vspace*{2cm} +\begin{flushright} +%¥makebox[10cm][l]{ +\begin{minipage}[t]{7cm} +\begin{center} +{\bf 論 文 審 査 会} +\end{center} + +\vspace{1cm} +\underline{\hspace{6cm}印}\\ +（主\hspace{0.5em}査）\hspace{0.5em}Mohammad Reza Asharif 氏 + +\vspace{1cm} +\underline{\hspace{6cm}印}\\ +（副\hspace{1em}査）\hspace{1em}宮城 隼夫 氏 + +\vspace{1cm} +\underline{\hspace{6cm}印}\\ +（副\hspace{1em}査）\hspace{1em}長田 智和 氏 + +\end{minipage} +\end{flushright} +\newpage diff -r 99d965c02c45 -r da6a6eba893d master_paper.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/master_paper.tex Tue Jan 24 14:53:52 2017 +0900 @@ -0,0 +1,102 @@ +\documentclass[a4j,12pt]{jreport} +\usepackage{master_paper} +\usepackage{ascmac} +\usepackage[dvipdfmx]{graphicx} +\usepackage{here} +\usepackage{listings,jlisting} +\usepackage{comment} +%\input{dummy.tex} %% font + +\jtitle{タイトル} +\etitle{英語タイトル} +\year{平成28年度} +\affiliation{\center% + \includegraphics[clip,keepaspectratio,width=.15\textwidth] + {images/u-ryukyu-Mark.eps}\\ + \vskip10mm + 琉球大学大学院 \ 理工学研究科\\ 情報工学専攻} + +\author{金川 竜己} + +\marklefthead{% 左上に挿入 + \begin{minipage}[b]{.4\textwidth} + \includegraphics[height=1zw,clip,keepaspectratio]{images/emblem-bitmap.eps} + 琉球大学大学院学位論文(修士) +\end{minipage}} +\markleftfoot{% 左下に挿入 + \begin{minipage}{.8\textwidth} + 英語タイトル +\end{minipage}} + +\newcommand\figref[1]{図 \ref{fig:#1}} +\newcommand\tabref[1]{表 \ref{tab:#1}} + +\lstset{% + language={Java}, + basicstyle={\footnotesize},% + identifierstyle={\footnotesize},% + commentstyle={\footnotesize\itshape},% + keywordstyle={\footnotesize\bfseries},% + ndkeywordstyle={\footnotesize},% + stringstyle={\footnotesize\ttfamily}, + frame={tb}, + breaklines=true, + columns=[l]{fullflexible},% + numbers=left,% + xrightmargin=0zw,% + xleftmargin=1zw,% + numberstyle={\scriptsize},% + stepnumber=1, + numbersep=0.5zw,% + lineskip=-0.5ex% +} + + +%%% 索引のために以下の2行を追加 +\usepackage{makeidx,multicol} +\makeindex +\begin{document} + +\maketitle +\newpage + +%\input{judge.tex} + +%要旨 +\input{abstract.tex} +\input{abstract_eng.tex} + +%目次 +\tableofcontents + +%図目次 +\listoffigures + +%表目次 +\listoftables + +%chapters +\input{introduciton.tex} +\input{chapter1.tex} % Jungleの説明 +\input{chapter2.tex} % 差分Treeの説明 +\input{chapter3.tex} % 赤黒木の説明 +\input{chapter4.tex} % Jungle Tree Brower +\input{chapter5.tex} % Rendering Engine +\input{chapter6.tex} % +\input{conclusion.tex} + +%謝辞 +\input{thanx.tex} + +%参考文献 +\nocite{*} +\bibliographystyle{junsrt} +\bibliography{master_paper} + +%発表文献 +\input{appendix.tex} + +%付録 + +\printindex +\end{document} diff -r 99d965c02c45 -r da6a6eba893d rendering.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/rendering.tex Tue Jan 24 14:53:52 2017 +0900 @@ -0,0 +1,10 @@ +\chapter{Rendering Engine} \label{chapter:rendering} + +\section{Rendering で用いるモデルの作成} +\section{Rendering で使うデータ構造} +\section{CreatePolygonFromSceneGraph} +\section{CreateSpan} +\section{Rendering する上での Texture の管理} +\section{DrawSpan} + + diff -r 99d965c02c45 -r da6a6eba893d thanx.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/thanx.tex Tue Jan 24 14:53:52 2017 +0900 @@ -0,0 +1,3 @@ +\chapter*{謝辞} +\addcontentsline{toc}{chapter}{謝辞} +謝辞を書く diff -r 99d965c02c45 -r da6a6eba893d 修論.xmind Binary file 修論.xmind has changed