/*
 * LOGICAL-PARADOX.ORG b-tree library
 * Copyright (C)2004,2005 satoshi akabane(akabane@logical-paradox.org)
 * $Id: Btree.java,v 1.3 2005/05/16 15:36:45 rampil Exp $
 */
package org.logical_paradox.common.btree;

import java.io.IOException;
import java.util.Properties;
import java.util.Stack;

import org.logical_paradox.common.thread.ReadWriteLock;

/**
 * B-tree構造を管理するクラス．<br>
 * このクラスを通して，永続ストレージ上に保管されているB-treeデータ構造
 * に対してアクセスする．<br>
 * このライブラリを利用するプログラムは，BtreeKeyとBtreeObjectを派生させて
 * 独自のデータ構造を実装する．<br>
 * 特にこだわりがない場合，BtreeおよびBtreePageクラスを拡張する必要はない．
 * @author satoshi akabane@logical-paradox.org
 * @version $Revision: 1.3 $
 */
public class Btree {
	private int _order = 0;								// 次数
	private String _filename = null;						// ファイル名
	private BtreeFile _file = null;						// ファイル
	private BtreePage[] _cachedPages = null;				// ページのキャッシュ用バッファ
	private final BtreeFactory _factory;					// Btreeの具体的な性質を指定するファクトリクラス
	private ReadWriteLock _lock = null;					// ReadersWriterロック

	/**
	 * コンストラクタ
	 */
	protected Btree(BtreeFactory factory) {
		_factory = factory;
		_lock = new ReadWriteLock();
	}

	/**
	 * Btreeクラスのインスタンスを生成して返す
	 *
	 * @param factory BtreeFactoryのインスタンス
	 * @return Btree Btreeクラスのインスタンス
	 * @exception BtreeException 何らかの原因でインスタンスの生成に失敗した
	 */
	public static Btree getInstance(BtreeFactory factory) {
		return new Btree(factory);
	}

	/**
	 * Btreeデータファイルを開く
	 *
	 * @param filename ファイル名
	 * @exception BtreeException
	 */
	public void open(String filename) throws BtreeException {
		open(filename, 0);
	}

	/**
	 * Btreeデータファイルを開く
	 *
	 * @param filename ファイル名
	 * @param cachesize キャッシュするページ数(0:キャッシュしない)
	 * @exception BtreeException
	 */
	public void open(String filename, int cachesize) throws BtreeException {
		Properties prop = _factory.getProperty();
		_filename = filename;
		_order = Integer.parseInt(prop.getProperty(BtreeFile.ORDER));
		_filename = filename;
		_cachedPages = new BtreePage[ cachesize ];

		// ファイルをランダムアクセス形式で開く
		try {
			_file = _factory.getFileHandle(filename);
			if(_file.length() > 0) {
				_file.reload();
			} else {
				// 初めて作成されたファイルの場合，ヘッダブロックを出力する
				_file.flush();
			}
		} catch(Exception fn) {
			throw new BtreeException(fn.getMessage());
		}
	}

	/**
	 * Btree操作のためのセッションを返す
	 * @return セッション
	 * @throws BtreeException
	 */
	public BtreeSession getSession() throws BtreeException {
		return new BtreeSession(this);
	}
	/**
	 * Btreeデータファイルを閉じる．
	 * 閉じる前にヘッダの更新を行なう
	 *
	 * @exception BtreeException 何らかの原因でクローズができなかった場合
	 */
	protected void close() throws BtreeException {
		try {
			_file.close();
		} catch(IOException ioe) {
			throw new BtreeException(ioe.getMessage());
		}
	}
	/**
	 * このB-tree構造に関連付けされているファイルが閉じているかどうかを返す
	 * 
	 * @return true:閉じている / false:開いている
	 */
	public boolean isClosed() {
		return _file == null || _file.isClosed();
	}
	/**
	 * 新しいキーを生成する
	 *
	 * @param o 引数オブジェクト
	 * @return BtreeKey 何も格納されていない空のキー
	 * @exception BtreeException 生成に失敗した場合
	 */
	protected BtreeKey newKey(Object o) throws BtreeException {
		return _factory.newKey(o);
	}

