The George Washington University
School of Engineering and Applied Science
Department of Electrical Engineering and Computer Science
CSci 131 -- Fall 1996

Project #5

Due Date: Thurs. Dec. 5 (sect. 10); Mon. Dec. 9 (sect. 11)

This project involves modifying Project 4 as follows:

1. Add a procedure to allow the rows of a spreadsheet to be sorted:

PROCEDURE Sort(Key_Column: IN Columns; Row_Slice: IN Row_Slices);

The column parameter specifies the sort key and the row range specifies the rows to be sorted. Use a generic version of the quick sort to accomplish this task. Do not physically sort the rows of the spreadsheet. Instead, sort a parallel array, whose type and variable declarations are shown below:

TYPE Sort_Keys IS ARRAY (Integer RANGE <>) OF Integer;

Keys: Sort_Keys(Rows'Pos(Rows'First)..Rows'Pos(Rows'Last));

Instantiate the generic shell sort procedure by supplying a Key_Of procedure that extracts the value from the corresponding row and the sort key column. A "<" function for spreadsheet cells must also be supplied at instantiation time. When the spreadsheet is printed, this parallel array should be used to print the spreadsheet in sorted order. In the main procedure, call the sort procedure to sort the spreadsheet by student name.

2. Add a procedure to recompute the cells of the spreadsheet that are defined by functions or formulas. The specification for that procedure is shown below:

PROCEDURE Recompute;

In order to recompute the values of cells of the spreadsheet defined by functions or formulas, it will be necessary to maintain the functions and formulas for such cells. The revised type definitions for the spreadsheet are shown below:

  TYPE Computations IS (Fixed,Functional,Formula);

  TYPE Calculations(Computation: Computations := Fixed) IS RECORD
      CASE Computation IS
        WHEN Fixed =>
          NULL;
        WHEN Functional =>
          A_Function: Functions;
          Block: Blocks;
        WHEN Formula =>
          Expression: Tree;
      END CASE;
    END RECORD;

  TYPE Cell_Data IS RECORD
      Value: Values;
      Calculation: Calculations;
    END RECORD;
  Spreadsheet: ARRAY(Rows,Columns) OF Cell_Data;

Formulas should be stored as binary expression trees (sects. 11.5, 11.6), not as the strings supplied to define them. The type definitions required are the following:

  TYPE Operators IS (Add,Subtract,Multiply,Divide);

  TYPE Node_Types IS
   (Operator_Type,Variable_Operand,Constant_Operand);

  TYPE Nodes(Node_Type: Node_Types := Operator_Type) IS RECORD
      CASE Node_Type IS
        WHEN Operator_Type =>
          Operator: Operators;
        WHEN Variable_Operand =>
          Cell: Cells;
        WHEN Constant_Operand =>
          Operand: Float;
      END CASE;
    END RECORD;

  TYPE TreeNode;

  TYPE Tree IS ACCESS TreeNode;

  TYPE TreeNode IS RECORD
      Left: Tree;
      Data: Nodes;
      Right: Tree;
  END RECORD;

The formulas supplied to the spreadsheet package should be written in infix notation instead of postfix. You can use Program 11.1 as a starting point for the translator that converts from infix notation to trees. Note that this program uses expressions consisting of only single-letter variables and operators, so you'll need to parse the cell references and constants as you did in Project 4.

To test the recomputation, after the spreadsheet has been set and printed, change some of the data values, recompute and reprint the spreadsheet.