Implement and test the ADT List from the lecture videos and textbook Chapter 3. You will only be responsible for the coding of file List.h. All other files are provided. Start by downloading these files: Random.h and Random.cpp Lab4Main.cpp With a working List implementation in file List.h, the running program will produce the following kind of output:

My list of random numbers:

(random pos. and neg. #'s coming from the random files))

The max subseq sum: (The max sub seq sum #)

The max subsum sequence:

(the sequence of max subsums)

My list after replacing all max subseq values with 0's:

(-# # # -# 0 0 0 # -# #)

One more time, we are seeing a maximal subsequence sum problem; the program determines the maximal subsequence, prints out the values of this sequence, and replaces (via erase+insert) each value in this subsum sequence with value 0. Since this program generates a list of random numbers (see files Random.h, .cpp), everyones output is likely differ, with a sequence of 0s in a different segment of sequence. When you code our class List, make sure that you include these three (without comment, to keep compiler happy):

List(List&& rhs)

: theSize{ rhs.theSize }, head{ rhs.head }, tail{rhs.tail}

{

rhs.theSize = 0;

rhs.head = nullptr;

rhs.tail = nullptr;

}

//keep for compiler

List& operator = (List&& rhs)

{

std::swap(theSize, rhs.theSize);

std::swap(head, rhs.head);

std::swap(tail, rhs.tail);

return *this;

}

//clear the list by removing all values;

void clear ()

{

while (!empty())

pop_front();

}

------

//here is lab4main.cpp

#include

#include "Random.h"

#include "List.h"

using namespace std;

template

void print_list(List);

List max_subseq_sum_collect(const List&, int&);

int main()

{

List mylst;

random_list(25, 1, 100, mylst, 4);

cout << "My list of random numbers: " << endl;

print_list(mylst);

int maxsubsum;

List maxsubseq = max_subseq_sum_collect(mylst, maxsubsum);

cout << endl;

cout << "The max subseq sum: " << maxsubsum << endl << endl;

cout << "The max subsum squence: " << endl;

print_list(maxsubseq);

cout << endl << endl;

List::iterator itr1 = maxsubseq.begin();

for (; itr1 != maxsubseq.end(); ++itr1)

{

//cout << "erasing value " << *itr1 << endl;

//outp << "erasing value " << *itr1 << endl;

List::iterator itr2 = mylst.begin();

while (itr2 != mylst.end())

{

if (*itr1 == *itr2)

{

int togo = *itr2;

itr2 = mylst.erase(itr2);

mylst.insert(itr2, 0);

//cout << "... erased " << endl;

}

else

itr2++;

}

}

cout << endl << endl;

cout << "My list after replacing all max subseq values with 0: " << endl;

print_list(mylst);

cout << endl << endl;

return 0;

}

template

void print_list(List lst)

{

cout << endl;

typename List::iterator itr;

for (itr = lst.begin(); itr != lst.end(); ++itr)

cout << *itr << " ";

cout << endl;

}

List max_subseq_sum_collect(const List& lst, int& max)

{

int maxsum = 0;

int localsum = 0;

List maxseq;

List localseq;

List::const_iterator itr = lst.begin();

for (; itr != lst.end(); itr++)

{

localsum += *itr;

localseq.push_back(*itr);

if (localsum > maxsum)

{

maxsum = localsum;

maxseq = localseq;

}

else if (localsum < 0)

{

localsum = 0;

localseq.clear();

}

}

max = maxsum;

return maxseq;

}

-----

//Random.cpp

#include

#include

#include "Random.h"

using namespace std;

void rand_seed()

{

int seed = static_cast(time(0));

srand(seed);

}

// random integer between a and b;

int rand_int(int a, int b)

{

return a + rand() % (b - a + 1);

}

// n*10% chance of negative number; repeats allowed;

// absolute value between from and upto;

void random_vector(int k, int from, int upto, vector& v, int negs)

{

rand_seed();

v.clear();

int rnum;

int rneg;

for (int i = 1; i <= k; i++)

{

rnum = rand_int(from, upto);

if (negs > 0)

{

rneg = rand_int(1, 10);

if (rneg < negs)

v.push_back(-rnum);

else

v.push_back(rnum);

}

else

v.push_back(rnum);

}

return;

}

// k random integers 1 to number upto -> vector v;

// no repeated elements in vector v;

void random_vector_norep(int k, int from, int upto, vector& v, int negs)

{

int next;

rand_seed();

v.clear();

vector in(upto + 1, 0);

while (v.size() < k)

{

next = rand_int(from, upto);

int rneg;

if (in[next] == 0)

{

if (negs > 0)

{

rneg = rand_int(1, 10);

if (rneg < negs)

v.push_back(-next);

else

v.push_back(next);

}

else

v.push_back(next);

in[next] = 1;

}

}

return;

}

// random numbers stored in a List

void random_list(int k, int from, int upto, List& lst, int negs)

{

lst.clear();

vector rnums;

random_vector(k, from, upto, rnums, negs);

for (int i = 0; i < rnums.size(); i++)

lst.push_back(rnums[i]);

return;

}

//Random.h

#ifndef RANDOM_H

#define RANDOM_H

#include

#include

#include

#include "List.h"

using namespace std;

void rand_seed();

int rand_int(int, int);

void random_vector(int, int, int, vector&, int);

void random_vector_norep(int, int, int, vector&, int);

void random_list(int, int, int, List&, int);

#endif