packagenet.blogjava.chenlb.util;importjava.util.AbstractQueue;importjava.util.Comparator;importjava.util.Iterator;/***@param
* 容量capacity大于0,最多只能添加capacity个,多出的被删除掉.
* 删除时根据{@linkComparable}或{@linkComparator} 和 desc
* 如果comparator==null时使用Comparable
* non-thread safe
*@authorchenlb 2008-4-23 下午11:31:06*/publicclassTopPriorityQueueextendsAbstractQueueimplementsjava.io.Serializable {privatestaticfinallongserialVersionUID=1L;privateintsize;privateLinkedItem head;privateLinkedItem last;privateinttop;//top>0后,容量有限制privateComparator<?superE>comparator;privatebooleandesc;//降序/*** 容量无限制,升序.*/publicTopPriorityQueue() {this(0,null,false);
}/*** 容量无限制,
*@paramdesc true为降序.*/publicTopPriorityQueue(booleandesc) {this(0,null, desc);
}/*** 容量无限制,升序,用comparator排序*/publicTopPriorityQueue(Comparator<?superE>comparator) {this(0, comparator,false);
}/*** 容量无限制,用comparator排序
*@paramdesc true为降序*/publicTopPriorityQueue(Comparator<?superE>comparator,booleandesc) {this(0, comparator, desc);
}/*** 容量限制为capacity.超出容量限制的,会删除优先级最小(队尾).*/publicTopPriorityQueue(intcapacity) {this(capacity,null,false);
}publicTopPriorityQueue(intcapacity,booleandesc) {this(capacity,null, desc);
}publicTopPriorityQueue(intcapacity, Comparator<?superE>comparator) {this(capacity, comparator,false);
}publicTopPriorityQueue(intcapacity, Comparator<?superE>comparator,booleandesc) {
head=newLinkedItem();
last=head;
top=capacity;this.comparator=comparator;this.desc=desc;
}
@OverridepublicIteratoriterator() {//TODO 迭代器returnnewIt(head);
}
@Overridepublicintsize() {returnsize;
}publicbooleanoffer(E o) {//TODO 添加到适当的位置if(o==null) {thrownewIllegalArgumentException("不能添加值为null的!");
}
LinkedItem temp=newLinkedItem(o);/*last.next = temp;
temp.prev = last;*/if(last==head) {//第一个last.next=temp;
temp.prev=last;
last=temp;
}else{
LinkedItem tempPrev=last;if(comparator!=null) {while(tempPrev!=null&&tempPrev!=head) {intr=comparator.compare(tempPrev.data, temp.data);if(desc) {
r=0-r;
}if(r==1) {//tempPrev > temp//重置,继续向前找tempPrev=tempPrev.prev;
}else{//找到插入的位置break;
}
}
}elseif(oinstanceofComparable) {//用Comparablewhile(tempPrev!=null&&tempPrev!=head) {
ComparabletPrev=(Comparable) tempPrev.data;intr=tPrev.compareTo(temp.data);if(desc) {
r=0-r;
}if(r==1) {//tempPrev > temp//重置,继续向前找tempPrev=tempPrev.prev;
}else{//找到插入的位置break;
}
}
}if(tempPrev!=null) {//插入if(tempPrev==last) {//后面添加的last=temp;
}
temp.next=tempPrev.next;if(tempPrev.next!=null) {
tempPrev.next.prev=temp;
}
tempPrev.next=temp;
temp.prev=tempPrev;
}
}
size++;if(top>0&&size>top) {//去掉优先级最小的tail();
}returntrue;
}/*** 从栈底去除*/publicE tail() {if(last==head) {returnnull;
}
LinkedItem laster=last;
last=last.prev;
last.next=null;
laster.prev=null;
size--;returnlaster.data;
}publicE peek() {//TODO 取得栈顶值LinkedItem first=head.next;if(first!=null) {returnfirst.data;
}returnnull;
}publicE poll() {//TODO 从栈顶去除LinkedItem first=head.next;if(first!=null) {
head.next=first.next;if(first.next!=null) {
first.next.prev=head;
}
size--;returnfirst.data;
}returnnull;
}privateclassItimplementsIterator{
LinkedItem curr;publicIt(LinkedItem curr) {super();this.curr=curr;
}publicbooleanhasNext() {if(curr!=null&&curr.next!=null) {returntrue;
}returnfalse;
}publicE next() {
curr=curr.next;
E d=curr.data;returnd;
}publicvoidremove() {
curr.prev.next=curr.next;if(curr.next!=null) {
curr.next.prev=curr.prev;
}
size--;
}
}/***@param
* 链结点.
*@authorchenlb 2008-5-4 下午04:48:17*/privateclassLinkedItem {
LinkedItem prev;
E data;
LinkedItem next;publicLinkedItem() {
}publicLinkedItem(E o) {this.data=o;
}
}
}