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

import java.io.IOException;
import java.nio.ByteBuffer;
import java.nio.ByteOrder;

/**
 * B-treeのページ1つ分を管理する．<br>
 * 1ページには複数のキーが含まれる．<br>
 * このクラスはパッケージ外から直接呼び出してインスタンスを作成することはできない．<br>
 * ページを生成するためには，BtreeクラスのnewPage()を使用する．<br>
 * @author satoshi akabane@logical-paradox.org
 * @version $Revision: 1.3 $
 */
public class BtreePage {
	public static final long NEW_PAGE = -1;				// 新しいページ番号を自動的に割り振る場合はこれを指定

	private final int _order;							// 次数
	private long _pageno;									// ページ番号
	private BtreeKey[] _keys;								// キー
	private long[] _children;								// 子ノードへのリンク(ページ番号)
	private int _keyCount;								// 格納されているキーの数

	private final BtreeKey[] _tempForPromoKey;			// 昇進処理などで使用するテンポラリ領域(キー)
	private final long[] _tempForPromoPtr;				// 昇進処理などで使用するテンポラリ領域(ノード関係)
	private final BtreeFactory _factory;					// Btreeファクトリ

	private boolean enabled = true;						// このページが有効かどうか(true: 有効 / false:無効)

	/**
	 * コンストラクタ<br>
	 * BtreePage内部から呼び出されることを想定しており，キーの配列や子ノードへのリンクも同時にコピーできる．<br>
	 * 指定されたキーの配列のサイズ = 格納されているキーの個数してカウントされる
	 *
	 * @param factory ファクトリ
	 * @param pageno ページ番号
	 * @param keys キー
	 * @param children 子ノードへのリンク
	 */
	protected BtreePage(BtreeFactory factory, long pageno, BtreeKey[] keys, long[] children) throws BtreeException {
		_factory = factory;
		int order = Integer.parseInt(factory.getProperty().getProperty(BtreeFile.ORDER));

		if(order <= 0 || pageno < 0) {
			throw new BtreeException("次数またはページ番号が不正です");
		}

		_order = order;
		_pageno = pageno;
		_keys = new BtreeKey[ order ];
		_children = new long[ order +1 ];			// 子ノードへのリンクはキーの数+1個作成する
		_keyCount = 0;
		init();

		_tempForPromoKey = new BtreeKey[order+1];
		_tempForPromoPtr = new long[order+1+1];

		// 引数で指定されたキーとリンクのコピー
		System.arraycopy(keys, 0, _keys, 0, keys.length);
		System.arraycopy(children, 0, _children, 0, children.length);
		_keyCount = keys.length;				// キーカウントの再設定

		cleanTemp();
	}

	/**
 	 * コンストラクタ<br>
	 * ※パッケージ外から直接呼び出すことはできない<br>
	 *
	 * @param factory ファクトリ
	 * @param pageno ページ番号
 	 */
	BtreePage(BtreeFactory factory, long pageno) throws BtreeException {
		_factory = factory;
		int order = Integer.parseInt(factory.getProperty().getProperty(BtreeFile.ORDER));
		if(order <= 0 || pageno < 0) {
			throw new BtreeException("次数またはページ番号が不正です");
		}

		_order = order;
		_pageno = pageno;
		_keys = new BtreeKey[ order ];
		_children = new long[ order +1 ];			// 子ノードへのリンクはキーの数+1個作成する
		_keyCount = 0;

		_tempForPromoKey = new BtreeKey[order+1];
		_tempForPromoPtr = new long[order+1+1];

		init();
		cleanTemp();
	}

