Lab 2 (100 pts) 
Due Monday, April 23 at 9:20am on Canvas


Part 1: Templating Your List
  • For this Lab, you will need to template your List class.
  • The purpose of templating your list is to allow it hold any type of data (not just ints).
  • Otherwise, you would need to write a whole new list class for strings, one for chars, one for doubles, or any other type of data you need to store in your list. What a pain!
  • Fortunately, we can use templating to help us.
  • Templating makes your list much more flexible by allowing it to store ANY type of data without having to rewrite the class.
  • You will need to specify that you List holds a generic type of objects (not ints anymore).
  • To do so, follow these steps:
  • Step 1: Open up your List.h file and add the following line above your definition of the List class:

    template <class listdata> //list stores generic listdata, not any specific C++ type
    class List {
  • Also, alter the Node struct to store listdata rather than integer data:

        struct Node {
            listdata data;
            Node* next;

            Node(listdata newData){
                data = newData;
                next = NULL;
            }

        };

  • Step 2: for EACH function in your list, you will need to alter it so it works with generic data. Make changes like so:
    void insertStart(listdata data); //this function now takes in generic data

    listdata getStart(); //this function now returns generic data
  • Alter ALL remaining functions prototypes inside your List.h to work with generic listdata, as show above. Note that you will not need to alter functions like getLength which always should return an int. (Why?)
  • Step 3: Alter the functions inside your List.cpp file that you wrote for Lab 1 to match the prototypes in the List header file. In other words:
        For EACH of these functions, you will need to template them.
       Also you *may* need to change the type of data that they return or take in as a parameter so that it is generic.
  • Here is an example of how to alter one of these functions:
template<class listdata>
void List<listdata>::insertStart(listdata data) {
    if (length == 0) {
        start = stop = new Node(data);
    } else {
        Node* N = new Node(data);
        N->next = start;
        start = N;
    }
    length++;
}
  • Step 4: Now, build your List.cpp file and correct any errors that the compiler is giving you.
  • Step 5: Inside of ListTest.cpp, alter any calls to your List constructor to specify that the list contains ints, by placing the word int inside of the <>. Please see below:

int main()
{
    List<int> L1; //indicate the list holds ints
    L1.insertStart(0);

    List<string> L2; //indicate the list holds strings

    L2.insertStart("Hi!");

}

  • Now, compile and run your code and verify that it works identically to the previous version without templates
  • Step 6: When you compile and run your code now (with your main function inside of ListTest.cpp), your code WILL NOT work.
  • To solve this problem, you must cut and paste all of the code from your List.cpp and place it inside your List.h file. This code will go at the very bottom, outside of and below the List class definition.
  • I want your List.h to look like this:

class List {

    //private fields

   //public function prototypes

    //No function definitions in here!!

};

//copy and paste all of the functions from List.cpp here

//Note that libraries and namespace should go at the top of this file, not right here


  • Now, you should have only two functional files: List.h and ListTest.cpp
  • You can leave List.cpp as an empty file or simply comment out the contents of this file.
  • Step 7: Compile and run your code again and verify that it is now working.
  • Once you are sure it is still working properly, try testing your list with different types of data.
  • For example, make Lists of strings, doubles, chars.

Part 2: Creating a Doubly-Linked List
  • The next part of the assignment is to alter the list that you wrote in class and lab to be a doubly-linked list.
  • The principle difference between the singly-linked list that you wrote in class and a doubly-linked list is that each node contains a pointer both to the next node and to the previous node in the list.
  • You can visualize a doubly-linked list likes so:

Image source.

  • Therefore, your inner Node struct will look like the following:


               struct Node {

        listdata data;
        Node* next;
        Node* previous;
        Node(listdata newData) {
                data = newData;
                next = NULL;
                previous = NULL;
        }

       };

  • Additionally, bear in mind that the first Node of the list now has a prev Node pointer to NULL while the stop Node has a next Node pointer to NULL.
  • The advantage of the previousnode pointer is the ease with which we can traverse the list in both directions.
  • To account for the presence of this additional pointer, you will need to make updates to your code for many of the list operations.
  • Most of these updates are as simple as adding one line of code per function.
  • For example, let's look at the insertFirst operation:
template<class listdata>
void List<listdata>::insertStart(listdata data) {
    if (length == 0) {
        start = stop = new Node(data);
    } else {
        Node* N = new Node(data);
        N->next = start;
        start->previous = N;
        start = N;
    }
    length++;
}
  • Important! Each time you update one of your functions, run your tests again to make sure your list is still working properly.

More Information


Part 3: Adding New Functions to your List

  • Your doubly-linked list needs to be able to perform all of the same operations as your singly linked list.
  • In addition, you must add some additional functions to your List class. 
  • When you add a new function to a class, you will need to do three things:
    • Write a prototype and comment for the function (include pre and post conditions in your comments) inside of List.h
    • Write the full function definition below the List class inside of List.h
    • Test the function 2-3 times inside of your ListTest.cpp file by calling the function 2-3 times.
  • All of the required functions are described below:


Constructors:

constructor: constructs a new linked list object.
copy constructor: makes a copy of the list object
destructor: frees the memory associated with the linked list

Manipulation Procedures:

removeStart: removes the element at the beginning of the list   
removeStop:
removes the element at the end of the list

insertStart:
inserts an element at the beginning of the linked list

insertStop:
inserts an element at the end of the list
startIterator: moves the iterator to the start of the list
removeIterator: removes the element currently pointed to by the iterator. Iterator then points to NULL.
insertIterator: inserts an element after the node currently pointed to by the iterator
moveIterNext: moves the iterator up by one node towards stop
moveIterPrevious: moves the iterator down by one node towards start

Access Functions:

getStart: returns the data of the first element
getStop:
returns the data of the last element

isEmpty: tests whether the linked list is empty
getLength: returns the current size of the list
getIterator: returns the element currently pointed at by the iterator
offEnd: returns whether the iterator is off the end of the list, i.e. is NULL
==: compares this list to see if it contains the same data, in the same order as another list.


Additional Operations:

displayList: prints the contents of the linked list to the screen or a file separated by a blank space
displayNumberedList: prints the contents of the linked list to the screen or a file in the format #: <element> followed by a newline

Updating displayList
  • For the purposes of this lab, you will need to update the signature of displayList to be the following:

void displayList(ostream& out);

  • Similarly, you will also write displayNumberedList, with the following signature:

void displayNumberedList(ostream& out);

  • Now, when you call these functions, you can pass in cout or a file stream parameter to indicate whether the function should write to the console or to a file. For example:

L1.displayList(cout);

ofstream fout;

....

L2.displayList(fout);

Testing displayList and displayNumberedList with a file in Eclipse:

  • You may want to create an output file to test your printing functions. Below is the process to follow in Eclipse:
    • Right-click on the main project folder
    • From the drop down menu select New->File
    • Choose a name for your file (e.g. output.txt) and click save.
    • A new file should appear under the main project folder.
      • Verify that your file ended up being saved in the main project folder. The compiler will look for it there.
      • Make sure your file did not get saved under the src folder!

Part 4: Handling Preconditions
  • Make sure that you are handling ALL preconditions using assert in your List class, as described in class.
  • Update your functions as necessary to use assert for these preconditions.
  • See Lesson 3 for more information and examples.


Part 5: Anagrams
Overview
  • Create a file called Anagram.cpp, which reads in a series of words from a file.
  • For each word read in from the file, the user will have the option to swap letters within that word.
  • You are required to use your templated doubly-linked list class to receive credit for this part of the assignment.
  • Therefore, your word should be stored as a List of chars.
  • After the user has rearranged the word, it should be written to a file, including the changes the user has made.

Specifications

  • The program should welcome the user with the message Welcome to the Anagram Arranger!
  • It should then prompt the user to enter the name of a file.
  • Provided the user enters a correct file name (see section regarding error checking below), then the program will read in all of the words in the file, one-by-one.
  • Each word should be stored in a List of chars.
  • It will display the word, along with its corresponding number, with the message:  Word #<count> is <word>
  • See below for examples.
  • The user will then be prompted to enter the position of two different letters in the word that the user wants to be swapped.
  • The program will verify the user choice by re-printing the word with carrots beneath the selected letters.
  • The user will then be required to confirm his or her choice with the message: Enter the position numbers of the two letters you wish to swap:
    • The program should accept four different input options from the user -- y, Y, yes, and Yes -- to indicate consent.
  • If the user indicates "no", the word will be reprinted with a prompt to enter the position of two different letters.
  • If the user enters yes, then the program should swap the two selected letters, and then prompt the user to indicate whether he or she would like to swap additional letters in the word.
    • The program should accept four different input options from the user -- y, Y, yes, and Yes -- to indicate consent.
  • The user should be able to continue swapping letters indefinitely.
  • Once the user no longer wishes to swap, the current version of the word should be written to a file named output.txt
  • Please see below for an incomplete example run:
Welcome to the Anagram Arranger!

Please enter the name of your input file: spooky.txt

Word #1 is zombie
1: z
2: o
3: m
4: b
5: i
6: e

Enter the position numbers of the two letters you wish to swap: 1 2

z o m b i e
^ ^  
Are these the letters you wish to swap? (y/n): y

The new word is: o z m b i e

Want to keep rearranging? (y/n): y

1: o
2: z
3: m
4: b
5: i
6: e

Enter the position numbers of the two letters you wish to swap: 3 5

o z m b i e
    ^   ^        
Are these the letters you wish to swap? (y/n): y

The new word is: o z i b m e

Want to keep rearranging? (y/n): n


Word #2 is mummy
1: m
2: u
3: m
4: m
5: y

Enter the position numbers of the two letters you wish to swap: 
etc...


A complete Example:

This example assumes an input file named words.txt with the following content:

Spring
Summer
Fall
Winter


Output of running Anagram.cpp


Welcome to the Anagram Arranger!

Please enter the name of your input file: abc.txt

Sorry. I cannot find a file by that name!
Please enter the name of a valid input file: 123.txt

Sorry. I cannot find a file by that name!
Please enter the name of a valid input file: words.txt

Word #1 is Spring
1: S
2: p
3: r
4: i
5: n
6: g

Enter the position numbers of the two letters you wish to swap: 3 5

S p r i n g
    ^   ^         
Are these the letters you wish to swap? (y/n): y

The new word is: S p n i r g

Want to keep rearranging? (y/n): yes

1: S
2: p
3: n
4: i
5: r
6: g

Enter the position numbers of the two letters you wish to swap: 1 6

S p n i r g
^         ^           
Are these the letters you wish to swap? (y/n): yes

The new word is: g p n i r S

Want to keep rearranging? (y/n): n


Word #2 is Summer
1: S
2: u
3: m
4: m
5: e
6: r

Enter the position numbers of the two letters you wish to swap: 2 3

S u m m e r
  ^ ^     
Are these the letters you wish to swap? (y/n): Yes

The new word is: S m u m e r

Want to keep rearranging? (y/n): Yes

1: S
2: m
3: u
4: m
5: e
6: r

Enter the position numbers of the two letters you wish to swap: 4 5

S m u m e r
      ^ ^         
Are these the letters you wish to swap? (y/n): y

The new word is: S m u e m r

Want to keep rearranging? (y/n): n


Word #3 is Fall
1: F
2: a
3: l
4: l

Enter the position numbers of the two letters you wish to swap: 1 2

F a l l
^ ^   
Are these the letters you wish to swap? (y/n): y

The new word is: a F l l

Want to keep rearranging? (y/n): n


Word #4 is Winter
1: W
2: i
3: n
4: t
5: e
6: r

Enter the position numbers of the two letters you wish to swap: 1 3

W i n t e r
^   ^     
Are these the letters you wish to swap? (y/n): n
1: W
2: i
3: n
4: t
5: e
6: r

Enter the position numbers of the two letters you wish to swap: 1 4

W i n t e r
^     ^       
Are these the letters you wish to swap? (y/n): y

The new word is: t i n W e r

Want to keep rearranging? (y/n): y

1: t
2: i
3: n
4: W
5: e
6: r

Enter the position numbers of the two letters you wish to swap: 2 5

t i n W e r
  ^     ^         
Are these the letters you wish to swap? (y/n): y

The new word is: t e n W i r

Want to keep rearranging? (y/n): y

1: t
2: e
3: n
4: W
5: i
6: r

Enter the position numbers of the two letters you wish to swap: 3 4

t e n W i r
    ^ ^       
Are these the letters you wish to swap? (y/n): y

The new word is: t e W n i r

Want to keep rearranging? (y/n): n

Bye!

Corresponding output.txt for above example:

g p n i r S
S m u e m r
a F l l
t e n W i r

Required Error Checking
  • Your Anagram.cpp should also do error checking for the following cases only:
  1. The user inputs a position number that is higher than the position of the last character in the word
  2. The user reverses the order of the two positions by giving the higher number followed by the lower number
  3. The user enters the same position number twice.
  • For the above errors, the program should print the message Invalid entry! and allow the user to try again, as shown in the example below.
  • Additionally, the program should correctly handle the below error:
  1. The user enters an incorrect name for a file.
    1. Error checking should be completed using a loop to handle multiple invalid inputs
    2. Error message must be:

Sorry. I cannot find a file by that name!
Please enter the name of a valid input file:

  • Please see below for examples of how to handle invalid input.

Error Checking Example:


Welcome to the Anagram Arranger!

Please enter the name of your input file: ddd.txt

Sorry. I cannot find a file by that name!
Please enter the name of a valid input file: nnn.txt

Sorry. I cannot find a file by that name!
Please enter the name of a valid input file: splooky.txt

Sorry. I cannot find a file by that name!
Please enter the name of a valid input file: spooky.txt

Word #1 is zombie
1: z
2: o
3: m
4: b
5: i
6: e

Enter the position numbers of the two letters you wish to swap: 4 2

Invalid entry!

1: z
2: o
3: m
4: b
5: i
6: e

Enter the position numbers of the two letters you wish to swap: 1 10

Invalid entry!

1: z
2: o
3: m
4: b
5: i
6: e

Enter the position numbers of the two letters you wish to swap: 2 2

Invalid entry!

1: z
2: o
3: m
4: b
5: i
6: e

Enter the position numbers of the two letters you wish to swap: 2 3

z o m b i e
  ^ ^    
Are these the letters you wish to swap? (y/n): yes

The new word is: z m o b i e

Want to keep rearranging? (y/n): etc.


Specifications for Submission
  • Please submit 3 files to Canvas before the deadline:
  1. List.h (header file as created in class - now with ALL of your full function definitions as described above)
  2. ListTest.cpp (test file with multiple tests for each function you write - this should be the test file you write, not the one I provide you. Please copy and paste the results of running your tests into the comments at the bottom of the file)
  3. Anagram.cpp (source file with all of the logic to process words identically to what is shown above)
  • Important: You must name your files exactly as described above -- List.h, ListTest.cpp and Anagram.cpp -- for full credit
  • Additionally, in Anagram.cpp the user must be allowed to enter the name of any input file. However, the name of the output file must be output.txt.
  • Your Anagram.cpp must run identically to mine for full credit - including formatting
  • Also, your code must compile using gcc on Eclipse for C++.
  • You must use NULL, not nullptr
  • Please do not submit as a Zip file


How You Will Be Graded:

  • No credit if your List.h file does not contain the functions specified in the directions or if the Node struct has been altered in any way from what was given in class.
  • Also, you are not permitted to add any additional List functions to those specified or you will receive no credit for this assignment.
  • Make sure that you test your list thoroughly inside of ListTest.cpp!
  • No credit if your assignment doesn't compile or run using the Eclipse IDE as specified above
  • No credit if your program doesn't compile. Make sure to comment out the parts that aren't working (if any) before you submit.
  • No credit for Anagram.cpp if you do not use the templated doubly-linked List class defined in parts 1-4 of this Lab to complete the Anagram.cpp program by storing each word in a List of chars and manipulating the word using the List operations you wrote.
  • Please include a block comment with your name on the top of EACH file like so:

/**

* FirstName LastName

* CIS 22C, Lab 2

*/

  • 60% of the credit will be for submitting a complete and functional templated, doubly-linked list, with your own test file
  • 40% of the credit will be for a fully functional Anagram.cpp as demonstrated using the examples above