Papers/2017/tatsuki-master: jungle.tex comparison

comparison jungle.tex @ 15:33d8077a5d45

commit

author	tatsuki
date	Thu, 09 Feb 2017 17:25:56 +0900
parents	e4da23b04260
children	d5306971efbf

comparison

equal deleted inserted replaced

-:e4da23b04260
+:33d8077a5d45
 \chapter{非破壊的木構造データベースJungle}
-本章では、当研究室で開発を行っているデータベース Jungle について記述する。
+本章では、Jungleの基本的な解説を行う。
+初めに Jungle の特徴である非破壊的木構造の説明をし、その後提供しているAPIについて述べる。
-\section{概要}
-Jungleは、当研究室で開発を行っているデータベースで、Javaを用いて実装されている。
-Jungleは名前付きの複数の木の集合からなり、木は複数のノードの集合で出来ている。
-ノードは自身の子のリストと属性名と属性値の組でデータを持ち、データベースのレコードに相当する。
-通常のレコードと異なるのは、ノードに子供となる複数のノードが付くところである。
-Jungleでは、親から子への片方向の参照しか持たない。
-通常のRDBと異なり、Jungleは木構造をそのまま読み込むことができる。例えば、XMLやJsonで記述された構造を、データベースを設計することなく読み込むことが可能である。
-また、この木を、そのままデータベースとして使用することも可能である。しかし、木の変更の手間は木の構造に依存する。
-%特に非破壊木構造を採用しているJungleでは木構造の変更にo(1)からo(n)の様々な選択肢がある。つまり、アプリケーションに合わせて木を設計しない限り、
-特に非破壊木構造を採用しているJungleでは、木構造の変更の手間はO(1)からO(n)となりえる。つまり、アプリケーションに合わせて木を設計しない限り、
-十分な性能を出すことはできない。逆に、正しい木の設計を行えば高速な処理が可能である。
-Jungleは基本的にon memoryで使用することを考えており、一度、木のルートを取得すれば、その上で木構造として自由にアクセスして良い。
-Jungleは分散データベースを構成するように設計されており、分散ノード間の通信は木の変更のログを交換することによって行われる。
-持続性のある分散ノードを用いることでJungleの持続性を保証することができる。本論文では基本的に分散実装部分ではなく on memory DBの
-部分について考察する。
-本章ではまず破壊的木構造と、非破壊的木構造の説明をし、その後Jungleの提供しているAPIについて述べる。
-\newpage
 \section{非破壊的木構造}
 Jungle は、非破壊的木構造という特殊な木構造を持つ。
-本節では、初めに破壊的木構造と非破壊的木構造の編集・メリットデメリットについて記述する。
+本節では、破壊的木構造と非破壊的木構造の編集・メリットデメリットについて記述する。
 \vspace{0.3in}
 {\Large 破壊的木構造の編集}
 \vspace{0.1in}
 \caption{非破壊的木構造の編集}
 \label{fig:nondestractive}
 \end{center}
 \end{figure}
-\newpage
 非破壊的木構造においてデータのロックが必要となる部分は、木のコピーを作り終えた後に
 ルートノードを更新するときだけである。
 データ編集を行っている間ロックが必要な破壊的木構造に比べ、編集中においてもデータの読み込みが可能であるが、
 書き込み時の手間は大きくなる。
 以下にEitherクラスが提供しているAPI(表\ref{EitherAPI})を記す。
 \begin{table}[htb]
 \begin{center}
 \caption{Eitherに実装されているAPI}
 \begin{tabular}{|p{15em}|p{24em}|}        \hline
