-- 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. <x+1, y>
];



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.