\documentclass[a4j,12pt]{jreport}
\usepackage[dvipdfmx]{graphicx}
\usepackage{mythesis}
\usepackage{multirow}
\usepackage{ascmac} 
\usepackage{here}
\usepackage{url}
\usepackage{fancyhdr}
\usepackage{float}
\usepackage{listings, jlisting}
%% \input{dummy} %% font

\lstset{
    language=java, 
    tabsize=2, 
    frame=single, 
    basicstyle={\ttfamily\footnotesize},% 
    identifierstyle={\footnotesize},% 
    commentstyle={\footnotesize\itshape},% 
    keywordstyle={\footnotesize\bfseries},% 
    ndkeywordstyle={\footnotesize},% 
    stringstyle={\footnotesize\ttfamily}, 
    breaklines=true, 
    captionpos=b, 
    columns=[l]{fullflexible},% 
    xrightmargin=0zw,% 
    xleftmargin=1zw,% 
    aboveskip=1zw, 
    numberstyle={\scriptsize},% 
    stepnumber=1, 
    numbersep=0.5zw,% 
    lineskip=-0.5ex, 
    numbers=left 
}
\renewcommand{\lstlistingname}{Code}

\setlength{\itemsep}{-1zh}

\title{ゲームエンジンにおける木構造データベースJungleの提案}
%\title{Supporting NAT in Screen Sharing System TreeVNC}
\icon{
    \includegraphics[width=80mm,bb=0 0 595 642]{fig/ryukyu.pdf} %%元は 642じゃなくて842
}
\year{平成28年度 卒業論文}
\belongto{琉球大学工学部情報工学科}
\author{135768K 武田 和馬 \\ 指導教員 {河野 真治} }

