In this assignment, you will implement a sort method on singly-linked and doubly-linked lists.

Implement the following sort member function on a singly-linked list:

void sort(bool(*comp)(const T &, const T &) = defaultCompare);

Implement the following sort member function on a doubly-linked list:

void sort(bool(*comp)(const T &, const T &) = defaultCompare);

The sort() methods take as a parameter a comparator function, having a default assignment of defaultCompare, a static function defined as follows:

template static bool defaultCompare(const T &key1, const T &key2) { return key1 }

defaultCompare is defined as a static function in the header file compare.h. Both sort algorithms must provide ascending and descending sorts by switching comparators.

You may use any sort algorithm you choose. If you implement the quick-sort algorithm (successfully!) for both lists, you may earn an extra 5 points.

The starter files are provided below. Do not alter the class definition in any way. Use the driver provided below. Programs that crash are subject to a 50% penalty. Please submit the class implementation files only (slist.h and dlist.h). PLEASE NOTE: You may not use any Standard Template Library (STL) classes for this assignment. Use code provided below only.

Please test and compile your code for errors before submitting code that contains bugs or that is not working. Thanks!

compare.h:

#pragma once

template

static bool defaultCompare(const T &key1, const T &key2) {

return key1

}

dlist.h:

#pragma once

#include

#include "compare.h"

namespace cs20a

