priorityqueue.java

SRI international 发布的OAA框架软件

    public boolean add(Object o) {
        return offer(o);
    }

    /**
     * Removes a single instance of the specified element from this
     * queue, if it is present.
     */
    public boolean remove(Object o) {
        if (o == null)
            return false;

        if (comparator == null) {
            for (int i = 1; i <= size; i++) {
                if (((Comparable)queue[i]).compareTo((Object)o) == 0) {
                    removeAt(i);
                    return true;
                }
            }
        } else {
            for (int i = 1; i <= size; i++) {
                if (comparator.compare((Object)queue[i], (Object)o) == 0) {
                    removeAt(i);
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * Returns an iterator over the elements in this queue. The iterator
     * does not return the elements in any particular order.
     *
     * @return an iterator over the elements in this queue.
     */
    public Iterator iterator() {
        return new Itr();
    }

    private class Itr implements Iterator {

        /**
         * Index (into queue array) of element to be returned by
         * subsequent call to next.
         */
        private int cursor = 1;

        /**
         * Index of element returned by most recent call to next,
         * unless that element came from the forgetMeNot list.
         * Reset to 0 if element is deleted by a call to remove.
         */
        private int lastRet = 0;

        /**
         * The modCount value that the iterator believes that the backing
         * List should have.  If this expectation is violated, the iterator
         * has detected concurrent modification.
         */
        private int expectedModCount = modCount;

        /**
         * A list of elements that were moved from the unvisited portion of
         * the heap into the visited portion as a result of "unlucky" element
         * removals during the iteration.  (Unlucky element removals are those
         * that require a fixup instead of a fixdown.)  We must visit all of
         * the elements in this list to complete the iteration.  We do this
         * after we've completed the "normal" iteration.
         *
         * We expect that most iterations, even those involving removals,
         * will not use need to store elements in this field.
         */
        private ArrayList forgetMeNot = null;

        /**
         * Element returned by the most recent call to next iff that
         * element was drawn from the forgetMeNot list.
         */
        private Object lastRetElt = null;

        public boolean hasNext() {
            return cursor <= size || forgetMeNot != null;
        }

        public Object next() {
            checkForComodification();
            Object result;
            if (cursor <= size) {
                result = (Object) queue[cursor];
                lastRet = cursor++;
            }
            else if (forgetMeNot == null)
                throw new NoSuchElementException();
            else {
                int remaining = forgetMeNot.size();
                result = forgetMeNot.remove(remaining - 1);
                if (remaining == 1)
                    forgetMeNot = null;
                lastRet = 0;
                lastRetElt = result;
            }
            return result;
        }

        public void remove() {
            checkForComodification();

            if (lastRet != 0) {
                Object moved = PriorityQueue.this.removeAt(lastRet);
                lastRet = 0;
                if (moved == null) {
                    cursor--;
                } else {
                    if (forgetMeNot == null)
                        forgetMeNot = new ArrayList();
                    forgetMeNot.add(moved);
                }
            } else if (lastRetElt != null) {
                PriorityQueue.this.remove(lastRetElt);
                lastRetElt = null;
            } else {
                throw new IllegalStateException();
            }

            expectedModCount = modCount;
        }

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

    public int size() {
        return size;
    }

    /**
     * Removes all elements from the priority queue.
     * The queue will be empty after this call returns.
     */
    public void clear() {
        modCount++;

        // Null out element references to prevent memory leak
        for (int i=1; i<=size; i++)
            queue[i] = null;

        size = 0;
    }

    public Object poll() {
        if (size == 0)
            return null;
        modCount++;

        Object result = (Object) queue[1];
        queue[1] = queue[size];
        queue[size--] = null;  // Drop extra ref to prevent memory leak
        if (size > 1)
            fixDown(1);

        return result;
    }

    /**
     * Removes and returns the ith element from queue.  (Recall that queue
     * is one-based, so 1 <= i <= size.)
     *
     * Normally this method leaves the elements at positions from 1 up to i-1,
     * inclusive, untouched.  Under these circumstances, it returns null.
     * Occasionally, in order to maintain the heap invariant, it must move
     * the last element of the list to some index in the range [2, i-1],
     * and move the element previously at position (i/2) to position i.
     * Under these circumstances, this method returns the element that was
     * previously at the end of the list and is now at some position between
     * 2 and i-1 inclusive.
     */
    private Object removeAt(int i) {
        Assert.assert_(i > 0 && i <= size);
        modCount++;

        Object moved = (Object) queue[size];
        queue[i] = moved;
        queue[size--] = null;  // Drop extra ref to prevent memory leak
        if (i <= size) {
            fixDown(i);
            if (queue[i] == moved) {
                fixUp(i);
                if (queue[i] != moved)
                    return moved;
            }
        }
        return null;
    }

    /**
     * Establishes the heap invariant (described above) assuming the heap
     * satisfies the invariant except possibly for the leaf-node indexed by k
     * (which may have a nextExecutionTime less than its parent's).
     *
     * This method functions by "promoting" queue[k] up the hierarchy
     * (by swapping it with its parent) repeatedly until queue[k]
     * is greater than or equal to its parent.
     */
    private void fixUp(int k) {
        if (comparator == null) {
            while (k > 1) {
                int j = k >> 1;
                if (((Comparable)queue[j]).compareTo((Object)queue[k]) <= 0)
                    break;
                Object tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
                k = j;
            }
        } else {
            while (k > 1) {
                int j = k >>> 1;
                if (comparator.compare((Object)queue[j], (Object)queue[k]) <= 0)
                    break;
                Object tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
                k = j;
            }
        }
    }

    /**
     * Establishes the heap invariant (described above) in the subtree
     * rooted at k, which is assumed to satisfy the heap invariant except
     * possibly for node k itself (which may be greater than its children).
     *
     * This method functions by "demoting" queue[k] down the hierarchy
     * (by swapping it with its smaller child) repeatedly until queue[k]
     * is less than or equal to its children.
     */
    private void fixDown(int k) {
        int j;
        if (comparator == null) {
            while ((j = k << 1) <= size && (j > 0)) {
                if (j<size &&
                    ((Comparable)queue[j]).compareTo((Object)queue[j+1]) > 0)
                    j++; // j indexes smallest kid

                if (((Comparable)queue[k]).compareTo((Object)queue[j]) <= 0)
                    break;
                Object tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
                k = j;
            }
        } else {
            while ((j = k << 1) <= size && (j > 0)) {
                if (j<size &&
                    comparator.compare((Object)queue[j], (Object)queue[j+1]) > 0)
                    j++; // j indexes smallest kid
                if (comparator.compare((Object)queue[k], (Object)queue[j]) <= 0)
                    break;
                Object tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
                k = j;
            }
        }
    }

    /**
     * Establishes the heap invariant (described above) in the entire tree,
     * assuming nothing about the order of the elements prior to the call.
     */
    private void heapify() {
        for (int i = size/2; i >= 1; i--)
            fixDown(i);
    }

    /**
     * Returns the comparator used to order this collection, or <tt>null</tt>
     * if this collection is sorted according to its elements natural ordering
     * (using <tt>Comparable</tt>).
     *
     * @return the comparator used to order this collection, or <tt>null</tt>
     * if this collection is sorted according to its elements natural ordering.
     */
    public Comparator comparator() {
        return comparator;
    }

    /**
     * Save the state of the instance to a stream (that
     * is, serialize it).
     *
     * @serialData The length of the array backing the instance is
     * emitted (int), followed by all of its elements (each an
     * <tt>Object</tt>) in the proper order.
     * @param s the stream
     */
    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException{
        // Write out element count, and any hidden stuff
        s.defaultWriteObject();

        // Write out array length
        s.writeInt(queue.length);

        // Write out all elements in the proper order.
        for (int i=1; i<=size; i++)
            s.writeObject(queue[i]);
    }

    /**
     * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
     * deserialize it).
     * @param s the stream
     */
    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        // Read in size, and any hidden stuff
        s.defaultReadObject();

        // Read in array length and allocate array
        int arrayLength = s.readInt();
        queue = new Object[arrayLength];

        // Read in all elements in the proper order.
        for (int i=1; i<=size; i++)
            queue[i] = (Object) s.readObject();
    }

}