Iterator für eine geordnete Menge

X

Xyz1

Gast
Nein, hatte ich nicht gelesen....
Man muss dazu sagen, dass es sich um einen Java doc handelt, der nur beschreibt, wie eine Klasse implementiert ist - und nur Empfehlungen ausspricht, wie eine das Interface implementierende Klasse zu implementieren wäre....
Möchte man das Interface anders implementieren, erwähnt man eben im eigenem Kommentar, dass zwingend neben compareTo() auch equals() konform zu compareTo() zu implementieren ist....
(So wird es auch bei vielen anderen Collections gehandhabt.)

Aber jetzt müsst ihr mir mal helfen, eine binäre Suche ist aufgrund der Verlinkungen nicht möglich oder? Man bleibt also so oder so bei O(n) beim Entfernen oder?
 

ocsme

Top Contributor
Ein letztes mal. So sieht jetzt die ganze Klasse aus. Wäre dort die remove(Object) Methode nun richtig? Irgendwie liest es sich komisch :D

Java:
class LinkedSetIterator implements Iterator<T> {
        Cell current;

        LinkedSetIterator() {
            current = anchor;
        }
        
        @Override
        public boolean hasNext() {
            return (current.succ != anchor);
        }

         public T next() {
                if (hasNext()) {
                    T next = (T) current.value;
                    current = current.succ;
                    return next;
                    
                }
                throw new IllegalStateException("No more elements");
            }
        
         public boolean remove(Object x) {
             while(hasNext()) {
                 Object next = next();
                 if(x.equals(next)) {
                     this.next();
                     this.remove();
                     return true;
                 }
             }
            
             return false;
         }
        
         public void remove() {
             current.pred.pred.succ = current;
             current.pred = current.pred.pred;
         }
        
    }
 
X

Xyz1

Gast
Wäre dort die remove(Object) Methode nun richtig
Nein, noch nicht....
Diese steht nun in dem Iterator, dass heißt, sie muss sich konform zu dem Iterator verhalten - und Du hast mit dem Iterieren im Iterator etwas übers Ziel hinaus geschossen...

Bearbeitung: Und da steht noch immer equals().... ;)
 
K

kneitzel

Gast
Aber jetzt müsst ihr mir mal helfen, eine binäre Suche ist aufgrund der Verlinkungen nicht möglich oder? Man bleibt also so oder so bei O(n) beim Entfernen oder?
Ja, das ist richtig. Und sorry - hatte nicht gesehen, dass da ja noch mehr Antworten auf einer weiteren Seite waren. Das Thema war ja bereits soweit abgehandelt...

@ocsme Ja, Dein Code wirkt etwas seltsam, da Du im if noch einmal next() aufrufst (Problem: was ist, wenn es kein nächstes Element gibt?) und Du daher current weiter gesetzt hast und dann current.pred.pred und so kommt. Das ist nicht ganz intuitiv lesbar finde ich.
 

ocsme

Top Contributor
o_O wieso ist hasNext() Falsch? ich Frage doch ab ob der current.zeiger != anchor ist. Wie sollte er sonst aussehen?
Und bei Next() was ist dort Falsch?

LG
 

mrBrown

Super-Moderator
Mitarbeiter
wieso ist hasNext() Falsch? ich Frage doch ab ob der current.zeiger != anchor ist. Wie sollte er sonst aussehen?
Und bei Next() was ist dort Falsch?
next und hasNext und der initialwert von current passen einfach nicht zusammen.

Zu Anfang ist current=anchor
hasNext prüft dann, ob es noch einen Nachfolger gibt, next gibt dann aber den aktuellen Wert von current (also im ersten Aufruf anchor) zurück.

Spiel das einfach mal mit einem Schreibtischtest mit einem Set mit einem Element durch ;)
 
X

Xyz1

Gast
@ocsme Nochmal...
Java:
public Iterator<T> iterator() {
	return new Iterator<T>() {

		Cell a = anchor;
		boolean b = true;

		@Override
		public boolean hasNext() {
			if (b && a.succ == anchor) {
				b = false;
				return a.value != null;
			}
			return b && a.value != null;
		}

		@Override
		public T next() {
			T t = (T) a.value;
			a = a.succ;
			return t;
		}

		@Override
		public void remove() {
			a.pred.pred.succ = a;
			a.pred = a.pred.pred;
		}

	};
}


ist nicht falsch, die Frage wäre nur, ob es noch kürzer ginge....

Zudem kannst Du remove() in LinkedSet auch beliebig/anders implementieren.
 
K

kneitzel

Gast
Was Du bei Tobias sehr gut sehen kannst ist die Implementation des Iterators. Implementiert auch genau den Iterator und macht nicht mehr. Ein eigener Iterator kann zwar mehr implementieren, aber wenn jemand später iterator() aufruft, erwartet diese Person lediglich einen Iterator mit genau diesen Funktionen.

Und das remove(obj) wird somit nicht vom Iterator erwartet sondern diese Funktion kommt von Deiner Hauptklasse.

Da ein Iterator hat tolle Funktionen, mit denen man diese Funktionalität abdecken kann:
Solange Elemente verfügbar sind holst Du Dir das nächste Element. Ist dieses das gesuchte Element rufst Du remove() auf und beendest den Durchgang.

Bei der Implementation, die Tobias jetzt eben noch mal gebracht hat, scheint das remove aber nicht korrekt zu sein. Das remove() der Iterator-Implementation soll das current Element löschen. Das bedeutet, dass danach das aktuelle Element (da "a" genannt) nicht mehr referenziert ist.

Daher müsste da sowas drin stehen wie:
a.pref.suc = a.suc; a.suc.pref = a.pref; Also der Nachfolger vom Vorgänger vom aktuellen Element wird zum Nachfolger des aktuellen Element.. Und der Vorgänger vom Nachfolger vom aktuellen Element wird zum Vorgänger des aktuellen Elements ....

