-- MatrixImpl.mesa -- last edit March 2, 1983 4:58 pm Sturgis DIRECTORY Matrix USING[]; MatrixImpl: PROGRAM EXPORTS Matrix = BEGIN Matrix: TYPE = REF MatrixBody; MatrixElement: TYPE = REF ANY; MatrixBody: PUBLIC TYPE = RECORD [ nRows: CARDINAL, nColumns: CARDINAL, firstRow: Row, firstColumn: Column, recentX: CARDINAL, recentColumn: Column, -- if not NIL then corresponds to recentX recentY: CARDINAL, recentRow: Row -- if not NIL then corresponds to recentY ]; Row: TYPE = REF RowBody; Column: TYPE = REF ColumnBody; CrossPoint: TYPE = REF CrossPointBody; RowBody: TYPE = RECORD [ next: Row, -- i.e. y+1 rowInfo: MatrixElement, firstCrossPoint: CrossPoint, recentX: CARDINAL, recentCrossPoint: CrossPoint -- if not NIL then corresponds to recentX ]; ColumnBody: TYPE = RECORD [ next: Column, -- i.e. x+1 columnInfo: MatrixElement ]; CrossPointBody: TYPE = RECORD [ element: MatrixElement, next: CrossPoint -- i.e. ]; CreateMatrix: PUBLIC PROCEDURE RETURNS[Matrix] = BEGIN RETURN[NEW[MatrixBody _ [ nRows: 0, nColumns: 0, firstRow: NIL, firstColumn: NIL, recentX: 0, recentY: 0, recentColumn: NIL, recentRow: NIL]]]; END; AddColumnAt: PUBLIC PROCEDURE[m: Matrix, x: CARDINAL] = BEGIN prevCol: Column _ MoveToColumn[m, x-1]; nextCol: Column _ IF prevCol = NIL THEN m.firstColumn ELSE prevCol.next; newCol: Column _ NEW[ColumnBody _ [nextCol, NIL]]; IF prevCol # NIL THEN prevCol.next _ newCol ELSE m.firstColumn _ newCol; m.recentX _ x-1; m.recentColumn _ prevCol; FOR row: Row _ m.firstRow, row.next WHILE row # NIL DO prevCrossPnt: CrossPoint _ MoveToCrossPntInRow[m, row, x-1]; nextCrossPnt: CrossPoint _ IF prevCrossPnt = NIL THEN row.firstCrossPoint ELSE prevCrossPnt.next; newCrossPnt: CrossPoint _ NEW[CrossPointBody _ [NIL, nextCrossPnt]]; IF prevCrossPnt = NIL THEN row.firstCrossPoint _ newCrossPnt ELSE prevCrossPnt.next _ newCrossPnt; ENDLOOP; m.recentY _ 0; m.recentRow _ NIL; m.nColumns _ m.nColumns+1; END; AddRowAt: PUBLIC PROCEDURE[m: Matrix, y: CARDINAL] = BEGIN prevRow: Row _ MoveToRow[m, y-1]; nextRow: Row _ IF prevRow = NIL THEN m.firstRow ELSE prevRow.next; newRow: Row _ NEW[RowBody _ [nextRow, NIL, NIL, 0, NIL]]; newCrossPnt: CrossPoint _ NIL; IF prevRow # NIL THEN prevRow.next _ newRow ELSE m.firstRow _ newRow; FOR I: CARDINAL IN [1..m.nColumns] DO newCrossPnt _ NEW[CrossPointBody _ [NIL, newCrossPnt]]; ENDLOOP; newRow.firstCrossPoint _ newCrossPnt; newRow.recentX _ 0; newRow.recentCrossPoint _ NIL; m.nRows _ m.nRows+1; END; DeleteColumnAt: PUBLIC PROCEDURE[m: Matrix, x: CARDINAL] = BEGIN prevCol: Column _ MoveToColumn[m, x-1]; oldCol: Column _ IF prevCol = NIL THEN m.firstColumn ELSE prevCol.next; IF prevCol = NIL THEN m.firstColumn _ oldCol.next ELSE prevCol.next _ oldCol.next; FOR row: Row _ m.firstRow, row.next WHILE row # NIL DO prevCrossPnt: CrossPoint _ MoveToCrossPntInRow[m, row, x-1]; oldCrossPnt: CrossPoint _ IF prevCrossPnt = NIL THEN row.firstCrossPoint ELSE prevCrossPnt.next; IF prevCrossPnt = NIL THEN row.firstCrossPoint _ oldCrossPnt.next ELSE prevCrossPnt.next _ oldCrossPnt.next ENDLOOP; m.nColumns _ m.nColumns-1; END; DeleteRowAt: PUBLIC PROCEDURE[m: Matrix, y: CARDINAL] = BEGIN prevRow: Row _ MoveToRow[m, y-1]; oldRow: Row _ IF prevRow = NIL THEN m.firstRow ELSE prevRow.next; IF prevRow = NIL THEN m.firstRow _ oldRow.next ELSE prevRow.next _ oldRow.next; m.nRows _ m.nRows-1; END; SetElementAt: PUBLIC PROCEDURE[m: Matrix, x, y: CARDINAL, e: MatrixElement] = BEGIN crossPoint: CrossPoint _ MoveToCrossPoint[m, x, y]; crossPoint.element _ e; END; GetElementAt: PUBLIC PROCEDURE[m: Matrix, x, y: CARDINAL] RETURNS[MatrixElement] = BEGIN crossPoint: CrossPoint _ MoveToCrossPoint[m, x, y]; RETURN[crossPoint.element]; END; SetRowInfoAt: PUBLIC PROCEDURE[m: Matrix, y: CARDINAL, e: MatrixElement] = BEGIN row: Row _ MoveToRow[m, y]; row.rowInfo _ e; END; SetColumnInfoAt: PUBLIC PROCEDURE[m: Matrix, x: CARDINAL, e: MatrixElement] = BEGIN column: Column _ MoveToColumn[m, x]; column.columnInfo _ e; END; GetRowInfoAt: PUBLIC PROCEDURE[m: Matrix, y: CARDINAL] RETURNS[MatrixElement] = BEGIN row: Row _ MoveToRow[m, y]; RETURN[row.rowInfo]; END; GetColumnInfoAt: PUBLIC PROCEDURE[m: Matrix, x: CARDINAL] RETURNS[MatrixElement] = BEGIN column: Column _ MoveToColumn[m, x]; RETURN[column.columnInfo]; END; OutOfBounds: PUBLIC ERROR = CODE; -- support code MoveToColumn: PROCEDURE[m: Matrix, x: CARDINAL] RETURNS[Column] = BEGIN col: Column; IF x > m.nColumns THEN ERROR; IF x >= m.recentX AND m.recentX > 0 THEN BEGIN col _ m.recentColumn; FOR I: CARDINAL IN (m.recentX..x] DO col _ col.next ENDLOOP; END ELSE IF x >= 1 THEN BEGIN col _ m.firstColumn; FOR I: CARDINAL IN (1..x] DO col _ col.next ENDLOOP; END ELSE col _ NIL; m.recentX _ x; m.recentColumn _ col; RETURN[col]; END; MoveToCrossPoint: PROCEDURE[m: Matrix, x, y: CARDINAL] RETURNS[CrossPoint] = {RETURN[MoveToCrossPntInRow[m, MoveToRow[m, y], x]]}; MoveToRow: PROCEDURE[m: Matrix, y: CARDINAL] RETURNS[Row] = BEGIN row: Row; IF y > m.nRows THEN ERROR; IF y >= m.recentY AND m.recentY > 0THEN BEGIN row _ m.recentRow; FOR I: CARDINAL IN (m.recentY..y] DO row _ row.next ENDLOOP; END ELSE IF y >= 1 THEN BEGIN row _ m.firstRow; FOR J: CARDINAL IN (1..y] DO row _ row.next ENDLOOP; END ELSE row _ NIL; m.recentY _ y; m.recentRow _ row; RETURN[row]; END; MoveToCrossPntInRow: PROCEDURE[m: Matrix, row: Row, x: CARDINAL] RETURNS[CrossPoint] = BEGIN crossPoint: CrossPoint; IF x > m.nColumns THEN ERROR; IF x >= row.recentX AND row.recentX > 0 THEN BEGIN crossPoint _ row.recentCrossPoint; FOR I: CARDINAL IN (row.recentX..x] DO crossPoint _ crossPoint.next ENDLOOP; END ELSE IF x >= 1 THEN BEGIN crossPoint _ row.firstCrossPoint; FOR I: CARDINAL IN (1..x] DO crossPoint _ crossPoint.next ENDLOOP; END ELSE crossPoint _ NIL; row.recentX _ x; row.recentCrossPoint _ crossPoint; RETURN[crossPoint]; END; END.. -- March 2, 1983 4:01 pm: Sturgis, re-write matrix impl from scratch, to not use doubly linked lists, or orthogonal links. -- RTE: March 2, 1983 4:51 pm: Forgot to increment and decrement nColumns and nRows. -- RTE: March 2, 1983 4:57 pm: add column forgot to install the newly created crosspoints in their rows. )J'JJJ:i