/*
 * @(#)SearchStatsTree.java
 */
package ereinionbw;

import java.util.Vector;

import ereinion.search.SearchStats;
import ereinion.search.SearchExceptionFail;
import ereinion.search.SearchNode;

/*
 * classe di package : SearchStatsTree
 *
 * Classe statistica che memorizza l'albero di ricerca
 */
class SearchStatsTree extends SearchStats
{

	private Vector tree;

	private int bufferSize;

	public SearchStatsTree(long time, int buffer)
	{
		super(time);
		bufferSize = buffer;
	}

	public void reset(long time)
	{
		super.reset(time);
		tree = new Vector();
	}

	public void makeStats(final SearchNode node, int queueSize) throws SearchExceptionFail
	{
		super.makeStats(node,queueSize);
		if (tree.size()<bufferSize)
			tree.addElement(node);
	}

	public SearchNode[] getNodes()
	{
		SearchNode[] result = new SearchNode[tree.size()];
		for (int k=0; k<tree.size(); k++)
			result[k] = (SearchNode)tree.elementAt(k);
		return result;
	}

}

/*
 * classe di package : BWTree
 *
 * Classe per la gestione di un albero di ricerca.
 */
class BWTree
{
	
	public SearchNode[] nodeList;

	public int levelNumber;

	public BWTree(SearchNode[] nodes)
	{
		nodeList = nodes;
		levelNumber = 0;
		for (int k=0; k<nodeList.length; k++)
			levelNumber = Math.max(levelNumber,nodeList[k].getDepth()+1);
	}

	public int[] getParentValue()
	{
		int[] parents = new int[nodeList.length];
		for (int i=0; i<parents.length; i++) {
			parents[i] = ROOT;
			for (int j=0; j<i && parents[i]==ROOT; j++)
				if (nodeList[i].getParent() == nodeList[j])
					parents[i] = j;
		}
		return parents;
	}
	
	public BWTreeNode[][] getTreeMap()
	{
		Vector[] levels = new Vector[levelNumber];
		int[] parents = getParentValue();
		int maxSpace = 0;
		for (int i=0; i<levelNumber; i++) {
			levels[i] = new Vector();
			for (int j=0; j<nodeList.length; j++)
				if (nodeList[j].getDepth() == i)
					levels[i].addElement(new BWTreeNode(j,parents[j]));
			maxSpace = Math.max(maxSpace,levels[i].size());
		}
		BWTreeNode[][] map = new BWTreeNode[levelNumber][maxSpace];
		int count = 0;
		for (int i=0; i<map.length; i++)
			for (int j=0; j<maxSpace; j++) {
				int filling = (maxSpace-levels[i].size())/2;
				if (j>=filling && j<filling+levels[i].size()) {
					map[i][j] = (BWTreeNode)levels[i].elementAt(j-filling);
					count++;
				} else
					map[i][j] = new BWTreeNode(FILL,FILL);
			}
		return map;
	}


	public static final int ROOT = -1;

	public static final int FILL = -2;

}

/*
 * classe di package : BWTreeNode
 *
 * Classe per la gestione di un nodo di BWTreeNode
 */
class BWTreeNode
{

	public int value, parent;

	public BWTreeNode(int v, int p)
	{
		value = v;
		parent = p;
	}

}