Der Code selbst hätte für deine remove(obj) Methode aber wohl funktioniert, weil Du da nicht das aktuelle Objekt gelöscht hast sondern den Vorgänger. Aber wenn man die Iterator Implementation getestet hätte, dann wäre da ein Fehler aufgetreten.
 

mrBrown

Super-Moderator
Mitarbeiter
Bei der Implementation, die Tobias jetzt eben noch mal gebracht hat, scheint das remove aber nicht korrekt zu sein. Das remove() der Iterator-Implementation soll das current Element löschen. Das bedeutet, dass danach das aktuelle Element (da "a" genannt) nicht mehr referenziert ist.
Das „aktuelle“ Element ist dabei nicht a, sondern a.pred ;)
 
X

Xyz1

Gast
Ich habe die Tests nochmal umgeschrieben und einige Methoden der Klasse LinkedSet auch...
Kann bitte nochmal jemand danach sehen, die Tests werden grün, aber die Methoden removeAll() und iterToString() halten nicht mehr an. Mist...
Java:
import java.lang.reflect.Array;
import java.util.Collection;
import java.util.Comparator;
import java.util.Iterator;
import java.util.SortedSet;
import java.util.StringJoiner;

public class LinkedSet<T extends Comparable<T>> implements SortedSet<T> {
	public static void main(String[] args) {
		LinkedSet<Integer> s = new LinkedSet<>();
		System.out.println(iterToString(s.iterator()));
		for (int i = 0; i < 10; i++) {
			s.add((int) (Math.random() * 5.0));
			System.out.println(iterToString(s.iterator()));
		}

		s.clear();
		System.out.println(iterToString(s.iterator()));
		for (int i = 0; i < 10; i++) {
			s.add((int) (Math.random() * 5.0));
			System.out.println(iterToString(s.iterator()));
		}
	}

	public static String iterToString(Iterator<?> i) {
		StringJoiner j = new StringJoiner("; ");
		j.setEmptyValue("");
		while (i.hasNext())
			j.add(i.next().toString());
		return j.toString();
	}

	private class Cell {
		Object value;
		Cell pred, succ;
	}

	private Cell anchor;

	public LinkedSet() {
		anchor = new Cell();
		anchor.pred = anchor;
		anchor.succ = anchor;
	}

	public Iterator<T> iterator() {
		return new Iterator<T>() {

			Cell a = anchor;
			boolean b = true;

			@Override
			public boolean hasNext() {
				if (b && a.succ == anchor) {
					b = false;
					return a.value != null;
				}
				return b && a.value != null;
			}

			@Override
			public T next() {
				@SuppressWarnings("unchecked")
				T t = (T) a.value;
				a = a.succ;
				return t;
			}

			@Override
			public void remove() {
				if (size() == 1) {
					a.value = null;
					a.pred = a;
					a.succ = a;
				} else if (a == anchor) {
					anchor = a.succ;
					a.pred.pred.succ = a;
					a.pred = a.pred.pred;
				} else {
					a.pred.pred.succ = a;
					a.pred = a.pred.pred;
				}
			}

		};
	}

	@SuppressWarnings("unchecked")
	public boolean add(T e) {
		if (e == null) {
			throw new NullPointerException();
		}

		if (isEmpty()) {
			anchor.value = e;
		} else if (contains(e)) {
			return false;
		} else if (((Comparable<T>) e).compareTo((T) anchor.value) < 0) {
			anchor = insertBefore(anchor, e);
		} else {
			Cell current = anchor.succ;
			while (current != anchor && ((Comparable<T>) current.value).compareTo(e) < 0) {
				current = current.succ;
			}
			insertBefore(current, e);
		}
		return true;
	}

	private Cell insertBefore(Cell cell, T e) {
		Cell result = new Cell();
		result.value = e;
		result.pred = cell.pred;
		result.succ = cell;
		cell.pred.succ = result;
		cell.pred = result;
		return result;
	}

	@Override
	public boolean addAll(Collection<? extends T> c) {
		for (T t : c) {
			add(t);
		}
		return true;
	}

	@Override
	public void clear() {
		anchor.pred = anchor;
		anchor.succ = anchor;
		anchor.value = null;
	}

	@Override
	public boolean contains(Object o) {
		Iterator<T> i = iterator();
		while (i.hasNext())
			if (i.next().equals(o))
				return true;
		return false;
	}

	@Override
	public boolean containsAll(Collection<?> c) {
		for (Object o : c) {
			if (!contains(o))
				return false;
		}
		return true;
	}

	@Override
	public boolean isEmpty() {
		return anchor.value == null;
	}

	@SuppressWarnings("unchecked")
	@Override
	public boolean remove(Object o) {
		Iterator<T> i = iterator();
		while (i.hasNext())
			if (i.next().compareTo((T) o) == 0) {
				i.remove();
				return true;
			}
		return false;
	}

	@Override
	public boolean removeAll(Collection<?> c) {
		for (Object o : c) {
			if (!remove(o)) {
				return false;
			}
		}
		return true;
	}

