CS 127, Data Structures: Final Project

Assigned on 11/7/01.
Design document due on Friday, 11/9/01 at the beginning of class.
Final submission due on Monday, 11/19/01, by 5 PM.

Overview

For this last project, you may choose one of the two options: writing a text editor, or a C++ style enforcer. More details of each follow below.

The final submission

In addition to submitting your project via hsp, you should submit the following items of documentation as well. They should be included in a single text file, and may be brief.

A description of your program and its features.
A description of your program's command-line syntax.
A description and justification of the main data structures your program uses.
A discussion of the current status of your program, what works and what doesn't, etc.

Grading criteria

Successful compilation. If your program doesn't compile, I won't grade it.
Correctness. Your program needs to do the job it's intended to do.
Design. I will look for well-considered choices of data structures, classes, and member functions, their return values, and their parameters. In the description of your project, you should explain your reasons for making the choices you made.
Style. I want to see good indentation, descriptive variable and function names, well-placed comments, consistent loop structure, and so on. Ideally, your code will be a pleasure to read.
Documentation. Your description of your project and the comments in your source code are important parts of your project. I want to be able to understand your project fairly well before diving into the code.
Performance. I will not run precise time tests, but I will frown on text editors that take 5 seconds to search for a word and C++ style enforcers that 10 minutes to process a short C++ program.

Project Option #1: Text Editor

Once upon a time, UNIX programmers used a text editor called "ed", which is a one-line-at-a-time editor. In response to a prompt, you issue commands that usually affect the current line (that is, the most recently printed line). So, for example, a typical session using ed on this file might look like this:

        knuth> edit final.txt
        [Editing "final.txt" 151 lines, 1884 characters]
        CS 127
        1> 1,3p
        CS 127
        Winter 1998
        Final Projects
        3> d
        Due: 5:00, Wednesday March 18
        3> a
        This is a new line typed by the user.
        The additions end with a period alone on a line.
        .
        5> s
        [Saved "final.txt" 152 lines, 1884 characters]
        5> q
        [Bye-bye]
        knuth>

Here, we have started editing the file "final.txt," asked to look at lines 1 through 3, deleted line 3 (making the old line 4 into the new line 3), added two new lines of text, saved the resulting file, and quit.

To get a better idea of how ed actually works, you can run it yourself in any UNIX window. Note that the example above is a bit different from the real edit. I have included the current line number in the edit prompt, enclosed all editor messages in square brackets, replaced the "w" ("write") command with the "s" ("save") command, and printed the first line as soon as the editing session began. If you want to make small modifications of this nature, do so, but document them well.

The core of this project will be to implement a small version of edit that includes the following commands:

        M,Np            Print lines M through N, inclusive.
        
        <return>        Print the next line.
        
        a               Add new text following the current line.
                        The new text will be ended by a period
                        alone on a line.
                        
        i               Insert new text before the current line.
                        The new text will be ended by a period
                        alone on a line.

        d               Delete the current line.
        
        /bleah  Print the next line on which the string "bleah"
                        occurs.
        
        w               Save the file.
        
        q               Quit

In addition to the core, you might add the ability to copy, cut, and paste lines, save to a new file, start editing a non-existent file (that is, create a new, empty file and start editing it), make global substitutions of one string for another, undo the previous operation, etc.

One of the biggest decisions you will need to make for this project is how to store and manipulate the text file you are editing. Ideally, your program should be able to handle an arbitrarily large file. Thus, if you shoot for the ideal, you won't be able to declare a fixed-size array in which you will store the entire file. Even if you do work with a fixed-size array, you'll need to make sure that your various operations take a reasonable amount of time (for example, finding the next occurrence of a string should take less than a second to keep your user from getting cranky).

Project Option #2: C++ Style Enforcer

For this option, you will write a program that takes a C++ source file as input, and fixes its style. For example, if the input source looks like this:

#include <iostream>

int main(){
int i;
for(i=0;i<10;i++) cout << "Hello\n";}

the output might look like this:

#include <iostream>

int main()
{
    int i;

    for( i=0; i < 10; i++ )
        cout << "Hello\n";
}

The most important style points you should concentrate on are indentation and placement of braces.

Once you have indentation and bracing working well, some other style elements you could work on include spacing within for, while, and if statements, spacing in parameter lists in function headers and function calls, consistent spacing in assignment and arithmetic statements, blank lines placed after local variable declarations, etc.

If you have time and inclination, you could have your program offer the user multiple styles. For example, the bracing convention some books use:

    if( this == that )
    {
        dosomething();
    }

is different from the one I use: