Version: 2.1, Feb. 24, 1998.
Maintained by: Darrah Chavey.
Changes from Previous Versions: Changes from v. 2.0. Changes from v. 1.0.
Non-standard Terminology: Applet, Beloit, dereference, int, IntNode, StringNode, prev, rescale, resizable, resized, reinitialization, Drexel.
Document purpose: This document is an overview of the product that we hope to construct, tentatively referred to as "C Pointers". It describes the goal of the product in a format that we hope is readable to an average client, e.g. a student taking a C++ Data Structures course. It deliberately does not include all of the details of the program, for which you should see the Specifications document, nor does it give instructions on how to actually use the product, for which you should see the User Documentation (sorry link not available).
The program "C Pointers" is intended to aid students in understanding pointers in C and C++, how they work, how to program with them, and the common types of errors that can arise. It provides a graphical representation of lists, doubly-linked lists, and binary trees. Students can execute basic pointer commands and see visually the effect of their commands. The program will store a sequence of commands that they have executed and allow that sequence to be output, e.g. for grading purposes or for inclusion in a program. In many cases, students can visually execute code that they expect to accomplish some purpose, and visually test whether it has that effect, and where it fails if it does not have the desired effect.
A series of "lessons" is available to progressively test the students' understanding of pointer concepts and manipulation, and facilities are available for constructing additional lessons.
In many cases, the program "Pascal Pointers", by Drexel University, will be used as a model of the style of program we are trying to produce, although we expect to support several features beyond what is supported by that program.
In the description below, we use the Ý symbol to indicate a feature that we would like to see implemented, but that we are willing to drop if it seems to be too difficult to implement, or if implementing it would interfere excessively with the final product release. Such items might then become feature enhancements for future versions of the product.
1.1: The product supports a singly linked list node, appearing roughly like the drawing on the right. This node will support a "data" field that can be either a number in the range 0 to 999, or else a string of up to 3 characters.
Ý1.2: The product should support doubly linked list nodes and tree nodes, appearing like: and
1.3: Only one type of node shall be supported on the screen at one time. This means only one of the three node types above, and either numeric data or else string data can be used at once. There will be reasonable facility for the user to choose which type of node they wish to work with.
1.4: There will be room in the node itself to store either a 3 digit number or a 3 character string at a standard 12 point font. The rest of the node will be grayed out, as indicated in the diagram with §1.1.
Ý1.5: The screen should check the current font size and rescale the nodes when necessary to optimally store the 3 character data fields. This is intended both to allow a teacher to increase the font size while demonstrating the program (e.g. with a projector) and to allow a user to decrease the font size and still fit a reasonable number of nodes on a smaller monitor.
2.1: Links will consist of arrows similar to those shown in section 1. In particular, the arrowheads are heavier than those in Pascal Pointers.
2.2: For purposes of user input, link fields will be named "next" for linked lists, "next" and "prev" for doubly linked lists, and "left" and "right" for binary trees.
2.3: For node types with more than one type of link (doubly linked lists and trees), coloring of the links will be used to distinguish the types of links, i.e. as indicated in the pictures above.
2.4: Uninitialized pointers will be indicated by grayed boxes with no arrow, as shown on the left. Nil pointers will be indicated by white boxes with a diagonal line crossing through the box, as indicated on the right.
3.1: Four labeled pointer boxes, which start uninitialized, not contained within nodes, will appear on the left of the screen. They will be labeled as p, q, r, and s, and the user manipulates them using those names. The format here is similar to that of Pascal Pointers, as shown in the figure below.
3.2: Nodes will all appear within a grid on the screen, separated by "rivers" of open space that are reserved for use by the links. There will be space for eight "rows" of nodes, two each for the four initial pointers. As new nodes are constructed, they will be placed in reasonably logical locations within this grid, never overlapping of course. In particular, if the user creates a new node using the "next" pointer of an existing node, the new node shall be created immediately to the right of the existing node, if that space is available. The actual grid used will depend on which of the three types of nodes (linked, doubly linked, or tree) are being used, and will be customized for their sizes.
3.3: Links from one node to another will be drawn only in the "rivers" around the node locations shown above. Links may cross each other, but will be drawn so that they do not "merge" for any length of distance. In other words, a viewer can always determine which link goes to which other location. "In" pointers will touch the node at points distinct from where "Out" pointers leave the nodes, so that no confusion arises as to the meaning of a particular line as drawn. In a similar vein, two pointers going to distinct nodes shall never coincide with each other (although they may cross), since otherwise the user can't tell, when those pointer lines separate, which one is which. On the other hand, if two pointers are going to the same node, it is acceptable to have them merge into a single line, since no ambiguity arises in this case.
3.4: For singly linked lists, links will start from the center of the "link field" in the pointer field of the node. For doubly linked lists, links will start from the center of one half of that link field (top or bottom half). This leaves room for pointers pointing to this node to point to the center of the other half of that side of the node. In doubly linked lists, "next" links will always start from the top half of the link field and point to the top half of the left side of the node to which they point; "prev" links will always start from the bottom half of the link field and point to the bottom half of the right side of the node to which they point. For tree nodes, "left" and "right" links will always start from the center of their respective link fields and point to the left side of the nodes to which they point. The special pointers p, q, r, and s will always start from the center of their nodes and point to the left side of the node to which they point. Note that this allows the construction of a doubly linked lists that looks like:
3.5: Facilities will be available to enter basic C++ commands, including modest sized loops, through text entry.
4.1: The program will accept commands such as p->next = q->next->next, or p->next = NULL
4.2: The program will accept commands such as p->data = 327, or p->data = "bye", depending on which of these is currently acceptable. (Only one type of command is acceptable at any one time.)
4.3: The program will accept both new and delete commands. In particular, it will accept a command such as p->next = new IntNode, if the user is working with integer data, or else p->next = new StringNode if the user is working with string data.
Ý4.4: The program should accept template format commands, specifically either p = new Node<int> or else p = new Node<string>.
4.5: The program will expect semi-colons to end statements, and parentheses (as with normal C++) for boolean expressions controlling if's and loops.
4.6: The program will not support C style use of (*p) as a pointer dereference.
4.7: The program will accept normal uses of ==, !=, <, <=, >, >=, &&, ||, and ! in comparing items for controlling loops.
Ý4.8: The program should accept simple "if" conditionals.
Ý4.9: The sequence of commands that has been executed since the last "reinitialization" should be available as text output, and should also be able to be written to a file.
4.10: Basic syntax errors shall be caught, and comprehensible error messages provided.
4.11: As with Pascal Pointers, the student shall be able to either step through a loop, or to execute it all at once. The student shall be able to see the entire collection of statements in the loop when they are stepping through the loop.
5.1: If a node becomes inaccessible, i.e. there is no pointer pointing to it, the user shall be informed that they have created memory leakage, and failed at the problem they were trying to solve.
Ý5.2: If a pointer becomes dangling, i.e. pointing to a node that has been disposed of, it should be assumed that the user will immediately set all necessary pointers to NULL. Thus if p and q point to the same thing, and the user executes "delete p", then the program should accept the commands "p = NULL" and "q = NULL", but any other command executed before that happens should result in the user being told that they have created a dangling pointer, and failed at the problem they were trying to solve.
5.3: It is desirable that the user have the option to "Undo" the previously executed command. There are no facilities for multiple "Undo" commands or for "Redo" commands.
6.1: The user shall be able to read lessons and create lessons similar to those used by Pascal Pointers. The instructions for the lesson shall appear in an html document which contains the Java Applet for the C Pointer program, so that the instructions remain visible throughout the use of the lesson.
Ý6.2: There should be a facility to ask the program to check whether a proposed solution to a lesson is correct. This checking should compare whether the proposed solution is logically equivalent to the established answer. For example, the exact screen location of nodes is irrelevant; only the pointer connections between them, and the node contents, are significant. A proposed answer is viewed as correct if every node that you can get to from p, q, r, or s in the official answer has the same contents and same logical connections as the node that would be reached along that path in the proposed solution, including the existence of null pointers. For example, if p->next->prev == NULL in the official answer, then the proposed answer must have the same chain of pointers from its p, having the same values for p->data, p->next->data, and with a NULL pointer for its version of p->next->prev. The one exception is that if the official answer has a null (or uninitialized) pointer value for some of the elements p, q, r, or s, and the proffered solution has some links from those values (most likely temporary pointers), the solution is still viewed as correct.
7.1: There are no facilities to allow the user to move nodes around on the screen or to "clean up" a linked list, for example. Once a node is placed, it remains in that location unless it is deleted.
Ý7.2: The screen should be resizable, and if the screen is resized to larger than is necessary to hold the standard array of nodes, then it should be possible to have more rows or columns of nodes.
8.1: User Manual: A user manual written for the expected C++ novice audience will be provided with the product. Features of interest only to an experienced C++ programmer, e.g. the creation of lesson plans by instructors, will be included, but relegated to sections specifically labeled for them.
8.2: Online Manual: An online (html) version of the manual will also be available.
8.3: Online Help: Online help, such as the succinct overview of commands that is provided in Pascal Pointers, will be made available. As with lessons, the user can choose to have this appear on-screen simultaneously with the Java Applet.
9.1: The programs and accompanying documentation developed are copyright by Beloit College, who maintain all rights to this software. The software can be used free of charge by academic institutions, as long as the program and documentation remain unmodified (portions may be added to, but not deleted from, the user documentation). Commercial use of the software requires licensing from Beloit College.