	@Override
	public boolean retainAll(Collection<?> c) {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public int size() {
		if (isEmpty())
			return 0;
		int s = 0;
		Iterator<?> i = iterator();
		while (i.hasNext()) {
			s++;
			i.next();
		}
		return s;
	}

	@Override
	public Object[] toArray() {
		Object[] a = new Object[size()];
		int j = 0;
		Iterator<T> i = iterator();
		while (i.hasNext())
			a[j++] = i.next();
		return a;
	}

	@SuppressWarnings({ "hiding", "unchecked" })
	@Override
	public <T> T[] toArray(T[] a) {
		T[] b = (T[]) Array.newInstance(a.getClass().getComponentType(), size());
		int j = 0;
		Iterator<T> i = (Iterator<T>) iterator();
		while (i.hasNext())
			b[j++] = i.next();
		return b;
	}

	@Override
	public Comparator<? super T> comparator() {
		return (T a, T b) -> a.compareTo(b);
	}

	@SuppressWarnings("unchecked")
	@Override
	public T first() {
		return (T) anchor.value;
	}

	@Override
	public SortedSet<T> headSet(T arg0) {
		// TODO Auto-generated method stub
		return null;
	}

	@SuppressWarnings("unchecked")
	@Override
	public T last() {
		return (T) anchor.pred.value;
	}

	@Override
	public SortedSet<T> subSet(T fromElement, T toElement) {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public SortedSet<T> tailSet(T fromElement) {
		// TODO Auto-generated method stub
		return null;
	}
}


Java:
import static org.junit.jupiter.api.Assertions.*;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.Random;

import org.junit.jupiter.api.AfterEach;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

class LinkedSetTest {
	LinkedSet<Integer> set = null;

	@BeforeEach
	void setUp() throws Exception {
		set = new LinkedSet<Integer>();
	}

	@AfterEach
	void tearDown() throws Exception {
		set.clear();
		set = null;
	}

	@Test
	void testMain() {
		LinkedSet.main(null);
	}

	@Test
	void testIterToString() {
		testAdd();
		Iterator<Integer> i = set.iterator();
		assertNotNull(i);
		String s = LinkedSet.iterToString(i);
		assertNotNull(s);
		System.out.println(s);
	}

	@Test
	void testLinkedSet() {
		assertNotNull(set);
	}

	@Test
	void testIterator() {
		Iterator<Integer> i = set.iterator();
		assertNotNull(i);
		assertFalse(i.hasNext());
		assertTrue(set.add(new Random().nextInt(5)));
		i = set.iterator();
		assertNotNull(i);
		assertTrue(i.hasNext());
	}

	@Test
	void testAdd() {
		ArrayList<Integer> l = new ArrayList<>();
		for (int i = 0; i < 12; i++) {
			l.add(i);
		}
		for (int j = 0; j < 12; j++) {
			set.clear();
			assertTrue(set.isEmpty());
			Collections.shuffle(l);
			for (int i = 0; i < 12; i++) {
				assertTrue(set.add(l.get(i)));
				assertFalse(set.isEmpty());
			}
		}
	}

	@Test
	void testAddAll() {
		assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
		assertEquals("2; 3; 4", LinkedSet.iterToString(set.iterator()));
	}

	@Test
	void testClear() {
		set.clear();
		assertTrue(set.isEmpty());
	}

	@Test
	void testContains() {
		assertTrue(set.add(2));
		assertTrue(set.contains(2));
	}

	@Test
	void testContainsAll() {
		assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
		assertTrue(set.containsAll(Arrays.asList(2, 3, 4)));
		assertEquals("2; 3; 4", LinkedSet.iterToString(set.iterator()));
	}

	@Test
	void testIsEmpty() {
		assertTrue(set.isEmpty());
		assertTrue(set.add(1));
		assertFalse(set.isEmpty());
	}

	@Test
	void testRemove() {
		assertFalse(set.remove(2));
		assertTrue(set.add(2));
		assertTrue(set.remove(2));
		assertFalse(set.remove(3));
	}

	@Test
	void testRemoveAll() {
		assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
		assertEquals("2; 3; 4", LinkedSet.iterToString(set.iterator()));
		assertTrue(set.removeAll(Arrays.asList(2, 3, 4)));
		assertEquals("", LinkedSet.iterToString(set.iterator()));
	}

	@Test
	void testRetainAll() {
		fail("Not yet implemented");
	}

	@Test
	void testSize() {
		assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
		assertEquals(3, set.size());
		assertEquals("2; 3; 4", LinkedSet.iterToString(set.iterator()));
	}

	@Test
	void testToArray() {
		assertNotNull(set.toArray());
		assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
		assertNotNull(set.toArray());
		assertEquals("2; 3; 4", LinkedSet.iterToString(set.iterator()));
	}

	@Test
	void testToArrayTArray() {
		assertNotNull(set.toArray(new Integer[0]));
		assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
		assertEquals(3, set.toArray(new Integer[0]).length);
		assertEquals(Integer[].class, set.toArray(new Integer[0]).getClass());
		assertEquals("2; 3; 4", LinkedSet.iterToString(set.iterator()));
	}

	@Test
	void testComparator() {
		assertTrue(set.comparator() instanceof Comparator<?>);
	}

	@Test
	void testFirst() {
		assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
		assertEquals(2, set.first());
		assertEquals("2; 3; 4", LinkedSet.iterToString(set.iterator()));
	}

	@Test
	void testHeadSet() {
		fail("Not yet implemented");
	}

	@Test
	void testLast() {
		assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
		assertEquals(4, set.last());
		assertEquals("2; 3; 4", LinkedSet.iterToString(set.iterator()));
	}

	@Test
	void testSubSet() {
		fail("Not yet implemented");
	}

	@Test
	void testTailSet() {
		fail("Not yet implemented");
	}
}
 

mrBrown

Super-Moderator
Mitarbeiter
die Tests werden grün, aber die Methoden removeAll() und iterToString() halten nicht mehr an
Das widerspricht sich doch....


Zu removeAll: wenn das nicht anhält, ist remove(Object o) falsch - und wenn die nicht anhält, ist der iterator falsch. Also würde ich den an deiner Stelle einfach mal gesondert testen.
Gleiches gilt für iterToString.


Abgesehen davon sind da noch einige verstoße gegen das Set-Interface drin, mindestens in removeAll ("fail fast"), first und last (die beide eine Exception schmeißen müssten), und in contains (das sollte compareTo nutzen).



(BTW, setUp und tearDown brauchst du in diesem Fall nicht, kannst das Feld auch direkt initialisieren und aufräumen musst du nichts)
 
X

Xyz1

Gast
remove() im Iterator ist falsch. Da müssen zusätzliche Fälle bedacht werden, wenn der Anker entfernt werden soll. Das ist mir erst aufgefallen, nachdem ich die Tests umschrieb...

UNd glaub mir, das ist Eclipse... und das kann auch nicht anhalten, wenngleich alle Tests "grün" werden.
 
X

Xyz1

Gast
Geschafft!
Java:
            @Override
            public void remove() {
                if (size() == 1) {
                    a.value = null;
                    a.pred = a;
                    a.succ = a;
                } else {
                    if (a.pred == anchor) {
                        anchor = a;
                    }
                    a.pred.pred.succ = a;
                    a.pred = a.pred.pred;
                }
            }


Java:
import java.lang.reflect.Array;
import java.util.Collection;
import java.util.Comparator;
import java.util.Iterator;
import java.util.SortedSet;
import java.util.StringJoiner;

public class LinkedSet<T extends Comparable<T>> implements SortedSet<T> {
    public static void main(String[] args) {
        LinkedSet<Integer> s = new LinkedSet<>();
        System.out.println(iterToString(s.iterator()));
        for (int i = 0; i < 10; i++) {
            s.add((int) (Math.random() * 5.0));
            System.out.println(iterToString(s.iterator()));
        }

        s.clear();
        System.out.println(iterToString(s.iterator()));
        for (int i = 0; i < 10; i++) {
            s.add((int) (Math.random() * 5.0));
            System.out.println(iterToString(s.iterator()));
        }
    }

    public static String iterToString(Iterator<?> i) {
        StringJoiner j = new StringJoiner("; ");
        j.setEmptyValue("");
        while (i.hasNext())
            j.add(i.next().toString());
        return j.toString();
    }

    private class Cell {
        Object value;
        Cell pred, succ;
    }

    private Cell anchor;

    public LinkedSet() {
        anchor = new Cell();
        anchor.pred = anchor;
        anchor.succ = anchor;
    }

    public Iterator<T> iterator() {
        return new Iterator<T>() {
            Cell a = anchor;
            boolean b = true;

            @Override
            public boolean hasNext() {
                if (b && a.succ == anchor) {
                    b = false;
                    return a.value != null;
                }
                return b && a.value != null;
            }

            @SuppressWarnings("unchecked")
            @Override
            public T next() {
                T t = (T) a.value;
                a = a.succ;
                return t;
            }

            @Override
            public void remove() {
                if (size() == 1) {
                    a.value = null;
                    a.pred = a;
                    a.succ = a;
                } else {
                    if (a.pred == anchor) {
                        anchor = a;
                    }
                    a.pred.pred.succ = a;
                    a.pred = a.pred.pred;
                }
            }
        };
    }

    @SuppressWarnings("unchecked")
    public boolean add(T e) {
        if (e == null) {
            throw new NullPointerException();
        }

        if (isEmpty()) {
            anchor.value = e;
        } else if (contains(e)) {
            return false;
        } else if (((Comparable<T>) e).compareTo((T) anchor.value) < 0) {
            anchor = insertBefore(anchor, e);
        } else {
            Cell current = anchor.succ;
            while (current != anchor && ((Comparable<T>) current.value).compareTo(e) < 0) {
                current = current.succ;
            }
            insertBefore(current, e);
        }
        return true;
    }

    private Cell insertBefore(Cell cell, T e) {
        Cell result = new Cell();
        result.value = e;
        result.pred = cell.pred;
        result.succ = cell;
        cell.pred.succ = result;
        cell.pred = result;
        return result;
    }

    @Override
    public boolean addAll(Collection<? extends T> c) {
        for (T t : c) {
            add(t);
        }
        return true;
    }

    @Override
    public void clear() {
        anchor.pred = anchor;
        anchor.succ = anchor;
        anchor.value = null;
    }

    @Override
    public boolean contains(Object o) {
        Iterator<T> i = iterator();
        while (i.hasNext())
            if (i.next().equals(o))
                return true;
        return false;
    }

    @Override
    public boolean containsAll(Collection<?> c) {
        for (Object o : c) {
            if (!contains(o))
                return false;
        }
        return true;
    }

    @Override
    public boolean isEmpty() {
        return anchor.value == null;
    }

    @SuppressWarnings("unchecked")
    @Override
    public boolean remove(Object o) {
        Iterator<T> i = iterator();
        while (i.hasNext())
            if (i.next().compareTo((T) o) == 0) {
                i.remove();
                return true;
            }
        return false;
    }

    @Override
    public boolean removeAll(Collection<?> c) {
        for (Object o : c) {
            if (!remove(o)) {
                return false;
            }
        }
        return true;
    }

    @Override
    public boolean retainAll(Collection<?> c) {
        // TODO Auto-generated method stub
        return false;
    }

    @Override
    public int size() {
        if (isEmpty())
            return 0;
        int s = 0;
        Iterator<?> i = iterator();
        while (i.hasNext()) {
            s++;
            i.next();
        }
        return s;
    }

    @Override
    public Object[] toArray() {
        Object[] a = new Object[size()];
        int j = 0;
        Iterator<T> i = iterator();
        while (i.hasNext())
            a[j++] = i.next();
        return a;
    }

    @SuppressWarnings({ "hiding", "unchecked" })
    @Override
    public <T> T[] toArray(T[] a) {
        T[] b = (T[]) Array.newInstance(a.getClass().getComponentType(), size());
        int j = 0;
        Iterator<T> i = (Iterator<T>) iterator();
        while (i.hasNext())
            b[j++] = i.next();
        return b;
    }

    @Override
    public Comparator<? super T> comparator() {
        return (T a, T b) -> a.compareTo(b);
    }

    @SuppressWarnings("unchecked")
    @Override
    public T first() {
        return (T) anchor.value;
    }

    @Override
    public SortedSet<T> headSet(T arg0) {
        // TODO Auto-generated method stub
        return null;
    }

    @SuppressWarnings("unchecked")
    @Override
    public T last() {
        return (T) anchor.pred.value;
    }

    @Override
    public SortedSet<T> subSet(T fromElement, T toElement) {
        // TODO Auto-generated method stub
        return null;
    }

    @Override
    public SortedSet<T> tailSet(T fromElement) {
        // TODO Auto-generated method stub
        return null;
    }
}


Java:
import static org.junit.jupiter.api.Assertions.*;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.Random;

import org.junit.jupiter.api.AfterEach;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

class LinkedSetTest {
    LinkedSet<Integer> set = null;

    @BeforeEach
    void setUp() throws Exception {
        set = new LinkedSet<Integer>();
    }

    @AfterEach
    void tearDown() throws Exception {
        set.clear();
        set = null;
    }

    @Test
    void testMain() {
        LinkedSet.main(null);
    }

    @Test
    void testIterToString() {
        testAdd();
        Iterator<Integer> i = set.iterator();
        assertNotNull(i);
        String s = LinkedSet.iterToString(i);
        assertNotNull(s);
        System.out.println(s);
    }

    @Test
    void testLinkedSet() {
        assertNotNull(set);
    }

    @Test
    void testIterator() {
        Iterator<Integer> i = set.iterator();
        assertNotNull(i);
        assertFalse(i.hasNext());
        assertTrue(set.add(new Random().nextInt(5)));
        i = set.iterator();
        assertNotNull(i);
        assertTrue(i.hasNext());
    }

    @Test
    void testAdd() {
        ArrayList<Integer> l = new ArrayList<>();
        for (int i = 0; i < 12; i++) {
            l.add(i);
        }
        for (int j = 0; j < 12; j++) {
            set.clear();
            assertTrue(set.isEmpty());
            Collections.shuffle(l);
            for (int i = 0; i < 12; i++) {
                assertTrue(set.add(l.get(i)));
                assertFalse(set.isEmpty());
            }
        }
    }

    @Test
    void testAddAll() {
        assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
        assertEquals("2; 3; 4", LinkedSet.iterToString(set.iterator()));
    }

    @Test
    void testClear() {
        set.clear();
        assertTrue(set.isEmpty());
    }

    @Test
    void testContains() {
        assertTrue(set.add(2));
        assertTrue(set.contains(2));
    }

    @Test
    void testContainsAll() {
        assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
        assertTrue(set.containsAll(Arrays.asList(2, 3, 4)));
        assertEquals("2; 3; 4", LinkedSet.iterToString(set.iterator()));
    }

    @Test
    void testIsEmpty() {
        assertTrue(set.isEmpty());
        assertTrue(set.add(1));
        assertFalse(set.isEmpty());
    }

    @Test
    void testRemove() {
        assertFalse(set.remove(2));
        assertTrue(set.add(2));
        assertTrue(set.remove(2));
        assertFalse(set.remove(3));
    }

    @Test
    void testRemoveAll() {
        assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
        assertEquals("2; 3; 4", LinkedSet.iterToString(set.iterator()));
        assertTrue(set.removeAll(Arrays.asList(2, 3, 4)));
        assertEquals("", LinkedSet.iterToString(set.iterator()));
    }

    @Test
    void testRetainAll() {
        fail("Not yet implemented");
    }

    @Test
    void testSize() {
        assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
        assertEquals(3, set.size());
        assertEquals("2; 3; 4", LinkedSet.iterToString(set.iterator()));
    }

    @Test
    void testToArray() {
        assertNotNull(set.toArray());
        assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
        assertNotNull(set.toArray());
        assertEquals("2; 3; 4", LinkedSet.iterToString(set.iterator()));
    }

    @Test
    void testToArrayTArray() {
        assertNotNull(set.toArray(new Integer[0]));
        assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
        assertEquals(3, set.toArray(new Integer[0]).length);
        assertEquals(Integer[].class, set.toArray(new Integer[0]).getClass());
        assertEquals("2; 3; 4", LinkedSet.iterToString(set.iterator()));
    }

    @Test
    void testComparator() {
        assertTrue(set.comparator() instanceof Comparator<?>);
    }

    @Test
    void testFirst() {
        assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
        assertEquals(2, set.first());
        assertEquals("2; 3; 4", LinkedSet.iterToString(set.iterator()));
    }

    @Test
    void testHeadSet() {
        fail("Not yet implemented");
    }

    @Test
    void testLast() {
        assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
        assertEquals(4, set.last());
        assertEquals("2; 3; 4", LinkedSet.iterToString(set.iterator()));
    }

    @Test
    void testSubSet() {
        fail("Not yet implemented");
    }

    @Test
    void testTailSet() {
        fail("Not yet implemented");
    }
}
 

ocsme

Top Contributor
Zu Anfang ist current=anchor
hasNext prüft dann, ob es noch einen Nachfolger gibt, next gibt dann aber den aktuellen Wert von current (also im ersten Aufruf anchor) zurück.

Zu Anfang ist current=anchor
hasNext prüft dann, ob es noch einen Nachfolger gibt, next gibt dann aber den aktuellen Wert von current (also im ersten Aufruf anchor) zurück.

:( so ein misst vergessen! Danke für die Hilfe :)

Dann nehme ich einfach alles von @Tobias-nrw ;)

LG
 

mrBrown

Super-Moderator
Mitarbeiter
Variablen heißen jetzt xXge93nd = a, current = za2g9dna :D Besser? :D:D
Nop.

Versuchs einfach noch mal selbst, wenn es nur um den Iterator geht, ist das wirklich nicht schwer.

remove(object o) im Iterator ist also eh Sinnfrei! Doch wenn ich Ihn einbauen würde könnte ich das von mir nehmen oder :O
Wenn du das wieder einbaust, wird man dir wieder sagen, dass es da nicht hingehört ¯\_(ツ)_/¯

Die Methode hat da einfach nichts zu suchen, die ist dort völlig sinnlos.
 
X

Xyz1

Gast
@mrBrown Habe mal folgendes geändert:
1. remove nicht vollständig im Iterator,
2. eigene Methode für remove im LinkedSet,
3. nach wie vor wird bei remove (noch) der Iterator verwendet.

Java:
import java.lang.reflect.Array;
import java.util.Collection;
import java.util.Comparator;
import java.util.Iterator;
import java.util.SortedSet;
import java.util.StringJoiner;

public class LinkedSet<T extends Comparable<T>> implements SortedSet<T> {
	public static void main(String[] args) {
		LinkedSet<Integer> s = new LinkedSet<>();
		System.out.println(iterToString(s.iterator()));
		for (int i = 0; i < 10; i++) {
			s.add((int) (Math.random() * 5.0));
			System.out.println(iterToString(s.iterator()));
		}

		s.clear();
		System.out.println(iterToString(s.iterator()));
		for (int i = 0; i < 10; i++) {
			s.add((int) (Math.random() * 5.0));
			System.out.println(iterToString(s.iterator()));
		}
	}

	public static String iterToString(Iterator<?> i) {
		StringJoiner j = new StringJoiner("; ");
		j.setEmptyValue("");
		while (i.hasNext())
			j.add(i.next().toString());
		return j.toString();
	}

	private class Cell {
		Object value;
		Cell pred, succ;
	}

	private Cell anchor;

	public LinkedSet() {
		anchor = new Cell();
		anchor.pred = anchor;
		anchor.succ = anchor;
	}

	public Iterator<T> iterator() {
		return new Iterator<T>() {
			Cell a = anchor;
			boolean b = true;

			@Override
			public boolean hasNext() {
				if (b && a.succ == anchor) {
					b = false;
					return a.value != null;
				}
				return b && a.value != null;
			}

			@SuppressWarnings("unchecked")
			@Override
			public T next() {
				T t = (T) a.value;
				a = a.succ;
				return t;
			}

			@Override
			public void remove() {
				LinkedSet.this.remove(a.pred);
			}
		};
	}

	@SuppressWarnings("unchecked")
	public boolean add(T e) {
		if (e == null) {
			throw new NullPointerException();
		}

		if (isEmpty()) {
			anchor.value = e;
		} else if (contains(e)) {
			return false;
		} else if (((Comparable<T>) e).compareTo((T) anchor.value) < 0) {
			anchor = insertBefore(anchor, e);
		} else {
			Cell current = anchor.succ;
			while (current != anchor && ((Comparable<T>) current.value).compareTo(e) < 0) {
				current = current.succ;
			}
			insertBefore(current, e);
		}
		return true;
	}

