Iterator für eine geordnete Menge

ocsme

Top Contributor
remove() soll x aus der Menge entfernen und dann true liefern (andernfalls false). Gesucht ist die Implementierung von remove(Object x).

Verstehe ich das richtig? -> Die Klasse LinkedSet implementiert SortedSet dieses Interface hat Collection als Interface und dort steht eine remove Methode. Soll man also in dieser remove Methode einfach die Methode von LinkedList aufrufen? bzw. wäre das erlaubt?
Danach wollte ich noch die normale remove Methode schreiben also ohne ein Object zu übergeben. Diese Methode kann man ja erst Aufrufen wenn man mindestens 1x next() gemacht hat.

So hätte ich jetzt die remove(object x) geschrieben:
Code:
         public boolean remove(Object x) {
             return LinkedSet.this.remove(x);
         }
 
X

Xyz1

Gast

ocsme

Top Contributor
Was heißt OT?

Nochmal kurz eine Frage: wie bekomme ich ein Datenelement aus einer Out() Klasse in eine Lokale Klasse? Muss man dazu eine Instanz erstellen hier ein Bsp:

Java:
public class Out {
    String a = "a";
   
    public void test() {
        System.out.println("Test");
        class In {
            public void test() {
                System.out.println(new Out().a);
            }
        }
        new In.test();
    }
}
 

ocsme

Top Contributor
Danke genau das habe ich gesucht.
Verstehen tu ich den Aufruf zwar nicht wirklich.
Wenn ich z. B. String.this. aufrufe was heißt das?
Ich hab zugriff auf String sowie auch auf Object!

LG
 

mrBrown

Super-Moderator
Mitarbeiter
Klassenname.this ist nur sinnvoll, wenn du aus einer inneren Klasse heraus eine Instanz der äußeren brauchst. Jede innere Klasse hat eine Referenz auf die äußere, und die spricht man eben mit Klassenname.this an.


Im Zusammenhang mit String und Object brauchst du das nie, das ist nur bei deinen eigenen Klassen sinnvoll.
 
X

Xyz1

Gast
Also der Grund, weswegen man Out.this nicht benötigt ist hierbei, weil die "äußere Klasse" nicht auf Deine eigene Implementierung zugreifen kann und weil ein Teil der "Kern"-Implementierung in einer eigenen Klasse vorgegeben ist, welche Du erweitern solltest...

Es wäre anders, wenn die "Kern"-Implementierung der "äußeren Klasse" vorgegeben gewesen wäre... (also wenn ihr auf diese zurückgreifen hättet sollen...)
 

mrBrown

Super-Moderator
Mitarbeiter
Also der Grund, weswegen man Out.this nicht benötigt ist hierbei, weil die "äußere Klasse" nicht auf Deine eigene Implementierung zugreifen kann und weil ein Teil der "Kern"-Implementierung in einer eigenen Klasse vorgegeben ist, welche Du erweitern solltest...

Es wäre anders, wenn die "Kern"-Implementierung der "äußeren Klasse" vorgegeben gewesen wäre... (also wenn ihr auf diese zurückgreifen hättet sollen...)
Häh?
 

mihe7

Top Contributor
Ist diese Aufgabe zu Lückenhaft. Leider ist es die Komplette Aufgabe mehr steht da nicht :(
Mit der Info, dass die Methoden des Set verwendet werden dürfen, ist die Aufgabe lösbar: man kann das kleinste Element mit first() erhalten und die Frage, ob die Menge leer ist, lässt sich mit isEmpty() beantworten.

Da hier schon Lösungen genannt wurden, schreibe ich hier mal meine mit der Entwicklung einer solchen Lösung verbundenen Gedanken zusammen. Vielleicht hilft es für das Verständnis.

Der Iterator hat einen Zeiger (current), der auf die "aktuelle" Zelle zeigt. Wurde die aktuelle Zelle noch nicht bestimmt, ist sie null.

Wann gibt es ein nächstes Element? Wenn die aktuelle Zelle noch nicht bestimmt wurde, wäre das kleinste Element das nächste Element. Es gibt genau dann ein kleinstes Element, wenn die Liste nicht leer ist. D. h.
Java:
boolean hasNext() {
    if (current == null) {
        return !isEmpty();
    }
}

Damit wäre der Fall für die leere Liste abgehakt.

Jetzt ist es ja so, dass man einen Ring hat, den man sich wie eine analoge Uhr vorstellen kann. Das kleinste Element wäre dort die 1. Es gibt nun so lange nächste Elemente, bis man wieder beim kleinsten Element angelangt ist, richtig? Also muss hasNext() so lange true liefern, so lange current nicht auf die Zelle mit dem kleinsten Wert zeigt.

Java:
boolean hasNext() {
    if (current == null) {
        return !isEmpty();
    } else {
        return current != smallest; 
    }
}
oder kurz:
Java:
boolean hasNext() {
    return current == null ? !isEmpty() : current != smallest;
}

Gut, was passiert nun in next()? Zuerst einmal wird geprüft, ob es ein nächstes Element gibt. Falls nein, wird eine NoSuchElementException geworfen (Contract von Iterator). Falls ja, muss der Wert der aktuellen Zelle zurückgegeben werden, gleichzeitig muss der Zeiger auf die nächste Zelle vorrücken.

Java:
T next() {
    if (hasNext()) {
        // current == null kommt gleich 
        T value  = current.value;
        current = current.succ;
        return value;
    } else {
        throw new NoSuchElementException();
    }
}

Jetzt muss noch der Fall current == null behandelt werden. Das ist der Fall, wenn next() erstmals aufgerufen wurde. Hier muss im Wesentlichen die Zelle mit dem kleinsten Element bestimmt werden, denn das muss nicht die Ankerzelle sein (z. B. könnte auf der Uhr die Zelle mit der 3 die Ankerzelle sein - wir haben ja einen Ring).

Das kleinste Element erhält man über das Set via first(). Man fängt bei der Ankerzelle an (smallest = anchor). So lange nun smallest.value und first() ungleich sind, rückt man den Zeiger um eine Zelle zurück. Am Ende setzt man current = smallest.

Also
Java:
T next() {
    if (hasNext()) {
        if (current == null) {
            smallest = anchor;
            T smallestValue = first(); 
            while (!Objects.equals(smallest.value, smallestValue)) {
                smallest = smallest.pred;
            }
            current = smallest;
        }
        T value  = current.value;
        current = current.succ;
        return value;
    } else {
        throw new NoSuchElementException();
    }
}

Dabei wird Objects.equals verwendet, weil nicht klar ist, ob null-Werte zulässig sind. Sollte passen.
 

mrBrown

Super-Moderator
Mitarbeiter
Mal meine Lösung:

Ausgehend von der Annahme, anchor != null && anchor.value == null und isEmpty() == (anchor.succ==anchor.pred==anchor) und, dass direkt geordnet eingefügt wird.

current ist das Element, bei welchem der Iterator aktuell steht. Bevor next das erste Mal aufgerufen wurde, steht das ganze vor ersten wirklichen Element, was der Anker ist:
Java:
Cell current = anchor;

Es gibt immer so lange ein nächstes Element, bis das nächste wieder der Anker ist, man also wieder am Anfang angekommen wäre:

Java:
public boolean hasNext() {
    return current.succ != anchor;
}

In next wird dann jeweils auf das nächste Element "weiter geschaltet", und dessen Wert dann zurück gegeben.
Erst wird natürlich geprüft, ob es überhaupt ein nächstes Element gibt, und notfalls die Exception geworfen.

Java:
public T next() {
    if (!hasNext()) throw new NoSuchElementException();
    current = current.succ;
    return current.value;
}

Im gesamten:
Java:
class LinkedSetIterator implements Iterator<T> {

    Cell current = anchor;

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

    @Override
    public T next() {
        if (!hasNext()) throw new NoSuchElementException();
        current = current.succ;
        return current.value;
    }

}
 
X

Xyz1

Gast
Habe mal weiter gemacht und tests dafür geschrieben, remove().... habe ich "delegiert" an den iterator. Sicherlich nicht die bestmögliche Lösung und es sollte eigentlich mit so 10.000 Elem getestet werden, aber es sind nur noch 4 tests rot. :D

Java:
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("; ");
		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() {
				T t = (T) a.value;
				a = a.succ;
				return t;
			}

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

		};
	}

	@Override
	public boolean add(T t) {
		if (anchor.value == null) {
			anchor.value = t;
		} else {
			if (anchor.succ == anchor) {
				if (((Comparable<T>) anchor.value).compareTo(t) < 0) {
					Cell n = new Cell();
					n.pred = anchor;
					n.succ = anchor;
					n.value = t;
					anchor.pred = n;
					anchor.succ = n;

				} else {
					Cell n = new Cell();
					n.pred = anchor;
					n.succ = anchor;
					n.value = t;
					anchor.pred = n;
					anchor.succ = n;
					anchor = n;
				}
			} else {
				Cell a = anchor;
				while (a.succ != anchor) {
					if (((Comparable<T>) a.value).compareTo(t) > 0) {
						Cell n = new Cell();
						n.pred = a.pred;
						n.succ = a;
						n.value = t;
						a.pred.succ = n;
						a.pred = n;

						if (a == anchor)
							anchor = n;
						break;
					}
					a = a.succ;
				}
				if (a.succ == anchor) {
					if (((Comparable<T>) a.value).compareTo(t) > 0) {
						Cell n = new Cell();
						n.pred = a.pred;
						n.succ = a;
						n.value = t;
						a.pred.succ = n;
						a.pred = n;
					} else {
						Cell n = new Cell();
						n.pred = a;
						n.succ = a.succ;
						n.value = t;
						a.succ.pred = n;
						a.succ = n;
					}
				}
			}
		}
		return true;
	}

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

	@Override
	public boolean remove(Object o) {
		Iterator<T> i = iterator();
		while (i.hasNext())
			if (i.next().equals(o)) {
				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() {
		int s = 1;
		if (isEmpty())
			return 0;
		Cell a = anchor;
		while (a.succ != anchor) {
			s++;
			a = a.succ;
		}
		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;
	}

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

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

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

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

	@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.Arrays;
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() {
		Iterator<Integer> i = set.iterator();
		assertNotNull(i);
		String s = LinkedSet.iterToString(i);
		assertNotNull(i);
		System.out.println(s);
	}

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

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

	@Test
	void testAdd() {
		for (int i = 0; i < 12; i++) {
			assertTrue(set.add(new Random().nextInt(5)));
		}
	}

	@Test
	void testAddAll() {
		assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
	}

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

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

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

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

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

	@Test
	void testSize() {
		assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
		assertTrue(set.size() == 3);
	}

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

	@Test
	void testToArrayTArray() {
		assertNotNull(set.toArray(new Integer[0]));
		assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
		assertTrue(set.toArray(new Integer[set.size()]).getClass().equals(Integer[].class));
	}

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

	@Test
	void testFirst() {
		assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
		assertTrue(set.first() == 2);
	}

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

	@Test
	void testLast() {
		assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
		assertTrue(set.last() == 4);
	}

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

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


@mrBrown Wie soll ich auf diesen qualifizierten Kommetar antworten?
 
X

Xyz1

Gast
Mindestens dieser Test (und auch die Implementierung von add) sind falsch. true darf nur zurückgegeben werden, wenn das Element nicht schon existierte.
Ja das ist ein alter Schuh. Mein Set erlaubt (immer noch :D ) doppelte Elemente (ich müsste das alles "umschreiben"). Das ist quasi nicht im Sinne von @Meniskusschaden . ;)

Deswegen werden auch nicht alle Methoden funktionieren...

Aber Danke das es dir aufgefallen ist..

Bearbeitung: Beitrag #64 bitte wieder entfernen falls möglich.
 

mihe7

Top Contributor
Ohne das jetzt getestet zu haben:
Java:
    public boolean add(T e) {
        if (e == null) {
            throw new NullPointerException();
        }

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

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

mihe7

Top Contributor
Woran liegts?

EDIT: LOL, hab beim insert wohl den Wert vergessen :)
Java:
    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 cell;
    }
 