{

template class dlist;

template class dlist_iterator;

template class const_dlist_iterator;

template class reverse_dlist_iterator;

template class const_reverse_dlist_iterator;

template

class dlist_node {

friend class dlist;

friend class dlist_iterator;

friend class const_dlist_iterator;

friend class reverse_dlist_iterator;

friend class const_reverse_dlist_iterator;

private:

dlist_node() {};

dlist_node(const T& t, dlist_node *prev = nullptr, dlist_node *next = nullptr)

: value(t), prev(prev), next(next) {};

T value;

dlist_node *next, *prev;

};

template

class dlist_iterator {

friend class dlist;

public:

T& operator*() const { return np->value; };

bool operator == (const dlist_iterator& li) const { return np == li.np; };

bool operator!=(const dlist_iterator& li) const { return np != li.np; };

const dlist_iterator& operator++() {

np = np->next;

return *this;

};

const dlist_iterator operator++(int) {

dlist_iterator clone(*this);

np = np->next;

return clone;

};

private:

dlist_node *np;

dlist_iterator(dlist_node *np) : np(np) {};

};

template

class reverse_dlist_iterator {

friend class dlist;

public:

T& operator*() const { return np->value; };

bool operator == (const reverse_dlist_iterator& li) const { return np == li.np; };

bool operator!=(const reverse_dlist_iterator& li) const { return np != li.np; };

const reverse_dlist_iterator& operator++() {

np = np->prev;

return *this;

};

const reverse_dlist_iterator operator++(int) {

reverse_dlist_iterator clone(*this);

np = np->prev;

return clone;

};

private:

dlist_node *np;

reverse_dlist_iterator(dlist_node *np) : np(np) {};

};

template

class const_dlist_iterator {

friend class dlist;

public:

T const& operator*() const { return np->value; };

bool operator == (const const_dlist_iterator& li) const { return np == li.np; };

bool operator!=(const const_dlist_iterator& li) const { return np != li.np; };

const const_dlist_iterator& operator++() {

np = np->next;

return *this;

};

const const_dlist_iterator operator++(int) {

const_dlist_iterator clone(*this);

np = np->next;

return clone;

};

private:

const dlist_node *np;

const_dlist_iterator(const dlist_node *ptr) : np(ptr) {};

};

template

class const_reverse_dlist_iterator {

friend class dlist;

public:

T const& operator*() const { return np->value; };

bool operator == (const const_reverse_dlist_iterator& li) const { return np == li.np; };

bool operator!=(const const_reverse_dlist_iterator& li) const { return np != li.np; };

const const_reverse_dlist_iterator& operator++() {

np = np->prev;

return *this;

};

const const_reverse_dlist_iterator operator++(int) {

const_reverse_dlist_iterator clone(*this);

np = np->prev;

return clone;

};

private:

const dlist_node *np;

const_reverse_dlist_iterator(const dlist_node *ptr) : np(ptr) {};

};

template

class dlist {

public:

typedef dlist_iterator iterator;

typedef const_dlist_iterator const_iterator;

typedef reverse_dlist_iterator reverse_iterator;

typedef const_reverse_dlist_iterator const_reverse_iterator;

public:

dlist();

dlist(const dlist &rhs);

~dlist();

dlist& operator =(const dlist & rhs);

bool operator==(const dlist &rhs) const;

bool operator!=(const dlist &rhs) const;

void push_back(const T& element);

T pop_back();

void push_front(const T& element);

T pop_front();

T& front();

const T& front() const;

T& back();

const T& back() const;

bool empty() const;

bool full() const;

void clear();

long size() const;

void remove(const T& element);

bool contains(const T& element) const;

void sort(bool(*comp)(const T &, const T &) = defaultCompare);

iterator begin() { return dlist_iterator(head->next); }

iterator end() { return dlist_iterator(nullptr); }

reverse_iterator rbegin() const { return reverse_dlist_iterator(tail->prev); };

reverse_iterator rend() const { return reverse_dlist_iterator(nullptr); };

const_iterator cbegin() const { return const_dlist_iterator(head->next); };

const_iterator cend() const { return const_dlist_iterator(nullptr); };

const_reverse_iterator crbegin() const { return const_reverse_dlist_iterator(tail->prev); };

const_reverse_iterator crend() const { return const_reverse_dlist_iterator(nullptr); };

iterator insert(iterator position, const T& element) {

dlist_node * successor = position.np;

dlist_node * target = new dlist_node(element, successor->prev, successor);

if (successor->prev != nullptr)

successor->prev->next = target;

successor->prev = target;

if (head->next == successor)

head->next = target;

_size++;

return iterator(target);

}

iterator erase(iterator position) {

dlist_node * successor = position.np->next;

dlist_node * target = position.np;

killNode(target);

return iterator(successor);

}

private:

dlist_node header, tailer, *head, *tail;

long _size;

bool(*compare)(const T &, const T &);

void makeEmpty();

void init();

void copy(const dlist& rhs);

void killNode(dlist_node *target);

dlist_node * findNode(const T& element) const;

};

template

dlist::dlist() {

init();

}

template

dlist::dlist(const dlist &rhs) {

init();

copy(rhs);

}

template

dlist& dlist::operator=(const dlist& rhs) {

if (this != &rhs) {

clear();

copy(rhs);

}

return *this;

}

template

dlist::~dlist() {

makeEmpty();

}

template

void dlist::push_back(const T& element) {

dlist_node *node = new dlist_node(element, tail->prev, nullptr);

if (empty())

head->next = node;

else

tail->prev->next = node;

tail->prev = node;

_size++;

}

template

T dlist::pop_back() {

if (empty())

throw std::logic_error("Empty list.");

T element = tail->prev->value;

killNode(tail->prev);

return element;

}

template

void dlist::push_front(const T& element) {

dlist_node *node = new dlist_node(element, nullptr, head->next);

if (empty())

tail->prev = node;

else

head->next->prev = node;

head->next = node;

_size++;

}

template

T dlist::pop_front() {

if (empty())

throw std::logic_error("Empty list.");

T element = head->next->value;

killNode(head->next);

return element;

}

template

T& dlist::front() {

return head->next->value;

}

template

const T & dlist::front() const {

return head->next->value;

}

template

T& dlist::back() {

return tail->prev->value;

}

template

const T & dlist::back() const {

return tail->prev->value;

}

template

bool dlist::empty() const {

return head->next == nullptr;

}

template

bool dlist::full() const {

return false;

}

template

void dlist::clear() {

makeEmpty();

init();

}

template

long dlist::size() const {

return _size;

}

template

bool dlist::operator==(const dlist& rhs) const {

if (this == &rhs)

return true;

if (size() != rhs.size())

return false;

dlist_node *ptr1 = head->next;

dlist_node *ptr2 = rhs.head->next;

while (ptr1 != nullptr || ptr2 != nullptr)

{

if (ptr1->value != ptr2->value)

return false;

ptr1 = ptr1->next;

ptr2 = ptr2->next;

}

return true;

}

template

bool dlist::operator!=(const dlist& rhs) const {

return !(*this == rhs);

}

template

void dlist::copy(const dlist& rhs) {

dlist_node *p = rhs.head->next;

while (p != nullptr) {

push_back(p->value);

p = p->next;

}

}

template

dlist_node* dlist::findNode(const T & element) const {

dlist_node *ptr = head->next;

while (ptr != nullptr && ptr->value != element)

ptr = ptr->next;

return ptr;

}

template

void dlist::init() {

header.prev = header.next = nullptr;

tailer.prev = tailer.next = nullptr;

head = &header;

tail = &tailer;

_size = 0;

}

template

void dlist::killNode(dlist_node* target) {

if (target->next != nullptr)

target->next->prev = target->prev;

if (target->prev != nullptr)

target->prev->next = target->next;

if (head->next == target)

head->next = target->next;

if (tail->prev == target)

tail->prev = target->prev;

delete target;

_size--;

}

template

void dlist::sort(bool(*comp)(const T &, const T &)) {

if (_size == 0)

return;

//*** Implement this function ***

}

template

void dlist::makeEmpty() {

dlist_node * ptr = head->next;

dlist_node * target;

while (ptr != nullptr) {

target = ptr;

ptr = ptr->next;

delete target;

}

}

template

void dlist::remove(const T& element) {

dlist_node *target = findNode(element);

if (target == nullptr)

throw std::logic_error("Node not found.");

killNode(target);

}

template

bool dlist::contains(const T & element) const {

dlist_node * node = findNode(element);

return node != nullptr;

}

}