-{\tt boolean isA()} & EitherがAを持っているかどうかを調べる。持っている場合trueを返す。\\ \hline
+{\small{\tt boolean isA()}} & {\small EitherがAを持っているかどうかを調べる。持っている場合trueを返す。}\\ \hline
-{\tt boolean isB()} & EitherがBを持っているかどうかを調べる。持っている場合trueを返す。\\ \hline
+{\small{\tt boolean isB()}} & {\small EitherがBを持っているかどうかを調べる。持っている場合trueを返す。}\\ \hline
-{\tt A a()} & Aの値を取得する。\\ \hline
+{\small{\tt A a()}} &{\small Aの値を取得する。}\\ \hline
-{\tt B b()} & Bの値を取得する。\\ \hline
+{\small{\tt B b()}} &{\small Bの値を取得する。}\\ \hline
 \end{tabular}
 \label{EitherAPI}
 \end{center}
 \end{table}
 \begin{table}[htb]
 \begin{center}
 \caption{Jungleに実装されているAPI}
 \begin{tabular}{|p{15em}|p{24em}|}        \hline
-{\tt JungleTree createNewTree(String treeName) } & Jungleに新しく木を生成する。木の名前が重複した場合、生成に失敗しnullを返す。     \\ \hline
+{\small {\tt JungleTree createNewTree(String treeName)}} &{\small Jungleに新しく木を生成する。木の名前が重複した場合、生成に失敗しnullを返す。}     \\ \hline
-{\tt JungleTree getTreeByName(String treeName)}  & JungleからtreeNameと名前が一致するtreeを取得する。名前が一致するTreeがない場合取得は失敗しnullを返す       \\ \hline
+{\small {\tt JungleTree getTreeByName(String treeName)}} &{\small JungleからtreeNameと名前が一致するtreeを取得する。名前が一致するTreeがない場合取得は失敗しnullを返す。}       \\ \hline
 \end{tabular}
 \label{jungleAPI}
 \end{center}
 \end{table}
 \section{JungleTree}
 Jungleは複数の木の集合で出来ている。
-Jungleの木は、変更を加えるためのEditor・検索を行うTraversreなどを保持しており、ユーザーはそれらを用いてデータにアクセスする。
+Jungleの木は、自身の情報をTreeContext というオブジェクトに保持している。
-過去のバージョンの木に対するアクセスや、特定のノードのPathを検索する機能も持っている。
+TreeContextとは、木構造のデータ(表\ref{TreeContext1})を持つクラスである。
+\newpage
+\begin{table}[htb]
+\begin{center}
+\caption{TreeContextが保持している値}
+\begin{tabular}{|l|}        \hline
+{\tt } 自身のルートノード\\ \hline
+{\tt } 1つ前のバージョンのTreeContext\\ \hline
+{\tt } 編集のログ\\ \hline
+{\tt } 木のuuid    \\ \hline
+{\tt } 木の名前    \\ \hline
+{\tt } 木のversion    \\ \hline
+{\tt } 木の検索に使うTraverser    \\ \hline
+\end{tabular}
+\label{TreeContext1}
+\end{center}
+\end{table}
+Jungle の木は、自身の木構造に編集を行う Editor や 検索に使用する Traverser を提供しており、ユーザーはそれを用いて木構造にアクセスする。
+また、過去のバージョンの木に対するアクセスや、特定のノードのPathを検索する機能も持っている。
 以下にJungleTreeクラスが提供しているAPI(表\ref{JungleTreeAPI})を記す
 \begin{table}[htb]
 \begin{center}
 \caption{JungleTreeに実装されているAPI}
 \begin{tabular}{|p{15em}|p{24em}|}        \hline
