Project 2 - A Deque-based Text Editor

Due - 11AM Tuesday, November 22, 2005

The goal of this project is to give you an opportunity to practice implementing linked lists, stacks, and queues as well as practice using object-oriented design and recursion. Your program should be implemented in C++ and should use classes where appropriate. Points will be deducted for poor design.

For this project, you will implement a text editor. Your editor will display a string of characters and a cursor. Your program will allow the user to move the cursor and modify the text using the following five operations:

left - move the cursor to the left one character or do nothing if at the end of the line
right - move the cursor to the right one character or do nothing if at the end of the line
rdelete n - delete n characters to the right of the cursor
ldelete n - delete n characters to the left of the cursor
insert c - insert the character c just before the cursor

A program that implements the preceding five operations will receive a maximum of 85% credit. For full credit, your program must also implement the following two operations:

findLeft s - recursively determine if the substring s is contained in the left part of the list
findRight s - recursively determine if the substring s is contained in the right part of the list

Your recursive operation should determine if the first character of the search string matches the current character of the target string. If so, recursively determine if there is a match of the search string without the first character.

A sample run of your program should look as follows:
^ insert S S^ insert A SA^ insert M SAM^ insert M SAMM^ findLeft AM true insert Y SAMMY^ left SAMM^Y findRight AT false left SAM^MY rdelete 2 SAM^ insert I SAMI^ right SAMI^ left SAM^I ldelete 3 ^I
Your program should implement a Deque class using a doubly-linked list. Your Deque should provide functions to insert and remove from both ends of the deque. You should declare two instances of this class. The first will store all of the text to the left of the cursor and the second will store all of the text to the right of the cursor. In addition to the typical Deque ADT operations you must implement : (1) a print function for the Deque which will print its contents and (2) a removeFirst(i) function and a removeLast(i) function which will remove the top i (an integer) elements from the Deque. Think carefully about what this special remove function should return.

Extra Credit Opportunity

For extra credit, implement a find operation that will determine if a substring exists anywhere in the given text. In other words, the desired string may cross the boundary between the left and right of the string.

Due 11AM Tuesday, November 22, 2005

Complete and submit your working code.
Make sure that each function is well documented. Your documentation should specify the type and function of the input parameters and output.
Run your program on a variety of inputs ensuring that all error conditions are handled correctly.

Note: No portion of your code may be copied from any other source including another text book, a web page, or another student (current or former). You must provide citations for any sources you have used in designing and implementing your program.

Sami Rollins