import java.util.Comparator;

/** 
 * Clase para empacado usando siempre el contenedor en el que mejor
 * quepa cada objeto a empacar
 * @author  Amparo López Gaona
 * @version 1a. ed.
 */
public class BinPack {
    ArbolBinarioBusquedaR arbol;

  /**
   * Constructor por omision crea un arbol binario de busqueda con duplicados
   */
    public BinPack () {
	arbol = new ArbolBinarioBusquedaR(new MiComparador());
    }

    /** 
     * Metodo que encuentra el contenedor en el que quepa un elemento de la capacidad 
     * especificada y que tenga la menor capacidad desocupada.
     * @param capacidad -- capacidad requerida del contenedor
     * @return Contenedor -- contenedor con la menor capacidad desocupada
     */
    private Contenedor menorMayor(int capacidad) {
	NodoArbol nodo = arbol.obtenerRaiz();
	NodoArbol elementoMejor = null;   

	while (nodo != null)
	    if (((Contenedor)(nodo.valor)).obtenerDisponible() >= capacidad) {
		elementoMejor = nodo;
		nodo = nodo.izquierda;
	    } else
		nodo = nodo.derecha;

	return (elementoMejor != null) ? (Contenedor)elementoMejor.valor : null;
    }

/** 
 * Metodo para empacar objetos en contenedores de capacidad predefinida
 * @param objetos - Arreglo de objetos que se van a empacar
 * @param capContenedor - capacidad de los contenedores
 * @return Lista - lista con los contenedores con los objetos almacenados 
 * en cada uno.
 */
    public Lista empacar(Objeto [] objetos, int capContenedor) {
	Lista acomodo = new Lista();
	int cont = 0;
	Contenedor mejor;

	for (int i = 0; i < objetos.length; i++) {
	    mejor = menorMayor(objetos[i].capacidad());
	    if (mejor == null) {
		mejor = new Contenedor("contenedor" + ++cont, capContenedor, objetos[i]);
	    } else {
		mejor.guardarObjeto(objetos[i]);
		arbol.eliminar(mejor); 
	    }

	    int nuevoDisp = mejor.obtenerDisponible() - objetos[i].capacidad();
	    mejor.asignarDisponible(nuevoDisp);
	    if (nuevoDisp > 0) {
		arbol.agregar(mejor);
	    } else {
		acomodo.agregar(mejor);
	    }
	}
	while (!arbol.estaVacio()){
	    acomodo.agregar(arbol.obtenerRaiz().valor);
	    arbol.eliminar(arbol.obtenerRaiz().valor);
	}
	return acomodo;
    }


     private class MiComparador implements Comparator {
	public int compare(Object o1, Object o2) {
	    return ((Contenedor)(o1)).obtenerDisponible() -
		((Contenedor)(o2)).obtenerDisponible();
	    }
	}
}