public class MultiInsieme {
    private static final int defaultSize = 50;
    private String[] M;               // il multi-insieme e' un array
    private int count;                // tot. elementi del multi-insieme


    // post: costruisce un array di dimensione defaultSize
    public MultiInsieme() {
	count = 0;
        M = new String[defaultSize];
    }


    // post: ritorna il numero di elementi del multi-insieme
    public int size() {
        return count;
    }


    // post: ritorna true sse il multi-insieme e' vuoto
    public boolean isEmpty() {
        return count == 0;
    }


    // post: svuota il multi-insieme
    public void clear() {
        count = 0;
    }


    // pre:  s non nulla
    // post: aggiunge la stringa s al multi-insieme ponendola in coda
    //       all'array. Ritorna true se l'operazione e' riuscita, false 
    //       se non c'e' piu' spazio libero nell'array
    public boolean insert(String s) {
	
	if (count == defaultSize)
	    return false;

        M[count++] = s;
	return true;        
    }


    // pre:  s non nulla
    // post: ritorna true se nel multi-insieme c'e' un elemento uguale a s,
    //       false altrimenti
    public boolean contains(String s) {
        return (findPos(0, s) < count);
    }


    // pre: s non nulla
    // post: ritorna il numero di occorrenze di s nel multi-insieme
    public int occurrences(String s) {
	int occ = 0;
        int i = 0;
	// INV: M[0...i-1] contiene occ occorrenze di s
        do {  
	    i = findPos(i,s); 
	    if (i < count)
	       occ++;
	    i++;
	} while (i < count);
	return occ;
    }

    /*
    // pre: s non nulla
    // post: ritorna il numero di occorrenze di s nel multi-insieme
    public int occurrences(String s) {
	int occ = 0;
        int i = 0;
        while (i < count) {
            if (M[i].equals(s))
	       occ++;
	    i++;
	};
	return occ;
    }
    */

    // pre:  s non nulla, 0 <= k < count
    // post: ritorna la posizione della prima occorrenza di s nella porzione di
    //       array che parte da k; ritorna count se s non e' presente
    private int findPos(int k, String s) {
        int i;

        // l'array non e' ordinato. 
        // Si deve necessariamente eseguire una ricerca sequenziale
	// INV: M[k...i-1] non contiene s
	for (i = k ; i < count && !M[i].equals(s) ; i++);

        return i;

    }


    // post: ritorna il numero di elementi distinti del multi insieme
    public int distinct( ) {
	int d = 0;
	int i = 0;
	int j;
	boolean trovato;
        // INV: d e' il numero di elementi distinti in M{0..i-1] 
	while (i < count) {
            // INV: gli elementi di M[0...j-1] sono diversi da M[i]
	    for (j = 0; j<i && !M[i].equals(M[j]); j++);
	    if (j == i) // non trovato!
		d++;
	    i++;
	}
	return d;
    }


    // pre:  s non nulla
    // post: rimuove la prima occorrenza di s nell'array. 
    //       Ritorna true se l'operazione e' riuscita, false altrimenti
    //       (cioe' se s non e' presente nell'array)
    public boolean remove(String s) {

        int i = findPos(0, s);
        if (i == count)
	   return false;

	for (int j = i; j < count - 1; j++)
            M[j] = M[j+1];    
        count--;
	return true;
    }


    // post: ritorna una stringa contenente gli elementi del multi-insieme
    //       utilizza un spazio come separatore tra gli elementi
    public String toString() {
	String s = "";
        // INV: s contiene gli elementi di M[0...i-1] separati tra loro da uno spazio
        for (int i = 0; i < count; i++)
	    s = s + M[i] + " ";
        return s;
    }


}