Iterator für eine geordnete Menge

mrBrown · 4. Jun 2019

Tobias-nrw hat gesagt.:
Du hast das falsch gelesen,

mihe lag richtig...

Den Rest hast du auch gelesen?

mihe7 · 5. Jun 2019

Tobias-nrw hat gesagt.:
mihe lag richtig...

@mrBrown hat Recht.

Xyz1 · 5. Jun 2019

Ok, verstehe, Danke

kneitzel · 5. Jun 2019

Tobias-nrw hat gesagt.:
Du hast das falsch gelesen,
mihe lag richtig...

Das " but a sorted set performs all element comparisons using its compareTo " hast Du auch gelesen?

Xyz1 · 5. Jun 2019

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 · 5. Jun 2019

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

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;
         }
        
    }

Xyz1 · 5. Jun 2019

ocsme hat gesagt.:
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().... 😉

mrBrown · 5. Jun 2019

ocsme hat gesagt.:
Wäre dort die remove(Object) Methode nun richtig?

Ne, ein Iterator braucht nur remove(). Die sieht aber passend aus.

Allerdings sind next und hasNext falsch - da hast du irgendwie das schlechteste aller Varianten zusammengemixt.

kneitzel · 5. Jun 2019

Tobias-nrw hat gesagt.:
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 · 5. Jun 2019

😵 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 · 5. Jun 2019

ocsme hat gesagt.:
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 😉

Xyz1 · 5. Jun 2019

@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.

kneitzel · 5. Jun 2019

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 · 5. Jun 2019

kneitzel hat gesagt.:
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 😉

kneitzel · 5. Jun 2019

mrBrown hat gesagt.:
Das „aktuelle“ Element ist dabei nicht a, sondern a.pred 😉

Ohh, stimmt. Hatte ich jetzt übersehen. Wenn man selbst eine andere Implementierung vor sich hat, dann vertut man sich da leicht ... (Ein Grund für sprechende Namen, so dass man weiß, was man vor sich hat.)

Xyz1 · 5. Jun 2019

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 · 5. Jun 2019

Tobias-nrw hat gesagt.:
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)

Xyz1 · 5. Jun 2019

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.

mrBrown · 5. Jun 2019

Tobias-nrw hat gesagt.:
UNd glaub mir, das ist Eclipse... und das kann auch nicht anhalten, wenngleich alle Tests "grün" werden.

Mindestens der nicht-anhaltende Test sollte nicht grün werden?

Ansonsten die @Timeout dran und gut ist 🙂

Xyz1 · 5. Jun 2019

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 · 5. Jun 2019

mrBrown hat gesagt.:
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 · 5. Jun 2019

ocsme hat gesagt.:
Dann nehme ich einfach alles von @Tobias-nrw 😉

Bitte nicht (und bitte auch nicht meine Variante...)

mrBrown · 5. Jun 2019

Tobias-nrw hat gesagt.:
Geschafft!

Naja, "ein paar" Verstöße gegen das Interface gibts aber schon noch 😉

ocsme · 5. Jun 2019

mrBrown hat gesagt.:
Bitte nicht (und bitte auch nicht meine Variante...)

Variablen heißen jetzt xXge93nd = a, current = za2g9dna 😀 Besser? 😀 😀
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

mrBrown · 5. Jun 2019

ocsme hat gesagt.:
Variablen heißen jetzt xXge93nd = a, current = za2g9dna 😀 Besser? 😀😀

Nop.

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

ocsme hat gesagt.:
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.

Xyz1 · 5. Jun 2019

Genau dafür kann der Iterator aber auch benutzt werden.

Xyz1 · 5. Jun 2019

@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 · 5. Jun 2019

Tobias-nrw hat gesagt.:
@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

Xyz1 · 5. Jun 2019

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

ocsme · 5. Jun 2019

Wenn die Aufgabenstellung so wäre das man einen Iterator mit der Methode remove(Object) Implementieren müsste 😀 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 😛

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

mrBrown · 5. Jun 2019

ocsme hat gesagt.:
Wenn die Aufgabenstellung so wäre das man einen Iterator mit der Methode remove(Object) Implementieren müsste 😀 wäre dann meine Okay? 🙂

Keine Ahnung, das müsstest du dann den hypothetische Aufgabensteller fragen 😛

ocsme hat gesagt.:
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 😉

ocsme hat gesagt.:
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 😛

Ich würde sagen „ja“

ocsme · 5. Jun 2019

mrBrown hat gesagt.:
Keine Ahnung, das müsstest du dann den hypothetische Aufgabensteller fragen 😛

Okay dann lasse ich das raus! Ist ja normalerweise auch nicht drin 😛

mrBrown hat gesagt.:
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 🙁??

mrBrown hat gesagt.:
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 😛
Danke nochmals 🙂

LG

Xyz1 · 5. Jun 2019

ocsme hat gesagt.:
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.

ocsme hat gesagt.:
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...

mrBrown · 5. Jun 2019

ocsme hat gesagt.:
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 🙁??

Das wäre zumindest sehr abenteuerlich, aber generell müsste das Möglich sein - dürfte aber mehr Aufwand werden.

ocsme · 7. Jun 2019

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

Iterator für eine geordnete Menge

Super-Moderator

Top Contributor

Xyz1

Gast

kneitzel

Gast

Xyz1

Gast

Top Contributor

Xyz1

Gast

Super-Moderator

kneitzel

Gast

Top Contributor

Super-Moderator

Xyz1

Gast

kneitzel

Gast

Super-Moderator

kneitzel

Gast

Xyz1

Gast

Super-Moderator

Xyz1

Gast

Super-Moderator

Xyz1

Gast

Top Contributor

Super-Moderator

Super-Moderator

Top Contributor

Super-Moderator

Xyz1

Gast

Xyz1

Gast

Super-Moderator

Xyz1

Gast

Top Contributor

Super-Moderator

Top Contributor

Xyz1

Gast

Super-Moderator

Top Contributor

Ähnliche Themen