4
\$\begingroup\$

I've tried implementing priority queue with fixed size in Java using TreeSet and overriding add() method:

public class FixedSizePriorityQueue<E> extends TreeSet<E> {
    private final int capacity;

    public FixedSizePriorityQueue(final int capacity) {
        this.capacity = capacity;
    }

    public FixedSizePriorityQueue(
            final int capacity,
            final Comparator<? super E> comparator) {

        super(comparator);
        this.capacity = capacity;
    }

    @Override
    public boolean add(final E e) {
        // initialized with 0 or less than zero capacity
        if (capacity <= 0) {
            return false;
        }

        // keep adding until we fill the queue
        if (size() < capacity) {
            return super.add(e);
        }

        if (comparator() != null
                && comparator().compare(this.last(), e) < 0) {
            pollLast();
            return super.add(e);
        }

        return false;
    }
}

I would really appreciate your thoughts, hints and comments.

\$\endgroup\$
  • 1
    \$\begingroup\$ Are you sure you want your FixedSizePriorityQueue be a TreeSet? Do you want to support all methods of a TreeSet ? I would internally use a TreeSet but not extend it. \$\endgroup\$ – MrSmith42 Aug 30 '13 at 10:10
  • 2
    \$\begingroup\$ @MrSmith42, good point! I don't need to extend it, I can use it internally. Tnx. \$\endgroup\$ – robosoul Aug 30 '13 at 10:11
  • \$\begingroup\$ What's the usage of pollLast() method in add method? \$\endgroup\$ – Anirban Nag 'tintinmj' Aug 30 '13 at 14:34
  • \$\begingroup\$ @tintinmj the idea is to have fixed size priority queue, and with pollLast(), I remove the most irrelevant element and add new one, using super.add(), leaving super to prioritize. \$\endgroup\$ – robosoul Sep 1 '13 at 13:48
3
\$\begingroup\$

Two thoughts:

  1. If there is other code and you need all the features of a TreeSet great, otherwise delegate to a TreeSet member variable.

  2. Your code if (capacity <= 0) is somewhat superfluous because of the next test if (size() < capacity)

\$\endgroup\$
  • \$\begingroup\$ thanks for noticing if (capacity <= 0). size() will always return 0 or greater than 0 :) \$\endgroup\$ – robosoul Aug 30 '13 at 10:25
-1
\$\begingroup\$

I rarely check the return of add methods. I would suggest throwing an exception to indicate the container is full. Add methods that return available space and full state.

\$\endgroup\$
  • 6
    \$\begingroup\$ I didn't downvote on this answer, but this is not what I would consider a "proper" review. Look at some other answers on this site, get a feel for what they should look like, and then come back with that knowledge and integrate it into your answer. \$\endgroup\$ – syb0rg Feb 19 '14 at 0:56
  • \$\begingroup\$ @syb0rg How is this not a proper review? (This answer was recently flagged, that's why I'm asking) \$\endgroup\$ – Simon Forsberg Jul 16 '17 at 8:42
  • \$\begingroup\$ @SimonForsberg It seemed better served as a comment, and I still believe it would be. There isn't enough content in my opinion. Why doesn't the OP check the return of add methods, there is no reason given nor a link to point me to evidence? Would one throw a custom exception, or a standard library exception, and why? Where is the benefit in adding functions that return available space and full state, and how would that be used to refine the code in the question? Now for you and I, these questions are well known. But I think newcomers need more explanation than what was supplied here. \$\endgroup\$ – syb0rg Jul 16 '17 at 17:50
  • \$\begingroup\$ @syb0rg That arguably makes it a bad answer, not "not an answer". Short answers are fine. \$\endgroup\$ – Simon Forsberg Jul 17 '17 at 6:52

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.