Educational Objectives: After completing this assignment, the student should be able to accomplish the following:
Apply generic algorithms in solving programming problems
Define and give examples of generic associative containers
Define and give examples of generic algorithms
Define the ADT Priority Queue
Implement the ADT Priority Queue as a generic associative container subject to various constraints, including:
Push(t) <= O(size), Pop() = T(1)
Push(t) = T(1), Pop() <= O(size)
Push(t) <= O(log size), Pop() <= O(log size)
Use namespaces to develop and test multiple implementations of an ADT
Experience applying the following concepts: associative generic containers; generic algorithms; priority queue; and developing and testing multiple implementations using namespace.
Operational Objectives: Design and implement six (6) distinct implementations of the Priority Queue template PriorityQueue based on List, MOList, Vector (2), MOVector, and Deque. Use namespaces pq1, pq2, ... , pq6 to scope the six variations.
Deliverables: Two files pq.h and log.txt
Background:
A priority queue stores elements of typename T with a priority determined by an object of a predicate class P. The operations are syntactically queue-like but have associative semantics (rather than positional semantics, as in an ordinary queue). The operations for a priority queue PQ and informal descriptions of them are as follows:
void Push (const T& t) // places t in the priority queue, position unspecified
void Pop () // removes the highest priority item from the priority queue
T Front () // returns (a copy of) the highest priority item in the priority queue
bool Empty () // returns true iff the priority queue is empty
as well as default constructor, destructor, copy constructor, and assignment operator (i.e., we need priority queue to be a proper type). We will also use the following additional operations (as usual for our course library):
void Clear () // makes the priority queue empty
size_t Size () // returns the number of elements in the priority queue
void Dump (std::ostream& os, char ofc = ''\0'') // display underlying structure
Priority queues are used in several important applications, including:
Operating system job schedulers
Communications Satelite schedulers
Discrete Event simulations
Embedded/RealTime Systems
Control structures for certain algorithms, such as Best First Search
Priority queues are traditionally built as adaptations of other data structures using special algorithms. The most sophisticated of these are discussed in the chapter Binary Heaps. However, us usual, "most sophisticated" does not always translate as "best". "Best" is usually determined by client programmers based on the client needs. (Compare g_insertion_sort() with g_heap_sort() for example.)
In this assignment you will build priority queues using (1) one of our familiar Containers Vector, Deque, List, MOVector, MOList as the data storage facility and (2) an appropriate algorithm for the search mechanism. In the case of heap-based priority queue (case 6) two generic algorithms will be required.
Procedural Requirements
The official development/testing/assessment environment is: gnu g++ on the linprog machines.
Be sure start and maintain your log.txt.
After creating your log.txt, begin by copying all of the files from LIB/hw5 into your project directory.
Create and work within a separate subdirectory. The usual COP 4530 rules apply (see Introduction/Work Rules). In particular: It is a violation of course ethics and the student honor code to use, or attempt to use, files other than those explicitly distributed in the course code library.
Place all work in one file named pq.h.
Turn in the files pq.h and log.txt using the hw5submit.sh script.
Warning: Submit scripts do not work on the program and linprog servers. Use shell.cs.fsu.edu to submit assignments. If you do not receive the second confirmation with the contents of your project, there has been a malfunction.
Technical Requirements and Specifications
Place all work in one file named pq.h. The code should use 6 distinct namespaces: std, fsu, pq1, pq2, pq3, pq4, pq5, and pq6.
The first two namespaces are those encountered in the standard and course libraries. The other six are defined in the submitted code. These six namespaces define the scope of certain definitions, as shown in the following sample file documentation:
/* pq.h
Various implementations for PriorityQueue < T , P >
organized by namespace as follows:
nmsp stbl container element order central algorithm push pop front
---- ---- --------- ------------- ------------------- ---- --- -----
pq1 y List unordered fsu::g_max_element() O(1) O(n) O(n)
pq2 y MOList sorted MOList::Insert O(n) O(1) O(1)
pq3 n Vector unordered fsu::g_max_element() AO(1) O(n) O(n)
pq4 y Vector unordered fsu::g_max_element() AO(1) O(n) O(n)
pq5 y MOVector sorted OVector::Insert O(n) O(1) O(1)
pq6 n Deque head fsu::g_push/pop_heap() O(log n) O(log n) O(1)
The pq3 version just copy the last element over the element
to be removed, whereas the pq4 version does a leapfrog copy. Note that the
leapfrog copy version is stable, the 1-element copy version is not.
All of the pq namespaces are defined in this file.
*/
Every method implementation must be one of three types:
Type 1 (no search is required): the body consists of a single call to an operation of the underlying container
Type 2 (search is required): the body uses a member function or a generic generic search algorithm with a minimum of ancillary code.
Type 3 (heap-based): the body uses a generic heap algorithm with a minimum of ancillary code.
Your submission is required to run correctly with the distributed client program tests/fpq.cpp. We will assess using fpq.cpp and another client program that uses a priority queue to sort data.
The log file should contain (1) statements of the runtime of the various priority queue methods, (2) explanations [informal proofs] that your statements are correct, and (3) testing procedures and results of testing. (See specific ABET outcomes iii and iv above.)
The file level documentation should contain brief descriptions of the design for each implementation of priority queue. (See specific ABET outcome v above). Please also include this in your log file.
Hints:
Here is a start on pq1, along with the include files that you will need:
· /* pq.h */
·
· #include // fsu::g_max_element()
· #include // fsu::g_push_heap() , fsu::g_pop_heap()
· #include // fsu::List<> , fsu::List<>::Iterator
· #include // fsu::Vector<> , fsu::Vector<>::Iterator
· #include // fsu::Deque<> , fsu::Deque<>::Iterator
· #include // fsu::MOList<> , fsu::MOList<>::Iterator
· #include // fsu::MOVector<> , fsu::MOVector<>::Iterator
·
· namespace pq1
· {
·
· template
· class PriorityQueue
· {
· typedef typename fsu::List < T > ContainerType;
· typedef T ValueType;
· typedef P PredicateType;
·
· // store elements in unsorted order in list
· // Push(t): PushBack(t)
· // Front(): use fsu::g_max_element() to locate largest, then return element
· // Pop() : use fsu::g_max_element() to locate largest, then remove element
·
· PredicateType p_;
· ContainerType c_;
·
· public:
· PriorityQueue() : p_(), c_()
· {}
·
· explicit PriorityQueue(P p) : p_(p), c_()
· {}
·
· void Push (const T& t)
· {
· // TBS
· }
·
· void Pop ()
· {
· // TBS
· }
·
· const T& Front () const
· {
· typedef typename ContainerType::ConstIterator IteratorType;
· IteratorType i = fsu::g_max_element (c_.Begin(), c_.End(), p_);
· return *i;
· }
·
· void Clear ()
· {
· // TBS
· }
·
· bool Empty () const
· {
· // TBS
· }
·
· size_t Size () const
· {
· // TBS
· }
·
· void Dump (std::ostream& os, char ofc = ''\0'') const
· {
· // TBS
· }
· };
·
· } // namespace pq1
·
· namespace pq2
· {
· // yada dada
Note that we have used in-class implementations, as we did with the adaptor classes Stack and Queue. This is an acceptable practice for classes like PriorotyQueue that are essentially adaptors of existing technology to a new interface.
Clear(), Empty(), and Size() should just call the container operation of the same name. Dump() should output the contents of the underlying container. That leaves only the three operations Push(t), Pop(), and Front() requiring plan-specific implementations.
Note that an implementation of Front() is supplied above, as an illustration of how to apply generic algorithms.
Note that there are two constructors. The first is the parameterless, or "default", constructor. It creates the predicate object using the default PredicateType constructor. The second takes a predicate object as an argument, so that the client can supply whatever exotic priority scheme is desired. By tradition established in the STL, function object arguments are passes by value.
If the model above is followed for all six versions, the default destructor, copy constructor, and assignment operator should work, so neither prototype nor implementation of these operations is necessary. (Can you explain why?)
The following operations can use the identical implementation across all the namespaces: Constructors and other proper type operations, Clear(), Empty(), and Size(). Thus the only operations whose implementation varies from one namespace to another are the three that define the priority queue concept: Push(), Pop(), and Front().
The term "IteratorType" is defined locally as a convenience only. This type is an iterator for the underlying structure, not an iterator for PriorityQueue.
Note the "const correctness" indicated in the example. Methods that should not disturb the priority queue are specified const. And the return type of Front() is a const reference, which prevents clients from modifying the element in the priority queue (which could disrupt the internal structure of the implementation).
Look carefully in fpq.cpp to see how to declare and use PriorityQueue objects, in particular, how the predicate is instantiated. (We will use LessThan or GreaterThan for the predicate class in our tests.)
Here are the "implementation plan" documentation statements for all 6 versions:
· namespace pq1
· {
· ...
· typedef typename fsu::List < T > ContainerType;
· typedef T ValueType;
· typedef P PredicateType;
·
· // store elements in unsorted order in list
· // Push(t): PushBack(t) (or PushFront(t)) will do
· // Front(): use fsu::g_max_element() to locate largest, then return element
· // Pop() : use fsu::g_max_element() to locate largest, then remove
· ...
· } // namespace pq1
·
· namespace pq2
· {
· ...
· typedef typename fsu::MOList < T , P > ContainerType;
· typedef T ValueType;
· typedef P PredicateType;
·
· // store elements in increasing order in list
· // last element is largest
· // Push(t): use MOList::LowerBound ()
· // Front(): return back element of list
· // Pop() : remove last element of list
· ...
· } // namespace pq2
·
· namespace pq3
· {
· ...
· typedef typename fsu::Vector < T > ContainerType;
· typedef T ValueType;
· typedef P PredicateType;
·
· // store elements in unsorted order in vector
· // Push(t): PushBack(t)
· // Front(): use fsu::g_max_element() to locate largest, then return element
· // Pop() : use fsu::g_max_element() to locate largest, then "remove"
· // "remove" can be done two ways:
· // (1) copy last element to popped element, then Popback()
· // Note that (1) is unstable but O(1)
· // (1) suggested by Janice Murillo March 2004
· // (2) "leapfrog" copy elements down one index, starting at popped element, then PopBack()
· // Note that (2) is stable and O(n)
· // In either case, both Front() and Pop() are O(n)
· // due to the call to g_max_element().
· // pq3 uses (1)
· // pq4 uses (2)
· ...
· } // namespace pq3
·
· namespace pq4
· {
· ...
· typedef typename fsu::Vector < T > ContainerType;
·