dimanche 3 juin 2018

Fail-Fast Iterator for an Stack

I want to implement a Fail-Fast Iterator to remove Entrys from my own List and test it on correct behaviour. The List holds Elements of the type MyEntry.

These Entrys hold an Generic Value and a reference to the next Entry.

class MyEntry<E>  {

    MyEntry<E> next;
    E o;

    MyEntry() {
        this(null, null);
    }

    MyEntry(E o) {
        this(o, null);
    }

    MyEntry(E o, MyEntry<E> e) {
        this.o = o;
        this.next = e;
    }
}

The List itself tracks its position with the pos Entry and behaves like a Stack. Now I would like to implement a fail-fast iterator that allows me to iterate over the List and remove Entrys instead of throwning an UnsupportedOperation Exception.

import java.util.Iterator;
import java.util.NoSuchElementException;

public class MyList<E> implements Cloneable, java.lang.Iterable {

    private MyEntry<E> begin;

    private MyEntry<E> pos;


    public MyList() {
        pos = begin = new MyEntry<E>();
    }


    public boolean empty() {
        return begin.next == null;
    }


    public boolean endpos() { 
        return pos.next == null;
    }


    public void reset() {
        pos = begin;
    }

    /**
     * Advances one step in this List.
     *
     * @throws NoSuchElementException if the last Entry of this List already has been reached.
     */
    public void advance() {
        if (endpos()) {
            throw new NoSuchElementException("Already at the end of this List");
        }
        pos = pos.next;
    }

    /**
     * Returns the actual element of this List.
     *
     * @return the actual element
     * @throws RuntimeException if the last Entry of this List already has been reached.
     */
    public E elem() {
        if (endpos()) {
            throw new NoSuchElementException("Already at the end of this List");
        }
        return pos.next.o;
    }

    /**
     * Inserts <code>o</code> in this List. It will be placed before the actual
     * element. After insertion the inserted element will become the actual
     * element.
     *
     * @param x the element to be inserted
     */
    public void add(E x) {
        MyEntry<E> newone = new MyEntry<E>(x, pos.next);

        pos.next = newone;
    }

    /**
     * Deletes the actual element of this List. The element after the actual
     * element will become the new actual element.
     *
     * @throws NoSuchElementException if the last Entry of this List already has been reached.
     */
    public void delete() {
        if (endpos()) {
            throw new NoSuchElementException("Already at the end of this List");
        }
        pos.next = pos.next.next;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            private MyEntry<E> it = null;

            @Override
            public boolean hasNext() {
                return pos != null;
            }
            @Override
            public E next() {
                if (it==null)
                    it = begin;
                else
                    it = it.next;
                return it.o;
            }
            @Override
            public void remove() {
                throw new UnsupportedOperationException();
            }
        };
    }

}

First of I found three cases which need to be handled.

  • The first one would be that i want to remove an Entry that has a previous and a next Entry. In that case the iterator should change the next element of the previous Entry to the next Entry, so the Entry that i want to delete gets skipped.
  • The second case would be the first Entry of the List. In that case the next Entry should be set as first.
  • The last case is that I delete the last Entry, in this case the previous Entrys next should be pointed to null.

I also already tried to implement an Iterator to my List and tested it with my test Class

public class MyListTest {

@Test
public void test() {

    MyList list = new MyList();

    list.add("a");
    list.add("b");
    list.add("c");

    while(list.iterator().hasNext()==true) {
        System.out.println(list);
    }

    list.iterator().remove();

    while(list.iterator().hasNext()==true) {
        System.out.println(list);
    }
}

}

But the output loops an c and doesnt even get to remove an Entry.

I am now stuck at the correct implementation of an Fast-Fail Iterator that can iterate over MyList and remove Entrys. Because i couldnt break it down to a single problem i made a list of a few questions that came up while i tried to implement the Iterator

  • Should the Iterator be implemented in the MyList class or should it be implemented in an own class?
  • How do i get the Iterator to advance over MyList like the advance() method did?
  • Is the while-loop in the test class convenient or should another method be used instead?

Aucun commentaire:

Enregistrer un commentaire