\chapter{Differential Jungle Tree}
Jungleは木の編集時、ルートから編集を行う位置までのノードの複製を行う。
そのため、木の編集の手間は、木構造の形によって異なる。
特に線形の木は、全てのノードの複製を行うため、変更の手間がO(n)になってしまう。
そこで、Jungle は、線形の木をO(1)で変更するPushPopの機能を持つ。
PushPopとは、ルートノードの上に新しいルートノードを付け加えるAPIである(図\ref{fig:pushpop})。
すると、木の複製を行う必要が無いため、木の変更の手間がO(1)でノードの追加を行える。


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

しかし、PushPopはルートノードを追加していくため、図\ref{fig:pushpop}のようにノードの並びが逆順になってしまう。
Logなどの正順の木でなければデータを表現できない場合、木の編集時 PushPop を使用できない。
その問題を解決するために、木の編集の手間をO(1)で、正順の木を構築できるDifferential Jungle Treeの実装を行った。
Differential Jungle Treeは、木のバージョンごとに、自身の木の最後尾を表す末尾のノードを保持する。

\newpage

\section{Differential Tree Context}
Jungleの木はTreeContextというオブジェクトに自身の木の情報を保持している。
Differential Jungle Treeでは、現在の版の木構造の末尾ノード保持することが可能な Differential Tree Context 作成した。


\section{Differential Jungle Treeの作成}
Differential Jungle Treeを作成するためにJungleに、新しいAPIを実装した(表\ref{createDifTreeAPI})。

\begin{table}[htb]
\begin{center}
\caption{Jungleに新しく実装したAPI}
\begin{tabular}{|p{15em}|p{24em}|}        \hline
{\small {\tt createNewDifferenceTree(String treeName)}} &{\small Jungleに新しくDifferential Jungle Tree を生成する。木の名前が重複した場合、生成に失敗しnullを返す。}     \\ \hline
\end{tabular}
\label{createDifTreeAPI}
\end{center}
\end{table}


ソースコード\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()); 
String treeName = "difTree"; 
JungleTree tree = jungle.createNewDifferenceTree(treeName); 
\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()); 
String treeName = "treeName"; 
JungleTree defaultTree = jungle.createNewTree(treeName) 
JungleTree dfTree = jungle.createNewDifferenceTree(treeName); 
\end{lstlisting}

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


\section{末尾ノードを使用した木の編集}
Differential Jungle Treeの木の編集は、Differential Jungle Tree Editorを使用して行う。
Differential Jungle Tree Editor は、Default Jungle Tree Editor と違い、生成時に新しい木構造(Sub Tree)を自身の中に構築する。
そして、木の編集は、自身が保持している木構造に対して行う。
編集後、Commiti を行う際に構築した木構造を、 Differential Jungle Tree の末尾ノードにAppendする。
その際木の複製は行わない。

また、Differential 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  Editor が保持している木構造に対して{\tt addNewChild(<-1,0>)}を実行し、ノードの追加を行う。
\item  Commitを行い、Treeの末尾ノードに Editor が保持している木構造をAppendする。
\end{enumerate}

Editor が保持している木構造に最後に追加したノードが、新しい木の末尾ノードとなる。
また、Differential Jungle Tree は、木の編集時複製を行わないため、
Indexのアップデートは、Editor が保持している木構造のデータをIndexに追加するだけで良い。



\section{Differential Jungle Treeの検索}
Differential Jungle Tree は、末尾ノードを使って、現在の木構造を表現している。
なので、過去の木に対して、Indexを使わずに全探索を行った場合、その版の木には無いはずのノードが取得できてしまう。
例として、編集前の木である {\tt Tree ver1} と編集後の木である {\tt Tree ver2}があるとする(図\ref{fig:multiTree})。
ここで、{\tt Tree ver1}に対して、検索をIndexを使わず行った場合、
本来{\tt Tree ver1}に存在しないノード3・4も検索対象に含まれてしまう。

そこで、その版の木が持つ末尾ノード以下のSub Treeを検索対象から除外する、Differential Interface Traverser を実装した。
Differential Interface Traverser を用いて Index を使用せず木の全探索を行った場合、{\tt Tree ver1}に存在しないノード3・4は検索対象から省かれる。

\begin{figure}[htpb]
\begin{center}
\includegraphics[scale=0.25]{figures/findDifTree.pdf}
\caption{複数の版の木の表現}
\label{fig:multiTree}
\end{center}
\end{figure}


Indexを使用した検索を行う場合、各版の木に対応したIndexがあるため、Default Treeと検索のアルゴリズムは変わらない。
これらの実装により Differential Jungle Tree は木構造の構築・検索を行う。


\section{Differential Jungle Treeの整合性}
Default Jungle Tree への Commit は、 編集後の木のデータを持つ TreeContext を作り、編集前の木が持つ TreeContext と Atomic に入れ替えることで行われる。
しかし、Differentail Jungle Tree の Commit は、Default Jungle Tree のCommit と異なり、
TreeContext の入れ替えと、Editor が保持している木構造の末尾ノードへの Append の２つのプロセスからなる。

TreeContext の入れ替えに関しては、 Default Jungle Tree と同じように行い、
末尾ノードへの Editor が持っている木構造の Append は、 TreeContext の入れ替えが成功した後に行う。
そうすることで、別 Thread で行われているCommitと競合した際に、
TreeContext を入れ替えた Thread と別 Thread が Append を行い、木の整合性が崩れることを回避している。


また、過去の版の木に対して、編集を加え Commit を行った場合、木の整合性が崩れてしまう問題もある。
図\ref{fig:multiTree}・\ref{fig:badDifTree2}を例に解説する。
図\ref{fig:multiTree}の過去の版の木 {\tt Tree ver1}に新しいノード5を追加・Commit を行うと、新しい木 {\tt Tree ver`2} が構築される。
ここで、{\tt Tree ver`2} に対して Index を使用しないで検索を行う。
Differential Jungle Tree に対する Index を使用しない検索は、末尾ノードより上にあるノードを検索対象にする。
しかしノード3・4という、本来存在しないはずのノードが検索対象に含まれてしまう。
これは、過去の版の木である、 {\tt tree ver1} の末尾ノードが２つ子ノード持っているせいで発生する。

この問題を解決するために、Differential Jungle Tree では、過去の木に対する変更を禁止している。
具体的には、末尾ノードは子を１つしか持つことができないようにした。
そうすることで木の整合性を保証している。


\begin{figure}[htpb]
\begin{center}
\includegraphics[scale=0.25]{figures/badDifTree2.pdf}
\caption{木の整合性が崩れる例}
\label{fig:badDifTree2}
\end{center}
\end{figure}