IMatrixImpl.mesa
Copyright © 1986 by Xerox Corporation. All rights reserved.
Created: Sindhu July 27, 1987 2:00:51 pm PDT
Pradeep Sindhu December 24, 1987 11:07:10 am PST
Public Procs
ConformanceCheck: PUBLIC SIGNAL = CODE;
DisallowedPath: PUBLIC SIGNAL [from, to: NAT] = CODE;
Creates an IMatrix and initializes it to all 0's
Create:
PUBLIC
PROC [size:
NAT]
RETURNS [im:
IM] = {
im ← NEW [IMRec[size]];
FOR i:
NAT
IN [0..size)
DO
im[i] ← NEW [IVectorRec[size]];
FOR j: NAT IN [0..size) DO im[i][j] ← 0 ENDLOOP;
ENDLOOP;
};
Copy:
PUBLIC
PROC [from:
IM]
RETURNS [to:
IM] = {
size: NAT ← from.size;
to ← Create[size];
FOR i:
NAT
IN [0..size)
DO
FOR j: NAT IN [0..size) DO to[i][j] ← from[i][j] ENDLOOP;
ENDLOOP;
};
Multiplies left by right according to the rules for incidence matrices
Multiply:
PUBLIC
PROC [left, right:
IM]
RETURNS[result:
IM] = {
size: NAT ← Size[left, right];
result ← Create[size];
FOR i:
NAT
IN [0..size)
DO
FOR j:
NAT
IN [0..size)
DO
FOR k: NAT IN [0..size) DO result[i][j] ← result[i][j] + left[i][k]*right[k][j] ENDLOOP;
IF result[i][j] > 1 THEN result[i][j] ← 1;
Process.Yield[];
ENDLOOP;
ENDLOOP;
};
Returns the size of im1 and im2 if they conform, otherwise generates a signal
Size:
PUBLIC
PROC [im1, im2:
IM]
RETURNS [size:
NAT] = {
size ← im1.size;
IF size#im2.size THEN SIGNAL ConformanceCheck;
FOR i:
NAT
IN [0..size)
DO
IF im1[i].size#size OR im2[i].size#size THEN SIGNAL ConformanceCheck;
ENDLOOP;
};
Equal:
PUBLIC
PROC [im1, im2:
IM]
RETURNS [
BOOL ←
TRUE] = {
size: NAT ← Size[im1, im2];
FOR i:
NAT
IN [0..size)
DO
FOR j: NAT IN [0..size) DO IF im1[i][j]#im2[i][j] THEN RETURN [FALSE] ENDLOOP
ENDLOOP;
};
Creates a sequence of Cardinality[im] Incidence Matrices and initalizes them to im, im**2, ...
CreateIMSeq:
PUBLIC
PROC [im:
IM]
RETURNS [imSeq: IMSeq] = {
InList:
PROC [im:
IM, imList:
LIST
OF
IM]
RETURNS [
BOOL ←
FALSE] = {
FOR l:
LIST
OF
IM ← imList, l.rest
WHILE l#
NIL
DO
IF Equal[im, l.first] THEN RETURN [TRUE]
ENDLOOP;
};
imN: IM ← Copy[im];
imList: LIST OF IM ← NIL;
imListSize: NAT ← 0;
oldPriority: Process.Priority ← Process.GetPriority[];
Process.SetPriority[Process.priorityBackground];
First create the matrices in a list, then copy them to a sequence
WHILE
NOT InList[imN, imList]
DO
imList ← CONS [imN, imList];
imListSize ← imListSize+1;
imN ← Multiply[imN, im];
Process.Yield[];
ENDLOOP;
imSeq ← NEW [IMSeqRec[imListSize]];
imSeq.buf ← NEW [BufRec[imListSize+1]]; -- buffer must be one longer
imSeq.buf[imListSize] ← 0;
FOR i:
NAT
DECREASING
IN [0..imListSize)
DO
imSeq.buf[i] ← 0;
imSeq[i] ← imList.first;
imList ← imList.rest;
ENDLOOP;
Process.SetPriority[oldPriority];
};
InitIMSeq:
PUBLIC
PROC [imSeq: IMSeq] = {
seqSize: NAT ← imSeq.size;
size: NAT ← imSeq[0].size;
IF imSeq.buf.first=imSeq.buf.last THEN RETURN; -- buffer is empty, no need to initialize
Initialize buffer
imSeq.buf.first ← imSeq.buf.last ← 0;
FOR i: NAT IN [0..imSeq.buf.size) DO imSeq.buf[i] ← 0 ENDLOOP;
Initialize imSeq
FOR s:
NAT
IN [0..seqSize)
DO
FOR i:
NAT
IN [0..size)
DO
FOR j:
NAT
IN [0..size)
DO
IF imSeq[s][i][j]>1 THEN imSeq[s][i][j] ← 1;
ENDLOOP;
ENDLOOP;
ENDLOOP;
};
UpdateIMSeq:
PUBLIC
PROC [imSeq: IMSeq, pc:
NAT] = {
PathLength:
PROC [i, j:
NAT]
RETURNS [
NAT] = {
IF (j-i)>=0 THEN RETURN [j-i] ELSE RETURN [bufSize+j-i]
};
bufSize: NAT ← imSeq.buf.size;
imSeq.buf.pcs[imSeq.buf.last] ← pc;
FOR i:
NAT ← imSeq.buf.first, (i+1)
MOD bufSize
WHILE i#imSeq.buf.last
DO
iPC: NAT ← imSeq.buf[i];
pathLength: NAT ← PathLength[i, imSeq.buf.last];
IF imSeq[pathLength-1][iPC][pc] = 0
THEN SIGNAL DisallowedPath[iPC, pc]
ELSE imSeq[pathLength-1][iPC][pc] ← imSeq[pathLength-1][iPC][pc]+1;
ENDLOOP;
imSeq.buf.last ← (imSeq.buf.last+1) MOD bufSize;
IF imSeq.buf.last=imSeq.buf.first THEN imSeq.buf.first ← (imSeq.buf.first+1) MOD bufSize;
};