\chapter{Differential Jungle Tree}
Jungleの木の変更の手間は形によって異なる。
特に線形の木は、変更の手間がO(n)となってしまう。
線形の木をO(1)で変更するために、Jungleは、ルートノードを追加していくPushPopの機能を持つ。
しかし、PushPopはルートノードを追加していくため、図\ref{fig:pushpop}のようにノードの並びが逆順になってしまう。
Logなどの正順の木でなければデータを表現できない場合、木の編集時 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は、木のバージョンごとに、自身の木の最後尾を表す末尾のノードを保持する。


\section{Differential Tree Context}
Jungleの木はTreeContextというオブジェクトに自身の木の情報を保持している(表\ref{TreeContext})。

\newpage 

\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では、現在の版の木構造の末尾ノード保持することが可能な Differential Tree Context 作成した。



\section{Differential Jungle Treeの作成}
Differential Jungle Treeを作成するためにJungleに、{\tt createNewDifferentialTree(String treeName) }を実装した。
これは、第一引数String {\tt treeName}で受け取った名前の Differential Tree を作成する。
その際、名前が重複した場合木の生成に失敗する。


ソースコード\ref{newDifferentialTree}に新しいDifferential Jungle Treeを作成するサンプルコードを記載する。
\begin{lstlisting}[frame=lrbt,numbers=left,label=newDifferentialTree,caption=Differential Jungle Treeの生成]
Jungle jungle = new DefaultJungle(null, "hogehoge", new DefaultTraverser()); // jungleの作成
String treeName = "difTree"; //treeNameの設定
JungleTree tree = jungle.createNewDifferenceTree(treeName]); //Differential Treeの作成
\end{lstlisting}

Jungle では、{\tt TreeMap<String,Jungle Tree>} を用いて Jungle Tree を管理している。
Differential Jungle Tree と Default Jungle Tree は、同じ TreeMap に保持されるため、別々の木に同じ名前をつけることはできない(ソースコード\ref{src:nameFail})。
\begin{lstlisting}[frame=lrbt,numbers=left,label=src:nameFail,caption=名前の重複]
Jungle jungle = new DefaultJungle(null, "hogehoge", new DefaultTraverser()); // jungleの作成
String treeName = "treeName"; //treeNameの設定
JungleTree defaultTree = jungle.createNewTree(treeName) //Default Treeの作成
JungleTree dfTree = jungle.createNewDifferenceTree(treeName); //Differential Treeの作成
\end{lstlisting}

ソースコード\ref{src:nameFail}では、4行目で Differentail Jungle Tree の名前が、3行目で生成した Default Jungle Tree の名前と重複するため、木の生成に失敗する。

\newpage

\section{末尾ノードを使用した木の編集}
Differential Jungle Treeの木の編集は、Differential Jungle Tree Editorを使用して行う。
%Differential Jungle Tree Editorは、Jungle Tree Editor インターフェースを実装しているため、使い方はDefault Jungle Tree Editorと同じである。

Default Jungle Tree との、木の編集時の処理の違いは、Default Jungle Tree の Editorは、木の複製を行い、過去の木を保持するのに対して、Differential Jungle TreeのEditor は、自身が保持している Sub Tree に対して破壊的に編集を行う。
そして、Commitを行う際に、構築したSub Treeを末尾ノードにAppendする。
そうすることで、木の複製を行う必要がないため、木の変更の手間はO(1)で行える。

また、Differential TreeはSub Treeに対する変更しか行えないため、一度Commitした木に対して変更は行えない。
図\ref{fig:EditDifTree}にDifferential Jungle Treeの編集の流れを記述する。

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

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

Sub Tree に最後に追加したノードが、新しい木の末尾ノードとなる。
また、Differential TreeのIndexのアップデートは、Commit 時に Sub Treeの中身をIndexに追加するだけで良い。


\section{Differential Jungle Treeの整合性}

Differential Jungle Treeに対する変更が競合した場合、先にCommitを行った方の変更が適応される。
末尾ノードへのAppendは、破壊的な変更であるため、Commit成功後に行う。
そうすることで、編集が競合した際の整合性を保っている。


また、Differential Jungle Treeは、木を破壊的に変更するため、過去の木を取得し変更を加えた場合、末尾ノードに複数のSub TreeがAppendされてしまい、木の整合性が崩れてしまう。
その問題を解決するため、末尾ノードは1つしか子ノードを持つことができない。
ノードのAppend時、末尾ノードが子ノードを持っていた場合、過去に木に対する変更と判断し、木の Commit は失敗する。

\begin{comment}
ソースコード\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 Differential Treeから末尾ノードを取得する。
\item 末尾ノードからChildrenを取得する。
\item 末尾ノードにSub TreeがすでにAppendされているか(子供を持っているか)を調べる。
\item 他のSub TreeがAppendされている(今編集を行っているのが過去の木)場合、木のAppendは失敗するため、エラーを返す。
\item そうでない場合、Sub Treeを末尾ノードにAppendする。
\end{enumerate}

このように、末尾ノードが複数の子を持つことを禁止することで、過去の木を取得した際の木の整合性を保証している。
\end{comment}


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

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

これらの実装により Differential Jungle Tree は木構造の構築・検索を行う。