import java.util.Arrays;
import java.util.LinkedList;


/**
 * Realizzazione della interfaccia Lista tramite strutture collegate
 * */

public class ListaLink implements Lista {

	/* nodo della lista: deve contenere l'elemento
     * ed il collegamento al successivo
     */
	protected static class Node {
		protected Object key;
		protected Node next;

		public Node(Object o) {
				key = o;
				next = null;
		}
	}
	
	private Node head; //inzio della lista
	private int nOggetti;//supporto

	
	public ListaLink(){
		head = null;
		nOggetti = 0;
	}
	
	@Override
	public Object get(int k) throws IndexOutOfBoundsException {
		if ((0 <= k) && (k < nOggetti)){
			Node aux = head;
			for (int i = 0; i < k; i++) {
				aux = aux.next;
			}
			return aux.key;
		} else {
			throw new IndexOutOfBoundsException("indice non valido : "+k);
		}
	}

	@Override
	public void insert(int k, Object u) throws IndexOutOfBoundsException {
		if ((k>=0)&&(k<=nOggetti)){
			Node nuovo = new Node(u);
			if (nOggetti==0){//primo oggetto da inserire
				head = nuovo;	
			} else {
				if (k==0){//inserimento in testa
					nuovo.next = head;
					head = nuovo;
				} else {
					Node aux = head; 	
					for (int i = 0; i < k-1; i++) {
						aux = aux.next;
					}
					nuovo.next = aux.next;
					aux.next = nuovo;
				}
			}
			nOggetti++;
		} else {
			throw new IndexOutOfBoundsException("indice non valido : "+k);
		}	
	} 	
		
	@Override
	public boolean isEmpty() {
		return (nOggetti==0);
	}

	@Override
	public int length() {
		return nOggetti;
	}

	@Override
	public Object remove(int k) throws IndexOutOfBoundsException {
	  System.out.println("Metodo da implmentare");
	  return null;
	}
	
	public int indexOf(Object o) {
		Node aux = head;
		for (int i = 0; i < nOggetti; i++) {
			if (aux.key.equals(o)){
				return i;
			}
			aux = aux.next;
		}		
		return -1;
	}

	public boolean remove(Object o){
		int index = indexOf(o);
		if (index == -1){
			return false;
		}
		remove(index);
		return true;
	}
	
	@Override
	public String toString() {
		String res = "";
		Node aux = head;
		for (int i = 0; i < nOggetti; i++) {
			res=res + aux.key + " ";
			aux = aux.next;
		}		
		return res;
	}
	
	public static void main(String[] args) {
		ListaLink a = new ListaLink();
		for (int i = 0; i<10; i++){
			a.insert(i,i);
		}
		System.out.println(a);
		
		a.insert(4, new Integer(100));
		System.out.println(a);
		
		for (int i = 0; i<10; i++){
			a.insert(10+i,10+i);
		}
		System.out.println(a);

		
		Object eliminato = a.remove(10);
		System.out.println("elemento in pos 10 eliminato : "+eliminato);
		System.out.println(a);
		
		eliminato = a.remove(0);
		System.out.println("elemento in pos 0 eliminato : "+eliminato);
		System.out.println(a);

		System.out.println("l'elemento 100 e' in posizione "+a.indexOf(100));
		System.out.println("elemento 100 eliminato : "+a.remove(new Integer(100)));
		System.out.println(a);
		
		System.out.println("l'elemento 9 e' in posizione "+a.indexOf(9));
		System.out.println("elemento 9 eliminato : "+a.remove(new Integer(9)));
		System.out.println(a);
		
		System.out.println("l'elemento 101 e' in posizione "+a.indexOf(9));
		System.out.println("elemento 9 eliminato : "+a.remove(new Integer(9)));
		System.out.println(a);
		
		
		Object[] x = a.toArray();
		System.out.println("array estratto dalla lista "+Arrays.toString(x));
		
		a.insert(5,a.get(0));
		a.insert(7,a.get(0));
		System.out.println(a);
		a.eliminaDoppi();
		System.out.println(a);

		a = new ListaLink();
		Lista b = a;
		a.insert(0,new Integer(1));
		a.insert(1,new Integer(2));


		System.out.println("a = "+a);
		System.out.println("b = "+b);


	}

	

	/**
	 * Ritorna un array contenente tutti gli elementi della lista dal primo all'ultimo
	 * 
	 * @return array di oggetti contenuti nella lista
	 * */
	private Object[] toArray(){
		System.out.println("metodo da implementare");
		return null;
	}

	/**
	 * Elimina tutte i doppioni dalla lista, 
	 * mantenendo solo la prima occorrenza di ogni elemento 
	 * versione alternativa che non modifica la lista su cui stiamo iterando.
	 * */
	private void eliminaDoppi() {
		System.out.println("metodo da implementare");
	}

	
	/**
	 * Confronta la lista oggetto di invocazione con l'oggetto passato come parametro obj. 
	 * Restituisce true se obj e' una Lista e se gli oggetti in possizioni corrispondenti sono uguali.
	 * Altrimenti restituisce false
	 *
         * @param obj oggetto da confrontare con l'oggetto di invocazione
	 * @return true se la lista oggetto di invocazione e' uguale alla lista passata come prametro, false altrimenti
	 * */
	@Override
	public boolean equals(Object obj) {
		System.out.println("metodo da implementare");
		return false;
	}



	
}