	private Cell insertBefore(Cell cell, T e) {
		Cell result = new Cell();
		result.value = e;
		result.pred = cell.pred;
		result.succ = cell;
		cell.pred.succ = result;
		cell.pred = result;
		return result;
	}

	@Override
	public boolean addAll(Collection<? extends T> c) {
		for (T t : c) {
			add(t);
		}
		return true;
	}

	@Override
	public void clear() {
		anchor.pred = anchor;
		anchor.succ = anchor;
		anchor.value = null;
	}

	@Override
	public boolean contains(Object o) {
		Iterator<T> i = iterator();
		while (i.hasNext())
			if (i.next().equals(o))
				return true;
		return false;
	}

	@Override
	public boolean containsAll(Collection<?> c) {
		for (Object o : c) {
			if (!contains(o))
				return false;
		}
		return true;
	}

	@Override
	public boolean isEmpty() {
		return anchor.value == null;
	}

	@SuppressWarnings("unchecked")
	@Override
	public boolean remove(Object o) {
		Iterator<T> i = iterator();
		while (i.hasNext())
			if (i.next().compareTo((T) o) == 0) {
				i.remove();
				return true;
			}
		return false;
	}

	private void remove(Cell c) {
		Cell a = c.succ;
		if (size() == 1) {
			a.value = null;
		} else {
			if (a.pred == anchor) {
				anchor = a;
			}
			a.pred.pred.succ = a;
			a.pred = a.pred.pred;
		}
	}

