CMSC731

Bryan Scappini
Cheney's Algorithm applet

Introduction: This applet graphically illustrates the Cheney's algorithm for a copying, semispace garbage collecting algorithm. It allows for stepping forward and backward through examples with associated text descriptions and for loading of arbitrary examples.

Included in the applet are three source files ConsCell.java, CheneyPanel.java, and CheneyApplet.java. The files hold the following purposes:

ConsCell.java: this class represents a cons cell, that is, a simple structure which contains to pointers to other cons cells. This is the basic unit of memory used in illustrating the Cheney's algorithm. This class will maintain the state of the cons cell and the pointer values, as well as graphical features needed for displaying the cons cell.
CheneyPanel.java: this class contains all the logic for moving the Cheney's algorithm forward and backward step-by-step. It maintains the information and cons cells of the current collection example.
CheneyApplet.java: this is the main applet class. It contains the UI elements for interacting with the CheneyPanel and the current collection example. The class can be run either as an applet or an application.

In addition there are two other files included in this submission:

ex1.txt: a sample example file which may be loaded into the applet.
cheney.html: a web page briefly describing Cheney's algorithm and outlining how to use the applet.

Once you start the applet, you are shown the default collection example which is built in. The main component shows a graphical representation of memory of the example: the root cells are shown in the top row of cons cells and the second row of cons cells shows the from-space of the heap. The buttons on the left allow you to step the current example forward or backwards by clicking the appropriate button. As you do so, the picture of the memory will update as new cons cells are allocated in the bottom row (the to-space) and pointers are moved and updated. In addition, the cons cells will change colors based upon what it happening:

white: default state
yellow: marks the pointer that is currently being scanned/updated
pink: indicates that the pointer has already been scanned
green: indicates that the cons cell had a reference to it forwarded to the to-space

Furthermore, at each step, a brief text description of what is taking place is added to the scrolling text area at the bottom of the applet. The other two buttons allow you to reset the current example to its beginning state, or to load a new example. To load a new example, you are prompted for a filename giving a file which contains the example information: this allows you to prepare beforehand then quickly load several different examples. The format of the input file is outlined by the sample file below:

# Here is a sample example file; notice that comment lines begin with '#'
# The first line of the file is the number of root cons cells
3
# The second line are the pointers of the root cons cells; -1 means no
#   pointer, other numbers are indexes into the from-space (0 points to 
#   first cells in from space, 1 points to next, etc...). Parens and commas
#   are allowed.
((0 -1) (0 1) (-1 1))
# The third line is the number fo from-space cons cells; this has to be at
#   least the greatest number from the previous line + 1
3
# The fourth line are the from-space cell pointers; these reference other cells 
#   in the from-space
((-1 -1) (0 -1) (1 -1))
# This file should end with a comment or blank line

Essentially, the input file has at least four lines with optional comment lines. Comment lines begin with '#'. The four lines give the number of root cons cells, their pointers into the heap, the number of heap cons cells, and the heap cells' pointers. If any of this data is missing, improperly formatted, or inconsistent, then the new example will fail to load the current example will remain unchanged.