	/**
	 * データを挿入する
	 *
	 * @param key キー
	 * @param o オブジェクト
	 * @exception BtreeException
	 */
	protected void insert(BtreeKey key) throws BtreeException, BtreeManipulationException {
		// データファイルに対して書き込みロックをかける
		try {
			_lock.beginWrite();

			/*
			 * 指定されたキーについて挿入の可能なページを探す
		 	 */
			BtreePathTrace trace = findInsertablePage(_file.getRootPageNo(), key, new BtreePathTrace());
			BtreePage insertableTarget = trace.getFound();

			if(insertableTarget == null) {
				// 挿入可能なページが存在しない場合，新しいページを作成する
				insertableTarget = _file.newPage();
			}

			/*
			 * 挿入
			 */
			BtreePage.PromoResult promo = null;
			long rightChild = -1;
			long originalPageNo = -1;

			// 昇進が発生する間はループする
			while((promo = insertableTarget.insert(key,rightChild)) != null) {
				// 昇進の発生によって分割された，元のページ自体もコミットする必要がある
				// 分割によってキーが減っているから
				commit(insertableTarget);
	
				originalPageNo = insertableTarget.getPageNo();
				// 新しく作成された兄弟に対して，新しいページ番号を付与してコミットする
				promo._page.setPageNo(BtreePage.NEW_PAGE);
				commit(promo._page);

				// 昇進するキーに対して，右の子のページ番号を設定する
				key = promo._promoKey;
				rightChild = promo._page.getPageNo();
				insertableTarget = trace.pop();
				if(insertableTarget == null) {
					// ルートのページにおいて，昇進が発生した場合は新しいページを作成する
					// その際，ルートのページ番号を更新する
					insertableTarget = _file.newPage();
					insertableTarget.setChildNodeAt(0, originalPageNo);
					_file.replaceRootPageNo(insertableTarget.getPageNo());
				}
			}

			// コミットする必要がある
			if(insertableTarget != null) {
				commit(insertableTarget);
			}
		} catch(Exception ioe) {
			// 入出力例外は，BtreeExceptionに変換する
			ioe.printStackTrace();
			throw new BtreeException(ioe.getMessage());
		} finally {
			// ロックを解放する
			try {
				_lock.release();
			} catch(Exception e){}
		}
	}

	/**
	 * データを削除する
	 *
	 * @param key キー
	 */
	protected void delete(BtreeKey key) throws BtreeException {
	}

	/**
	 * データを更新する
	 *
	 * @param o オブジェクト
	 * @exception BtreeException
	 */
	protected void update(BtreeKey key) throws BtreeException {
	}

	/**
	 * データとキーのペアを取得する
	 *
	 * @param key キー
	 * @return BtreeResultSet 結果セット
	 * @exception BtreeException
	 */
	protected BtreeResultSet find(BtreeKey key) throws BtreeException {
		BtreeResultSet result = null;

		try {
			_lock.beginRead();
			return findRecursive(_file.getRootPageNo(), key);
			// ルートページから検索する
		} catch(BtreeException be) {
			be.printStackTrace();
			throw be;
		} catch(Exception e) {
			e.printStackTrace();
			throw new BtreeException(e.getMessage());
		} finally {
			try {
				_lock.release();
			} catch(Exception ee) {}
		}
	}

