listpriorityqueue.java

java 的源代码

package com.reddragon2046.base.utilities.data;

import java.util.NoSuchElementException;

// Referenced classes of package com.reddragon2046.base.utilities.data:
//            SecondOrderSequence, xHashComparator, Array, PriorityQueue,
//            Sequence, Container, InputIterator, ForwardIterator,
//            BinaryPredicate

public class ListPriorityQueue extends SecondOrderSequence
    implements PriorityQueue
{

    public ListPriorityQueue()
    {
        this(((BinaryPredicate) (new xHashComparator())));
    }

    public ListPriorityQueue(BinaryPredicate comparator)
    {
        super(new Array());
        m_comparator = comparator;
    }

    public ListPriorityQueue(ListPriorityQueue queue)
    {
        super((Array)queue.getUnderlyingSequence().clone());
        m_comparator = queue.m_comparator;
    }

    public String toString()
    {
        return "ListPriorityQueue( " + getUnderlyingSequence().toString() + " )";
    }

    public synchronized Object clone()
    {
        return new ListPriorityQueue(this);
    }

    public synchronized void copy(ListPriorityQueue queue)
    {
        super.copy(queue);
        m_comparator = queue.m_comparator;
    }

    public boolean equals(Object object)
    {
        if(super.equals(object) && (object instanceof ListPriorityQueue))
        {
            ListPriorityQueue other = (ListPriorityQueue)object;
            return other.m_comparator.equals(m_comparator);
        } else
        {
            return false;
        }
    }

    public BinaryPredicate getComparator()
    {
        return m_comparator;
    }

    public synchronized Object top()
    {
        return getUnderlyingSequence().front();
    }

    public boolean add(Object object)
    {
        push(object);
        return true;
    }

    public synchronized void push(Object object)
    {
        Sequence seq = getUnderlyingSequence();
        seq.pushBack(object);
        pushHeap(seq.start(), seq.finish(), m_comparator);
    }

    public synchronized Object pop()
    {
        if(isEmpty())
        {
            throw new NoSuchElementException("ListPriorityQueue is empty");
        } else
        {
            popHeap(start(), finish(), m_comparator);
            return getUnderlyingSequence().popBack();
        }
    }

    public synchronized void swap(ListPriorityQueue queue)
    {
        super.swap(queue);
        BinaryPredicate tmpComparator = m_comparator;
        m_comparator = queue.m_comparator;
        queue.m_comparator = tmpComparator;
    }

    private static void pushHeap(ForwardIterator first, ForwardIterator last, BinaryPredicate comparator)
    {
        pushHeap(first, first.distance(last) - 1, 0, last.get(-1), comparator);
    }

    private static void pushHeap(ForwardIterator first, int holeIndex, int topIndex, Object value, BinaryPredicate comparator)
    {
        for(int parent = (holeIndex - 1) / 2; holeIndex > topIndex && comparator.execute(first.get(parent), value); parent = (holeIndex - 1) / 2)
        {
            first.put(holeIndex, first.get(parent));
            holeIndex = parent;
        }

        first.put(holeIndex, value);
    }

    private static void popHeap(ForwardIterator first, ForwardIterator last, BinaryPredicate comparator)
    {
        Object value = last.get(-1);
        last.put(-1, first.get());
        int holeIndex = 0;
        int len = first.distance(last) - 1;
        int topIndex = holeIndex;
        int secondChild;
        for(secondChild = 2 * (holeIndex + 1); secondChild < len; secondChild = 2 * (secondChild + 1))
        {
            if(comparator.execute(first.get(secondChild), first.get(secondChild - 1)))
                secondChild--;
            first.put(holeIndex, first.get(secondChild));
            holeIndex = secondChild;
        }

        if(secondChild == len)
        {
            first.put(holeIndex, first.get(secondChild - 1));
            holeIndex = secondChild - 1;
        }
        pushHeap(first, holeIndex, topIndex, value, comparator);
    }

    protected BinaryPredicate m_comparator;
    static final long serialVersionUID = 0x56f1b7e44e56942fL;
}