Insiemi

Gli array permettono di rappresentare sequenze indicizzate di elementi

Gli insiemi sono diversi:

• un elemento non può trovarsi più di una volta in un insieme
• non c'è un ordine/indice negli elementi dell'insieme
• gli insiemi possono avere dimensione variabile

Possiamo rappresentare insiemi usando array

Idea di base

memorizzo gli elementi nel vettore

Devo tenere presente le caratteristiche dei vettori:

1. dimensione fissa
2. accesso per indice
3. più elementi uguali

Soluzione: incapsulamento!

Operazioni sugli insiemi

• creare un insieme vuoto
• verificare se l'insieme è vuoto
• aggiungere un elemento all'insieme
• togliere un elemento all'insieme
• verificare se un elemento si trova nell'insieme

Da questo, ricavo la definizione dei metodi della classe

Metodi della classe

Per insiemi di interi:

Insieme()

costruttore: genera l'insieme vuoto

boolean verificaVuoto()

ritorna un booleano, che dice se l'insieme è vuoto

void inserisci(int)

inserisce un elemento nell'insieme

void elimina(int)

elimina un elemento dall'insieme

boolean presente(int)

verifica se un elemento si trova nell'insieme

Manca un modo per fare la scansione dell'insieme

Per ora, mettiamo solo un metodo di stampa

Dimensione fissata

Ogni volta che devo inserire un elemento, creo un nuovo array, più grande di uno

Ogni volta che elimino un elemento, creo un nuovo vettore, più piccolo

La classe

La classe si presenta in questo modo:

class Insieme {
  private int elementi[];

  Insieme() { ... }
  void stampa() { ... }
  boolean verificaVuoto() { ... }
  boolean presente(int x) { ... }
  void inserisci(int x) { ... }
  void elimina(int x) { ... }
}

Implementiamo i metodi uno per volta

Il costruttore

Deve creare l'insieme vuoto

È il vettore che ha zero elementi

  Insieme() {
    this.elementi=new int[0];
  }

Domanda: this.elementi=null è lo stesso?

Array vuoto e null

Non sono la stessa cosa:

Con new si crea comunque un oggetto, anche se poi non ha nessuna componente

Vantaggio: posso usare this.elementi.length se this.elementi è l'array vuoto

Se this.elementi è null, allora non esiste nemmeno la componente length

Stampa l'insieme

Devo stampare il vettore

  void stampa() {
    int i;
    for(i=0; i<this.elementi.length; i++)
      System.out.println(this.elementi[i]);
  }

Se l'insieme vuoto lo rappresento con null:

this.elementi era null

Quindi, this.elementi.length è un errore

Invece l'array vuoto ha this.elementi.length==0.

La condizione è subito falsa, e non si esegue mai il corpo del ciclo

Verifica insieme vuoto

L'insieme è vuoto se l'array ha zero elementi

  boolean verificaVuoto() {
    return this.elementi.length==0;
  }

Presenza nell'insieme

Faccio la scansione del vettore

  boolean presente(int x) {
    int i;

    for(i=0; i<this.elementi.length; i++)
      if(this.elementi[i]==x)
        return true;

    return false;
  }

Inserimento di un elemento

Devo tenere presente che:

1. un elemento non può stare due volte in un insieme
2. l'array ha una dimensione fissata

Soluzione:

1. prima verifico se l'elemento già sta nell'insieme
2. creo un nuovo vettore, più grande di uno

Inserimento: verifica

Per controllare se l'elemento sta già nell'insieme, posso usare il metodo presente

  void inserisci(int x) {
    if(this.presente(x))
      return;

    // aggiungi l'elemento
  }

Inserimento: creazione nuovo array

L'array attuale ha dimensione this.elementi.length

Ne creo uno più grande di uno:

  void inserisci(int x) {
    if(this.presente(x))
      return;

    int nuovo[];
    nuovo=new int[this.elementi.length+1];

    // copia e aggiungi
  }

Inserimento: copiatura

Tutti gli elementi del vecchio array vanno nel nuovo:

  void inserisci(int x) {
    if(this.presente(x))
      return;

    int nuovo[];
    nuovo=new int[this.elementi.length+1];

    int i;
    for(i=0; i<this.elementi.length; i++)
      nuovo[i]=this.elementi[i];

    // aggiungi
  }

Perchè una nuova variabile?

Cosa succede se faccio direttamente:

  void inserisci(int x) {
    if(this.presente(x))
      return;

    this.elementi=new int[this.elementi.length+1];

    //
  }