	//----- Btree下位サービスメソッド -----------------------------------------
	/**
	 * 指定されたページをディスクに書き出す
	 * @param bp 出力対象のページ
	 * @exception BtreeException 何か問題が発生した
	 */
	protected void commit(BtreePage bp) throws BtreeException {
		if(bp.getPageNo() == BtreePage.NEW_PAGE) {
			// 新しいページが申請された場合，ページ領域を作成して
			// 採番されたページ番号を取得する
			BtreePage newp = _file.newPage();
			bp.setPageNo(newp.getPageNo());
		}
		// ページ領域の更新処理
		_file.replacePage(bp);
	}
	/**
	 * 指定されたキーを探す
	 * キーは文字列表現に従って検索し，戻り値はバイト列から復元されたキーそのものである
	 * @param root 検索を開始するページ番号
	 * @param key 探すキー(文字列表現が正しければ不完全でも可)
	 * @return 検索された完全な状態のキー(null: みあたらなかった)
	 * @throws BtreeException 検索中に何らかの障害が発生した
	 */
	protected BtreeResultSet findRecursive(long root, BtreeKey key) throws BtreeException {
		// 検索開始ページ自体が存在しないのでパス
		if(root <= 0) {
			return null;
		}

		BtreePage btp = getPage(root);
		BtreeKey bk = btp.find(key.toString());
		if(bk != null) {
			// みつけた
			BtreeResultSet result = new BtreeResultSet();
			result.setKey(bk);
			return result;
		}

		// このページには存在しないようなので，下の階層を探す
		return findRecursive(btp.getChildPageNo(key), key);
	}
	/**
	 * 新しいキーを挿入することのできるページを探す．
	 * @param root 検索を開始するページ番号
	 * @param key キー
	 * @param pt パストレース
	 * @return BtreePathTrace パストレース
	 */
	protected BtreePathTrace findInsertablePage(long root, BtreeKey key, BtreePathTrace pt) throws BtreeException {
		// ページ番号が-1の場合は終了
		if(root <= 0) {
			return pt;
		}

		// 指定されたページを取得して，パストレースにページを追加する
		BtreePage btp = getPage(root);

		// 指定されたページに空きがあり，かつこのページに挿入されるべきかどうかを調べる
//		if(btp.keyCount() < btp.order() && btp.shouldBeContained(key) == true) {
		if(btp.shouldBeContained(key) == true) {
			// ここに挿入されるべきなので，決定して処理を返す
			pt.setFound(btp);
			return pt;
		} else {
			// 取得したページをパストレースに追加
			pt.push(btp);
			// このページの下の階層のページ番号を取得する
			long child = btp.getChildPageNo(key);
			// 更に下の階層を探す
			return findInsertablePage(child, key, pt);
		}
	}

	/**
	 * 指定されたページを返す．
	 * 指定されたページがキャッシュ内に存在した場合はそれを返す．<br>
	 *
	 * @param pageno ページ番号
	 * @return BtreePage ストレージから復元されたページオブジェクト(null:なかった)
	 * @exception BtreeException B-treeのデータ構造がおかしい場合に返る
	 */
	protected BtreePage getPage(long pageno) throws BtreeException {
		return getPage(pageno, false);
	}

	/**
	 * 指定されたページを返す．
	 * 指定されたページがキャッシュ内に存在した場合はそれを返す．<br>
	 * swapがtrueの場合，可能であればキャッシュの順番も入れ替える．<br>
	 * 浅い階層のデータがキャッシュに登録されるように，順番の入れ替えが発生する．
	 *
	 * @param pageno ページ番号
	 * @param swap true: キャッシュの入れ替えあり false: 入れ替えなし
	 * @return BtreePage ストレージから復元されたページオブジェクト(null:なかった)
	 * @exception BtreeException B-treeのデータ構造がおかしい場合に返る
	 */
	protected BtreePage getPage(long pageno, boolean swap) throws BtreeException {
		if(swap) {
		}
		return _file.getPage(pageno);
	}

	/**
	 * Btreeの検索パストレースを保管するクラス
	 * @author satoshi akabane
	 * @version 1.0
	 */
	protected class BtreePathTrace {
		private final Stack pathStack;			// 検索パス
		private BtreePage foundPage = null;		// 目的のページ

		/**
	 	 * コンストラクタ
		 */
		protected BtreePathTrace() {
			pathStack = new Stack();
		}
		/**
		 * 探索パスに対してページを追加する
		 * @param bp 追加するページ
		 */
		protected void push(BtreePage bp) {
			pathStack.push(bp);
		}
		/**
		 * 検索パスの最後から1つ取り出す
		 * @return BtreePage 取り出したページ
		 */
		protected BtreePage pop() {
			return pathStack.empty() == false ? (BtreePage)pathStack.pop() : null;
		}
		/**
		 * 探していたページを設定する
		 * @param bp ページ
		 */
		protected void setFound(BtreePage bp) {
			foundPage = bp;
		}
		/**
		 * 探していたページを返す
		 * @return BtreePage ページ(null:結局なかった)
		 */
		protected BtreePage getFound() {
			return foundPage;
		}
		/**
		 * スタックが空かどうかを返す
		 * @return boolean true: 空 / false: 何か入っている
		 */
		protected boolean isEmpty() {
			return pathStack.empty();
		}
		/**
		 * パストレースを完全に初期化する
		 */
		protected void clear() {
			synchronized(pathStack) {
				while(pathStack.empty() == false) {
					pathStack.pop();
				}
			}
		}
	}
}

// end of Btree.java
