\chapter{分散コンテンツマネージメントシステムの実装}

本章では, 分散コンテンツマネージメントシステムのサーバーサイド部分の実装について述べる. 前章では, 我々のシステムのおおまかな設計について説明した.
そこでは, サーバーサイドで木構造を管理するデータベースがあると述べた. ここでは, その木構造データベースについて詳細な設計について説明する.
最初に, 実装した木構造データベースの利用方法について述べ, 次に詳細な設計と実装について述べる.

\section{木構造データベースJungle}
木構造データベースJungleは, Javaで実装された分散コンテンツマネージメントシステムのための木構造データベースである.
非破壊的木構造の方法に則ったAPIと, 木構造のトラバースするための方法を提供する. 分散コンテンツマネージメントシステムに組み込んで利用する予定で実装されているため, 他のシステムに組み込んで利用することも可能である.

\subsubsection{木の作成}
はじめに, データベースオブジェクトと木の作成方法について述べる. 
Jungleは複数の木を保持することが出来る. 木には名前がついており, 名前を利用して作成・編集・削除を行うことが出来る.

\begin{lstlisting}[frame=lrbt,label=src:create_jungle,caption=データベースオブジェクトと木の作成,numbers=left]
import jp.ac.u_ryukyu.cr.ie.shoshi.jungle.*;
import jp.ac.u_ryukyu.cr.ie.shoshi.jungle.traverser.*;
import jp.ac.u_ryukyu.cr.ie.shohsi.jungle.editor.*;

DefaultTraverser traverser = new DefaultTraverser();
DefaultTreeEditor editor = new DefaultTreeEditor(traverser);
DefaultJungle jungle = new DefaultJungle(null,"sample",editor);

JungleTree tree = jungle.createTree("name of new tree here");
\end{lstlisting}

DeafultJungleが, 木構造データベースのオブジェクトとなる. 
jungle.createTreeメソッドを利用して木構造を作成する. もし, すでに木構造が存在している場合は, nullが返される.

\subsubsection{木と木を構成するノード}
データベースオブジェクトを作成し, 木構造とルートノードを取得するためには以下のように記述する.

\begin{lstlisting}[frame=lrbt,label=src:get_jungle,caption=木とノードの取得,numbers=left]
/* データベースの取得まで省略 */
JungleTree tree = jungle.getTreeByName("your tree name here");

Node root = tree.getRootNode();

Children<Node> children = root.getChildren(); // 子供ノードのリスト
Attributes attributes = root.getAttributes(); // ノードが保持する辞書

ByteBuffer value = attributes.get("key name");
Node child = children.at(2);
\end{lstlisting}

jungle.getTreeByNameメソッドで名前を指定して木構造を取得し, tree.getRootNodeメソッドでルートノードを取得することが出来る.
ノードは, 子供ノードのリストと辞書を保持しており, それぞれ, root.getChildren()とroot.getAttributes()で取得することが出来る.

\subsubsection{木の編集}
木の編集は, 通常Nodeを書き換えるためNodeのAPIとして提供されることが多いが, JungleではJungleTreeEditorを利用して行う.
JungleTreeEditorには編集するためのいくつかのメソッドが用意されており, NodePathと呼ばれるルートノードからノードまでのパスを指定することでノードが編集される.
NodePathは, ルートノードからスタートし, ノードの子供の場所を次々に指定していくことで編集対象のノードの場所を表す.(図\ref{fig:nodepath})

\begin{figure}[!htbp]
\begin{center}
\includegraphics[width=80mm]{./images/nodepath.pdf}
\end{center}
\caption{NodePath}
\label{fig:nodepath}
\end{figure}

\begin{lstlisting}[frame=lrbt,label=src:treeeditor,caption=木の編集を行うTreeEditor,numbers=left]
/* データベースの取得まで省略 */
JungleTree tree = jungle.getTreeByName("your tree name here");

JungleTreeEditor editor = tree.getEditor();

//パスの生成
DefaultNodePath path = new DefaultNodePath();
path = path.add(1).add(2).add(3);