%% TreeVNC のNATへの対応
%% マルチスクリーン TreeVNC
%% プリアンブルに記述
%% Figure 環境中で Table 環境の見出しを表示・カウンタの操作に必要
%%
\makeatletter
\newcommand{\figcaption}[1]{\def\@captype{figure}\caption{#1}}
\newcommand{\tblcaption}[1]{\def\@captype{table}\caption{#1}}
\makeatother
\setlength\abovecaptionskip{0pt}

\begin{document}

% タイトル
\maketitle
\baselineskip 17pt plus 1pt minus 1pt

\pagenumbering{roman}
\setcounter{page}{0}

\tableofcontents	% 目次
\listoffigures		% 図目次
\listoftables		% 表目次

%以下のように、章ごとに個別の tex ファイルを作成して、
% main.tex をコンパイルして確認する。
%章分けは個人で違うので下のフォーマットを参考にして下さい。

% はじめに

\chapter{研究目的}

プログラムからデータを分離して扱うデータベースには、プログラム中のデータ構造とRDBの表構造のズレによりインピーダンスミスマッチという問題がある。

データベースのレコードをプログラム中のオブジェクトとして扱えるORMapperやデータベース自体も、表に特化したKey Value Storeや、Json、XMLの不定形のデータ構造を格納するように機能拡張されている。

ORMapperではデータベースのレコードをプログラム中のオブジェクトとして扱うことができる。オブジェクトに対する操作を行うとORMapperがSQLを発行し、処理を行ってくれる。

しかしレコードをプログラム中のオブジェクトを対応させるORMapperの技術でインピーダンスミスマッチを解決することはできない。

JsonやXMLを扱えるデータベースでは通常スキームを必要としないため、特に設計を行わずデータを格納することができる。

しかし、不定形の構造の変更をトランザクションとして、Jsonの一括変更という形で処理されてしまっており、並列アプリケーションには向いていない。

当研究室ではデータの変更の際に過去の木構造を保存する非破壊木構造データベースであるJungleを提案している\cite{1}。

本研究ではJungleをUnityを用いたゲームで使用する方法を提案する。
データベースとしてJungle DBをC\#で再実装を行い、Unity向けに組み込みを行う。

\label{chap:introduction}
\pagenumbering{arabic}

%序論の目安としては1枚半ぐらい．
%英語発表者は，最終予稿の「はじめに」の英訳などを載せてもいいかも．

\chapter{Unityでのデータベースの取扱い}
\label{chap:concept}

\section{UnityとJungleの関係}

Unityは3Dゲームエンジンで、ゲームを構成する要素(Object)をC\#で制御する。
Objectは一つのゲームのシーン(一画面の状況)の中で木構造を持つ。
これをシーングラフと言う。
シーングラフをそのままJungleに格納するという手法が考えられる。

\section{Unityにおけるデータベース}

Unityでのデータベースとして考えられるものとしてはMySQL、SQlite3、PlayerPrefsが挙げられる。

PlayerPrefsとは、Unityに特化したバイナリ形式でKeyとValueのみで保存されるものである。セーブ機能に特化していてメモリ上にDBを展開するものではない。

\chapter{Jungle-Sharpの実装}

JavaとC\#はよく似た言語であり、移行はそれほど難しくない。
Jungleの中心部分である木構造とIndexを構成する赤黒木のコードはほぼ変更なく移行できた。
C\#ではインナークラスが使えないので明示的なクラスに変換する必要があった。

\section{AtomicRefarenceの実装}

Jungleの木の変更(commit)はCAS(Check and Set)を用いてatomicに行われる。競合している書き込み中に自分の書き込みが成功した場合に関数\verb+success()+が成功する。

JavaではAtomicRefarenceが標準であるがC\#にはなかったためAtomicRefarenceのClassを新たにつくった。

\begin{itembox}[l]{AtomicReplace}
\scriptsize{
\begin{verbatim}
// C#  
public bool CompareAndSet(T newValue, T prevValue) {
    T oldValue = value;
    return (oldValue 
        != Interlocked.CompareExchange 
                  (ref value, newValue, prevValue));
}

// Java
AtomicRefarence<T> atomic = new AtomicRefarence<T>();
atomic.compareAndSet(prevValue, newValue);

\end{verbatim}
}
\end{itembox}


\section{Listの実装}

木やリストをたどる時にJavaではIteratorを用いる。
Iteratorは次の値があるかを返すboolean hasNext()と、Tという型の次の値を取ってくるT next()を持つObjectである。
C\#では木やリストを辿りながらyeildで次の値を返す。
Javaでは以下のように実装されている。

\begin{itembox}[l]{List.java}
\scriptsize{
\begin{verbatim}
public Iterator<T> iterator() {
  return new Iterator<T>() {
    Node<T> currentNode = head.getNext();

    @Override
    public boolean hasNext() {
      return currentNode.getAttribute() 
                                    != null;
    }

    @Override
    public T next() {
      T attribute 
            = currentNode.getAttribute();
      currentNode 
            = currentNode.getNext();
      return attribute;
    }
  };
}
\end{verbatim}
}
\end{itembox}

C\#ではIEnumeratorがあるのでそれを利用した。
ListのforeachではIteratorを呼び出すために、一つずつ要素を返す必要がある。
yield returnステートメントを利用することで位置が保持され、次に呼ばれた際に続きから値の取り出しが可能になる。
以下にその実装例を示す。

\begin{itembox}[l]{List.cs}
\scriptsize{
\begin{verbatim}
public IEnumerator<T> iterator() {
  Node<T> currentNode = head.getNext();
  while (currentNode.getAttribute() != null) {
    yield return (T)currentNode.getAttribute();
    currentNode = currentNode.getNext ();
  }
}
\end{verbatim}
}
\end{itembox}

\chapter{Jungle Database の概念}

Jungleは名前付きの複数の木の集合からなり、木は複数のノードの集合で出来ている。
ノードは自身の子のリストと属性名と属性値の組でデータを持つ。
これはデータベースのレコードに相当する。
通常のレコードと異なるのは、ノードに子どもとなる複数のノードがつくところである。

Jungleは、データの変更を一度生成した木を上書きせず、ルートから編集を行うノードまでのコピーを行い、新しく木構造を構築し、そのルートをアトミックに入れ替える{図\ref{nonDestractTreeEdit}}。
これを非破壊的木構造と呼ぶ。非破壊木構造は新しい木を構築している時にも、現在の木を安全に読み出せるという大きな特徴がある。
しかし、書き込みの手間は大きくなる。

\begin{figure}[h]
\begin{center}
\includegraphics[height = 2.5cm , bb=0 0 511 188]{images/nonDestractTreeEdit.pdf}
\caption{非破壊的木構造の木の編集}
\label{nonDestractTreeEdit}
\end{center}
\end{figure}

\section{Jungle Database の構造}

非破壊木構造を採用しているJungleでは、木の変更の手間はO(1)からO(n)となり得る。つまりアプリケーションに合わせて木を設計しない限り充分な性能を出すことは出来ない。逆に木の設計を行えば高速な処理が可能である。

Jungleはオンメモリで使用することを考えており、一度木のルートを取得すれば、その上で木構造として自由にアクセスしてもよい。

Jungleはcommit logを持ち、それを他のノードやディスクに転送することにより、分散構成と持続性を実現する。

\section{JungleDatabaseのAPI}

\subsection{Jungleの木}

Jungleは複数の木の名前を利用し、管理しており、名前により生成、編集を行う。
以下にJungleクラスが提供している木の生成、管理を行うAPI(表\ref{jungleTree})に記述する。

\begin{table}[htb]
\begin{center}
\caption{Jungleに実装されているAPI}
\begin{tabular}{|p{10em}|p{12em}|}        \hline
{\tt JungleTree  createNewTree(string treeName) } & Jungleに新しく木を生成する。木の名前が重複した場合、生成に失敗しnullを返す。     \\ \hline
{\tt JungleTree getTreeByName(string treeName)}   & JungleからtreeNameと名前が一致するtreeを取得する。名前が一致するTreeがない場合取得は失敗しnullを返す       \\ \hline
\end{tabular}
\label{jungleTree}
\end{center}
\end{table}

\subsection{TreeNode}

Jungleが保有する木は、複数のノードの集合で出来ている。
ノードは、自身の子のList、属性名と属性値の組のデータを持つ。
ノードに対するアクセスは表\ref{treeNodeAPI}に記述されているAPIを用いて行う。

\begin{table}[htb]
\begin{center}
\caption{TreeNodeに実装されているAPI}
\begin{tabular}{|p{8em}|p{14em}|}                                  \hline
{\tt Children getChildren()} & ノードの子供を扱うChildrenオブジェクトを返す。\\ \hline
{\tt Attribute getAttribute()} &ノードが保持しているデータを扱うAttribteオブジェクトを返す。    \\ \hline
\end{tabular}
\label{treeNodeAPI}
\end{center}
\end{table}

\subsection{Either}

jungleでは例外処理を投げる時にEitherクラスを用いて行う。返って来たEitherのオブジェクトに対して、{\tt isA() }で{\tt Error}かどうかをチェックする。
{\tt Error}でない場合は{\tt b()}で対象のオブジェクトを取り出す事ができる。

以下にルートノードの2番目の子どもを取ってくるのEitherのサンプルコードを記述する。

\begin{lstlisting}[frame=lrbt,numbers=left,label=getAttributeCode]
Either<Error,TreeNode> either = children.at(2);
if (either.isA()) 
    return either.a();
TreeNode child = either.b();
\end{lstlisting}

\subsection{ChildrenとAttribute}

Childrenクラスへのアクセスは表\ref{Children}に記述されているAPIを、Attributeクラスへアクセスは表\ref{Attribute}に記述されているAPIを用いて行う。

\begin{table}[htb]
\begin{center}
\caption{Childrenに実装されているAPI}
\begin{tabular}{|p{8em}|p{14em}|}                                  \hline
{\tt int size()}  &  子供の数を返す。\\ \hline
{\tt <Either Error,TreeNode> at(int num)} &ノードが持つ子供の中から、 変数{\tt num}で指定された位置にある子ノードを返す。   \\ \hline
\end{tabular}
\label{Children}
\end{center}
\end{table}

\begin{table}[htb]
\begin{center}
\caption{Attributeに実装されているAPI}
\begin{tabular}{|p{10em}|p{12em}|} \hline
{\tt byte[] get(string key)}   &ノードが持つ値から、属性名 {\tt key}とペアの属性値を{\tt byte array}型で返す。 \\ \hline
{\tt string getString(string key)} &ノードが持つ値から、属性名 {\tt key} とペアの属性値を{\tt string}型で返す。 \\ \hline
\end{tabular}
\label{Attribute}
\end{center}
\end{table}

\subsection{NodePath}

Jungleでは、木のノードの位置を{\tt NodePath}クラスを使って表す。
{\tt NodePath}クラスはルートノードからスタートし、対象のノードまでの経路を、数字を用いて指し示すことで対象のノードの場所を表す。また、ルートノードは例外として-1と表記される。
{\tt NodePath}クラスが{\tt < -1,1,2,3>} を表している際の例を図\ref{NodePath}に記す。
\begin{figure}[h]
\begin{center}
\includegraphics[height = 6cm , bb=0 0 568 455]{images/nodePath.pdf}
\caption{NodePath}
\label{NodePath}
\end{center}
\end{figure}

\subsection{木の編集}

Jungleの木の編集は{\tt JungleTreeEditor}クラスを用いて行われる。
{\tt JungleTreeEditor}クラスには編集を行うために、表\ref{editor}に記述されているAPIを用いて行う。

\begin{table}[htb]
\begin{center}
\caption{Editorに実装されているAPI}
\begin{tabular}{|p{8em}|p{14em}|}        \hline
{\tt Either<Error, JungleTreeEditor> addNewChildAt( NodePath path,  int pos)} &
変数{\tt path}で指定した場所にある、ノードの子供の変数{\tt pos}で指定した位置子ノードを追加する\\ \hline
{\tt Either<Error, JungleTreeEditor> deleteChildAt( NodePath path,int pos)}      &
変数{\tt path}で指定した場所にある、ノードの子供の変数{\tt pos}で指定した位置の子ノードを削除する。 \\ \hline
{\tt Either<Error, JungleTreeEditor> putAttribute( NodePath path,String key,ByteBuffer value)} &
変数{\tt path}で指定した場所にあるノードに、属性名 変数{\tt key} 属性値 変数{\tt value} のペアで値を挿入する。 \\ \hline
{\tt Either< Error, JungleTreeEditor> deleteAttribute( NodePath path,String key)}&
変数{\tt path}で指定した場所にあるノードが持つ、属性名 変数{\tt key}とペアで保存されているデータを削除する。\\ \hline
{\tt Either<Error, JungleTreeEditor> commit()}  &
木へ行った変更をコミットする。自分が編集を行っていた間に、他のJungleTreeEditorクラスによって木が更新されていた場合、コミットは失敗する。 \\ \hline
\end{tabular}
\label{editor}
\end{center}
\end{table}

編集を行った後は、関数{\tt editor.commit()}で今までの編集をコミットすることができる。他の{\tt JungleTreeEditor}クラスによって木が更新されていた場合はコミットは失敗し、{\tt commit()}は{\tt Error}を返す。
その場合は、木の編集を最初からやり直す必要がある。

\chapter{Unityで実装したアプリケーション}

本論文ではC\#で再実装を行ったJungleをUnityで作られたゲームの上に構築する。
例題のゲームとしては図\ref{craft}のマインクラフトの簡易版を作成する。

\begin{figure}[h]
\begin{center}
\includegraphics[height = 6cm , bb=0 0 568 455]{images/craft.png}
\caption{craft}
\label{craft}
\end{center}
\end{figure}

\section{データ設計}

\chapter{ベンチマーク}

\section{Javaとの比較}

\section{他のデータベースとの比較}

% 今後の課題

\chapter{結論}
\section{まとめ}



\section{今後の課題}

ネットワークゲームの課題はデータの偽装、つまりチートである。今後ネットワークとして対応させるにはそこを考える必要がある。

%\section{Alice での実装}

% 参考文献
\def\line{−\hspace*{-.7zw}−}
\nocite{*}
\bibliographystyle{junsrt}
\bibliography{reference}


\chapter*{謝辞}
\thispagestyle{empty}

%基本的な内容は以下の通り．参考にしてみて下さい．
%厳密な決まりは無いので，個々人の文体でも構わない．
%GISゼミや英語ゼミに参加した人はその分も入れておく．
%順番は重要なので気を付けるように．(提出前に周りの人に確認してもらう．)

\hspace{1zw}本研究の遂行，また本論文の作成にあたり、御多忙にも関わらず終始懇切なる御指導と御教授を賜わりました河野真治准教授に深く感謝致します。

数々の貴重な御助言と細かな御配慮を戴いた金川 竜己さん、並びに並列信頼研究室の皆様に深く感謝致します。

最後に、有意義な時間を共に過ごした情報工学科の学友、並びに物心両面で支えてくれた両親に深く感謝致します。

\begin{flushright}
    2017年 3月 \\ 武田和馬
\end{flushright}

% 付録

\end{document}