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 <typename T>
static bool defaultCompare(const T &key1, const T
&key2) {
return key1 <
key2;
}
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 <typename T>
static bool defaultCompare(const T &key1, const T &key2) {
return key1 < key2;
}
dlist.h:
#pragma once
#include <stdexcept>
#include "compare.h"
namespace cs20a
{
template <typename T> class dlist;
template <typename T> class dlist_iterator;
template <typename T> class const_dlist_iterator;
template <typename T> class reverse_dlist_iterator;
template <typename T> class const_reverse_dlist_iterator;
template <typename T>
class dlist_node {
friend class dlist<T>;
friend class dlist_iterator<T>;
friend class const_dlist_iterator<T>;
friend class reverse_dlist_iterator<T>;
friend class const_reverse_dlist_iterator<T>;
private:
dlist_node() {};
dlist_node(const T& t, dlist_node<T> *prev = nullptr, dlist_node<T> *next = nullptr)
: value(t), prev(prev), next(next) {};
T value;
dlist_node<T> *next, *prev;
};
template <typename T>
class dlist_iterator {
friend class dlist<T>;
public:
T& operator*() const { return np->value; };
bool operator == (const dlist_iterator<T>& li) const { return np == li.np; };
bool operator!=(const dlist_iterator<T>& li) const { return np != li.np; };
const dlist_iterator<T>& operator++() {
np = np->next;
return *this;
};
const dlist_iterator<T> operator++(int) {
dlist_iterator<T> clone(*this);
np = np->next;
return clone;
};
private:
dlist_node<T> *np;
dlist_iterator(dlist_node<T> *np) : np(np) {};
};
template <typename T>
class reverse_dlist_iterator {
friend class dlist<T>;
public:
T& operator*() const { return np->value; };
bool operator == (const reverse_dlist_iterator<T>& li) const { return np == li.np; };
bool operator!=(const reverse_dlist_iterator<T>& li) const { return np != li.np; };
const reverse_dlist_iterator<T>& operator++() {
np = np->prev;
return *this;
};
const reverse_dlist_iterator<T> operator++(int) {
reverse_dlist_iterator<T> clone(*this);
np = np->prev;
return clone;
};
private:
dlist_node<T> *np;
reverse_dlist_iterator(dlist_node<T> *np) : np(np) {};
};
template <typename T>
class const_dlist_iterator {
friend class dlist<T>;
public:
T const& operator*() const { return np->value; };
bool operator == (const const_dlist_iterator<T>& li) const { return np == li.np; };
bool operator!=(const const_dlist_iterator<T>& li) const { return np != li.np; };
const const_dlist_iterator<T>& operator++() {
np = np->next;
return *this;
};
const const_dlist_iterator<T> operator++(int) {
const_dlist_iterator<T> clone(*this);
np = np->next;
return clone;
};
private:
const dlist_node<T> *np;
const_dlist_iterator(const dlist_node<T> *ptr) : np(ptr) {};
};
template <typename T>
class const_reverse_dlist_iterator {
friend class dlist<T>;
public:
T const& operator*() const { return np->value; };
bool operator == (const const_reverse_dlist_iterator<T>& li) const { return np == li.np; };
bool operator!=(const const_reverse_dlist_iterator<T>& li) const { return np != li.np; };
const const_reverse_dlist_iterator<T>& operator++() {
np = np->prev;
return *this;
};
const const_reverse_dlist_iterator<T> operator++(int) {
const_reverse_dlist_iterator<T> clone(*this);
np = np->prev;
return clone;
};
private:
const dlist_node<T> *np;
const_reverse_dlist_iterator(const dlist_node<T> *ptr) : np(ptr) {};
};
template <typename T>
class dlist {
public:
typedef dlist_iterator<T> iterator;
typedef const_dlist_iterator<T> const_iterator;
typedef reverse_dlist_iterator<T> reverse_iterator;
typedef const_reverse_dlist_iterator<T> const_reverse_iterator;
public:
dlist();
dlist(const dlist<T> &rhs);
~dlist();
dlist<T>& operator =(const dlist<T> & rhs);
bool operator==(const dlist<T> &rhs) const;
bool operator!=(const dlist<T> &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<T>(head->next); }
iterator end() { return dlist_iterator<T>(nullptr); }
reverse_iterator rbegin() const { return reverse_dlist_iterator<T>(tail->prev); };
reverse_iterator rend() const { return reverse_dlist_iterator<T>(nullptr); };
const_iterator cbegin() const { return const_dlist_iterator<T>(head->next); };
const_iterator cend() const { return const_dlist_iterator<T>(nullptr); };
const_reverse_iterator crbegin() const { return const_reverse_dlist_iterator<T>(tail->prev); };
const_reverse_iterator crend() const { return const_reverse_dlist_iterator<T>(nullptr); };
iterator insert(iterator position, const T& element) {
dlist_node<T> * successor = position.np;
dlist_node<T> * target = new dlist_node<T>(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<T> * successor = position.np->next;
dlist_node<T> * target = position.np;
killNode(target);
return iterator(successor);
}
private:
dlist_node<T> header, tailer, *head, *tail;
long _size;
bool(*compare)(const T &, const T &);
void makeEmpty();
void init();
void copy(const dlist<T>& rhs);
void killNode(dlist_node<T> *target);
dlist_node<T> * findNode(const T& element) const;
};
template <typename T>
dlist<T>::dlist() {
init();
}
template <typename T>
dlist<T>::dlist(const dlist<T> &rhs) {
init();
copy(rhs);
}
template<typename T>
dlist<T>& dlist<T>::operator=(const dlist<T>& rhs) {
if (this != &rhs) {
clear();
copy(rhs);
}
return *this;
}
template <typename T>
dlist<T>::~dlist() {
makeEmpty();
}
template <typename T>
void dlist<T>::push_back(const T& element) {
dlist_node<T> *node = new dlist_node<T>(element, tail->prev, nullptr);
if (empty())
head->next = node;
else
tail->prev->next = node;
tail->prev = node;
_size++;
}
template<typename T>
T dlist<T>::pop_back() {
if (empty())
throw std::logic_error("Empty list.");
T element = tail->prev->value;
killNode(tail->prev);
return element;
}
template <typename T>
void dlist<T>::push_front(const T& element) {
dlist_node<T> *node = new dlist_node<T>(element, nullptr, head->next);
if (empty())
tail->prev = node;
else
head->next->prev = node;
head->next = node;
_size++;
}
template<typename T>
T dlist<T>::pop_front() {
if (empty())
throw std::logic_error("Empty list.");
T element = head->next->value;
killNode(head->next);
return element;
}
template<typename T>
T& dlist<T>::front() {
return head->next->value;
}
template<typename T>
const T & dlist<T>::front() const {
return head->next->value;
}
template<typename T>
T& dlist<T>::back() {
return tail->prev->value;
}
template<typename T>
const T & dlist<T>::back() const {
return tail->prev->value;
}
template<typename T>
bool dlist<T>::empty() const {
return head->next == nullptr;
}
template<typename T>
bool dlist<T>::full() const {
return false;
}
template<typename T>
void dlist<T>::clear() {
makeEmpty();
init();
}
template<typename T>
long dlist<T>::size() const {
return _size;
}
template<typename T>
bool dlist<T>::operator==(const dlist<T>& rhs) const {
if (this == &rhs)
return true;
if (size() != rhs.size())
return false;
dlist_node<T> *ptr1 = head->next;
dlist_node<T> *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<typename T>
bool dlist<T>::operator!=(const dlist<T>& rhs) const {
return !(*this == rhs);
}
template <typename T>
void dlist<T>::copy(const dlist<T>& rhs) {
dlist_node<T> *p = rhs.head->next;
while (p != nullptr) {
push_back(p->value);
p = p->next;
}
}
template<typename T>
dlist_node<T>* dlist<T>::findNode(const T & element) const {
dlist_node<T> *ptr = head->next;
while (ptr != nullptr && ptr->value != element)
ptr = ptr->next;
return ptr;
}
template<class T>
void dlist<T>::init() {
header.prev = header.next = nullptr;
tailer.prev = tailer.next = nullptr;
head = &header;
tail = &tailer;
_size = 0;
}
template<typename T>
void dlist<T>::killNode(dlist_node<T>* 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<typename T>
void dlist<T>::sort(bool(*comp)(const T &, const T &)) {
if (_size == 0)
return;
//*** Implement this function ***
}
template<class T>
void dlist<T>::makeEmpty() {
dlist_node<T> * ptr = head->next;
dlist_node<T> * target;
while (ptr != nullptr) {
target = ptr;
ptr = ptr->next;
delete target;
}
}
template<typename T>
void dlist<T>::remove(const T& element) {
dlist_node<T> *target = findNode(element);
if (target == nullptr)
throw std::logic_error("Node not found.");
killNode(target);
}
template<typename T>
bool dlist<T>::contains(const T & element) const {
dlist_node<T> * node = findNode(element);
return node != nullptr;
}
}
slist.h:
#pragma once
#include <stdexcept>
#include "compare.h"
namespace cs20a
{
template <typename T> class slist;
template <typename T> class slist_iterator;
template <typename T> class const_slist_iterator;
template <typename T> class slist_node;
template <typename T>
class slist_node {
friend class slist<T>;
friend class slist_iterator<T>;
friend class const_slist_iterator<T>;
private:
slist_node() {};
slist_node(const T& t, slist_node<T> *next = nullptr) : value(t), next(next) {};
T value;
slist_node<T> *next;
};
template <typename T>
class slist_iterator {
friend class slist<T>;
public:
T& operator*() const { return np->value; };
bool operator == (const slist_iterator<T>& li) const { return np == other.np; };
bool operator!=(const slist_iterator<T>& li) const { return np != li.np; };
const slist_iterator<T>& operator++() {
np = np->next;
return *this;
};
const slist_iterator<T> operator++(int) {
slist_iterator<T> clone(*this);
np = np->next;
return clone;
};
private:
slist_node<T> *np;
slist_iterator(slist_node<T> *np) : np(np) {};
};
template <typename T>
class const_slist_iterator {
friend class slist<T>;
public:
T const& operator*() const { return np->value; };
bool operator == (const const_slist_iterator<T>& li) const { return np == other.np; };
bool operator!=(const const_slist_iterator<T>& li) const { return np != li.np; };
const const_slist_iterator<T>& operator++() {
np = np->next;
return *this;
};
const const_slist_iterator<T> operator++(int) {
const_slist_iterator<T> clone(*this);
np = np->next;
return clone;
};
private:
const slist_node<T> *np;
const_slist_iterator(const slist_node<T> *ptr) : np(ptr) {};
};
template <typename T>
class slist {
public:
typedef slist_iterator<T> iterator;
typedef const_slist_iterator<T> const_iterator;
public:
slist();
slist(const slist<T> &rhs);
~slist();
slist<T>& operator =(const slist<T> & rhs);
bool operator==(const slist<T> & rhs) const;
bool operator!=(const slist<T> & 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<T>(head->next); }
iterator end() { return slist_iterator<T>(nullptr); }
const_iterator cbegin() const { return const_slist_iterator<T>(head->next); };
const_iterator cend() const { return const_slist_iterator<T>(nullptr); };
iterator insert(iterator position, const T& element) {
slist_node<T> * successor = position.np;
slist_node<T> * target = new slist_node<T>(element, successor);
if (head->next == successor)
head->next = target;
_size++;
return iterator(target);
}
iterator erase(iterator position) {
slist_node<T> * successor = position.np->next;
slist_node<T> * target = position.np;
killNode(target);
return iterator(successor);
}
private:
slist_node<T> header, *head, *tail;
long _size;
bool(*compare)(const T &, const T &);
void makeEmpty();
void init();
void copy(const slist<T>& rhs);
void killNode(slist_node<T> *target);
slist_node<T> * findNode(const T& element) const;
slist_node<T> * findNodePrevious(slist_node<T> * node) const;
};
template <typename T>
slist<T>::slist() {
init();
}
template <typename T>
slist<T>::slist(const slist<T> &rhs) {
init();
copy(rhs);
}
template<typename T>
slist<T> & slist<T>::operator=(const slist<T>& rhs) {
if (this != &rhs) {
clear();
copy(rhs);
}
return *this;
}
template <typename T>
slist<T>::~slist() {
makeEmpty();
}
template <typename T>
void slist<T>::push_back(const T& element) {
slist_node<T> * node = new slist_node<T>(element, nullptr);
if (empty())
head->next = node;
else
tail->next = node;
tail = node;
_size++;
}
template<typename T>
T slist<T>::pop_back() {
if (empty())
throw std::logic_error("Empty list.");
T element = tail->value;
killNode(tail);
return element;
}
template<typename T>
void slist<T>::push_front(const T & element) {
slist_node<T> * node = new slist_node<T>(element, head->next);
if (empty())
tail = node;
head->next = node;
_size++;
}
template<typename T>
T slist<T>::pop_front() {
if (empty())
throw std::logic_error("Empty list.");
T element = head->next->value;
killNode(head->next);
return element;
}
template<typename T>
T& slist<T>::front() {
return head->next->value;
}
template<typename T>
const T & slist<T>::front() const {
return head->next->value;
}
template<typename T>
T& slist<T>::back() {
return tail->value;
}
template<typename T>
const T & slist<T>::back() const {
return tail->value;
}
template<typename T>
bool slist<T>::empty() const {
return head->next == nullptr;
}
template<typename T>
bool slist<T>::full() const {
return false;
}
template<typename T>
void slist<T>::clear() {
makeEmpty();
init();
}
template<typename T>
long slist<T>::size() const {
return _size;
}
template<typename T>
bool slist<T>::operator==(const slist<T>& rhs) const {
if (this == &rhs)
return true;
if (size() != rhs.size())
return false;
slist_node<T> * p1 = head->next;
slist_node<T> * 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<typename T>
bool slist<T>::operator!=(const slist<T>& rhs) const {
return !(*this == rhs);
}
template <typename T>
void slist<T>::copy(const slist<T>& rhs) {
slist_node<T> * p = rhs.head->next;
while (p != nullptr) {
push_back(p->value);
p = p->next;
}
}
template<class T>
void slist<T>::init() {
header.next = nullptr;
head = tail = &header;
_size = 0;
}
template<typename T>
void slist<T>::killNode(slist_node<T>* target) {
slist_node<T> * previous = findNodePrevious(target);
previous->next = target->next;
if (tail == target)
tail = previous;
delete target;
_size--;
}
template<typename T>
void slist<T>::sort(bool(*comp)(const T &, const T &)) {
if (_size == 0)
return;
//*** Implement this function ***
}
template<class T>
void slist<T>::makeEmpty() {
slist_node<T> * ptr = head->next;
slist_node<T> * target;
while (ptr != nullptr) {
target = ptr;
ptr = ptr->next;
delete target;
}
}
template<typename T>
slist_node<T>* slist<T>::findNode(const T & element) const {
slist_node<T> * ptr = head->next;
while (ptr != nullptr && ptr->value != element)
ptr = ptr->next;
return ptr;
}
template<class T>
slist_node<T>* slist<T>::findNodePrevious(slist_node<T> * node) const {
slist_node<T> * ptr = head;
while (ptr->next != nullptr && ptr->next != node)
ptr = ptr->next;
return ((ptr->next != nullptr) ? ptr : nullptr);
}
template<typename T>
void slist<T>::remove(const T& element) {
slist_node<T> * target = findNode(element);
if (target == nullptr)
throw std::logic_error("Node not found.");
killNode(target);
}
template<typename T>
bool slist<T>::contains(const T & element) const {
slist_node<T> * node = findNode(element);
return node != nullptr;
}
}
ListMenu.cpp:
// Menu.cpp : Defines the entry point for the console application.
//
#define DOUBLE
#include <iostream>
#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<int>& l);
void printList(dlist<int>& 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<int> list;
#else
dlist<int> list;
#endif
int value = 0;
CHOICE choice;
do {
choice = menu();
switch (choice) {
case MAKEEMPTY:
list.clear();
break;
case ISEMPTY:
if (list.empty())
cout << "List is empty." << endl;
else
cout << "List is not empty." << endl;
break;
case SIZE:
cout << "List has " << list.size() << " elements. " << endl;
break;
case REMOVE:
cout << "Please provide int to remove: ";
cin >> value;
list.remove(value);
break;
case APPEND:
cout << "Please provide seed for random number generator: ";
cin >> value;
srand(value);
cout << "Please provide number of nodes: ";
cin >> value;
for (int i = 0; i < value; i++)
list.push_back(rand() % value);
break;
case CONTAINS:
cout << "Please provide int to find: ";
cin >> value;
if (list.contains(value))
cout << "List contains " << value << "." << endl;
else
cout << "List does not contain " << value << "." << endl;
break;
case PRINT:
printList(list);
break;
case SORTASCENDING:
list.sort(sortAscending);
break;
case SORTDESCENDING:
list.sort(sortDescending);
break;
case OTHER:
cout << "Not a valid choice." << endl;
}
} while (choice != QUIT);
return(0);
}
CHOICE menu() {
char choice;
CHOICE result;
cout << "(A)dd Nodes (R)emove (C)ontains (M)akeEmpty (S)ize (I)sEmpty (P)rint (1) Sort Asc (2) Sort Desc (Q)uit: " << endl;
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<int>& l) {
if (l.empty())
cout << "Empty list" << endl;
else {
for (slist<int>::iterator it = l.begin(); it != l.end(); it++) {
cout << *it << " -> ";
}
cout << "NULL" << endl;
}
}
void printList(dlist<int>& l) {
if (l.empty())
cout << "Empty list" << endl;
else {
for (dlist<int>::iterator it = l.begin(); it != l.end(); it++) {
cout << *it << " -> ";
}
cout << "NULL" << endl;
}
}
bool sortAscending(const int & val1, const int & val2) {
return val1 < val2;
}
bool sortDescending(const int & val1, const int & val2) {
return val1 > val2;
}
Homework Answers
Here are the modified files for the question. The progam did not compile because of error in slist.h - undeclared variable 'other' was being used. Fixed it. The sort functions in both slist.h and dlist.h implement selection sort algorithm.
Note: To test for single list, you need to change the line 4 in ListMenu.cpp to #define SINGLE
Please don't forget to rate the answer if it helped. Thank you very much.
slist.h
#pragma once
#include <stdexcept>
#include "compare.h"
namespace cs20a
{
template <typename T> class slist;
template <typename T> class slist_iterator;
template <typename T> class const_slist_iterator;
template <typename T> class slist_node;
template <typename T>
class slist_node {
friend class slist<T>;
friend class slist_iterator<T>;
friend class const_slist_iterator<T>;
private:
slist_node() {};
slist_node(const T& t, slist_node<T> *next = nullptr) :
value(t), next(next) {};
T value;
slist_node<T> *next;
};
template <typename T>
class slist_iterator {
friend class slist<T>;
public:
T& operator*() const { return np->value; };
bool operator == (const slist_iterator<T>& li) const {
return np == li.np; };
bool operator!=(const slist_iterator<T>& li) const {
return np != li.np; };
const slist_iterator<T>& operator++() {
np = np->next;
return *this;
};
const slist_iterator<T> operator++(int) {
slist_iterator<T> clone(*this);
np = np->next;
return clone;
};
private:
slist_node<T> *np;
slist_iterator(slist_node<T> *np) : np(np) {};
};
template <typename T>
class const_slist_iterator {
friend class slist<T>;
public:
T const& operator*() const { return np->value; };
bool operator == (const const_slist_iterator<T>& li)
const { return np == li.np; };
bool operator!=(const const_slist_iterator<T>& li) const
{ return np != li.np; };
const const_slist_iterator<T>& operator++() {
np = np->next;
return *this;
};
const const_slist_iterator<T> operator++(int) {
const_slist_iterator<T> clone(*this);
np = np->next;
return clone;
};
private:
const slist_node<T> *np;
const_slist_iterator(const slist_node<T> *ptr) : np(ptr)
{};
};
template <typename T>
class slist {
public:
typedef slist_iterator<T> iterator;
typedef const_slist_iterator<T> const_iterator;
public:
slist();
slist(const slist<T> &rhs);
~slist();
slist<T>& operator =(const slist<T> &
rhs);
bool operator==(const slist<T> & rhs) const;
bool operator!=(const slist<T> & 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<T>(head->next);
}
iterator end() { return slist_iterator<T>(nullptr); }
const_iterator cbegin() const { return
const_slist_iterator<T>(head->next); };
const_iterator cend() const { return
const_slist_iterator<T>(nullptr); };
iterator insert(iterator position, const T& element) {
slist_node<T> * successor = position.np;
slist_node<T> * target = new slist_node<T>(element,
successor);
if (head->next == successor)
head->next = target;
_size++;
return iterator(target);
}
iterator erase(iterator position) {
slist_node<T> * successor = position.np->next;
slist_node<T> * target = position.np;
killNode(target);
return iterator(successor);
}
private:
slist_node<T> header, *head, *tail;
long _size;
bool(*compare)(const T &, const T &);
void makeEmpty();
void init();
void copy(const slist<T>& rhs);
void killNode(slist_node<T> *target);
slist_node<T> * findNode(const T& element) const;
slist_node<T> * findNodePrevious(slist_node<T> * node)
const;
};
template <typename T>
slist<T>::slist() {
init();
}
template <typename T>
slist<T>::slist(const slist<T> &rhs) {
init();
copy(rhs);
}
template<typename T>
slist<T> & slist<T>::operator=(const
slist<T>& rhs) {
if (this != &rhs) {
clear();
copy(rhs);
}
return *this;
}
template <typename T>
slist<T>::~slist() {
makeEmpty();
}
template <typename T>
void slist<T>::push_back(const T& element) {
slist_node<T> * node = new slist_node<T>(element,
nullptr);
if (empty())
head->next = node;
else
tail->next = node;
tail = node;
_size++;
}
template<typename T>
T slist<T>::pop_back() {
if (empty())
throw std::logic_error("Empty list.");
T element = tail->value;
killNode(tail);
return element;
}
template<typename T>
void slist<T>::push_front(const T & element) {
slist_node<T> * node = new slist_node<T>(element,
head->next);
if (empty())
tail = node;
head->next = node;
_size++;
}
template<typename T>
T slist<T>::pop_front() {
if (empty())
throw std::logic_error("Empty list.");
T element = head->next->value;
killNode(head->next);
return element;
}
template<typename T>
T& slist<T>::front() {
return head->next->value;
}
template<typename T>
const T & slist<T>::front() const {
return head->next->value;
}
template<typename T>
T& slist<T>::back() {
return tail->value;
}
template<typename T>
const T & slist<T>::back() const {
return tail->value;
}
template<typename T>
bool slist<T>::empty() const {
return head->next == nullptr;
}
template<typename T>
bool slist<T>::full() const {
return false;
}
template<typename T>
void slist<T>::clear() {
makeEmpty();
init();
}
template<typename T>
long slist<T>::size() const {
return _size;
}
template<typename T>
bool slist<T>::operator==(const slist<T>& rhs)
const {
if (this == &rhs)
return true;
if (size() != rhs.size())
return false;
slist_node<T> * p1 = head->next;
slist_node<T> * 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<typename T>
bool slist<T>::operator!=(const slist<T>& rhs)
const {
return !(*this == rhs);
}
template <typename T>
void slist<T>::copy(const slist<T>& rhs) {
slist_node<T> * p = rhs.head->next;
while (p != nullptr) {
push_back(p->value);
p = p->next;
}
}
template<class T>
void slist<T>::init() {
header.next = nullptr;
head = tail = &header;
_size = 0;
}
template<typename T>
void slist<T>::killNode(slist_node<T>* target) {
slist_node<T> * previous = findNodePrevious(target);
previous->next = target->next;
if (tail == target)
tail = previous;
delete target;
_size--;
}
template<typename T>
void slist<T>::sort(bool(*comp)(const T &, const T
&)) {
slist_node<T> *toSwap;
if (_size <= 1) //no need to sort if there are zero OR just 1
item
return;
// selection sort algorithm
for(slist_node<T> *ptr1 = head->next; ptr1 != nullptr;
ptr1 = ptr1->next)
{
toSwap = ptr1;
for(slist_node<T> *ptr2 = ptr1->next; ptr2 != nullptr;
ptr2 = ptr2->next)
{
if(comp(ptr2->value, toSwap->value))
toSwap = ptr2;
}
if(ptr1 != toSwap)
{
T temp = ptr1->value;
ptr1->value = toSwap->value;
toSwap->value = temp;
}
}
}
template<class T>
void slist<T>::makeEmpty() {
slist_node<T> * ptr = head->next;
slist_node<T> * target;
while (ptr != nullptr) {
target = ptr;
ptr = ptr->next;
delete target;
}
}
template<typename T>
slist_node<T>* slist<T>::findNode(const T &
element) const {
slist_node<T> * ptr = head->next;
while (ptr != nullptr && ptr->value != element)
ptr = ptr->next;
return ptr;
}
template<class T>
slist_node<T>*
slist<T>::findNodePrevious(slist_node<T> * node) const
{
slist_node<T> * ptr = head;
while (ptr->next != nullptr && ptr->next !=
node)
ptr = ptr->next;
return ((ptr->next != nullptr) ? ptr : nullptr);
}
template<typename T>
void slist<T>::remove(const T& element) {
slist_node<T> * target = findNode(element);
if (target == nullptr)
throw std::logic_error("Node not found.");
killNode(target);
}
template<typename T>
bool slist<T>::contains(const T & element) const {
slist_node<T> * node = findNode(element);
return node != nullptr;
}
}
dlist.h
#pragma once
#include <stdexcept>
#include "compare.h"
namespace cs20a
{
template <typename T> class dlist;
template <typename T> class dlist_iterator;
template <typename T> class const_dlist_iterator;
template <typename T> class reverse_dlist_iterator;
template <typename T> class
const_reverse_dlist_iterator;
template <typename T>
class dlist_node {
friend class dlist<T>;
friend class dlist_iterator<T>;
friend class const_dlist_iterator<T>;
friend class reverse_dlist_iterator<T>;
friend class const_reverse_dlist_iterator<T>;
private:
dlist_node() {};
dlist_node(const T& t, dlist_node<T> *prev = nullptr,
dlist_node<T> *next = nullptr)
: value(t), prev(prev), next(next) {};
T value;
dlist_node<T> *next, *prev;
};
template <typename T>
class dlist_iterator {
friend class dlist<T>;
public:
T& operator*() const { return np->value; };
bool operator == (const dlist_iterator<T>& li) const {
return np == li.np; };
bool operator!=(const dlist_iterator<T>& li) const {
return np != li.np; };
const dlist_iterator<T>& operator++() {
np = np->next;
return *this;
};
const dlist_iterator<T> operator++(int) {
dlist_iterator<T> clone(*this);
np = np->next;
return clone;
};
private:
dlist_node<T> *np;
dlist_iterator(dlist_node<T> *np) : np(np) {};
};
template <typename T>
class reverse_dlist_iterator {
friend class dlist<T>;
public:
T& operator*() const { return np->value; };
bool operator == (const reverse_dlist_iterator<T>& li)
const { return np == li.np; };
bool operator!=(const reverse_dlist_iterator<T>& li)
const { return np != li.np; };
const reverse_dlist_iterator<T>& operator++() {
np = np->prev;
return *this;
};
const reverse_dlist_iterator<T> operator++(int) {
reverse_dlist_iterator<T> clone(*this);
np = np->prev;
return clone;
};
private:
dlist_node<T> *np;
reverse_dlist_iterator(dlist_node<T> *np) : np(np) {};
};
template <typename T>
class const_dlist_iterator {
friend class dlist<T>;
public:
T const& operator*() const { return np->value; };
bool operator == (const const_dlist_iterator<T>& li)
const { return np == li.np; };
bool operator!=(const const_dlist_iterator<T>& li) const
{ return np != li.np; };
const const_dlist_iterator<T>& operator++() {
np = np->next;
return *this;
};
const const_dlist_iterator<T> operator++(int) {
const_dlist_iterator<T> clone(*this);
np = np->next;
return clone;
};
private:
const dlist_node<T> *np;
const_dlist_iterator(const dlist_node<T> *ptr) : np(ptr)
{};
};
template <typename T>
class const_reverse_dlist_iterator {
friend class dlist<T>;
public:
T const& operator*() const { return np->value; };
bool operator == (const const_reverse_dlist_iterator<T>&
li) const { return np == li.np; };
bool operator!=(const const_reverse_dlist_iterator<T>&
li) const { return np != li.np; };
const const_reverse_dlist_iterator<T>& operator++()
{
np = np->prev;
return *this;
};
const const_reverse_dlist_iterator<T> operator++(int) {
const_reverse_dlist_iterator<T> clone(*this);
np = np->prev;
return clone;
};
private:
const dlist_node<T> *np;
const_reverse_dlist_iterator(const dlist_node<T> *ptr) :
np(ptr) {};
};
template <typename T>
class dlist {
public:
typedef dlist_iterator<T> iterator;
typedef const_dlist_iterator<T> const_iterator;
typedef reverse_dlist_iterator<T> reverse_iterator;
typedef const_reverse_dlist_iterator<T>
const_reverse_iterator;
public:
dlist();
dlist(const dlist<T> &rhs);
~dlist();
dlist<T>& operator =(const dlist<T> &
rhs);
bool operator==(const dlist<T> &rhs) const;
bool operator!=(const dlist<T> &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<T>(head->next);
}
iterator end() { return dlist_iterator<T>(nullptr); }
reverse_iterator rbegin() const { return
reverse_dlist_iterator<T>(tail->prev); };
reverse_iterator rend() const { return
reverse_dlist_iterator<T>(nullptr); };
const_iterator cbegin() const { return
const_dlist_iterator<T>(head->next); };
const_iterator cend() const { return
const_dlist_iterator<T>(nullptr); };
const_reverse_iterator crbegin() const { return
const_reverse_dlist_iterator<T>(tail->prev); };
const_reverse_iterator crend() const { return
const_reverse_dlist_iterator<T>(nullptr); };
iterator insert(iterator position, const T& element) {
dlist_node<T> * successor = position.np;
dlist_node<T> * target = new dlist_node<T>(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<T> * successor = position.np->next;
dlist_node<T> * target = position.np;
killNode(target);
return iterator(successor);
}
private:
dlist_node<T> header, tailer, *head, *tail;
long _size;
bool(*compare)(const T &, const T &);
void makeEmpty();
void init();
void copy(const dlist<T>& rhs);
void killNode(dlist_node<T> *target);
dlist_node<T> * findNode(const T& element) const;
};
template <typename T>
dlist<T>::dlist() {
init();
}
template <typename T>
dlist<T>::dlist(const dlist<T> &rhs) {
init();
copy(rhs);
}
template<typename T>
dlist<T>& dlist<T>::operator=(const
dlist<T>& rhs) {
if (this != &rhs) {
clear();
copy(rhs);
}
return *this;
}
template <typename T>
dlist<T>::~dlist() {
makeEmpty();
}
template <typename T>
void dlist<T>::push_back(const T& element) {
dlist_node<T> *node = new dlist_node<T>(element,
tail->prev, nullptr);
if (empty())
head->next = node;
else
tail->prev->next = node;
tail->prev = node;
_size++;
}
template<typename T>
T dlist<T>::pop_back() {
if (empty())
throw std::logic_error("Empty list.");
T element = tail->prev->value;
killNode(tail->prev);
return element;
}
template <typename T>
void dlist<T>::push_front(const T& element) {
dlist_node<T> *node = new dlist_node<T>(element,
nullptr, head->next);
if (empty())
tail->prev = node;
else
head->next->prev = node;
head->next = node;
_size++;
}
template<typename T>
T dlist<T>::pop_front() {
if (empty())
throw std::logic_error("Empty list.");
T element = head->next->value;
killNode(head->next);
return element;
}
template<typename T>
T& dlist<T>::front() {
return head->next->value;
}
template<typename T>
const T & dlist<T>::front() const {
return head->next->value;
}
template<typename T>
T& dlist<T>::back() {
return tail->prev->value;
}
template<typename T>
const T & dlist<T>::back() const {
return tail->prev->value;
}
template<typename T>
bool dlist<T>::empty() const {
return head->next == nullptr;
}
template<typename T>
bool dlist<T>::full() const {
return false;
}
template<typename T>
void dlist<T>::clear() {
makeEmpty();
init();
}
template<typename T>
long dlist<T>::size() const {
return _size;
}
template<typename T>
bool dlist<T>::operator==(const dlist<T>& rhs)
const {
if (this == &rhs)
return true;
if (size() != rhs.size())
return false;
dlist_node<T> *ptr1 = head->next;
dlist_node<T> *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<typename T>
bool dlist<T>::operator!=(const dlist<T>& rhs)
const {
return !(*this == rhs);
}
template <typename T>
void dlist<T>::copy(const dlist<T>& rhs) {
dlist_node<T> *p = rhs.head->next;
while (p != nullptr) {
push_back(p->value);
p = p->next;
}
}
template<typename T>
dlist_node<T>* dlist<T>::findNode(const T &
element) const {
dlist_node<T> *ptr = head->next;
while (ptr != nullptr && ptr->value != element)
ptr = ptr->next;
return ptr;
}
template<class T>
void dlist<T>::init() {
header.prev = header.next = nullptr;
tailer.prev = tailer.next = nullptr;
head = &header;
tail = &tailer;
_size = 0;
}
template<typename T>
void dlist<T>::killNode(dlist_node<T>* 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<typename T>
void dlist<T>::sort(bool(*comp)(const T &, const T
&)) {
dlist_node<T> *toSwap;
if (_size <= 1) //no need to sort if there are zero OR just 1
item
return;
// selection sort algorithm
for(dlist_node<T> *ptr1 = head->next; ptr1 != nullptr;
ptr1 = ptr1->next)
{
toSwap = ptr1;
for(dlist_node<T> *ptr2 = ptr1->next; ptr2 != nullptr;
ptr2 = ptr2->next)
{
if(comp(ptr2->value, toSwap->value))
toSwap = ptr2;
}
if(ptr1 != toSwap)
{
T temp = ptr1->value;
ptr1->value = toSwap->value;
toSwap->value = temp;
}
}
}
template<class T>
void dlist<T>::makeEmpty() {
dlist_node<T> * ptr = head->next;
dlist_node<T> * target;
while (ptr != nullptr) {
target = ptr;
ptr = ptr->next;
delete target;
}
}
template<typename T>
void dlist<T>::remove(const T& element) {
dlist_node<T> *target = findNode(element);
if (target == nullptr)
throw std::logic_error("Node not found.");
killNode(target);
}
template<typename T>
bool dlist<T>::contains(const T & element) const {
dlist_node<T> * node = findNode(element);
return node != nullptr;
}
}
output
(A)dd Nodes (R)emove (C)ontains (M)akeEmpty (S)ize (I)sEmpty
(P)rint (1) Sort Asc (2) Sort Desc (Q)uit:
A
Please provide seed for random number generator: 10
Please provide number of nodes: 10
(A)dd Nodes (R)emove (C)ontains (M)akeEmpty (S)ize (I)sEmpty
(P)rint (1) Sort Asc (2) Sort Desc (Q)uit:
p
0 -> 3 -> 1 -> 2 -> 5 -> 6 -> 0 -> 8 -> 8
-> 7 -> NULL
(A)dd Nodes (R)emove (C)ontains (M)akeEmpty (S)ize (I)sEmpty
(P)rint (1) Sort Asc (2) Sort Desc (Q)uit:
1
(A)dd Nodes (R)emove (C)ontains (M)akeEmpty (S)ize (I)sEmpty
(P)rint (1) Sort Asc (2) Sort Desc (Q)uit:
p
0 -> 0 -> 1 -> 2 -> 3 -> 5 -> 6 -> 7 -> 8
-> 8 -> NULL
(A)dd Nodes (R)emove (C)ontains (M)akeEmpty (S)ize (I)sEmpty
(P)rint (1) Sort Asc (2) Sort Desc (Q)uit:
2
(A)dd Nodes (R)emove (C)ontains (M)akeEmpty (S)ize (I)sEmpty
(P)rint (1) Sort Asc (2) Sort Desc (Q)uit:
p
8 -> 8 -> 7 -> 6 -> 5 -> 3 -> 2 -> 1 -> 0
-> 0 -> NULL
(A)dd Nodes (R)emove (C)ontains (M)akeEmpty (S)ize (I)sEmpty
(P)rint (1) Sort Asc (2) Sort Desc (Q)uit:
q
Add Answer to:
In this assignment, you will implement a sort method on
singly-linked and doubly-linked lists.
Implement the...
What is the specific answer for 1. and 2. Thanks! Add a new method, find, to...
What is the specific answer for 1. and 2. Thanks! Add a new method, find, to class SinglyLinkedList (defined here) that takes as input a “data” value and returns a pointer to a node. If the input data is present in the linked list, the returned pointer should point to that node; if not, the returned pointer is nullptr. Write the (single line) method declaration/specification. Write the method definition/implementation. Test by running the main() function below and capture the console...
I have the following c++ data structures assignment: Copy Constructors, Destructors, and Assignment Operators An understanding...
I have the following c++ data structures assignment: Copy Constructors, Destructors, and Assignment Operators An understanding of how to implement copy constructors, destructors, and assignment operators is essential when working with data structures using dynamic memory allocation. Failure to implement these methods correctly can and probably will result in memory leaks. In this project, you are provided with a working implementation of a doubly-linked list in which the copy constructor, destructor, and assignment operator methods are not complete. To complete...
(The SortedLinkedList class template) Complete the SortedLinkedList class template which is a doubly linked list and...
(The SortedLinkedList class template) Complete the SortedLinkedList class template which is a doubly linked list and is implemented with a header node and a tail node. // SortedLinkedList.h // SortedLinkedList.h // A collection of data are stored in the list by ascending order #ifndef SORTEDLIST_H #define SORTEDLIST_H using namespace std; template <typename T> class SortedList { private: // The basic single linked list node type. // Nested inside of SortedList. struct NodeType { T data; NodeType* next; NodeType* prev; NodeType(const...
The program I wrote has a few memory leaks. My assignment is to just fix the...
The program I wrote has a few memory leaks. My assignment is to
just fix the memory leaks. Here's the code:
bool RemoveTail()
{
if (tail == nullptr)
return false;
Node *ptr = tail;
if(tail->prev != nullptr)
{
tail = tail->prev;
tail->next = nullptr;
}
else
{
tail = nullptr;
head = nullptr;
}
delete ptr;
ptr = nullptr;
length--;
return true;
}
bool RemoveAt(const unsigned int index)
{
if(index >= length || index < 0)
return false;
unsigned int...
1. void raw_push_front(const Object &x) { // insert x at the head of the list *without*...
1. void raw_push_front(const Object &x) { // insert x at the head of the list *without* using the iterator classes // Place your code here. } 2. void raw_push_back(const Object &x) { // insert x at the tail of the list *without* using the iterator classes // Place your code here. } #ifndef LIST_H #define LIST_H #include <algorithm> using namespace std; template<typename Object> class List { private: // The basic doubly linked list node. // Nested inside of List, can...
Language: C++ Complete this function 1.Object &raw_front() { // Return the element at the front of...
Language: C++ Complete this function 1.Object &raw_front() { // Return the element at the front of the list *without* using the iterator classes // (You may assume the list is not empty) // Place your code here. Code: #ifndef LIST_H #define LIST_H #include using namespace std; template class List { private: // The basic doubly linked list node. // Nested inside of List, can be public // because the Node is itself private struct Node { Object data; Node *prev;...
Template Dequeue Class (C++ ) In this assignment, we will use a given test menu for the template ...
Template Dequeue Class (C++ )
In this assignment, we will use a given test menu for the
template Deque Class (a Linked List based Double Ended Queue,
Deque) that you have put together.
Starter
testDeque.cpp which contains:
Timer class holder (you need to go through the LearnCpp Ch15
and import it in)
Node class
Deque class specification (you need to fill out the
definition)
here is the testDeque.cpp code:
// C++ implementation of doubly linked list Deque doubly linked
list...
I need help with understanding dummy nodes in doubly-linked lists. Here is the code that I...
I need help with understanding dummy nodes in doubly-linked lists. Here is the code that I have right now. ************city.h**************** #ifndef city_h #define city_h #include <string> using namespace std; class City{ public: City () { name = "N/A"; population = 0; } City (string nm, unsigned int pop){ name = nm; population = pop; } void setName (string name) { this -> name = name; } void setPopulation (unsigned int population){ this -> population = population; } string getName() const...
Please show me how to overload the operators << and >> #ifndef LINK_LIST #define LINK_LIST #include...
Please show me how to overload the operators << and >> #ifndef LINK_LIST #define LINK_LIST #include <iostream> using namespace std; template <typename T> struct Int_Node { T value; Int_Node<T> *pre, *next; }; template <typename T> class Link_List { template <typename U> friend ostream &operator<<(ostream &, const Link_List<U> &);// print all integers in the list template <typename U> friend istream &operator>>(istream &, Link_List<U> &);// input a value at the back of the list, like insert_node(val);...
there show an error in sample.cpp file that more than one instance of overloaded function find...
there show an error in sample.cpp file that more than one instance of overloaded function find matches the argument list. can you please fix it. and rewrite the program and debug. thanks. I also wrote error below on which line in sample.cpp. it shows on find. #include #include #include "node1.cpp" using namespace main_savitch_5; // node1.h #ifndef MAIN_SAVITCH_NODE1_H #define MAIN_SAVITCH_NODE1_H #include <string> namespace main_savitch_5 { template<class item> class node { public: typedef item value_type; ...
The program I wrote has a few memory leaks. My assignment is to
just fix the memory leaks. Here's the code:
bool RemoveTail()
{
if (tail == nullptr)
return false;
Node *ptr = tail;
if(tail->prev != nullptr)
{
tail = tail->prev;
tail->next = nullptr;
}
else
{
tail = nullptr;
head = nullptr;
}
delete ptr;
ptr = nullptr;
length--;
return true;
}
bool RemoveAt(const unsigned int index)
{
if(index >= length || index < 0)
return false;
unsigned int...
Template Dequeue Class (C++ )
In this assignment, we will use a given test menu for the
template Deque Class (a Linked List based Double Ended Queue,
Deque) that you have put together.
Starter
testDeque.cpp which contains:
Timer class holder (you need to go through the LearnCpp Ch15
and import it in)
Node class
Deque class specification (you need to fill out the
definition)
here is the testDeque.cpp code:
// C++ implementation of doubly linked list Deque doubly linked
list...
Most questions answered within 3 hours.
-
An ANOVA comparing two groups is equivalent to an independent
samples t-test.
True
False
asked 2 minutes from now -
Amazon is not just a
surviving company of the 1990s tech boom; it is now one...
asked 47 seconds ago -
You are the CEO of a major corporation whose databases were
recently hacked, and sensitive customer...
asked 2 minutes ago -
Q1b. Provide an example of how pricing should interact
with the services offered by the retailer.
asked 29 minutes ago -
a mass weighing 8 pounds when attached to a spring, stretches
it 6 inches.the object is...
asked 36 minutes ago -
The following is part of the computer output from a regression
of monthly returns on Waterworks...
asked 40 minutes ago -
Bob Katz is purchasing a new Honda Pilot for $35,000. He is
financing $30,000 with a...
asked 44 minutes ago -
The equity holders of Super Nova, Inc. have 100 million of
equity in the firm. Because...
asked 43 minutes ago -
A sample of 240 observations is selected from a normal
population with a population standard deviation...
asked 59 minutes ago -
Write an (efficient) pseudocode for the implementation of each
of the following function prototypes (proper C...
asked 58 minutes ago -
Klingon Widgets, Inc., purchased new cloaking machinery three
years ago for $5.6 million. The machinery can...
asked 1 hour ago -
Social work's goal of social betterment implies
A. That social workers should be models of good...
asked 59 minutes ago