-{\tt TreeNode getRootNode()} &木のルートノードを取得する。   \\ \hline
+{\small {\tt TreeNode getRootNode()}} &{\small 木のルートノードを取得する。}   \\ \hline
-{\tt long revision()} & 木のバーションを取得する。初めは0から始まり、木への変更がCommitされる度に1上昇する。 \\ \hline
+{\small {\tt long revision()}} & {\small 木のバーションを取得する。初めは0から始まり、木への変更がCommitされる度に1上昇する。} \\ \hline
-{\tt JungleTreeEditor getJungleTreeEditor()} & 木へ変更を加えるEditorを取得する。\\ \hline
+{\small {\tt JungleTreeEditor getJungleTreeEditor()}} &{\small  木へ変更を加えるEditorを取得する。}\\ \hline
-{\tt Either<Error, JungleTree> getOldTree(long revision)} & 引数で指定したint revisionに等しいバージョンの木を取得する。 \\ \hline
+{\small {\tt Either<Error, JungleTree> getOldTree(long revision)}} & {\small 引数で指定したint revisionに等しいバージョンの木を取得する。} \\ \hline
-{\tt InterfaceTraverser getTraverser()} & 木の検索を行うTraverserを取得する。 \\ \hline
+{\small {\tt InterfaceTraverser getTraverser()}} & {\small 木の検索を行うTraverserを取得する。} \\ \hline
-{\tt Either<Error, TreeNode> getNodeOfPath(NodePath path)} & {\tt NodePathで指定した位置と値なるノードを取得する。}  \\ \hline
+{\small {\tt Either<Error, TreeNode> getNodeOfPath(NodePath path)}} &{\small  {\tt NodePathで指定した位置と値なるノードを取得する。}}  \\ \hline
-{\tt NodePath getNodePath(TreeNode node)} & 引数で渡したノードの位置を表す{\tt NodePath}を返す。\\ \hline
+{\small {\tt NodePath getNodePath(TreeNode node)}} & {\small 引数で渡したノードの位置を表す{\tt NodePath}を返す。}\\ \hline
 \end{tabular}
 \label{JungleTreeAPI}
 \end{center}
 \end{table}
 \begin{table}[htb]
 \begin{center}
 \caption{TreeNodeに実装されているAPI}
 \begin{tabular}{|p{15em}|p{24em}|}                                  \hline
-{\tt Children getChildren()} & ノードの子供を扱うChildrenオブジェクトを返す。\\ \hline
+{\small {\tt Children getChildren()}} &{\small  ノードの子供を扱うChildrenオブジェクトを返す} \\ \hline
-{\tt Attribute getAttribute()} &ノードが保持しているデータを扱うAttribteオブジェクトを返す。    \\ \hline
+{\small {\tt Attribute getAttribute()}} &{\small ノードが保持しているデータを扱うAttribteオブジェクトを返す。}   \\ \hline
 \end{tabular}
 \label{TreeNodeAPI}
 \end{center}
 \end{table}
 これらを利用しノードが保持している値や、子供にアクセスする。
 \begin{table}[htbH]
 \begin{center}
 \caption{Childrenに実装されているAPI}
 \begin{tabular}{|p{15em}|p{24em}|}                                  \hline
-{\tt int size()}  &  子供の数を返す。\\ \hline
+{\small{\tt int size()}}  & {\small 子供の数を返す。}\\ \hline
-{\tt <Either Error,TreeNode> at(int num)} &ノードが持つ子供の中から、 変数{\tt num}で指定された位置にある子ノードを返す。存在しない位置を指定した場合、{\tt Error} を返す。   \\ \hline
+{\small{\tt <Either Error,TreeNode> at(int num)}} &{\small ノードが持つ子供の中から、 変数{\tt num}で指定された位置にある子ノードを返す。存在しない位置を指定した場合、{\tt Error} を返す。}   \\ \hline
 \end{tabular}
 \label{Children}
 \end{center}
 \end{table}
 \begin{table}[htbH]
 \begin{center}
 \caption{Attributeに実装されているAPI}
 \begin{tabular}{|p{15em}|p{24em}|} \hline
-{\tt ByteBuffer get(String key)}   &ノードが持つ値から、属性名 {\tt key}とペアの属性値を{\tt ByteBuffer}型で返す。ノードが保持していない{\tt key}を渡した場合エラーを返す。 \\ \hline
+{\small{\tt ByteBuffer get(String key)}}   &{\small ノードが持つ値から、属性名 {\tt key}とペアの属性値を{\tt ByteBuffer}型で返す。ノードが保持していない{\tt key}を渡した場合エラーを返す。} \\ \hline
-{\tt String getString(String key)} &ノードが持つ値から、属性名 {\tt key} とペアの属性値を{\tt String}型で返す。ノードが保持していない{\tt key}を渡した場合エラーを返す。 \\ \hline
+{\small{\tt String getString(String key)}} &{\small ノードが持つ値から、属性名 {\tt key} とペアの属性値を{\tt String}型で返す。ノードが保持していない{\tt key}を渡した場合エラーを返す。} \\ \hline
 \end{tabular}
 \label{Attribute}
 \end{center}
 \end{table}
 Attribute attribute = child.getAttribute();
 String value = attribute.getString("name");
 \end{lstlisting}
 ソースコード\ref{getAttributeCode}の説明を行う。