	/**
	 * コンストラクタ<br>
	 * 指定されたバイト列からページ全体を復元するタイプ
	 *
	 * @param factory ファクトリ
	 * @param pageno ページ番号
	 * @param page ページのバイト列
	 * @exception BtreeException 指定されたバイト列からページが復元できなかった場合
	 */
	BtreePage(BtreeFactory factory, long pageno, byte[] page) throws BtreeException {
		_factory = factory;
		int order = Integer.parseInt(factory.getProperty().getProperty(BtreeFile.ORDER));
		if(order <= 0 || pageno < 0) {
			throw new BtreeException("次数またはページ番号が不正です");
		}
		if(page == null || page.length == 0) {
			throw new BtreeException("復元するページのバイト列が指定されていないか，バイト列が空です");
		}

		_order = order;
		_pageno = pageno;
		_keys = new BtreeKey[ order ];
		_children = new long[ order +1 ];			// 子ノードへのリンクはキーの数+1個作成する
		_keyCount = 0;

		_tempForPromoKey = new BtreeKey[order+1];
		_tempForPromoPtr = new long[order+1+1];

		init();
		cleanTemp();

		// 指定されたバイト列からページの内容を復元する
		byteStreamToBtreePage(page, Integer.parseInt(factory.getProperty().getProperty(BtreeFile.KEYSIZE)));
	}

	/**
	 * このページのページ番号を返す
	 *
	 * @return long ページ番号
	 */
	public long getPageNo() {
		return _pageno;
	}
	/**
	 * このページのページ番号を再設定する
	 * 
	 * @param pn ページ番号(NEW_PAGE: 新しいページ番号を自動的に割り振る)
	 */
	public void setPageNo(long pn) {
		_pageno = pn;
	}
	/**
	 * 格納されているキーの数を返す
	 *
	 * @return int キーの数(< _order)
	 */
	public int keyCount() {
		return _keyCount;
	}

	/**
	 * このページの次数を返す
	 *
	 * @return int 次数
	 */
	public int order() {
		return _order;
	}

