I needed a data structure offering both poll
returning the smallest element and fast contains
. A PriorityQueue
has slow contains
, so I adapted a SortedSet
as a queue. I wonder, if I did it right and if using an iterator
would be better.
I'm not sure, if I'm bending the semantics of offer
too far.
Thanks to Guava and Lombok, my code is very short. Nonetheless, my previous version had a bug, so reviewing it may be a good idea.
@RequiredArgsConstructor
public final class SortedSetAsQueue<E> extends ForwardingSortedSet<E>
implements Queue<E> {
@Override public boolean offer(E e) {
return add(e);
}
@Override public E remove() {
final E result = element();
delegate.remove(result);
return result;
}
@Override @Nullable public E poll() {
return isEmpty() ? null : remove();
}
@Override public E element() {
return delegate.first();
}
@Override @Nullable public E peek() {
return isEmpty() ? null : element();
}
// using lombok.accessors.fluent=true, so no "get" prefix
@Getter(value=AccessLevel.PROTECTED)
private final SortedSet<E> delegate;
}
remove
callselement
which callsSortedSet::first
which throwsNoSuchElementException
, which is exactly right.+++
Yes,pollFirst
sounds like a good idea. \$\endgroup\$ – maaartinus Dec 12 '17 at 22:46