随笔-153  评论-235  文章-19  trackbacks-0
    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(0nullfalse);
    }
    
    
/**
     * 容量无限制,
     * 
@param desc true为降序.
     
*/
    
public TopPriorityQueue(boolean desc) {
        
this(0null, 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, nullfalse);
    }
    
    
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 流浪汗 阅读(848) 评论(0)  编辑  收藏 所属分类: JAVA/J2EE

只有注册用户登录后才能发表评论。


网站导航: