[JAVA] Accesso a lista

[zanardi84]

Ciao a tutti.
Ho una classe che implementa una lista semplice con alcuni metodi.
In dettaglio ho al suo interno una classe che definisce il tipo del nodo dichiarato come private.
Tra i metodi disponibili ho l'inserimento e l'eliminazione, ma non un semplice scorrimento con accesso ai contenuti dei nodi che compongono la lista.
La classe non implementa l'interfaccia Iterable.
Devo trovare, se possibile, un modo per accedere alla lista esternamente.
Cosa posso fare?

[banryu79]

Originariamente inviato da zanardi84

...
In dettaglio ho al suo interno una classe che definisce il tipo del nodo dichiarato come private.
...
La classe non implementa l'interfaccia Iterable.
Devo trovare, se possibile, un modo per accedere alla lista esternamente.

Immagino tu non abbia potuto implementare Itarable e il metodo iterator perchè appunto il tipo degli elementi/nodi della lista è privato?
Ma allora come hai implementato inserimento e rimozione di un elemento della lista?
Prova a postare il codice.

[zanardi84]

Il codice della classe che ho a disposizione è questo

import java.util.EmptyStackException;

public class Coda<E>
{
	private Nodo testa, coda;
	
	
	// definisco il nodo che compone la coda.
	private class Nodo
	{
		E oggetto;
		Nodo successivo;
	}
	
	// Costruttore: crea una nuova coda vuota
	public Coda()
	{
		testa = coda = null;
	}
	
	// metodo per aggiungere un oggetto alla coda
	public void aggiungi(E oggetto)
	{
		// prima creo il nodo, poi lo aggancio alla coda.
		Nodo t = new Nodo();
		t.oggetto = oggetto;
		t.successivo = null; // pongo a null perchè inserisco in coda.
		
		// inserisco in coda alla lista
		if(testa == null)
		{
			testa = coda = t; // il nodo è sia testa che coda perchè è unico essendo il primo
		}
		else
		{
			coda.successivo = t; // la vecchia coda punta adesso a t
			coda = t; // t diventa la nuova coda.
		}
	}
	
	// metodo per prelevare un oggetto dalla coda
	public E estrai()
	{
		if(testa == null)
			throw new EmptyStackException();
		else
		{
			E estratto = testa.oggetto; // estraggo
			testa = testa.successivo; // cambio la testa
			if(testa == null) // se la coda resta vuota?
			{
				coda = null;
			}
			return estratto;
		}
	}
}

[banryu79]

Della serie: meglio tardi che mai

Ho trovato il tempo di buttare giù un esempio, prova a vedere se ti può servire per chiarire alcuni dubbi. Comunque immagino che tu abbia già risolto, e che la soluzione sia simile.

Ho definito un'interfaccia Queue:

package collections;

import java.util.Iterator;

/**
 * Interface of a FIFO data structure.
 * Null elements are not allowed, duplicated elments are.
 * Iterator must run in insertion order (FIFO).
 * 
 * @author francesco
 */
public interface Queue<T> extends Iterable<T> {

    @Override Iterator<T> iterator();
    
    /**
     * Returns the size of this queue
     * @return the number of elements in this queue
     */
    int size();
    
    /**
     * Check if the queue is empty.
     * @return true if the queue is empty
     */
    boolean isEmpty();

    /**
     * Insert an element in this queue. Throws an 
     * IllegalArgumentException if element is null
     * @param elem the element to insert into the queue
     */
    void put(T elem);

    /**
     * Take an element (in FIFO order) from the queue. Throws an
     * IllegalStateException if the queue is empty
     * @return
     */
    T take();
    
    /**
     * Check if the queue contains the given elem
     * @param elem the element to check
     * @return true if elem is contained in the queue
     */
    boolean contains(T elem);
}

Poi ho definito di pari passo sia dei test per aiutarmi nell'implementazione della classe, che la classe stessa. La classe implementa la coda con una lista doppiamente linkata, come nel tuo esempio:

I test:

package collections;

import java.util.ConcurrentModificationException;
import org.junit.Assert;
import static org.junit.Assert.*;
import org.junit.Test;

/**
 * Unit test for linked list implementation of the Queue interface.
 * @author francesco
 */
public class LinkedQueueTest {
    
//    @Before
//    public void setUp() {
//    }
    
//    @After
//    public void tearDown() {
//    }

    @Test
    public void constructEmptyQueue() {
        Queue<String> q = new LinkedQueue<>();
        assertEquals(0, q.size());
    }
    
    @Test(expected=IllegalArgumentException.class)
    public void shouldFailPuttingNullElements() {
        Queue<String> q = new LinkedQueue<>();
        String nullString = null;
        q.put(nullString);
    }
    
    @Test
    public void putSomeElements() {
        Queue<String> q = new LinkedQueue<>();
        q.put("Item 1");
        Assert.assertEquals(1, q.size());
        q.put("Item 2");
        Assert.assertEquals(2, q.size());
        q.put("Item 3");
        Assert.assertEquals(3, q.size());
    }
    