Il nuovo vettore viene creato vuoto
(tutti gli elementi sono zero)

Ho perso il riferimento al vecchio array
non posso più copiare i vecchi elementi

Inserimento: nuovo elemento

Il nuovo array ha una posizione libera (l'ultima)

Ci metto il nuovo elemento

  void inserisci(int x) {
    if(this.presente(x))
      return;

    int nuovo[];
    nuovo=new int[this.elementi.length+1];

    int i;
    for(i=0; i<this.elementi.length; i++)
      nuovo[i]=this.elementi[i];

    nuovo[nuovo.length-1]=x;

    // e ora?
  }

Nuovo al posto del vecchio

Situazione attuale:

Situazione che voglio ottenere:

Nuovo al posto di vecchio

Dal confronto: in this.elementi voglio l'indirizzo del nuovo array

L'indirizzo del nuovo array sta in nuovo

Basta fare this.elementi=nuovo;

  void inserisci(int x) {
    if(this.presente(x))
      return;

    int nuovo[];
    nuovo=new int[this.elementi.length+1];

    int i;
    for(i=0; i<this.elementi.length; i++)
      nuovo[i]=this.elementi[i];

    nuovo[nuovo.length-1]=x;

    this.elementi=nuovo;
  }

Metodo di eliminazione

Devo creare un nuovo vettore, più piccolo di uno

  int nuovo[];
  nuovo=new int[this.elementi.lenght-1];

Esempio:

Posso fare la copia come prima?

Non funziona se l'elemento da eliminare non è l'ultimo

Soluzioni?

Modo sbagliato

for(i=0; i<...; i++)
  if(this.elementi[i]!=x)
    nuovo[i]=this.elementi[i];

L'unica cosa che fa è lasciare vuota la posizione in cui stava prima l'elemento da eliminare

Se il ciclo arriva ad i=nuovo.length-1, l'ultimo non viene copiato.

Se arriva fino a i=nuovo.length, si usa nuovo[i] che non esiste

Soluzioni

1. cerco l'elemento
   copio in ordine gli elementi fino a quello precedente
   copio indietro di uno i successivi

   

2. copio gli elementi in ordine
   quando incontro quello da eliminare, al suo posto ci metto l'ultimo

   

Ora posso fare la copia nell'array nuovo

Eliminazione: controllo

Prima, controllo se l'elemento c'è:

  void elimina(int x) {
    if(!this.presente(x))
      return;

    // copia
  }

Eliminazione: sposto l'ultimo

Faccio un ciclo di copia

Quando trovo l'elemento da eliminare, copio l'ultimo

  void elimina(int x) {
    if(!this.presente(x))
      return;

    int nuovo[];
    nuovo=new int[this.elementi.length-1];

    int i;
    for(i=0; i<this.elementi.length-1; i++)
      if(this.elementi[i]==x)
        nuovo[i]=this.elementi[this.elementi.length-1];
      else
        nuovo[i]=this.elementi[i];

    this.elementi=nuovo;
  }

Spostamento di tutti gli elementi

Più complicato

Trovo la posizione dell'elemento da eliminare

Copio normalmente tutti quelli prima

Quelli dopo, li copio in una posizione indietro

  void elimina(int x) {
    if(!this.presente(x))
      return;

    int nuovo[];
    nuovo=new int[this.elementi.length-1];

    int pos=0;

    int i;
    for(i=0; i<this.elementi.length; i++)
      if(this.elementi[i]==x) {
        pos=i;
        break;
      }

    for(i=0; i<pos; i++)
      nuovo[i]=this.elementi[i];

    for(i=pos; i<nuovo.length; i++)
      nuovo[i]=this.elementi[i+1];

    this.elementi=nuovo;
  }
}

Vantaggio: si mantiene l'ordine degli elementi

Nel caso degli insiemi non serve

Si usa un meccanismo di questo tipo se voglio usare gli array per rappresentare sequenze di elementi (non insiemi) in cui l'ordine è importante

Insiemi di altri tipi

Se voglio fare un insieme di stringhe, devo fare un'altra classe

Devo riscrivere tutto, con la sola differenza che == diventa .equals

Ci torneremo

Copiatura degli array

Metodo System.arraycopy

Come si usa:

System.arraycopy(origine, posiniziale,
   destinazione, posfinale, numero);

Cosa passare:

origine

l'array da copiare

posiniziale

la posizione da cui iniziare la copia

destinazione

l'array in cui vanno copiati i valori

posfinale

