Mercurial > hg > Papers > 2013 > shoshi-master-2013 > paper
annotate chapter3.tex @ 8:b75c564064a8 default tip
fix undefined reference , multiply defined references
| author | Shoshi TAMAKI |
|---|---|
| date | Thu, 21 Feb 2013 22:53:20 +0900 |
| parents | 44a95cddab8a |
| children |
| rev | line source |
|---|---|
| 0 | 1 \chapter{分散コンテンツマネージメントシステムの実装} |
| 2 | |
| 4 | 3 本章では, 分散コンテンツマネージメントシステムのサーバーサイド部分の実装について述べる. 前章では, 我々のシステムのおおまかな設計について説明した. |
| 4 そこでは, サーバーサイドで木構造を管理するデータベースがあると述べた. ここでは, その木構造データベースについて詳細な設計について説明する. | |
| 5 最初に, 実装した木構造データベースの利用方法について述べ, 次に詳細な設計と実装について述べる. | |
| 6 | |
| 7 \section{木構造データベースJungle} | |
| 8 木構造データベースJungleは, Javaで実装された分散コンテンツマネージメントシステムのための木構造データベースである. | |
| 9 非破壊的木構造の方法に則ったAPIと, 木構造のトラバースするための方法を提供する. 分散コンテンツマネージメントシステムに組み込んで利用する予定で実装されているため, 他のシステムに組み込んで利用することも可能である. | |
| 10 | |
| 11 \subsubsection{木の作成} | |
| 12 はじめに, データベースオブジェクトと木の作成方法について述べる. | |
| 13 Jungleは複数の木を保持することが出来る. 木には名前がついており, 名前を利用して作成・編集・削除を行うことが出来る. | |
| 14 | |
| 15 \begin{lstlisting}[frame=lrbt,label=src:create_jungle,caption=データベースオブジェクトと木の作成,numbers=left] | |
| 16 import jp.ac.u_ryukyu.cr.ie.shoshi.jungle.*; | |
| 17 import jp.ac.u_ryukyu.cr.ie.shoshi.jungle.traverser.*; | |
| 18 import jp.ac.u_ryukyu.cr.ie.shohsi.jungle.editor.*; | |
| 19 | |
| 20 DefaultTraverser traverser = new DefaultTraverser(); | |
| 21 DefaultTreeEditor editor = new DefaultTreeEditor(traverser); | |
| 22 DefaultJungle jungle = new DefaultJungle(null,"sample",editor); | |
| 23 | |
| 24 JungleTree tree = jungle.createTree("name of new tree here"); | |
| 25 \end{lstlisting} | |
| 26 | |
| 27 DeafultJungleが, 木構造データベースのオブジェクトとなる. | |
| 28 jungle.createTreeメソッドを利用して木構造を作成する. もし, すでに木構造が存在している場合は, nullが返される. | |
| 29 | |
| 30 \subsubsection{木と木を構成するノード} | |
| 31 データベースオブジェクトを作成し, 木構造とルートノードを取得するためには以下のように記述する. | |
| 32 | |
|
8
b75c564064a8
fix undefined reference , multiply defined references
Shoshi TAMAKI
parents:
7
diff
changeset
|
33 \begin{lstlisting}[frame=lrbt,label=src:get_jungle,caption=木とノードの取得,numbers=left] |
| 4 | 34 /* データベースの取得まで省略 */ |
| 35 JungleTree tree = jungle.getTreeByName("your tree name here"); | |
| 36 | |
| 37 Node root = tree.getRootNode(); | |
| 38 | |
| 39 Children<Node> children = root.getChildren(); // 子供ノードのリスト | |
| 40 Attributes attributes = root.getAttributes(); // ノードが保持する辞書 | |
| 41 | |
| 42 ByteBuffer value = attributes.get("key name"); | |
| 43 Node child = children.at(2); | |
| 44 \end{lstlisting} | |
| 45 | |
| 46 jungle.getTreeByNameメソッドで名前を指定して木構造を取得し, tree.getRootNodeメソッドでルートノードを取得することが出来る. | |
| 47 ノードは, 子供ノードのリストと辞書を保持しており, それぞれ, root.getChildren()とroot.getAttributes()で取得することが出来る. | |
| 48 | |
| 49 \subsubsection{木の編集} | |
| 50 木の編集は, 通常Nodeを書き換えるためNodeのAPIとして提供されることが多いが, JungleではJungleTreeEditorを利用して行う. | |
| 51 JungleTreeEditorには編集するためのいくつかのメソッドが用意されており, NodePathと呼ばれるルートノードからノードまでのパスを指定することでノードが編集される. | |
| 52 NodePathは, ルートノードからスタートし, ノードの子供の場所を次々に指定していくことで編集対象のノードの場所を表す.(図\ref{fig:nodepath}) | |
| 53 | |
| 54 \begin{figure}[!htbp] | |
| 55 \begin{center} | |
| 56 \includegraphics[width=80mm]{./images/nodepath.pdf} | |
| 57 \end{center} | |
| 58 \caption{NodePath} | |
| 59 \label{fig:nodepath} | |
| 60 \end{figure} | |
| 61 | |
| 62 \begin{lstlisting}[frame=lrbt,label=src:treeeditor,caption=木の編集を行うTreeEditor,numbers=left] | |
| 63 /* データベースの取得まで省略 */ | |
| 64 JungleTree tree = jungle.getTreeByName("your tree name here"); | |
| 65 | |
| 66 JungleTreeEditor editor = tree.getEditor(); | |
| 67 | |
| 68 //パスの生成 | |
| 69 DefaultNodePath path = new DefaultNodePath(); | |
| 70 path = path.add(1).add(2).add(3); | |
| 71 | |
| 72 // トランザクションの始まり | |
| 73 Either<Error,JungleTreeEditor> e = editor.addNewChildAt(path,0); | |
| 74 if(e.isA()){ | |
| 75 // エラーが起きた場合のコード | |
| 76 } | |
| 77 editor = e.b(); | |
| 78 e = editor.putAttribute(path,"key",ByteBuffer.wrap("value".getBytes()); | |
| 79 if(e.isA()){ | |
| 80 // エラーが起きた場合のコード | |
| 81 } | |
| 82 editor = e.b(); | |
| 83 editor.success(); | |
| 84 // トランザクションの終わり | |
| 85 \end{lstlisting} | |
| 86 | |
| 87 JungleTreeEditorはtree.getEditor()で取得することが出来る. | |
| 88 JungleTreeEditorはJungleTreeを非破壊的に編集し, Either$<$Error,JungleTreeEditor$>$型を返す. これは, エラーの場合はErrorが格納されており, 正常に編集が成功した場合はJungleTreeEditorを保持する型である. | |
| 89 木構造の編集により返されるJungleTreeEditorは, 編集された木構造を保持しており編集前の木構造を保持するJungleTreeEditorは別のオブジェクトである. | |
| 90 非破壊的に編集を繰り返した後, editor.successにより今までの編集をコミットすることが出来る, このとき他のJungleTreeEditorなどでJungleTreeがすでに更新されていた場合はコミットは失敗する. そのため, 最初からやり直す必要がある. | |
| 91 | |
| 92 \subsubsection{木の編集にNodeEditorを利用する} | |
| 93 木の編集にはNodeEditorを利用することも出来る, NodeEditorにはNodeの編集手順を記述しJungleTreeEditorに渡す. ソース\ref{src:treeeditor}と同等な処理を行うNodeEditorを以下に示す. | |
| 94 | |
| 95 \begin{lstlisting}[frame=lrbt,label=src:nodeeditor,caption=同等の処理を行うNodeEditor,numbers=left] | |
| 96 /* データベースの取得まで省略 */ | |
| 97 JungleTree tree = jungle.getTreeByName("your tree name here"); | |
| 98 | |
| 99 JungleTreeEditor treeEditor = tree.getEditor(); | |
| 100 | |
| 101 NodeEditor nodeEditor = new NodeEditor(){ | |
| 102 public <T extends EditableNode<T>> edit(T node){ | |
| 103 Either<Error,T> e = node.addNewChildAt(0); | |
| 104 if(e.isA()){ | |
| 105 // エラーが起きた場合のコード | |
| 106 } | |
| 107 node = e.b(); | |
| 108 e = node.putAttribute("key",ByteBuffer.wrap("value".getBytes())); | |
| 109 if(e.isA()){ | |
| 110 // エラーが起きた場合のコード | |
| 111 } | |
| 112 return e.b(); | |
| 113 } | |
| 114 }; | |
| 115 | |
| 116 DefaultNodePath path = new DefaultNodePath(); | |
| 117 path = path.add(1).add(2).add(3); | |
| 118 | |
| 119 // トランザクションの始まり | |
| 120 Either<Error,JungleTreeEditor> e = editor.edit(path,nodeEditor); | |
| 121 if(e.isA()){ | |
| 122 // エラーが起きた場合のコード | |
| 123 } | |
| 124 editor.success(); | |
| 125 // トランザクションの終わり | |
| 126 \end{lstlisting} | |
| 127 | |
| 128 \subsubsection{木のトラバース} | |
| 129 木をトラバースするためには, Traverserを利用する. Traverserは木を対象にせずNodeを対象に取るため, 木の任意の部分から走査を始めることが可能である. | |
| 130 Traverserは目的のノードまでに通ったノードをすべて列挙するため, JungleTreeEditorはNodePathとTraverserを用いて編集対象のノードまでの全てのノードを取得している. | |
| 131 以下のコードはNodePathを用いて目的のノードまでをトラバースするコードである. | |
| 132 | |
|
8
b75c564064a8
fix undefined reference , multiply defined references
Shoshi TAMAKI
parents:
7
diff
changeset
|
133 \begin{lstlisting}[frame=lrbt,label=src:tree_traverse,caption=NodePathを用いた木のトラバース,numbers=left] |
| 4 | 134 /* データベースの取得まで省略 */ |
| 135 JungleTree tree = jungle.getTreeByName("your tree name here"); | |
| 136 | |
| 137 DefaultNodePath path = new DefaultNodePath(); | |
| 138 path = path.add(1).add(2).add(3); | |
| 139 DefaultEvaluator evaluator = new DefaultEvaluator(path); | |
| 140 | |
| 141 Node root = tree.getRootNode(); | |
| 142 TraversableNodeWrapper<Node> wrapper = new TraversableNodeWrapper<Node>(root); | |
| 143 | |
| 144 // Traverserの作成 | |
| 145 DefaultTraverser traverser = new DefaultTraverser(); | |
| 146 Traversal result = traverser.traverse(wrapper,evaluator); | |
| 147 | |
| 148 for(Direction d : result){ // パスの分だけDirectionが生成される | |
| 149 int pos = d.getPosition(); | |
| 150 Node node = d.getTraget(); | |
| 151 // etc etc.. | |
| 152 } | |
| 153 \end{lstlisting} | |
| 154 | |
| 155 Evaluator,Directionなどのクラスの説明については後述する. | |
| 156 これまでに, Jungleの基本的な利用方法について述べた. 以降はJungleの更に細かい部分の実装について説明する. | |
| 157 | |
| 158 \section{木構造データベースJungleの実装} | |
| 159 \subsection{開発環境} | |
| 160 \subsubsection{言語} | |
| 161 本システムではサーバーサイドの実装にJavaを用いる. Javaは豊富なライブラリと開発環境が整っているため使いやすい言語である.\\ | |
| 162 また, 外部ライブラリとしてFunctionalJavaを用いる. このライブラリはJavaで関数型スタイルのプログラミングを行うために開発された. 本システムでは, 非破壊的木構造をメインのデータ構造とする, そのため, 多くの非破壊的データ構造を利用できるFunctionalJavaは有効に利用できる. | |
| 163 | |
| 164 \subsection{全体の構造} | |
| 165 全体木構造データベースは木構造を表現するNodeと, Nodeを非破壊的に編集するNodeEditor, Nodeの集合である木構造を非破壊的に編集するTreeEditorから構成される. 以下に, 述べたコンポーネントとその他の構成要素の表を示す. | |
| 166 | |
| 167 \begin{table}[!htbp] | |
| 168 \caption{コンポーネント一覧} | |
| 169 \label{tab:components} | |
| 170 \begin{center} | |
| 171 \begin{tabular}{|c||c|} \hline | |
| 172 名前 & 概要 \\ \hline | |
| 173 Node & 基本的なデータ構造, 読み込み専用の親子関係を表現する \\ \hline | |
| 174 NodeEditor & ノードを編集する \\ \hline | |
| 175 TreeEditor & 複数のノードから構成される木構造を編集する \\ \hline | |
| 176 Traverser & 木構造を走査し目的のNodeを取得する \\ \hline | |
| 177 JungleTreeEditor & TreeEditorに加え, トランザクションを管理する \\ \hline | |
| 178 JungleTree & JungleTreeEditorなど, 木の情報を管理する \\ \hline | |
| 179 Jungle & 木の作成・取得・削除を担当する. \\ \hline | |
| 180 \end{tabular} | |
| 181 \end{center} | |
| 182 \end{table} | |
| 183 | |
| 184 \subsection{型パラメータつきインターフェイスParentの導入} | |
| 185 我々は, Javaで木構造を表すためにParent,Childrenというインターフェイスを作成する. これは非常に複雑であるが, 親子関係を表すのに有用な仕組みだと思われる. 定義を以下に示す. | |
| 186 | |
| 187 \begin{lstlisting}[frame=lrbt,label=src:parent,caption=Parentの定義,numbers=left] | |
| 188 public interface Parent<T> { | |
| 189 public Children<T> getChildren(); | |
| 190 } | |
| 191 \end{lstlisting} | |
| 192 | |
| 193 \begin{lstlisting}[frame=lrbt,label=src:child,caption=Childrenの定義,numbers=left] | |
| 194 public interface Children<T> extends Iterable<T>{ | |
| 195 public int size(); | |
| 196 } | |
| 197 \end{lstlisting} | |
| 198 | |
| 199 これらのインターフェイスを利用するためには, まず, ソース\ref{src:node}のようにして継承したインターフェイスを作成する. | |
| 200 ここで型パラメータTはNodeを継承した型として宣言する. | |
| 201 | |
| 202 \begin{lstlisting}[frame=lrbt,label=src:node,caption=Nodeの定義,numbers=left] | |
| 203 public interface Node<T extends Node<T>> implements Parent<T> { | |
| 204 public Children<T> getChildren(); | |
| 205 } | |
| 206 \end{lstlisting} | |
| 207 | |
| 208 NodeはParentの定義よりT型の子供を保持するインターフェイスとして宣言できる. そしてT型はNode型を継承する型なので, 再帰的な構造を表現することが出来る. | |
| 209 このインターフェイスを実装すると以下のようになる. | |
| 210 | |
| 211 \begin{lstlisting}[frame=lrbt,label=src:nodeimpl,caption=NodeImplの定義,numbers=left] | |
| 212 public class NodeImpl implements Node<NodeImpl> { | |
| 213 public Children<NodeImpl> getChildren(); | |
| 214 } | |
| 215 \end{lstlisting} | |
| 216 | |
| 217 このNodeの実装では, Childrenの型パラメータがNodeImplになる. こうすることで, 実装を知らないクラスに引数として渡しても型パラメータが失われることがないコードを記述できるようになる.\\ | |
| 218 例えば, 我々のシステムでは, 主に非破壊的なデータ構造を扱う. すなわち, 非破壊的オブジェクトを編集して返すメソッドがあるクラスに存在する場合, その返されたオブジェクトは元々のオブジェクトと異なるため, 型の情報が失われてしまうためキャストが必要になる.\\ | |
| 219 しかし, この方法では, キャストは必要なく常に型パラメータは保持される. | |
| 220 | |
| 221 \begin{lstlisting}[frame=lrbt,label=src:parent_example,caption=Parentが有用な例,numbers=left] | |
| 222 class EditorA { | |
| 223 public Node edit(Node obj) { .... } | |
| 224 } | |
| 225 class EditorB { | |
| 226 public <T extends Node<T>> edit(T obj) { .... } | |
| 227 } | |
| 228 class Obj implements Node<Obj> { | |
| 229 public static void main(String args[]){ | |
| 230 Obj o = new Obj(); | |
| 231 EditorA a = new EditorA(); | |
| 232 EditorB b = new EditorB(); | |
| 233 Node n = a.edit(o); // 型が失われてNodeになるキャストが必要 | |
| 234 Obj newObj = b.edit(o); // 型は失われない. | |
| 235 } | |
| 236 } | |
| 237 \end{lstlisting} | |
| 238 | |
| 239 我々の実装で, 親子関係を扱うコンポーネントはすべてこのインターフェイスを継承する. 次に, 他の構成するコンポーネントについて述べる. | |
| 240 | |
| 241 \newpage | |
| 242 | |
| 243 \section{Node} | |
| 244 Nodeは, 木構造を表現するためのコンポーネントである. 木構造は子供と辞書を保持する. (図\ref{fig:node_components}) | |
| 245 我々はNodeのAPIをソース\ref{src:definition_of_node}のように定義した. | |
| 246 基本的に, Nodeは読み込み専用であり, 編集操作を持たない. | |
| 247 \begin{figure}[!htbp] | |
| 248 \begin{center} | |
| 6 | 249 \includegraphics[width=110mm]{./images/node_component.pdf} |
| 4 | 250 \end{center} |
| 251 \caption{Nodeの構成要素} | |
| 252 \label{fig:node_components} | |
| 253 \end{figure} | |
| 254 | |
| 255 \begin{lstlisting}[frame=lrbt,label=src:definition_of_node,caption=Nodeの定義,numbers=left] | |
| 256 public class Node implements Children<Node> | |
| 257 ,AttributesContainer { | |
| 258 public Attribute getAttribute(); | |
| 259 public Children<NodeImpl> getChildren(); | |
| 260 } | |
| 261 \end{lstlisting} | |
| 262 | |
| 263 getAttributesは辞書オブジェクトを取得するメソッドで, getChildrenは子ノードのリストを取得するメソッドである. | |
| 264 Childrenの定義は前述したとおりで, Attributesの定義を以下に示す. | |
| 265 | |
| 266 \begin{lstlisting}[frame=lrbt,label=src:definition_of_children,caption=Nodeの定義,numbers=left] | |
| 267 public interface Attributes { | |
| 268 public ByteBuffer get(String key); | |
| 269 } | |
| 270 \end{lstlisting} | |
| 271 | |
| 272 ここで, ByteBufferはjava.nio.ByteBufferである. ここでは, 辞書に格納するものが文字列に限らないことを考慮しByteBuffer型を採用した. | |
| 273 | |
| 274 \newpage | |
| 275 | |
| 276 \section{NodeEditor} | |
| 277 前章で述べたとおり, 非破壊的木構造は編集対象までのNodeをRootからすべてコピーした後, 編集対象のNodeを書き換える. | |
| 278 よって, Nodeを書き換える仕組みが必要である. NodeEditorはNodeを(木構造ではない)を編集するためのコンポーネントである. | |
| 279 NodeEditorを構成する要素を表\ref{tab:nodeeditor_components}に示す. | |
| 280 | |
| 281 \begin{figure}[!htbp] | |
| 282 \begin{center} | |
| 283 \includegraphics[width=150mm]{./images/nodeeditor_component.pdf} | |
| 284 \end{center} | |
| 285 \caption{NodeEditorのイメージ} | |
| 286 \label{fig:nodeeditor_component} | |
| 287 \end{figure} | |
| 288 | |
| 289 \begin{table}[!htbp] | |
| 290 \caption{NodeEditorを構成する要素} | |
| 291 \label{tab:nodeeditor_components} | |
| 292 \begin{center} | |
| 293 \begin{tabular}{|c||p{25zw}|} \hline | |
| 294 クラス名 & 概要 \\ \hline \hline | |
| 295 EditableNode & 非破壊的に編集できるNode \\ \hline | |
| 296 EditableAttribute & 非破壊的に編集できる辞書, 編集の際に新しいEditableNodeを返す. \\ \hline | |
| 297 EditableChildren & 非破壊的に編集できる子Nodeリスト, 編集の際に新しいEditableNodeを返す. \\ \hline | |
| 298 NodeEditor & Nodeの編集処理を記述するためのシングルメソッドクラス. \\ \hline | |
| 299 \end{tabular} | |
| 300 \end{center} | |
| 301 \end{table} | |
| 302 | |
| 303 \subsubsection{EditableNode} | |
| 304 EditableNodeは, Parentを継承した非破壊的に編集できることを示すNodeである. EditableAttributesとEditableChildrenをここから取得することが出来る. | |
| 305 | |
| 306 \subsubsection{EditableAttributes} | |
| 307 EditableAttributeは, Attributesを拡張し編集操作を加えたインターフェイスである. 辞書への追加, 削除が定義されている. | |
| 308 また, 辞書への追加, 削除の操作が行われると新しくEditableNodeが作成される. この作成されたEditableNodeは辞書を元々保持していたEditableNodeのコピーを編集したものでる. | |
| 309 | |
| 310 \begin{lstlisting}[frame=lrbt,label=src:definition_of_editableattributes,caption=EditableAttributesの定義,numbers=left] | |
| 311 public interface EditableAttributes<T extends EditableNode<T>> | |
| 312 implements Attributes { | |
| 313 public void put(String key,ByteBuffer value); | |
| 314 public void delete(String key); | |
| 315 } | |
| 316 \end{lstlisting} | |
| 317 | |
| 318 \subsubsection{EditableChildren} | |
| 319 EditableChildrenは, Childrenを拡張し編集操作を加えたインターフェイスである. 子リストへのNodeの新規追加, 削除を行うことが出来る. | |
| 320 EditableAttributes同様に, リストを編集すると新しくコピーされたオブジェクトを作成し, それを編集して返却する. | |
| 321 | |
| 322 \begin{lstlisting}[frame=lrbt,label=src:definition_of_editablechildren,caption=EditableChildrenの定義,numbers=left] | |
| 323 public interface EditableChildren<T extends EditableNode<T>> | |
| 324 implements Children<T> { | |
| 325 public Either<Error,T> addNewChildAt(int pos); | |
| 326 public Either<Error,T> deleteChildAt(int pos); | |
| 327 } | |
| 328 \end{lstlisting} | |
| 329 | |
| 330 \subsubsection{NodeEditor} | |
| 331 NodeEditorは, Nodeの編集を手順を記述するためのインターフェイスである. メソッドeditを持ち引数としてEditableNodeを取る, edit内部に編集手順を記述し, 戻り値として編集されたEditableNodeを返す.\\ | |
| 332 このインターフェイスは, ユーザー側がNodeを編集するための手順をクラス化し, 木構造を編集するコンポーネント(後述)に渡すことで, 柔軟な編集を実現することが出来る. | |
| 333 | |
| 334 \begin{lstlisting}[frame=lrbt,label=src:definition_of_nodeeditor,caption=NodeEditorの定義,numbers=left] | |
| 335 public interface NodeEditor { | |
| 336 public <T extends EditableNode<T>> Either<Error,T> edit(T node); | |
| 337 } | |
| 338 \end{lstlisting} | |
| 339 | |
| 340 例えば, あるNodeの辞書に名前と生年月日, 研究室を追加するNodeEditorは以下のように記述する. | |
| 341 | |
| 342 \begin{lstlisting}[frame=lrbt,label=src:nodeditor_sample,caption=NodeEditorのサンプル実装,numbers=left] | |
| 343 public class AddProfile implements NodeEditor { | |
| 344 public <T extends EditableNode<T>> Either<Error,T> edit(T node){ | |
| 345 node = node.getAttributes().put(key_name,name).b(); | |
| 346 node = node.getAttributes().put(key_birth,birth).b(); | |
| 347 node = node.getAttributes().put(key_lab,laboname).b(); | |
| 348 return node; | |
| 349 } | |
| 350 } | |
| 351 \end{lstlisting} | |
| 352 | |
| 353 \newpage | |
| 354 | |
| 355 \subsection{TreeEditor} | |
| 356 TreeEditorは木構造を非破壊的に編集するためのコンポーネントでありNodeEditorを利用して実装される. | |
| 357 非破壊的木構造の編集方法通り, TreeEditorは編集対象のNodeまでをコピーする. コピーした編集対象のNodeをNodeEditorを使って編集する. | |
| 358 NodeEditorはNodeを編集するためのコンポーネントだが, TreeEditorは木を構成するためのコンポーネントであるため木を構成するためのNodeを持つ. | |
| 359 TreeEditorを構成する要素を表\ref{tab:treeeditor_components}に示す. | |
| 360 | |
| 361 \begin{table}[!htbp] | |
| 362 \caption{TreeEditorの構成要素} | |
| 363 \label{tab:treeeditor_components} | |
| 364 \begin{center} | |
| 365 \begin{tabular}{|c||c|} \hline | |
| 366 クラス名 & 概要 \\ \hline \hline | |
| 367 TreeNode & 木を構成するノード \\ \hline | |
| 368 TreeNodeChildren & 子供ノードのリスト \\ \hline | |
| 369 TreeNodeAttributes & ノードが保持する辞書 \\ \hline | |
| 370 TreeEditor & 木を編集するためのメソッドを持つエディタ \\ \hline | |
| 371 \end{tabular} | |
| 372 \end{center} | |
| 373 \end{table} | |
| 374 | |
| 375 \subsubsection{TreeNode} | |
| 376 TreeNodeは, EditableNodeとほぼ同じであるが木を構成するために適したメソッドを保持するTreeNodeAttributeとTreeNodeChildrenを保持する. | |
| 377 | |
| 378 \subsubsection{TreeAttribute} | |
| 379 TreeNodeAttributeは, Attributesを拡張し編集操作を加えたインターフェイスである. EditableAttribute同様, 辞書への追加, 削除が定義されている. | |
| 380 また, 辞書への追加, 削除の操作が行われると新しくTreeNodeが作成される. | |
| 381 | |
| 382 \subsubsection{TreeNodeChildren} | |
| 383 TreeNodeChildrenは, Childrenを拡張し編集操作を加えたインターフェイスである. 子リストへのNodeの新規追加, 削除を行うことが出来る. | |
| 384 EditableChildrenは, 子供Nodeとして既存のNodeを追加することが出来ないが, TreeNodeChildrenはそれが可能であるため, 効率よく木を構成することができる. | |
| 385 また, EditableChildren同様にリストを編集すると新しくコピーされたオブジェクトを作成し, それを編集して返却する. | |
| 386 | |
| 6 | 387 \newpage |
| 388 | |
| 4 | 389 \begin{lstlisting}[frame=lrbt,label=src:definition_of_treenodechildren,caption=TreeNodeChildrenの定義,numbers=left] |
| 390 public interface TreeNodeChildren<T extends TreeNode<T>> | |
| 391 implements Children<T> { | |
| 392 public Either<Error,T> addNewChildAt(int pos); | |
| 393 public Either<Error,T> deleteChildAt(int pos); | |
| 394 public Either<Error,T> addNewChildAt(int pos,T newChild); | |
| 395 } | |
| 396 \end{lstlisting} | |
| 397 | |
| 398 \subsubsection{TreeEditor} | |
| 399 TreeEditorは, TreeNodeで構成される木を編集するための操作が定義されているインターフェイスである. | |
| 400 NodePathと呼ばれるルートNodeから編集対象のNodeまでのパスとNodeEditorを引数として受け取り, 非破壊的に編集する. | |
| 401 TreeEditorの定義を以下に示す. | |
| 402 | |
|
8
b75c564064a8
fix undefined reference , multiply defined references
Shoshi TAMAKI
parents:
7
diff
changeset
|
403 \begin{lstlisting}[frame=lrbt,label=src:definition_of_treeeditor,caption=TreeEditorの定義,numbers=left] |
| 4 | 404 public interface TreeEditor { |
| 405 public <T extends TreeNode<T>> Either<Error,T> edit(T root,NodePath,NodeEditor editor); | |
| 406 } | |
| 407 \end{lstlisting} | |
| 408 | |
| 409 TreeEditorは, 木を対象にするわけではなくNodeを引数に取るため, 木を構成する任意のTreeNodeから編集することも可能である. | |
| 410 | |
| 6 | 411 \newpage |
| 4 | 412 |
| 0 | 413 \subsection{Traverser} |
| 6 | 414 Traverserは木構造を走査するためのコンポーネントであり, TreeEditorでも利用されている. |
| 415 TraverserはNodeと走査するためのEvaluatorと呼ばれるものを引数に取り走査を行う. Evaluatorとは, TraverserがあるNodeを走査中にそのNodeの先に進むかどうか判断するために利用される. | |
| 416 Evaluatorは, Nodeとその他の情報(Nodeの場所)を受け取り, そのNodeの先に進むか進まないか判断する. | |
| 417 そして, 戻り値として次のNodeを評価するための新しいEvaluatorと評価結果をTraverserに返却する. 表\ref{tab:traverser_components}にTraverserを構成する要素を示す. | |
| 418 | |
| 419 \begin{table}[!htbp] | |
| 420 \caption{Traverserを構成する要素} | |
| 421 \label{tab:traverser_components} | |
| 422 \begin{center} | |
| 423 \begin{tabular}{|c||p{27zw}|} \hline | |
| 424 名前 & 概要 \\ \hline \hline | |
| 425 Traverser & 木構造, Nodeを走査する. \\ \hline | |
| 426 TraversableNode & Traverserで走査することの出来るNode \\ \hline | |
| 427 TraversableChildren & TraversableNode同様, Traverserで走査することの出来るChildren \\ \hline | |
| 428 Evaluator & TraversableNodeを評価する \\ \hline | |
| 429 Traversal & Traverseの結果, ルートNodeから目的Nodeまでの全てのNodeのリスト \\ \hline | |
| 430 Direction & Traverseの結果に含まれる, 次のNodeの位置情報が含まれている \\ \hline | |
| 431 \end{tabular} | |
| 432 \end{center} | |
| 433 \end{table} | |
| 434 | |
| 435 \subsubsection{TraversableNode} | |
| 436 TraversableNodeは, Traverserが走査することの出来ることを示すNodeである. | |
| 437 | |
| 438 \subsubsection{TraversableChildren} | |
| 439 TraversableChildrenは, Traverserが走査することの出来ることを示すNodeの子供Nodeのリストである. | |
| 440 | |
| 441 \subsubsection{Evaluator} | |
| 442 Evaluatorは, Traverserが走査しているNodeを評価する. | |
| 443 戻り値としてEvaluationと呼ばれる, 次のEvaluatorとNodeの評価を保持するオブジェクトを返す. | |
| 444 Evaluatorにより, 評価されたNodeはTraverserがNodeを走査するべきかしないべきか判断するために利用される. | |
| 445 Evaluatorの定義とEvaluationの定義をソース\ref{src:evaluator_definition}とソース\ref{src:evaluation_definition}に示す. | |
| 446 | |
| 447 \begin{lstlisting}[frame=lrbt,label=src:evaluator_definition,caption=Evaluatorの定義,numbers=left] | |
| 448 public interface Evaluator | |
| 449 { | |
| 450 public <T extends TraversableNode<T>> Evaluation evaluate(T _current,int _pos); | |
| 451 } | |
| 452 \end{lstlisting} | |
| 453 | |
| 454 \begin{lstlisting}[frame=lrbt,label=src:evaluation_definition,caption=Evaluatorの定義,numbers=left] | |
| 455 public interface Evaluation | |
| 456 { | |
| 457 public Result result(); | |
| 458 public Evaluator evaluator(); | |
| 459 } | |
| 460 \end{lstlisting} | |
| 461 | |
|
8
b75c564064a8
fix undefined reference , multiply defined references
Shoshi TAMAKI
parents:
7
diff
changeset
|
462 Evaluationのresultメソッドは, このNodeの評価結果を表すEnum型のクラスResultを返す. 表\ref{tab:evaluation_result}に評価の種類を示す. |
| 6 | 463 |
| 464 \begin{table}[!htbp] | |
| 465 \caption{Evalautionの結果一覧} | |
| 466 \label{tab:evaluation_result} | |
| 467 \begin{center} | |
| 468 \begin{tabular}{|c||c|} \hline | |
| 469 名前 & 概要 \\ \hline \hline | |
| 470 ACCEPT & このNodeを受け入れて先に進む \\ \hline | |
| 471 CONTINUE & このNodeを受け入れずに, 次の候補を評価する \\ \hline | |
| 472 BREAK & このNodeを受け入れず, でこれ以上の走査をやめる \\ \hline | |
| 473 GOAL & このNodeを受け入れて, 走査をやめる \\ \hline | |
| 474 \end{tabular} | |
| 475 \end{center} | |
| 476 \end{table} | |
| 477 | |
| 478 \subsubsection{Traversal} | |
| 479 Traversalは, Traverserによる走査の結果である. ルートノードから目的ノードまでのノードのリストを保持する. | |
| 480 図\ref{fig:traversal_image}にTraversalのイメージを示す. | |
| 481 この図はTraverserで, NodePath"-1,1,2,3"を走査した時のTraversalが保持する結果を表している. | |
| 482 | |
| 483 \begin{figure}[!htbp] | |
| 484 \begin{center} | |
| 485 \includegraphics[width=100mm]{./images/traversal_image.pdf} | |
| 486 \end{center} | |
| 487 \caption{Traversalのイメージ} | |
| 488 \label{fig:traversal_image} | |
| 489 \end{figure} | |
| 490 | |
| 491 \subsubsection{Direction} | |
| 492 Directionは, あるノードがその親ノードの何番目の子供ノードに値するかを示す. Traversalにて, ルートノードから目的ノードまでのリストを表す時, あるノードから次のノードへの | |
| 493 方向を示す際に利用される. | |
| 494 | |
| 495 \subsubsection{Traverserを用いた走査の流れ} | |
| 496 Traverserを用いた走査の流れを図\ref{fig:traverse_sample_1}から図\ref{fig:traverse_sample_5}に示す. | |
| 497 例では, NodePath"-1,1,2,3"をTraverseする流れを示す.\\ | |
| 498 \\ | |
| 499 初めに, TraverserはEvaluatorを用いて走査を行うので, NodePathをEvaluatorに変換してルートノードから走査を開始する. | |
| 500 | |
| 501 \begin{figure}[!htbp] | |
| 502 \begin{center} | |
| 503 \includegraphics[width=60mm]{./images/traverse_sample_1.pdf} | |
| 504 \end{center} | |
| 505 \caption{ステップ1:ルートノードから走査を開始} | |
| 506 \label{fig:traverse_sample_1} | |
| 507 \end{figure} | |
| 508 | |
| 509 Traverserは, ルートノードの評価をEvaluatorに依頼する. Evaluatorはルートノード(-1)がNodePathに含まれているのでACCEPTして, 次のEvalautorをTraverserに渡す. | |
| 510 この時, EvaluatorはNodePathから"-1"を除外し, 残りのNodePathを新しいEvaluatorにして渡す. 結果を受け取ったTraverserは, ルートノードの子供ノードを順番に評価を開始する. | |
| 511 | |
| 512 \begin{figure}[!htbp] | |
| 513 \begin{center} | |
| 514 \includegraphics[width=120mm]{./images/traverse_sample_2.pdf} | |
| 515 \end{center} | |
| 516 \caption{ステップ2:ルートノードを評価して次のノードの評価に進む} | |
|
7
44a95cddab8a
added benchmark results and graphs and gnuplot script
Shoshi TAMAKI
parents:
6
diff
changeset
|
517 \label{fig:traverse_sample_2} |
| 6 | 518 \end{figure} |
| 519 | |
| 520 次に, ルートノードの子供ノードの評価を開始する, TraverserはEvalautorに子供ノードを順番に評価してもらう. | |
| 521 Evaluatorは受け取ったノードを評価し, Traverserに返却する. この時, EvalautorのNodePathは"1,2,3"なので, 最初のノード"0"は無視されCONTINUEと次のノードを評価するためのEvalautorが渡される. | |
| 522 | |
| 523 \begin{figure}[!htbp] | |
| 524 \begin{center} | |
| 525 \includegraphics[width=140mm]{./images/traverse_sample_3.pdf} | |
| 526 \end{center} | |
| 527 \caption{ステップ3:子供ノードの評価を順々に行う} | |
|
7
44a95cddab8a
added benchmark results and graphs and gnuplot script
Shoshi TAMAKI
parents:
6
diff
changeset
|
528 \label{fig:traverse_sample_3} |
| 6 | 529 \end{figure} |
| 530 | |
| 531 Traverserは, 次のノード"1"をEvalautorに渡す, EvalautorはNodePathに"1"が含まれていることを確認しノードをACCEPTする. そして, いままでの手順同様に更に木の走査を続ける. | |
| 532 | |
| 533 \begin{figure}[!htbp] | |
| 534 \begin{center} | |
| 535 \includegraphics[width=160mm]{./images/traverse_sample_4.pdf} | |
| 536 \end{center} | |
| 537 \caption{ステップ4:子供ノードの評価した後, 更に走査を続ける} | |
|
7
44a95cddab8a
added benchmark results and graphs and gnuplot script
Shoshi TAMAKI
parents:
6
diff
changeset
|
538 \label{fig:traverse_sample_4} |
| 6 | 539 \end{figure} |
| 540 | |
| 541 以上のステップを繰り返すことで最終的に目的のノードへたどり着くことが出来る. NodePathは最後の"3"を指しているので, Evaluatorはノード"3"をGOALとしてTraverserに伝える. | |
| 542 Traverserは, ノード"3"をGOALとし, いままでACCEPTしてきたノードすべてをTraversalとしてリストにまとめて終了する. | |
| 543 | |
| 544 \newpage | |
| 545 | |
| 546 \begin{figure}[!htbp] | |
| 547 \begin{center} | |
| 548 \includegraphics[width=150mm]{./images/traverse_sample_5.pdf} | |
| 549 \end{center} | |
| 550 \caption{ステップ5:ノード"3"をGOALとし, ACCEPTしたノードをリスト化して終了} | |
|
7
44a95cddab8a
added benchmark results and graphs and gnuplot script
Shoshi TAMAKI
parents:
6
diff
changeset
|
551 \label{fig:traverse_sample_5} |
| 6 | 552 \end{figure} |
| 553 | |
| 554 \subsection{Jungle} | |
| 555 Jungleは, いままで説明してきたコンポーネントを利用して複数の木構造を管理するためのコンポーネントである. | |
| 556 木構造と名前の結びつけ, トランザクションの管理などを担当する. | |
| 557 Jungleを構成する要素を\ref{tab:jungle_components}に示す. | |
| 558 | |
| 559 \begin{table}[!htbp] | |
| 560 \caption{Jungleを構成する要素} | |
| 561 \label{tab:jungle_components} | |
| 562 \begin{center} | |
| 563 \begin{tabular}{|c||c|} \hline | |
| 564 Jungle & 木構造の作成, 管理を行う \\ \hline | |
| 565 JungleTree & Editorの管理, ノードの管理を行う \\ \hline | |
| 566 JungleTreeEditor & トランザクションと木構造の編集を行う \\ \hline | |
| 567 \end{tabular} | |
| 568 \end{center} | |
| 569 \end{table} | |
| 570 | |
| 571 \subsubsection{Jungle} | |
| 572 複数の木構造を管理する, 作成, 削除も行う. 定義をソース\ref{src:jungle_definition}に示す． | |
| 573 Jungleでは, 木はバージョン番号を持つ, これはマージ処理の時に情報として利用するためである. | |
| 574 | |
| 575 \begin{lstlisting}[frame=lrbt,label=src:jungle_definition,caption=Jungleの定義,numbers=left] | |
| 576 public interface Jungle | |
| 577 { | |
| 578 public JungleTree getTreeByName(String _name); | |
| 579 public JungleTree createNewTree(String _name); | |
| 580 public JungleTree deleteTree(String _name); | |
| 581 } | |
| 582 \end{lstlisting} | |
| 583 | |
| 584 \subsubsection{JungleTree} | |
| 585 JungleTreeは, 内部にJungleTreeEditorとルートノードの情報を保持する. | |
| 586 JungleTreeから取得されるNodeは常に最新のものである. | |
| 587 定義をソース\ref{src:jungletree}に示す. | |
| 588 | |
| 589 \begin{lstlisting}[frame=lrbt,label=src:jungletree,caption=JungleTreeの定義,numbers=left] | |
| 590 public interface JungleTree | |
| 591 { | |
| 592 public JungleTreeEditor getTreeEditor(); | |
| 593 public Node getRootNode(); | |
| 594 } | |
| 595 \end{lstlisting} | |
| 596 | |
| 597 \subsubsection{JungleTreeEditor} | |
| 598 JungleTreeEditorは, 木の編集とトランザクション, バージョン番号を管理する. | |
| 599 なんらかの木の編集を行うと, 非破壊的に木を編集し新しい木を保持したJungleTreeEditorを返却する. | |
| 600 トランザクションのコミットはsuccessメソッドにより行うことができ, もし他のスレッドなどでJungleTreeEditorを用いてすでに更新されている場合sucessメソッドは失敗する. | |
| 601 定義をソース\ref{src:jungletreeeditor}に示す. | |
| 602 | |
| 603 \begin{lstlisting}[frame=lrbt,label=src:jungletreeeditor,caption=JungleTreeEditorの定義,numbers=left] | |
| 604 public interface JungleTreeEditor | |
| 605 { | |
| 606 public Node getRoot(); | |
| 607 | |
| 608 public Either<Error,JungleTreeEditor> addNewChildAt(NodePath _path,int _pos); | |
| 609 public Either<Error,JungleTreeEditor> deleteChildAt(NodePath _path,int _pos); | |
| 610 public Either<Error,JungleTreeEditor> putAttribute(NodePath _path,String _key,ByteBuffer _value); | |
| 611 public Either<Error,JungleTreeEditor> deleteAttribute(NodePath _path,String _key); | |
| 612 public Either<Error,JungleTreeEditor> edit(NodePath _path,NodeEditor _editor); | |
| 613 | |
| 614 public Either<Error,JungleTreeEditor> success(); | |
| 615 public String getID(); | |
| 616 public String getRevision(); | |
| 617 } | |
| 618 \end{lstlisting} |