In C++ not C In this project, you will write the implementation of the PeopleLis
ID: 3869029 • Letter: I
Question
In C++ not C
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.
Implement PeopleList
Consider the following PeopleList interface:
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 other words, this code fragment
must result in the output:
Notice that the empty string is just as good a string as any other; you should not treat it in any special way:
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 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 arenon-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.
For example, suppose a PeopleList maps the full name to integers. If m1 consists of these three elements
and m2 consists of
then no matter what value it had before, result must end up as a list consisting of
and combine must return true. If instead, m1 were as before, and m2 consisted of
then no matter what value it had before, result must end up as a list consisting of
and combine must return false.
When this function returns, result must contain a copy of all the elements in m1 that match the search terms; it must not contain any other elements. You can wildcard the first name, last name or both by supplying "*". (You must not assume result is empty when it is passed in to this function; it may not be.)
For example, if p consists of the three elements
and the following call is made:
then no matter what value it had before, result must end up as a PeopleList consisting of
If instead, p1 were
and the following call is made:
then no matter what value it had before, result must end up as a list consisting of
and if the following call is made:
then no matter what value it had before, result must end up being a copy of p
Be sure these functions behave correctly in the face of aliasing: What if m1 and result refer to the same PeopleList, for example?
Other Requirements
Regardless of how much work you put into the assignment, your program will receive a low score for correctness if you violate these requirements:
Your class definition, declarations for the two required non-member functions, and the implementations of any functions you choose to inline must be in a file named PeopleList.h, which must have appropriate include guards. The implementations of the functions you declared in PeopleList.h that you did not inline must be in a file named PeopleList.cpp. Neither of those files may have a main routine (unless it's commented out). You may use a separate file for the main routine to test your PeopleList class; you won't turn in that separate file.
Except to add a destructor, copy constructor, assignment operator, and dump function (described below), you must not add functions to, delete functions from, or change the public interface of the PeopleList class. You must not declare any additional struct/class outside the PeopleList class, and you must not declare any public struct/class inside the PeopleList class. You may add whatever private data members and private member functions you like, and you may declare private structs/classes inside the PeopleList class if you like. The source files you submit for this project must not contain the word friend. You must not use any global variables whose values may be changed during execution.
If you wish, you may add a public member function with the signature void dump() const. The intent of this function is that for your own testing purposes, you can call it to print information about the map; we will never call it. You do not have to add this function if you don't want to, but if you do add it, it must not make any changes to the map; if we were to replace your implementation of this function with one that simply returned immediately, your code must still work correctly. The dump function must not write to cout, but it's allowed to write to cerr.
Your code must build successfully (under both g32 and either clang++ or Visual C++) if linked with a file that contains a main routine.
You must have an implementation for every member function of PeopleList, as well as the non-member functions combine and psearch. Even if you can't get a function implemented correctly, it must have an implementation that at least builds successfully. For example, if you don't have time to correctly implement PeopleList::remove or psearch, say, here are implementations that meet this requirement in that they at least build successfully:
You've probably met this requirement if the following file compiles and links with your code. (This uses magic beyond the scope of CS 32.)
If you add #include to PeopleList.h, have the typedef define InfoType as std::string, and link your code to a file containing
the linking must succeed. When the resulting executable is run, it must write Passed all tests to cout and nothing else to cout.
If we successfully do the above, then make no changes to PeopleList.h other than to change the typedefs for PeopleList so that InfoType specifies int, recompile PeopleList.cpp, and link it to a file containing
the linking must succeed. When the resulting executable is run, it must write Passed all tests to cout and nothing else to cout.
During execution, if a client performs actions whose behavior is defined by this spec, your program must not perform any undefined actions, such as dereferencing a null or uninitialized pointer.
Your code in PeopleList.h and PeopleList.cpp must not read anything from cin and must not write anything whatsoever to cout. If you want to print things out for debugging purposes, write to cerr instead of cout. cerr is the standard error destination; items written to it by default go to the screen. When we test your program, we will cause everything written to cerr to be discarded instead — we will never see that output, so you may leave those debugging output statements in your program if you wish.
Explanation / Answer
main.cpp
--------------------------
#include <iostream>
#include <string>
#include <assert.h>
#include "PeopleList.h"
using namespace std;
/*
int main() {
PeopleList result;
PeopleList m1;
PeopleList m2;
result.add("Allen", "Amy", 1000);
m1.add("Skyler", "White", 45);
m1.add("James", "McGill", 49);
m1.add("Charles", "McGill", 58);
m2.add("Walter", "White", 52);
m2.add("Jesse", "Pinkman", 27);
cout << combine(m1, m2, result) << endl;
for (int n = 0; n < result.size(); n++)
{
string f;
string l;
int v;
result.get(n, f, l, v);
cout << f << " " << l << " " << v << endl;
}
}
*/
/*int main() {
PeopleList p1;
PeopleList result;
p1.add("Gustavo", "Fring", 57);
p1.add("Skyler", "White", 45);
p1.add("Walter", "White", 45);
p1.add("Jane", "Doe", 35);
p1.add("Marie", "Schrader", 37);
p1.add("Jane", "Margolis", 27);
search("*", "*", p1, result);
for (int n = 0; n < result.size(); n++)
{
string f;
string l;
int v;
result.get(n, f, l, v);
cout << f << " " << l << " " << v << endl;
}
}*/
#include "PeopleList.h"
#include <string>
#include <iostream>
#include <cassert>
using namespace std;
void test()
{
PeopleList m;
assert(m.add("Fred", "Mertz", 52));
assert(m.add("Ethel", "Mertz", 49));
assert(m.size() == 2);
string first, last;
int a;
assert(m.get(0, first, last, a) && a == 49);
string s1;
assert(m.get(1, first, last, a) &&
(first == "Fred" && a == 52));
}
int main()
{
test();
cout << "Passed all tests" << endl;
}
------------------------------------------------------
PeopleList.cpp
-----------------------------
#include <iostream>
#include <string>
#include "PeopleList.h"
PeopleList::PeopleList()
:listSize(0) {
Node *newNode = new Node;
head = newNode;
head -> next = head;
head -> previous = head;
head -> m_firstName = "";
head -> m_lastName = "";
}
PeopleList::PeopleList(const PeopleList &other) {
Node *newNode = new Node;
head = newNode;
head->next = head;
head->previous = head;
head->m_firstName = "";
head->m_lastName = "";
Node *p = other.head->next;
Node *n = head;
while (p!=other.head) {
Node *newNode = new Node;
newNode->next = head;
newNode->previous = n;
n->next = newNode;
head->previous = newNode;
newNode->m_value = p->m_value;
newNode->m_firstName = p->m_firstName;
newNode->m_lastName = p->m_lastName;
n = newNode;
p = p->next;
}
listSize = other.listSize;
}
PeopleList& PeopleList::operator=(const PeopleList& other) {
PeopleList copy(other);
swap(copy);
return *this;
}
PeopleList::~PeopleList() {
Node *p = head->next;
while (p!=head) {
head->next = p->next;
head->next->previous = head;
Node *n = p;
p = p->next;
delete n;
}
delete head;
}
PeopleList::Node* PeopleList::PosOfFirstName(const std::string &firstname) { //return the place ready to insert. Need to insert the next node.
Node *p = head;
for (p=p->next; p!=head; p=p->next) {
if (p->m_firstName < firstname && p->next->m_firstName > firstname) {
return p;
}
}
if (firstname > p->next->m_firstName)
return p->previous;
else
return p;
}
PeopleList::Node* PeopleList::PosOfLastName(const std::string &lastname) {
Node *p = head;
for (p=p->next; p!=head; p=p->next) {
if (p->m_lastName < lastname && p->next->m_lastName > lastname) {
return p;
}
}
if (lastname > p->next->m_lastName)
return p -> previous;
else
return p;
}
int PeopleList::size() const {
return listSize;
}
bool PeopleList::add(const std::string& firstName, const std::string& lastName, const InfoType& value) {
bool lastNameSame = false;
Node *p = head->next;
for (; p!=head; p = p->next) {
if (p->m_firstName == firstName && p->m_lastName == lastName){
return false;
}
else if (p->m_lastName == lastName) {
lastNameSame = true;
break;
}
else
;
}
Node *newNode = new Node;
newNode->m_firstName = firstName;
newNode->m_lastName = lastName;
newNode->m_value = value;
if (lastNameSame == true) {
p = PosOfFirstName(firstName);
newNode->next = p->next;
newNode->previous = p;
p->next->previous = newNode;
p->next = newNode;
listSize++;
return true;
}
else {
p = PosOfLastName(lastName);
newNode->next = p->next;
newNode->previous = p;
p->next->previous = newNode;
p->next = newNode;
listSize++;
return true;
}
}
bool PeopleList::get(int i, std::string& firstName, std::string& lastName, InfoType& value) const {
int counter = 0;
for (Node *p = head->next; p != head; p=p->next) {
if (counter == i) {
firstName = p->m_firstName;
lastName = p-> m_lastName;
value = p->m_value;
return true;
}
else
counter++;
}
return false;
}
bool PeopleList::change(const std::string& firstName, const std::string& lastName, const InfoType& value) {
Node *p = head->next;
for (; p != head; p = p->next) {
if (p->m_firstName == firstName && p->m_lastName == lastName) {
p->m_value = value;
return true;
}
}
return false;
}
bool PeopleList::addOrChange(const std::string& firstName, const std::string& lastName, const InfoType& value) {
bool lastNameSame = false;
Node *p = head->next;
for (; p != head; p = p->next) {
if (p->m_firstName == firstName && p->m_lastName == lastName) {
p->m_value = value;
return true;
}
else if (p->m_lastName == lastName) {
lastNameSame = true;
break;
}
else
;
}
Node *newNode = new Node;
newNode->m_firstName = firstName;
newNode->m_lastName = lastName;
newNode->m_value = value;
if (lastNameSame == true) {
p = PosOfFirstName(firstName);
newNode->next = p->next;
newNode->previous = p;
p->next->previous = newNode;
p->next = newNode;
listSize++;
return true;
}
else {
p = PosOfLastName(lastName);
newNode->next = p->next;
newNode->previous = p;
p->next->previous = newNode;
p->next = newNode;
listSize++;
return true;
}
}
bool PeopleList::remove(const std::string& firstName, const std::string& lastName) {
Node *p = head->next;
for (; p != head; p = p->next) {
if (p->m_firstName == firstName && p->m_lastName == lastName) {
p->previous->next = p->next;
p->next->previous = p->previous;
delete p;
listSize--;
return true;
}
}
return false;
}
bool PeopleList::contains(const std::string& firstName, const std::string& lastName) const {
Node *p = head->next;
for (; p != head; p = p->next) {
if (p->m_firstName == firstName && p->m_lastName == lastName)
return true;
}
return false;
}
bool PeopleList::lookup(const std::string& firstName, const std::string& lastName, InfoType& value) const {
Node *p = head->next;
for (; p != head; p = p->next) {
if (p->m_firstName == firstName && p->m_lastName == lastName) {
value = p->m_value;
return true;
}
}
return false;
}
bool PeopleList::empty() const {
if (head->next == head && head->previous == head)
return true;
else
return false;
}
void PeopleList::swap(PeopleList& other) {
Node *temp = new Node;
temp->m_firstName = "";
temp->m_lastName = "";
temp->next = head->next;
head->next->previous = temp;
temp->previous = head->previous;
head->previous->next = temp;
head->next = other.head->next;
other.head->next->previous = head;
head->previous = other.head->previous;
other.head->previous->next = head;
other.head->next = temp->next;
temp->next->previous = other.head;
other.head->previous = temp->previous;
temp->previous->next = other.head;
std::swap(listSize, other.listSize);
}
bool combine(const PeopleList& m1, const PeopleList& m2, PeopleList& result) {
bool isEqualValue = true;
for (int j = 0; j < m1.size(); j++) {
std::string firstName;
std::string lastName;
InfoType m1Value;
InfoType resultValue;
m1.get(j, firstName, lastName, m1Value);
if (result.lookup(firstName, lastName, resultValue) && resultValue == m1Value) {
;
}
else if (result.lookup(firstName, lastName, resultValue) && resultValue != m1Value) {
result.remove(firstName, lastName);
isEqualValue = false;
}
else {
result.add(firstName, lastName, m1Value);
}
}
for (int i = 0; i < m2.size();i++){
std::string firstName;
std::string lastName;
InfoType m2Value;
InfoType resultValue;
m2.get(i, firstName, lastName, m2Value);
if (result.lookup(firstName,lastName,resultValue) && resultValue == m2Value ) {
;
}
else if (result.lookup(firstName, lastName, resultValue) && resultValue != m2Value) {
result.remove(firstName, lastName);
isEqualValue = false;
}
else {
result.add(firstName, lastName, m2Value);
}
}
return isEqualValue;
}
void search(const std::string& fsearch, const std::string& lsearch, const PeopleList& p1, PeopleList& result) {
if (fsearch == "*" && lsearch == "*") {
for (int i = 0; i < p1.size(); i++) {
std::string firstName;
std::string lastName;
InfoType p1Value;
p1.get(i, firstName, lastName, p1Value);
result.add(firstName, lastName, p1Value);
}
}
else if (fsearch == "*" && lsearch != "*") {
for (int j = 0; j < p1.size(); j++) {
std::string firstName;
std::string lastName;
InfoType p1Value;
p1.get(j, firstName, lastName, p1Value);
if (lastName==lsearch) {
result.add(firstName, lastName, p1Value);
}
}
}
else if (fsearch != "*" && lsearch == "*") {
for (int j = 0; j < p1.size(); j++) {
std::string firstName;
std::string lastName;
InfoType p1Value;
p1.get(j, firstName, lastName, p1Value);
if (firstName == fsearch) {
result.add(firstName, lastName, p1Value);
}
}
}
else {
if (p1.contains(fsearch,lsearch)) {
InfoType p1Value;
p1.lookup(fsearch, lsearch, p1Value);
result.add(fsearch, lsearch, p1Value);
}
else{
return;
}
}
}
------------------------------------------------------
PeopleList.h
-----------------------------
#ifndef PeopleList_h
#define PeopleList_h
#include <string>
typedef int InfoType;
class PeopleList
{
private:
struct Node {
InfoType m_value;
std::string m_firstName;
std::string m_lastName;
Node *previous;
Node *next;
};
Node *head;
int listSize;
Node *PosOfLastName(const std::string &lastName);
Node *PosOfFirstName(const std::string &firstName);
public:
PeopleList(); // Create an empty In (i.e., one with no InfoType values)
PeopleList(const PeopleList &other); // Copy constructor
PeopleList& operator=(const PeopleList& other); //assignment operator overloading
~PeopleList(); // When a PeopleList is destroyed, all dynamic memory must be deallocated.
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, const 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.
};
bool combine(const PeopleList& m1, const PeopleList& m2, PeopleList& result);
void search(const std::string& fsearch, const std::string& lsearch,
const PeopleList& p1, PeopleList& result);
#endif /* PeopleList_h */