/*
 * LOGICAL-PARADOX.ORG
 * Copyright (C)2005 satoshi akabane(akabane@logical-paradox.org)
 * $Id: DefaultRoutingAlgorithm.java,v 1.9 2006/02/19 05:01:09 akabane Exp $
 */
package org.logical_paradox.rss.dsr.routing;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;

import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;
import org.logical_paradox.rss.dsr.routing.metrics.Metric;

/**
 * デフォルトのルーティングアルゴリズム
 * @author satoshi akabane@logical-paradox.org
 * @version $Revision: 1.9 $
 */
public class DefaultRoutingAlgorithm extends RoutingAlgorithm {
	/** ロガー */
	private static final Log log = LogFactory.getLog(DefaultRoutingAlgorithm.class);

	/** 最適ノード選択時の曲線の傾き */
	public static final double SLOPE_OF_CURVE = 1.125;
	/** ノードリストとして保持する最適ノード数 */
	public static final int MAX_FETCH_COUNT = 15;
	/** 探索の深度 */
	public static final int MAX_SEARCH_DEPTH = 2;

	/**
	 * コンストラクタ
	 * @param node 結合するノード
	 */
	protected DefaultRoutingAlgorithm(Node node) {
		super(node);
	}

	/**
	 * 最適ノード選択処理を実行する
	 */
	@SuppressWarnings("unchecked")
	@Override
	public void configure() {
		// 現在紐づいているノードから、適当な深度のノードリストを取得してノードリストを構成する
		List<Node> collectedNodeList = collectNodeList(getNode().getRelativeNodes(true), MAX_SEARCH_DEPTH);
		log.info("取得されたノード数: " + collectedNodeList.size());
		// HUG要求を発行する(※この処理は無駄にトラフィックを発生させるので、実際にはhugしない方法を考えること)
		for(Node node : collectedNodeList) {
			if(getNode().equals(node) == false && getNode().contains(node) == false) {
				node.hug(getNode());
				getNode().add(node);
			}
		}
		log.info("メトリックを計測しています");
		ArrayList<Metric> metrics = new ArrayList<Metric>();
		for(Iterator<Node> it = getNode().iteratorRelativeNodes(); it.hasNext();) {
			Node n = it.next();
			metrics.add(new Metric(getNode().distanceFrom(n), n));
		}

		// メトリック値の小さい順(近いもの順)にソートする
		Collections.sort(metrics);
		int fetchPoint = 0;
		int fetchCount = 0;
		ArrayList<Node> bestNodes = new ArrayList<Node>();

		log.info("最適ノードを選択しています");
		for(;;) {
			fetchPoint = (int)Math.pow((double)fetchCount, SLOPE_OF_CURVE);
			fetchCount++;

			if(fetchPoint >= metrics.size()) {
				break;
			}
			Metric m = metrics.get(fetchPoint);
			if(bestNodes.contains(m)) {
				// 選択したノードは既に最適ノードとして選択済みだった
				continue;
			} else {
				// 最適ノードとして選択する
				bestNodes.add(m.getBuddy());
				log.info("接続先ノード: " + m.getBuddy().getNodeId());
			}
			if(bestNodes.size() >= MAX_FETCH_COUNT) {
				break;
			}
		}

		if(bestNodes.size() > 0) {
			// 最適ノード選択されたものを全て削除
			getNode().getRelativeNodes().removeAll(bestNodes);		
			// 残ったノード(=リンクを切断するノード)に対して、離脱を通知する
			notifyDisconnect();
			// 最適ノードのみのリストでリンクを再構成
			getNode().addAll(bestNodes);
		}
	}

	/**
	 * このノードと繋がっている他のノードからノードリストを収集する
	 * 指定された階層分だけ繰り返し実行する
	 * 深さ優先探索で実行される
	 * @param depth 探索の深さ(1以上)
	 * @return 収集されたノードリスト(重複分と自分のノードを含まない)
	 */
	protected List<Node> collectNodeList(List<Node> nodeList, int depth) {
		List<Node> nodes = new ArrayList<Node>();

		if(depth > 0) {
			// 引数として渡されたノードについて，ノードリストを要求する
			for(Node node : nodeList) {
				if(node.equals(getNode()) == false && nodes.contains(node) == false) {
					nodes.add(node);
				}
				// ノードリストを追加する
				for(Node n : node.getRelativeNodes(true)) {
					if(nodes.contains(n) == false) {
						nodes.add(n);
					}
				}
				// 下の階層を探索した結果を追加する
				nodes.addAll(collectNodeList(node.getRelativeNodes(), depth-1));
			}
		}
		return nodes;
	}

	/**
	 * hugする
	 * @param node hugを要求してきたノード
	 * @return true:許可 / false:拒否
	 */
	public boolean hug(Node node) {
		if(getNode().contains(node) == false) {
			getNode().add(node);
		}
		return true;
	}

	/**
	 * hugしている全てのノードに対して，分散ネットワークからの離脱を通知する
	 */
	public void notifyDisconnect() {
		for(Iterator<Node> it = getNode().iteratorRelativeNodes(); it.hasNext();) {
			Node node = it.next();
			// 接続相手のノードから，自分のノードに関するリンクを削除する
			node.remove(getNode());
			it.remove();
		}
	}
}