X

Xyz1

Gast
LOL, hab beim insert wohl den Wert vergessen
Ohman.... :D

Damit funktionierts, ich habe die Tests nochmal etwas verbessert....

Java:
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("; ");
		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() {
				T t = (T) a.value;
				a = a.succ;
				return t;
			}

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

		};
	}

	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) e).compareTo(anchor.value) < 0) {
			anchor = insertBefore(anchor, e);
		} else {
			Cell current = anchor.succ;
			while (current != anchor && ((Comparable) 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;
	}

	@Override
	public boolean remove(Object o) {
		Iterator<T> i = iterator();
		while (i.hasNext())
			if (i.next().equals(o)) {
				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() {
		int s = 1;
		if (isEmpty())
			return 0;
		Cell a = anchor;
		while (a.succ != anchor) {
			s++;
			a = a.succ;
		}
		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;
	}

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

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

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

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

	@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(i);
		System.out.println(s);
	}

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

	@Test
	void testIterator() {
		assertTrue(set.add(new Random().nextInt(5)));
		Iterator<Integer> 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();
			Collections.shuffle(l);
			for (int i = 0; i < 12; i++) {
				assertTrue(set.add(l.get(i)));
			}
		}
	}

	@Test
	void testAddAll() {
		assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
	}

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

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

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

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

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

	@Test
	void testSize() {
		assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
		assertTrue(set.size() == 3);
	}

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

	@Test
	void testToArrayTArray() {
		assertNotNull(set.toArray(new Integer[0]));
		assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
		assertTrue(set.toArray(new Integer[set.size()]).getClass().equals(Integer[].class));
	}

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

	@Test
	void testFirst() {
		assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
		assertTrue(set.first() == 2);
	}

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

	@Test
	void testLast() {
		assertTrue(set.addAll(Arrays.asList(4, 2, 3)));
		assertTrue(set.last() == 4);
	}

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

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

Code:
Leerzeile
2
0; 2
0; 2
0; 2; 3
0; 2; 3
0; 2; 3
0; 2; 3; 4
0; 2; 3; 4
0; 2; 3; 4
0; 2; 3; 4

4
4
2; 4
0; 2; 4
0; 2; 4
0; 2; 4
0; 2; 4
0; 1; 2; 4
0; 1; 2; 4
0; 1; 2; 3; 4
0; 1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11


@mihe7 Hast Du Lust die noch verbleibenden 4 Methoden zu implementieren?
 

mrBrown

Super-Moderator
Mitarbeiter
@mihe7 Hast Du Lust die noch verbleibenden 4 Methoden zu implementieren?
Die Methoden des Subsets sind nicht wirklich gut getestet, da steckt bestimmt noch ein Fehler drin...
Java:
import java.util.*;


public class LinkedSet<T extends Comparable<T>> extends AbstractSet<T> implements SortedSet<T> {

    private Cell anchor;

    private int size = 0;

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

    public LinkedSet(Collection<T> collection) {
        this.anchor = new Cell();
        this.addAll(collection);
    }

    @SafeVarargs
    public static <T extends Comparable<T>> LinkedSet<T> of(T... ts) {
        return new LinkedSet<T>(Arrays.asList(ts));
    }

    @Override
    public Iterator<T> iterator() {
        return new LinkedSetIterator();
    }

    public boolean add(T t) {
        if (contains(t)) {
            return false;
        }
        Cell newCell = new Cell(Objects.requireNonNull(t));
        Cell insertionPoint = findFloor(t);
        newCell.insertAfter(insertionPoint);
        size++;
        return true;
    }

    private Cell findFloor(T value) {
        Cell lower = anchor;
        while (lower.succ != anchor && lower.succ.value.compareTo(value) <= 0) {
            lower = lower.succ;
        }
        return lower;
    }

    private Comparator<? super T> internalComparator() {
        return Comparator.naturalOrder();
    }

    @Override
    @SuppressWarnings("unchecked")
    public boolean contains(final Object o) {
        for (final T t : this) {
            if (this.internalComparator().compare(t, (T) o) == 0) {
                return true;
            }
        }
        return false;
    }

    @Override
    public Comparator<? super T> comparator() {
        return null;
    }

    private Cell findLower(T value) {
        Cell lower = anchor;
        while (lower.succ != anchor && lower.succ.value.compareTo(value) < 0) {
            lower = lower.succ;
        }
        return lower;
    }

    private Cell findCeiling(T value) {
        Cell greater = anchor;
        while (greater.succ != anchor && !(greater.succ.value.compareTo(value) > 0)) {
            greater = greater.succ;
        }
        return greater;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public SortedSet<T> subSet(final T fromElement, final T toElement) {
        return new LinkedSubSet(fromElement, toElement);
    }

    @Override
    public SortedSet<T> headSet(final T toElement) {
        return new LinkedSubSet(null, toElement);
    }

    @Override
    public SortedSet<T> tailSet(final T fromElement) {
        return new LinkedSubSet(fromElement, null);

    }

    @Override
    public T first() {
        if (this.isEmpty()) {
            throw new NoSuchElementException();
        }
        return anchor.succ.value;
    }

    @Override
    public T last() {
        if (this.isEmpty()) {
            throw new NoSuchElementException();
        }
        return anchor.pred.value;
    }

    private final class Cell {

        final T value;

        Cell pred;

        Cell succ;

        private Cell() {
            this(null);
            this.pred = this;
            this.succ = this;
        }

        private Cell(final T value) {
            this.value = value;
        }

        private void insertAfter(Cell insertionPoint) {
            this.pred = insertionPoint;
            this.succ = insertionPoint.succ;
            this.pred.succ = this;
            this.succ.pred = this;
        }

        private void unlink() {
            this.pred.succ = this.succ;
            this.succ.pred = this.pred;
        }

        @Override
        public String toString() {
            return "Cell{"
                   + "value=" + value
                   + '}';
        }

    }

    private final class LinkedSetIterator implements Iterator<T> {

        final Cell last;

        Cell current;

        private LinkedSetIterator() {
            this(anchor, anchor);
        }

        private LinkedSetIterator(final Cell beforeFirst, final Cell last) {
            this.current = beforeFirst;
            this.last = last;
        }

        @Override
        public T next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            current = current.succ;
            return current.value;
        }

        public boolean hasNext() {
            return current.succ != last;
        }

        @Override
        public void remove() {
            current.unlink();
        }

    }

    private final class LinkedSubSet extends AbstractSet<T> implements SortedSet<T> {

        final T from;

        final T to;

        private final Cell fromCell;

        private final Cell toCell;

        private LinkedSubSet(final T from, final T to) {
            this.from = from;
            this.to = to;

            fromCell = from != null ? findLower(from) : anchor;
            toCell = to != null ? findCeiling(to) : anchor;
        }

        @Override
        public Iterator<T> iterator() {
            return new LinkedSetIterator(fromCell, toCell);
        }

        @Override
        public int size() {
            int size = 0;
            for (final T t : this) {
                size++;
            }
            return size;
        }

        @Override
        public Comparator<? super T> comparator() {
            return LinkedSet.this.comparator();
        }

        @Override
        public boolean add(final T t) {
            checkRange(t);
            return LinkedSet.this.add(t);
        }

        private void checkRange(final T t) {
            if (!isGreaterEqualThanFrom(t) || !isLowerThanTo(t)) {
                throw new IllegalArgumentException("Value out of range [" + from + "," + to + "): " + t);
            }
        }

        private boolean isLowerThanTo(final T t) {
            return to != null && t.compareTo(to) < 0;
        }

        private boolean isGreaterEqualThanFrom(final T t) {
            return from != null && t.compareTo(from) >= 0;
        }

        @Override
        public SortedSet<T> subSet(final T fromElement, final T toElement) {
            return LinkedSet.this.subSet(fromElement, toElement);
        }

        @Override
        public SortedSet<T> headSet(final T toElement) {
            return LinkedSet.this.subSet(from, toElement);
       }

       @Override
       public SortedSet<T> tailSet(final T fromElement) {
           return LinkedSet.this.subSet(fromElement, to);
       }

        @Override
        public T first() {
            return fromCell.succ.value;
        }

        @Override
        public T last() {
            return toCell.pred.value;
        }

       @Override
       @SuppressWarnings("unchecked")
       public boolean contains(final Object o) {
           for (final T t : this) {
               if (LinkedSet.this.internalComparator().compare(t, (T) o) == 0) {
                   return true;
               }
           }
           return false;
       }

    }

}
 
Zuletzt bearbeitet:

mrBrown

Super-Moderator
Mitarbeiter
LOL, ich weiß auch nicht, was die gegen O(n) haben.
Ist ja bei anderen Methoden genauso gelöst :p



Java:
import java.util.*;


public class LinkedSet<T extends Comparable<T>> extends AbstractSet<T> implements SortedSet<T> {

    private Cell anchor;

    private int size = 0;

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

    public LinkedSet(Collection<T> collection) {
        this.anchor = new Cell();
        this.addAll(collection);
    }

    @SafeVarargs
    public static <T extends Comparable<T>> LinkedSet<T> of(T... ts) {
        return new LinkedSet<T>(Arrays.asList(ts));
    }

    @Override
    public Iterator<T> iterator() {
        return new LinkedSetIterator();
    }

    public boolean add(T t) {
        if (contains(t)) {
            return false;
        }
        Cell newCell = new Cell(Objects.requireNonNull(t));
        Cell insertionPoint = findFloor(t);
        newCell.insertAfter(insertionPoint);
        size++;
        return true;
    }

    private Cell findFloor(T value) {
        Cell lower = anchor;
        while (lower.succ != anchor && lower.succ.value.compareTo(value) <= 0) {
            lower = lower.succ;
        }
        return lower;
    }

    private Comparator<? super T> internalComparator() {
        return Comparator.naturalOrder();
    }

    @Override
    @SuppressWarnings("unchecked")
    public boolean contains(final Object o) {
        for (final T t : this) {
            if (this.internalComparator().compare(t, (T) o) == 0) {
                return true;
            }
        }
        return false;
    }

    @Override
    public Comparator<? super T> comparator() {
        return null;
    }

    private Cell findLower(T value) {
        Cell lower = anchor;
        while (lower.succ != anchor && lower.succ.value.compareTo(value) < 0) {
            lower = lower.succ;
        }
        return lower;
    }

    private Cell findCeiling(T value) {
        Cell greater = anchor;
        while (greater.succ != anchor && !(greater.succ.value.compareTo(value) > 0)) {
            greater = greater.succ;
        }
        return greater;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public SortedSet<T> subSet(final T fromElement, final T toElement) {
        return new LinkedSubSet(fromElement, toElement);
    }

    @Override
    public SortedSet<T> headSet(final T toElement) {
        return new LinkedSubSet(null, toElement);
    }

    @Override
    public SortedSet<T> tailSet(final T fromElement) {
        return new LinkedSubSet(fromElement, null);

    }

    @Override
    public T first() {
        if (this.isEmpty()) {
            throw new NoSuchElementException();
        }
        return anchor.succ.value;
    }

    @Override
    public T last() {
        if (this.isEmpty()) {
            throw new NoSuchElementException();
        }
        return anchor.pred.value;
    }

    private final class Cell {

        final T value;

        Cell pred;

        Cell succ;

        private Cell() {
            this(null);
            this.pred = this;
            this.succ = this;
        }

        private Cell(final T value) {
            this.value = value;
        }

        private void insertAfter(Cell insertionPoint) {
            this.pred = insertionPoint;
            this.succ = insertionPoint.succ;
            this.pred.succ = this;
            this.succ.pred = this;
        }

        private void unlink() {
            this.pred.succ = this.succ;
            this.succ.pred = this.pred;
        }

        @Override
        public String toString() {
            return "Cell{"
                   + "value=" + value
                   + '}';
        }

    }

    private final class LinkedSetIterator implements Iterator<T> {

        final Cell last;

        Cell current;

        private LinkedSetIterator() {
            this(anchor, anchor);
        }

        private LinkedSetIterator(final Cell beforeFirst, final Cell last) {
            this.current = beforeFirst;
            this.last = last;
        }

        @Override
        public T next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            current = current.succ;
            return current.value;
        }

        public boolean hasNext() {
            return current.succ != last;
        }

        @Override
        public void remove() {
            current.unlink();
            size--;
        }

    }

    private final class LinkedSubSet extends AbstractSet<T> implements SortedSet<T> {

        final T from;

        final T to;

        private final Cell fromCell;

        private final Cell toCell;

        private LinkedSubSet(final T from, final T to) {
            this.from = from;
            this.to = to;

            fromCell = from != null ? findLower(from) : anchor;
            toCell = to != null ? findCeiling(to) : anchor;
        }

        @Override
        public Iterator<T> iterator() {
            return new LinkedSetIterator(fromCell, toCell);
        }

        @Override
        public int size() {
            int size = 0;
            for (final T t : this) {
                size++;
            }
            return size;
        }

        @Override
        public Comparator<? super T> comparator() {
            return LinkedSet.this.comparator();
        }

        @Override
        public boolean add(final T t) {
            checkRange(t);
            return LinkedSet.this.add(t);
        }

        private void checkRange(final T t) {
            if (!isGreaterEqualThanFrom(t) || !isLowerThanTo(t)) {
                throw new IllegalArgumentException("Value out of range [" + from + "," + to + "): " + t);
            }
        }

        private boolean isLowerThanTo(final T t) {
            return to != null && t.compareTo(to) < 0;
        }

        private boolean isGreaterEqualThanFrom(final T t) {
            return from != null && t.compareTo(from) >= 0;
        }

        @Override
        public SortedSet<T> subSet(final T fromElement, final T toElement) {
            return LinkedSet.this.subSet(fromElement, toElement);
        }

        @Override
        public SortedSet<T> headSet(final T toElement) {
            return LinkedSet.this.subSet(from, toElement);
        }

        @Override
        public SortedSet<T> tailSet(final T fromElement) {
            return LinkedSet.this.subSet(fromElement, to);
        }

        @Override
        public T first() {
            if (this.isEmpty()) {
                throw new NoSuchElementException();
            }
            return fromCell.succ.value;
        }

        @Override
        public T last() {
            if (this.isEmpty()) {
                throw new NoSuchElementException();
            }
            return toCell.pred.value;
        }

        @Override
        @SuppressWarnings("unchecked")
        public boolean contains(final Object o) {
            for (final T t : this) {
                if (LinkedSet.this.internalComparator().compare(t, (T) o) == 0) {
                    return true;
                }
            }
            return false;
        }

    }

}


Java:
import java.util.*;

import org.junit.jupiter.api.Nested;
import org.junit.jupiter.api.Test;

import static org.assertj.core.api.Assertions.assertThat;
import static org.assertj.core.api.Assertions.assertThatThrownBy;
import static org.assertj.core.api.Assumptions.assumeThat;


class LinkedSetTest {

    @Test
    void shouldReturnNullComparator() {
        assertThat(new LinkedSet<>().comparator()).isNull();
    }

    @Test
    void firstShouldReturnSmallest() {
        LinkedSet<Integer> integers = LinkedSet.of(4, 2, 3, 1);
        assertThat(integers.first()).isEqualTo(1);
    }

    @Test
    void firstOnEmptySetShouldThrow() {
        LinkedSet<Integer> integers = LinkedSet.of();
        assertThatThrownBy(integers::first)
                .isInstanceOf(NoSuchElementException.class);
    }

    @Test
    void lastShouldReturnGreatest() {
        LinkedSet<Integer> integers = LinkedSet.of(4, 2, 3, 1);
        assertThat(integers.last()).isEqualTo(4);
    }

    @Test
    void lastOnEmptySetShouldThrow() {
        LinkedSet<Integer> integers = LinkedSet.of();
        assertThatThrownBy(integers::last)
                .isInstanceOf(NoSuchElementException.class);
    }

    @Test
    void shouldContainElementsInCorrectOrderAfterAdd() throws Exception {
        LinkedSet<Integer> integers = new LinkedSet<>();
        integers.add(1);
        integers.add(4);
        integers.add(3);
        integers.add(2);

        assertThat(integers).containsExactly(1, 2, 3, 4);
    }

    @Test
    void tailSet() throws Exception {
        LinkedSet<Integer> integers = new LinkedSet<>();
        integers.add(1);
        integers.add(4);
        integers.add(3);
        integers.add(2);
        assumeThat(integers).containsExactly(1, 2, 3, 4);
        assertThat(integers.tailSet(2)).containsExactly(2, 3, 4);
    }

    @Test
    void headSet() throws Exception {
        LinkedSet<Integer> integers = new LinkedSet<>();
        integers.add(1);
        integers.add(4);
        integers.add(3);
        integers.add(2);

        assumeThat(integers).containsExactly(1, 2, 3, 4);
        assertThat(integers.headSet(3)).containsExactly(1, 2);
    }

    @Test
    void removeShouldRemoveElement() throws Exception {
        LinkedSet<Integer> integers = LinkedSet.of(1, 4, 3, 2);
        assumeThat(integers).containsExactly(1, 2, 3, 4);
        assertThat(integers.remove(2)).isTrue();
        assertThat(integers).containsExactly(1, 3, 4);
    }

    @Test
    void repeatedRemoveShouldReturnFalse() throws Exception {
        LinkedSet<Integer> integers = LinkedSet.of(1, 4, 3, 2);
        assumeThat(integers).containsExactly(1, 2, 3, 4);
        assumeThat(integers.remove(2)).isTrue();
        assumeThat(integers).containsExactly(1, 3, 4);

        assertThat(integers.remove(2)).isFalse();
    }

    @Test
    void emptySetShouldHaveSizeZero() throws Exception {
        LinkedSet<Integer> integers = new LinkedSet<>();

        assertThat(integers).hasSize(0).isEmpty();
    }

    @Test
    void oneElementSetShouldNotBeEmptyAndHaveSizeOne() throws Exception {
        LinkedSet<Integer> integers = new LinkedSet<>();
        integers.add(1);

        assertThat(integers).hasSize(1).isNotEmpty();
    }

    @Test
    void shouldReturnCorrectSizeAfterRemove() {
        LinkedSet<Integer> integers = new LinkedSet<>();
        integers.add(1);
        assumeThat(integers).hasSize(1).isNotEmpty();

        assertThat(integers.remove(1)).isTrue();
        assumeThat(integers).hasSize(0).isEmpty();
    }

    @Nested
    class SubSetTest {

        LinkedSet<Integer> integers = LinkedSet.of(1, 2, 4, 5);

        @Test
        void shouldReturnCorrectSubSet() throws Exception {
            SortedSet<Integer> subSet = integers.subSet(2, 5);
            assertThat(subSet).containsExactly(2, 4);
        }

        @Test
        void addOnSubSetShouldAddOnSet() throws Exception {
            SortedSet<Integer> subSet = integers.subSet(2, 5);
            assumeThat(subSet).containsExactly(2, 4);

            subSet.add(3);
            subSet.add(2);
            subSet.add(4);
            assertThat(subSet).containsExactly(2, 3, 4);
            assertThat(integers).containsExactly(1, 2, 3, 4, 5);
        }

        @Test
        void shouldThrowIfLowerThanRange() throws Exception {
            SortedSet<Integer> subSet = integers.subSet(2, 5);
            assumeThat(subSet).containsExactly(2, 4);

            assertThatThrownBy(() -> subSet.add(1))
                    .isInstanceOf(IllegalArgumentException.class)
                    .hasMessage("Value out of range [2,5): 1");
        }

        @Test
        void shouldThrowIfGreaterThanRange() throws Exception {
            SortedSet<Integer> subSet = integers.subSet(2, 5);
            assumeThat(subSet).containsExactly(2, 4);

            assertThatThrownBy(() -> subSet.add(5))
                    .isInstanceOf(IllegalArgumentException.class)
                    .hasMessage("Value out of range [2,5): 5");
        }

        @Test
        void shouldReturnEmptySet() {
            SortedSet<Integer> subSet = integers.subSet(2, 2);

            assertThat(subSet).isEmpty();
        }


        @Test
        void shouldReturnCorrectHeadSetFromSubSet() throws Exception {
            SortedSet<Integer> subSet = integers.subSet(2, 5);
            assumeThat(subSet).containsExactly(2, 4);

            assumeThat(subSet.headSet(4)).containsExactly(2);
            assumeThat(subSet.headSet(2)).isEmpty();

        }
        @Test
        void shouldReturnCorrectTailSetFromSubSet() throws Exception {
            SortedSet<Integer> subSet = integers.subSet(2, 5);
            assumeThat(subSet).containsExactly(2, 4);

            assumeThat(subSet.tailSet(2)).containsExactly(2, 4);
            assumeThat(subSet.tailSet(4)).containsExactly(4);

        }

        @Test
        void shouldReturnNullComparator() {
            assertThat(new LinkedSet<>().comparator()).isNull();
        }

        @Test
        void firstShouldReturnSmallest() {
            SortedSet<Integer> subSet = integers.subSet(2, 5);
            assumeThat(subSet).containsExactly(2, 4);
            assertThat(subSet.first()).isEqualTo(2);
        }

        @Test
        void firstOnEmptySetShouldThrow() {
            SortedSet<Integer> subSet = integers.subSet(2, 2);
            assumeThat(subSet).isEmpty();
            assertThatThrownBy(subSet::first)
                    .isInstanceOf(NoSuchElementException.class);
        }

        @Test
        void lastShouldReturnGreatest() {
            SortedSet<Integer> subSet = integers.subSet(2, 5);
            assumeThat(subSet).containsExactly(2, 4);
            assertThat(subSet.last()).isEqualTo(4);
        }

        @Test
        void lastOnEmptySetShouldThrow() {
            SortedSet<Integer> subSet = integers.subSet(2, 2);
            assumeThat(subSet).isEmpty();
            assertThatThrownBy(subSet::last)
                    .isInstanceOf(NoSuchElementException.class);
        }
    }

}
 
X

Xyz1

Gast
Mit size spart man sich natürlich eine Laufzeit von n zu 1...
Aber hier ging/geht es doch auch darum, dass TE etwas dabei "lernt/mitnimmt".
Und da finde ich unterschiedliche Möglichkeiten nicht schlecht zum lernen...

Genauso wie mit den Tests... meine sind nicht wirklich gut. Aber hab halt noch nicht so viele Erfahrungen damit.
 
X

Xyz1

Gast
BTW es ist nicht ganz richtig, den Begriff "Set" mit Menge zu übersetzen, denn unter einer Menge versteht man etwas anderes, denn eine Menge erlaubt z.B auch doppelte Elemente - "Sets" hingegen nicht. Es gibt dafür keine "adäquate" Übersetzung...
 
K

kneitzel

Gast
BTW es ist nicht ganz richtig, den Begriff "Set" mit Menge zu übersetzen, denn unter einer Menge versteht man etwas anderes, denn eine Menge erlaubt z.B auch doppelte Elemente - "Sets" hingegen nicht. Es gibt dafür keine "adäquate" Übersetzung...
Hier wird natürlich nicht der mathematische Begriff der Menge verwendet sondern wenn wir von Datenstrukturen reden, dann wird natürlich auch die entsprechende Definition benutzt.

Siehe:
https://de.wikipedia.org/wiki/Menge_(Datenstruktur)
https://de.wikipedia.org/wiki/Menge_(Mathematik)
 

mrBrown

Super-Moderator
Mitarbeiter
BTW es ist nicht ganz richtig, den Begriff "Set" mit Menge zu übersetzen, denn unter einer Menge versteht man etwas anderes, denn eine Menge erlaubt z.B auch doppelte Elemente - "Sets" hingegen nicht. Es gibt dafür keine "adäquate" Übersetzung...

Du kannst auch ein Set schreiben, welches intern doppelte Elemente enthält. Das muss sich nur identisch zu dem verhalten, welches keine doppelten enthält....
 

ocsme

Top Contributor
:D wow da habe ich ja eine Aufgabe gepostet :D

:) Freut mich so viel Feedback :)

