Why SingletonSet Doesn't Run SortedSet

Question

To reduce memory consumption, I rewrite the class with SortedSet<Integer> . In 80% of cases, this collection contains only one item. So I thought I could use a SingeltonSet in these cases and a regular TreeSet in other cases. Now I noticed that the SingletonSet returned by Collections.singleton() does not implement the SortedSet . Is there a reason for this flaw? I would say that one element can be considered sorted. Should I write my own implementation of SingletonSet ?

Answer 1

This is an interesting point that seems to illustrate a small hole in the collections API.

The fact is that Collections.singleton() defined to return Set , not SortedSet , and in fact, the implementation does not support this interface. I don't think it would be useful for Collections.singleton() to change their behavior and return an instance of SortedSet . This will encourage implementations to perform instanceof checks and downing. (And similarly for the corresponding Map methods and interfaces.)

This is a small consolation for this emptyNavigableSet use, but new methods for Collections.emptyNavigableMap and emptyNavigableSet have been introduced in Java SE 8. This is useful for use cases where you need an empty navigation collection, but if you really want a navigation system with a single element or display, you're out of luck. There is a request for improvement of JDK-6201174, which covers a similar area; I updated and focused it on providing an API for a singleton navigation set and map.

But wait! As you pointed out , there are several additional states that are used together with sorted / moved collections, which is a comparator. (Or in the absence of a comparator, implicitly one that provides natural ordering.) Any new singleton APIs can also provide this. And this indicates the fact that the above empty * methods do not talk about the Comparator. This seems like another mistake: JDK-8181754 .

Unfortunately, I don’t have a really good workaround for you, except to buckle up and implement a singleton, possibly immutable SortedSet or NavigableSet. You can start with Collections.UnmodifiableNavigableSet . It helps a little, but not much. In fact, an empty navigation set is one of them wrapped around an empty TreeSet ! This is completely useless since you want to avoid TreeSet instances.

I would probably start with AbstractSet and then add a minimal set of methods from SortedSet. There are far fewer methods than NavigableSet, so if you don’t need all of its twists, it would be easier to stick with SortedSet.

Answer 2

The SortedSet interface defines methods that require a Comparator for specified elements. Thus, the elements supported by a SortedSet must be comparable. If the singleton returned by Collections.singleton() will implement a SortedSet , then Collections.singleton() can only accept Comparables (this is not what we want).

Answer 3

I think Stuart Marx's answer very well explains why there is no singleton for a sorted set. However, implementing SingletonSortedSet is easy.

What about:

 import java.util.*; import java.util.function.Consumer; import java.util.function.Predicate; public class SingletonSortedSet<E> extends AbstractSet<E> implements SortedSet<E> { private final E element; private final Comparator<? super E> comparator; private SingletonSortedSet(E e, Comparator<? super E> comparator) { element = e; this.comparator = comparator; } public static <E> SortedSet<E> singletonSortedSet(E e, Comparator<? super E> comparator) { return new SingletonSortedSet<>(e, comparator); } public Iterator<E> iterator() { return singletonIterator(element); } public int size() { return 1; } public boolean contains(Object o) { return Objects.equals(o, element); } // Override default methods for Collection @Override public void forEach(Consumer<? super E> action) { action.accept(element); } @Override public Spliterator<E> spliterator() { return singletonSpliterator(element, comparator); } @Override public boolean removeIf(Predicate<? super E> filter) { throw new UnsupportedOperationException(); } @Override public int hashCode() { return Objects.hashCode(element); } @Override public Comparator<? super E> comparator() { return comparator; } @Override public SortedSet<E> subSet(E fromElement, E toElement) { if(contains(fromElement) || contains(toElement)) { return this; } else { return Collections.emptySortedSet(); } } @Override public SortedSet<E> headSet(E toElement) { if(contains(toElement)) { return this; } else { return Collections.emptySortedSet(); } } @Override public SortedSet<E> tailSet(E fromElement) { if(contains(fromElement)) { return this; } else { return Collections.emptySortedSet(); } } @Override public E first() { return element; } @Override public E last() { return element; } private static <E> Iterator<E> singletonIterator(final E e) { return new Iterator<E>() { private boolean hasNext = true; public boolean hasNext() { return hasNext; } public E next() { if (hasNext) { hasNext = false; return e; } throw new NoSuchElementException(); } public void remove() { throw new UnsupportedOperationException(); } @Override public void forEachRemaining(Consumer<? super E> action) { Objects.requireNonNull(action); if (hasNext) { hasNext = false; action.accept(e); } } }; } private static <T> Spliterator<T> singletonSpliterator(final T element, Comparator<? super T> comparator) { return new Spliterator<T>() { long est = 1; @Override public Spliterator<T> trySplit() { return null; } @Override public boolean tryAdvance(Consumer<? super T> consumer) { Objects.requireNonNull(consumer); if (est > 0) { est--; consumer.accept(element); return true; } return false; } @Override public void forEachRemaining(Consumer<? super T> consumer) { tryAdvance(consumer); } @Override public long estimateSize() { return est; } @Override public int characteristics() { int value = (element != null) ? Spliterator.NONNULL : 0; return value | Spliterator.SIZED | Spliterator.SUBSIZED | Spliterator.IMMUTABLE | Spliterator.DISTINCT | Spliterator.SORTED; } @Override public Comparator<? super T> getComparator() { return comparator; } }; } } 

Then you can use SingletonSortedSet.singletonSortedSet (...).