\section{非破壊的木構造データベースJungle}
\subsection{Jungleのデータ構造}
Jungleは複数の木の集合からなり、木は複数のノードの集合で出来ている。
ノードは自身の子のListと属性名と属性値の組を持ち、ノードの位置はNodePathで表される。
Jungleは非破壊的木構造であるためデータの編集は一度生成した木を上書きせず、ルートから編集を行うノードまでコピーを行い新しく木構造を構築することで行う。
そのため、読み込みと書き込みを同時に行うことができる。

\subsection{木の生成}
Jungleには木を生成、管理を行うAPI(*表\ref{jungleAPI})が実装されている。
\begin{table}[htb]
\begin{center}
\caption{Jungleに実装されているAPI}
\begin{tabular}{|l|l|}        \hline
createNewTree(       &Jungleに新しく木を生成する      \\
String treeName)     &木の名前が重複した場合          \\
　　　　　　　　　　 &生成に失敗する                  \\ \hline
getTreeByName(       &JungleからtreeNameと名前が      \\
String treeName)     &一致したtreeを取得する          \\
                     &名前が一致するTreeがない場合    \\
                     &取得は失敗する                  \\ \hline
\end{tabular}
\label{jungleAPI}
\end{center}
\end{table}


\subsection{NodePath}
JungleのNodeの位置はNodePathを使って表される。
NodePathはrootNodeからスタートし、ノードの子供の場所を次々表すことで対象のNodeの場所を表す。
\begin{figure}[h]
\begin{center}
\includegraphics[height = 4cm , bb=0 0 313 301]{images/nodePath.pdf}
\caption{NodePath}
\label{goodLayoutTree}
\end{center}
\end{figure}

\newpage
\subsection{木の編集}
Jungleの木の編集はJungleTreeEditorを用いて行われる。
JungleTreeEditorには表\ref{editor}で定義されているAPIが実装されている。

\begin{table}[htb]
\begin{center}
\caption{Editorに実装されているAPI}
\begin{tabular}{|l|l|}        \hline
addNewChildAt(      &pathで指定した場所にある        \\ 
NodePath path,      &Nodeの子供のpos番目にNodeを     \\ 
int pos)            &追加する                        \\ \hline
deleteChildAt(      &pathで指定した場所にある        \\ 
NodePath path,      &Nodeのpos番目の子ノードを       \\ 
int pos)            &削除する                        \\ \hline
putAttribute(       &pathで指定した場所にある        \\ 
NodePath path,      &Nodeに属性名 key                \\ 
String key,         &属性値 valueのペアで            \\ 
ByteBuffer value)   &値を挿入する                    \\ \hline 
deleteAttribute(    &pathで指定した場所にある        \\
NodePath path,      &Nodeが持つ属性名keyとペアで     \\ 
String key)         &保存されているデータを削除する  \\ \hline
moveChild(          &pathで指定された位置にある      \\
NodePath path       &NodeのchildNum番目の            \\
,int childNum,      &childをmoveの方向に移動させる   \\
String move)        &                                \\ \hline   
pushPop()           & rootNodeの上に                 \\
                    & Nodeを追加する                 \\ \hline
\end{tabular}
\label{editor}
\end{center}
\end{table}


これらのAPIは
\begin{lstlisting}[frame=lrbt,numbers=left,label=editorCode]
Either<Error, JungleTreeNode>
\end{lstlisting}
型を返す。
これはエラーの場合はErrorが格納されており、編集が成功した場合JungleTreeEditorを保持する。
編集後に返されるJungleTreeEditorは、編集された木構造を保持しているため、編集前の木構造を保持しているJungleTreeEditorとは別のオブジェクトである。
編集を行った後は、editor.success()で今までの編集をコミットすることができる。その際他のJungleTreeEditorによって木が更新されていた場合はコミットに失敗する。
その場合は最初からやり直す必要がある。


以下にJungleTreeEditorを使ったサンプルコードを記述する

\begin{lstlisting}[frame=lrbt,numbers=left,label=editorCode]
JungleTreeEditor editor = tree.getTreeEditor();
DefaultNodePath root = new DefaultNodePath();
Either<Error, JungleTreeEditor> either = editor.addNewChildAt(root, 0);
if (either.isA()) {
  throw new IllegalStateException();
}
editor = either.b();
editor.success();
\end{lstlisting}

\begin{enumerate}
\item tree.getEditor()でtreeからJungleTreeEditorを取得する 
\item 次に変更するノードの場所を指すNodePathを作成する
\item editor.addNewChildAtでpathで指定したノードの子供の0番目に子ノードを追加する
\item 返り値のEitherがErrorを保持していないか(編集に失敗していないか)を確認する 
\item Errorを保持していた場合Exceptionを投げる
\item Editorを持っていた場合木の変更をコミットする
\end{enumerate}

これらのAPIによりJungleは木構造を格納する機能を持っている。

\subsection{その他のJungle}
他には当研究室で開発を行っている並列分散フレームワークAliceを用いて実装された分散木構造データベースJungle、Haskell版Jungleなどもある。