	/**
	 * 子ノードに対するリンク数を返す
	 *
	 * @return int リンク数(次数+1)
	 */
	public int children() {
		return _children.length;
	}
	/**
	 * 格納されているキー全てを返す
	 * @return キーの配列
	 */
	public synchronized BtreeKey[] getKeys() {
		BtreeKey[] bkeys = new BtreeKey[_keyCount];
		System.arraycopy(_keys, 0, bkeys, 0, _keyCount);

		return bkeys;
	}
	/**
	 * 新しいキーを挿入する．<br>
	 * 新しいキーが既にページに格納されている場合，BtreeManipulation
	 * Exceptionが発生する．<br>
	 * 新しいキーを挿入しようとしてI/Oエラーが発生した場合，IOExceptionが発生
	 * する．<br>
	 * それ以外の場合必ずキーは挿入できる．ただし，挿入によって分割と昇進が発
	 * 生する場合，昇進対象のキーが返る．ツリー構造に変化が発生しない場合は
	 * nullを返す．
	 *
	 * @param ikey 挿入するキー
	 * @param rchild 挿入するキーの右のノード(ページ番号)
	 * @return PromoResult 発生した分割と昇進の情報(null:分割と昇進が発生しなかった)
	 * @exception BtreeManipulationException 既にあるキーを挿入しようとした
	 * @exception IOException 挿入時に何らかのI/Oエラーが発生した
	 */
	public synchronized PromoResult insert(BtreeKey ikey, long rchild) throws BtreeException, BtreeManipulationException, IOException {
		if(ikey == null) {
			throw new BtreeManipulationException("キーがNULLです");
//		} else if(shouldBeContained(ikey) == false) {
//			shouldBeContained(ikey);
//			throw new BtreeManipulationException("指定されたキー:" + ikey + " は，このページに格納されるべきではありません");
		}

		cleanTemp();

		/*
		 * 現在設定されているキーを確認しつつ，昇進処理用のテンポラリへコピーする
		 */
		int pkey = 0;		// マスタ
		int ptmp = 0;		// 作業領域
		boolean isCopied = false;
		boolean isReplaced = false;

		_tempForPromoPtr[0] = _children[0];						// 一番左の子がコピーされないアルゴリズムの関係上必要な措置
		int cnt = 0;
		while(pkey  < _keyCount) {
			if(_keys[pkey].equals(ikey) == true) {
				// 同じキーがあった場合，上書き更新処理
				_keys[pkey] = ikey;
				isCopied = true;
				isReplaced = true;
//				// 同じキーが既に格納されている場合はエラー
//				throw new BtreeManipulationException("キー:" + ikey + " は，既に格納されています");
			} else if(isCopied == false && ikey.isLessThan(_keys[pkey]) == true) {
				// マスタのキーより挿入予定のキーのほうが小さい場合，作業領域へ挿入予定のキーを入れる
				_tempForPromoKey[ptmp++] = ikey;
				_tempForPromoPtr[ptmp] = rchild;				// キーの右のノードをコピーするので，ptmpはこれでよし
				isCopied = true;
			}

			// 作業領域へコピー
			_tempForPromoKey[ptmp++] = _keys[pkey++];
			_tempForPromoPtr[ptmp] = _children[pkey];			// キーの右のノードをコピーするので，ptmp/pkeyはこれでよし
		}
		if(isCopied == false) {
			// ↑のループでテンポラリ領域に引数のキーがコピーされていない場合
			_tempForPromoKey[ptmp++] = ikey;
			_tempForPromoPtr[ptmp] = rchild;					// キーの右のノードをコピーするので，ptmpはこれでよし
		}
		if(isReplaced == true) {
			// 単なるキーの置換の場合，ツリー構造に変更が発生しないので，そのまま戻す
			return null;
		}
		/*
		 * キーが全て埋まっている場合，挿入が発生すると必ず1つは昇進が発生する
		 * 昇進の場合，必ず真中のキーが昇進対象となる
		 */
		if(_keyCount < _order) {
			// 次数分のキーがまだ埋まっていない場合，作業用の配列からマスタへコピーする
			// なお，キーが一杯でない場合は昇進が発生しないので，nullを返す
			System.arraycopy(_tempForPromoKey, 0, _keys, 0, _keyCount+1);
			System.arraycopy(_tempForPromoPtr, 0, _children, 0, _keyCount+2);
			if(isReplaced == false) {
				_keyCount++;
			}
			return null;
		} else {
			// 昇進するので昇進キーを返す
			// ページの内容はそのままにしておく．
			// 昇進対象のキーと，キーの位置を求める
			int promoKeyIdx = _order / 2 + _order % 2;
			BtreeKey promoKey = _tempForPromoKey[promoKeyIdx];

			/*
			 * 兄弟のページを作成する
			 */
			BtreeKey[] brotherKeys = new BtreeKey[(_tempForPromoKey.length -1) - promoKeyIdx];
			long[] brotherChildren = new long[brotherKeys.length +1];

			System.arraycopy(_tempForPromoKey, promoKeyIdx+1, brotherKeys, 0, brotherKeys.length);
			System.arraycopy(_tempForPromoPtr, promoKeyIdx+1, brotherChildren, 0, brotherKeys.length+1);
			BtreePage brother = new BtreePage(_factory, _pageno +1, brotherKeys, brotherChildren);

			// 分割して兄弟のページへ移動したキーとポインタを消去する
			_keys = new BtreeKey[_order];
			_children = new long[_order+1];
			System.arraycopy(_tempForPromoKey, 0, _keys, 0, promoKeyIdx);
			System.arraycopy(_tempForPromoPtr, 0, _children, 0, promoKeyIdx+1);
			_keyCount = promoKeyIdx;

			// 分割と昇進の情報を，呼び出し元へ返す
			// BtreePage内では，データストアに相当する処理を行なわないため，呼び出し元で処理させる
			PromoResult pr = new PromoResult(promoKey, brother);
			return pr;
		}
	}

