C++. Please help. I'm stuck with my homework.

The DoubleLinkedList class needs to implement a double linked list. Your program cannot use any existing C++ collections to implement this, you need to create the code from scratch.

The ListNode class is going to make the DoubleLinkedList class a friend class (so it can call the private next and previous member functions that update the next and previous pointers). To make this work we are going to have a forward declaration of the DoubleLinkedList template class. See the sample header file for details.

/*

BaseDoubleLinkedList.h

*/

#ifndef DOUBLELINKEDLIST_H_

#define DOUBLELINKEDLIST_H_

#include

#include

#include

// forward declaration of the template class DoubleLinkedList

template

class DoubleLinkedList;

// ListNode class

template

class ListNode

{

// make DoubleLinkedList a friend class

friend class DoubleLinkedList;

private:

// contains the actual data

DataType dataType;

// pointer to the next item in the list or nullptr

// if at the end

ListNode* pNext;

// pointer to the previous item in the list or nullptr

// if at the start

ListNode* pPrevious;

public:

// default constructor

ListNode();

// copy constructor

ListNode(const DataType &newItem);

// get the next node

ListNode* next() const;

// get the previous node

ListNode* previous() const;

// return the data stored in the node as a const

const DataType& data() const;

// return the data stored in the node

DataType& data();

private:

// update the next node

void next(ListNode *nextNode);

// update the previous node

void previous(ListNode *previousNode);

};

// DoubleLinkedList class

template

class DoubleLinkedList

{

private:

// number of nodes in the list. Note that std::size_t

// is defined in header file cstddef.

std::size_t numberNodes;

// point to the first node or nullptr for empty list

ListNode* firstNode;

// point to the last node or nullptr for empty list

ListNode* lastNode;

public:

// default constructor

DoubleLinkedList();

// copy constructor

DoubleLinkedList(const DoubleLinkedList &other);

// destructor

virtual ~DoubleLinkedList();

// return the number of nodes in the list

std::size_t size() const;

// return true if the list is empty

bool empty() const;

// display the contents of the list to std::cout

void print() const;

// dump the contends in debug format to passed in

// ostream - usage to cout would be:

// list.debug(std::cout);

void debug(std::ostream &out) const;

// first node in the list (or nullptr for empty)

virtual ListNode* first() const;

// last node in the list (or nullptr for empty)

virtual ListNode* last() const;

// add an item to the front of the list

virtual void push_front(const DataType &newItem);

// add an item to the back of the list

virtual void push_back(const DataType &newItem);

// remove an item from the front of the list

virtual void pop_front();

// remove an item from the back of the list

virtual void pop_back();

// insert newItem before the existingNode

virtual void insert_before (ListNode* existingNode,

const DataType &newItem);

// insert newItem after the existingNode

virtual void insert_after (ListNode* existingNode,

const DataType &newItem);

// find the node and return the address to the node. Return

// nullptr if not found

virtual ListNode* find(const DataType &existingItem);

// remove the node equal to currentItem

virtual bool erase(const DataType ¤tItem);

// remove the node by address existingNode

virtual bool erase(ListNode *existingNode);

};

// your implementation code goes here

// note the code for the debug() function is included

// display a debug version of the list

template

void DoubleLinkedList::debug(std::ostream &out) const

{

const unsigned int ADDRWIDTH = 10;

out << "START DEBUG" << std::endl;

out << "first =" << std::setw(ADDRWIDTH) << firstNode;

out << ", last=" << std::setw(ADDRWIDTH) << lastNode;

out << ", # nodes=" << size() << std::endl;

unsigned int count = 1;

for (auto current=firstNode; current!= nullptr; current=current->next())

{

out << "node " << std::setw(2) << count;

out << "=" << std::setw(ADDRWIDTH) << current;

out << ", next=" << std::setw(ADDRWIDTH)

<< current->next();

out << ", previous=" << std::setw(ADDRWIDTH)

<< current->previous();

out << ", value=" << current->data() << std::endl;

count++;

}

out << "END DEBUG" << std::endl;

}

#endif /* DOUBLELINKEDLIST_H_ */

The OrderedDoubleLinkedList class will make use of the DoubleLinkList class to implement a sorted

