Subject Computer Science Data Structures and Algorithms

Question

Priority Queues
Generic implementations of priority queue

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() = Θ(1)
       Push(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

   
Pre-requisite Knowledge Required: Be sure that you have mastered the material in these chapters before beginning the assignment:
Iterators, Generic Algorithms, Introduction to Trees, and Binary Heaps.

Operational Objectives: Design and implement six (6) distinct implementations of the Priority Queue template PriorityQueue<T,P> based on List<T>, MOList<T,P>, Vector<T> (2), MOVector<T,P>, and Deque<T>. 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<T,P> 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   () const    // returns (usually by const reference) the highest priority item in the priority queue
    void   Clear   ()          // makes the priority queue empty
    bool   Empty   () const    // returns true iff the priority queue is empty
    size_t Size    () const    // returns the number of elements in the priority queue

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:

    const P& GetPredicate () const // returns ref to predicate object
    void      Dump         (std::ostream& os, char ofc = '') const // displays underlying structure

These last operations are useful in development and performace testing. We could, for example, drop in a "spy" version of order and use GetPredicate to obtain counts of the number of calls, obtaining runtime data on the implementation. Dump gives a snapshot of the underlying container, useful in development and testing.

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<T>, Deque<T>, List<T>, MOVector<T,P>, MOList<T,P> 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 specified in the Course Organizer.

    Be sure start and maintain your log.txt.

    After creating your log.txt, begin by copying all of the files from LIB/proj8 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 submit script LIB/scripts/submit.sh and the configuration file LIB/proj8/deliverables.sh.

    Warning: The submit system uses CS email to deliver your assignment. It does not work on the program or linprog servers. Use shell.cs.fsu.edu to submit assignments. If you do not receive the second confirmation with the contents of your submission, 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   yes List      unordered    fsu::g_max_element()   O(1)    O(n)    O(n)
      pq2   yes MOList    sorted       MOList::Insert()       O(n)    O(1)    O(1)
      pq3   no   Deque    unordered    fsu::g_max_element()   AO(1)    O(n)    O(n)
      pq4   yes Deque    unordered    fsu::g_max_element()   AO(1)    O(n)    O(n)
      pq5   yes MOVector sorted       MOVector::Insert()    O(n)    O(1)    O(1)
      pq6   no   Vector    heap          fsu::g_push/pop_heap() O(log n) O(log n) O(1)

      The pq3 version just copies 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 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.

    The file level documentation should contain brief descriptions of the design for each implementation of priority queue. 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 <genalg.h>    // fsu::g_max_element()
       #include <gheap.h>    // fsu::g_push_heap()    , fsu::g_pop_heap()
       #include <list.h>      // fsu::List<>    , fsu::List<>::Iterator
       #include <vector.h>    // fsu::Vector<>   , fsu::Vector<>::Iterator
       #include <deque.h>    // fsu::Deque<>    , fsu::Deque<>::Iterator
       #include <olist.h>    // fsu::MOList<>   , fsu::MOList<>::Iterator
       #include <ovector.h>   // fsu::MOVector<> , fsu::MOVector<>::Iterator

       namespace pq1
       {

          template <typename T, class P >
          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 ()
            {
             c_.Clear();
            }
         
            bool Empty () const
            {
             return c_.Empty();
            }
         
            size_t Size () const
            {
             return c_.Size();
            }
         
            const P& GetPredicate() const
            {
             return p_;
            }
         
            void Dump (std::ostream& os, char ofc = '') const
            {
             c_.Display(os,ofc);
            }
          };
         
       } // 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() just call the container operation of the same name. GetPredicate() returns the underlying predicate object. And Dump(os,ofc) outputs the contents of the underlying container. The methods Clear, Empty, Size, GetPredicate, and Dump use exactly the same code across all six implementations. That leaves only the three operations Push(t), Pop(), and Front() requiring plan-specific implementations.

    Note that an implementation of pq1::PriorityQueue<T,P>::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. The example code for the constructors for the pq1 case can be used for the other five cases.

    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, Size, GetPredicate, and Dump. 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" (used in the example implementation of Pop) 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<T,P> objects, in particular, how the predicate is instantiated. (We will use LessThan<T> or GreaterThan<T> 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::Insert (t)
          // Front(): return back element of list
          // Pop() : remove last element of list
          ...
       } // namespace pq2

       namespace pq3
       {
          ...
          typedef typename fsu::Deque < 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::Deque < 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 pq4

       namespace pq5
       {
          ...
          typedef typename fsu::MOVector < T , P >       ContainerType;
          typedef T                                     ValueType;
          typedef P                                     PredicateType;

          // store elements in increasing order in vector
          // last element is largest
          // Push(t): use MOVector::Insert(t)
          // Front(): return back element of vector
          // Pop() : remove element from vector
          ...
       } // namespace pq5

       namespace pq6
       {
          ...
          typedef typename fsu::Vector < T >               ContainerType;
          typedef T                                        ValueType;
          typedef P                                        PredicateType;

          // store elements in partial order using heap algorithms
          // first element is largest
          // Push(t): c_.PushBack(t) followed by g_push_heap()
          // Front(): c_.Front()
          // Pop() : g_pop_heap() followed by c_.PopBack()
          ...
       } // namespace pq6

    Sample executables fpq?.x and pqsorttest?.x will be available in area51.

    There are two check scripts that can be used to test your code:
       Create subdirectory named testbench and cd into that directory.
       Copy all files from testfiles into testbench.
       Change "check.*" to executable permissions.
       Run check.fpq fpq.com1.
       Examine fpq.com1, create other fpq comamnd files, and run check on those files.
       Run check.pqsort pqsort.data1.
       Examine pqsort.data1, create other pqsort.data files, and run check.pqsort on those files.

Solution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

#pragma once

#include <genalg.h> // fsu::g_max_element()
#include <gheap.h> // fsu::g_push_heap() , fsu::g_pop_heap()
#include <list.h> // fsu::List<> , fsu::List<>::Iterator
#include <vector.h> // fsu::Vector<> , fsu::Vector<>::Iterator
#include <deque.h> // fsu::Deque<> , fsu::Deque<>::Iterator
#include <olist.h> // fsu::MOList<> , fsu::MOList<>::Iterator
#include <ovector.h> // fsu::MOVector<> , fsu::MOVector<>::Iterator

namespace pq1
{

template <typename T, class P >
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
c_.PushBack(t);
}

void Pop()
{
// TBS
typedef typename ContainerType::ConstIterator IteratorType;
IteratorType i = fsu::g_max_element(c_.Begin(), c_.End(), p_);
c_.Remove(i);
}

const T& Front() const
{
typedef typename ContainerType::ConstIterator IteratorType;
IteratorType i = fsu::g_max_element(c_.Begin(), c_.End(), p_);
return *i;
}

void Clear()
{
c_.Clear();
}

bool Empty() const
{
return c_.Empty();
}

size_t Size() const
{
return c_.Size();
}

const P& GetPredicate() const
{
return p_;
}

void Dump(std::ostream& os, char ofc = '\0') const
{
c_.Display(os, ofc);
}
};

} // namespace pq2...

This is only a preview of the solution. Please use the purchase button to see the entire solution

Assisting Tutor

Related Homework Solutions

5 Problems Involving Greedy Algorithms
Homework Solution
$50.00
Greedy
Algorithm
Analysis
Optimal
Program
Disk
Megabyte
Storage
Capacity
Decimalization
Denomination
Change-making
Half-crown
Florin
Shilling
Sixpence
Threepence
Pence
Coin
Solution
Selection
Sort
Framework
Decomposition
Egyptian
Get help from a qualified tutor
Live Chats