BinarySearchForFile

BinarySearchFile.java

package info.motteke.util;

import java.io.File;
import java.io.IOException;
import java.io.InputStream;
import java.io.RandomAccessFile;

/**
 * ファイルに対してバイナリサーチを実施するクラスです。
 * 
 * @param <E> 検索の比較に使用する型
 * 
 * @author YWak
 */
public abstract class BinarySearchFile<E extends Comparable<? super E>> {

	/** 要素が見つからなかった場合に返される値です。 */
	public static final long NOT_FOUND = -1;

	/**
	 * ファイルから指定された要素を検索し、その要素の位置を返します。<br>
	 * 見つからなかった場合は{@linkplain #NOT_FOUND}を返します。
	 * 
	 * @param file
	 *            検索対象のファイル
	 * @param condition
	 *            検索条件
	 * 
	 * @return file中でconditionに一致する要素が出現する位置。見つからなければ{@linkplain #NOT_FOUND}。
	 * @throws IOException
	 *             入出力例外が発生した場合
	 */
	public long search(File file, E condition) throws IOException {

		/* ここでは検索にあまり関係ない処理だけを実装し、
		 * 検索の実装はdoSearchで行います。
		 */
		if (file == null) {
			throw new NullPointerException("file can't be null");
		}
		if (condition == null) {
			throw new NullPointerException("condition can't be null");
		}

		RandomAccessFile target = null;

		try {
			target = new RandomAccessFile(file, "r");

			return doSearch(target, condition);
		} finally {
			close(target);
		}
	}

	/**
	 * ファイルからの検索を行います。
	 * 
	 * @param file ファイル
	 * @param condition 検索条件
	 * @return conditionに一致するインデックス。または{@linkplain #NOT_FOUND}
	 * @throws IOException 
	 */
	protected long doSearch(RandomAccessFile file, E condition) throws IOException {
		// データ取得用InputStream。file.seekを呼ぶたびに読み込み位置が変わる。
		RandomAccessFileInputStream input = new RandomAccessFileInputStream(file);

		/* 以降のアルゴリズムでは、最初の行は絶対に発見できない。
		 * 最初の行が該当する場合はあらかじめチェックしておく。
		 */
		file.seek(0);
		E firstData = getData(input);
		
		if (firstData != null && firstData.equals(condition)) {
			return 0;
		}

		long top = -1;
		long middle = NOT_FOUND;
		long bottom = file.length() + 1;
		boolean matched = false;

		/* これ以降、常に以下の式が成り立つ
		 * 1. elements[top] < condition
		 * 2. elements[bottom] >= condition
		 */
		while (top + 1 < bottom) {
			middle = (top + bottom) / 2;

//			System.out.printf("top(%d) middle(%d) bottom(%d)\n", top, middle, bottom);
			seekUntilNewLine(file, middle);
			
			if (input.isEOF()) {
				break;
			}

			E middleData = getData(input);

			int comp = condition.compareTo(middleData);
			
			if (comp < 0) {
				bottom = middle;
			} else {
				top = middle;
			}
		}

		file.seek(bottom);
		if (getData(input) == null) {
			bottom = NOT_FOUND;
		}
		
		return handleResult(matched, bottom);
	}

	/**
	 * 指定された位置に存在するデータを返します。<br>
	 * 該当する位置が存在しない場合は、nullを返します。
	 * 
	 * @param input データを読み出す{@linkplain InputStream}
	 * @return 読み出したデータ
	 */
	protected abstract E getData(InputStream input) throws IOException;

	/**
	 * 検索が完了した際の振る舞いを記述します。
	 * 
	 * @param matched 検索条件に一致する要素が見つかったかどうか
	 * @param index 条件に最も適合するインデックス
	 * @return 検索に合致するインデックス
	 * @see {@linkplain #returnsFirst(boolean, long)}, {@linkplain #returnsMatchedIndex(boolean, long)}
	 */
	protected abstract long handleResult(boolean matched, long index);

	/**
	 * 条件に完全に一致した場合のみ、インデックスを返します。<br>
	 * 条件に一致しない場合は{@linkplain #NOT_FOUND}を返します。
	 */
	protected long returnsMatchedIndex(boolean matched, long index) {
		if (matched) {
			return index;
		} else {
			return NOT_FOUND;
		}
	}

	/**
	 * 条件に等しいか、より大きくなる最初のインデックスを返します。<br>
	 * すべての要素が条件より小さい場合のみ{@linkplain #NOT_FOUND}を返します。
	 */
	protected long returnsFirst(boolean matched, long index) {
		return index;
	}

	/**
	 * 改行の直後の位置まで移動します。
	 * 
	 * @param file ランダムアクセスファイルのインスタンス
	 * @param pos 初期位置
	 * @throws IOException 
	 */
	protected void seekUntilNewLine(RandomAccessFile file, long pos) throws IOException {
		assert pos >= 0;

		file.seek(pos);
		file.readLine();
	}

	/**
	 * RandamAccessFileのインスタンスを閉じます。<br>
	 * この実装は例外を発生させません。
	 * 
	 * @param raf
	 *            閉じるRandamAccessFileのインスタンス
	 */
	protected void close(RandomAccessFile raf) {
		if (raf == null) {
			return;
		}

		try {
			raf.close();
		} catch (IOException e) {
			/* empty */
		}
	}

	/**
	 * {@linkplain RandomAccessFile}をラップして{@linkplain InputStream}のインスタンスに変換します。<br>
	 * この実装は、close()を呼んでも何もしません。
	 * 
	 * @author YWak
	 */
	protected static class RandomAccessFileInputStream extends InputStream {
		
		/** 委譲先のRandomAccessFileインスタンス */
		private final RandomAccessFile raf;
		
		/**
		 * 引数の{@linkplain RandomAccessFile}のインスタンスに処理を委譲する
		 * {@linkplain InputStream}のインスタンスを作成します。
		 * 
		 * @param raf 委譲先のインスタンス
		 */
		protected RandomAccessFileInputStream(RandomAccessFile raf) {
			this.raf = raf;
		}
		
		/**
		 * ファイルの終端であるかを判断します。
		 * 
		 * @return ファイルの終端であるか
		 * @throws IOException ファイルの読み込みに失敗した場合
		 */
		public boolean isEOF() throws IOException {
			return raf.getFilePointer() >= raf.length();
		}

		/**
		 * {@inheritDoc}
		 */
		@Override
		public int read() throws IOException {
			return raf.read();
		}

		/**
		 * {@inheritDoc}
		 * <p>この実装では何もしません。</p>
		 */
		@Override
		public void close() {
			/* empty */
		}
	}
}