CSCI 362 — Lab 5b

PriorityQueue: a std::priority_queue class (but mostly just heap library functions)

Due: June 23, 2019 @ 11:59PM

Handout

Grab the handout tarfile from here: http://cs.millersville.edu/~wkillian/2019/summer/files/csci362/lab5b-priority-queue.tar

Overview

I've given you a mostly complete implementation of PriorityQueue. PriorityQueue is almost like std::priority_queue however, we do not handle certain forms of constructors or dealing with any underlying container. You are tasked with completing its implementation which relies heavily on HeapUtils.

The assignment is split into three files:

Like prior labs, it can be easy to get overwhelmed. But, if you work on one file at a time and complete the implementations of the functions in the specified order, you will make progress quickly!

  1. I recommend solving the pieces in the order I have them listed
  2. I am giving you a comprehensive unit test autograder as part of the handout

New C++ Features!

Priority Queues give the user an option of specifying a custom comparator. This is similar to what we could do in Java with Comparator<E>

The C++ standard library provides a few useful comparator function objects (or functors).

namespace std
{

template <typename T = void>
struct less
{
  bool
  operator() (T const& a, T const& b) const noexcept
  {
    return a < b;
  }
};

template <typename T = void>
struct greater
{
  bool
  operator() (T const& a, T const& b) const noexcept
  {
    return a > b;
  }
};

} // end namespace std

Okay, this is weird/confusing. What's going on here? We are creating a struct that overloads the function call operator()

This means we can say something like this:

int a = /* initialized */;
int b = /* initialized */;
std::less<int> less_than;

// equivalent to saying: bool result = a < b;
bool result = less_than (a, b);

In fact, another cool way of explaining how things like this can work:

a < b /* is equivalent to saying */ operator<(a, b)

Throughout the HeapUtils file, there is reference to a Comparator called comp.

Anytime you would say a < b WHEN COMPARING VALUES IN THE HEAP just say comp(a, b)

Operator Comparator
a < b comp (a, b)
a > b comp (b, a)
a <= b !comp (b, a)
a >= b !comp (a, b)

Required functions

NOTE: solve in the listed order

HeapUtils.hpp
namespace HeapUtils
{
namespace detail
{

/* [2] returns the parent's index
 *
 * p: the zero-based node index
 */
constexpr size_t
parent (size_t p) noexcept;

/* [2] returns the left child's index
 *
 * p: the zero-based node index
 */
constexpr size_t
left_child (size_t p) noexcept;

/* [2] returns the right child's index
 *
 * p: the zero-based node index
 */
constexpr size_t
right_child (size_t p) noexcept;

/* [2] returns the last interior node's index
 *
 * s: the size of the heap
 */
size_t
last_interior (size_t s) noexcept;

/* [4] returns the index of the maximum child of the node at index "pos"
 *
 * v: a vector representing a heap
 * pos: the zero-based index of a node
 * size: the logical size of the heap (may not be equal to v.size())
 * comp: a comparator function object
 */
template<typename T, typename Comp>
constexpr inline size_t
max_child (std::vector<T> const& v, size_t const pos, size_t const size, Comp& comp) noexcept;

/* [10] down-heaps a node at index "curr" into place
 *
 * v: a vector representing a heap
 * curr: the zero-based index of a node
 * size: logical size of heap (may not be equal to v.size())
 * comp: a comparator function object
 */
template<class T, class Comp>
void
sift_down (std::vector<T>& v, size_t curr, size_t size, Comp& comp) noexcept;

/* [10] up-heaps a node at index "curr" into place
 *
 * v: a vector representing a heap
 * curr: the zero-based index of a node
 * comp: a comparator function object
 */
template<class T, class Comp>
void
sift_up (std::vector<T>& v, size_t curr, Comp& comp) noexcept;

} // end namespace internal

/* [6] modifies v to become a heap. Starts at the last interior node and downHeaps
 * each node until the root has been downHeaped
 *
 * v: a vector representing a heap
 * comp: a comparator function object
 */
template<class T, class Comp>
void
make_heap (std::vector<T>& v, Comp& comp) noexcept;

/* [4] "inserts" a new element into the heap. The new element must reside
 * at index v.size() - 1. Essentially calls upHeap(v.size() - 1)
 *
 * Preconditions:
 * - v.size() > 0
 * - v.back() was just added to the vector and may not be in place
 *
 * Postconditions:
 * - v is a heap
 *
 * v: a vector representing a heap
 * comp: a comparator function object
 */
template<class T, class Comp>
void
push_heap (std::vector<T>& v, Comp& comp) noexcept;

/* [4] "removes" the max element in the heap (and places it at index
 * v.size() - 1). Essentially swaps front() with back() and then
 * performs downHeap from index zero
 *
 * Preconditions:
 * - v cannot be empty
 *
 * Postconditions:
 * - v is a heap under the bounds [0, v.size() - 1)
 *
 * v: a vector representing a heap
 * comp: a comparator function object
 */
template<class T, class Comp>
void
pop_heap (std::vector<T>& v, Comp& comp) noexcept;

/* [4] determines whether or not v is a heap (given the comparator)
 * returns true IFF v is a valid heap
 *
 * v: a vector
 * comp: a comparator object
 */
template<class T, class Comp>
bool
is_heap (std::vector<T> const& v, Comp& comp) noexcept;

} // end namespace HeapUtils

PriorityQueue.hpp

Note: this is not autograded

template<class T, class Comp = std::less<T>>
class PriorityQueue
{
public:

  // [2] construct a priority queue from a comparator and underlying container
  PriorityQueue (Comp const &comp, container_type const &c);

  // [2] construct a priority queue from a comparator and underlying (r-value) container
  explicit PriorityQueue (Comp const &comp, container_type &&c);

  // [2] return True IFF the heap is empty
  bool
  empty () const;

  // [2] return the size of the heap
  size_type
  size () const;

  // [2] return the top of the heap
  const_reference
  top () const;

  // [2] insert the new element "v" into the heap
  void
  push (value_type const &v);

  // [2] insert the new element "v" into the heap
  void
  push (value_type &&v);

  // [2] remove the top element from the heap
  void
  pop ();
};

Running the autograder

Invoking make should create the autograder.

There can be a lot of output shown from the autograder. Some of it could be overwhelming at times. I recommend adding a couple of arguments to the autograder to help ease the pain.

./autograder -a

Will run the autograder and stop as soon as the first FAILURE is found

./autograder -t

Will list all of the tags for each of the tests. If you want to run a specific subset of tags you can do so by stating the following:

./autograder [access],[iterator]

Will run all tests that have the access and iterator tags

./autograder --failed

Will list all failed tests at the end of the autograder output

./autograder --passed

Will list all passed tests at the end of the autograder output

Style

Use good programming style:

Submission

Since this consists of multiple files, a tarball will be required for submission.

invoking make handin should create handin.tar

Please submit handin.tar to autolab

Grading

This lab is graded out of 75 points.