Goal

The purpose of the second programming assignment is to experience stacks, queues, and new data structures. The data structure for this assignment is a doubly linked list.

Problem Statement

Have you wondered how the editors do undo and redo actions? In this assignment you are going to design and implement a data structure that helps solving the undo and redo problem. In order to be able to undo or redo some editing commands, you need to keep track of the command history. We are going to use a deque for that. Deque is sometimes called double$-$ended queue. You can add and remove from both ends.$$

Programming

Part I: The Deque ADT

The deque will represent the command history for our assignment.$$

The command should include:

sequence number of the command, e$.$g$.1,2,..,$ and they should not change throughout the program

command description, e$.$g$.$ copy line $3-6$

The deque should be implemented using a doubly linked list of commands, where the front pointer points to the command that will be used for redo and the rear pointer points to the most recent command. You must implement

addToEnd

removeFromEnd

addToFront

removeFromFront

peekEnd

peekFront

display

Part II: The Driver or the Test Program

The test program needs to first load the test data set from external file at the beginning of the program. The menu$-$based user interface should allow user to do the following:

Show the entire command history

Undo a certain number of commands

Redo a certain number of commands $($the opposite of undo$)$

Here is an example of undoing and redoing and it should give you hint about how to implement the undo$/$redo operations:

After loading from file, the command history:

copy line $3-6$

paste line $3-6$ after line $10$

remove line $20-30$

remove the first $3$ words of line $1$

join line $20$ and $30$

replace all occurrences of "num" to "number"

comment out line $4-5$

indent line $12-15$

unindent line $5-8$

uncomment line $9-11$

After undo $3$ commands, the command history:

$8.$ indent line $12-15$

$9.$ unindent line $5-8$

$10.$ uncomment line $9-11$

copy line $3-6$

paste line $3-6$ after line $10$

remove line $20-30$

remove the first $3$ words of line $1$

join line $20$ and $30$

replace all occurrences of "num" to "number"

comment out line $4-5$

After redo $2$ commands, the command history:

$$

$10.$ uncomment line $9-11$

copy line $3-6$

paste line $3-6$ after line $10$

remove line $20-30$

remove the first $3$ words of line $1$

join line $20$ and $30$

replace all occurrences of "num" to "number"

comment out line $4-5$

indent line $12-15$

unindent line $5-8$

Things you should know...as part of your program

Do not use statically allocated arrays in your classes or structures used by the ADT.$$

All data members in a class must be private

Never perform input operations from your data structure class in CS$260$

Global variables are not allowed in CS$260$

Do not use the String class! $($use arrays of characters instead!$)$ You may use the cstring library.$$

Use modular design, separating the $.$h files from the $.$cpp files. Remember, $.$h files should contain the class header and any necessary prototypes. The $.$cpp files should contain function definitions. Never $"$#include" $.$cpp files!