    @Test(expected=IllegalStateException.class)
    public void shouldFailTakingFromEmptyQueue() {
        Queue<String> q = new LinkedQueue<>();
        String it = q.take();
    }
    
    @Test
    public void takeSomeElements() {
        Queue<String> q = new LinkedQueue<>();
        q.put("Item 1");
        q.put("Item 2");
        q.put("Item 3");
        String it = q.take();
        Assert.assertEquals(2, q.size());
        Assert.assertEquals("Item 1", it);
        it = q.take();
        Assert.assertEquals(1, q.size());
        Assert.assertEquals("Item 2", it);
        it = q.take();
        Assert.assertEquals(0, q.size());
        Assert.assertEquals("Item 3", it);
    }
    
    @Test
    public void iterateEmptyQueue() {
        Queue<Integer> q = new LinkedQueue<>();
        int sum = 0;
        for (Integer i : q) {
            sum += i;
        }
        assertEquals(0, sum);
    }
    
    @Test
    public void iterateFullQueue() {
        Queue<Integer> q = new LinkedQueue<>();
        q.put(1);
        q.put(2);
        q.put(3);
        q.put(4);
        q.put(5);
        int sum = 0;
        for (Integer i : q) {
            sum += i;
        }
        assertEquals(15, sum);
    }
    
    @Test(expected=ConcurrentModificationException.class)
    public void shouldFailDuringIterationOnConcurrentModification() {
        final Queue<Integer> q = new LinkedQueue<>();
        q.put(1);
        q.put(2);
        q.put(3);
        q.put(4);
        q.put(5);
        boolean doConcurrentModification = true;
        for (Integer i : q) {
            if (doConcurrentModification) {
                doConcurrentModification = false;
                q.put(99);
            }
        }
    }
    
    @Test
    public void isEmptyProperty() {
        Queue q = new LinkedQueue();
        assertTrue(q.isEmpty());
        q.put(new Object());
        assertFalse(q.isEmpty());
        q.take();
        assertTrue(q.isEmpty());
    }
    
    @Test
    public void lookForContainedElement() {
        Queue<Integer> q = new LinkedQueue<>();
        q.put(1);
        q.put(2);
        q.put(3);
        q.put(4);
        q.put(5);
        assertTrue(q.contains(3));
    }
    
    @Test
    public void lookForMissingElement() {
        Queue<Integer> q = new LinkedQueue<>();
        q.put(1);
        q.put(2);
        q.put(3);
        q.put(4);
        q.put(5);
        assertFalse(q.contains(9));
    }
}

E infine la classe (qui puoi vedere l'implementazione dell'iteratore)

package collections;

import java.util.ConcurrentModificationException;
import java.util.Iterator;

/**
 * Double linked list implementation of the Queue interface.
 * 
 * @author francesco
 */
public class LinkedQueue<T> implements Queue<T> {
    
    /**
     * The queue is implementd as a double linked list of nodes.
     * @param <T> the type of the elements in the Queue.
     */
    private final class Node<T> {
        private Node<T> prev;
        private Node<T> next;
        private final T data;
        Node(T elem) {
            data = elem;
        }
    };
    
    private int modCount = 0;
    
    private int size = 0;
    
    private Node head = null;
    
    private Node tail = null;
    
    @Override public int size() {
        return size;
    }
    
    @Override public void put(T elem) {
        if (elem == null) {
            throw new IllegalArgumentException("Null elements not allowed.");
        }
        
        Node<T> nnew = new Node<>(elem);
        
        if (head == null) {//empty queue
            head = nnew;
            tail = nnew;
        } else {
            nnew.prev = tail;
            tail.next = nnew;
            tail = nnew;
        }
        
        size++;
        modCount++;
    }
     
    @Override public T take() {
        if (size == 0) {
            throw new IllegalStateException("Queue is empty.");
        }
        
        Node<T> first = head;
        
        if (head == tail) {//only one elem
            head = tail = null;
        } else {
            head = first.next;
            head.prev = null;
        }
        
        size--;
        modCount++;
        
        return first.data;
    }
    
    @Override public boolean contains(T elem) {
        if (elem != null) {
            for (T it : this)
                if (it.equals(elem)) 
                    return true;
        }
        return false;
    }
    
    @Override public boolean isEmpty() {
        return size == 0;
    }
    
    @Override public Iterator<T> iterator() {
        return new Iterator<T>() {

            private Node current = LinkedQueue.this.head;
            private final int modCount = LinkedQueue.this.modCount;
            
            @Override public boolean hasNext() {
                return current != null;
            }

            @Override public T next() {
                if (modCount != LinkedQueue.this.modCount) {
                    throw new ConcurrentModificationException();
                }
                
                Node<T> next = current;
                current = current.next;
                return next.data;
            }

            @Override public void remove() {
                throw new UnsupportedOperationException("Remove operation not supported.");
            }
        };
    }
}

Spero ti sia utile, ciao.