Use the DLinkedList provided in class. You must not change any of the existing code in this file! You will add your code to this file.

Add the following methods:

A remove() method that removes a single node containing the value passed in as a parameter from the list. Method signature is provided and may not be changed.

An insertOrder() method that inserts a value into the list in such a way that the list remains sorted in ascending order. Method signature is provided and may not be changed.

An insertOrderUnique() method that does the same as insertOrder() with the additional requirement that the value is only inserted in the list if it is unique. Method signature is provided and may not be changed.

A merge() method that merges the calling list with the parameter list in such a way that the result is a list that is sorted in ascending order and contains no duplicate values. The resulting list should be returned. The two original lists should be empty when the function exits (not destroyed). Method signature is provided and may not be changed.

I am providing a main method. You will add a static method called cleanUp() that takes a string as an argument. The method should return the string after removing any leading or trailing nonalphabetic characters. The resulting string should be in all lowercase. Method signature is provided and may not be changed.

Ideally, merge() should only make one pass through each list. merge() is tricky to get right it may be solved iteratively or recursively. There are many cases to deal with: either initial list may be empty, during processing either list may run out first, and finally there's the problem of starting the result list empty, and building it up while going through the two lists. To get full credit, this method must not use insertOrder or insertOrderUnique or remove.

The main method reads from two files and builds the lists as it goes with cleaned words. It outputs each list, calls merge, and then outputs the two initial lists (which should be empty) and the resulting list.

When you have finished coding your project, create a Loom video in which you execute your program, walk-through your code, and provide a Big-O analysis for your insertOrderUnique() and merge() functions.

Sample run for the following input files:

File1:

Baby Face! You've got the cutest little Baby Face! There's not another one could take your place Baby Face

File2:

I'm bringing home a baby bumblebee, Won't my mommy be so proud of me, I'm bringing home a baby bumblebee, Won't my mommy be so proud of me, Ouch! It stung me! (spoken)

run:

Before merge()

lst1: [another, baby, could, cutest, face, got, little, not, one, place, take, the, there's, you've, your]

lst2: [a, baby, be, bringing, bumblebee, home, i'm, it, me, mommy, my, of, ouch, proud, so, spoken, stung, won't]

After merge()

lst1: []

lst2: []

answer: [a, another, baby, be, bringing, bumblebee, could, cutest, face, got, home, i'm, it, little, me, mommy, my, not, of, one, ouch, place, proud, so, spoken, stung, take, the, there's, won't, you've, your]

BUILD SUCCESSFUL (total time: 0 seconds)

---------

//Lydia K Fritz //2/14/2019 //driver program for DLinkedList C++ //provided

#include "DLinkedList.h" #include #include #include

using namespace std;

string cleanUp(string str);

int main() {

DLinkedList lst1; DLinkedList lst2;

ifstream fin("Text1.in");

string str;

while (fin>>str) { str = cleanUp(str); lst1.insertOrderUnique(str); } fin.close();

fin.open("Text2.in"); while (fin>>str) { str = cleanUp(str); lst2.insertOrderUnique(str); }

cout << "List 1: " << lst1 << endl; cout << "List 2: " << lst2 << endl;

DLinkedList combined = lst1.merge(lst2);

cout << " AFTER MERGE" << endl; cout << "List 1: " << lst1 << endl; cout << "List 2: " << lst2 << endl; cout << " Combined: " << combined << endl;

return 0; }

/** * ASSIGNED * @param str * @return str in all lower case with LEADING and TRAILING non-alpha * chars removed */ string cleanUp(string str) { return str; }

-------------------------DlinkedList.h

//Lydia K Fritz //2/14/2019 //Provided C++ DLinkedList

#pragma once

#ifndef DLINKLIST_H #define DLINKLIST_H

#include

using namespace std;

template class DLinkedList {

//PROVIDED friend ostream & operator<<(ostream & out, const DLinkedList & rhs) { DNode * curr = rhs.header->next; while (curr != rhs.header) { out << curr->data << " "; curr = curr->next; } return out; }

public:

//inner class DNode PROVIDED class DNode { public: DNode * next; DNode * prev; T data;

DNode(T val = T()) { data = val; next = prev = this; } };

//create an empty list: PROVIDED DLinkedList() { //create the header header = new DNode(); }

//add method PROVIDED DNode * add(T item) { //add a new node and return a //pointer to this node DNode * newNode = new DNode(item); newNode->prev = header; newNode->next = header->next; header->next->prev = newNode; header->next = newNode; return newNode; }

/** * ASSIGNED * remove val from the list * * @param val * @return true if successful, false otherwise */ bool remove(T val) { return true; }

/** * ASSIGNED * * @param item */ void insertOrder(T item) {

}

/** * ASSIGNED * * @param item */ bool insertOrderUnique(T item) { return true; }

/** * ASSIGNED * PRE: this and rhs are sorted lists * @param rhs * @return list that contains this and rhs merged into a sorted list * POST: returned list will not contain duplicates, both rhs and this * will have no elements */ DLinkedList merge(DLinkedList rhs) { DLinkedList result; return result; }

private: //DLinkedList fields: PROVIDED DNode * header;

};

#endif