// トランザクションの始まり
Either<Error,JungleTreeEditor> e = editor.addNewChildAt(path,0);
if(e.isA()){
 // エラーが起きた場合のコード
}
editor = e.b();
e = editor.putAttribute(path,"key",ByteBuffer.wrap("value".getBytes());
if(e.isA()){
 // エラーが起きた場合のコード
}
editor = e.b();
editor.success();
// トランザクションの終わり
\end{lstlisting}

JungleTreeEditorはtree.getEditor()で取得することが出来る.
JungleTreeEditorはJungleTreeを非破壊的に編集し, Either$<$Error,JungleTreeEditor$>$型を返す. これは, エラーの場合はErrorが格納されており, 正常に編集が成功した場合はJungleTreeEditorを保持する型である.
木構造の編集により返されるJungleTreeEditorは, 編集された木構造を保持しており編集前の木構造を保持するJungleTreeEditorは別のオブジェクトである.
非破壊的に編集を繰り返した後, editor.successにより今までの編集をコミットすることが出来る, このとき他のJungleTreeEditorなどでJungleTreeがすでに更新されていた場合はコミットは失敗する. そのため, 最初からやり直す必要がある.

\subsubsection{木の編集にNodeEditorを利用する}
木の編集にはNodeEditorを利用することも出来る, NodeEditorにはNodeの編集手順を記述しJungleTreeEditorに渡す. ソース\ref{src:treeeditor}と同等な処理を行うNodeEditorを以下に示す.

\begin{lstlisting}[frame=lrbt,label=src:nodeeditor,caption=同等の処理を行うNodeEditor,numbers=left]
/* データベースの取得まで省略 */
JungleTree tree = jungle.getTreeByName("your tree name here");

JungleTreeEditor treeEditor = tree.getEditor();

NodeEditor nodeEditor = new NodeEditor(){
 public <T extends EditableNode<T>> edit(T node){
  Either<Error,T> e = node.addNewChildAt(0);
  if(e.isA()){
   // エラーが起きた場合のコード
  }
  node = e.b();
	e = node.putAttribute("key",ByteBuffer.wrap("value".getBytes()));
  if(e.isA()){
   // エラーが起きた場合のコード
  }
  return e.b();
 }
};

DefaultNodePath path = new DefaultNodePath();
path = path.add(1).add(2).add(3);

// トランザクションの始まり
Either<Error,JungleTreeEditor> e = editor.edit(path,nodeEditor);
if(e.isA()){
 // エラーが起きた場合のコード
}
editor.success();
// トランザクションの終わり
\end{lstlisting}

\subsubsection{木のトラバース}
木をトラバースするためには, Traverserを利用する. Traverserは木を対象にせずNodeを対象に取るため, 木の任意の部分から走査を始めることが可能である.
Traverserは目的のノードまでに通ったノードをすべて列挙するため, JungleTreeEditorはNodePathとTraverserを用いて編集対象のノードまでの全てのノードを取得している.
以下のコードはNodePathを用いて目的のノードまでをトラバースするコードである.

\begin{lstlisting}[frame=lrbt,label=src:tree_traverse,caption=NodePathを用いた木のトラバース,numbers=left]
/* データベースの取得まで省略 */
JungleTree tree = jungle.getTreeByName("your tree name here");

DefaultNodePath path = new DefaultNodePath();
path = path.add(1).add(2).add(3);
DefaultEvaluator evaluator = new DefaultEvaluator(path);

Node root = tree.getRootNode();
TraversableNodeWrapper<Node> wrapper = new TraversableNodeWrapper<Node>(root);

// Traverserの作成
DefaultTraverser traverser = new DefaultTraverser();
Traversal result = traverser.traverse(wrapper,evaluator);

for(Direction d : result){ // パスの分だけDirectionが生成される
 int pos = d.getPosition(); 
 Node node = d.getTraget();
 // etc etc..
}
\end{lstlisting}

Evaluator,Directionなどのクラスの説明については後述する.
これまでに, Jungleの基本的な利用方法について述べた. 以降はJungleの更に細かい部分の実装について説明する.

\section{木構造データベースJungleの実装}
\subsection{開発環境}
\subsubsection{言語}
本システムではサーバーサイドの実装にJavaを用いる. Javaは豊富なライブラリと開発環境が整っているため使いやすい言語である.\\
また, 外部ライブラリとしてFunctionalJavaを用いる. このライブラリはJavaで関数型スタイルのプログラミングを行うために開発された. 本システムでは, 非破壊的木構造をメインのデータ構造とする, そのため, 多くの非破壊的データ構造を利用できるFunctionalJavaは有効に利用できる.

\subsection{全体の構造}
全体木構造データベースは木構造を表現するNodeと, Nodeを非破壊的に編集するNodeEditor, Nodeの集合である木構造を非破壊的に編集するTreeEditorから構成される. 以下に, 述べたコンポーネントとその他の構成要素の表を示す.

\begin{table}[!htbp]
\caption{コンポーネント一覧}
\label{tab:components}
\begin{center}
\begin{tabular}{|c||c|} \hline
名前 & 概要 \\ \hline
Node & 基本的なデータ構造, 読み込み専用の親子関係を表現する \\ \hline
NodeEditor & ノードを編集する \\ \hline
TreeEditor & 複数のノードから構成される木構造を編集する \\ \hline
Traverser & 木構造を走査し目的のNodeを取得する \\ \hline
JungleTreeEditor & TreeEditorに加え, トランザクションを管理する \\ \hline
JungleTree & JungleTreeEditorなど, 木の情報を管理する \\ \hline
Jungle & 木の作成・取得・削除を担当する. \\ \hline
\end{tabular}
\end{center}
\end{table}

\subsection{型パラメータつきインターフェイスParentの導入}
我々は, Javaで木構造を表すためにParent,Childrenというインターフェイスを作成する. これは非常に複雑であるが, 親子関係を表すのに有用な仕組みだと思われる. 定義を以下に示す.

\begin{lstlisting}[frame=lrbt,label=src:parent,caption=Parentの定義,numbers=left]
public interface Parent<T> {
 public Children<T> getChildren();
}
\end{lstlisting}

\begin{lstlisting}[frame=lrbt,label=src:child,caption=Childrenの定義,numbers=left]
public interface Children<T> extends Iterable<T>{
 public int size();
}
\end{lstlisting}

これらのインターフェイスを利用するためには, まず, ソース\ref{src:node}のようにして継承したインターフェイスを作成する.
ここで型パラメータTはNodeを継承した型として宣言する.

\begin{lstlisting}[frame=lrbt,label=src:node,caption=Nodeの定義,numbers=left]
public interface Node<T extends Node<T>> implements Parent<T> {
 public Children<T> getChildren();
}
\end{lstlisting}

NodeはParentの定義よりT型の子供を保持するインターフェイスとして宣言できる. そしてT型はNode型を継承する型なので, 再帰的な構造を表現することが出来る.
このインターフェイスを実装すると以下のようになる.

\begin{lstlisting}[frame=lrbt,label=src:nodeimpl,caption=NodeImplの定義,numbers=left]
public class NodeImpl implements Node<NodeImpl> {
 public Children<NodeImpl> getChildren();
}
\end{lstlisting}

このNodeの実装では, Childrenの型パラメータがNodeImplになる. こうすることで, 実装を知らないクラスに引数として渡しても型パラメータが失われることがないコードを記述できるようになる.\\
例えば, 我々のシステムでは, 主に非破壊的なデータ構造を扱う. すなわち, 非破壊的オブジェクトを編集して返すメソッドがあるクラスに存在する場合, その返されたオブジェクトは元々のオブジェクトと異なるため, 型の情報が失われてしまうためキャストが必要になる.\\
しかし, この方法では, キャストは必要なく常に型パラメータは保持される.

\begin{lstlisting}[frame=lrbt,label=src:parent_example,caption=Parentが有用な例,numbers=left]
class EditorA {
 public Node edit(Node obj) { .... }
}
class EditorB {
 public <T extends Node<T>> edit(T obj) { .... }
}
class Obj implements Node<Obj> {
 public static void main(String args[]){
  Obj o = new Obj();
  EditorA a = new EditorA();
  EditorB b = new EditorB();
  Node n = a.edit(o); // 型が失われてNodeになるキャストが必要
  Obj newObj = b.edit(o); // 型は失われない.
 }
}
\end{lstlisting}

我々の実装で, 親子関係を扱うコンポーネントはすべてこのインターフェイスを継承する. 次に, 他の構成するコンポーネントについて述べる.

\newpage

\section{Node}
Nodeは, 木構造を表現するためのコンポーネントである. 木構造は子供と辞書を保持する. (図\ref{fig:node_components})
我々はNodeのAPIをソース\ref{src:definition_of_node}のように定義した.
基本的に, Nodeは読み込み専用であり, 編集操作を持たない.
\begin{figure}[!htbp]
\begin{center}
\includegraphics[width=110mm]{./images/node_component.pdf}
\end{center}
\caption{Nodeの構成要素}
\label{fig:node_components}
\end{figure}

\begin{lstlisting}[frame=lrbt,label=src:definition_of_node,caption=Nodeの定義,numbers=left]
public class Node implements Children<Node>
 ,AttributesContainer {
 public Attribute getAttribute();
 public Children<NodeImpl> getChildren();
}
\end{lstlisting}

getAttributesは辞書オブジェクトを取得するメソッドで, getChildrenは子ノードのリストを取得するメソッドである.
Childrenの定義は前述したとおりで, Attributesの定義を以下に示す.

\begin{lstlisting}[frame=lrbt,label=src:definition_of_children,caption=Nodeの定義,numbers=left]
public interface Attributes {
 public ByteBuffer get(String key);
}
\end{lstlisting}

ここで, ByteBufferはjava.nio.ByteBufferである. ここでは, 辞書に格納するものが文字列に限らないことを考慮しByteBuffer型を採用した.

\newpage

\section{NodeEditor}
前章で述べたとおり, 非破壊的木構造は編集対象までのNodeをRootからすべてコピーした後, 編集対象のNodeを書き換える.
よって, Nodeを書き換える仕組みが必要である. NodeEditorはNodeを(木構造ではない)を編集するためのコンポーネントである.
NodeEditorを構成する要素を表\ref{tab:nodeeditor_components}に示す.

\begin{figure}[!htbp]
\begin{center}
\includegraphics[width=150mm]{./images/nodeeditor_component.pdf}
\end{center}
\caption{NodeEditorのイメージ}
\label{fig:nodeeditor_component}
\end{figure}

\begin{table}[!htbp]
\caption{NodeEditorを構成する要素}
\label{tab:nodeeditor_components}
\begin{center}
\begin{tabular}{|c||p{25zw}|} \hline
クラス名 & 概要 \\ \hline \hline
EditableNode & 非破壊的に編集できるNode \\ \hline
EditableAttribute & 非破壊的に編集できる辞書, 編集の際に新しいEditableNodeを返す. \\ \hline
EditableChildren & 非破壊的に編集できる子Nodeリスト, 編集の際に新しいEditableNodeを返す. \\ \hline
NodeEditor & Nodeの編集処理を記述するためのシングルメソッドクラス. \\ \hline
\end{tabular}
\end{center}
\end{table}

\subsubsection{EditableNode}
EditableNodeは, Parentを継承した非破壊的に編集できることを示すNodeである. EditableAttributesとEditableChildrenをここから取得することが出来る.

\subsubsection{EditableAttributes}
EditableAttributeは, Attributesを拡張し編集操作を加えたインターフェイスである. 辞書への追加, 削除が定義されている.
また, 辞書への追加, 削除の操作が行われると新しくEditableNodeが作成される. この作成されたEditableNodeは辞書を元々保持していたEditableNodeのコピーを編集したものでる.

\begin{lstlisting}[frame=lrbt,label=src:definition_of_editableattributes,caption=EditableAttributesの定義,numbers=left]
public interface EditableAttributes<T extends EditableNode<T>>
 implements Attributes {
 public void put(String key,ByteBuffer value);
 public void delete(String key);
}
\end{lstlisting}

\subsubsection{EditableChildren}
EditableChildrenは, Childrenを拡張し編集操作を加えたインターフェイスである. 子リストへのNodeの新規追加, 削除を行うことが出来る.
EditableAttributes同様に, リストを編集すると新しくコピーされたオブジェクトを作成し, それを編集して返却する.

\begin{lstlisting}[frame=lrbt,label=src:definition_of_editablechildren,caption=EditableChildrenの定義,numbers=left]
public interface EditableChildren<T extends EditableNode<T>>
 implements Children<T> {
 public Either<Error,T> addNewChildAt(int pos);
 public Either<Error,T> deleteChildAt(int pos);
}
\end{lstlisting}

\subsubsection{NodeEditor}
NodeEditorは, Nodeの編集を手順を記述するためのインターフェイスである. メソッドeditを持ち引数としてEditableNodeを取る, edit内部に編集手順を記述し, 戻り値として編集されたEditableNodeを返す.\\
このインターフェイスは, ユーザー側がNodeを編集するための手順をクラス化し, 木構造を編集するコンポーネント(後述)に渡すことで, 柔軟な編集を実現することが出来る.

\begin{lstlisting}[frame=lrbt,label=src:definition_of_nodeeditor,caption=NodeEditorの定義,numbers=left]
public interface NodeEditor {
 public <T extends EditableNode<T>> Either<Error,T> edit(T node);
}
\end{lstlisting}

例えば, あるNodeの辞書に名前と生年月日, 研究室を追加するNodeEditorは以下のように記述する.

\begin{lstlisting}[frame=lrbt,label=src:nodeditor_sample,caption=NodeEditorのサンプル実装,numbers=left]
public class AddProfile implements NodeEditor {
 public <T extends EditableNode<T>> Either<Error,T> edit(T node){
  node = node.getAttributes().put(key_name,name).b();
  node = node.getAttributes().put(key_birth,birth).b();
  node = node.getAttributes().put(key_lab,laboname).b();
  return node;
 }
}
\end{lstlisting}

\newpage

\subsection{TreeEditor}
TreeEditorは木構造を非破壊的に編集するためのコンポーネントでありNodeEditorを利用して実装される.
非破壊的木構造の編集方法通り, TreeEditorは編集対象のNodeまでをコピーする. コピーした編集対象のNodeをNodeEditorを使って編集する.
NodeEditorはNodeを編集するためのコンポーネントだが, TreeEditorは木を構成するためのコンポーネントであるため木を構成するためのNodeを持つ.
TreeEditorを構成する要素を表\ref{tab:treeeditor_components}に示す.

\begin{table}[!htbp]
\caption{TreeEditorの構成要素}
\label{tab:treeeditor_components}
\begin{center}
\begin{tabular}{|c||c|}  \hline
クラス名 & 概要 \\ \hline \hline
TreeNode & 木を構成するノード \\ \hline
TreeNodeChildren & 子供ノードのリスト \\ \hline
TreeNodeAttributes & ノードが保持する辞書 \\ \hline
TreeEditor & 木を編集するためのメソッドを持つエディタ \\ \hline
\end{tabular}
\end{center}
\end{table}

\subsubsection{TreeNode}
TreeNodeは, EditableNodeとほぼ同じであるが木を構成するために適したメソッドを保持するTreeNodeAttributeとTreeNodeChildrenを保持する.

\subsubsection{TreeAttribute}
TreeNodeAttributeは, Attributesを拡張し編集操作を加えたインターフェイスである. EditableAttribute同様, 辞書への追加, 削除が定義されている.
また, 辞書への追加, 削除の操作が行われると新しくTreeNodeが作成される. 

\subsubsection{TreeNodeChildren}
TreeNodeChildrenは, Childrenを拡張し編集操作を加えたインターフェイスである. 子リストへのNodeの新規追加, 削除を行うことが出来る.
EditableChildrenは, 子供Nodeとして既存のNodeを追加することが出来ないが, TreeNodeChildrenはそれが可能であるため, 効率よく木を構成することができる.
また, EditableChildren同様にリストを編集すると新しくコピーされたオブジェクトを作成し, それを編集して返却する.

\newpage

\begin{lstlisting}[frame=lrbt,label=src:definition_of_treenodechildren,caption=TreeNodeChildrenの定義,numbers=left]
public interface TreeNodeChildren<T extends TreeNode<T>>
 implements Children<T> {
 public Either<Error,T> addNewChildAt(int pos);
 public Either<Error,T> deleteChildAt(int pos);
 public Either<Error,T> addNewChildAt(int pos,T newChild);
}
\end{lstlisting}

\subsubsection{TreeEditor}
TreeEditorは, TreeNodeで構成される木を編集するための操作が定義されているインターフェイスである.
NodePathと呼ばれるルートNodeから編集対象のNodeまでのパスとNodeEditorを引数として受け取り, 非破壊的に編集する. 
TreeEditorの定義を以下に示す.

\begin{lstlisting}[frame=lrbt,label=src:definition_of_treeeditor,caption=TreeEditorの定義,numbers=left]
public interface TreeEditor {
 public <T extends TreeNode<T>> Either<Error,T> edit(T root,NodePath,NodeEditor editor);
}
\end{lstlisting}

TreeEditorは, 木を対象にするわけではなくNodeを引数に取るため, 木を構成する任意のTreeNodeから編集することも可能である.

\newpage

\subsection{Traverser}
Traverserは木構造を走査するためのコンポーネントであり, TreeEditorでも利用されている.
TraverserはNodeと走査するためのEvaluatorと呼ばれるものを引数に取り走査を行う. Evaluatorとは, TraverserがあるNodeを走査中にそのNodeの先に進むかどうか判断するために利用される.
Evaluatorは, Nodeとその他の情報(Nodeの場所)を受け取り, そのNodeの先に進むか進まないか判断する.
そして, 戻り値として次のNodeを評価するための新しいEvaluatorと評価結果をTraverserに返却する. 表\ref{tab:traverser_components}にTraverserを構成する要素を示す.

\begin{table}[!htbp]
\caption{Traverserを構成する要素}
\label{tab:traverser_components}
\begin{center}
\begin{tabular}{|c||p{27zw}|} \hline
名前 & 概要 \\ \hline \hline
Traverser & 木構造, Nodeを走査する. \\ \hline
TraversableNode & Traverserで走査することの出来るNode \\ \hline
TraversableChildren & TraversableNode同様, Traverserで走査することの出来るChildren \\ \hline
Evaluator & TraversableNodeを評価する \\ \hline
Traversal & Traverseの結果, ルートNodeから目的Nodeまでの全てのNodeのリスト \\ \hline
Direction & Traverseの結果に含まれる, 次のNodeの位置情報が含まれている \\ \hline
\end{tabular}
\end{center}
\end{table}

\subsubsection{TraversableNode}
TraversableNodeは, Traverserが走査することの出来ることを示すNodeである.

\subsubsection{TraversableChildren}
TraversableChildrenは, Traverserが走査することの出来ることを示すNodeの子供Nodeのリストである.

\subsubsection{Evaluator}
Evaluatorは, Traverserが走査しているNodeを評価する.
戻り値としてEvaluationと呼ばれる, 次のEvaluatorとNodeの評価を保持するオブジェクトを返す. 
Evaluatorにより, 評価されたNodeはTraverserがNodeを走査するべきかしないべきか判断するために利用される.
Evaluatorの定義とEvaluationの定義をソース\ref{src:evaluator_definition}とソース\ref{src:evaluation_definition}に示す.

\begin{lstlisting}[frame=lrbt,label=src:evaluator_definition,caption=Evaluatorの定義,numbers=left]
public interface Evaluator
{
	public <T extends TraversableNode<T>> Evaluation evaluate(T _current,int _pos);
}
\end{lstlisting}

\begin{lstlisting}[frame=lrbt,label=src:evaluation_definition,caption=Evaluatorの定義,numbers=left]
public interface Evaluation
{
	public Result result();
	public Evaluator evaluator();
}
\end{lstlisting}

Evaluationのresultメソッドは, このNodeの評価結果を表すEnum型のクラスResultを返す. 表\ref{tab:evaluation_result}に評価の種類を示す.

\begin{table}[!htbp]
 \caption{Evalautionの結果一覧}
 \label{tab:evaluation_result}
 \begin{center}
  \begin{tabular}{|c||c|} \hline
   名前 & 概要 \\ \hline \hline
   ACCEPT & このNodeを受け入れて先に進む \\ \hline
   CONTINUE & このNodeを受け入れずに, 次の候補を評価する \\ \hline
   BREAK & このNodeを受け入れず, でこれ以上の走査をやめる \\ \hline
   GOAL & このNodeを受け入れて, 走査をやめる \\ \hline
  \end{tabular}
 \end{center}
\end{table}

\subsubsection{Traversal}
Traversalは, Traverserによる走査の結果である. ルートノードから目的ノードまでのノードのリストを保持する.
図\ref{fig:traversal_image}にTraversalのイメージを示す.
この図はTraverserで, NodePath"-1,1,2,3"を走査した時のTraversalが保持する結果を表している.

\begin{figure}[!htbp]
\begin{center}
\includegraphics[width=100mm]{./images/traversal_image.pdf}
\end{center}
\caption{Traversalのイメージ}
\label{fig:traversal_image}
\end{figure}

\subsubsection{Direction}
Directionは, あるノードがその親ノードの何番目の子供ノードに値するかを示す. Traversalにて, ルートノードから目的ノードまでのリストを表す時, あるノードから次のノードへの
方向を示す際に利用される.

\subsubsection{Traverserを用いた走査の流れ}
Traverserを用いた走査の流れを図\ref{fig:traverse_sample_1}から図\ref{fig:traverse_sample_5}に示す.
例では, NodePath"-1,1,2,3"をTraverseする流れを示す.\\
\\
初めに, TraverserはEvaluatorを用いて走査を行うので, NodePathをEvaluatorに変換してルートノードから走査を開始する.

\begin{figure}[!htbp]
 \begin{center}
  \includegraphics[width=60mm]{./images/traverse_sample_1.pdf}
 \end{center}
 \caption{ステップ1:ルートノードから走査を開始}
 \label{fig:traverse_sample_1}
\end{figure}

Traverserは, ルートノードの評価をEvaluatorに依頼する. Evaluatorはルートノード(-1)がNodePathに含まれているのでACCEPTして, 次のEvalautorをTraverserに渡す.
この時, EvaluatorはNodePathから"-1"を除外し, 残りのNodePathを新しいEvaluatorにして渡す. 結果を受け取ったTraverserは, ルートノードの子供ノードを順番に評価を開始する.

\begin{figure}[!htbp]
 \begin{center}
  \includegraphics[width=120mm]{./images/traverse_sample_2.pdf}
 \end{center}
 \caption{ステップ2:ルートノードを評価して次のノードの評価に進む}
 \label{fig:traverse_sample_2}
\end{figure}

次に, ルートノードの子供ノードの評価を開始する, TraverserはEvalautorに子供ノードを順番に評価してもらう.
Evaluatorは受け取ったノードを評価し, Traverserに返却する. この時, EvalautorのNodePathは"1,2,3"なので, 最初のノード"0"は無視されCONTINUEと次のノードを評価するためのEvalautorが渡される.

\begin{figure}[!htbp]
 \begin{center}
  \includegraphics[width=140mm]{./images/traverse_sample_3.pdf}
 \end{center}
 \caption{ステップ3:子供ノードの評価を順々に行う}
 \label{fig:traverse_sample_3}
\end{figure}

Traverserは, 次のノード"1"をEvalautorに渡す, EvalautorはNodePathに"1"が含まれていることを確認しノードをACCEPTする. そして, いままでの手順同様に更に木の走査を続ける.

\begin{figure}[!htbp]
 \begin{center}
  \includegraphics[width=160mm]{./images/traverse_sample_4.pdf}
 \end{center}
 \caption{ステップ4:子供ノードの評価した後, 更に走査を続ける}
 \label{fig:traverse_sample_4}
\end{figure}

以上のステップを繰り返すことで最終的に目的のノードへたどり着くことが出来る. NodePathは最後の"3"を指しているので, Evaluatorはノード"3"をGOALとしてTraverserに伝える.
Traverserは, ノード"3"をGOALとし, いままでACCEPTしてきたノードすべてをTraversalとしてリストにまとめて終了する. 

\newpage

\begin{figure}[!htbp]
 \begin{center}
  \includegraphics[width=150mm]{./images/traverse_sample_5.pdf}
 \end{center}
 \caption{ステップ5:ノード"3"をGOALとし, ACCEPTしたノードをリスト化して終了}
 \label{fig:traverse_sample_5}
\end{figure}

\subsection{Jungle}
Jungleは, いままで説明してきたコンポーネントを利用して複数の木構造を管理するためのコンポーネントである.
木構造と名前の結びつけ, トランザクションの管理などを担当する.
Jungleを構成する要素を\ref{tab:jungle_components}に示す.

\begin{table}[!htbp]
\caption{Jungleを構成する要素}
\label{tab:jungle_components}
\begin{center}
\begin{tabular}{|c||c|} \hline
Jungle & 木構造の作成, 管理を行う \\ \hline
JungleTree & Editorの管理, ノードの管理を行う \\ \hline
JungleTreeEditor & トランザクションと木構造の編集を行う \\ \hline
\end{tabular}
\end{center}
\end{table}

\subsubsection{Jungle}
複数の木構造を管理する, 作成, 削除も行う. 定義をソース\ref{src:jungle_definition}に示す．
Jungleでは, 木はバージョン番号を持つ, これはマージ処理の時に情報として利用するためである.

\begin{lstlisting}[frame=lrbt,label=src:jungle_definition,caption=Jungleの定義,numbers=left]
public interface Jungle
{
	public JungleTree getTreeByName(String _name);
	public JungleTree createNewTree(String _name);
	public JungleTree deleteTree(String _name);
}
\end{lstlisting}

\subsubsection{JungleTree}
JungleTreeは, 内部にJungleTreeEditorとルートノードの情報を保持する.
JungleTreeから取得されるNodeは常に最新のものである.
定義をソース\ref{src:jungletree}に示す.

\begin{lstlisting}[frame=lrbt,label=src:jungletree,caption=JungleTreeの定義,numbers=left]
public interface JungleTree
{
	public JungleTreeEditor getTreeEditor();
	public Node getRootNode();
}
\end{lstlisting}

\subsubsection{JungleTreeEditor}
JungleTreeEditorは, 木の編集とトランザクション, バージョン番号を管理する.
なんらかの木の編集を行うと, 非破壊的に木を編集し新しい木を保持したJungleTreeEditorを返却する. 
トランザクションのコミットはsuccessメソッドにより行うことができ, もし他のスレッドなどでJungleTreeEditorを用いてすでに更新されている場合sucessメソッドは失敗する.
定義をソース\ref{src:jungletreeeditor}に示す.

\begin{lstlisting}[frame=lrbt,label=src:jungletreeeditor,caption=JungleTreeEditorの定義,numbers=left]
public interface JungleTreeEditor
{
	public Node getRoot();
	
	public Either<Error,JungleTreeEditor> addNewChildAt(NodePath _path,int _pos);
	public Either<Error,JungleTreeEditor> deleteChildAt(NodePath _path,int _pos);
	public Either<Error,JungleTreeEditor> putAttribute(NodePath _path,String _key,ByteBuffer _value);
	public Either<Error,JungleTreeEditor> deleteAttribute(NodePath _path,String _key);
	public Either<Error,JungleTreeEditor> edit(NodePath _path,NodeEditor _editor);
	
	public Either<Error,JungleTreeEditor> success();
	public String getID();
	public String getRevision();
}
\end{lstlisting}