com.putable.pqueue: A 'from-scratch' fast intrusive priority queue A component of UNM CS351 F'13 Individual Project 2 See (P.2) for dates and deliverables See (P.4) for changes. Document version 0.9 Last revision: Sat Oct 5 05:10:03 2013 ------------------------------------------------- ((P.0)) Table of Contents (P.1) Introduction (P.2) Requirements and restrictions (P.3) (P.4) Document revision history ------------------------------------------------- ((P.1)) INTRODUCTION: There are two key concepts to introduce: The concept of a priority queue, and the concept of an intrusive container. ((P.1.1)) PRIORITY QUEUES: A 'priority queue' (abbreviated 'pqueue' or 'PQ') is a data structure for managing objects with ordered keys, where the ordering determines 'priority'. A PQ's special power is to find and remove the highest priority object very efficiently. ((P.1.1.1)) We will model priority by requiring that objects to be contained in the priority queue must implement the Comparable interface (as well as other restrictions, see (P.2)), and we define priority such that the object with the SMALLEST key, as determined by calls to the Comparable.compareTo(), is considered the HIGHEST priority object. In other words, we are developing a pq with a fast 'find-min' operation, rather than 'find-max'. ((P.1.1.2)) A 'basic' priority queue implementation holding N objects consumes O(N) space, and supports these operations and time bounds: ((P.1.1.2.1)) Insert a suitable object into the PQ in amortized O(log N) time. ((P.1.1.2.2)) Remove the highest priority object from the PQ in O(log N) time. ((P.1.1.3)) A 'advanced' priority queue implementation holding N objects has all the capabilities and restrictions of a 'basic' priority queue, but additionally supports these operations and time bounds: ((P.1.1.3.1)) Delete an object from anywhere in the PQ (not just the highest priority one) in O(log N) time ((P.1.1.4)) For the P2D1 deliverable, only a 'basic' priority queue -- but implemented 'from scratch' -- is required (satisfying certain interfaces, and along with its unit tests of course). For the P2D2 deliverable, an 'advanced' priority queue must be constructed. ((P.1.1.5)) Although, in general, there are many ways to implement a fast priority queue, given the interfaces we are required to use (P.2), the implementation called a 'heap priority queue' is the only viable candidate. Implementors are encouraged to familiarize themselves with this approach ahead of the class discussion of it. ((P.1.2)) INTRUSIVE CONTAINERS: Loosely speaking, an intrusive container is one that 'makes demands' on the objects it contains. A data structure like an array of references, for example, makes no demands on the objects it contains -- they can be anything that can be referred to. An array is perhaps the ultimate 'non-inrusive container'. ((P.1.2.1)) A hash table, by contrast, requires the contained objects be hashable and define equality; a search tree requires the contained objects to be comparable to each other. So a hash table or search tree can be viewed as 'more intrusive' than an array -- but usually the 'intrusive container' term is reserved for even more demanding containers. ((P.1.2.2)) The Java Collection classes, including its Lists and Maps and Queues of many sorts, are all considered (relatively) non-intrusive in that they require no more from the contained objects than some combination of hashCode(), equals(), and/or compareTo(). ((P.1.2.2.1)) That _lack_ of intrusiveness is considered a feature of the Java Collection classes, and often it is -- but it has drawbacks as well. In particular, non-intrusive containers have difficulty dealing with objects directly by reference. ((P.1.2.2.2)) For example, the remove(Object) method in the (non-intrusive) java.util.LinkedList class runs in O(N) time for a list of N elements -- searching from the head of the list to find the first Object that is equals() to the Object provided. ((P.1.2.2.3)) By contrast, in an _intrusive_ doubly-linked list, objects specified by reference can be removed in O(1) time. But to accomplish that, the 'next item' and 'previous item' pointers needed to form the list must _already exist_ in each object being placed on the list. It is in that sense that the container 'intrudes' into the contained objects: The contained objects must have data members or other support specifically and solely for use by the container. ((P.1.2.3)) Similarly, an intrusive priority queue will require specific abilities in all objects it will contain. In Java, a natural way to accomplish that is require that all objects-to-be-contained implement an interface that specifies those required abilities. ((P.1.2.3.1)) For this project, the interface that contained objects must implement is called com.putable.pqueue.PQAble, and the interface that the pqueue itself implements is called com.putable.pqueue.PQueue. See (P.2). ------------------------------------------------- ((P.2)) REQUIREMENTS AND RESTRICTIONS: To maximize learning and demonstrate our mastery of Java, the priority queue made for this project is _NOT_ allowed to use any of the Java Collection classes. Of course that means no PriorityQueue, but it ALSO means: no List, LinkedList, or ArrayList; no Map, HashMap, or TreeMap; and so on. You can use primitive types and arrays, and Strings as needed for toString() or other messaging, and the supplied interfaces (P.2.1). ((P.2.1)) See P2PQ.jar for the two interfaces that define our fast intrusive priority, and one abstract class that manages the intrusive state needed by the PQ. All the sources in P2PQ.jar must be used AS-IS, without modifications. ------------------------------------------------- ((P.3)) ------------------------------------------------- ((P.4)) Document revision history ((P.4.1)) This is version 0.9 of this document, released Sat Oct 5 09:36:36 2013.