Implementare una NodePositionList

[Bombonera]

Salve a tutti,

Il libro mi da il codice per creare una lista doppiamente concatenata. La nuova cosa è che io in questa lista posso accedere a qualunque nodo. In pratica l'elemento di un nodo è anche indice del nodo.

Però non ho capito i passi che ha fatto il libro per arrivare alla soluzione. Cioè ha implementato una interfaccia:

public interface Position<E> 
{
	E element();
}

Ora questa interfaccia la implementa nella classe del Nodo

Public class DNode<E> implements Position<E>
{
     ....................................................

     public E element() 	{
		if((prev==null) && (next == null))
		     throw new InvalidPositionException("La posizione non è in una lista");
		return element;
	}

     .......................................................
}

Ora nella classe NodePositionList io ad esempio posso accedere al nodo che segue il nodo nella posizione p:

// restituisce la posizione dell'elemento che segue l'elemento in posizione p
	public Position<E> next(Position<E> p)

Il metodo ha come parametro Position<E> p. Che sarebbe ? nodo.element() ?
Perché restituendo un elemento accedo al nodo che contiene quel elemento ?

p non è un puntatore che punta all'elemento selezionato ?
Non so se so stato chiaro.

[Bombonera]

Posto il codice

public class NodePositionList<E> 
{
	
	protected int size;
	protected DNode<E> header, trailer;
	
	public NodePositionList()
	{
		header = new DNode<E>(null, null, null);
		trailer = new DNode<E>(header, null, null);
		header.setNext(trailer);
		size = 0;
	}
	
	public int size()
	{
		return size;
	}
	
	public boolean isEmpty()
	{
		return (size == 0);
	}
	
	public Position<E> first()
	{
		if(isEmpty())
			throw new EmptyListException("La lista è vuota");
		return header.getNext();
	}
	
	public Position<E> last()
	{
		if(isEmpty())
			throw new EmptyListException("La lista è vuota");
		return trailer.getPrev();
	}
	
	protected DNode<E> checkPosition(Position<E> p)
	{
		if(p == null) throw new InvalidPositionException("Nulla passato come posizione");
		if(p == header) throw new InvalidPositionException("header non è una posizione valida nella lista");
		if(p == trailer) throw new InvalidPositionException("trailer non è una posizione valida nella lista");
		
		try
		{
			DNode<E> temp = (DNode<E>) p;
			if((temp.getPrev() == null) || (temp.getNext() == null))
				throw new InvalidPositionException("La posizione non fa parte della lista");
			return temp;
		}
		catch(ClassCastException e)
		{
			throw new InvalidPositionException("Il tipo della posizione non è valido in questa lista");
		}
	}
	
	public Position<E> prev(Position<E> p)
	{
		DNode<E> v = checkPosition(p);
		DNode<E> prev = v.getPrev();
		
		if(prev == header)
			throw new BoundaryViolationException("Non posso retrocedere oltre l'inizio della lista");
		return prev;
	}
	
	public Position<E> next(Position<E> p)
	{
		DNode<E> v = checkPosition(p);
		DNode<E> next = v.getNext();
		
		if(next == trailer)
			throw new BoundaryViolationException("Non posso avanzare oltre la fine della lista");
		
		return next;
	}
	
	public void addAfter(Position<E> p, E e)
	{
		DNode<E> v = checkPosition(p);
		size++;
		DNode<E> newNodo = new DNode<E>(v, v.getNext(), e);
		v.getNext().setPrev(newNodo);
		v.setNext(newNodo);
	}
	
	public void addBefore(Position<E> p, E e)
	{
		DNode<E> v = checkPosition(p);
		size++;
		DNode<E> newNodo = new DNode<E>(v.getPrev(), v, e);
		v.getPrev().setNext(newNodo);
		v.setPrev(newNodo);
	}
	
	public void addFirst(E e)
	{
		size++;
		DNode<E> newNodo = new DNode<E>(header, header.getNext(), e); 
		header.getNext().setPrev(newNodo);
		header.setNext(newNodo);
	}
	
	public void addLast(E e)
	{
		size++;
		DNode<E> newNodo = new DNode<E>(trailer.getPrev(), trailer, e);
		trailer.getPrev().setNext(newNodo);
		trailer.setPrev(newNodo);
	}
	
