From 478ea40a48f781239e016570e59c9c4de5bd4ed8 Mon Sep 17 00:00:00 2001 From: jzhou Date: Sat, 8 Oct 2011 00:08:03 +0000 Subject: [PATCH] More classes for galois --- Robust/src/ClassLibrary/MGC/HashMap.java | 33 ++ Robust/src/ClassLibrary/MGC/Map.java | 2 + Robust/src/ClassLibrary/MGC/Thread.java | 6 + .../ClassLibrary/MGC/gnu/AbstractQueue.java | 166 +++++++++ .../src/ClassLibrary/MGC/gnu/Collections.java | 75 ++++ Robust/src/ClassLibrary/MGC/gnu/Lock.java | 327 +++++++++++++++++ .../ClassLibrary/MGC/gnu/PriorityQueue.java | 345 ++++++++++++++++++ 7 files changed, 954 insertions(+) create mode 100644 Robust/src/ClassLibrary/MGC/gnu/AbstractQueue.java create mode 100644 Robust/src/ClassLibrary/MGC/gnu/Lock.java create mode 100644 Robust/src/ClassLibrary/MGC/gnu/PriorityQueue.java diff --git a/Robust/src/ClassLibrary/MGC/HashMap.java b/Robust/src/ClassLibrary/MGC/HashMap.java index 9ec53db3..562ef51d 100644 --- a/Robust/src/ClassLibrary/MGC/HashMap.java +++ b/Robust/src/ClassLibrary/MGC/HashMap.java @@ -3,6 +3,7 @@ public class HashMap implements Map { float loadFactor; int numItems; int threshold; + Collection values; public HashMap() { init(16, 0.75f); @@ -143,4 +144,36 @@ public class HashMap implements Map { table[bin]=he; return null; } + + public Collection values() + { + if (values == null) + // We don't bother overriding many of the optional methods, as doing so + // wouldn't provide any significant performance advantage. + values = new AbstractCollection() + { + HashMap map; + + public AbstractCollection(HashMap m) { + this.map = map; + } + + public int size() + { + return size; + } + + public Iterator iterator() + { + // Cannot create the iterator directly, because of LinkedHashMap. + return HashMapIterator(map, 1); + } + + public void clear() + { + map.clear(); + } + }; + return values; + } } diff --git a/Robust/src/ClassLibrary/MGC/Map.java b/Robust/src/ClassLibrary/MGC/Map.java index 1156a956..3c50aace 100644 --- a/Robust/src/ClassLibrary/MGC/Map.java +++ b/Robust/src/ClassLibrary/MGC/Map.java @@ -246,4 +246,6 @@ public interface Map// * @return the number of mappings */ int size(); + + Collection values(); } diff --git a/Robust/src/ClassLibrary/MGC/Thread.java b/Robust/src/ClassLibrary/MGC/Thread.java index dd7bd5e5..917d3475 100644 --- a/Robust/src/ClassLibrary/MGC/Thread.java +++ b/Robust/src/ClassLibrary/MGC/Thread.java @@ -53,5 +53,11 @@ public class Thread implements Runnable { checkAccess();*/ this.daemon = daemon; } + + public static Thread currentThread() + { + System.out.println("Unimplemented Thread.currentThread()!"); + return null; + } } diff --git a/Robust/src/ClassLibrary/MGC/gnu/AbstractQueue.java b/Robust/src/ClassLibrary/MGC/gnu/AbstractQueue.java new file mode 100644 index 00000000..dd2a0922 --- /dev/null +++ b/Robust/src/ClassLibrary/MGC/gnu/AbstractQueue.java @@ -0,0 +1,166 @@ +/* + * Written by Doug Lea with assistance from members of JCP JSR-166 + * Expert Group and released to the public domain, as explained at + * http://creativecommons.org/licenses/publicdomain + */ + +package java.util; + +/** + * This class provides skeletal implementations of some {@link Queue} + * operations. The implementations in this class are appropriate when + * the base implementation does not allow null + * elements. Methods {@link #add add}, {@link #remove remove}, and + * {@link #element element} are based on {@link #offer offer}, {@link + * #poll poll}, and {@link #peek peek}, respectively but throw + * exceptions instead of indicating failure via false or + * null returns. + * + *

A Queue implementation that extends this class must + * minimally define a method {@link Queue#offer} which does not permit + * insertion of null elements, along with methods {@link + * Queue#peek}, {@link Queue#poll}, {@link Collection#size}, and a + * {@link Collection#iterator} supporting {@link + * Iterator#remove}. Typically, additional methods will be overridden + * as well. If these requirements cannot be met, consider instead + * subclassing {@link AbstractCollection}. + * + *

This class is a member of the + * + * Java Collections Framework. + * + * @since 1.5 + * @author Doug Lea + * @param the type of elements held in this collection + */ +public abstract class AbstractQueue/**/ + extends AbstractCollection/**/ + implements Queue/**/ { + + /** + * Constructor for use by subclasses. + */ + protected AbstractQueue() { + } + + /** + * Inserts the specified element into this queue if it is possible to do so + * immediately without violating capacity restrictions, returning + * true upon success and throwing an IllegalStateException + * if no space is currently available. + * + *

This implementation returns true if offer succeeds, + * else throws an IllegalStateException. + * + * @param e the element to add + * @return true (as specified by {@link Collection#add}) + * @throws IllegalStateException if the element cannot be added at this + * time due to capacity restrictions + * @throws ClassCastException if the class of the specified element + * prevents it from being added to this queue + * @throws NullPointerException if the specified element is null and + * this queue does not permit null elements + * @throws IllegalArgumentException if some property of this element + * prevents it from being added to this queue + */ + public boolean add(Object/*E*/ e) { + if (offer(e)) + return true; + else + throw new IllegalStateException("Queue full"); + } + + /** + * Retrieves and removes the head of this queue. This method differs + * from {@link #poll poll} only in that it throws an exception if this + * queue is empty. + * + *

This implementation returns the result of poll + * unless the queue is empty. + * + * @return the head of this queue + * @throws NoSuchElementException if this queue is empty + */ + public Object/*E*/ remove() { + Object/*E*/ x = poll(); + if (x != null) + return x; + else + throw new NoSuchElementException(); + } + + /** + * Retrieves, but does not remove, the head of this queue. This method + * differs from {@link #peek peek} only in that it throws an exception if + * this queue is empty. + * + *

This implementation returns the result of peek + * unless the queue is empty. + * + * @return the head of this queue + * @throws NoSuchElementException if this queue is empty + */ + public Object/*E*/ element() { + Object/*E*/ x = peek(); + if (x != null) + return x; + else + throw new NoSuchElementException(); + } + + /** + * Removes all of the elements from this queue. + * The queue will be empty after this call returns. + * + *

This implementation repeatedly invokes {@link #poll poll} until it + * returns null. + */ + public void clear() { + while (poll() != null) + ; + } + + /** + * Adds all of the elements in the specified collection to this + * queue. Attempts to addAll of a queue to itself result in + * IllegalArgumentException. Further, the behavior of + * this operation is undefined if the specified collection is + * modified while the operation is in progress. + * + *

This implementation iterates over the specified collection, + * and adds each element returned by the iterator to this + * queue, in turn. A runtime exception encountered while + * trying to add an element (including, in particular, a + * null element) may result in only some of the elements + * having been successfully added when the associated exception is + * thrown. + * + * @param c collection containing elements to be added to this queue + * @return true if this queue changed as a result of the call + * @throws ClassCastException if the class of an element of the specified + * collection prevents it from being added to this queue + * @throws NullPointerException if the specified collection contains a + * null element and this queue does not permit null elements, + * or if the specified collection is null + * @throws IllegalArgumentException if some property of an element of the + * specified collection prevents it from being added to this + * queue, or if the specified collection is this queue + * @throws IllegalStateException if not all the elements can be added at + * this time due to insertion restrictions + * @see #add(Object) + */ + public boolean addAll(Collection/**/ c) { + if (c == null) + throw new NullPointerException(); + if (c == this) + throw new IllegalArgumentException(); + boolean modified = false; + Iterator/**/ e = c.iterator(); + while (e.hasNext()) { + if (add(e.next())) + modified = true; + } + return modified; + } + +} diff --git a/Robust/src/ClassLibrary/MGC/gnu/Collections.java b/Robust/src/ClassLibrary/MGC/gnu/Collections.java index 416d9b18..748ade0f 100644 --- a/Robust/src/ClassLibrary/MGC/gnu/Collections.java +++ b/Robust/src/ClassLibrary/MGC/gnu/Collections.java @@ -96,4 +96,79 @@ public class Collections }*/ //TODO System.println("Collections.sort() invoked"); } + + static final /**/ int compare(Object/*T*/ o1, Object/*T*/ o2, Comparator/**/ c) + { + return c == null ? ((Comparable) o1).compareTo(o2) : c.compare(o1, o2); + } + + public static /*>*/ + Object/*T*/ min(Collection/**/ c) + { + return min(c, null); + } + + /** + * Find the minimum element in a Collection, according to a specified + * Comparator. This implementation iterates over the Collection, so it + * works in linear time. + * + * @param c the Collection to find the minimum element of + * @param order the Comparator to order the elements by, or null for natural + * ordering + * @return the minimum element of c + * @throws NoSuchElementException if c is empty + * @throws ClassCastException if elements in c are not mutually comparable + * @throws NullPointerException if null is compared by natural ordering + * (only possible when order is null) + */ + public static /* T*/Object min(Collection/**/ c, + Comparator/**/ order) + { + Iterator/**/ itr = c.iterator(); + Object/*T*/ min = itr.next(); // throws NoSuchElementExcception + int csize = c.size(); + for (int i = 1; i < csize; i++) + { + Object/*T*/ o = itr.next(); + if (compare(min, o, order) > 0) + min = o; + } + return min; + } + + public static /*> + T*/Object max(Collection/**/ c) + { + return max(c, null); + } + + /** + * Find the maximum element in a Collection, according to a specified + * Comparator. This implementation iterates over the Collection, so it + * works in linear time. + * + * @param c the Collection to find the maximum element of + * @param order the Comparator to order the elements by, or null for natural + * ordering + * @return the maximum element of c + * @throws NoSuchElementException if c is empty + * @throws ClassCastException if elements in c are not mutually comparable + * @throws NullPointerException if null is compared by natural ordering + * (only possible when order is null) + */ + public static /* T*/Object max(Collection/**/ c, + Comparator/**/ order) + { + Iterator/**/ itr = c.iterator(); + Object/*T*/ max = itr.next(); // throws NoSuchElementException + int csize = c.size(); + for (int i = 1; i < csize; i++) + { + Object/*T*/ o = itr.next(); + if (compare(max, o, order) < 0) + max = o; + } + return max; + } } // class Collections diff --git a/Robust/src/ClassLibrary/MGC/gnu/Lock.java b/Robust/src/ClassLibrary/MGC/gnu/Lock.java new file mode 100644 index 00000000..5e117a61 --- /dev/null +++ b/Robust/src/ClassLibrary/MGC/gnu/Lock.java @@ -0,0 +1,327 @@ +/* + * Written by Doug Lea with assistance from members of JCP JSR-166 + * Expert Group and released to the public domain, as explained at + * http://creativecommons.org/licenses/publicdomain + */ + +package java.util.concurrent.locks; +import java.util.concurrent.TimeUnit; + +/** + * {@code Lock} implementations provide more extensive locking + * operations than can be obtained using {@code synchronized} methods + * and statements. They allow more flexible structuring, may have + * quite different properties, and may support multiple associated + * {@link Condition} objects. + * + *

A lock is a tool for controlling access to a shared resource by + * multiple threads. Commonly, a lock provides exclusive access to a + * shared resource: only one thread at a time can acquire the lock and + * all access to the shared resource requires that the lock be + * acquired first. However, some locks may allow concurrent access to + * a shared resource, such as the read lock of a {@link ReadWriteLock}. + * + *

The use of {@code synchronized} methods or statements provides + * access to the implicit monitor lock associated with every object, but + * forces all lock acquisition and release to occur in a block-structured way: + * when multiple locks are acquired they must be released in the opposite + * order, and all locks must be released in the same lexical scope in which + * they were acquired. + * + *

While the scoping mechanism for {@code synchronized} methods + * and statements makes it much easier to program with monitor locks, + * and helps avoid many common programming errors involving locks, + * there are occasions where you need to work with locks in a more + * flexible way. For example, some algorithms for traversing + * concurrently accessed data structures require the use of + * "hand-over-hand" or "chain locking": you + * acquire the lock of node A, then node B, then release A and acquire + * C, then release B and acquire D and so on. Implementations of the + * {@code Lock} interface enable the use of such techniques by + * allowing a lock to be acquired and released in different scopes, + * and allowing multiple locks to be acquired and released in any + * order. + * + *

With this increased flexibility comes additional + * responsibility. The absence of block-structured locking removes the + * automatic release of locks that occurs with {@code synchronized} + * methods and statements. In most cases, the following idiom + * should be used: + * + * 

     Lock l = ...;
+ *     l.lock();
+ *     try {
+ *         // access the resource protected by this lock
+ *     } finally {
+ *         l.unlock();
+ *     }
+ *
+ * + * When locking and unlocking occur in different scopes, care must be + * taken to ensure that all code that is executed while the lock is + * held is protected by try-finally or try-catch to ensure that the + * lock is released when necessary. + * + *

{@code Lock} implementations provide additional functionality + * over the use of {@code synchronized} methods and statements by + * providing a non-blocking attempt to acquire a lock ({@link + * #tryLock()}), an attempt to acquire the lock that can be + * interrupted ({@link #lockInterruptibly}, and an attempt to acquire + * the lock that can timeout ({@link #tryLock(long, TimeUnit)}). + * + *

A {@code Lock} class can also provide behavior and semantics + * that is quite different from that of the implicit monitor lock, + * such as guaranteed ordering, non-reentrant usage, or deadlock + * detection. If an implementation provides such specialized semantics + * then the implementation must document those semantics. + * + *

Note that {@code Lock} instances are just normal objects and can + * themselves be used as the target in a {@code synchronized} statement. + * Acquiring the + * monitor lock of a {@code Lock} instance has no specified relationship + * with invoking any of the {@link #lock} methods of that instance. + * It is recommended that to avoid confusion you never use {@code Lock} + * instances in this way, except within their own implementation. + * + *

Except where noted, passing a {@code null} value for any + * parameter will result in a {@link NullPointerException} being + * thrown. + * + *

Memory Synchronization

+ * + *

All {@code Lock} implementations must enforce the same + * memory synchronization semantics as provided by the built-in monitor + * lock, as described in + * The Java Language Specification, Third Edition (17.4 Memory Model): + *

+ * + * Unsuccessful locking and unlocking operations, and reentrant + * locking/unlocking operations, do not require any memory + * synchronization effects. + * + *

Implementation Considerations

+ * + *

The three forms of lock acquisition (interruptible, + * non-interruptible, and timed) may differ in their performance + * characteristics, ordering guarantees, or other implementation + * qualities. Further, the ability to interrupt the ongoing + * acquisition of a lock may not be available in a given {@code Lock} + * class. Consequently, an implementation is not required to define + * exactly the same guarantees or semantics for all three forms of + * lock acquisition, nor is it required to support interruption of an + * ongoing lock acquisition. An implementation is required to clearly + * document the semantics and guarantees provided by each of the + * locking methods. It must also obey the interruption semantics as + * defined in this interface, to the extent that interruption of lock + * acquisition is supported: which is either totally, or only on + * method entry. + * + *

As interruption generally implies cancellation, and checks for + * interruption are often infrequent, an implementation can favor responding + * to an interrupt over normal method return. This is true even if it can be + * shown that the interrupt occurred after another action may have unblocked + * the thread. An implementation should document this behavior. + * + * @see ReentrantLock + * @see Condition + * @see ReadWriteLock + * + * @since 1.5 + * @author Doug Lea + */ +public interface Lock { + + /** + * Acquires the lock. + * + *

If the lock is not available then the current thread becomes + * disabled for thread scheduling purposes and lies dormant until the + * lock has been acquired. + * + *

Implementation Considerations + * + *

A {@code Lock} implementation may be able to detect erroneous use + * of the lock, such as an invocation that would cause deadlock, and + * may throw an (unchecked) exception in such circumstances. The + * circumstances and the exception type must be documented by that + * {@code Lock} implementation. + */ + void lock(); + + /** + * Acquires the lock unless the current thread is + * {@linkplain Thread#interrupt interrupted}. + * + *

Acquires the lock if it is available and returns immediately. + * + *

If the lock is not available then the current thread becomes + * disabled for thread scheduling purposes and lies dormant until + * one of two things happens: + * + *

+ * + *

If the current thread: + *

+ * then {@link InterruptedException} is thrown and the current thread's + * interrupted status is cleared. + * + *

Implementation Considerations + * + *

The ability to interrupt a lock acquisition in some + * implementations may not be possible, and if possible may be an + * expensive operation. The programmer should be aware that this + * may be the case. An implementation should document when this is + * the case. + * + *

An implementation can favor responding to an interrupt over + * normal method return. + * + *

A {@code Lock} implementation may be able to detect + * erroneous use of the lock, such as an invocation that would + * cause deadlock, and may throw an (unchecked) exception in such + * circumstances. The circumstances and the exception type must + * be documented by that {@code Lock} implementation. + * + * @throws InterruptedException if the current thread is + * interrupted while acquiring the lock (and interruption + * of lock acquisition is supported). + */ + //void lockInterruptibly() throws InterruptedException; + + /** + * Acquires the lock only if it is free at the time of invocation. + * + *

Acquires the lock if it is available and returns immediately + * with the value {@code true}. + * If the lock is not available then this method will return + * immediately with the value {@code false}. + * + *

A typical usage idiom for this method would be: + * 

+     *      Lock lock = ...;
+     *      if (lock.tryLock()) {
+     *          try {
+     *              // manipulate protected state
+     *          } finally {
+     *              lock.unlock();
+     *          }
+     *      } else {
+     *          // perform alternative actions
+     *      }
+     *
+ * This usage ensures that the lock is unlocked if it was acquired, and + * doesn't try to unlock if the lock was not acquired. + * + * @return {@code true} if the lock was acquired and + * {@code false} otherwise + */ + boolean tryLock(); + + /** + * Acquires the lock if it is free within the given waiting time and the + * current thread has not been {@linkplain Thread#interrupt interrupted}. + * + *

If the lock is available this method returns immediately + * with the value {@code true}. + * If the lock is not available then + * the current thread becomes disabled for thread scheduling + * purposes and lies dormant until one of three things happens: + *

+ * + *

If the lock is acquired then the value {@code true} is returned. + * + *

If the current thread: + *

+ * then {@link InterruptedException} is thrown and the current thread's + * interrupted status is cleared. + * + *

If the specified waiting time elapses then the value {@code false} + * is returned. + * If the time is + * less than or equal to zero, the method will not wait at all. + * + *

Implementation Considerations + * + *

The ability to interrupt a lock acquisition in some implementations + * may not be possible, and if possible may + * be an expensive operation. + * The programmer should be aware that this may be the case. An + * implementation should document when this is the case. + * + *

An implementation can favor responding to an interrupt over normal + * method return, or reporting a timeout. + * + *

A {@code Lock} implementation may be able to detect + * erroneous use of the lock, such as an invocation that would cause + * deadlock, and may throw an (unchecked) exception in such circumstances. + * The circumstances and the exception type must be documented by that + * {@code Lock} implementation. + * + * @param time the maximum time to wait for the lock + * @param unit the time unit of the {@code time} argument + * @return {@code true} if the lock was acquired and {@code false} + * if the waiting time elapsed before the lock was acquired + * + * @throws InterruptedException if the current thread is interrupted + * while acquiring the lock (and interruption of lock + * acquisition is supported) + */ + //boolean tryLock(long time, TimeUnit unit) throws InterruptedException; + + /** + * Releases the lock. + * + *

Implementation Considerations + * + *

A {@code Lock} implementation will usually impose + * restrictions on which thread can release a lock (typically only the + * holder of the lock can release it) and may throw + * an (unchecked) exception if the restriction is violated. + * Any restrictions and the exception + * type must be documented by that {@code Lock} implementation. + */ + void unlock(); + + /** + * Returns a new {@link Condition} instance that is bound to this + * {@code Lock} instance. + * + *

Before waiting on the condition the lock must be held by the + * current thread. + * A call to {@link Condition#await()} will atomically release the lock + * before waiting and re-acquire the lock before the wait returns. + * + *

Implementation Considerations + * + *

The exact operation of the {@link Condition} instance depends on + * the {@code Lock} implementation and must be documented by that + * implementation. + * + * @return A new {@link Condition} instance for this {@code Lock} instance + * @throws UnsupportedOperationException if this {@code Lock} + * implementation does not support conditions + */ + Condition newCondition(); +} diff --git a/Robust/src/ClassLibrary/MGC/gnu/PriorityQueue.java b/Robust/src/ClassLibrary/MGC/gnu/PriorityQueue.java new file mode 100644 index 00000000..5b23890b --- /dev/null +++ b/Robust/src/ClassLibrary/MGC/gnu/PriorityQueue.java @@ -0,0 +1,345 @@ +/* PriorityQueue.java -- Unbounded priority queue + Copyright (C) 2004, 2005 Free Software Foundation, Inc. + +This file is part of GNU Classpath. + +GNU Classpath is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 2, or (at your option) +any later version. + +GNU Classpath is distributed in the hope that it will be useful, but +WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GNU Classpath; see the file COPYING. If not, write to the +Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA +02110-1301 USA. + +Linking this library statically or dynamically with other modules is +making a combined work based on this library. Thus, the terms and +conditions of the GNU General Public License cover the whole +combination. + +As a special exception, the copyright holders of this library give you +permission to link this library with independent modules to produce an +executable, regardless of the license terms of these independent +modules, and to copy and distribute the resulting executable under +terms of your choice, provided that you also meet, for each linked +independent module, the terms and conditions of the license of that +module. An independent module is a module which is not derived from +or based on this library. If you modify this library, you may extend +this exception to your version of the library, but you are not +obligated to do so. If you do not wish to do so, delete this +exception statement from your version. */ + + +package java.util; + +import java.io.Serializable; + +/** + * @author Tom Tromey (tromey@redhat.com) + * @author Andrew John Hughes (gnu_andrew@member.fsf.org) + * @since 1.5 + */ +public class PriorityQueue/**/ extends AbstractQueue/**/ implements Serializable +{ + private static final int DEFAULT_CAPACITY = 11; + + private static final long serialVersionUID = -7720805057305804111L; + + /** Number of elements actually used in the storage array. */ + int used; + + /** + * This is the storage for the underlying binomial heap. + * The idea is, each node is less than or equal to its children. + * A node at index N (0-based) has two direct children, at + * nodes 2N+1 and 2N+2. + */ + Object/*E*/[] storage; + + /** + * The comparator we're using, or null for natural ordering. + */ + Comparator/**/ comparator; + + public PriorityQueue() + { + this(DEFAULT_CAPACITY, null); + } + + public PriorityQueue(Collection/**/ c) + { + this(Math.max(1, (int) (1.1 * c.size())), null); + + // Special case where we can find the comparator to use. + /*if (c instanceof SortedSet) + { + SortedSet ss = (SortedSet) c; + this.comparator = (Comparator) ss.comparator(); + // We can insert the elements directly, since they are sorted. + int i = 0; + for (E val : ss) + { + if (val == null) + throw new NullPointerException(); + storage[i++] = val; + } + } + else */if (c instanceof PriorityQueue) + { + PriorityQueue/**/ pq = (PriorityQueue/**/) c; + this.comparator = (Comparator/**/)pq.comparator(); + // We can just copy the contents. + System.arraycopy(pq.storage, 0, storage, 0, pq.storage.length); + } + + addAll(c); + } + + public PriorityQueue(int cap) + { + this(cap, null); + } + + public PriorityQueue(int cap, Comparator/**/ comp) + { + this.used = 0; + this.storage = /*(E[])*/ new Object[cap]; + this.comparator = comp; + } + + public PriorityQueue(PriorityQueue/**/ c) + { + this(Math.max(1, (int) (1.1 * c.size())), + (Comparator/**/)c.comparator()); + // We can just copy the contents. + System.arraycopy(c.storage, 0, storage, 0, c.storage.length); + } + + /*public PriorityQueue(SortedSet c) + { + this(Math.max(1, (int) (1.1 * c.size())), + (Comparator)c.comparator()); + // We can insert the elements directly, since they are sorted. + int i = 0; + for (E val : c) + { + if (val == null) + throw new NullPointerException(); + storage[i++] = val; + } + }*/ + + public void clear() + { + //Arrays.fill(storage, null); + for(int i = 0; i*/ comparator() + { + return comparator; + } + + public Iterator/**/ iterator() + { + return (Iterator)(new PriorityQueueIterator/**/(this)); + } + + public boolean offer(Object/*E*/ o) + { + if (o == null) + throw new NullPointerException(); + + int slot = findSlot(-1); + + storage[slot] = o; + ++used; + bubbleUp(slot); + + return true; + } + + public Object/*E*/ peek() + { + return used == 0 ? null : storage[0]; + } + + public Object/*E*/ poll() + { + if (used == 0) + return null; + Object/*E*/ result = storage[0]; + remove(0); + return result; + } + + public boolean remove(Object o) + { + if (o != null) + { + for (int i = 0; i < storage.length; ++i) + { + if (o.equals(storage[i])) + { + remove(i); + return true; + } + } + } + return false; + } + + public int size() + { + return used; + } + + // It is more efficient to implement this locally -- less searching + // for free slots. + public boolean addAll(Collection/**/ c) + { + if (c == this) + throw new IllegalArgumentException(); + + int newSlot = -1; + int save = used; + //for (Object/*E*/ val : c) + Iterator it = c.iterator(); + while(it.hasNext()) + { + Object val = it.next(); + if (val == null) + throw new NullPointerException(); + newSlot = findSlot(newSlot); + storage[newSlot] = val; + ++used; + bubbleUp(newSlot); + } + + return save != used; + } + + int findSlot(int start) + { + int slot; + if (used == storage.length) + { + resize(); + slot = used; + } + else + { + for (slot = start + 1; slot < storage.length; ++slot) + { + if (storage[slot] == null) + break; + } + // We'll always find a slot. + } + return slot; + } + + void remove(int index) + { + // Remove the element at INDEX. We do this by finding the least + // child and moving it into place, then iterating until we reach + // the bottom of the tree. + while (storage[index] != null) + { + int child = 2 * index + 1; + + // See if we went off the end. + if (child >= storage.length) + { + storage[index] = null; + break; + } + + // Find which child we want to promote. If one is not null, + // we pick it. If both are null, it doesn't matter, we're + // about to leave. If neither is null, pick the lesser. + if (child + 1 >= storage.length || storage[child + 1] == null) + { + // Nothing. + } + else if (storage[child] == null + || (Collections.compare(storage[child], storage[child + 1], + comparator) > 0)) + ++child; + storage[index] = storage[child]; + index = child; + } + --used; + } + + void bubbleUp(int index) + { + // The element at INDEX was inserted into a blank spot. Now move + // it up the tree to its natural resting place. + while (index > 0) + { + // This works regardless of whether we're at 2N+1 or 2N+2. + int parent = (index - 1) / 2; + if (Collections.compare(storage[parent], storage[index], comparator) + <= 0) + { + // Parent is the same or smaller than this element, so the + // invariant is preserved. Note that if the new element + // is smaller than the parent, then it is necessarily + // smaller than the parent's other child. + break; + } + + Object/*E*/ temp = storage[index]; + storage[index] = storage[parent]; + storage[parent] = temp; + + index = parent; + } + } + + void resize() + { + Object/*E*/[] new_data = /*(E[])*/ new Object[2 * storage.length]; + System.arraycopy(storage, 0, new_data, 0, storage.length); + storage = new_data; + } +} + +public class PriorityQueueIterator implements Iterator { + int index = -1; + int count = 0; + PriorityQueue queue; + + public PriorityQueueIterator(PriorityQueue queue) { + this.queue = queue; + } + + public boolean hasNext() + { + return count < used; + } + + public Object/*E*/ next() + { + while (this.queue.storage[++index] == null) + ; + + ++count; + return this.queue.storage[index]; + } + + public void remove() + { + this.queue.remove(index); + } +} -- 2.34.1