-1行目から2行目で
+1行目で Jungle から木を取得し、
+2行目で、取得した木のルートノードを取得している。
+3 - 7行目でルートノードの1番目の子ノードを取得し、
+8 - 9行目で、ルートの1番目の子ノードから、属性名 "name" とペアの属性値を取得している。
 \section{木の編集API}
 Jungleの木の編集は{\tt Default Jungle Tree Editor}クラスを用いて行われる。
 {\tt Default Jungle Tree Editor}クラスは、木に対する編集を行うAPIが定義されているJungle Tree Editorインターフェースを実装している。
 Default Jungle Tree Editorは、Jungle Tree から、{\tt getTreeEditor()}を用いて取得する。
 表\ref{editor}にJungle Tree Editorインターフェースに定義されているAPIを記述する。
 また、表\ref{editor}に記述しているAPIは全て、{\tt Either<Error,JungleTreeEditor>} を返す。
-\newpage
 \begin{table}[htb]
 \begin{center}
 \caption{Editorに実装されているAPI}
 \begin{tabular*}{\textwidth}{|p{15em}|p{22em}|}         \hline
 {\small\tt addNewChildAt( NodePath path,  int pos)} &
-{\tt path}で指定したノードの{\tt pos}番目の子の後にノードを追加する。\\ \hline
+{\small\tt path}で指定したノードの{\tt pos}番目の子の後にノードを追加する。\\ \hline
 {\small\tt deleteChildAt( NodePath path,int pos)}      &
-{\tt path}で指定したノードの{\tt pos}番目の子ノードを削除する。 \\ \hline
+{\small\tt path}で指定したノードの{\tt pos}番目の子ノードを削除する。 \\ \hline
 {\small\tt putAttribute( NodePath path,String key,ByteBuffer value)} &
-{\tt path}で指定したノードに属性名 {\tt key} 属性値 {\tt value} のペアで値を挿入する。 \\ \hline
+{\small\tt path}で指定したノードに属性名 {\tt key} 属性値 {\tt value} のペアで値を挿入する。 \\ \hline
 {\small\tt deleteAttribute( NodePath path,String key)}&
-{\tt path}で指定したノードが持つ、属性名 {\tt key}とペアで保存されている属性値を削除する。\\ \hline
+{\small\tt path}で指定したノードが持つ、属性名 {\tt key}とペアで保存されている属性値を削除する。\\ \hline
 {\small\tt moveChild( NodePath path,int num,String move)} &
-{\tt path}で指定したノードの{\tt num}番目の子供を{\tt move}の方向に移動させる。 \\ \hline %あとで直す
+{\small\tt path}で指定したノードの{\tt num}番目の子供を{\tt move}の方向に移動させる。 \\ \hline %あとで直す
 {\small\tt pushPop()} &
 ルートノードの上に新しいルートノードを追加する。線形の木を作る際に使用することで木の変更の手間をO(n)からO(1)にできる。\\ \hline
 {\small\tt success()}  &
 木へ行った変更をコミットする。自分が編集を行っていた間に、他のJungleTreeEditorクラスによって木が更新されていた場合、コミットは失敗する。 \\ \hline
 \end{tabular*}
 \end{center}
 \end{table}
