Introduction

Now Google is hiring! They have many opening positions, where some positions are for new graduates and some are for experienced ones. A lot of resumes have been received. We assume new graduated students can only submit to positions for new graduates and people with working experience can only submit to positions for experienced ones. The Google HR (Human Resources) department wants to evaluate these resumes, and you are asked to implement a resume container for storing and reviewing resumes submitted to each position.

The Google HR department raised the following requirements:

1. The container can store different types of resumes:
   • Experienced resume: we denote it as a string of the applicant's name, such as "Jack";
   • New graduate resume: we denote it as a pair of strings: the applicant's name and the university's name, such as <"Yang", "HKUST">. We use the std::pair container provided in STL to represent it (a description of std::pair can be found here).
   Note each container will store the same type of resume.
2. The resumes in a container are stored in an ordered sequence. Normally, new resumes can be added to the end of the sequence. Sometimes, high-priority resumes can also be added to the front of the sequence.
3. The HR managers can review the resumes in a container in order. They can choose to review it from the head to the end or from the end to the head.
4. The HR managers can merge two containers with the same type of resumes, make copy of a container, and compare two containers.

After some investigation, you find deque(double end queue) is the most appropriate data structure to implement the resume container. As shown in the figure, a deque is a sequence container that allows adding/removing elements from both the front and the back end. Deque has been implemented in C++ Standrad Template Library (STL), related information can be found in std::deque.

In this lab, you will implement your own version of deque using a doubly linked list. The doubly linked list is a data structure that generalizes the linked list, where every node in a doubly linked list has a pointer to the next node and also a pointer to the previous node. We have implement a skeleton of the deque data structure in source files, you have to finish the TODOs left in the code.

Overview

The descriptions of classes and members in classes are as follows:

• class BiLNode: Class of nodes in the doubly linked list.
  • T data:
  Data element that stores a resume.
  • BiLNode *next:
  Pointer to the next node in the doubly linked list.
  • BiLNode *prev:
  Pointer to the previous node in the doubly linked list.
  • BiLNode(T input):
  Constructor: initilize a node with a resume.

• class Deque:
  • BiLNode *head:
  Pointer to the first element in the deque.
  • BiLNode *tail:
  Pointer to the last element in the deque.
  • int size:
  Size of the deque.
  • void push_back(const T& value) :
  Add element at the end.
  • void push_front(const T& value) :
  Insert element at begining.
  • T pop_back():
  Return and remove the last element.
  • T pop_front():
  Return and remove the first element.
  • void clear():
  Remove all elements.
  • operator==(TODO):
  Return true if and only if the size, elements and the order of elements in two deques are the same. Otherwise return false.
  • operator=(TODO):
  Copy the contents of the input deque to this one. Deep copy is required.
  • operator+(TODO):
  Merge two deques. When computing A+B, return a new deque that has elements from both A and B (A elements in the front and B elements after A elements). Deque A and B should not be changed after this operation. Note this operation is asymmetric.
  • operator<<(TODO):
  Print the information of the deque to the stream. You should loop over all elements in the deque and print them in the format "[element1<-->element2<-->...]" (refer to the example outputs). You can assume operator<< is alreay overloaded for all types of elements.

Following external links may be useful for you:

• Wikipedia: Double-ended queue ;
• Wikipedia: Doubly linked list;
• Examples of using std::pair: here.

Lab tasks

1. Finish the TODOs in deque.h:
   • operator==
   • operator=
   • operator+
   • operator<<
2. Compile the project.
3. Run main.exe, check with the expected output below:

Create resume container for position: C++ developer.
Applicants of C++ developer:
[(James, HKUST)<-->(Yang, HKUST)<-->(Amelia, CUHK)<-->(David, HKU)]
Create resume container for position: C developer.
Applicants of C developer:
[(Tony, HKUST)<-->(Oliver, PolyU)<-->(Wang, CUHK)]
Create resume container for position: AI researcher (experienced)
Applicants of AI researcher (experienced):
[Michael<-->Noah<-->Isabella]
Reviewing resumes for C++ developer.
Remaining resumes for C++ developer:
[(Amelia, CUHK)<-->(David, HKU)]
C++ developer position is closed, add resumes to C developer container.
Applicants of C developer before adding:
[(Tony, HKUST)<-->(Oliver, PolyU)<-->(Wang, CUHK)]
Applicants of C developer after adding:
[(Tony, HKUST)<-->(Oliver, PolyU)<-->(Wang, CUHK)<-->(Amelia, CUHK)<-->(David, HKU)]
Make a copy of AI researcher resumes.
Copy of AI researcher resumes:
[Michael<-->Noah<-->Isabella]
Is the copy equivalent to the orign?
Yes
Is the copy still equivalent to the orign?
No 

FAQ

• Question: Can we return a deque object by value when overloading operator+?

  Answer:

  Usually, when we return a temporary object created in a function by value, the copy constructor will be called to make a copy of the object, and the original temporary object will be destroyed when the function is finished. In this case, if the object holds some dynamically allocated memory and the copy constructor only does shallow copy (as the deque class does), it will cause errors.

  But since C++11, the copy constructor will be omitted in many pass-by-value semantics because of a feature named copy elision (Please also see p18 in lecture notes of constructor & destructor). In the case of this lab, we can safely return a deque object by value when overloading operator+ and the copy constructor will not be called. But since copy elision is not a mandatory feature until C++17, we should still implement the copy constructor carefully in normal cases.

Submission Deadline and Guidelines:

The due date and time will be 10-min after your lab session. You are supposed to upload the following files in an archive to ZINC:

- deque.h

You can submit your codes multiple times by the deadline. Only the last submission will be graded.