import java.util.*;

/**
 * Programa que implementa el tipo de datos abstracto conjunto.
 * @author Amparo López Gaona
 * @version 1a edicion.
 */
public class Conjunto implements Conjuntable {
    private Object[] datos;     // Almacenamiento para el conjunto
    private int nElems;         // Cantidad de datos almacenados

    /**
     *  Constructor de un conjunto con capacidad para 20 elementos.
     */
    public Conjunto() {
	this(20);
    }

    /**
     * Constructor de un conjunto con capacidad para los elementos
     * indicados. Si el tamanio es negativo o cero, se construye un
     * conjunto con capacidad para 20 elementos.
     * @param tam -- capacidad del conjunto.
     */
    public Conjunto(int tam) {
	datos = new Object[tam <= 0 ? 20 : tam];
	for (int i = 0; i < datos.length; i++)
	    datos[i] = null;
	nElems = 0;
    }

    /**
     * Constructor de copia.
     * @param c -- conjunto que se toma como valor inicial para
     * crear el nuevo.
     */
    public Conjunto(Conjunto c) {
	datos = new Object[c.datos.length];

	for (int i = 0; i < c.datos.length; i++)
	    datos[i] = c.datos[i];
	nElems = c.nElems;
    }

    /**
     * Determina si el conjunto tiene elementos o no.
     * @return boolean - Devuelve true si el conjunto no tiene elementos y
     *  false en otro caso.
     */
    public boolean estaVacio(){ 
	return nElems == 0;
    }

    /**
     * Devuelve la cantidad de elementos que tiene el conjunto.
     * @return int - cantidad de  elementos que tiene el conjunto.
     */
    public int tamanio(){ 
	return nElems;
    }

    /**
     * Elimina los elementos que tiene el conjunto.
     */
    public void vaciar(){ 
	nElems = 0;
    }

    /**
     * Determina si un elemento esta contenido en el conjunto.
     * @param elem - elemento que se desea saber si esta en el conjunto.
     * @return boolean - devuelve true si el elemnto esta en el conjunto y
     *                   false en otro caso.
     */
    public boolean contiene (Object elem){
	if (!estaVacio())
	    for (int i = 0; i < nElems; i++)
		if (elem.equals(datos[i]))
		    return true;
	return false;
    }

    /**
     * Elimina del conjunto el elemento especificado.
     * @param elem - elemento que se desea eliminar del conjunto.
     */
    public void eliminar(Object elem) { 
	if (!estaVacio())
	    for (int i = 0; i < nElems; i++) 
		if (elem.equals(datos[i])){
			datos[j] = datos[nElems--];
		    return;
		}
    }

    /**
     * Agrega un elemento al conjunto, siempre y cuando no exista.
     * @param elem - Elemento a insertar.
     */
    public void agregar(Object elem){
	if (nElems >= datos.length)
	    crecerArreglo();
	if (! contiene(elem)) {
	    datos[nElems++] = elem;
	}
    }

    private void crecerArreglo() {
	int tamanoNuevo =datos.length + 10;
	Object[] arregloNuevo = new Object[tamanoNuevo];
	
	for (int i = 0; i < nElems; i++)
	    arregloNuevo[i] = datos[i];
	datos = arregloNuevo;
    }

    /**
     * Metodo que devuelve  un iterador sobre el conjunto
     * @return Iterator -- iterador sobre el conjunto
     */
    public Iterator iterador () {
	return new miIterador();
    }

    /**  Implementacion del iterador **/
    private class miIterador implements Iterator {
	private int pos;       //Indice para recorrer el conjunto

	public miIterador(){   // Constructor por omision
	    pos = 0;
	}

	/*  Determina si aun hay elementos en el conjunto */
	public boolean hasNext() { 
	    return (pos < nElems);
	}

	/* Devuelve el siguiente elemento en el conjunto y avanza el
	   indice una posicion */
	public Object next() throws NoSuchElementException {
	    if (hasNext()) 
		return datos[pos++];
	    throw new NoSuchElementException("No hay elementos en el conjunto");
	}
    
	/* Operacion no implementada */
	public void remove() throws UnsupportedOperationException,
                                IllegalStateException {
	    throw new UnsupportedOperationException();
	}
    }

    /**
     * Metodo que devuelve la union de dos conjuntos
     * @param c -- conjunto que une al que llama a este metodo
     * @return Conjunto -- conjunto con la union
     */
    public Conjunto union(Conjuntable c) {
	Conjunto cUnion = new Conjunto(this);
	Iterator it = c.iterador();
	while(it.hasNext())  {
	    cUnion.agregar(it.next());
	}
	return cUnion;
    }

    /**
     * Metodo que devuelve la interseccion de dos conjuntos
     * @param c -- conjunto que intersectara con el conjunto que 
     * llama a este metodo
     * @return Conjunto -- conjunto con la interseccion
     */
    public Conjunto interseccion(Conjuntable c) {
	Conjunto cInterseccion = new Conjunto(this);

	Iterator it = iterador();
	while (it.hasNext()) {
	    Object elemento = it.next();
	    if (!c.contiene(elemento))
		cInterseccion.eliminar(elemento);
	}
	return cInterseccion;
    }

    /**
     * Metodo que devuelve la diferencia de dos conjuntos
     * @param c -- conjunto con el que se hace la diferencia
     */
    public Conjunto diferencia(Conjuntable c) {
	Conjunto cMenos = new Conjunto(this);
	Iterator it = iterador();

	while (it.hasNext()) {
	    Object elemento = it.next();
	    if (c.contiene(elemento))
		cMenos.eliminar(elemento);
	}
	return cMenos;
    }

    /**
     * Metodo para determinar si un conjunto es subconjunto de otro.
     * @param c -- conjunto en el que se busca el subconjunto.
     * @return boolean -- devuelve true si el conjunto que llama a este metodo
     * es subconjunto del parametro y false en otro caso.
     */
    public boolean subconjunto(Conjuntable c) {
	Iterator it = iterador();
	while (it.hasNext())
	    if (!c.contiene(it.next()))
		return false;
	return true;
    }
}