package org.logical_paradox.rss.router.algorithm;
import java.net.MalformedURLException;
import java.util.Iterator;
import java.util.LinkedList;

import org.logical_paradox.rss.http.URLPool;

/**
 * LBRoutingAlgorithm
 * サイト探索のための負荷分散探索アルゴリズム
 * @author satoshi akabane@logical-paradox.org
 * @version $Revision: 1.3 $
 */
public class LBRoutingAlgorithm extends RoutingAlgorithm {
	public static final int REQ_DOMAINS_PER_TIME = 20;			// 一度にプールから取得するドメイン名の総数
	public static final int HISTORY_PRIO_BUFSIZE = 20;			// 負荷分散用ヒストリのサイズ

	private URLHistoryPrio prio = null;
	private int lastRefIdx = 0;

	public LBRoutingAlgorithm() {
		super();
		prio = new URLHistoryPrio(REQ_DOMAINS_PER_TIME);
	}

	// このメソッドを実装すること
	/**
	 * アルゴリズムの名称を返す
	 */
	public String getAlgorithmName() {
		return "Load Balanced Routing Algorithm";
	}

	/**
	 * 次の1つを決定するためのアルゴリズム(実装)
	 */
	public String nextURL(URLPool urls) {
		String rc = null;

//		synchronized(urls) {
			boolean exitf = true;
			do {
				if(urls.size() == 0) {
					// もうない
					rc = null;
					exitf = false;
				} else {
					// 未処理URLのプールからURLを1つ取得する
					String dn = getNextSite(urls);
					Iterator<String> i = urls.getURLIterator(dn);
					if(i == null) {
						return null;
					}
					rc = i.next();
					try {
						urls.remove(rc);
					} catch(MalformedURLException e) {
					}

					if(history.isTraced(rc) == false) {
						// まだトレースしていないURLだった場合
						// 探索履歴に追加する
						history.add(rc);
						exitf = false;
					}
				}
			} while(exitf == true);
//		}

		return rc;
	}

	/**
	 * 次に探索するべきサイトを返す
	 */
	private String getNextSite(URLPool urls) {
		String rc = null;

		String[] domains = urls.domains();
		if(domains == null) {
			return null;
		}

		int looptime = domains.length >= REQ_DOMAINS_PER_TIME ? REQ_DOMAINS_PER_TIME : domains.length;
		int idx = lastRefIdx;
		int highscore = REQ_DOMAINS_PER_TIME + 1;

		int priority = 0;

		for(int i = 0; i < looptime; i++) {
			if(idx >= domains.length) {
				idx = 0;
			}
			String dn = domains[ idx ];
			priority = prio.indexOf(dn);
			if(priority <= highscore) {
				highscore = priority;
				rc = dn;
			}
			// 優先順位-1の場合はそこで終了してしまってOK
			if(priority == -1) {
				break;
			}

			idx++;
		}

		if(rc != null) {
			// 取り出し順序を管理するオブジェクトに，選択されたものを登録する
			lastRefIdx = idx;
			prio.addFirst(rc);
		}
		return rc;
	}

	/**
	 * ドメイン名を取り出した順番を管理するクラス
	 * 平たくいえばindexつきリングバッファ
	 */
	class URLHistoryPrio {
		private LinkedList<String> buf = null;				// バッファ
		private int bufsize = 0;					// バッファのサイズ

		// コンストラクタ
		private URLHistoryPrio(int size) {
			buf = new LinkedList<String>();
			bufsize = size;
		}

		// 追加する
		// 追加すると同時に，必要なくなったものについてはリストから削除される
		private void addFirst(String url) {
			synchronized(buf) {
				int idx = indexOf(url);
				if(idx >= 0) {
					// 既に同じURLが存在する場合は，そっちを削除
					buf.remove(url);
				} else if(buf.size() >= bufsize) {
					// 指定URLが存在せず，かつバッファのサイズがいっぱいの場合は，一番最後のものを削除
					buf.removeLast();
				}
				// リストの最後に今与えられたURLを追加する
				buf.addLast(url);
			}
		}

		// 指定URLが含まれている位置を返す
		// 含まれていない場合は-1がかえる
		private int indexOf(String url) {
			return buf.indexOf(url);
		}
	}
}

// end of LBRoutingAlgorithm.java