	@Override
	public boolean removeAll(Collection<?> c) {
		boolean b = true;
		for (Object o : c) {
			if (!remove(o)) {
				b = false;
			}
		}
		return b;
	}

	@Override
	public boolean retainAll(Collection<?> c) {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public int size() {
		if (isEmpty())
			return 0;
		int s = 0;
		Iterator<?> i = iterator();
		while (i.hasNext()) {
			s++;
			i.next();
		}
		return s;
	}

	@Override
	public Object[] toArray() {
		Object[] a = new Object[size()];
		int j = 0;
		Iterator<T> i = iterator();
		while (i.hasNext())
			a[j++] = i.next();
		return a;
	}

	@SuppressWarnings({ "hiding", "unchecked" })
	@Override
	public <T> T[] toArray(T[] a) {
		T[] b = (T[]) Array.newInstance(a.getClass().getComponentType(), size());
		int j = 0;
		Iterator<T> i = (Iterator<T>) iterator();
		while (i.hasNext())
			b[j++] = i.next();
		return b;
	}

	@Override
	public Comparator<? super T> comparator() {
		return (T a, T b) -> a.compareTo(b);
	}

	@SuppressWarnings("unchecked")
	@Override
	public T first() {
		return (T) anchor.value;
	}

	@Override
	public SortedSet<T> headSet(T arg0) {
		// TODO Auto-generated method stub
		return null;
	}

	@SuppressWarnings("unchecked")
	@Override
	public T last() {
		return (T) anchor.pred.value;
	}

	@Override
	public SortedSet<T> subSet(T fromElement, T toElement) {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public SortedSet<T> tailSet(T fromElement) {
		// TODO Auto-generated method stub
		return null;
	}
}
 

mrBrown

Super-Moderator
Mitarbeiter
@mrBrown Habe mal folgendes geändert:
1. remove nicht vollständig im Iterator,
2. eigene Methode für remove im LinkedSet,
3. nach wie vor wird bei remove (noch) der Iterator verwendet.
Na da war die vorherige Lösung aber schöner ;)


Was aktuell nicht nach Doku implementiert ist, sind
  • last: muss NoSuchElementException werfen
  • first: muss NSEE werfen
  • comparator: muss in diesem Fall null zurückgeben
  • toArray(T): neues Array darf nur erstellt werden, wenn übergebenes zu klein
  • contains: muss compareTo nutzen
  • Iterator#next: muss NSEE werfen
  • Iterator#remove: muss IllegalStateException werfen
Und halt die nicht implementierten Methoden
 
X

Xyz1

Gast
Danke für diese Auflistung... ja, die Fehlerbehandlung wurde von mir komplett ignoriert, zudem war ich bei toTArray sehr faul. ;)
 

ocsme

Top Contributor
Wenn die Aufgabenstellung so wäre das man einen Iterator mit der Methode remove(Object) Implementieren müsste :D wäre dann meine Okay? :)

