package LDL; 

public class ListaDiListe implements LDL {
    private LKnodo head = null;     // riferimento alla lista di liste
    private int countKey = 0;        // totale chiavi memorizzate 

    // post: ritorna true sse la lista di liste e' vuota
    public boolean isEmpty() {
	return head == null;
    }

    // post: svuota la lista di liste
    public void clear() {
	head = null;
	countKey = 0;
    } 


    // post: ritorna il numero delle chiavi nella lista delle chiavi
    public int sizeKey() {
	return countKey;
    }
    

    // pre: key non nullo
    // post: ritorna il numero di elementi della lista associata alla 
    //       chiave key; ritorna zero se key non e' presente nella lista 
    //       delle chiavi
    public int sizeElem(Object key) {
	LKnodo index1 = findPosKey(key);
	LEnodo index2;
	int count = 0;

        if (index1 != null && index1.key.equals(key)) {
	   index2 = index1.list; 
	   while (index2 != null) {
	      index2 = index2.next; 
	      count++;
	   }
	}
	return count;
    }




    // pre: key non nullo
    // post: ritorna il riferimento al primo record della lista delle chiavi, 
    //       in cui la chiave e' uguale a key; ritorna null se 
    //       tale record non esiste
    private LKnodo findPosKey(Object key) {
	LKnodo index = head;
	while (index != null && !index.key.equals(key))
	       index = index.next;
        return index;
    }


    // pre: l, ob non nulli
    // post: ritorna il riferimento al record che contiene ob nella
    //       lista di elementi di l; ritorna null se ob non e' presente
    private LEnodo findPosElem(LEnodo l, Object ob) {
	LEnodo index = l;
	while (index != null && !ob.equals(index.elem))
	       index = index.next;
        return index;
    }

    // pre: key, at non nulli
    // post: inserisce la coppia (key, at) nella lista di liste. Precisamente, se key
    //       e' gia' presente nella lista delle chiavi, aggiunge at alla lista degli 
    //       elementi associati (in testa). Se key non e' presente, aggiunge un nodo 
    //       per key nella lista delle chiavi (in testa) e un nodo per at nella 
    //       corrispondente lista degli elementi (sempre in testa)
    public void insert(Object key, Object at) {
        LKnodo index = findPosKey(key);

	if (index != null) // trovato!
	    index.list = new LEnodo(at, index.list);
	else  { // non trovato, inserimento in testa
	    head = new LKnodo(key, null, head, null);
	    head.list = new LEnodo(at,null);
	    countKey++;
	}
    }


    // pre: index non nullo
    // post: cancella il record puntato da index dalla lista delle chiavi
    private void deleteKey(LKnodo index) {

	if (index == head) { // cancellazione in testa
	   head = head.next;
	   if (head != null)
	      head.prev = null;
	}
	else if (index.next == null) // cancellazione in coda
                index.prev.next = null;
	     else { // cancellazione in mezzo
	        index.prev.next = index.next;
  	        index.next.prev = index.prev;
	     }
	countKey--;
    }

       
    // pre: key, at non nulli
    // post: cancella la prima occorrenza di at nella lista associata a key.
    //       Se la lista di elementi di key diventa vuota, cancella anche key
    //       dalla lista delle chiavi.
    //       Ritorna true se l'operazione e' andata a buon fine; false altrimenti
    public boolean delete(Object key, Object at) {
	LKnodo index1 = findPosKey(key);

	if (index1 == null)
	    return false; // key non presente

        LEnodo index2 = index1.list;
        LEnodo prec = null;
	while (index2 != null && !index2.elem.equals(at)) {
	    prec = index2;
	    index2 = index2.next;
	}

	if (index2 == null)
	    return false; // at non presente nella lista di attributi di key

	// cancellazione attributo
	if (prec == null) // cancellazione in testa
	    index1.list = index2.next;
	else 
	    prec.next = index2.next; 

	// eventuale cancellazione chiave
	if (index1.list == null)
	    deleteKey(index1);

	return true;
    }



    
    // pre: key non nulla
    // post: cancella key dalla lista delle chiavi (e tutti gli elementi 
    //       associati). Ritorna true se l'operazione e' andata a buon fine; 
    //       ritorna false altrimenti
    public boolean deleteKey(Object key) {
	LKnodo index = findPosKey(key);
	if (index != null) {
	    deleteKey(index);
	    return true;
	}
	else
	    return false;
    }


    // pre: at non nullo
    // post: cancella dalla lista di liste TUTTE le occorrenze dell'elemento at
    //       Cancella anche tutte le chiavi che restano prive di elementi
    public void deleteElem(Object at) {

	LKnodo index1 = head;
	LEnodo index2, prec = null;

	while (index1 != null) {
	    index2 = index1.list;
	    prec = null;
   	    while (index2 != null) {
		if (!index2.elem.equals(at))
	           prec = index2;
		else { // cancellazione elemento
		    if (prec == null)  // cancellazione in testa
	              index1.list = index2.next;
	           else 
	              prec.next = index2.next; 
		}	           
		index2 = index2.next; 
	    }

 	   // eventuale cancellazione chiave
	   if (index1.list == null)
	       deleteKey(index1); // non perde il riferimento next di index1

	   index1 = index1.next;
	}
    }


    // pre: key, at non nulli
    // post: ritorna true sse esiste un nodo della lista delle chiavi con 
    //       valore key e la cui lista degli elementi contiene at
    public boolean search(Object key, Object at) {
        LKnodo index = findPosKey(key);
        if (index != null)
           return (findPosElem(index.list, at) != null);
        else 
          return false;
    }


    // pre: key non nullo
    // post: ritorna true sse esiste un nodo della lista delle chiavi 
    //       con valore key 
    public boolean searchKey(Object key) {
	LKnodo index = findPosKey(key);
	return (index != null);
    }


    // pre: at non nullo
    // post: ritorna true sse esiste un nodo nelle liste degli elementi
    //       con valore at
    public boolean searchElem(Object at) {
	LKnodo index1 = head;
	LEnodo index2, prec = null;
        boolean trovato = false;
	while (index1 != null & !trovato)  
	    if (findPosElem(index1.list, at) != null)
		trovato = true;
	    else
		index1 = index1.next;
	return trovato;
    }


    // post: ritorna una stringa che rappresenta la lista di liste 
    //       come coppie (chiave, elemento) separate da uno spazio
    public String toString() {
        LKnodo index1 = head;
        LEnodo index2;
        String s = "";

        while (index1 != null) {
	   index2 = index1.list;
	   while (index2 != null) {
	      s = s + "(" + index1.key.toString() + "," + index2.elem.toString() + ") ";
	      index2 = index2.next;
	   }
	   s = s + "\n";
	   index1 = index1.next;
        }
        return s;
    }
    
}