la posizione in cui va messo il primo elemento da copiare

numero

quanti elementi copiare

Metodo di copia: esempio

  int v[]=new int[12];
  int k[]=new int[12];

  System.arraycopy(v, 3, k, 5, 4);

elementi da copiare:

quattro elementi, il primo è l'elemento tre di v (il quarto)

dove vengono copiati:

nel vettore k, a partire dalla posizione 5

Inserimento, con arraycopy

Devo copiare gli elementi dell'array vecchio in quello nuovo

  void inserisci(int x) {
    if(this.presente(x))
      return;

    int nuovo[];
    nuovo=new int[this.elementi.length+1];

    System.arraycopy(this.elementi, 0,
                     nuovo, 0,
                     this.elementi.length);

    nuovo[nuovo.length-1]=x;

    this.elementi=nuovo;
  }

Eliminazione, prima versione

Copio prima tutti gli elementi.

Poi, al posto di quello da eliminare, ci metto l'ultimo

  void elimina(int x) {
    if(!this.presente(x))
      return;

    int nuovo[];
    nuovo=new int[this.elementi.length-1];

    System.arraycopy(this.elementi, 0,
                     nuovo, 0,
                     this.elementi.length-1);

    int i;
    for(i=0; i<this.elementi.length-1; i++)
      if(this.elementi[i]==x) {
        nuovo[i]=this.elementi[this.elementi.length-1];
        break;
      }

    this.elementi=nuovo;
  }

Eliminazione, seconda versione

Prima trovo l'elemento da eliminare

Copio in ordine gli elementi prima

Copio gli elementi dopo

  void eliminaDue(int x) {
    if(!this.presente(x))
      return;

    int nuovo[];
    nuovo=new int[this.elementi.length-1];

    int pos=0;

    int i;
    for(i=0; i<this.elementi.length; i++)
      if(this.elementi[i]==x) {
        pos=i;
        break;
      }

    System.arraycopy(this.elementi, 0,
                     nuovo, 0,
                     pos);

    System.arraycopy(this.elementi, pos+1,
                     nuovo, pos,
                     this.elementi.length-pos-1);

    this.elementi=nuovo;
  }

Da dove viene fuori this.length-pos-1?

Come determinare...

Si fa in questo modo:

1. il numero di elementi da copiare aumenta con this.elementi.length e diminuisce con pos

2. dal momento che l'aumento/diminuzione è di uno per uno, la relazione è:

   numero_elem_da_copiare=this.elementi.length-pos+k
   

   Devo solo determinare il numero k

3. faccio la prova su un esempio:

   Qui ho

   • this.elementi.length=6
   • pos=2
   • il numero di elementi da copiare è 4

   Quindi, 4=6-2+k, ossia k=-1

4. verifico se il conto funziona sui casi limite (pos=0 e pos=this.elementi.lenght-1, poi this.elementi.lenght=0)

Classe completa

Rappresenta insiemi di interi

class Insieme {
  private int elementi[];

  Insieme() {
    this.elementi=new int[0];
  }

  void stampa() {
    int i;

    for(i=0; i<this.elementi.length; i++)
      System.out.println(this.elementi[i]);
  }

  boolean verificaVuoto() {
    return this.elementi.length==0;
  }

  boolean presente(int x) {
    int i;

    for(i=0; i<this.elementi.length; i++)
      if(this.elementi[i]==x)
        return true;

    return false;
  }

  void inserisci(int x) {
    if(this.presente(x))
      return;

    int nuovo[];
    nuovo=new int[this.elementi.length+1];

    int i;
    for(i=0; i<this.elementi.length; i++)
      nuovo[i]=this.elementi[i];

    nuovo[nuovo.length-1]=x;

    this.elementi=nuovo;
  }

  void elimina(int x) {
    if(!this.presente(x))
      return;

    int nuovo[];
    nuovo=new int[this.elementi.length-1];

    int i;
    for(i=0; i<this.elementi.length-1; i++)
      if(this.elementi[i]==x)
        nuovo[i]=this.elementi[this.elementi.length-1];
      else
        nuovo[i]=this.elementi[i];

    this.elementi=nuovo;
  }
}

Insiemi di altri tipi

Esempio: insieme di punti

L'unica cosa che cambia è che == diventa equals

import java.awt.*;

class InsiemePoint {
  private Point elementi[];

  InsiemePoint() {
    this.elementi=new Point[0];
  }

  void stampa() {
    int i;

    for(i=0; i<this.elementi.length; i++)
      System.out.println(this.elementi[i]);
  }

