CS 305 -- Software Engineering

Specifications

Version: 2.0, April 20, 1998

Maintained by: John C. Duggins

Other Members of Specifications Team: Joe Squire and Dave Sager

Non-standard Terminology: int, prev, dereferencing, Misc, beloit, 0xFF0000, 0x0000FF, 0xFF00FF, bitwise, Ptr, intNode, stringNode, cs, edu, quickstart, typeable, resizeable, 0xFFFFFF.

Document purpose: This document specifies the process of the creation C++ Pointers. It outlines the general blueprint. This document shall be used as a basis for the User Documentation, the Architectural Design, and User Interface.

0. Overview:

The program called C++ pointers is intended to help teach students how to use pointers in C++. Specifically, this program helps teach about creation of pointers, reassignment of pointers, use of linked lists and doubly linked lists, use of binary trees and deletion of pointers. C++ Pointers shall also give users a forum to test and debug actual C++ code.

A graphical interface is specified for the use of visually informative pictures in which to demonstrate these operations. A command line interface is specified such that the user is forced to learn proper C++ syntax. Some lessons are provided but new ones can be created using the lesson editor.

Apart from the use of lessons, instructors can use this program as a demonstration tool during classroom activities.

1. Nodes:

Figure 1

1.1: Two types of data fields are allowed, integer and string. If the node's data field is an integer field, the data shall range from between 0 to 999. If the node's data field is a string field, the data shall range from between zero and three characters.

1.1.1: If the data field is an "integer" field, then the numbers shall appear as standard decimal numbers, e.g. 1, 42 or 420. The numbers shall not appear as 001 or 042.

Ý1.2: The program shall support singly linked, doubly linked, and binary tree nodes. The appearance of these nodes are as follows, respectively:

Figures 2, 3 and 4

For colors of the node boxes, see section 1.7.

For colors of the data fields, see section 1.6.

For colors of the pointer boxes, see section 1.8.

For colors of the links, see sections 2.3 and 2.4.

1.3: Only one type of node shall exist on the screen at one time. Either all of the nodes shall be "integer" nodes or all shall be "string" nodes. Either all of the nodes shall be "tree" nodes, all shall be "singly linked" nodes or all shall be "doubly linked" nodes.

Ý1.4: The user shall have the ability to change the font size as allowed by the browser used. The program shall support a maximum character size of 18 point while the minimum of 10 point.

1.5: The dimensions of the node are as follows:

Figure 5

Figure 6

1.6: Data fields

1.6.1: New nodes shall have the data field completely "grayed out". These colors shall follow the HTML Safe Color format. The desired color is 0x909090 (Light Gray). See figures 9 and 10 in section 1.8.

1.6.2: Initialized data fields shall appear as the appear as below:

Figure 7

1.6.3: The placement of the data field in the node box shall be:

Figure 8

1.7: The node box shall be "grayed out" when the node is first created. The color used shall be 0x333333 (Dark Gray) in HTML code. See figures 9 and 10 below in section 1.8 for visualization.

1.8: Pointer Box

1.8.1: Null pointers shall be white boxes with a single diagonal line running from the top left to the lower right of the pointer box. See figure 9 below for better visualization.

Figure 9

1.8.2: Uninitialized pointer boxes shall be drawn as follows:

Figure 10

1.8.3: The pointer box shall have a color the same as the uninitialized data field, 0x909090 (Light Gray).

1.9: The nodes shall resize themselves to best fit the contents of the data field.

2. Links:

2.1: Link Appearance

2.1.1: A link shall consist of a sequence of horizontal and vertical line segments beginning with a filled circle of radius two pixels and ending in an arrowhead from an initial pointer box to its destination node. The width of the line segments shall be 1 pixel.

2.1.2: The filled circle at the base of the link shall be the same color as the rest of the link.

2.1.3: Arrowheads of the links shall be completely filled in with the color of the link. Arrowheads shall look as follows:

Figure 11

