/**
 * LOGICAL-PARADOX.ORG
 * Copyright (C)2004 satoshi akabane(akabane@logical-paradox.org)
 *
 */
package org.logical_paradox.common.util;

import java.util.Iterator;

/**
 * 優先順位つきキャッシュ
 * 
 * @author satoshi akabane@logical-paradox.org
 * @version 1.0
 */
public class PriorityCache extends Cache {
	public static final int GREATER_FIRST = 1;
	public static final int LESS_FIRST = 0;

	private final int sortOrder;

	/**
	 * デフォルトコンストラクタ
	 * キャッシュアウトしない設定で初期化される
	 */
	public PriorityCache() {
		super();
		sortOrder = GREATER_FIRST;
	}
	/**
	 * コンストラクタ
	 * 指定されたキャッシュサイズを超えた場合，古いものがキャッシュアウトする．<br>
	 * sizeに0を指定した場合，キャッシュアウトされない
	 *
	 * @param size サイズ
	 */
	public PriorityCache(int size) {
		super(size);
		sortOrder = GREATER_FIRST;
	}
	/**
	 * コンストラクタ
	 * 指定されたキャッシュサイズを超えた場合，古いものがキャッシュアウトする．<br>
	 * sizeに0を指定した場合，キャッシュアウトされない
	 * 
	 * @param size サイズ
	 * @param order ソートオーダー(GREATER_FIRST: 大きいほうを優先 LESS_FIRST: 小さいほうを優先)
	 */
	public PriorityCache(int size, int order) {
		super(size);
		sortOrder = order;
	}
	/**
	 * キャッシュにオブジェクトを追加する
	 * キャッシュサイズを超えた場合，妥当なキャッシュドオブジェクトがキャッシュアウトされる
	 * 
	 * @param o 追加するオブジェクト
	 * @return キャッシュアウトしたオブジェクト(null: なし)
	 */
	public Object add(Object o) {
		return add((Comparable)o);
	}
	/**
	 * キャッシュにオブジェクトを追加する
	 * キャッシュサイズを超えた場合，妥当なキャッシュドオブジェクトがキャッシュアウトされる
	 * 
	 * @param o 追加するオブジェクト
	 * @return キャッシュアウトしたオブジェクト(null: なし)
	 */
	public Object add(Comparable o) {
		Object rc = null;
		synchronized(collection) {
			if(collection.size() == limit) {
				rc = cacheOut();
			}
			// 挿入可能位置を取得する
			int idx = findInsertableIndex(o);
			if(idx == -1) {
				// 普通に最後尾に追加する
				collection.add(o);
			} else {
				// 途中に挿入
				collection.add(idx, o);
			}
		}
		return rc;
	}
	/**
	 * 挿入可能なインデックスを返す
	 * 
	 * @param o 挿入するオブジェクト
	 * @return 挿入位置(-1: 最後尾)
	 */
	protected int findInsertableIndex(Comparable o) {
		// sequential searchな探索法
		int idx = 0;
		synchronized(this) {
			for(Iterator it = collection.iterator(); it.hasNext(); idx++) {
				switch(sortOrder) {
					case GREATER_FIRST:
						// 与えられたオブジェクトのほうがもともとのものより大きい場合
						if(o.compareTo((Comparable)it.next()) > 0) {
							return idx;
						}
						break;
					case LESS_FIRST:
						// 与えられたオブジェクトのほうがもともとのものより小さい場合
						if(o.compareTo((Comparable)it.next()) < 0) {
							return idx;
						}
						break;
					default:
						throw new IllegalArgumentException("設定されている優先順位オーダーがおかしい:" + sortOrder);
				}
			}
		}
		// 最後まで挿入可能な位置が見つからなかった
		return -1;
	}
}