slist.h:

#pragma once

#include

#include "compare.h"

namespace cs20a

{

template class slist;

template class slist_iterator;

template class const_slist_iterator;

template class slist_node;

template

class slist_node {

friend class slist;

friend class slist_iterator;

friend class const_slist_iterator;

private:

slist_node() {};

slist_node(const T& t, slist_node *next = nullptr) : value(t), next(next) {};

T value;

slist_node *next;

};

template

class slist_iterator {

friend class slist;

public:

T& operator*() const { return np->value; };

bool operator == (const slist_iterator& li) const { return np == other.np; };

bool operator!=(const slist_iterator& li) const { return np != li.np; };

const slist_iterator& operator++() {

np = np->next;

return *this;

};

const slist_iterator operator++(int) {

slist_iterator clone(*this);

np = np->next;

return clone;

};

private:

slist_node *np;

slist_iterator(slist_node *np) : np(np) {};

};

template

class const_slist_iterator {

friend class slist;

public:

T const& operator*() const { return np->value; };

bool operator == (const const_slist_iterator& li) const { return np == other.np; };

bool operator!=(const const_slist_iterator& li) const { return np != li.np; };

const const_slist_iterator& operator++() {

np = np->next;

return *this;

};

const const_slist_iterator operator++(int) {

const_slist_iterator clone(*this);

np = np->next;

return clone;

};

private:

const slist_node *np;

const_slist_iterator(const slist_node *ptr) : np(ptr) {};

};

template

class slist {

public:

typedef slist_iterator iterator;

typedef const_slist_iterator const_iterator;

public:

slist();

slist(const slist &rhs);

~slist();

slist& operator =(const slist & rhs);

bool operator==(const slist & rhs) const;

bool operator!=(const slist & rhs) const;

void push_back(const T& element);

T pop_back();

void push_front(const T& element);

T pop_front();

T& front();

const T& front() const;

T& back();

const T& back() const;

bool empty() const;

bool full() const;

void clear();

long size() const;

void remove(const T& element);

bool contains(const T& element) const;

void sort(bool(*comp)(const T &, const T &) = defaultCompare);

iterator begin() { return slist_iterator(head->next); }

iterator end() { return slist_iterator(nullptr); }

const_iterator cbegin() const { return const_slist_iterator(head->next); };

const_iterator cend() const { return const_slist_iterator(nullptr); };

iterator insert(iterator position, const T& element) {

slist_node * successor = position.np;

slist_node * target = new slist_node(element, successor);

if (head->next == successor)

head->next = target;

_size++;

return iterator(target);

}

iterator erase(iterator position) {

slist_node * successor = position.np->next;

slist_node * target = position.np;

killNode(target);

return iterator(successor);

}

private:

slist_node header, *head, *tail;

long _size;

bool(*compare)(const T &, const T &);

void makeEmpty();

void init();

void copy(const slist& rhs);

void killNode(slist_node *target);

slist_node * findNode(const T& element) const;

slist_node * findNodePrevious(slist_node * node) const;

};

template

slist::slist() {

init();

}

template

slist::slist(const slist &rhs) {

init();

copy(rhs);

}

template

slist & slist::operator=(const slist& rhs) {

if (this != &rhs) {

clear();

copy(rhs);

}

return *this;

}

template

slist::~slist() {

makeEmpty();

}

template

void slist::push_back(const T& element) {

slist_node * node = new slist_node(element, nullptr);

if (empty())

head->next = node;

else

tail->next = node;

tail = node;

_size++;

}

template

T slist::pop_back() {

if (empty())

throw std::logic_error("Empty list.");

T element = tail->value;

killNode(tail);

return element;

}

template

void slist::push_front(const T & element) {

slist_node * node = new slist_node(element, head->next);

if (empty())

tail = node;

head->next = node;

_size++;

}

template

T slist::pop_front() {

if (empty())

throw std::logic_error("Empty list.");

T element = head->next->value;

killNode(head->next);

return element;

}

template

T& slist::front() {

return head->next->value;

}

template

const T & slist::front() const {

return head->next->value;

}

template

T& slist::back() {

return tail->value;

}

template

const T & slist::back() const {

return tail->value;

}

template

bool slist::empty() const {

return head->next == nullptr;

}

template

bool slist::full() const {

return false;

}

template

void slist::clear() {

makeEmpty();

init();

}

template

long slist::size() const {

return _size;

}

template

bool slist::operator==(const slist& rhs) const {

if (this == &rhs)

return true;

if (size() != rhs.size())

return false;

slist_node * p1 = head->next;

slist_node * p2 = rhs.head->next;

while (p1 != nullptr || p2 != nullptr)

{

if (p1->value != p2->value)

return false;

p1 = p1->next;

p2 = p2->next;

}

return true;

}

template

bool slist::operator!=(const slist& rhs) const {

return !(*this == rhs);

}

template

void slist::copy(const slist& rhs) {

slist_node * p = rhs.head->next;

while (p != nullptr) {

push_back(p->value);

p = p->next;

}

}

template

void slist::init() {

header.next = nullptr;

head = tail = &header;

_size = 0;

}

template

void slist::killNode(slist_node* target) {

slist_node * previous = findNodePrevious(target);

previous->next = target->next;

if (tail == target)

tail = previous;

delete target;

_size--;

}

template

void slist::sort(bool(*comp)(const T &, const T &)) {

if (_size == 0)

return;

//*** Implement this function ***

}

template

void slist::makeEmpty() {

slist_node * ptr = head->next;

slist_node * target;

while (ptr != nullptr) {

target = ptr;

ptr = ptr->next;

delete target;

}

}

template

slist_node* slist::findNode(const T & element) const {

slist_node * ptr = head->next;

while (ptr != nullptr && ptr->value != element)

ptr = ptr->next;

return ptr;

}

template

slist_node* slist::findNodePrevious(slist_node * node) const {

slist_node * ptr = head;

while (ptr->next != nullptr && ptr->next != node)

ptr = ptr->next;

return ((ptr->next != nullptr) ? ptr : nullptr);

}

template

void slist::remove(const T& element) {

slist_node * target = findNode(element);

if (target == nullptr)

throw std::logic_error("Node not found.");

killNode(target);

}

template

bool slist::contains(const T & element) const {

slist_node * node = findNode(element);

return node != nullptr;

}

}

