In this project, you will write the implementation of the PeopleList using a doubly linked list, which should be sorted alphabetically according to last name, then first name. You will also implement a couple of algorithms that operate on a PeopleList. You must not use any container/STL from the C++ library.

Implement PeopleList Consider the following PeopleList interface: typedef std::string InfoType; class PeopleList { public: PeopleList(); // Create an empty List bool empty() const; // Return true if the list is empty, otherwise false. int size() const; // Return the number of elements in the linked list. bool add(const std::string& firstName, const std::string& lastName, const InfoType& value); // If the full name (both the first and last name) is not equal to any full name currently // in the list then add it and return true. Elements should be added according to // their last name. Elements with the same last name should be added according to // their first names. Otherwise, make no change to the list and return false // (indicating that the name is already in the list). bool change(const std::string& firstName, const std::string& lastName, const InfoType& value); // If the full name is equal to a full name currently in the list, then make that full // name no longer map to the value it currently maps to, but instead map to // the value of the third parameter; return true in this case. // Otherwise, make no change to the list and return false. bool addOrChange(const std::string& firstName, const std::string& lastName, const InfoType &value); // If full name is equal to a name currently in the list, then make that full name no // longer map to the value it currently maps to, but instead map to // the value of the third parameter; return true in this case. // If the full name is not equal to any full name currently in the list then add it // and return true. In fact this function always returns true. bool remove(const std::string& firstName, cont std::string& lastName); // If the full name is equal to a full name currently in the list, remove the // full name and value from the list and return true. Otherwise, make // no change to the list and return false. bool contains(const std::string& firstName, const std::string& lastName) const; // Return true if the full name is equal to a full name currently in the list, otherwise // false. bool lookup(const std::string& firstName, const std::string& lastName, InfoType& value) const; // If the full name is equal to a full name currently in the list, set value to the // value in the list that that full name maps to, and return true. Otherwise, // make no change to the value parameter of this function and return // false. bool get(int i, std::string& firstName, std::string& lastName, InfoType& value) const; // If 0 <= i < size(), copy into firstName, lastName and value parameters the // corresponding information of the element at position i in the list and return // true. Otherwise, leave the parameters unchanged and return false. // (See below for details about this function.)

void swap(PeopleList& other);

// Exchange the contents of this list with the other one. };

The add function primarily places elements so that they are sorted in the list based on last name. If there are multiple entries with the same last name then those elements, with the same last name, are added so that they are sorted by their first name.

In this project, you will write the implementation of the PeopleList using a doubly linked list, which should be sorted alphabetically according to last name, then first name. You will also implement a couple of algorithms that operate on a PeopleList. You must not use any container/STL from the C++ library.

Implement PeopleList Consider the following PeopleList interface: typedef std::string InfoType; class PeopleList { public: PeopleList(); // Create an empty List bool empty() const; // Return true if the list is empty, otherwise false. int size() const; // Return the number of elements in the linked list. bool add(const std::string& firstName, const std::string& lastName, const InfoType& value); // If the full name (both the first and last name) is not equal to any full name currently // in the list then add it and return true. Elements should be added according to // their last name. Elements with the same last name should be added according to // their first names. Otherwise, make no change to the list and return false // (indicating that the name is already in the list). bool change(const std::string& firstName, const std::string& lastName, const InfoType& value); // If the full name is equal to a full name currently in the list, then make that full // name no longer map to the value it currently maps to, but instead map to // the value of the third parameter; return true in this case. // Otherwise, make no change to the list and return false. bool addOrChange(const std::string& firstName, const std::string& lastName, const InfoType &value); // If full name is equal to a name currently in the list, then make that full name no // longer map to the value it currently maps to, but instead map to // the value of the third parameter; return true in this case. // If the full name is not equal to any full name currently in the list then add it // and return true. In fact this function always returns true. bool remove(const std::string& firstName, cont std::string& lastName); // If the full name is equal to a full name currently in the list, remove the // full name and value from the list and return true. Otherwise, make // no change to the list and return false. bool contains(const std::string& firstName, const std::string& lastName) const; // Return true if the full name is equal to a full name currently in the list, otherwise // false. bool lookup(const std::string& firstName, const std::string& lastName, InfoType& value) const; // If the full name is equal to a full name currently in the list, set value to the // value in the list that that full name maps to, and return true. Otherwise, // make no change to the value parameter of this function and return // false. bool get(int i, std::string& firstName, std::string& lastName, InfoType& value) const; // If 0 <= i < size(), copy into firstName, lastName and value parameters the // corresponding information of the element at position i in the list and return // true. Otherwise, leave the parameters unchanged and return false. // (See below for details about this function.)

void swap(PeopleList& other);

// Exchange the contents of this list with the other one. };

The add function primarily places elements so that they are sorted in the list based on last name. If there are multiple entries with the same last name then those elements, with the same last name, are added so that they are sorted by their first name.

When comparing keys for add, change, addOrChange, remove, contains, and lookup, just use the == or != operators provided for the string type by the library. These do case-sensitive comparisons, and that's fine.

For this project, implement this PeopleList interface using a doubly-linked list. (You must not use any container/STL from the C++ library.)

For your implementation, if you let the compiler write the destructor, copy constructor, and assignment operator, they will do the wrong thing, so you will have to declare and implement these public member functions as well:

Destructor

When a PeopleList is destroyed, all dynamic memory must be deallocated.

Copy constructor

When a brand new PeopleList is created as a copy of an existing PeopleList, a deep copy should be made.

Assignment operator

When an existing PeopleList (the left-hand side) is assigned the value of another PeopleList (the right-hand side), the result must be that the left-hand side object is a duplicate of the right-hand side object, with no memory leak (i.e. no memory from the old value of the left-hand side should be still allocated yet inaccessible).

Notice that there is no a priori limit on the maximum number of elements in the PeopleList (so addOrChange should always return true). Also, if a PeopleList has a size of n, then the values of the first parameter to the get member function are 0, 1, 2, ..., n-1; for other values, it returns false without setting its parameters.

Implement some non member functions

Using only the public interface of PeopleList, implement the following two functions. (Notice that they are non-member functions; they are not members of PeopleList or any other class.)

bool combine(const PeopleList& m1, const PeopleList& m2, PeopleList& result);

When this function returns, result must consist of pairs determined by these rules:

If a full name appears in exactly one of m1 and m2, then result must contain an element consisting of that full name and its corresponding value.

If a full name appears in both m1 and m2, with the same corresponding value in both, then result must contain an element with that full name and value.

When this function returns, result must contain no elements other than those required by these rules. (You must not assume result is empty when it is passed in to this function; it might not be.) If there exists a full name that appears in both m1 and m2, but with different corresponding values, then this function returns false; if there is no full name like this, the function returns true. Even if the function returns false, result must be constituted as defined by the above rules.