\chapter{Differential Jungle Tree}
Jungleの木の変更の手間は木の形によって異なる。
特に線形の木は、変更の手間がO(n)となってしまう。
線形の木をO(1)で変更するために、Jungleは、ルートノードを追加していくPushPopの機能を持つ。
しかし、PushPopはルートノードを追加していくため、図\ref{fig:pushpop}のようにノードの並びが逆順になってしまうため、正順の木を構築する際は、PushPopを使用できない。

\begin{figure}[htpb]
\begin{center}
\includegraphics[scale=0.3]{figures/PushPopDemerit.pdf}
\caption{PushPopの問題点}
\label{fig:pushpop}
\end{center}
\end{figure}

その問題を解決するために、木の編集の手間をO(1)で、正順の木を構築できるDifferential Jungle Treeの実装を行った。
Differential Jungle Treeは、木のバージョンごとに、自身の末尾のノードを持つ。

\newpage
\section{Differential Tree Context}

Jungleの木はTreeContextというオブジェクトに自身の木の情報を保持する。 
表\ref{TreeContext}にTreeContextが保持するデータを記述する。
\begin{table}[htb]
\begin{center}
\caption{TreeContextが保持している値}
\begin{tabular}{|l|}        \hline
{\tt } 自身のルートノード\\ \hline
{\tt } 1つ前のversionのTreeContext\\ \hline
{\tt } 編集のログ\\ \hline
{\tt } 木のuuid    \\ \hline
{\tt } 木の名前    \\ \hline
{\tt } 木のversion    \\ \hline
{\tt } 木の検索に使うTraverser    \\ \hline
\end{tabular}           
\label{TreeContext}
\end{center}                  
\end{table}  

Differential Jungle Treeでは、現在のバージョンの木構造の末尾ノード保持することが可能な DifferentialTreeContext 作成した。


\section{末尾ノードを使用した木の編集}
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の編集の流れを記述する。

\begin{figure}[htpb]
\begin{center}
\includegraphics[scale=0.28]{figures/EditDifferencialTree.pdf}
\caption{末尾ノードを使用した木の編集}
\label{fig:EditDifTree}
\end{center}
\end{figure}

\newpage
\begin{enumerate}
\item  木から{\tt getTreeEditor}でEditorを取得する。(このとき取得するEditorはSub Treeを持つ)
\item  SubTreeに対して{\tt addNewChild(<-1,0>)}を実行し、ノードの追加を行う。
\item  Commitを行い、Treeの末尾ノードにSub TreeをAppendする。
\end{enumerate}

また、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<Error, TreeNode> 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 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]
1.[APPEND_CHILD:<-1>:pos:0]
2[COMMIT]
3.[APPEND_CHILD:<-1>:pos:0]
4.[APPEND_CHILD:<-1,0>:pos:0]
\end{lstlisting}

大文字の英字はLogとして書き出された Operation の種類を表す。
\verb|<>| により囲まれている数字は NodePath を示す。
NodePath の表記以降は、ノードの position などの情報を表している。
[COMMIT]は、実際の木を構築した際にCommitが行われたタイミングを表す。

[COMMIT]のタイミングでCommitを行わず、全ての変更を加えた後にCommitを行った場合、Editor 内部の Sub Treeに、図\ref{fig:badDifTreeCreate}のような変更が加えられ、Append後、図\ref{fig:badDifTree}のような木が構築される。


\begin{figure}[htpb]
\begin{center}
\includegraphics[scale=0.45]{figures/badDifTreeCreate.pdf}
\caption{適切なタイミングでCommitを行わない木の復元の流れ}
\label{fig:badDifTreeCreate}
\end{center}
\end{figure}

\begin{figure}[htpb]
\begin{center}
\includegraphics[scale=0.45]{figures/BadDifTree.pdf}
\caption{適切なタイミングでCommitを行わなかった木}
\label{fig:badDifTree}
\end{center}
\end{figure}

\clearpage

しかし、実際には、図\ref{fig:createGoodDifTree1}、図\ref{fig:createGoodDifTree2}のような変更が加えられる。
以下に、適切に Commit を行った場合の木の編集の流れを記述する。

\begin{figure}[htpb]
\begin{center}
\includegraphics[scale=0.45]{figures/goodDifTreeCreate1.pdf}
\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前、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.45]{figures/goodDifTree.pdf}
\caption{適切なタイミングでCommitを行なった木の変更。}
\label{fig:goodDifTree}
\end{center}
\end{figure}

このように、Logとして書き出されたTreeOperationから、適切な構造のDifferential Treeを復元するためには、木の構築時と同じタイミングでCommitを行う必要がある。
そのため、Commitのタイミングを、Logとして書き出し、適切なタイミングでCommitを行えるようにした。




\section{Differential Jungle Treeの検索}
Differential Treeは、木を破壊的に編集する。
そのため、過去の木から特定の値を持ったノードを取得する際、全てのノードを走破した場合その版の木には無いはずのノードが取得できてしまうことがある。
そこで、その版の木が持つ末尾ノード以下のSub Treeを検索対象から除外する検索を実装した。

Indexを使用した検索を行う場合、各版に対応したIndexがあるため、Default Treeと検索の方法は変わらない。