	/**
	 * 指定された文字列表現に対応するキーを返す．<br>
	 * 指定された文字列表現に対応するキーが，このページに存在すれば
	 * キーオブジェクトを，存在しない場合はnullを返す
	 *
	 * @param key 検索するキーの文字列表現
	 * @return BtreeKey 該当するキー(存在しない場合はnull)
	 */
	public BtreeKey find(String key) {
		for(int i = 0; i < _keyCount; i++) {
			if(key.equals(_keys[i].toString())) {
				return _keys[i];
			}
		}
		return null;
	}

	/**
	 * 指定されたキーがこのページに含まれるべきかどうかを返す．
	 * 実際に挿入できるかどうかを返すわけではないことに注意
	 *
	 * @param key キー
	 * @return boolean true: 含まれるべきである / false: 違うページに挿入する必要がある
	 */
	public boolean shouldBeContained(BtreeKey key) {
		return getChildPageNo(key) < 0;
	}
	/**
	 * 指定された位置のノード番号を更新する
	 * @param idx インデックス
	 * @param pageno ページ番号
	 */
	void setChildNodeAt(int idx, long pageno) {
		_children[idx] = pageno;
	}
	public long getChildNodeAt(int idx) {
		return _children[idx];
	}
	/**
	 * 指定されたキーの左の子を設定する
	 * @param key キー
	 * @param pageno ページ番号
	 */
	public void setLeftChildOf(BtreeKey key, long pageno) {
		for(int i = 0; i < _keyCount; i++) {
			if(key.equals(_keys[i].toString())) {
				_children[i] = pageno;
				return;
			}
		}
	}
	/**
	 * 指定されたキーの右の子を設定する
	 * @param key キー
	 * @param pageno ページ番号
	 */
	public void setRightChildOf(BtreeKey key, long pageno) {
		for(int i = 0; i < _keyCount; i++) {
			if(key.equals(_keys[i].toString())) {
				_children[i+1] = pageno;
				return;
			}
		}
	}
	/**
	 * 指定されたキーが挿入されるべき，子階層のページ番号を取得する
	 * @param key キー
	 * @return ページ番号 -1:子階層がない 0以上: ページ番号
	 * @throws BtreeException 処理に失敗した
	 */
	public long getChildPageNo(BtreeKey key) {
		if(_keyCount == 0) {
			// 何もキーが格納されていない場合，格納できるはずなのでtrue
			return -2;
		}
		BtreeKey theGreaterKey = null;
		int offsetOfTheGreaterKey = -1;

		for(int i = 0; i < _keyCount; i++) {
			if(key.equals(_keys[i])) {
				// 全く同じキーがあったので，これをリプレースする
				return -2;
			} else if(key.isLessThan(_keys[i])) {
				// 指定されたキーより大きいものを発見したので中断する
				offsetOfTheGreaterKey = i;
				break;
			}
		}
		if(offsetOfTheGreaterKey == -1) {
			// 指定されたキーより大きいものがなかった場合
			// このページの一番右の子のページ番号がある場合はそれ．
			// 一番右が-1の場合(下の階層が存在しない場合)は，-2
			if(getChildNodeAt(_keyCount) > 0) {
				return getChildNodeAt(_keyCount);
			} else {
				return -2;
			}
		} else {
			// 何か自分より大きいキーを発見した場合
			// 自分より大きいキーの左の子のページ番号が指定されている場合(=下の階層がある場合)
			// 指定キーは下の階層に格納されるべき
			if(_children[offsetOfTheGreaterKey] >= 0) {
				return _children[offsetOfTheGreaterKey];
			} else {
				// 挿入されるべき位置に対して，下の階層がなかった
				return -1;
			}
		}
	}
	/**
	 * 指定されたキーがこのページに含まれているかどうかを返す．<br>
	 * 含まれている場合はtrue，含まれていない場合はfalseを返す
	 *
	 * @param key 確認するキー
	 * @return boolean true: 存在する / false: 存在しない
	 */
	public boolean isContained(BtreeKey key) {
		return find(key.toString()) != null;
	}

