2005/6 Q3
(a)
Public class MyPriorityQueue implements PriorityQueue {
	// instance state
	Private static class QueueItem {
		Object item;
		Int priority;
	}
	// e.g. solution with a single queue of 
	// priority-labelled items
	Java.util.Vector<QueueItem> items;
	// constructor
	Public MyPriorityQueue() {
		Items = new java.util.Vector<QueueItem>();
	}
	// put
	Public void put(Object item, int priority) {
		// entry protocol ? just need the lock
		Synchronized(this) {
			// (could have made method synchronized)
			// new item
			QueueItem qi = new QueueItem();
			qi.item = item;
			qi.priority = priority;
			// is the queue ordered by priority?
			// e.g. priority ordered, i.e. find
			// where to put the item
			int followingItemIndex = 0;
			for ( ; followingItemIndex<items.size(); 
				followingItemIndex++) 
			{
				// used generics so no need to cast
				QueueItem qi2 = items.element(followingItemIndex);
				If (qi2.priority<priority)
					break;
			}
			Items.insertElementAt(qi, followingItemIndex);
			// exit protocol ? wake all
			notifyAll();
		}
	}
	Public Object get(int minPriority) {
		Synchronized(this) {
			// entry protocol ? require item in
			// queue priority>= minPriority
			while(true) {
				// requires queue sorted by 
				// priority ? otherwise check ALL
				// items?
				if (items.size()>0) {
					QueueItem qi2 = items.elementAt(0);
					If (qi2.priority>=minPriority)
						break; // OK
				}
				// no item of sufficient priority
				try {
					wait();
				} catch(InterruptedException ie) 
				{ /* ignore */ }
			}
			// done entry protocol, got lock
			// since we have sorted queue
			QueueItem qi = items.elementAt(0);
			items.removeElementAt(0);
			// exit protocol
			// no-op
		}
	}



	Public Boolean readyToGet(int minPriority, 
long timeout) {
		long startTime = System.currentTimeMillis();
		synchronized(this) {
			// entry protocol
			while(true) {
				// requires queue sorted by 
				// priority ? otherwise check ALL
				// items?
				if (items.size()>0) {
					QueueItem qi2 = items.elementAt(0);
					If (qi2.priority>=minPriority)
						break; // OK
				}
				// no item of sufficient priority
				try {
					// check remaining timeout
					If (timeout==0)
						Return false;
					Long now = System.currentTimeMillis();
					Long elapsed = now-startTime;
					If (elapsed >= timeout)
						Return false;
					// timed delay
					wait(timeout - elapsed);
				} catch(InterruptedException ie) 
				{ /* ignore */ }
			}
			// done entry protocol
			Return true;
		}
	}
}