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.
FixedSizePriorityQueuebe aTreeSet? Do you want to support all methods of aTreeSet? I would internally use aTreeSetbut not extend it. – MrSmith42 Aug 30 '13 at 10:10pollLast()method inaddmethod? – tintinmj Aug 30 '13 at 14:34pollLast(), I remove the most irrelevant element and add new one, usingsuper.add(), leaving super to prioritize. – robosoul Sep 1 '13 at 13:48