-編集後に返される{\tt JungleTreeEditor}クラスは、編集後の木構造を保持しているため、編集前の木構造を保持している{\tt JungleTreeEditor}クラスとは別のオブジェクトである。
+編集後に返される{\tt Default Jungle Tree Editor}クラスは、編集後の木構造を保持しているため、編集前の木構造を保持している{\tt Default Jungle Tree Editor}クラスとは別のオブジェクトである。
-編集を行った後は、関数{\tt editor.success()}で今までの編集をコミットすることができる。他の{\tt JungleTreeEditor}クラスによって木が更新されていた場合はコミットは失敗し、{\tt success()}は{\tt Error}を返す。
+編集を行った後は、関数{\tt editor.success()}で今までの編集をコミットすることができる。他の{\tt Default Jungle Tree Editor}クラスによって木が更新されていた場合はコミットは失敗し、{\tt success()}は{\tt Error}を返す。
 その場合は、木の編集を最初からやり直す必要がある。
 以下に{\tt JungleTreeEditor}クラスを用いて、木の編集を行うサンプルコードを記述する。
-\newpage
 \begin{lstlisting}[frame=lrbt,numbers=left,label=editorCode]
 JungleTreeEditor editor = tree.getTreeEditor();
 DefaultNodePath editNodePath = new DefaultNodePath();
 Either<Error, JungleTreeEditor> either = editor.addNewChildAt(editNodePath, 0);
 return either.a();
 editor = either.b();
 editor.success();
 \end{lstlisting}
+1行目で、木から Editor を取得している。
+2行目で、編集を行うノードの Path を作成している。Default Node Path は、生成時はルートノードを指しているため、今回はルートノードに対する変更であることがわかる。
+3行目で、実際にルートノードに対して、子ノードの追加を行っている。
+4行目以降で、編集が成功したかどうかを {\tt Either }を使って確かめ、成功していた場合7行目で変更を木に Commit している。
+\begin{comment}
 \begin{enumerate}
 \item 関数{\tt tree.getEditor()}で編集を行う木から、{\tt JungleTreeEditor}クラスを取得する。
 \item 次に変更するノードの場所を示す、{\tt NodePath}クラスを作成する。
 \item 関数{\tt editor.addNewChildAt()}を用いて、変数{\tt path}で指定したノードの子供の0番目に子ノードを追加する。
 \item 返り値の変数{\tt either}が{\tt Error}クラスを保持していないか(編集に失敗していないか)を確認する。
 \item {\tt Error}クラスを保持していた場合{\tt Either.a()}でErrorを返す。
 \item 編集に成功していた場合、編集後木を持った、{\tt JungleTreeEditor}クラスを取得する。
 \item 取得した{\tt JungleTreeEditor}クラスを用いて木の変更をコミットする。
 \end{enumerate}
+\end{comment}
 また、木に対して行われた変更は、Logとして書き出される。
+\section{Commit}
+Jungle Tree Editor を用いて木に変更を加えた後は、Commit を行う必要がある。
+Commit は、前節で記述した Jungle Tree Editor が持つ関数 {\tt success()} を使用することで行われる。
+Commit を行うと、Jungle Tree Editor が保持している編集後の木構造のデータを持つ TreeContext を作成する。
+そして、編集前の木が持つ TreeContext と 新しく作った TreeContext を置き換えることで Commit は完了する。
+TreeContext の置き換えは、編集を行っている他の Thread と競合した際に、木の整合性を保つために以下の手順で行われる。
+\begin{enumerate}
+\item 新しく作った TreeContext が持つ、1つ前のバージョンの TreeContext と、編集前の木構造の TreeContext を比較する。
+\item 一致しなかった場合、他のが Thread が Commit をすでに行っているため、失敗する(競合に負けた)。
+\item 一致した場合、TreeContext を Atomic に入れ替える(競合に勝った)。
+\end{enumerate}
+競合に負けた場合は、新しい木に対してもう一度同じ変更を行う必要がある。
 これらのAPIにより、Jungleは木構造を格納、編集する機能を持っている。
 \section{Log}
 Jungle は、 Editor を用いて木に編集を加える際、使用した API に応じて対応する NodeOperation を作成する。
 NodeOperation は NodePath とペアで扱わなければならず、このペアを TreeOperation という。
 この TreeOperation の集まりを TreeOperationLog という。
 TreeOperationLogの仕様をソースコード\ref{src:treeoperationlog}に示す.
 \begin{lstlisting}[frame=lrbt,label=src:treeoperationlog,caption=TreeOperationLogの仕様,numbers=left]
 public interface TreeOperationLog extends Iterable<TreeOperation>
 {
 public TreeOperationLog add(NodePath _p,NodeOperation _op);
 public TreeOperationLog append(TreeOperationLog _log);
 public int length();
 }
 \end{lstlisting}
 \verb|Iterable<TreeOperation>|を継承しているためIteratorによりTreeOperationを取り出せるようになっている。
 addやappendメソッドを使ってTreeOperationを積み上げていくことができる。
 \section{検索API}
 これまでに紹介したAPIにより、Jungleは木構造を構築できるようになった。
