1
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ Will remove() work with empty set? I would explicitly use TreeSet (instead of SortedSet) and use pollFirst() - it will be faster than separate peek()+remove(). \$\endgroup\$ – user158037 Dec 11 '17 at 13:00
  • \$\begingroup\$ @user158037 Yes, on an empty set, remove calls element which calls SortedSet::first which throws NoSuchElementException, which is exactly right. +++ Yes, pollFirst sounds like a good idea. \$\endgroup\$ – maaartinus Dec 12 '17 at 22:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.