AMatrixImpl.mesa
Copyright © 1986 by Xerox Corporation. All rights reserved.
Created: Sindhu July 27, 1987 2:00:51 pm PDT
Pradeep Sindhu January 25, 1988 2:42:17 pm PST
Public Procs
ConformanceCheck: PUBLIC SIGNAL = CODE;
DisallowedPath: PUBLIC SIGNAL [from, to: NAT] = CODE;
Creates an AMatrix and initializes it to all 0's
Create:
PUBLIC
PROC [size:
NAT]
RETURNS [am:
AM] = {
am ← NEW [AMRec[size]];
FOR i:
NAT
IN [0..size)
DO
am[i] ← NEW [AVectorRec[size]];
FOR j: NAT IN [0..size) DO am[i][j] ← 0 ENDLOOP;
ENDLOOP;
};
Copy:
PUBLIC
PROC [from:
AM]
RETURNS [to:
AM] = {
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 Adjacency matrices
Multiply:
PUBLIC
PROC [left, right:
AM]
RETURNS[result:
AM] = {
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 am1 and am2 if they conform, otherwise generates a signal
Size:
PUBLIC
PROC [am1, am2:
AM]
RETURNS [size:
NAT] = {
size ← am1.size;
IF size#am2.size THEN SIGNAL ConformanceCheck;
FOR i:
NAT
IN [0..size)
DO
IF am1[i].size#size OR am2[i].size#size THEN SIGNAL ConformanceCheck;
ENDLOOP;
};
Equal:
PUBLIC
PROC [am1, am2:
AM]
RETURNS [
BOOL ←
TRUE] = {
size: NAT ← Size[am1, am2];
FOR i:
NAT
IN [0..size)
DO
FOR j: NAT IN [0..size) DO IF am1[i][j]#am2[i][j] THEN RETURN [FALSE] ENDLOOP
ENDLOOP;
};
Creates a sequence of Cardinality[am] Incidence Matrices and initalizes them to am, am**2, ...
CreateAMSeq:
PUBLIC
PROC [am:
AM]
RETURNS [amSeq: AMSeq] = {
InList:
PROC [am:
AM, amList:
LIST
OF
AM]
RETURNS [
BOOL ←
FALSE] = {
FOR l:
LIST
OF
AM ← amList, l.rest
WHILE l#
NIL
DO
IF Equal[am, l.first] THEN RETURN [TRUE]
ENDLOOP;
};
amN: AM ← Copy[am];
amList: LIST OF AM ← NIL;
amListSize: 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[amN, amList]
DO
amList ← CONS [amN, amList];
amListSize ← amListSize+1;
amN ← Multiply[amN, am];
Process.Yield[];
ENDLOOP;
amSeq ← NEW [AMSeqRec[amListSize]];
amSeq.buf ← NEW [BufRec[amListSize+1]]; -- buffer must be one longer
amSeq.buf[amListSize] ← 0;
FOR i:
NAT
DECREASING
IN [0..amListSize)
DO
amSeq.buf[i] ← 0;
amSeq[i] ← amList.first;
amList ← amList.rest;
ENDLOOP;
Process.SetPriority[oldPriority];
};
InitAMSeq:
PUBLIC
PROC [amSeq: AMSeq] = {
seqSize: NAT ← amSeq.size;
size: NAT ← amSeq[0].size;
IF amSeq.buf.first=amSeq.buf.last THEN RETURN; -- buffer is empty, no need to initialize
Initialize buffer
amSeq.buf.first ← amSeq.buf.last ← 0;
FOR i: NAT IN [0..amSeq.buf.size) DO amSeq.buf[i] ← 0 ENDLOOP;
Initialize amSeq
FOR s:
NAT
IN [0..seqSize)
DO
FOR i:
NAT
IN [0..size)
DO
FOR j:
NAT
IN [0..size)
DO
IF amSeq[s][i][j]>1 THEN amSeq[s][i][j] ← 1;
ENDLOOP;
ENDLOOP;
ENDLOOP;
};
UpdateAMSeq:
PUBLIC
PROC [amSeq: AMSeq, pc:
NAT] = {
PathLength:
PROC [i, j:
NAT]
RETURNS [
NAT] = {
IF (j-i)>=0 THEN RETURN [j-i] ELSE RETURN [bufSize+j-i]
};
bufSize: NAT ← amSeq.buf.size;
amSeq.buf.pcs[amSeq.buf.last] ← pc;
FOR i:
NAT ← amSeq.buf.first, (i+1)
MOD bufSize
WHILE i#amSeq.buf.last
DO
iPC: NAT ← amSeq.buf[i];
pathLength: NAT ← PathLength[i, amSeq.buf.last];
IF amSeq[pathLength-1][iPC][pc] = 0
THEN SIGNAL DisallowedPath[iPC, pc]
ELSE amSeq[pathLength-1][iPC][pc] ← amSeq[pathLength-1][iPC][pc]+1;
ENDLOOP;
amSeq.buf.last ← (amSeq.buf.last+1) MOD bufSize;
IF amSeq.buf.last=amSeq.buf.first THEN amSeq.buf.first ← (amSeq.buf.first+1) MOD bufSize;
};