-しかし、木に問い合わせを行う検索APIが実装されていなかったため、木の走査を行う{\tt Traverser}クラス内に、lambda式を用いて実装した。
+しかし、木に問い合わせを行う検索APIが実装されていなかったため、木の走査を行う{\tt Interface Traverser}クラス内に、lambda式を用いて実装した。
 以下に検索を行う関数{\tt find}の定義を記述する。
 \begin{lstlisting}[frame=lrbt,label=query,numbers=left]
 public Iterator<TreeNode> find(Query query, String key, String searchValue);
 \end{lstlisting}
-関数{\tt find}は、第一引数には、探索の条件を記述する関数{\tt boolean comdition(TreeNode)}を定義した{\tt Query}を。
+関数{\tt find}は、第一引数には、探索の条件を記述する関数{\tt boolean comdition(TreeNode)}を定義した{\tt Query}を、
 第二、第三引数には、Indexを用いた絞込に使用する{\tt String key、String value}を取り、条件に一致したノードの{\tt Iterator}を返す。
 {\tt 関数find}の使用例を以下に記す。
 \begin{lstlisting}[frame=lrbt,label=find,numbers=left]
 InterfaceTraverser traverser = tree.getTraverser(true);
 Iterator<TreeNode> resultNodeIterator = traverser.find((TreeNode node) -> {
-String personId = node.getAttributes().getString("name");
+String name = node.getAttributes().getString("name");
-if (personId == null) return false;
+if (name == null) return false;
-return personId.equals("kanagawa");
+return name.equals("kanagawa");
 }, "belong", "ryukyu");
 \end{lstlisting}
 上記コードについて解説する。
+1行目で検索対象の木から、検索に使用する {\tt Interface Traverser} を取得する。
+2行目で、検索を行う関数 {\tt find()} を使用する。
+今回は、Index を使って、属性名 {\tt "belong"} 属性値 {\tt "ryukyu"} を持つノード取得し、
+3 - 5行目で定義されたクエリに渡す。
+そして、クエリの中で属性名 {\tt "name"} 属性値 {\tt "kanagawa"} を持つノードかどうかを確かめる。
+結果として、属性名 {\tt "belong"} 属性値{\tt "ryukyu"}と、属性名 {\tt "name"} 属性値{\tt kanagawa}の2つのデータを持つノードの {\tt Iterator} が取得できる。
+検索の際に使用する Index の実装については次節に記述する。
+\begin{comment}
 \begin{enumerate}
 \item 木の走査を行う{\tt Traverser}クラスを取得する。
 \item Indexから{\tt find}の第2、第3引数である、属性名 {\tt belong}、属性値 {\tt ryukyu}の組のデータを持つノードを取得し、Queryに渡す(ノードの絞込を行う)。
 \item 引数のノードから関数{\tt getAttributes().getString("name")}で属性名 {\tt name}とペアになっている属性値を取得する。
 \item 属性値が{\tt null}だった場合、このノードには属性名が{\tt name}の組のデータは存在しないので、{\tt false}を返し次のノードの評価を行う。
 \item 属性値が{\tt null}でなかった場合、{\tt kanagawa}と一致するかどうかを調べ結果を返す。
 \end{enumerate}