ListMenu.cpp:

// Menu.cpp : Defines the entry point for the console application.

//

#define DOUBLE

#include

#include "slist.h"

#include "dlist.h"

using namespace std;

using namespace cs20a;

enum CHOICE { APPEND, REMOVE, CONTAINS, SIZE, MAKEEMPTY, ISEMPTY, QUIT, PRINT, SORTASCENDING, SORTDESCENDING, OTHER };

CHOICE menu();

void printList(slist& l);

void printList(dlist& l);

bool sortAscending(const int &val1, const int &val2);

bool sortDescending(const int &val1, const int &val2);

int main(int argc, char* argv[]) {

#ifdef SINGLE

slist list;

#else

dlist list;

#endif

int value = 0;

CHOICE choice;

do {

choice = menu();

switch (choice) {

case MAKEEMPTY:

list.clear();

break;

case ISEMPTY:

if (list.empty())

cout

else

cout

break;

case SIZE:

cout

break;

case REMOVE:

cout

cin >> value;

list.remove(value);

break;

case APPEND:

cout

cin >> value;

srand(value);

cout

cin >> value;

for (int i = 0; i

list.push_back(rand() % value);

break;

case CONTAINS:

cout

cin >> value;

if (list.contains(value))

cout

else

cout

break;

case PRINT:

printList(list);

break;

case SORTASCENDING:

list.sort(sortAscending);

break;

case SORTDESCENDING:

list.sort(sortDescending);

break;

case OTHER:

cout

}

} while (choice != QUIT);

return(0);

}

CHOICE menu() {

char choice;

CHOICE result;

cout

cin >> choice;

switch (choice) {

case 'M':

case 'm':

result = MAKEEMPTY;

break;

case 'I':

case 'i':

result = ISEMPTY;

break;

case 'A':

case 'a':

result = APPEND;

break;

case 'R':

case 'r':

result = REMOVE;

break;

case 'C':

case 'c':

result = CONTAINS;

break;

case 'S':

case 's':

result = SIZE;

break;

case 'P':

case 'p':

result = PRINT;

break;

case 'Q':

case 'q':

result = QUIT;

break;

case '1':

result = SORTASCENDING;

break;

case '2':

result = SORTDESCENDING;

break;

default:

result = OTHER;

break;

}

return(result);

}

void printList(slist& l) {

if (l.empty())

cout

else {

for (slist::iterator it = l.begin(); it != l.end(); it++) {

cout ";

}

cout

}

}

void printList(dlist& l) {

if (l.empty())

cout

else {

for (dlist::iterator it = l.begin(); it != l.end(); it++) {

cout ";

}

cout

}

}

bool sortAscending(const int & val1, const int & val2) {

return val1

}

bool sortDescending(const int & val1, const int & val2) {

return val1 > val2;

}

slist sll srand (837) for (int i 0; i K 100 1++ sll push back (rand()); sll. Sort sll sort descendingCompare) default: ascending sort descending Compare static compare function