Eine Frage hätte ich aber noch.

Code:
            public void remove() {
                a.pred.pred.succ = a;
                a.pred = a.pred.pred;
            }

Das ganze habe ich verstanden. Doch wie soll man das machen wenn man nach einem Object o gefragt wird das dieses Element entfernt werden soll?
Also
public void remove(Object o)
Könnte mir dabei noch jemand auf die Sprünge Helfen vielleicht?
"Ich dachte mit einem Vergleich auf das Überquerte Object und dann könnte man ja den remove von oben nutzen? macht sowas Sinn?"

Liebe Grüße
 

mrBrown

Super-Moderator
Mitarbeiter
Die Methode ist in beiden Varianten vorhanden ;)

In meinem Code nur im AbstractSet, wovon ich erbe, in @Tobias-nrw aber direkt implementiert. (wobei ich grad merke, dass das bei mir noch falsch ist...)


Aber ja - deine Idee passt. Mit dem Iterator den Wert suchen und dann damit löschen.
 
X

Xyz1

Gast
@ocsme stimmt, das war jetzt eine Menge. ;)

Du musst dir das bildlich vorstellen. a1, a2 und a3. a2 soll gelöscht werden. rot = zu löschen, grün = hinzuzufügen, a1 und a3 können natürlich noch weitere Kanten haben:

gra1.png
 

mrBrown

Super-Moderator
Mitarbeiter
Wir sind aber vermutlich völlig übers Ziel der Aufgabe hinausgeschossen...


Set inklusive der SubSet-methoden ist zumindest nicht wirklich das, was ich im ersten/zweiten Semester Java erwarten würde.
 
X

Xyz1

Gast
WOOOBEI, man die aus a2 ausgehenden Kanten nicht extra löschen muss, da a2 nicht mehr referenziert wird nachher...
 

ocsme

Top Contributor
Das remove(Object o) finde ich bei euren Daten jetzt nicht auf anhieb.
Dachte mir so etwas wenn wir ja nun die ganzen Methoden im Iterator hätten :)

Java:
         public boolean remove(Object x) {
             while(hasNext()) {
                 Object next = next();
                 if(x.equals(next)) {
                     this.next();
                     this.remove();
                     return true;
                 }
             }
            
             return false;
         }

bei dem this.next() und this.remove() bin ich mir nicht sicher :?
 

mihe7

Top Contributor
Dachte mir so etwas wenn wir ja nun die ganzen Methoden im Iterator hätten
Die remove(o)-Methode ist aber keine Methode, die vom Iterator-Interface spezifiziert wird.

Unabhängig davon sähe die remove(o)-Methode im Set fast identisch zu Deiner aus, wenn man mittels Iterator arbeiten will:
Java:
Iterator<T> it = iterator();
while (it.hasNext()) {
    T next = it.next();
    if (next.equals(o)) {
        it.remove();
        return true;
    }
}
return false;
 