und die anderen Methoden hasNext und Next() könne ich ja auch von dir nehmen okay :)
Eine andere Lösung fällt mir dort jetzt nicht ein.

Ich hätte aber noch eine Ähnliche Aufgabe wie diese hier und eine Frage vor ab. Darf ich wenn eine Klasse implements Collection im Iterator die Methoden bentuzen also wie z. B. to Array und isEmpty? Bestimmt oder :p

Ich danke euch nochmals ganz Herzlich für euren vielen Beiträgen :) super "Daumen Hoch =)"
 

mrBrown

Super-Moderator
Mitarbeiter
Wenn die Aufgabenstellung so wäre das man einen Iterator mit der Methode remove(Object) Implementieren müsste :D wäre dann meine Okay? :)
Keine Ahnung, das müsstest du dann den hypothetische Aufgabensteller fragen :p

und die anderen Methoden hasNext und Next() könne ich ja auch von dir nehmen okay :)
Eine andere Lösung fällt mir dort jetzt nicht ein.
Wenn du die Lösung frei erklären kannst gerne - aber dann wäre es doch sicher auch kein Problem, das selbst zu schreiben ;)

Ich hätte aber noch eine Ähnliche Aufgabe wie diese hier und eine Frage vor ab. Darf ich wenn eine Klasse implements Collection im Iterator die Methoden bentuzen also wie z. B. to Array und isEmpty? Bestimmt oder :p
Ich würde sagen „ja“
 

ocsme

Top Contributor
Keine Ahnung, das müsstest du dann den hypothetische Aufgabensteller fragen :p
Okay dann lasse ich das raus! Ist ja normalerweise auch nicht drin :p

Ich würde sagen „ja“
Das hört sich gut an denn dann könnte man ja auch mit der toArray Methode sich ein Array im Iterator anlegen und über das Iterieren oder wäre das auch wieder FALSCH :(??

Wenn du die Lösung frei erklären kannst gerne - aber dann wäre es doch sicher auch kein Problem, das selbst zu schreiben ;)
Ich glaube das ich das nicht kann :( dann lasse ich das alles weg :p
Danke nochmals :)

LG
 
X

Xyz1

Gast
und die anderen Methoden hasNext und Next() könne ich ja auch von dir nehmen okay :)
Von meiner Seite aus stünde nix dagegen. :) Ich kann aber Fehler, trotz der Tests, nicht ganz ausschließen.


Darf ich wenn eine Klasse implements Collection im Iterator die Methoden bentuzen also wie z. B. to Array und isEmpty? Bestimmt oder
Kläre das am besten mit dem hypothetischen Aufgabensteller ab, wenn es nicht schon in der Aufgabe stünde...
 

ocsme

Top Contributor
So damit hat sich diese Aufgabe erst einmal Erledigt :)