	/**
	 * 指定されたキーを削除する．<br>
	 * 削除処理が無事に成功した場合はtrue，過疎が発生した場合はfalse<br>
	 * を返す．<br>
	 * 削除処理中にI/Oエラーが発生した場合，IOExceptionが発生する．
	 *
	 * @param key 削除するキー
	 * @return boolean true: 成功 / false: 過疎が発生した
	 * @exception IOException 削除処理中にI/Oエラーが発生した場合
	 */
	public boolean delete(String key) throws IOException {
		return true;
	}

	/**
	 * 指定されたキーを削除する．<br>
	 * 削除処理が無事に成功した場合はtrue，過疎が発生した場合はfalse<br>
	 * を返す．<br>
	 * 削除処理中にI/Oエラーが発生した場合，IOExceptionが発生する．
	 *
	 * @param key 削除するキー
	 * @return boolean true: 成功 / false: 過疎が発生した
	 * @exception IOException 削除処理中にI/Oエラーが発生した場合
	 */
	public boolean delete(BtreeKey key) throws IOException {
		return delete(key.toString());
	}

	/**
	 * Btreeの内容を初期化する
	 */
	protected void init() {
		for(int i = 0; i < _children.length; i++) {
			_children[i] = -1L;
		}
	}

	/**
	 * 昇進処理用のテンポラリ領域をクリアする
	 */
	protected void cleanTemp() {
		for(int i = 0; i < _tempForPromoKey.length; i++) {
			_tempForPromoKey[i] = null;
			_tempForPromoPtr[i] = -1L;
		}

		// ノード関係用の配列は，キー用より1つ多いため
		_tempForPromoPtr[_tempForPromoKey.length] = -1L;
	}

	/**
	 * 指定されたキーの，ページ内での格納位置を返す
	 *
	 * @return int 一番左からのインデックス(0ベース)
	 * @exception BtreeManipulationException 指定されたきーがないなど
	 */
	protected int indexOf(BtreeKey key) throws BtreeManipulationException {
		for(int i = 0; i < _keyCount; i++) {
			if(key.equals(_keys[i].toString())) {
				return i;
			}
		}

		throw new BtreeManipulationException("指定されたキー[" + key +"]がない");
	}
	/**
	 * 指定されたキーの右の子を返す
	 *
	 * @return long 右の子 -1:子がない
	 * @exception BtreeManipulationException 指定されたキーがないなど
	 */
	public long rightChildOf(BtreeKey key) throws BtreeManipulationException {
		return _children[ indexOf(key)+1 ];
	}
	/**
	 * 指定されたキーの左の子を返す
	 *
	 * @return long 左の子 -1:子がない
	 * @exception BtreeManipulationException 指定されたキーがないなど
	 */
	public long leftChildOf(BtreeKey key) throws BtreeManipulationException {
		return _children[ indexOf(key) ];
	}

