package business;

import java.awt.Dimension;
import java.awt.Point;

public class Arbol extends Grafo {

	public Arbol(int numeroVertices, int grado, Dimension d) {
		int nivel = 1;
		double finNivel = Math.pow(grado, nivel) + (double)((nivel - 1) * grado);
		int w = d.width;
		int dist = 30;
		int xRaiz = 500;
		int altura = calcularAlturaArbol(numeroVertices, grado);
		w = ((int)Math.pow(grado, altura) * dist) / 2;
		if(500 - (w + 30) < 0)
			xRaiz = d.width / 2;
		int yRaiz = 100;
		int wTotal = (dist * ((int)Math.pow(grado, nivel) - 1)) / 2;
		int nXPadre = xRaiz;
		Vertice n = new Vertice(new Point(xRaiz, yRaiz), getVerticeId(), false);
		anadirVertice(n);
		yRaiz += 70;
		for(int i = 1; i < numeroVertices; i++) {
			if((double)i > finNivel) {
				yRaiz += 70;
				nivel++;
				finNivel = Math.pow(grado, nivel) + (double)(i - 1);
				wTotal = (dist * ((int)Math.pow(grado, nivel) - 1)) / 2;
				xRaiz = nXPadre - wTotal;
				if(xRaiz <= 0)
					xRaiz = 15;
			} else if(i == 1) {
				wTotal = (dist * ((int)Math.pow(grado, nivel) - 1)) / 2;
				xRaiz -= wTotal;
				if(xRaiz <= 0)
					xRaiz = 15;
			} else {
				wTotal = (dist * (int)Math.pow(grado, nivel)) / (int)Math.pow(grado, nivel);
				xRaiz += wTotal;
			}
			n = new Vertice(new Point(xRaiz, yRaiz), getVerticeId(), false);
			anadirVertice(n);
		}

		nivel = 0;
		finNivel = calcularVerticesNivel(nivel, grado) + (nivel - 1) * grado;
		for(int i = 0; i < getVertices().size(); i++) {
			if((double)i > finNivel) {
				nivel++;
				finNivel = calcularVerticesNivel(nivel, grado) + (i - 1);
			}
			Vertice nO = (Vertice)getVertices().get(i);
			int nx = calcularVerticesNivel(nivel + 1, grado) + grado * (i - calcularVerticesNivel(nivel, grado));
			for(int j = 0; j < grado; j++) {
				if(nx == getVertices().size())
					return;
				Vertice nF = (Vertice)getVertices().get(nx);
				Arista a = new Arista(nO, nF, getAristaId(), false);
				anadirArista(a);
				nx++;
			}
		}
	}

	/**
	 * 
	 * @param nivel en el que nos encontramos
	 * @param grado del árbol
	 * @return el número de vértices que caben hasta dicho nivel
	 */
	public int calcularVerticesNivel(int nivel, int grado) {
		int res = 0;
		for(int i = 0; i <= nivel; i++)
			res += Math.pow(grado, i);
		return res;
	}

	public int calcularAlturaArbol(int numeroVertices, int grado) {
		int i = 1;
		boolean acaba = false;
		while(!acaba) {
			if(calcularVerticesNivel(i, grado) >= numeroVertices)
				acaba = true;
			else
				i++;
		}
		return i;
	}
}