need to do the Compare_with function in this linked list #ifndef LIST_H #define
ID: 3751157 • Letter: N
Question
need to do the Compare_with function in this linked list
#ifndef LIST_H
#define LIST_H
#include <algorithm>
#include <iostream>
/**
* class List<T>
*
* General description: class for storing and manipulating sequences of items
* where item type is specified via template.
*
* Underlying organization: the implementation uses a singly-linked list data structure
* with pointers to both the front (first node) and back (last node) of the list.
*
* A private struct Node is used to represent individual nodes in a list.
*/
template <typename T>
class List
{
private:
struct Node
{
T data;
Node *next;
Node(const T &d = T{}, Node *n = nullptr)
: data{d}, next{n} {}
};
/* Data members of List class: a front and back pointer */
Node *front;
Node *back;
int list_size;
public:
// constructor
List() {
front = nullptr;
back = nullptr;
list_size = 0;
}
// destructor
~List() {
clear();
}
/**
* Disclaimer: C++ conventions tell us that we should have a couple
* of additional constructors here (a copy constructor, assignment operator
* etc.)
*
* However, to keep things simple for now we will ignore that convention
* (since the exposure to C++ is pretty variable it seems -- some students
* having taken 141 before last semester; some students coming from 107,
* etc.)
*/
/**
* function: clear
* desc: makes the calling list empty (but the list still
* exists).
*/
void clear()
{
Node *p = front;
Node *pnext;
while (p != nullptr)
{
pnext = p->next;
delete p;
p = pnext;
}
front = back = nullptr;
}
int length() const
{
return list_size;
}
public:
/**
* function: is_empty
* desc: Returntrue if the list is empty, false otherwise.
*/
bool is_empty() const
{
return front == nullptr;
}
/**
* function: print
* desc: self-evident: simply prints the elements/values of the list in order.
*/
void print() const
{
Node *p = front;
std::cout << "[ ";
while (p != nullptr)
{
std::cout << p->data << " ";
p = p->next;
}
std::cout << "] ";
}
/**
* function: push_front
* desc: adds a new element to the front of the list (calling object) containing val.
* Equivalently, you can think of this as an "prepend" operation.
*/
void push_front(const T &data)
{
front = new Node(data, front);
if (back == nullptr)
back = front;
list_size++;
}
/**
* function: pop_front
* desc: if the list (calling object) is non-empty, the first element (front of list)
* is removed and the value it stored is 'passed back' to the caller via the reference
* parameter val. In this case (non-empty list), true is returned for success.
*
* Otherwise (the list is empty), false is returned and the reference parameter val has
* no meaning.
*/
bool pop_front(T &val)
{
Node *tmp;
if (front == nullptr)
return false;
val = front->data;
tmp = front;
front = front->next;
delete tmp;
if (front == nullptr)
back = nullptr;
list_size++;
return true;
}
/**
* function: push_back
* desc: adds a new element to the end of the list (calling object) containing val.
* Equivalently, you can think of this as an "append" operation.
*/
void push_back(const T &val)
{
Node *tmp = new Node(val, nullptr);
if (front == nullptr)
{
front = back = tmp;
}
else
{
back->next = tmp;
back = tmp;
list_size--;
}
}
/**
* function: remove_first
* desc: removes first ocflience of x (if any) in given list (calling object).
* if a match is found (and removed), true is returned.
* Otherwise (no match found), false is returned and the list is unchanged.
*/
bool remove_first(const T &x)
{
Node *p, *tmp;
T dummy;
if (front == nullptr)
return false;
if (front->data == x)
{
pop_front(dummy);
return true;
}
p = front;
while (p->next != nullptr)
{
if (x == p->next->data)
{
tmp = p->next;
p->next = tmp->next;
if (tmp == back)
back = p;
delete tmp;
return true;
}
p = p->next;
}
return false;
}
/**
* function: slow_remove_all
* desc: removes all occurrences of x (if any) in given list (calling object).
* returns number of matches found/deleted. Relative order of undeleted elements
* is unchanged.
*
* approach: repeatedly calls remove_first until it fails.
*
* Note: function is designated with the slow_ prefix because, in the worst case, it can
* take quadratic time.
*/
int slow_remove_all(const T &x)
{
int n = 0;
while (remove_first(x))
n++;
return n;
list_size--;
}
/**
* function: is_sorted
* desc: returns true if elements in list are in sorted order from
* smallest to largest (duplicates allowed); returns false otherwise.
*
* Note: requires that type T has the > operator defined on it (perhaps via
* operator overloading as in the case of the string class)
*/
bool is_sorted() const
{
Node *p = front;
while (p != nullptr && p->next != nullptr)
{
if (p->data > p->next->data)
return false;
p = p->next;
}
return true;
}
int count(const T &x) const
{
int frequency = 0;
if (this->is_empty())
return frequency;
Node* temp1 = front;
while (temp1 != nullptr) {
if (temp1->data == x)
frequency++;
temp1 = temp1->next;
}
return frequency;
}
bool pop_back(T &data)
{
if(front == nullptr)
return false;
else{
Node *temp1 = front;
while(temp1->next->next != nullptr) {
temp1 = temp1->next;
}
this->back = temp1;
temp1=temp1->next ;
data = temp1-> data;
delete (temp1);
return true;
}
/**
* TODO
*
* function: compare_with
* description: compares the calling list with parameter list (other)
* "LEXICALLY" (essentially a generalization of dictionary
* ordering).
*
* link: https://en.wikipedia.org/wiki/Lexicographical_order
*
* Return Value:
*
* o if the two lists are identical, 0 is returned.
* o if the calling list is lexically BEFORE the other list,
* -1 is returned
* o otherwise, the other list is lexically before the calling
* list and 1 (positive one) is returned.
*
* Properties and examples:
*
* The empty list is lexically before all non-empty lists
* (you can say it is "less than" all non-empty lists).
*
* Examples (using mathematical notation):
*
* [2 5 1] < [3 1 1 1 1] (think dictionary ordering!)
*
* [4 1 3] < [4 1 3 0 0 0] (prefix: just like "car" is before
* "cartoon" in the dictionary).
*
* [4 5 6 1 2 3 9 9 9] < [4 5 6 1 4 0 0]
* ^ ^
* (they have a common prefix of length 4; but at
* the fifth position they differ and the left list
* is the winner (smaller) -- no need to look further)
*
*
* Templates?
*
* Since List is a template class, the elements of a particular
* list need not be integers. For example, we could have
* lists of strings.
*
* Good news: the exact same principle applies because
* strings can be compared just like integers can be compared!
*
* Great news: you don't need to think about this at all!
* The exact same code you would write if you assumed the element
* type is integer will work for other types like strings.
*
* Why? Because, for example, all of these operators:
*
* <, <=, ==, > and >=
*
* all work on strings. They are not 'built-in' to C++, but
* the class string has "overloaded" these operators (they
* result in an appropriate function call).
*
* (In a subsequent exercise, we will do this kind of
* overloading ourselves!)
*
* Examples with lists of strings:
*
* ["egg", "goat"] < ["egg", "globe", "apple"]
*
* ["zebra", "fun"] < ["zebra", "funny"]
*
* [Yes, the components of these lists are THEMSELVES compared
* lexically, but the string class is doing those comparisons)
*
*/
int compare_with(const List<T> &other) const
{
return 0;
}
Explanation / Answer
Please let me know if you have any doubts or you want me to modify the code. And if you find this code useful then don't forget to rate my answer as thumps up. Thank you! :)
//main.cpp
#include "List.h"
#include <stdlib.h>
#include <iostream>
#include <string>
using namespace std;
List<int> * slow_list(int n) {
// placeholder
return nullptr;
}
int main(int argc, char *argv[]){
List<int> *list = new List<int>();
List<string> *list2 = new List<string>();
List<string> *list3 = new List<string>();
List<int> *list4 = new List<int>();
int x;
int n, ndel;
n = 1000;
if(argc == 2) {
n = atoi(argv[1]);
}
// TEST: length() function by calling print which calls length() and length() returns number of elements in list
cout << "*** TEST LENGTH() FUNCTION: ***" << endl;
for(x=1; x<=4; x++) {
list->push_front(x);
list4->push_front(x);
}
list->print();
for(x=1; x<=4; x++) {
list->push_back(x);
}
list->print();
cout << endl;
// TEST: count() function after duplicates have been put into list
cout << "*** TEST COUNT() FUNCTION: ***" << endl
<< "How many 4's are in list (should be 2): " << list->count(4) << endl
<< "How many 10's are in list (should be 0): " << list->count(10) << endl << endl;
// TEST: equal_to() function
cout << "*** TEST EQUAL_TO() FUNCTION: ***" << endl
<< "Are these lists equal (NO): " << list->equal_to(*list4) << endl;
// Make them equal now
for(x=1; x<=4; x++) {
list4->push_back(x);
}
cout << "Are these lists equal (YES): " << list->equal_to(*list4) << endl << endl;
// TEST: pop_back() function
cout << "*** TEST POP_BACK() FUNCTION: ***" << endl
<< "Before list (more than 1 node): ";
list->print();
int testVal= 0;
cout << "Was pop back successful? (should be yes): " << list->pop_back(testVal) << "; and popped off (should be 4): ";
cout << testVal << endl;
list->print();
cout << endl;
// Make list one node long
int listLength = list->length();
for (x = 0; x < listLength - 1; x++) {
list->pop_back(testVal);
}
cout << "Before list (1 node): ";
list->print();
cout << "Was pop back successful? (should be yes): " << list->pop_back(testVal) << "; and popped off (should be 4): ";
cout << testVal << endl;
list->print();
cout << endl;
// Make list empty
cout << "Before list (empty): ";
list->print();
cout << "Was pop back successful? (should be no): " << list->pop_back(testVal) << endl << endl;
// TEST: print_rev() function
cout << "*** TEST PRINT_REV() FUNCTION: ***" << endl;
// Put values in list again [1,10]
for(x = 1; x <= 10; x++) {
list->push_front(x);
}
cout << "Before list (10 elements): ";
list->print();
cout << "List reveresed by calling print_rev which prints out elements in reverse order: ";
list->print_rev();
// Make list have 1 element
cout << endl;
listLength = list->length();
for (x = 0; x < listLength - 1; x++) {
list->pop_back(testVal);
}
cout << "Before list (1 element): ";
list->print();
cout << "Call to print_rev: " << endl;
list->print_rev();
// Make list empty
cout << endl;
list->pop_back(testVal);
cout << "Before list (0 elements): ";
list->print();
cout << "Call to print_rev: " << endl;
list->print_rev();
cout << endl;
// TEST: insert_sorted() function
cout << "*** TEST INSERT_SORTED() FUNCTION: ***" << endl;
// Create list of ordered numbers
list->push_front(7); list->push_front(6); list->push_front(4); list->push_front(3); list->push_front(2);
cout << "List before: ";
list->print();
cout << endl;
// Insert in the middle
cout << "Insert in middle (5): ";
list->insert_sorted(5);
list->print();
cout << endl;
// Insert in beginning
cout << "Insert in beginning (1): ";
list->insert_sorted(1);
list->print();
cout << endl;
// Insert at end
cout << "Insert at end (10): ";
list->insert_sorted(10);
list->print();
cout << endl;
// Insert a duplicate integer
cout << "Insert duplicate integers (1): ";
list->insert_sorted(1);
list->print();
cout << "Insert duplicate integers (5): ";
list->insert_sorted(5);
list->print();
cout << "Insert duplicate integers (10): ";
list->insert_sorted(10);
list->print();
cout << endl;
// Create list of one number, try inserting a smaller integer
listLength = list->length();
for (x = 0; x < listLength - 1; x++) {
list->pop_back(testVal);
}
cout << "Before list (1 element): ";
list->print();
cout << endl;
cout << "Insert a smaller integer (0): ";
list->insert_sorted(0);
list->print();
cout << endl;
list->pop_front(testVal); // Make list one element long again
cout << "Before list (1 element): ";
list->print();
cout << endl;
cout << "Insert a larger integer (9): ";
list->insert_sorted(9);
list->print();
cout << endl;
// Create an empty list and insert
list->pop_back(testVal);
list->pop_back(testVal);
list->print();
cout << "Insert an integer on empty list: ";
list->insert_sorted(25);
list->print();
cout << endl;
// TEST: concat() function
cout << "*** TEST CONCAT() FUNCTION: ***" << endl;
list->push_front(3);
list->push_front(17);
list->print();
list4->print();
// trying to concat the same list
cout << endl << "Trying to concat same lists..." << endl;
list->concat(*list);
cout << endl;
// make two lists with elements and combine them
list->concat(*list4);
list->print();
list4->print();
cout << endl;
// test if concat with empty list, both ways
cout << "Concat list with empty list: " << endl;
list->concat(*list4);
list->print();
list4->print();
cout << endl;
// TEST: clone() function
cout << "*** TEST CLONE() FUNCTION: ***" << endl;
cout << "Current list (ints): ";
list->print();
List<int> *recieveClonedListI;
recieveClonedListI = list->clone();
cout << "Cloned list (ints): ";
recieveClonedListI->print();
cout << endl;
// Put string elements in list and make copy using same clone function
string words[] = {"alice", "bob", "cathy", "donald"};
for (int i = 0; i < 4; i++) {
list2->push_front(words[i]);
}
cout << "Current list (strings): ";
list2->print();
List<string> *recieveClonedListS;
recieveClonedListS = list2->clone();
cout << "Cloned list (strings): ";
recieveClonedListS->print();
cout << endl;
// TEST: reverse() function
cout << "*** TEST REVERSE() FUNCTION: ***" << endl;
cout << "Current list: ";
list->print();
list->reverse();
cout << "List reversed: ";
list->print();
cout << endl;
// TEST: merge_with() function
cout << "*** TEST MERGE_WITH() FUNCTION: ***" << endl;
// Clear lists
listLength = list->length();
for (x = 0; x < listLength; x++) {
list->pop_back(testVal);
}
listLength = list4->length();
for (x = 0; x < listLength; x++) {
list4->pop_back(testVal);
}
// Populate lists with ordered values
list->push_back(5); list->push_back(7); list->push_back(7);list->push_back(10);list->push_back(12);
list4->push_back(0); list4->push_back(1); list4->push_back(6);list4->push_back(11);list4->push_back(20);
// Test merge_with() function
cout << "Current lists: ";
list->print();
list4->print();
cout << "Merge the lists!";
list->merge_with(*list4);
list->print();
list4->print();
cout << "Push back 99" << endl;
list->push_back(99);
list->print();
cout << endl;
cout << endl;
list->clear();
list4->clear();
list4->push_back(5); list4->push_back(7); list4->push_back(7);list4->push_back(10);list4->push_back(12);
cout << "THE TEST................" << endl;
cout << "Current lists...empty calling with filled parameter [5 7 7 10 12]: " << endl;
cout << "calling list: " << endl;
list->print();
cout << "parameter list: " << endl;
list4->print();
list->merge_with(*list4);
cout << "after: " << endl;
list->print();
list4->print();
// TEST: prefix() function
cout << "*** TEST PREFIX() FUNCTION: ***" << endl
<< "Current list (ints): ";
list->print();
// Declare list of ints
cout << "Call to prefix with k = 4: " << endl;
List<int> * preI = list->prefix(4);
list->print();
preI->print();
cout << endl;
cout << "Call to prefix with k = 6 (all the elements): " << endl;
list->print();
List<int> * replace = list->prefix(6);
cout << "After call..." << endl;
list->print();
replace->print();
cout << endl;
cout << "Call to prefix with k = 0 (should return empty list)" << endl;
preI->print();
List<int> * empty = preI->prefix(0);
cout << "After call..." << endl;
preI->print();
empty->print();
cout << endl;
// Declare list of strings
cout << "Current list (strings): ";
list2->print();
cout << "Call to prefix with k = 2: " << endl;
List<string> *preS = list2->prefix(2);
list2->print();
preS->print();
cout << endl;
cout << "Calling with k = 3 (larger than elements...2 elements in list)" << endl;
list2->print();
List<string> *larger = list2->prefix(3);
list2->print();
larger->print();
cout << endl;
// TEST: fast_remove_all() function
cout << "*** TEST FAST_REMOVE_ALL() FUNCTION: ***" << endl
<< "Current list: ";
list->push_back(4); list->push_back(1); list->push_back(4); list->push_back(6); list->push_back(5); list->push_back(4);
list->print();
int numDel = list->fast_remove_all(4);
cout << "After fast remove all (4)...Elements deleted: " << numDel << endl;
list->print();
cout << endl;
// TEST: fast_remove_all() function
cout << "*** TEST FILTER_LEQ() FUNCTION: ***" << endl
<< "Current list: ";
list->clear();
list->push_front(2); list->push_front(3); list->push_front(4);
list->print();
List<int> *filter = list->filter_leq(4);
cout << "After filter_leq(4): " << endl;
list->print();
filter->print();
cout << endl;
cout << "Teacher example list: [4, 9, 2, 4, 8, 12, 7, 3]" << endl;
list->clear();
list->push_back(4); list->push_back(9); list->push_back(2); list->push_back(4);
list->push_back(8); list->push_back(12); list->push_back(7); list->push_back(3);
filter->clear();
list->print();
filter->print();
filter = list->filter_leq(4);
cout << "After filter_leq(4): " << endl;
list->print();
filter->print();
// TEST: suffix maxes
cout << "*** TEST SUFFIX_MAXES() FUNCTION: ***" << endl
<< "Current list: ";
list->clear();
list->push_back(6); list->push_back(-18); list->push_back(12); list->push_back(4);
list->push_back(1); list->push_back(7); list->push_back(2); list->push_back(5); list->push_back(4);
list->print();
filter->clear();
filter->print();
cout << "AFTER: " << endl;
filter = list->suffix_maxes();
list->print();
filter->print();
//filter->print();
return 0;
}
---------------------------------------------------------------------------------------------------------------------------------
//List.h
#ifndef LIST_H
#define LIST_H
#include <algorithm>
#include <iostream>
using namespace std;
template <typename T> class List
{
private:
// struct for singly-linked list nodes
struct Node
{
T data;
Node *next;
Node( const T & d = T{}, Node * n = nullptr)
: data{ d }, next{ n } { }
};
// Holds recursive calls for print_rev so list can be traversed
static void print_rev_help(Node *temp) {
// Base case
if (temp == nullptr) {
return;
}
// Print the list after front node
print_rev_help(temp->next);
cout << temp->data << " ";
}
// suffix_maxes helper function
void suffix_help(Node *p, T &max) {
if (p->next == nullptr) {
return;
}
suffix_help(p->next, max);
if (p->data < max) {
p->data = max;
}
else {
max = p->data;
}
}
public:
// constructors
List( ) {
init( );
}
~List( ) {
clear( );
}
// Makes the calling list empty (but the list still exists)
void clear() {
Node * p = front;
Node *pnext;
while(p != nullptr) {
pnext = p->next;
delete p;
p = pnext;
}
front = back = nullptr;
nodeCount = 0;
}
// Returns the length of the calling list in O(1) time
int length( ) const {
return nodeCount;
}
public:
// Return true if the list is empty, false otherwise
bool is_empty( ) const {
return front == nullptr;
}
// Run through list and print contents
void print() const {
Node *p = front;
if (p == nullptr) {
cout << "List is EMPTY!" << " Number of elements in list: " << length() << endl;
return;
}
cout << "[ ";
while(p != nullptr) {
cout << p->data << " ";
p = p->next;
}
cout << "] ";
cout << "Number of elements in list: " << length() << " ||| Front val/pt: " << front->data << " / "
<< front << " Back val/pt: " << back->data << " / " << back << endl;
}
// Put data onto new node at front of list
void push_front(const T & data) {
front = new Node(data, front);
nodeCount++;
if(back == nullptr)
back = front;
}
// Take front node and delete it from list
bool pop_front(T &val) {
Node *tmp;
if(front==nullptr)
return false;
val = front->data;
tmp = front;
front = front->next;
delete tmp;
if(front==nullptr)
back = nullptr;
nodeCount--;
return true;
}
// Put data onto new node at back of list
void push_back(const T & val) {
Node *tmp = new Node(val, nullptr);
nodeCount++;
if(front == nullptr) {
front = back = tmp;
}
else {
back->next = tmp;
back = tmp;
}
}
// Checks to see if remove first node with specific data is valid
bool remove_first(const T &x) {
Node *p, *tmp;
T dummy;
if(front==nullptr) return false;
if(front->data == x) {
pop_front(dummy);
return true;
}
p = front;
while(p->next != nullptr) {
if(x == p->next->data) {
tmp = p->next;
p->next = tmp->next;
if(tmp == back)
back = p;
delete tmp;
nodeCount--;
return true;
}
p = p->next;
}
return false;
}
// Remove all slow function
int slow_remove_all(const T &x) {
int n=0;
while(remove_first(x))
n++;
return n;
}
// Check each node's value in list and seeing if in order
bool is_sorted() const {
Node *p = front;
while(p!=nullptr && p->next != nullptr) {
if(p->data > p->next->data)
return false;
p = p->next;
}
return true;
}
// Counts number of occurrences of x in the list and returns that count
int count(const T &x) const {
int frequency = 0;
Node *p = front;
while (p != nullptr) {
if (p->data == x) {
frequency++;
}
p = p->next;
}
return frequency;
}
// Remove the last element in the list
bool pop_back(T &data) {
// Check if list is empty
if (is_empty()) {
return false;
}
// Check if list is only one element
if (length() == 1) {
Node *p = back;
data = p->data;
delete p;
front = nullptr;
back = nullptr;
nodeCount--;
return true;
}
// More than one element
Node *x = front;
Node *y = front->next;
while (y->next != nullptr) {
y = y->next;
x = x->next;
}
data = y->data;
x->next = nullptr;
back = x;
delete y;
nodeCount--;
return true;
}
// Return true if calling list and parameter list contain exactly same sequence of values
bool equal_to(const List<T> &other) const {
Node *clist, *plist;
clist = front;
plist = other.front;
// Check same length
if (length() != other.length()) {
return false;
}
// Check values are the same for each node
while (clist != nullptr) {
if (clist->data != plist->data) {
return false;
}
clist = clist->next;
plist = plist->next;
}
return true;
}
// Print reverse of list contents using a recursive helper function
void print_rev() const {
// If list is empty, print it is empty
if (is_empty()) {
cout << "List is EMPTY! Cannot print elements." << endl;
return;
}
// If list is only one element, print same list with note that it only contains one element
if (length() == 1) {
cout << "List has only ONE element and cannot be reversed. That element is: " << front->data << endl;
return;
}
// If list has more than one element, print in reverse order using recursive helper function
print_rev_help(front);
}
// Reverse list in O(n) runtime
void reverse() {
// Declare temp pointers to walk the list
Node *tPrev, *tCurr, *tNext;
tPrev = nullptr;
tCurr = front;
// Keep walking list switching each node's next pointer
while (tCurr != nullptr) {
tNext = tCurr->next;
tCurr->next = tPrev;
tPrev = tCurr;
tCurr = tNext;
}
back = front;
front = tPrev;
}
// function: fast_remove_all
int fast_remove_all(const T &x) {
// Check if list is empty
if (is_empty()) {
cout << "List is empty!" << endl;
return 0;
}
int numDel = 0; // Track number of deletions
Node *temp = front;
Node *prev;
// Check if first element is equal to x
if (front->data == x) {
front = temp->next;
delete temp;
if (front == nullptr) {
back = nullptr;
}
temp = front;
nodeCount--;
numDel++;
}
// Check rest of list, other than front
while (temp != nullptr) {
while (temp != nullptr && temp->data != x) {
prev = temp;
temp = temp->next;
}
// Value was not present in list
if (temp == nullptr) {
return 0;
}
// If lst node is disconnected, set back correctly
if (temp->next == nullptr) {
back = prev;
}
// Unlink node if value found
prev->next = temp->next;
delete(temp);
numDel++;
nodeCount--;
temp = prev->next;
}
return numDel;
}
// Insert x into appropriate position, assuming list given is sorted from smallest to largest
void insert_sorted(const T &x) {
// Check if x is smaller than 1st element and insert there
if (is_empty() || front->data > x) {
push_front(x);
return;
}
// Declare variables to walk the list and track element values
Node *temp, *walk;
temp = front->next;
walk = front;
// Traverse list and find where to put element
while (temp != nullptr) {
if ((temp->data > x && walk->data < x) || walk->data == x) {
Node *xNode = new Node(x, temp);
walk->next = xNode;
nodeCount++;
return;
}
temp = temp->next;
walk = walk->next;
}
push_back(x);
}
// Merge two sorted lists into one, runtime is linear
void merge_with(List<T> &other) {
// Check if calling list is same as parameter list
if(this == &other) {
cerr << "warning: List::merge_with(): calling object same as parameter";
cerr << " list unchanged ";
return;
}
// Check if other list is empty
if (other.is_empty()) {
cerr << "warning: &other is EMPTY! List unchanged." << endl;
return;
}
// Check if calling list is empty
if (is_empty()) {
cout << "Is_empty called!" << endl;
int dummy = 0;
Node *tracker;
while (other.front != nullptr) {
tracker = other.front->next;
push_back(other.front->data);
other.pop_front(dummy);
other.front = tracker;
}
/*
front = other.front;
back = other.back;
other.front = nullptr;
other.back = nullptr;
*/
return;
}
Node *tempFront, *tempBack;
// Set the head of merged list
if (front->data < other.front->data) {
tempFront = front;
tempBack = front;
front = front->next;
}
else {
tempFront = other.front;
tempBack = other.front;
other.front = other.front->next;
}
// Swap nodes into one list
while (front != nullptr && other.front != nullptr) {
if (front->data < other.front->data) {
tempBack->next = front;
tempBack = front;
front = front->next;
}
else {
tempBack->next = other.front;
tempBack = other.front;
other.front = other.front->next;
}
}
// Once one list has run out of elements
if (front != nullptr) {
tempBack->next = front;
}
else {
tempBack->next = other.front;
back = other.back;
}
// Set calling list to temp list with merged values
front = tempFront;
// Set list parameter to nullptr and correct node counts
nodeCount += other.nodeCount;
other.nodeCount = 0;
other.front = other.back = nullptr;
}
// Makes a deep copy of given list and returns list pointer (similar to copy constructor)
List<T> * clone() const {
List<T> *listClone = new List<T>();
Node *temp = front;
while (temp != nullptr) {
listClone->push_back(temp->data);
temp = temp->next;
}
return listClone;
}
// Remove the first k elements from the calling list which are used to form a new list which is then returned
List<T> * prefix(unsigned int k) {
List<T> *prefixList = new List<T>;
// Check if empty
if (is_empty() || k == 0) {
prefixList->nodeCount = 0;
return prefixList;
}
// Check if k is larger than number of elements in list
if (k > length()){
cout << "List only has " << length() << " elements ::: k set to " << k << "." << endl;
cout << "Changing k to equal maximum length of current list: " << length() << endl;
k = length();
}
// Rearrange k values off of calling list and put that value onto newly declared list that will be returned
unsigned int i;
Node *temp;
temp = front;
prefixList->front = temp;
for (i = 0; i < k - 1; i++) {
temp = temp->next;
}
prefixList->back = temp;
front = temp->next;
prefixList->back->next = nullptr;
nodeCount = nodeCount - k;
prefixList->nodeCount = k;
return prefixList;
}
// Remove all elements of given list which is less than or equal to cutoff.
List<T> * filter_leq(const T & cutoff) {
List<T> *filterList = new List<T>;
// Check if empty
if (is_empty()) {
return filterList;
}
Node *p = front;
Node *temp, *q, *walk;
bool frontSet = false;
bool filterFrontSet = false;
// Check each node and compare with cutoff, if data <= cutoff move node to filterList
while (p != nullptr) {
walk = p->next;
if (p->data <= cutoff) {
// Check if front has been assigned yet
if (filterFrontSet) {
q->next = p;
q = p;
q->next = nullptr;
}
else {
q = p;
q->next = nullptr;
filterList->front = q;
filterList->back = filterList->front;
filterFrontSet = true;
}
// Increment node counters
nodeCount--;
filterList->nodeCount = filterList->nodeCount + 1;
}
else {
if (frontSet) {
temp->next = p;
temp = p;
temp->next = nullptr;
}
else {
temp = p;
temp->next = nullptr;
front = temp;
frontSet = true;
}
}
p = walk;
}
// If the entire list is LEQ
if (!frontSet) {
front = nullptr;
}
cout << frontSet << endl;
filterList->back = q;
back = temp;
return filterList;
}
// Concatenates the calling list with parameter list, resulting concatenation reflected in calling list,
void concat(List<T> &other) {
// Check if calling list is same as parameter list
if(this == &other) {
cerr << "warning: List::concat(): calling object same as parameter";
cerr << " list unchanged ";
return;
}
// Check if other list is empty
if (other.is_empty()) {
//cerr << "warning: &other is EMPTY! List unchanged." << endl;
return;
}
// Check if calling list is empty
if (is_empty()) {
//cerr << "warning: calling list is EMPTY!" << endl;
front = other.front;
back = other.back;
nodeCount += other.nodeCount;
other.nodeCount = 0;
other.front = nullptr;
other.back = nullptr;
return;
}
// Set correct nodeCounts
nodeCount += other.length();
other.nodeCount = 0;
back->next = other.front;
back = other.back;
other.front = nullptr;
other.back = nullptr;
//cout << "List::concat(): no error... ";
}
// Compare the calling list with parameter lexically
int compare_with(const List<T> &other) const {
if (this == &other) {
cerr << "warning: List::compare_with(): calling object same as parameter";
cerr << " list unchanged ";
return 0;
}
if (equal_to(other)) {
return 0;
}// || nodeCount < other.nodeCount
else if (is_empty()) {
return -1;
}//|| other.nodeCount < nodeCount
else if (other.is_empty()) {
return 1;
}
Node *clist = front;
Node *plist = other.front;
while (clist != nullptr && plist != nullptr) {
if (clist->data < plist->data) {
return -1;
}
if (plist->data < clist->data) {
return 1;
}
clist = clist->next;
plist = plist->next;
}
if (clist == nullptr) {
return -1;
}
if (plist == nullptr) {
return 1;
}
return 2;
}
// function: suffix_maxes
List<T> * suffix_maxes() const{
List<T> * suffixList = new List<T>;
if (is_empty()) {
return suffixList;
}
suffixList = clone();
Node *p = suffixList->front;
T max = suffixList->back->data;
suffixList->suffix_help(p, max);
return suffixList;
}
private:
Node *front;
Node *back;
int nodeCount; // track numer of nodes created for an instance of List
void init( ) {
front = nullptr;
back = nullptr;
}
};
#endif
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.