Inselupdate: NavigableSet und SortedSet

TreeSet implementiert die Schnittstelle NavigableSet und bietet darüber Funktionen, um insbesondere zu einem gegebenen Element das nächst höhere/kleinere zu liefern. Somit sind auf Mengen nicht nur die üblichen Anfragen über Mengenzugehörigkeit denkbar, sondern auch Anfragen wie „gib mir das Element, das größer oder gleich einem gegebenen Element ist“.
Folgendes Beispiel reiht in ein TreeSet drei Calendar-Objekte ein – die Klasse Calendar implementiert Comparable<Calendar>. Die Funktionen lower(), ceiling(), floor() und higher() wählen aus der Menge das angefragte Objekt heraus.

com/tutego/insel/util/set/SortedSetDemo.java
NavigableSet<Calendar> set = new TreeSet<Calendar>();
set.add( new GregorianCalendar(2007, Calendar.MARCH, 10) );
set.add( new GregorianCalendar(2007, Calendar.MARCH, 12) );
set.add( new GregorianCalendar(2007, Calendar.APRIL, 12) );

Calendar cal1 = set.lower( new GregorianCalendar(2007, Calendar.MARCH, 12) );
System.out.printf( "%tF%n", cal1 ); // 2007-03-10

Calendar cal2 = set.ceiling( new GregorianCalendar(2007, Calendar.MARCH, 12) );
System.out.printf( "%tF%n", cal2 ); // 2007-03-12

Calendar cal3 = set.floor( new GregorianCalendar(2007, Calendar.MARCH, 12) );
System.out.printf( "%tF%n", cal3 ); // 2007-03-12

Calendar cal4 = set.higher( new GregorianCalendar(2007, Calendar.MARCH, 12) );
System.out.printf( "%tF%n", cal4 ); // 2007-04-12

Eine Funktion wie tailSet() ist insbesondere bei Datumsobjekten sehr praktisch, da es alle Zeitpunkte liefern kann, die nach einem Startdatum liegen.

Seit Java 6 implementiert TreeSet statt SortedSet direkt die Schnittstelle NavigableSet, die ihrerseits SortedSet erweitert. Insgesamt bietet NavigableSet 15 Operationen, wobei sie aus SortedSet die Methoden headSet(), tailSet(), subSet() überschreibt, um eine überladene Version der Methoden anzubieten, die die Grenzen exklusiv oder inklusiv erlauben.

interface java.util.NavigableSet<E> extends SortedSet<E>

• SortedSet<E> headSet( E toElement )
• SortedSet<E> tailSet( E fromElement )
  Liefert eine Teilmenge von Elementen, die echt kleiner/größer als toElement/fromElement ist.
• NavigableSet<E> headSet( E toElement, boolean inclusive )
• NavigableSet<E> tailSet( E fromElement, boolean inclusive )
  Bestimmt gegenüber den oberen Funktionen zusätzlich, ob das Ausgangselement zur Ergebnismenge gehören darf.
• SortedSet<E> subSet( E fromElement, E toElement )
  Liefert eine Teilmenge im gewünschten Bereich.
• E pollFirst()
• E pollLast()
  Holt und entfernt das erste/letzte Element. Die Rückgabe ist null, wenn das Set leer ist.
• E higher( E e )
• E lower( E e )
  Liefert das folgende/vorangehende Element im Set, welches echt größer/kleiner als E ist oder null, falls ein solches Element nicht exisitert.
• E ceiling( E e )
• E floor( E e )
  Liefert das folgende/vorangehende Element im Set, welches größer/kleiner oder gleich E ist oder null, falls ein solches Element nicht exisitert.
• Iterator<E> descendingIterator()
  Liefert die Elemente in umgekehrter Reihenfolge.
  

Aus der Schnittstelle SortedSet übernimmt NavigableSet drei Operationen:

interface java.util.SortedSet<E> extends Set<E>

• E first()
  Liefert das erste Element in der Liste.
• E last()
  Liefert das größte Element.
• Comparator<? super E> comparator()
  Liefert den mit der Menge verbundenen Comparator. Die Rückgabe kann null sein, wenn die Objekte sich mit Comparable selbst vergleichen können.
  

Anders als HashSet liefert der Iterator beim TreeSet die Elemente aufsteigend sortiert. Davon profitieren auch die beiden toArray()-Funktionen – implementiert in AbstractCollection –, denn sie nutzen den Iterator um ein sortiertes Feld zurückzugeben.