@mrBrown : Ich finde die Aufgabenstellung etwas unnötig kompliziert oder nicht ausreichend gestellt formuliert...
und genau dafür entschuldige ich mich nochmals und deswegen kein STREIT hier
LG
@mrBrown : Ich finde die Aufgabenstellung etwas unnötig kompliziert oder nicht ausreichend gestellt formuliert...
public boolean remove(Object x) {
return LinkedSet.this.remove(x);
}
Das ist mit ein Grund, warum doppelte Elemente eigentlich falsch ist.remove() soll x aus der Menge entfernen und dann true liefern (andernfalls false).
Nein, Du musst jede Methode, die überschrieben werden soll, auch selber überschreiben. Das sind fast alle Methoden... (leider..)Soll man also in dieser remove Methode einfach die Methode von LinkedList aufrufen?
Was heißt OT?
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();
}
}
Off-TopicWas heißt OT?
Kommt drauf an was du eigentlich machen willst...in dem Beispiel ginge das mitNochmal 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:
Out.this
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...Out.this
Häh?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...)
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.Ist diese Aufgabe zu Lückenhaft. Leider ist es die Komplette Aufgabe mehr steht da nicht
boolean hasNext() {
if (current == null) {
return !isEmpty();
}
}
boolean hasNext() {
if (current == null) {
return !isEmpty();
} else {
return current != smallest;
}
}
boolean hasNext() {
return current == null ? !isEmpty() : current != smallest;
}
T next() {
if (hasNext()) {
// current == null kommt gleich
T value = current.value;
current = current.succ;
return value;
} else {
throw new NoSuchElementException();
}
}
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();
}
}
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:Cell current = anchor;
public boolean hasNext() {
return current.succ != anchor;
}
public T next() {
if (!hasNext()) throw new NoSuchElementException();
current = current.succ;
return current.value;
}
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;
}
}
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. 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;
}
}
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");
}
}
Mindestens dieser Test (und auch die Implementierung von add) sind falsch. true darf nur zurückgegeben werden, wenn das Element nicht schon existierte.Java:@Test void testAdd() { for (int i = 0; i < 12; i++) { assertTrue(set.add(new Random().nextInt(5))); } }
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 .Mindestens dieser Test (und auch die Implementierung von add) sind falsch. true darf nur zurückgegeben werden, wenn das Element nicht schon existierte.
Theoretisch schon, praktisch ist aber schonNa die Änderung hin zu einem "korrekten" Set sollte doch nicht mehr als eine neue Zeile erfordern...
Etwas zu lang...public boolean add(T t) {
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;
}
habe s getestet. Es funktioniert noch nicht, es fügt nicht ein, die Verknüpfungen sind noch nicht richtig.getestet
Ohman....LOL, hab beim insert wohl den Wert vergessen
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;
}
}
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");
}
}
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?
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;
}
}
}
Mit size kann ja jeder. Bei Dir ist anchor.value immer null?private int size = 0;
Mit size kann ja jeder.
Ja, spart halt den einen Sonderfall.Bei Dir ist anchor.value immer null?
LOL, ich weiß auch nicht, was die gegen O(n) haben.Bin überrascht, dass das nicht einfach in AbstractSet/AbstractCollection ganz primitiv über iterieren gelöst ist
Das würde ich bei einem Ring immer machen: das Geschiss mit den Prüfungen wegen eines Elements...Ja, spart halt den einen Sonderfall.
Ist ja bei anderen Methoden genauso gelöstLOL, ich weiß auch nicht, was die gegen O(n) haben.
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;
}
}
}
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);
}
}
}
Hm... das ließe sich doch auch in quadratischer Laufzeit hinbekommen.Ist ja bei anderen Methoden genauso gelöst
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.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...
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...
public void remove() {
a.pred.pred.succ = a;
a.pred = a.pred.pred;
}
Könnte mir dabei noch jemand auf die Sprünge Helfen vielleicht?public void remove(Object o)
Da sieht man erst einmal wie viele Möglichkeiten es gibt, ein und dasselbe Problem anzugehen.wow da habe ich ja eine Aufgabe gepostet
public boolean remove(Object x) {
while(hasNext()) {
Object next = next();
if(x.equals(next)) {
this.next();
this.remove();
return true;
}
}
return false;
}
Die remove(o)-Methode ist aber keine Methode, die vom Iterator-Interface spezifiziert wird.Dachte mir so etwas wenn wir ja nun die ganzen Methoden im Iterator hätten
Iterator<T> it = iterator();
while (it.hasNext()) {
T next = it.next();
if (next.equals(o)) {
it.remove();
return true;
}
}
return false;
@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;
}
Wo steht dasWobei bei einem SortedSet compareTo
Im Javadoc:Wo steht das
Es gibt doch die Übereinkunft, dass a.equals(b) = true, gdw a.compareTo(b) = 0.
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.
must be consistent with equals