und genau dafür entschuldige ich mich nochmals 🙂 und deswegen kein STREIT hier 🙂
LG
Iterator für eine geordnete Menge
- Themenstarter ocsme
- Beginndatum
und genau dafür entschuldige ich mich nochmals 🙂 und deswegen kein STREIT hier 🙂
LG
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:
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
Das ist mit ein Grund, warum doppelte Elemente eigentlich falsch ist.
Nein, Du musst jede Methode, die überschrieben werden soll, auch selber überschreiben. Das sind fast alle Methoden... (leider..)
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();
}
}
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.
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...)
mihe7
Top Contributor
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;
}
}
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.
Mal meine Lösung:
Ausgehend von der Annahme,
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:
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.
Im gesamten:
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,
@mrBrown Wie soll ich auf diesen qualifizierten Kommetar antworten?
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. 😀
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?
Mindestens dieser Test (und auch die Implementierung von add) sind falsch. true darf nur zurückgegeben werden, wenn das Element nicht schon existierte.
X
Xyz1
Gast
Ja das ist ein alter Schuh. Mein Set erlaubt (immer noch 😀 ) 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.
X
Xyz1
Gast
Theoretisch schon, praktisch ist aber schon
Etwas zu lang...
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;
}
X
Xyz1
Gast
Moin,
Die Hälfte der Tests sind nun rot. 😀
habe s getestet. Es funktioniert noch nicht, es fügt nicht ein, die Verknüpfungen sind noch nicht richtig.
Die Hälfte der Tests sind nun rot. 😀
X
Xyz1
Gast
Ohman.... 😀
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?
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:
mihe7
Top Contributor
Mit size kann ja jeder. 😛 Bei Dir ist anchor.value immer null?
😛
Bin überrascht, dass das nicht einfach in AbstractSet/AbstractCollection ganz primitiv über iterieren gelöst ist
Ja, spart halt den einen Sonderfall.
mihe7
Top Contributor
LOL, ich weiß auch nicht, was die gegen O(n) haben.
Das würde ich bei einem Ring immer machen: das Geschiss mit den Prüfungen wegen eines Elements...
Ist ja bei anderen Methoden genauso gelöst 😛
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);
}
}
}mihe7
Top Contributor
Hm... das ließe sich doch auch in quadratischer Laufzeit hinbekommen.
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.
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
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)
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....
😀 wow da habe ich ja eine Aufgabe gepostet 😀
🙂 Freut mich so viel Feedback 🙂
Eine Frage hätte ich aber noch.
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
"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
🙂 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
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
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.
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.
mihe7
Top Contributor
Da sieht man erst einmal wie viele Möglichkeiten es gibt, ein und dasselbe Problem anzugehen.
X
Xyz1
Gast
WOOOBEI, man die aus a2 ausgehenden Kanten nicht extra löschen muss, da a2 nicht mehr referenziert wird nachher...
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 🙂
bei dem this.next() und this.remove() bin ich mir nicht sicher :?
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
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;
}
X
Xyz1
Gast
Wo steht das 😀
Es gibt doch die Übereinkunft, dass a.equals(b) = true, gdw a.compareTo(b) = 0.
X
Xyz1
Gast
Du hast das falsch gelesen,
mihe lag richtig...
mihe lag richtig...
Aktuelle Jobs
-
Wafios Softwareentwickler Cloud (JAVA/Spring) m/w/d - Reutlingen- Gestartet von Java_Jobs
- Antworten: 0
-
Inek Senior Java Softwareentwickler (m/w/d) - Siegburg
- Gestartet von Java_Jobs
- Antworten: 0
-
Atos Senior Java Architekt (m/w/d) - Fürth
- Gestartet von Java_Jobs
- Antworten: 0
-
-
FCA Bank Java-Entwickler (m/w/d) (Heilbronn)
- Gestartet von Java_Jobs
- Antworten: 0
Neue Themen
-
Duplikate in Funktionsbildmenge
- Gestartet von OpaK
- Antworten: 21
-
JavaFX Ist Java FX tot, oder doch nicht, oder nur ein bisschen ?- Gestartet von Ernesto95
- Antworten: 6
-
UtilLib: Java-Werkzeugkasten für kleine Projekte – Mitstreiter gesucht
- Gestartet von TomBombadil
- Antworten: 11
-
-
Ich brauche Hilfe bei einem Java-Chat-Applet
- Gestartet von Artemde96
- Antworten: 21