package dataStructures;

import java.util.*;

/**
 * <p>Titulo: Uma implementaçao vectorial do Conjunto</p>
 * <p>Descrição: Esta implementaçao usa uma representação estática crescente
 *               para guardar a informaçao</p>
 * @version 1.0
 */

public class VSet implements Set,Cloneable {

   private final int  DELTA = 128;
   private int      nElems;
   private Object[] theSet;

   public VSet() {
     theSet  = new Object[DELTA];
     nElems  = 0;
   }

   public Set empty() {
     return new VSet();
   }

   public boolean isEmpty() {
     return nElems == 0;
   }

   public int length() {
     return nElems;
   }

   /**
    * Increments the structure length (adds 'DELTA' new slots)
    */
   private void grow() {
     Object[] newSet = new Object[theSet.length + DELTA];

     for(int i=0;i<theSet.length;i++)
       newSet[i] = theSet[i];

     theSet = newSet;
   }

   private boolean isInSet(int n) {
     return theSet[n] != null;
   }

   public void insert(Object item) {

     if (belongs(item))
       return;

     if (nElems == theSet.length)
       grow();

     int i;
     for (i=0; isInSet(i); i++); //ciclo vazio
     theSet[i] = item;
     nElems++;
   }

   public void remove(Object item) {
     for (int i=0; i<theSet.length; i++)
       if (isInSet(i) && theSet[i].equals(item)) {
         theSet[i] = null;
         nElems--;
         return;
       }
   }

   public boolean belongs(Object item) {
     for (int i=0; i<theSet.length; i++)
       if (isInSet(i) && theSet[i].equals(item))
         return true;
     return false;
   }

  public void union(Set s) {
    Iterator it = s.iterator();

    while(it.hasNext())
      insert(it.next());
  }

  public void intersection(Set s) {
    Iterator it = iterator();

    while(it.hasNext()) {
      Object elem = it.next();
      if (!s.belongs(elem))
        remove(elem);
    }
  }

  public void subtraction(Set s) {
    Iterator it = s.iterator();

    while(it.hasNext())
      remove(it.next());
  }

  public boolean contains(Set s) {
    Iterator it = s.iterator();

    while(it.hasNext())
      if (!belongs(it.next()))
        return false;
    return true;
  }

  public boolean equals(Set s) {
    return contains(s) && s.contains(this);
  }

  public Object clone() {
    VSet cp = new VSet();

    cp.theSet = new Object[theSet.length];

    for (int i=0; i<theSet.length; i++)
      cp.theSet[i] = theSet[i];

    return cp;
  }

  public String toString() {
    if (isEmpty())
      return "{}";

    Iterator it = iterator();
    String s = "{" + it.next();

    while(it.hasNext())
      s += "," + it.next();

    return s + "}";
  }

  public Iterator iterator() {
     return new SetIterator();
  }
  //********************************************************************
  //** Iterator Methods

  private class SetIterator implements Iterator {

    private int nextElem;

    private SetIterator() {
      nextElem = isEmpty() ? -1 : 0;
    }

    /* Returns the next element of the set.
     * If not available, returns NULL
     */
     public Object next() {
       if (nextElem >= 0)
         for (int i=nextElem; i<theSet.length; i++)
           if (isInSet(i)) {
             nextElem = i+1;
             return theSet[i];
           }
       nextElem = -1;
       return null;
     }

    /* Is there next elements?
     */
     public boolean hasNext() {
       if (nextElem != -1)
         for (int i=nextElem; i<theSet.length; i++)
           if (isInSet(i))
             return true;
       return false;
     }

     public void remove() {
       throw new UnsupportedOperationException();
     }

  } // endLocalClass SetIterator

  //********************************************************************
  public static void main(String[] args) {
    VSet v1 = new VSet(),
         v2 = new VSet();

    v1.insert(new Integer(1));
    v1.insert(new Integer(2));
    v1.insert(new Integer(3));
    v1.insert(new Integer(4));
    v1.insert(new Integer(2));
    v1.remove(new Integer(3));
    v1.remove(new Integer(10));
    System.out.println("v1="+v1);

    v2.insert(new Integer(6));
    v2.insert(new Integer(7));
    v2.insert(new Integer(8));
    v2.insert(new Integer(9));
    v2.insert(new Integer(9));
    System.out.println("v2="+v2);

//    v1.intersection(v2);
    v1.union(v2);
    System.out.println("v1 union v2="+v1);

    System.out.println(v1 + " length=" + v1.length());
    System.out.println(v2 + " length=" + v2.length());

    System.out.println(v1.contains(v2)?"sim":"nao");

    Iterator e = v2.iterator();
    while(e.hasNext())
      System.out.print(e.next()+" ");
  }
}  // endClass VSet