+\end{comment}
-結果として、{\tt ryukyu}に所属する、名前が{\tt kanagawa}のデータを持つノードが取得できる。
-検索の際に使用する Index の実装については次節に記述する。
 \section{Index}
 Jungleは、非破壊的木構造というデータ構造上、過去の版の木構造を全て保持している。
 よって、全ての版に独立したIndexが必要となるため、前の版のIndexを破壊すること無く、Indexを更新する必要がある。
 既存のTreeMapでは、一度Indexの複製を行ない、その後更新する必要があったため、Indexの更新オーダーがO(n)となっていた。
 \begin{lstlisting}[frame=lrbt,label=find,numbers=left]
 Optional<TreeMap<String, List<TreeNode>>> indexOp = indexMap.get("name");
 if (!indexOp.isPresent())
 return new NulIterator<TreeNode>();
 TreeMap<String, List<TreeNode>> index = indexOp.get();
 Optional<List<TreeNode>> nodeListOp = index.get("kanagawa");
 if (!nodeListOp.isPresent())
 return new NulIterator<TreeNode>();
 return nodeListOp.get().iterator();
 \end{lstlisting}
+1 - 4行目で IndexMap から 属性名 "name" に対する値を持つ Index を取得している。
-\begin{enumerate}
+5 - 8行目で 取得した Index から、 属性名 "kanagawa" を持つノードの{ \tt Iterator}を取得している。
-\item {\tt indexMap}に、今回検索で使用する属性名 {\tt name}を使用して{\tt get("name")}を行う。すると属性名 {\tt "name"}に対応したIndexが、{\tt Optional}クラスで包まれて返ってくる。
-\item {\tt Optional}オブジェクトに対して、中身を保持しているか(属性名 {\tt name}に対応したIndexを木が持っているか)を調べる。
+\begin{comment}
+\begin{enumerate}
-\item 持っていなかった場合、空の{\tt Iterator}オブジェクトを返す。
+\item {\tt indexMap}に、今回検索で使用する属性名 {\tt name}を使用して{\tt get("name")}を行う。すると属性名 {\tt "name"}に対応したIndexが、{\tt Optional}クラスで包まれて返ってくる。
-\item 持っていた場合、{\tt Optional}オブジェクトからIndexを取得する。
+\item {\tt Optional}オブジェクトに対して、中身を保持しているか(属性名 {\tt name}に対応したIndexを木が持っているか)を調べる。
-\item 取得したIndexに、検索で使用する属性値{\tt "kanagawa"}で{\tt get()}を行う。すると、属性名 {\tt "name"} 属性値{\tt  "kanagawa"}の値を持つノードのリストが、{\tt Optional}クラスに包まれて返ってくる。
+\item 持っていなかった場合、空の{\tt Iterator}オブジェクトを返す。
-\item {\tt Optional}オブジェクトに対して中身を保持しているか(属性名 {\tt "name"} 属性値 {\tt "kanagawa"}を持つノードを木が持っているか)を調べる。
+\item 持っていた場合、{\tt Optional}オブジェクトからIndexを取得する。
-\item 持っていなかった場合、空の{\tt Iterator}オブジェクトを返す。
+\item 取得したIndexに、検索で使用する属性値{\tt "kanagawa"}で{\tt get()}を行う。すると、属性名 {\tt "name"} 属性値{\tt  "kanagawa"}の値を持つノードのリストが、{\tt Optional}クラスに包まれて返ってくる。
-\item 持っていた場合{\tt Optional}オブジェクトからノードリストの{\tt Iterator}を返す。
+\item {\tt Optional}オブジェクトに対して中身を保持しているか(属性名 {\tt "name"} 属性値 {\tt "kanagawa"}を持つノードを木が持っているか)を調べる。
-\end{enumerate}
+\item 持っていなかった場合、空の{\tt Iterator}オブジェクトを返す。
-JungleはこれらのAPIにより、木構造を格納、編集、検索する機能を持っている。
+\item 持っていた場合{\tt Optional}オブジェクトからノードリストの{\tt Iterator}を返す。
-\newpage
+\end{enumerate}
+\end{comment}
+JungleはこれらのAPIにより、木構造を格納、編集、検索する機能を持っている。
+\newpage

Mercurial > hg > Papers > 2017 > tatsuki-master

comparison jungle.tex @ 15:33d8077a5d45