2.1.4: Links shall not be resizeable.

2.2: All links used with singly linked lists shall be referred to as "next". Two types of links shall be used with doubly linked lists, "prev" for links leaving the right pointer box and "next" for links leaving the left pointer box. Two types of links shall be used with binary trees, "right" for links leaving the right pointer box and "left" for links leaving the left pointer box.

2.2.1: All incoming links from singly linked nodes and binary tree nodes shall point to that destination node's left side, 50% down from the top-left corner of the node box. Also, all links leaving a pointer box shall originate in the horizontal and vertical center of that box, 50% up and 50% right of the bottom-right corner of the pointer box.

Figure 12

2.2.2: All incoming "prev" links shall contact the node's right side at 25% above the bottom-right corner of the destination's pointer box. Also, all incoming "next" pointers shall contact the node's left side at 25% below the top-left corner of the pointer box. All of the outgoing "prev" links shall originate 25% up from the bottom and 50% within the pointer box. All of the outgoing "next" shall originate 25% down from the top and 50% within the pointer box.

Figure 13

2.3: Links for singly linked nodes shall be the color 0x000000 (Black) in HTML code. The "next" link for doubly linked nodes and the "right" link for tree nodes shall be the color 0xFF0000 (Red) in HTML code. The "prev" link for doubly linked nodes and the "left" link for tree nodes shall be the color 0x0000FF (Blue). These colors can be seen in figures 12 and 13 above.

2.4: Links that terminate at the same node shall merge into one link. If the links are the same color, the new link shall be the same color. If the two links are different colors, i.e. 0xFF0000 and 0x0000FF, the color of the merged link is 0xFF00FF (Purple). See figure 14 for representation.

Figure 14

2.5: Links shall only be allowed to cross each other for 1 pixel.

3. Screen Layout and Appearance:

3.1: The four initial pointers shall lie on the left side of the program screen beginning as uninitialized pointers. The names and labels of these pointers are, respectively, p, q, r, and s. The label shall be separated from the pointer box by 5 pixels. The label shall be centered vertically with respect to the pointer box.

Figure 15

3.2: The program shall support eight rows of six nodes per row; therefore, the program shall be able to handle 48 nodes, no more. See figure 16 for better visualization.

3.3: The initial pointer boxes shall be placed such that: pointer box "p" shall be placed vertically centered in respect to the first node row, pointer box "q" shall be placed vertically centered in respect to the third node row, pointer box "r" shall be placed vertically centered in respect to the fifth node row, pointer box "s" shall be placed vertically centered in respect to the seventh node row.

3.4: Created nodes shall be sequentially placed left to right and top to bottom. The placement point shall be the next available spot in sequential order in respect to its head pointer. For instance, if the following code were entered

p->next = new intNode;

while p->next is the only other node, the new intNode shall be placed in slot 2. Also, if p were currently pointed to node 48 and the same command was issued, the new intNode would be placed in slot 1, if available. The figure below depicts the sequence in which the nodes shall be placed.

Figure 16

 

3.5: Spaces between any created nodes shall be for links. This document shall refer to this space as "rivers" henceforth. Only twelve links per river shall be allowed. If the river is "filled", i.e. it contains twelve links, another path shall be found. A space of five pixels shall exist between a node box and the link river. The river's width shall be 23 pixels.

3.5.1: Links shall be laid out as follows:

3.6: The program's background shall be 0xFFFFFF (White) in HTML code.

3.7: A key of all symbols and colors shall be available to the user at all times. See the User Interface documentation for more details.

4. Input:

4.1: The text input field shall only accept ANSI C++ compliant code. For example, to assign the next pointer of p to NULL, the user shall type:

p->next = NULL;

4.2: Data fields can be named and changed by using the following syntax: for an int data field, p->data = 327; and for string data, p->data = "bye";.

4.3: The program shall support dynamically allocating memory for new nodes and deleting these nodes using C++ new and delete.

p = new intNode;

delete r->next;

Ý4.4: The program shall accept template format commands such as p = new Node<int>;.

4.5: The program shall not support the use of C style pointer dereferencing, e.g. (*p).

4.6: The program shall support all normal conditional comparisons (>, <, ==, !=, <=, >=, !, &&, || ). The program gives no support for bitwise comparisons.

4.7: Error checking and handling shall be discussed in Section 5.

Ý4.8: Loop control shall be discussed in Section 12.

4.9: The following table lists in Backus-Naur form all of the available commands in the text input field. It gives the syntax of these commands also.

<Statement> ::= if ( <Boolean Condition> ) <Simple Statement>
<Statement> ::= if ( <Boolean Condition> ) <Simple Statement> else <Simple Statement>
<Statement> ::= <Simple Statement>
<Simple Statement> ::= <Data Field> = <Data Value>;
<Simple Statement> ::= <Pointer Field> = <Pointer Value>;
<Simple Statement> ::= delete <Pointer Field>;
<Data Value> ::= <Data Field> OR <integer value> or <string value>
<Pointer Value> ::= <Pointer Field> OR NULL OR new <Node value>
<Node Value> ::= IntNode OR StringNode OR Node<int> OR Node<string>
<Data Field> ::= <Pointer Field> data
<Pointer Field> ::= p OR q OR r OR s OR <Pointer Field> -> <Link Name>
<Link Name> ::= next OR prev OR left OR right
<Boolean Condition> ::= <Boolean Expression>
<Boolean Condition> ::= (<Boolean Expression>) && (<Boolean Expression>)
<Boolean Condition> ::= (<Boolean Expression>) ||(<Boolean Expression>)
<Boolean Expression> ::= !(<Boolean Expression>)
<Boolean Expression> ::= <Data Field> <Boolean Comparison> <Data Field>
<Boolean Expression> ::= <Pointer Field> == <Pointer Field>
<Boolean Expression> ::= <Pointer Field> != <Pointer Field>
<Boolean Comparison> ::= "==" OR "!=" OR ">" OR "<" OR ">=" OR "<="

5. Error Control:

5.1: There shall be two general categories for errors: runtime errors (also called semantic errors), and compile-time errors (also called syntax errors).

5.2: The program shall report the error along with a message describing the error to the user.

5.3: A runtime error is the result of statement execution. The statement shall not be executed if a runtime error occurs.

5.3.1: If a node becomes unreachable, error number R1 shall be reported.

5.3.2: If the user attempts to execute a command containing a pointer field of the form "p->next" when "p" is uninitialized, then the error number R2 shall be reported. If "p" were NULL, then the error number reported shall be R3.

5.3.3: If the user attempts to execute a statement of the form "delete(p->next)" when "p->next" is an uninitialized pointer, then the program shall report the error number R4; if "p->next" is NULL, then the program shall report the error number R5.

5.3.4: If the user attempts to assign the data field of an IntNode a value greater than 999, then the program shall report the error number R6; if the user attempts to assign the data field of an IntNode a value less than 0, then the program shall report the error number R7.

5.3.5: If the user attempts to assign the data field of a StringNode a string with more than three characters, then the program shall report the error number R8.

5.3.6: If the user attempts to allocate a new node and the maximum number of nodes has been allocated, then the program shall report the error number R9.

5.3.7: If the user tries to allocate a new node, but a new link to the node cannot be allocated, then the program shall report the error R10.

5.4: A compile-time error occurs when the compiler cannot properly parse a statement that the user has entered.

5.4.1: If a line does not end with a semicolon, except for flow control statements and braces (i.e., "if" and "while" statements, including "else" with the if-statement), then the program shall report the error number C1.

5.4.2: If the keyword "else" is found without a corresponding "if" statement, then the program shall report the error number C2.

5.4.3: If a close-parenthesis appears in a line before an open-parenthesis, or too many close-parentheses exist, or not enough close-parentheses exist, then the program shall report the error number C3; if angle brackets are unbalanced in a way similar to parentheses, then the program shall report the error number C4; if curly braces are unbalanced in a way similar to parentheses, then the program shall report the error number C5.

5.4.4: If there is an uneven quantity of quotation marks, then the program shall report the error number C6.

5.4.5: If the assignment operator appears in a flow control conditional expression instead of the equals comparison operator, then the program shall report the error number C7. (Note: this error can only occur in an "if" or "while" control expression).

5.4.6: If the user enters a Boolean expression or a Boolean conditional that is too complex (see Section 4.9 for details), then the program shall report the error number C8.

5.4.7: If the user enters a Boolean expression or a Boolean conditional that uses an unsupported operator except for the assignment operator (see Section 4.9 for details), then the program shall report the error number C8.

5.4.8: If the user enters an expression that contains an identifier that is unknown to the program (see Section 4.9 for defined identifiers), then the program shall report the error number C10.

5.4.9: If a statement is too complex (see Section 4.9 for acceptable statements), then the program shall report the error number C11.

5.4.10: If the user attempts to assign a number to a string node (i.e., "p->data = 42;" when a string was expected), then the program shall report the error number C12. (*Note: in the example shown above, p->data was attempting to take the value of 5. If the pointer field had attempted to take the value of "42", no error would occur.) If the user attempts to put a string in an IntNode, then the program shall report the error number C13.

5.4.11: If the user is working with string nodes but tries to allocate a new node using a statement of the form "p = new IntNode;", then the program shall report the error number C14; if the user is working with IntNodes but tries to allocate a new node using the StringNode type, then the program shall report the error number C15.

5.4.12: The program shall report an error number C16 if the user attempts to use a pointer field that is not available for that particular "LinkType", e.g. p->left in a singly linked list.

5.4.13: If the user attempts a statement of the form "p->next = 42", then the program shall report the error number C17; if the user attempts a statement of the form "p->next = "hi.", then the program shall report the error number C18; if the user attempts to execute a statement of the form "p->next = r->data", then the program shall report the error number C19; if the user attempts a statement of the form "r->data = p->next", then the program shall report the error number C20.

5.4.14: If the user attempts a statement of the form "if (p->next == r->data)...", then the program shall report the error number C21.

5.4.15: If an if-statement is nested in the "then" or "else" part of another if-statement, then the program shall report the error number C22.

5.4.16: If a miscellaneous parsing error occurs, then the program shall report the general error number C23.

5.5: In addition to all the other errors enumerated, some runtime errors are specific to loop control:

5.5.1: After every 500 iterations in the while loop, the program shall report the error number R11. An option to abort the loop or to continue execution shall be given to the user. The "Abort Loop" option will also undo the action of the loop.

5.5.2: After 10,000 iterations in the while loop, the program shall report the error number R12. The only option given to the user when this occurs is to abort and undo the loop.

5.6: If any error occurs, the statement will not be executed and the user must fix the statement or action that caused the error to occur.

6. Lessons:

6.1: During a lesson, the instructions for the lesson shall always be available to the user.

Ý6.2: The program shall support a feature for the user to check for correctness of an answer during a lesson. The lesson's answer shall be checked against the user's work to determine this correctness. Any extraneous nodes or links created by the user shall be ignored during this process; only the statements in the lesson's solution shall be looked for in the user's proposed solution. For instance, every data field and pointer box state in the lesson's solution shall be compared to the user's nodes and links to determine correctness; if any discrepencies exist, the proposed solution is incorrect. If the solution is correct, a message on the screen shall appear to the user explaning this occurence; if the proposed solution was incorrect, the program shall tell the user that the proposed solution is incorrect; no support for explaining the incorrectness shall be given to the program.

6.3: At least ten default lessons shall exist: 2 singly linked node lessons, 4 doubly linked node lessons, and 4 tree node lessons.

6.4: Default lessons are stored at cs.beloit.edu/~pointers/lessons/ , while lessons created by the user are stored locally.

