Created
July 22, 2013 07:18
-
-
Save changbinwang/6051895 to your computer and use it in GitHub Desktop.
Fixed size priority queue
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class FixedSizePriorityQueue<E> extends TreeSet<E> { | |
private int elementsLeft; | |
public FixedSizePriorityQueue(int maxSize) { | |
super(new NaturalComparator()); | |
this.elementsLeft = maxSize; | |
} | |
public FixedSizePriorityQueue(int maxSize, Comparator<E> comparator) { | |
super(comparator); | |
this.elementsLeft = maxSize; | |
} | |
/** | |
* @return true if element was added, false otherwise | |
* */ | |
@Override | |
public boolean add(E e) { | |
if (elementsLeft == 0 && size() == 0) { | |
// max size was initiated to zero => just return false | |
return false; | |
} else if (elementsLeft > 0) { | |
// queue isn't full => add element and decrement elementsLeft | |
boolean added = super.add(e); | |
if (added) { | |
elementsLeft--; | |
} | |
return added; | |
} else { | |
// there is already 1 or more elements => compare to the least | |
int compared = super.comparator().compare(e, this.first()); | |
if (compared == 1) { | |
// new element is larger than the least in queue => pull the least and add new one to queue | |
pollFirst(); | |
super.add(e); | |
return true; | |
} else { | |
// new element is less than the least in queue => return false | |
return false; | |
} | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment