Quiesta classe fornisce un insieme di metodi statici: non e' pensata per essere istanziata.
Riportiamo nel seguito lo "scheletro" della classe (sara' vostra cura riempirlo).
class MyArrayOfIntUtil
{
/*
In questo modo (cioe' dichiarando il costruttore come private}
si impedisce di
costruire oggetti appatenenti a questa classe
*/
private MyArrayOfIntUtil(){}
/*
AI: a != null
AF: restituisce il numero di volte che "e occorre in a"
*/
public static int howMany(int[] a, int e)
{
// NOTA: questo non e' il vero corpo del metodo,
// e' un corpo "fittizio" il cui unico
// scopo e' quello di permettere di compilare
// la classe, e provare ad eseguire,
// di in volta in volta,
// i metodi che si scrivono
return 0;
}
/*
AI: a != null
AF: restituisce un nuovo array ottenuto da a eliminando
la prima occorrenza di e
*/
public static int[] deleteFirst(int[] a, int e)
{
// NOTA: questo non e' il vero corpo del metodo,
// e' un corpo "fittizio" il cui unico
// scopo e' quello di permettere di compilare
// la classe, e provare ad eseguire,
// di in volta in volta,
// i metodi che si scrivono
int[] c = new int[1];
c[0] = 0;
return c;
}
}
Scriviamo il corpo del primo metodo:
/*
AI: a != null
AF: restituisce il numero di volte che "e occorre in a"
*/
public static int howMany(int[] a, int e)
{
if (a==null) throw new IllegalArgumentException();
int counter = 0;
/*
0 <= i <= a.length
AND counter = numero di occorrenze di e in a[0..i-1]
*/
for (int i=0; i < a.length; i++)
if (a[i]==e) counter++;
return counter;
}
L'esempio precedente e' relativamente semplice: per scrivere il corpo del metodo non e' necessario scrivere altri metodi.
Consideriamo invece il metodo
/*
AI: a != null
AF: restituisce un nuovo array, ottenuto da a eliminando
la prima occorrenza di e
*/
public static int[] deleteFirst(int[] a, int e)
Da un'analisi del problema ci si rende conto che la scrittura di tale
metodo richiede di effettuare operazioni complesse come
ad esempio:
In tal caso e' bene scrivere metodi che si occupino di fare queste cose. Tali metodi dovranno essere "il piu' generici possibile" (in modo da poter essere riutilizzati anche in altre circostanze).
A tale scopo, a lezione abbiamo considerato i seguenti metodi:
/*
AI: a != null
AF: restituisce il minimo i tale che a[i]==x,
-1 altrimenti (se a[i]!=x per tutti gli i)
*/
public static int indexOfFirst(int[] a, int x)
/*
AI: a,b != null
AND n >= 0
AND firstA+n <= a.length
AND firstB+n <= b.length
AF: copia a[firstA], a[firstA+1],..., a[firstB+n-1]
in
b[firstB], b[firstB+1],..., b[firstB+n-1]
*/
public static void copy(int[] a, int firstA, int n, int[] b, int firstB)
Supponendo di avere a disposizione tali metodi,
possiamo scrivere il metodo deleteFirst:
/*
AI: a != null
AF: restituisce un nuovo array, ottenuto da a eliminando
la prima occorrenza di e
*/
public static int[] deleteFirst(int[] a, int e)
{
if (a==null)
throw new IllegalArgumentException();
int i = indexOfFirst(a,e);
int[] c;
if (i ==-1)
{
c = new int[a.length];
copy(a, 0, a.lenght, c, 0);
}
else
{
c = new int[a.length-1;]
copy(a, 0, i, c, 0);
copy(a, i+1, a.length-(i+1), c, i);
}
return c;
}
Ora possiamo completare il tutto scrivendo il metodo
indexOfFirst e il metodo copy:
/*
AI: a != null
AF: restituisce il minimo i tale che a[i]==x,
-1 altrimenti (se a[i]!=x per tutti gli i)
*/
public static int indexOfFirst(int[] a, int x)
{
if (a==null) throw new IllegalArgumentException();
/*
0 <= i <= a.length
AND per ogni j in {0,..,i-1}. a[j]!=x
*/
for (int i=0; i < a.length; i++)
if (a[i]==x) return i;
return -1;
}
/*
AI: a,b != null
AND n >= 0
AND firstA+n <= a.length
AND firstB+n <= b.length
AF: copia a[firstA], a[firstA+1],..., a[firstB+n-1]
in
b[firstB], b[firstB+1],..., b[firstB+n-1]
*/
public static void copy(int[] a, int firstA, int n, int[] b, int firstB)
{
if ((a==null)
|| (b==null)
|| (firstA+n > a.length)
|| (firstB+n > b.length))
throw new IllegalArgumentException();
/*
0 <= i <= n
AND per ogni j in {0,..,i-1}.
a[firstA+j] e' stato copiato in b[firstB+i]
*/
for (int i=0; i < n; i++)
b[firstB+i] = a[firstA+i];
}
/*
AI: a != null
AF: restituisce un indice i tale che a[i]==x,
-1 altrimenti (se a[i]!=x per tutti gli i)
*/
public static int binarySearch(int[] a, int x)
{
int lo=0;
int hi=a.length-1;
/*
IC: se esiste j tale che a[j]==x, allora lo <= j <= hi
*/
while (lo <= hi)
{
int i = (hi+lo)/2;
if (a[i] == x) return i;
else
if (a[i] < x) lo=i+1;
else
hi=i-1;
}
return -1;
}
Per eventuali chiarimenti rivolgersi ai docenti.
/*
AI: a != null
AF: restituisce un nuovo array ottenuto, da a eliminando
tutte le occorrenze di e
*/
public static int[] deleteAll(int[] a, int e)
/*
AI: a != null
AF: restituisce un nuovo'array ottenuto, da a eliminando
le prime n occorrenze di e
*/
public static int[] deleteFirst(int[] a, int e, int n)
/*
AI: a != null
AF: restituisce un nuovo'array ottenuto, da a eliminando
l'ultima occorrenza di e
*/
public static int[] deleteLast(int[] a, int e)
/*
AI: a != null
AF: restituisce un nuovo'array ottenuto, da a eliminando
le ultime n occorrenze di e
*/
public static int[] deleteLast(int[] a, int e, int n)
/*
AI: a != null
AF: restituisce un nuovo array, ottenuto da a eliminando
tutte le duplicazioni di elementi,
preservando la prima occorrenza di ciascun elemento
(esempio:
semplify({4,5,3,4,1}) restituisce {4,5,3,1})
*/
public static int[] simplify(int[] a, int e, int n)
/*
AI: a,b != null
AF: restituisce un nuovo array, ottenuto da a eliminando
tutte le occorrenze degli elementi di b
(se un elemento occorre piu' volte in a,
si devono eliminare tutte le sue occorrenze)
(esempio:
add({4,5,3,4,1},{3,7,4,7,1,1}) restituisce {5})
*/
public static int[] deleteAll(int[] a, int b[])
/*
AI: a,b != null
AF: restituisce un nuovo array, ottenuto da a aggiungendo in coda
gli elementi di b
che non accorrono in a
(se un elemento occorre piu' volte in b,
lo si deve aggiungere una volta sola)
(esempio:
add({4,5,3,4,1},{5,3,7,8,7,1}) restituisce {4,5,3,1,7,8})
*/
int[] add(int[] a, int[] b)