Class definitions needed for Linked List-type class: My class RMQlist needs implementations in some functions of the class RMQlist. Please see all functions from the table that need to be implemented in RMQlist.h. Apart from those class implementations you can declare some private helper functions if you need in class RMQlist and please do not modify the Node class.

For your understanding I've also given the table where in they say how each function needs to be implemented. And then see the attached rmqlist.h file and do your implementation of those functions based on what description they have given in the table only, no other implementation of those functions is allowed because I am already given Test.cpp file where in I am going to test those functions and if it runs then I'm going to graded based on that file. Please make sure to run and test your rmqlist.h file before giving the answer to make sure there are zero errors in the rmqlist.h file.

Table showing required implementations to do:

Method	Description
RMQList()	Constructor. Creates an empty RMQList object.
~RMQList()	Destructor
RMQList(const RMQList &rhs)	Copy Constructor
const RMQList& operator=(const RMQList &rhs)	Assignment Operator
int size() const	Returns the number of elements in the list. This function is already implemented.
bool empty() const	Returns true if the list is empty, false otherwise.
bool insert(const K& key, const V& value)	Inserts an element into the list. The list must be kept in increasing order by key, and duplicate keys are not allowed. The function returns false if there is already an entry with the given key value and returns true otherwise. If the specified key is larger than all keys in the list, then the function should append the new data to the end of the list, avoiding unecessary iteration.
bool remove(const K& key)	Remove the element with specified key value from the list. Returns false if there is no element with the specified key; returns true otherwise.
bool update(const K& key, const V& value)	Update the value for the element with the given key value. Returns false if there is no element with the given key; returns true otherwise.
V query(const K& k1, const K& k2)	Returns the minimum value between k1 and k2 in the list data (including the values associated with k1 and k2). Must be implemented using Dynamic Programming or Block Decomposition, and queries must be efficient for large lists (tens of thousands of entries). Throws an exception if the list is empty or if an invalid key is passed (see Requirements, below).
void dumpList() const	Dump the contents of the linked list.
void dumpTable() const	Dump the entire RMQ tables. This will depend on which RMQ method you choose to implement. For the dynamic programming approach, the function should print the number of blocks, the block size, and the block averages. For dyanmic programming, the function should print the entire array of pre-computed minimums.
void clear()	Reset the RMQList object to its initial, empty state.

RMQlist.h file:

#ifndef _RMQLIST_H #define _RMQLIST_H

#include #include #include

using std::swap; using std::ostream; using std::cout; using std::endl; using std::sqrt; using std::range_error; using std::invalid_argument;

// Macro for a two-argument min function #define MIN(a, b) ((a) < (b) ? (a) : (b))

// forward declarations template class RMQList; template class Node; template ostream& operator<<(ostream &sout, const Node &x); // Node - node class for the RMQList linked list // key and value are templated (types K and V)

template class Node { friend RMQList; public: Node(K key = K(), V value = V(), Node *next = nullptr) { _key = key; _value = value; _next = next; } friend ostream& operator<< (ostream &sout, const Node &x); private: K _key; V _value; Node *_next; };

// Overloaded insertion operator for Node template ostream& operator<<(ostream &sout, const Node &x) { sout << "Key: " << x._key << ", Value: " << x._value; return sout; } // RMQList - list container (linked list) with RMQ support // key and value are templated (types K and V)

template class RMQList { public: // Create an empty RMQList object RMQList(); // Destructor, Copy Constructor, Assignment Operator ~RMQList(); RMQList(const RMQList &rhs); const RMQList& operator=(const RMQList &rhs); // In-line function. Returns the size (number of elements). int size() const { return _listSize; }

// In-line function. Returns true if the list is empty; false // otherwise. bool empty() const { return _head == nullptr; } // Insert an element into the list; list must be kept in increasing // order by key; duplicate keys are not allowed, so return false if // there is already an entry with the specified key, true otherwise. // Should check if key > largest current key and, if so, append to // the end of the list without iteration. bool insert(const K& key, const V& value);

// Remove an element from the list; return false if no element // exists with the specified key value, true otherwise bool remove(const K& key);

// Update value for the element with given key; return false if // there is no element with the given key, true otherwise bool update(const K& key, const V& value); // RMQ Query for k1 to k2. Throws exceptions (see documentation). V query(const K& k1, const K& k2);

// Dump the list entries void dumpList() const; // Dump the RMQ info and table. What gets dumped depends on which // RMQ method is used. void dumpTable() const;

// Clear the data data strucures void clear(); private: Node *_head; Node *_tail; int _listSize;

// Private variables for RMQ go here! // ********************************** // Declarations for additional private functions go here! };

// ** Implement all of the below functions from the their given description in the Table**

// ********************************** template RMQList::RMQList() { }

template RMQList::~RMQList() { }

template RMQList::RMQList(const RMQList &rhs) { }

template const RMQList& RMQList::operator=(const RMQList &rhs) { }

template bool RMQList::insert(const K& key, const V& value) { }

template bool RMQList::remove(const K& key) { }

template bool RMQList::update(const K& key, const V& value) { }

template V RMQList::query(const K& k1, const K& k2) { }

template void RMQList::dumpList() const { }

template void RMQList::dumpTable() const { }

template void RMQList::clear() { }

#endif