Lab 2 (100 pts) 
Due Tuesday, January 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 insertFirst(listdata data); //this function now takes in generic data

    listdata getFirst(); //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. For example:
        For EACH of these functions, you will need to template them and change the type of data that they return and take in so that it is generic.
  • Here is an example of how to alter one of these functions:

template <class listdata> //Step 1: template the function
void List<listdata>::insertFirst(listdata data) //step 2 & 3: List is templated and takes in a generic param
{
    if (length == 0)
    {
        first = last = new Node(data);

    }
    else
    {
        Node* N = new Node(data);
        N->next = first;
        first = 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> L; //indicate the list holds ints
    L.insertFirst(5);

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

    L2.insertFirst("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
  • Your 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* prev;

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

  • Additionally, bear in mind that the first Node of the list now has a prev Node pointer to NULL while the last Node has a next Node pointer to NULL.
  • The advantage of the prev 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>::insertFirst(listdata data)
{

    if (length == 0)
    {
        Node* N = new Node(data);
        first = last = N;
    }
    else
    {
        Node* N = new Node(data);
        N->next = first;
        first->prev = N; //Need to update the prev pointer of first to point back at the new node
        first = N;
    }

    length++;

}

  • Important! Each time you update one of your functions, run your tests again to make sure your list is still working properly.
  • If you want more information on doubly-linked lists, you can watch this short video (4.5 min).


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.
  • 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:

removeFirst: removes the element at the beginning of the list   
removeLast:
removes the element at the end of the list

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

insertLast:
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
advanceIterator: moves the iterator up by one node
reverseIterator: moves the iterator down by one node

Access Functions:

getFirst: returns the first element
getLast:
returns the last element

isEmpty: tests whether the linked list is empty
getLength: returns the current length 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 two lists to see if they are equal.


Additional Operations:

printList: prints the contents of the linked list to the screen separated by a blank space
printNumberedList: prints the contents of the linked list to the screen in the format #. <element> followed by a newline


Part 4: Poem Rearranger
  • Create a file called Poem.cpp, which reads in the contents of a file and allows the user to manipulate the poem by rearranging the order of the lines.
  • The user should have the option to move lines of the poem up and down to create a new poem.
  • The program should welcome the user and prompt the user for the name of a file
  • If this file cannot be found, the program should use a loop to re-prompt the user for a valid file name.
  • It should then read in the file and report the the title and author of the poem and the number of lines.
  • Using a loop, the program should then prompt the user for the line number to be rearranged, whether the line should be shifted up or down and then how many lines up or down it should be moved.
  • The program will report the line that was selected or print "The line is blank" if the user selects a blank line.
  • Each time a line is moved, the new version of the poem should be displayed.
  • The poem should accept both upper and lower case versions of the user responses.
  • Poem.cpp should give identical output to the output below (given the same user input):

Example 1:

Welcome to the poetry re-arranger!

Enter the name of a file containing a poem: poem.txt
Please enter a valid file name: poem1t.xt
Please enter a valid file name: poem1.txt

There are 14 lines in your poem
The poem is:
“Hope” is the thing with feathers By Emily Dickinson

1. “Hope” is the thing with feathers -
2. That perches in the soul -
3. And sings the tune without the words -
4. And never stops - at all -
5.
6. And sweetest - in the Gale - is heard -
7. And sore must be the storm -
8. That could abash the little Bird
9. That kept so many warm -
10.
11. I’ve heard it in the chillest land -
12. And on the strangest Sea -
13. Yet - never - in Extremity,
14. It asked a crumb - of me.


How would you like to re-arrange this poem?

Enter the line number of the poem: 7
The line is: And sore must be the storm -

Do you want to move this line up or down: Up
How many lines do you want to move it: 3
The new poem is:
1. “Hope” is the thing with feathers -
2. That perches in the soul -
3. And sings the tune without the words -
4. And sore must be the storm -
5. And never stops - at all -
6.
7. And sweetest - in the Gale - is heard -
8. That could abash the little Bird
9. That kept so many warm -
10.
11. I’ve heard it in the chillest land -
12. And on the strangest Sea -
13. Yet - never - in Extremity,
14. It asked a crumb - of me.

Would you like to rearrange this poem further: yes

How would you like to re-arrange this poem?

Enter the line number of the poem: 6
The line is blank

Do you want to move this line up or down: down
How many lines do you want to move it: 6
The new poem is:
1. “Hope” is the thing with feathers -
2. That perches in the soul -
3. And sings the tune without the words -
4. And sore must be the storm -
5. And never stops - at all -
6. And sweetest - in the Gale - is heard -
7. That could abash the little Bird
8. That kept so many warm -
9.
10. I’ve heard it in the chillest land -
11. And on the strangest Sea -
12.
13. Yet - never - in Extremity,
14. It asked a crumb - of me.

Would you like to rearrange this poem further: Yes

How would you like to re-arrange this poem?

Enter the line number of the poem: 8
The line is: That kept so many warm -

Do you want to move this line up or down: Down
How many lines do you want to move it: 3
The new poem is:
1. “Hope” is the thing with feathers -
2. That perches in the soul -
3. And sings the tune without the words -
4. And sore must be the storm -
5. And never stops - at all -
6. And sweetest - in the Gale - is heard -
7. That could abash the little Bird
8.
9. I’ve heard it in the chillest land -
10. And on the strangest Sea -
11. That kept so many warm -
12.
13. Yet - never - in Extremity,
14. It asked a crumb - of me.

Would you like to rearrange this poem further: No
Goodbye!

Example 2:

Welcome to the poetry re-arranger!

Enter the name of a file containing a poem: poem2.txt

There are 27 lines in your poem
The poem is:
I Wandered Lonely as a Cloud By William Wordsworth

1. I wandered lonely as a cloud
2. That floats on high o'er vales and hills,
3. When all at once I saw a crowd,
4. A host, of golden daffodils;
5. Beside the lake, beneath the trees,
6. Fluttering and dancing in the breeze.
7.
8. Continuous as the stars that shine
9. And twinkle on the milky way,
10. They stretched in never-ending line
11. Along the margin of a bay:
12. Ten thousand saw I at a glance,
13. Tossing their heads in sprightly dance.
14.
15. The waves beside them danced; but they
16. Out-did the sparkling waves in glee:
17. A poet could not but be gay,
18. In such a jocund company:
19. I gazed—and gazed—but little thought
20. What wealth the show to me had brought:
21.
22. For oft, when on my couch I lie
23. In vacant or in pensive mood,
24. They flash upon that inward eye
25. Which is the bliss of solitude;
26. And then my heart with pleasure fills,
27. And dances with the daffodils.


How would you like to re-arrange this poem?

Enter the line number of the poem: 6
The line is: Fluttering and dancing in the breeze.

Do you want to move this line up or down: Up
How many lines do you want to move it: 5
The new poem is:
1. Fluttering and dancing in the breeze.
2. I wandered lonely as a cloud
3. That floats on high o'er vales and hills,
4. When all at once I saw a crowd,
5. A host, of golden daffodils;
6. Beside the lake, beneath the trees,
7.
8. Continuous as the stars that shine
9. And twinkle on the milky way,
10. They stretched in never-ending line
11. Along the margin of a bay:
12. Ten thousand saw I at a glance,
13. Tossing their heads in sprightly dance.
14.
15. The waves beside them danced; but they
16. Out-did the sparkling waves in glee:
17. A poet could not but be gay,
18. In such a jocund company:
19. I gazed—and gazed—but little thought
20. What wealth the show to me had brought:
21.
22. For oft, when on my couch I lie
23. In vacant or in pensive mood,
24. They flash upon that inward eye
25. Which is the bliss of solitude;
26. And then my heart with pleasure fills,
27. And dances with the daffodils.

Would you like to rearrange this poem further: no
Goodbye!


Hint:
  • Since the insertIterator function inserts data after the current node, it cannot insert data at the very front of the list.
  • Therefore, you will have to use an if statement to check for the case where the user wishes to insert a new first line of the poem, and then call insertFirst.
  • See example 2 above.

Input File
  • Note that it an be assumed that each input file is structured the same way:
 <title>
<Blank line>
<body>
<Blank line>
By <author>
  • Below is an input file named poem1.txt which can be used with the first example above:

“Hope” is the thing with feathers

“Hope” is the thing with feathers -
That perches in the soul -
And sings the tune without the words -
And never stops - at all -

And sweetest - in the Gale - is heard -
And sore must be the storm -
That could abash the little Bird
That kept so many warm -

I’ve heard it in the chillest land -
And on the strangest Sea -
Yet - never - in Extremity,
It asked a crumb - of me.

By Emily Dickinson

  • To insert this file into your Eclipse project, right-click on the project folder, and then go to File->File. Note that the file will be placed in the main folder. It should not be placed under src or your program will not be able to find this file.
  • Below is another file named poem2.txt which can be used with the second example above:
I Wandered Lonely as a Cloud

I wandered lonely as a cloud
That floats on high o'er vales and hills,
When all at once I saw a crowd,
A host, of golden daffodils;
Beside the lake, beneath the trees,
Fluttering and dancing in the breeze.

Continuous as the stars that shine
And twinkle on the milky way,
They stretched in never-ending line
Along the margin of a bay:
Ten thousand saw I at a glance,
Tossing their heads in sprightly dance.

The waves beside them danced; but they
Out-did the sparkling waves in glee:
A poet could not but be gay,
In such a jocund company:
I gazed—and gazed—but little thought
What wealth the show to me had brought:

For oft, when on my couch I lie
In vacant or in pensive mood,
They flash upon that inward eye
Which is the bliss of solitude;
And then my heart with pleasure fills,
And dances with the daffodils.

By William Wordsworth

Specifications for Submission
  • Please submit 3 files to Catalyst by Tuesday at 11:20am:
  1. List.h (header file as created in class - now with ALL of your full function definitions)
  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. Poem.cpp (source file with all of the logic to process poems as shown above)
  • Important: You must name your files exactly as described above -- List.h, ListTest.cpp and Poem.cpp -- for full credit
  • 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 List 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.
  • Please include a block comment with your name on the top of EACH file like so:

/**

* FirstName LastName

* CIS 22C, Lab 2

*/

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