CS 127 Final Project, Winter 1996

What to hand in

• By Friday, March 8, hand in via email to jondich a brief description of your choice of project, the main data structures you intend to use, and your main() and prototypes of the functions called by main().
• By noon Friday, March 15, submitted using HSP
  1. Prose description. This should describe and justify your choice of data structures, and explain what your program does. You should also discuss the status of the program: if it still has trouble doing certain things, tell me about that here.
  2. Manual pages. You should include a manual page, modelled on the UNIX man pages, for your program as a UNIX command.
  3. The code.

Grading Criteria

• Design. I will look for well-considered choices of data structures and 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 manual page(s), your description of your project, and the comments in your source code are all 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 spelling checkers that take an hour to check a two page document or editors that take three seconds to find the next occurrence of the word "blue" in the file being edited.
• Extras. Each of the projects described below consists of a core of essential functions, and a list of possible extensions of that core. An A program will implement the core plus two or three extensions, with good design, style, documentation, and performance. A C program will have a core that mostly does what it is supposed to do, in addition to some documentation.

Project Option #1: Text Editor

These editors are, essentially, one-line-at-a-time editors. 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 edit on this file might look like this:

	knuth> edit final.txt
	[Editing "final.txt" 151 lines, 1884 characters]
	CS 127
	1> 1,3
	CS 127
	Winter 1995
	Final Projects
	3> d
	Due: noon, Friday March 15
	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 edit actually works, you can run it yourself in any Unix window. Note that my 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,N		Print lines M through N, inclusive.
	
		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.
	
	s		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: Small HTML Interpreter

For this project, you will write a program to interpret a subset of HTML, the Hyper-Text Markup Language in which most Web documents are written. Your program will not communicate with HTTP servers, and so will not really be a browser, but your users will be able to follow links to local files.

Your program should take a single command-line argument, which will be the name of the HTML file the user wants to view. Your program will print the entire formatted file on the screen, and then present the user with a prompt. If the file contains links (using the "<a>" tag), the links will be numbered, and the user will be able to enter a link number at the prompt, at which point the requested file will be opened and displayed, and the prompt will return.

For example, if the file specified by the user contains this:

<h1>Works of Art</h1>
	
From "Computer Programming as an Art," 1974, by Donald Knuth.
See Knuth's "Literate Programming," 1992, Center for the Study of
Language and Information, pp. 7-8.  For a bibliography of
Knuth's work, click <a href="knuthbib.html">here</a>.
<p> <hr> <p>
"When I speak about computer programming as an art, I am
thinking primarily of it as an art form, in an
aesthetic sense.  The chief goal of my work as
educator and author is to help people
learn how to write beautiful programs...
<p>
"My feeling is that when we prepare
a program, the experience can be just like composing poetry
or music; as Andrei Ershov has said, programming can
give us both intellectual
and emotional satisfaction, because
it is a real achievement to master complexity and to establish
a system of consistent rules...
<p>
"Some programs are elegant, some are exquisite, some are
sparkling.  My claim is
that it is possible to write
grand programs, noble programs, truly magnificent ones!"

your program might print this:

                           WORKS OF ART
                               
From "Computer Programming as an Art," 1974, by Donald Knuth. See
Knuth's "Literate Programming," 1992, Center for the Study of Language
and Information, pp. 7-8.  For a bibliography of Knuth's work, click
here[1]. 

  ------------------------------------------------------------
 
"When I speak about computer programming as an art, I am thinking
primarily of it as an art form, in an aesthetic sense.  The chief goal
of my work as educator and author is to help people learn how to write
beautiful programs...

"My feeling is that when we prepare a program, the experience can be
just like composing poetry or music; as Andrei Ershov has said,
programming can give us both intellectual and emotional satisfaction,
because it is a real achievement to master complexity and to establish
a system of consistent rules...

"Some programs are elegant, some are exquisite, some are sparkling.  My
claim is that it is possible to write grand programs, noble programs,
truly magnificent ones!"

Enter Command:

If the user were now to enter a 1 at the prompt, your program would open the file "knuthbib.html" and display it in this same manner.

This example above includes a major heading (<h1>), a horizontal rule (<hr>), several paragraphs (<p>), and a link (<a>). It also requires that jagged lines of text be assembled into nicely justified paragraphs. Though you may choose to display some details differently than I have here, this example should give you an idea of what I'm looking for.

For an introduction to HTML, please see NCSA's Beginner's Guide to HTML and Michael Grobe's HTML Quick Reference Guide. The tags I will ask you to implement are relatively simple ones. If you have HTML questions, please ask me. Also, you can write your own test HTML files and see how lynx handles the various tags.

The core of your program should be able to process the following HTML tags:

• <h1>, <h2>,..., <h6> These tags give 6 different types of headings, ranging from the big and important (<h1>) to the small and barely noticeable (<h6>). I recommend capitalizing and centering text for a <h1> header, capitalizing and left-justifying a <h2> header, and left-justifying the rest.
• <p> This tag requires no closing tag (</p>). When you encounter this tag, start a new paragraph. Typical ways of displaying a new paragraph include inserting a blank line, or just starting a new line with a few spaces of indentation.
• <br> This tag requires no closing tag (</br>). This causes a line break. That is, you just start a new line immediately after this tag.
• <hr> This tag requires no closing tag (</hr>). This tag causes a line break, and then draws a horizontal rule (line) across the screen.
• <a href="filename"> text </a> The "text" here should be accompanied by an indication that "text" is hyper-text, and that selection of "text" (by typing the corresponding link number at the prompt) will cause your program to load the given file.
• <pre>, </pre> Any text between these two tags should be displayed character for character--that is, not formatted at all.

Your program should ignore tags it doesn't know about.

Once you have the core done, if you want to extend it, you may extend it to any real HTML tags. I recommend the ordered and unordered lists (<ol> and <ul>, with <li>), not including nested lists (lists within lists). You could also try Netscape tables (<table>, <th>, <tr>, and <td>), but that's a much harder job.