java庫里的PriorityQueue無法滿足我，它不能固定容量，不遍歷（遍歷后就無序了），它的排序因字是從小到大（雖然可以用Comparator來反轉大小順序）。我所要的是可以固定容量（在一大堆數據通信中選擇最大或最小的幾個數時很有用），可遍歷（不是一個個poll()）。
于是，在有空的時間里寫了一下。內容是一個雙向鏈表（帶頭的，頭不作保存數據），用插入排序。個人認為一個個添加的用插入排序效果比較好。從隊尾到隊頭找合適的插入位置，是穩定的排序。
添加的實體可以用Comparator或Comparable，如果這兩個都不是，就失去排序的效果。實現了比較高興，發表下，讓大家找出bug
package net.blogjava.chenlb.util;
import java.util.AbstractQueue;
import java.util.Comparator;
import java.util.Iterator;
/**
* @param <E>
* 容量capacity大于0,最多只能添加capacity個,多出的被刪除掉.<br/>
* 刪除時根據{@link Comparable}或{@link Comparator} 和 desc
* 如果comparator==null時使用Comparable<br/>
* non-thread safe
* @author chenlb 2008-4-23 下午11:31:06
*/
public class TopPriorityQueue<E> extends AbstractQueue<E> implements java.io.Serializable {
private static final long serialVersionUID = 1L;
private int size;
private LinkedItem head;
private LinkedItem last;
private int top; //top>0后,容量有限制
private Comparator<? super E> comparator;
private boolean desc; //降序
/**
* 容量無限制,升序.
*/
public TopPriorityQueue() {
this(0, null, false);
}
/**
* 容量無限制,
* @param desc true為降序.
*/
public TopPriorityQueue(boolean desc) {
this(0, null, desc);
}
/**
* 容量無限制,升序,用comparator排序
*/
public TopPriorityQueue(Comparator<? super E> comparator) {
this(0, comparator, false);
}
/**
* 容量無限制,用comparator排序
* @param desc true為降序
*/
public TopPriorityQueue(Comparator<? super E> comparator, boolean desc) {
this(0, comparator, desc);
}
/**
* 容量限制為capacity.超出容量限制的,會刪除優先級最小(隊尾).
*/
public TopPriorityQueue(int capacity) {
this(capacity, null, false);
}
public TopPriorityQueue(int capacity, boolean desc) {
this(capacity, null, desc);
}
public TopPriorityQueue(int capacity, Comparator<? super E> comparator) {
this(capacity, comparator, false);
}
public TopPriorityQueue(int capacity, Comparator<? super E> comparator, boolean desc) {
head = new LinkedItem();
last = head;
top = capacity;
this.comparator = comparator;
this.desc = desc;
}
@Override
public Iterator<E> iterator() {
// TODO 迭代器
return new It(head);
}
@Override
public int size() {
return size;
}
public boolean offer(E o) {
// TODO 添加到適當的位置
if(o == null) {
throw new IllegalArgumentException("不能添加值為null的!");
}
LinkedItem temp = new LinkedItem(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) {
int r = comparator.compare(tempPrev.data, temp.data);
if(desc) {
r = 0 - r;
}
if(r == 1) { //tempPrev > temp
//重置,繼續向前找
tempPrev = tempPrev.prev;
} else { //找到插入的位置
break;
}
}
} else if(o instanceof Comparable) { //用Comparable
while(tempPrev!=null && tempPrev != head) {
Comparable<E> tPrev = (Comparable<E>) tempPrev.data;
int r = 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();
}
return true;
}
/**
* 從棧底去除
*/
public E tail() {
if(last == head) {
return null;
}
LinkedItem laster = last;
last = last.prev;
last.next = null;
laster.prev = null;
size--;
return laster.data;
}
public E peek() {
// TODO 取得棧頂值
LinkedItem first = head.next;
if(first != null) {
return first.data;
}
return null;
}
public E poll() {
// TODO 從棧頂去除
LinkedItem first = head.next;
if(first != null) {
head.next = first.next;
if(first.next != null) {
first.next.prev = head;
}
size--;
return first.data;
}
return null;
}
private class It implements Iterator<E> {
LinkedItem curr;
public It(LinkedItem curr) {
super();
this.curr = curr;
}
public boolean hasNext() {
if(curr != null && curr.next != null) {
return true;
}
return false;
}
public E next() {
curr = curr.next;
E d = curr.data;
return d;
}
public void remove() {
curr.prev.next = curr.next;
if(curr.next != null) {
curr.next.prev = curr.prev;
}
size--;
}
}
/**
* @param <E>
* 鏈結點.
* @author chenlb 2008-5-4 下午04:48:17
*/
private class LinkedItem {
LinkedItem prev;
E data;
LinkedItem next;
public LinkedItem() {
}
public LinkedItem(E o) {
this.data = o;
}
}
}
posted on 2008-05-08 23:08
流浪汗 閱讀(1011)
評論(0) 編輯 收藏 所屬分類:
JAVA/J2EE