Ý6.5: The lesson's solution shall be encoded such that a user cannot view the solution to the lesson.

7. User Documentation:

7.1: Two sections shall exist in the user documentation: a user section describing how to use the program and an instructor section describing how to use the lesson editor and how to create lessons.

7.1.1: The user section shall include a quickstart section and a reference section. The quickstart shall contain the essentials for easily and quickly using the basics of the program. The reference section shall go in depth and describe all of the available features of the program.

8. On-Line Help:

8.1: All help screens shall be in HTML format and opened in their own windows or frames.

8.2: A help screen listing all of the commands allowed in the text input field shall be available.

9. Copyrights and Licensing:

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 as long as these modifications are submitted to Beloit College for possible change of master documents). Commercial use of this software requires licensing from Beloit College.

10. Supported Features:

10.1: A restart program option with confirmation shall be made available to the user. This feature shall invoke the following procedures: clear the node space of all nodes and links, clear the prior command list (accompanied by the option to print out this list), close any lesson (if one is open), and close any extraneous windows that the program opened (if applicable).

10.2: A restart lesson option with confirmation shall be available to the user during a lesson. This command shall bring the node space to the beginning state of the lesson and clear the prior command list (accompanied by the option to print out this list).

10.3: A set of radio button shall exist allowing the user to specify which type of node to use; i.e. SinglyLinked, DoublyLinked, or BinaryTree. Also, two radio button shall exist allowing the user to choose which type of data field to use, either integer or string.

10.4: The program colors of links and nodes are fixed. The user shall not be able to change them.

10.5: All typed commands executed by the user shall be stored and can be printed. This list of commands shall be called the prior command list, henceforth. The program shall save all commands for this purpose until the user restarts the program or restarts the lesson (if currently in a lesson). Also, the program shall log the "undo" menu command (see section 10.6) along with any "correctness" checks (see section 6.2) during a lesson. All commands logged shall appear just as they were typed. The only exceptions to the appearance of these commands are the "undo" and "correctness" commands. These commands are saved as C++ style comments. Also, any commands "undone" shall be commented out.

10.5.1: No support shall be given to saving or printing the prior command list. The user shall have to use their web browser's internal support for saving and printing text.

10.6: An "undo" command shall be available to the user. The program shall return to the state it was in before the user entered the undone command. The "undo" is limited to one usage, i.e. the user can only undo the prior C++ command typed. A special case exists for loop control and shall be explained in section 11.6.

Ý11. Loop Control:

11.1: No break statements shall be allowed in a loop.

11.2: Loops shall be six lines or less. The body of the iteration statement shall be the only lines counted towards this limit.

11.3: The only type of loop allowed shall be (in C++ syntax) while loops, excepting further updates.

Ý11.3.1: The use of for loops shall be supported.

11.4: The option to "undo" a loop shall exist in addition to the normal "undo" command. This command shall only be enabled directly after the execution of the loop and disabled otherwise.

11.4.1: A loop shall be undone automatically if the loop ends prematurely.

11.5: The program shall give the user the option of either stepping through the loop, one line at a time, or executing the loop to completion.

11.5.1: The user shall have a command available to quit a loop as they step through it.

11.6: If any errors occur during the running of a loop, the loop shall terminate at the point of error and "undo" the loop portion run.

12. Conditionals:

12.1: Compound conditionals shall be supported. For example, the following conditional shall be supported:

( (p->data == q->data) && ( q->data == r->data) )

12.2: The program shall not support nested conditionals. For example, the following sequence of commands shall not be allowed:

if (p->next == NULL) {

if (q->next == NULL) {

p->next = q;

}

}

ÝÝ13. Other Misc:

13.1: Somewhere on the HTML page for this program, a hot link shall exist to a picture of the creation team, eating copius amounts of pizza and imbibing beverages of choice. The User Documentation team shall determine the attire worn during the picture.

Search engine sitemap created by AutoSitemap.com