Ich danke ganz Herzlich allen die sich die Mühe gemacht haben und mir so sehr geholfen haben DANKE :)
LG
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
M Eigener Iterator für LinkedList Java Basics - Anfänger-Themen 20
A Für was Iterator ? Java Basics - Anfänger-Themen 3
M Java Iterator Verständnisfrage Java Basics - Anfänger-Themen 6
N Kann man einen Iterator nur einmal verwenden Java Basics - Anfänger-Themen 5
N Warum Springt iterator nur in der Schleife weiter Java Basics - Anfänger-Themen 9
volcanos HashSet und Iterator -> Falsche Sortierreihenfolge ? Java Basics - Anfänger-Themen 18
J Methoden Die Reihenfolge der Iterator-Elemente umkehren Java Basics - Anfänger-Themen 3
J Methoden iterator for-schleife (hasNext() ) Java Basics - Anfänger-Themen 7
Stargirlxo Iterator + Methode Java Basics - Anfänger-Themen 10
G Java Listen und Iterator Java Basics - Anfänger-Themen 2
U Hashmap Iterator selbst implementieren Java Basics - Anfänger-Themen 10
F nur das erste Element mit iterator ausgeben Java Basics - Anfänger-Themen 5
O Iterator erneut! Java Basics - Anfänger-Themen 8
J Doppelte Ausgabe erzeugen Iterator Java Basics - Anfänger-Themen 6
K Iterator zurückliefern Java Basics - Anfänger-Themen 8
W Eigener Iterator soll mehrdimensionales Array durchlaufen Java Basics - Anfänger-Themen 4
S Iterator einer Liste Java Basics - Anfänger-Themen 4
B Sortieren mit Iterator Java Basics - Anfänger-Themen 4
I Erste Schritte Iterator Java Basics - Anfänger-Themen 3
M Iterator funktioniert nicht Java Basics - Anfänger-Themen 5
M Iterator cannot refer to a non final... Java Basics - Anfänger-Themen 20
O Interface Iterator Java Basics - Anfänger-Themen 2
M Collections Frage Beispielprogrammierung Iterator Java Basics - Anfänger-Themen 13
M Iterator Java Basics - Anfänger-Themen 25
J Iterator Funktioniert nicht richtig in StackImplementierung Java Basics - Anfänger-Themen 3
Z Hashmap Iterator löscht nicht Java Basics - Anfänger-Themen 8
L Iterator Java Basics - Anfänger-Themen 1
K Nutzung einer Klasse die das Iterator-Interface implementiert Java Basics - Anfänger-Themen 0
K Iterator-Interface implementieren mit Exception Handlung Java Basics - Anfänger-Themen 1
M Collections Iterator und generischer Baum Java Basics - Anfänger-Themen 0
O Kleine Frage zu Iterator und Iterable Java Basics - Anfänger-Themen 6
OnDemand Iterator Interfacve Java Basics - Anfänger-Themen 23
S Iterator next() Nullpointer Java Basics - Anfänger-Themen 2
T Methoden Iterator über ArrayList Java Basics - Anfänger-Themen 3
W Iterator Java Basics - Anfänger-Themen 2
D Aufgabe: Stack mit Iterator Java Basics - Anfänger-Themen 8
R Mit iterator auf Element zugreifen Java Basics - Anfänger-Themen 2
T Collections Zugriff auf Elemente aus Iterator() Schleife Java Basics - Anfänger-Themen 4
P Casting Warning bei Iterator Java Basics - Anfänger-Themen 32
F Wie Werte einer ArrayList an einen 'Custom'-Iterator übergeben? Java Basics - Anfänger-Themen 2
J Iterator Java Basics - Anfänger-Themen 5
P ArrayList mit Iterator / Iterable ausgeben Java Basics - Anfänger-Themen 8
B Funktionsweise Iterator unklar Java Basics - Anfänger-Themen 7
A Datentypen Iterator von hinten nach vorne durchlaufen Java Basics - Anfänger-Themen 4
D Wie Iterator Remove implementieren? Java Basics - Anfänger-Themen 11
B Datentypen Inhalt zum Iterator wieder aufrufen? Java Basics - Anfänger-Themen 10
D Iterator schaltet nicht weiter?! Java Basics - Anfänger-Themen 5
A Problem mit Iterator Java Basics - Anfänger-Themen 2
B Türme von Hanoi - Iterator Java Basics - Anfänger-Themen 50
V Hilfe beim implementieren von Iterator Java Basics - Anfänger-Themen 5
W Collections Iterator<E> Java Basics - Anfänger-Themen 7
L Lokale Variable und Instanzvariable innerhalb Iterator Java Basics - Anfänger-Themen 8
W OOP problem mit iterator! -.- Java Basics - Anfänger-Themen 9
B Iterator und Collection Java Basics - Anfänger-Themen 11
ruutaiokwu Iterator oder .size ??? Java Basics - Anfänger-Themen 6
vandread Iterator zählt nicht hoch?! Java Basics - Anfänger-Themen 3
L Problem mit Iterator bzw. Sortierte Liste Java Basics - Anfänger-Themen 14
N HashMap mit Iterator durchlaufen Java Basics - Anfänger-Themen 11
R Iterator Liste, Verständnisproblem Java Basics - Anfänger-Themen 4
J Verschachtelte for-Schleife mit Löschen von Iterationen. Wie über Iterator abbilden? Java Basics - Anfänger-Themen 6
M Iterator Java Basics - Anfänger-Themen 15
L Implementation gesucht - ArrayList.iterator() Java Basics - Anfänger-Themen 3
pun Iterator über ArrayList Java Basics - Anfänger-Themen 12
P Iterator.add() Java Basics - Anfänger-Themen 3
A For Schleife - Iterator wird null Java Basics - Anfänger-Themen 7
? Map und iterator Java Basics - Anfänger-Themen 11
0x7F800000 ungereimtheiten mit Iterator/ListIterator Java Basics - Anfänger-Themen 2
N "Dynamischer" Iterator Java Basics - Anfänger-Themen 21
J Iterator remove()? Java Basics - Anfänger-Themen 5
T Liste mit Iterator auslesen Java Basics - Anfänger-Themen 11
Kr0e Iterator Java Basics - Anfänger-Themen 2
D iterator instanziieren! Java Basics - Anfänger-Themen 11
M Der Umgang mit Iterator - Wie ein Objekt aus einer ArrayList Java Basics - Anfänger-Themen 2
J ArrayList mit Iterator Java Basics - Anfänger-Themen 3
W Iterator in Queue Java Basics - Anfänger-Themen 5
M warum interface iterator verwendbar? Java Basics - Anfänger-Themen 5
O Iterator - Durchlauf "einschränken" bzw. steuern&q Java Basics - Anfänger-Themen 2
K Collection und Iterator Java Basics - Anfänger-Themen 7
Q Iterator next erstellen Java Basics - Anfänger-Themen 4
S iterator problem Java Basics - Anfänger-Themen 3
S Iterator --__-- Zugriff auf nächstes Element Java Basics - Anfänger-Themen 5
N Set + Iterator oder doch nur zu blöd API zu lesen Java Basics - Anfänger-Themen 32
R Java 5.0 neue For schleife Iterator was ist der fehler? Java Basics - Anfänger-Themen 5
N generische HashMap und Iterator Java Basics - Anfänger-Themen 2
R Iterator und HashMap Java Basics - Anfänger-Themen 10
G Probleme mit Iterator Java Basics - Anfänger-Themen 2
E umgededrehte if anweisung funzt nicht , iterator. Java Basics - Anfänger-Themen 2
A Iterator, wie funkioniert das richtig? Java Basics - Anfänger-Themen 6
S Iterator Schreibweise Java Basics - Anfänger-Themen 7
P ArrayList, iterator: Fehler in while Schleife Java Basics - Anfänger-Themen 2
T Iterator Java Basics - Anfänger-Themen 8
G Frage zur Iterator ? Java Basics - Anfänger-Themen 12
A Iterator auf anfang setzen Java Basics - Anfänger-Themen 5
blackfeet Bildfadeffekt (Halptransparenz) & iterator Java Basics - Anfänger-Themen 8
C Problem mit verschachteltem Iterator Java Basics - Anfänger-Themen 2
R Problem mit Iterator Java Basics - Anfänger-Themen 6
M Problem mit Iterator.remove() Java Basics - Anfänger-Themen 5
R Enumeration oder Iterator? Java Basics - Anfänger-Themen 2
J Klasse Iterator Java Basics - Anfänger-Themen 5
D unregelmäßige NullPointerException bei LinkedList Iterator? Java Basics - Anfänger-Themen 9

Ähnliche Java Themen

Neue Themen


Oben