TAD IntSet

Um conjunto de numeros inteiros, que suporta operacoes para inserir, adicionar e verificar se um numero esta no conjunto.

// -----------------------------------------------------------
// Estruturas de Dados 2019/2020 (CC1007) - DCC/FCUP
// http://www.dcc.fc.up.pt/~pribeiro/aulas/edados1920/
// -----------------------------------------------------------
// Interface que define o TAD conjunto de numeros inteiros
// Ultima alteracao: 10/03/2018
// -----------------------------------------------------------

// Interface que define o TAD conjunto de numeros inteiros
public interface IntSet {
   public boolean contains(int x); // Retorna true se x esta no conjunto
   public boolean add(int x);      // Adiciona x ao conjunto
   public boolean remove(int x);   // Remove x do conjunto
   public int     size();          // Retorna o numero de elementos do conjunto
   public void    clear();         // Limpa o conjunto (torna-o vazio)
}

// -----------------------------------------------------------
// Estruturas de Dados 2019/2020 (CC1007) - DCC/FCUP
// http://www.dcc.fc.up.pt/~pribeiro/aulas/edados1920/
// -----------------------------------------------------------
// Implementa o TAD conjunto usando um array como lista de elementos
// Ultima alteracao: 10/03/2018
// -----------------------------------------------------------

public class ArrayListIntSet implements IntSet {
   private int size;   // Numero de elementos do conjunto
   private int elem[]; // Array que contem os elementos em si 
   
   ArrayListIntSet(int maxSize) {
      elem = new int[maxSize];
      size = 0;
   }

   public boolean add(int x) {
      if (!contains(x)) {
         if (size == elem.length)
            throw new RuntimeException("Maximum size of set reached");         
         elem[size] =  x;
         size++;
         return true;
      }
      return false;
   }

   public boolean remove(int x) {
      if (contains(x)) {
         int pos = 0;
         while (elem[pos] != x) pos++;
         size--;
         elem[pos] = elem[size]; // Trocar ultimo elemento 
         return true;            // com o que se removeu
      }
      return false;
   }
   
   
   public boolean contains(int x) {
      for (int i=0; i<size; i++)
         if (elem[i] == x)
            return true;
      return false;
   }
   
   public void clear() {
      size = 0;
   }
   
   public int size() {
      return size;
   }

   public String toString() {
      String res = "{";
      for (int i=0; i<size; i++) {
         if (i>0) res += ",";
         res += elem[i];
      }
      res += "}";
      return res;
   }
}

// -----------------------------------------------------------
// Estruturas de Dados 2019/2020 (CC1007) - DCC/FCUP
// http://www.dcc.fc.up.pt/~pribeiro/aulas/edados1920/
// -----------------------------------------------------------
// Exemplo de utilizacao do TAD Conjunto
// Ultima alteracao: 10/03/2018
// -----------------------------------------------------------

public class TestSet {
   public static void main(String[] args) {
      IntSet s = new ArrayListIntSet(100); // Cria um conjunto com espaco para 100 inteiros

      System.out.println(s);
      System.out.println(s.add(1));
      System.out.println(s.add(5));
      System.out.println(s.add(7));
      System.out.println(s);
      System.out.println(s.contains(1));
      System.out.println(s.contains(2));
      System.out.println(s.add(1));
      System.out.println(s.size());
      System.out.println(s.remove(5));
      System.out.println(s.remove(5));
      System.out.println(s);
      s.clear();
      System.out.println(s);
      System.out.println(s.size());
   }
}