	/**
	 * このページのバイトストリームを返す
	 * @param buffer バイトストリームを格納するバッファ
	 * @return バイトストリーム
	 * @exception バイトストリームに変換できなかった
	 */
	public byte[] getByteStream() throws BtreeException {
		// キー1つあたりのバイトサイズを取得する
		int keyByteSize = _factory.keyByteSize();
		int pageByteSize = keyByteSize * _order + 8 * (_order+1) +4;
		byte[] buffer = new byte[pageByteSize];

		// 作業用のバッファを作成する(ビッグエンディアン)
		ByteBuffer bf = ByteBuffer.allocate(pageByteSize).order(ByteOrder.BIG_ENDIAN);
		bf.rewind();

		// キーカウントの出力
		if(isEnabled() == true) {
			bf.putInt(_keyCount);
		} else {
			// ページが使用されていない場合，キーカウントは-1で固定
			bf.putInt(-1);
		}

		// キーの出力
		byte[] emptyKey = new byte[keyByteSize];
		for(int i = 0; i < _keys.length; i++) {
			if(_keys[i] != null) {
				bf.put(_keys[i].byteStream());
			} else {
				bf.put(emptyKey);
			}
		}
		// 子ノードへのリンクの出力
		for(int j = 0; j < _children.length; j++) {
			bf.putLong(_children[j]);
		}
		// 結果を返す．引数として渡されたバイト配列のサイズより生成されたバイト配列のほうが
		// 大きい場合，例外が発生する
		byte[] ba = bf.array();
		try {
			System.arraycopy(ba, 0, buffer, 0, ba.length);
		} catch(Exception e) {
			throw new BtreeException(e.getMessage());
		}
		return buffer;
	}
	/**
	 * バイト列からページの内容を復元する．<br>
	 * 復元できない場合はBtreeExceptionが発生する．
	 * @param stream バイト列
	 * @param keyByteSize キーのバイトサイズ
	 * @throws BtreeException 復元に失敗した
	 */
	protected void byteStreamToBtreePage(byte[] stream,int keyByteSize) throws BtreeException {
		int pageStreamSize = keyByteSize * _order + 8 * (_order+1) + 4;
		if(pageStreamSize != stream.length) {
			throw new BtreeException("バイト列データの長さとページの設定値が違う");
		}

		try {
			ByteBuffer buffer = ByteBuffer.allocate(pageStreamSize).order(ByteOrder.BIG_ENDIAN);
			buffer.rewind();
			buffer.put(stream);
			buffer.rewind();

			// 格納されているキーの数を復元する
			_keyCount = buffer.getInt();
			if(_keyCount == -1) {
				// キーの数が-1の場合，そのページは使われていないと判定する
				_keyCount = 0;			// 念のため
				_pageno = -1;			// ページ番号は-1
				setEnabled(false);
				return;
			}
			byte[] keyBuffer = new byte[keyByteSize];

			// キーの復元
			for(int i = 0; i < _keys.length; i++) {
				buffer.get(keyBuffer);
				_keys[i] = _factory.newKey(keyBuffer);
			}

			// 子ノードへのリンクの復元
			for(int j = 0; j < _children.length; j++) {
				_children[j] = buffer.getLong();
			}
		} catch(Exception e) {
			e.printStackTrace();
			throw new BtreeException("ページの復元中にエラーが発生しました");
		}
	}
	/**
	 * このページが有効かどうかを返す
	 * 
	 * @return 状態(true:有効 / false:無効)
	 */
	public boolean isEnabled() {
		return enabled;
	}
	/**
	 * このページの有効/無効を設定する<br>
	 * 無効に設定してファイルにコミットした場合，ページ領域自体は削除されずに
	 * 再利用のフラグが立つ
	 * 
	 * @param status true:有効 / false:無効
	 */
	public void setEnabled(boolean status) {
		enabled = status;
	}
	/**
	 * 昇進キーおよび分割によって新しく作成されたページを格納する構造体<br>
	 * BtreePage.insert()を実行した際の戻り値のための型．<br>
	 * 新しく作成されたページには，ページ番号が割り当てられないため，この結果を受け取ったクラスが発行する必要がある．<br>
	 * また，昇進キーの右のノード(ページ番号)は，新しく作成されるページの番号になるため，これについても結果を受け取ったクラスが設定する必要がある．<br>
	 *
	 * @author satoshi akabane
	 * @version 1.0
	 */
	public class PromoResult {
		final BtreeKey _promoKey;			// 昇進したキー
		final BtreePage _page;				// 分割によって発生した，兄弟のページ

		/**
		 * コンストラクタ
	 	 * @param pk 昇進するキー
		 * @param bp 分割によって新しく作成されたページ(分割されたページの兄弟に相当する)
		 */
		PromoResult(BtreeKey pk, BtreePage bp) {
			_promoKey = pk;
			_page = bp;
		}
	}
}

// end of BtreePage.java