X

Xyz1

Gast
@ocsme Ich hatte das an den Iterator delegiert, es geht natürlich auch ohne.... Zum Bleistift:
Java:
	@Override
	public boolean remove(Object o) {
		if (isEmpty())
			return false;
		Cell a = anchor;
		do {
			if (Objects.equals(a.value, o)) {
				a.pred.pred.succ = a;
				a.pred = a.pred.pred;
				return true;
			}
			a = a.succ;
		} while (a != anchor);
		return false;
//		Iterator<T> i = iterator();
//		while (i.hasNext())
//			if (i.next().equals(o)) {
//				i.remove();
//				return true;
//			}
//		return false;
	}
 

mrBrown

Super-Moderator
Mitarbeiter
Wobei bei einem SortedSet compareTo (oder Comparator#compare) statt equals benutzt werden sollte (bzw: muss).
 

mrBrown

Super-Moderator
Mitarbeiter
Wo steht das :D

Es gibt doch die Übereinkunft, dass a.equals(b) = true, gdw a.compareTo(b) = 0.
Im Javadoc:

Note that the ordering maintained by a sorted set (whether or not an explicit comparator is provided) must be consistent with equals if the sorted set is to correctly implement the Set interface. (See the Comparable interface or Comparator interface for a precise definition of consistent with equals.) This is so because the Set interface is defined in terms of the equals operation, but a sorted set performs all element comparisons using its compareTo (or compare) method, so two elements that are deemed equal by this method are, from the standpoint of the sorted set, equal. The behavior of a sorted set is well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of the Set interface.
 
Ä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