linked list. Note that the ordering will depend on you DataType class supporting the relational

operators. This will be used to determine the order the items are being added. Some of the public

member functions in the OrderedDoubleLinkedList class will have the same signature as those in the

DoubleLinkedList class. Some will have similar signatures. Other member functions in the

DoubleLinkeList will not be in the OrderedLinkedList (such as push_front, pop_front, push_back,

push_front. Insert_before and insert_after). Since the public interface of the OrderedDoubleLinkedList

is not a superset of the public interface of the DoubleLinkedList class we are NOT going to use

inheritance. Instead we are going to use composition.

The insert member function should check and see if the entry being inserted already exists. This is done

my checking to see if there is an existing entry equal to the entry being inserted. If it is already in the

collection the insert member function should replace/update the existing item with the new values. You

should not end up with duplicate entries in the list.

Here is the interface you need for the OrderedDoubleLinkedList

#ifndef ORDEREDDOUBLELINKEDLIST_H_

#define ORDEREDDOUBLELINKEDLIST_H_

#include

#include "DoubleLinkedList.h"

template

class OrderedDoubleLinkedList

{

private:

// we are making use of the DoubleLinkedList class

DoubleLinkedList list;

public:

// default constructor

OrderedDoubleLinkedList();

// destructor

virtual ~OrderedDoubleLinkedList();

// number of items in the list

std::size_t size() const;

// is the list empty (true) or does it have entries (false)

bool empty() const;

// print the items in the list

void print() const;

// display debug information on the passed in ostream

void debug(std::ostream &out) const;

// get first node in the list (or nullptr)

ListNode* first() const;

// get last node in the list (or nullptr)

ListNode* last() const;

// find the entry and return its address

// (nullptr if not found)

ListNode* find(const DataType &existingItem);

// erase the item by DataType value

bool erase(const DataType ¤tItem);

// insert the new item into the list (in sorted order)

// a duplicate entry will be ignored

void insert(const DataType &newItem);

};

// Your implementation code goes here

#endif /* ORDEREDDOUBLELINKEDLIST_H_ */

You are going to be creating a phone book using the OrdererDoubleLinkList class. The entries being

added are going to be of type PhoneBookEntry. This will contain three std::string values for name,

phone number, and e-mail address.

Here are the requirements for the PhoneBookEntry class.

You will need four constructors for the PhoneBookEntry class as follows:

PhoneBookEntry();

PhoneBookEntry(const std::string &name, const std::string &number);

PhoneBookEntry(const std::string &name, const std::string &number,

const std::string &email);

PhoneBookEntry(const PhoneBookEntry ©From);

Note that the last one above is a copy constructor.

In addition you will need the following accessors. Note that we are using more of a C++ style for these

and not the getXxxxx format:

std::string name() const {return sName;

std::string phoneNumber() const;

std::string email() const;

You can also allow updates to the phoneNumber and email values. Note you cannot change the name

member data.

void phoneNumber(const std::string &newNumber);

void email(const std::string &newEmail);

Finally you need to overload the operators ==, !=, <, ><=, > and >= for the PhoneBookEntry class.

You need to check only the name values and not all of the other values for the comparison operations.

For example two PhoneBookEntry objects would be == if the name of one was equal to the name of the

other, even if the phone numbers are different.

You will also need the following stand-alone function. The prototype of this needs to be in the

PhoneBookEntry.h file (but NOT in the class declaration). You should implement it in the PhoneBookEntry.cpp file. This function will display the contents of the PhoneBookEntry on the outostream object.

std::ostream& operator<<(std::ostream &out, const PhoneBookEntry &entry);

Here are the requirements for the PhoneBook class.

The PhoneBook class will be using the OrderedLinkedListClass you created above.

The PhoneBook class needs to have a default constructor.

In addition it will need the following public member functions:

The insert operations will add the PhoneBookEntry to the collection. They are being added in sorted

order, ordered by the name field. This is done by the OrderedDoubleLinkedList class when it uses the

relational operators to determine where to insert the phone book entry. For the 2nd and 3rd versions of

the insert you need to create the PhoneBookEntry that is to be added to the collection. These can be

temporary PhoneBookEntry objects.

void insert(const PhoneBookEntry &entry);

void insert(const std::string &name, const std::string &number,

const std::string &email);

void insert(const std::string &name, const std::string &number);

The erase operation will remove the phone book entry with the associated name from the collection.

This will need to create a temporary PhoneBookEntry that is passed to the appropriate

OrderedDoubleLinkedList operation.

bool erase(std::string name);

The find operation will determine if there is a phone book entry with the specified name in the

collection. It will return true if it is found and false if it is not found.

bool find(std::string name);

The rest of the member functions will delegate the work to the corresponding OrderedDoubleLinkedList

member function.

void print() const;

std::size_t size() const;

ListNode* first() const;

ListNode* last() const;

void debug(std::ostream &out) const;

#include  

#include  

#include "PhoneBook.h" 

#include "DoubleLinkedList.h" 

void testPhoneBook(); 

void testList(); 

int main() 

{ 

 std::cout << "Testing the Phone Book" << std::endl; 

 testPhoneBook(); 

 std::cout << std::endl; 

 std::cout << "Testing the DoubleLinkedList class" << std::endl; 

 testList(); 

 return 0; 

} 

void testPhoneBook() 

{ 

 PhoneBook phoneBook; 

 std::cout << "First do 6 inserts" << std::endl; 

 phoneBook.insert(PhoneBookEntry("The Phone Place", "800-333-2222", "service@example.com")); 

 phoneBook.insert(PhoneBookEntry("Bob Smith", "800-222-3333")); 

 phoneBook.insert(PhoneBookEntry("Sue Jones", "999-444-5678", "suej@example.net")); 

 phoneBook.insert(PhoneBookEntry("Albert A. Allan", "800-111-3333","aaa.whats.up@example.net")); 

 phoneBook.insert(PhoneBookEntry("Zed Zedson", "800-777-3333", "zztop@example.org")); 

 phoneBook.insert(PhoneBookEntry("Sven Stevens", "800-444-3333")); 

 std::cout << std::endl; 

 std::cout << "Display list with " << phoneBook.size() << " items" << std::endl; 

 std::cout << "They should be in order, sorted by name" << std::endl; 

 phoneBook.print(); 

 std::cout << std::endl; 

 std::cout << "Try to insert an already existing entry (Sven Stevens) with a different phone number." << std::endl; 

 std::cout << "This should update the exsting entry." << std::endl; 

 phoneBook.insert(PhoneBookEntry("Sven Stevens", "888-555-1234")); 

 std::cout << std::endl; 

 std::cout << "Display list with " << phoneBook.size() << " items" << std::endl; 

 std::cout << "Sven's number should now be 888-555-1234" << std::endl; 

 phoneBook.print(); 

 std::cout << std::endl; 

 std::cout << "Try out some find operators. Notta Person will not be found." << std::endl; 

 for (auto name: {"Albert A. Allan", "Notta Person", "Zed Zedson"}) 

 { 

 if (phoneBook.find(name)) 

 { 

 std::cout << "Name \"" << name << "\" was found" << std::endl; 

 } 

 else 

 { 

 std::cout << "Name \"" << name << "\" was not found" << std::endl; 

 } 

 } 

 std::cout << std::endl; 

 std::cout << "Now erase some entries from the list. Notta Person will not be dropped since it isn't in the list" << std::endl; 

 for (auto name: {"Albert A. Allan", "Notta Person", "Sue Jones", "Zed Zedson"}) 

 { 

 std::cout << "Erase \""<< name << "\"" << std::endl; 

 if (phoneBook.erase(name)) 

 { 

 std::cout << "Erase was successful" << std::endl; 

 } 

 else 

 { 

 std::cout << "Erase was not successful" << std::endl; 

 } 

 std::cout << std::endl; 

 std::cout << "Display list with " << phoneBook.size() << " items" << std::endl; 

 phoneBook.print(); 

 std::cout << std::endl; 

 } 

 std::cout << "Display list with " << phoneBook.size() << " items in reverse order" << std::endl; 

 std::cout << "When Sven Stevens is found in the loop, update the phone number and e-mail address" << std::endl; 

 for (auto current=phoneBook.last(); current!=nullptr;current=current->previous()) 

 { 

 // note the & in auto &item allows us to update the item. 

 // without this we are just updating a copy and it won't be 

 // reflected in the actual phoneBook entry. 

 auto &item = current->data(); 

 if (item.name() == "Sven Stevens") 

 { 

 item.phoneNumber("555-222-3333"); 

 item.email("sven@example.org"); 

 } 

 std::cout << item << std::endl; 

 } 

 std::cout << std::endl; 

 std::cout << "Debug output" << std::endl; 

 phoneBook.debug(std::cout); 

 std::cout << std::endl; 

} 

void testList() 

{ 

 std::cout << "DoubleLinkedList" << std::endl; 

 DoubleLinkedList list; 

 std::cout << std::endl; 

 std::cout << "First add items 1, 2, 3, 4 and 5 using push_front()" << std::endl; 

 for (auto value: {1, 2, 3, 4, 5}) 

 { 

 std::cout << "push_front()" << std::endl; 

 list.push_front(value); 

 } 

 list.debug(std::cout); 

 std::cout << std::endl; 

 std::cout << "Remove items 5, 4, and 3 using pop_front()" << std::endl; 

 for (auto value: {5, 4, 3}) 

 { 

 std::cout << "pop_front() # " << value << std::endl; 

 list.pop_front(); 

 } 

 std::cout << "First add items 6, 7, 8 and 9 using push_back()" << std::endl; 

 for (auto value: {6, 7, 8, 9}) 

 { 

 std::cout << "push_back()" << std::endl; 

 list.push_back(value); 

 } 

 list.debug(std::cout); 

 std::cout << "Try to find entries 2, 4, 6 and 9. Item 4 will not be found." << std::endl; 

 for (auto entry: {2, 4, 6, 9}) 

 { 

 auto foundEntry = list.find(entry); 

 if (foundEntry == nullptr) 

 { 

 // entry not found 

 std::cout << "Entry " << entry << " was not found" << std::endl; 

 } 

 else 

 { 

 // entry found 

 std::cout << "Entry " << foundEntry->data() << " was found" << std::endl; 

 } 

 } 

 std::cout << "Remove items 9, and 8 using pop_back()" << std::endl; 

 for (auto value: {9, 8}) 

 { 

 std::cout << "pop_back() # " << value << std::endl; 

 list.pop_back(); 

 } 

 list.debug(std::cout); 

 std::cout << "Use the print() function" << std::endl; 

 list.print(); 

 std::cout << "Add new nodes before existing nodes." << std::endl; 

 for (auto value: {6, 2, 7, 3}) 

 { 

 auto findNode = list.find(value); 

 if (findNode != nullptr) 

 { 

 std::cout << "add new node (" << value+10 << ") before " << value << std::endl; 

 list.insert_before(findNode, value+10); 

 } 

 else 

 { 

 std::cout << "node " << value << " not found" << std::endl; 

 } 

 } 

 list.debug(std::cout); 

 std::cout << "Add new nodes after existing nodes." << std::endl; 

 for (auto value: {12, 8, 16, 7}) 

 { 

 auto findNode = list.find(value); 

 if (findNode != nullptr) 

 { 

 std::cout << "add new node (" << value+20 << ") after " << value << std::endl; 

 list.insert_after(findNode, value+20); 

 } 

 else 

 { 

 std::cout << "node " << value << " not found" << std::endl; 

 } 

 } 

 list.debug(std::cout); 

 std::cout << "Try to delete nodes 12, 8, 16, and 27." << std::endl; 

 for (auto value: {12, 8, 16, 27}) 

 { 

 bool deleted = list.erase(value); 

 if (deleted) 

 { 

 std::cout << "deleted node " << value << std::endl; 

 } 

 else 

 { 

 std::cout << "node " << value << " not found" << std::endl; 

 } 

 } 

 list.debug(std::cout); 

 std::cout << "make a copy of the list" << std::endl; 

 { 

 auto list2(list); 

 std::cout << "Original list" << std::endl; 

 list.debug(std::cout); 

 std::cout << "Copy of list" << std::endl; 

 list2.debug(std::cout); 

 } 

 std::cout << "remove all entries" << std::endl; 

 while (!list.empty()) 

 { 

 std::cout << "pop_front()" << std::endl; 

 list.pop_front(); 

 } 

 list.debug(std::cout); 

}