  boolean verificaVuoto() {
    return this.elementi.length==0;
  }

  boolean presente(Point x) {
    int i;

    for(i=0; i<this.elementi.length; i++)
      if(this.elementi[i].equals(x))
        return true;

    return false;
  }

  void inserisci(Point x) {
    if(this.presente(x))
      return;

    Point nuovo[];
    nuovo=new Point[this.elementi.length+1];

    System.arraycopy(this.elementi, 0,
                     nuovo, 0,
                     this.elementi.length);

    nuovo[nuovo.length-1]=x;

    this.elementi=nuovo;
  }

  void elimina(Point x) {
    if(!this.presente(x))
      return;

    Point nuovo[];
    nuovo=new Point[this.elementi.length-1];

    System.arraycopy(this.elementi, 0,
                     nuovo, 0,
                     this.elementi.length-1);

    int i;
    for(i=0; i<this.elementi.length-1; i++)
      if(x.equals(this.elementi[i])) {
        nuovo[i]=this.elementi[this.elementi.length-1];
        break;
      }

    this.elementi=nuovo;
  }
}

Altro esempio

Insieme di rettangoli

import java.awt.*;

class InsiemeRectangle {
  private Rectangle elementi[];

  InsiemeRectangle() {
    this.elementi=new Rectangle[0];
  }

  void stampa() {
    int i;

    for(i=0; i<this.elementi.length; i++)
      System.out.println(this.elementi[i]);
  }

  boolean verificaVuoto() {
    return this.elementi.length==0;
  }

  boolean presente(Rectangle x) {
    int i;

    for(i=0; i<this.elementi.length; i++)
      if(this.elementi[i].equals(x))
        return true;

    return false;
  }

  void inserisci(Rectangle x) {
    if(this.presente(x))
      return;

    Rectangle nuovo[];
    nuovo=new Rectangle[this.elementi.length+1];

    System.arraycopy(this.elementi, 0,
                     nuovo, 0,
                     this.elementi.length);

    nuovo[nuovo.length-1]=x;

    this.elementi=nuovo;
  }

  void elimina(Rectangle x) {
    if(!this.presente(x))
      return;

    Rectangle nuovo[];
    nuovo=new Rectangle[this.elementi.length-1];

    System.arraycopy(this.elementi, 0,
                     nuovo, 0,
                     this.elementi.length-1);

    int i;
    for(i=0; i<this.elementi.length-1; i++)
      if(x.equals(this.elementi[i])) {
        nuovo[i]=this.elementi[this.elementi.length-1];
        break;
      }

    this.elementi=nuovo;
  }
}

Ancora un altro

Insieme di stringhe

import java.awt.*;

class InsiemeString {
  private String elementi[];

  InsiemeString() {
    this.elementi=new String[0];
  }

  void stampa() {
    int i;

    for(i=0; i<this.elementi.length; i++)
      System.out.println(this.elementi[i]);
  }

  boolean verificaVuoto() {
    return this.elementi.length==0;
  }

  boolean presente(String x) {
    int i;

    for(i=0; i<this.elementi.length; i++)
      if(this.elementi[i].equals(x))
        return true;

    return false;
  }

  void inserisci(String x) {
    if(this.presente(x))
      return;

    String nuovo[];
    nuovo=new String[this.elementi.length+1];

    System.arraycopy(this.elementi, 0,
                     nuovo, 0,
                     this.elementi.length);

    nuovo[nuovo.length-1]=x;

    this.elementi=nuovo;
  }

  void elimina(String x) {
    if(!this.presente(x))
      return;

    String nuovo[];
    nuovo=new String[this.elementi.length-1];

    System.arraycopy(this.elementi, 0,
                     nuovo, 0,
                     this.elementi.length-1);

    int i;
    for(i=0; i<this.elementi.length-1; i++)
      if(this.elementi[i]==x) {
        nuovo[i]=this.elementi[this.elementi.length-1];
        break;
      }

    this.elementi=nuovo;
  }
}

Cosa cambia?

A parte il tipo, gli insiemi di oggetti sono identici

Generati (sotto Unix) con:

sed "s,Point,Rectangle,g"
InsiemePoint.java > InsiemeRectangle.java

sed "s,Point,String,g"
InsiemePoint.java > InsiemeString.java

Basta mettere Rectangle oppure String al posto di Point

Per gli oggetti, l'unica differenza è il nome del tipo

Si può definire una classe Insieme generico, che funziona per tutte le classi