	public E remove(Position<E> p)
	{
		DNode<E> v = checkPosition(p);
		size--;
		DNode<E> vPrev = v.getPrev();
		DNode<E> vNext = v.getNext();
		vPrev.setNext(vNext);
		vNext.setPrev(vPrev);
		E element = v.element();
		v.setNext(null);
		v.setPrev(null);
		return element;
	}


}

[Bombonera]

Non ho capito Position<E> cosa rappresenta.

[andbin]

Non ho capito Position<E> cosa rappresenta.

Position è la interfaccia (che hai postato all'inizio) che rappresenta una "astrazione" per ottenere un elemento, cioè in questo caso il valore di un nodo.

[Bombonera]

Position è la interfaccia (che hai postato all'inizio) che rappresenta una "astrazione" per ottenere un elemento, cioè in questo caso il valore di un nodo.

Perché utilizzare una interfaccia quando posso passare per parametro un riferimento ad un elemento di tipo DNode ? Poi non ho capito qual è il meccanismo che mi fa accedere ad un nodo della lista ? Con Position<E> io non passo l'elemento di un nodo ?

[andbin]

Perché utilizzare una interfaccia quando posso passare per parametro un riferimento ad un elemento di tipo DNode ?

Se noti, i metodi che ricevono e/o restituiscono un nodo (first, last, prev, addAfter ecc...) hanno come ritorno/parametro un Position<E> (l'astrazione) e non DNode<E> (la implementazione concreta).
Questo perché così, "vedendo" un nodo solo come Position, non puoi accedere/toccare i prev/next del nodo. Insomma, la astrazione ti nasconde il modo in cui i nodi vengono incatenati. E questo di per sé è un bene, perché non puoi sballare la lista.

Poi è chiaro che l'esempio è basilare e solo "didattico". La classe DNode infatti è pubblica e tu "sai" che tutti i nodi sono realmente dei DNode, quindi nessuno ti impedisce di fare es. first() poi fare un cast a DNode<TipoSpecifico> (se hai fatto un NodePositionList<String>, avrai DNode<String>) e poi andare a danneggiare i next/prev nella lista come ti pare.

La classe NodePositionList infatti si aspetta solo dei DNode, infatti c'è un cast in checkPosition:

DNode<E> temp = (DNode<E>) p;

Quindi il senso della astrazione è proprio solo quello "didattico" di mostrare che Position offre solo il valore nascondendo il modo di incatenamento dei nodi. La interfaccia non è quindi intesa per poter avere N altre implementazioni (perlomeno rispetto a NodePositionList).

Poi non ho capito qual è il meccanismo che mi fa accedere ad un nodo della lista ? Con Position<E> io non passo l'elemento di un nodo ?

Se fai un first() ottieni un nodo, il primo. Materialmente sarà un DNode ma tu lo "vedi" solo come Position. Se vuoi il successivo devi invocare next della lista che ti fornisce il successivo. Proprio perché Position non ti fornisce appigli in tal senso.

[Bombonera]

Allora prima di tutto ti ringrazio per l'aiuto che mi stai dando.

Vediamo se ho capito

il metodo addAfter ha come primo parametro Position<E>. Come primo parametro gli passo a addAfter l'elemento che viene prima di lui e non il nodo.

Metto il codice:

lista.addFirst(5);
lista.addAfter(lista.first(), 8);

lista.addAfter prende in input header.getNext, quindi il riferimento del nodo che lo precede nella lista. Però siccome il primo parametro accetta Position<E> che è una estrazione del DNode<E>, il metodo addAfter lo "vede" solo come elemento che in questo caso è 5. Poi se tutto va bene viene fatto il cast su p per scoprire l'implementazione dell'intero nodo. In questo modo il nodo può essere modificato.

p che è una variabile di tipo Position<E> ha lo stesso indirizzo di DNode<E> giusto ?

Quindi l'obiettivo è quello di far vedere la lista come una lista di elementi e non di nodi.

Dico bene oppure sto dicendo un mucchio di cretinate

[Bombonera]

Finalmente ho capito tutto. Non era un fatto logico ma tecnico, purtroppo è da poco che programmo ad oggetti. Il tuo intervento è stato prezioso. Grazie mille.