/** Returns but does not remove an entry with minimum key. */ public Entry min () throws EmptyPriorityQueueException { if (L.isEmpty()) throw new EmptyPriorityQueueException("priority queue is empty"); else return (Entry) L.first().element(); } /** Inserts a key-value pair and return the entry created. */ public Entry insert (Object k, Object v) throws InvalidKeyException { checkKey(k); // auxiliary key-checking method (could throw exception) Entry entry = new MyEntry(k, v); insertEntry(entry); // auxiliary insertion method return entry; } /** Auxiliary method used for insertion. */ protected void insertEntry(Entry e) { Object k = e.key(); if (L.isEmpty()) { actionPos = L.insertFirst(e); // insert into empty list } else if (c.compare(k, key(L.last())) > 0) { actionPos = L.insertLast(e); // insert at the end of the list } else { Position curr = L.first(); while (c.compare(k, key(curr))> 0) { curr = L.next(curr); // advance toward insertion position } actionPos = L.insertBefore(curr, e); // useful for subclasses } } /** Removes and returns an entry with minimum key. */ public Entry removeMin() throws EmptyPriorityQueueException { if (L.isEmpty()) throw new EmptyPriorityQueueException("priority queue is empty"); else return (Entry) (L.remove(L.first())); } protected Object key(Position pos) { return ((Entry) pos.element()).key(); }