\section{検索API}
Jungle上でのmaTrixの組織構造の表現はIdを用いた木の検索を用いて表現するため、Jungleに属性名:属性値の組で検索を行うAPIの実装を行った、

JungleのTreeに対する検索は、lambda式を用いてfind関数を実装した。
lambda式を使用することで、匿名クラスを使用した場合より簡潔にコードを記述できるようになった。
以下にfind関数の定義を記す。

\begin{verbatim}
 public Iterator<TreeNode> find(Query query, 
              String key, String searchValue);
 \end{verbatim}

find関数は引数にQuery、String key、String valueの3つの引数を取り、条件に一致したNodeのIteratorを返す。
第1引数には、探索の条件を記述する関数boolean comdition(TreeNode)を定義したInterfaceQueryを。
第2、第3引数の、String key、String valueはIndexの取得を行うために使用する。find関数の使用例を以下に記す。


findのサンプル%属性名 PersonId ,属性値 p:4の値を持ったノードを検索するfindのサンプル
\begin{verbatim}
InterfaceTraverser personTraverser 
= personTree.getTraverser(true);
Iterator<TreeNode> personIdpairIterator 
= personTraverser.find((TreeNode node) -> {
    String personId = 
    node.getAttributes().getString("Personid");
    if (personId == null)
      return false;
    if (personId.equals("p:4"))
      return true;
    return false;
}, "Personid", "p:4");
\end{verbatim}

上記コードのQuery内での処理について解説する。
\begin{enumerate}
\item 引数のノードからgetAttributes()

.getString("Personid")で属性名がPersonidの属性値を取得する。

\item 属性値がnullだった場合、このNodeには属性名がPersonidの組のデータは存在しないのでfalseを返し次のNodeの評価を行う。

\item 属性値がnullでなかった場合、p:4と一致するかどうかを調べ結果を返す。
\end{enumerate}


\section{Indexの実装}
Jungleのデータ検索は、木の全探索であるため計算量はO(n)である。
しかし、Indexを実装することでO(logN)で探索を行うことが可能になる。
Jungleは、過去の木のデータを全て保持しており、アクセスすることが可能であるため全てのversionでIndexを保持する必要がある。
よって、Indexを破壊すること無く更新する必要があったため、非破壊的木構造のTreeMapを新しく自作し使用した。
このTreeMapは、データの更新を行った際、前の版のTreeMapとデータを最大限共有した新しいTreeMapを作成する。
これにより、複数の版全てに対するIndexをサポートすることが可能になった。

以下にIndexの型を示す
\begin{verbatim}
TreeMap<String key,TreeMap<String attribute,
        List<TreeNode> node> index> indexList
\end{verbatim}

JungleのIndexはIndexList内に保持されている。
属性名でIndexListに検索を行うと、対応したIndexが取得できる。
その取得したIndexに属性名で検索を行うとノードのリストが返ってくる。

他にも、渡したノードの親を返すParentIndexの実装も行った。
ParentIndexを使用することで、木構造の親を取得する検索も行えるようになった。