DIRECTORY AMatrix, Process; AMatrixImpl: CEDAR PROGRAM IMPORTS Process EXPORTS AMatrix ~ BEGIN OPEN AMatrix; ConformanceCheck: PUBLIC SIGNAL = CODE; DisallowedPath: PUBLIC SIGNAL [from, to: NAT] = CODE; 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; }; 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; }; 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; }; 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]; 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 amSeq.buf.first _ amSeq.buf.last _ 0; FOR i: NAT IN [0..amSeq.buf.size) DO amSeq.buf[i] _ 0 ENDLOOP; 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; }; END. tAMatrixImpl.mesa Copyright c 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 Implementation of Adjacency matrices. Public Procs Creates an AMatrix and initializes it to all 0's Multiplies left by right according to the rules for Adjacency matrices Returns the size of am1 and am2 if they conform, otherwise generates a signal Creates a sequence of Cardinality[am] Incidence Matrices and initalizes them to am, am**2, ... First create the matrices in a list, then copy them to a sequence Initialize buffer Initialize amSeq ΚI˜codešœ™Kšœ Οmœ1™K˜K™šŸœŸœŸœŸ˜šŸœŸœŸœ Ÿ˜šŸœŸœŸœ Ÿ˜KšŸœŸœ˜,KšŸœ˜—KšŸœ˜—KšŸœ˜—K˜—K˜šž œŸœŸœŸœ˜4š ž œŸœŸœŸœŸœ˜.Kš Ÿœ ŸœŸœŸœŸœ˜7K˜—Kšœ Ÿœ˜K˜K˜#K˜š ŸœŸœŸœ ŸœŸ˜IKšœŸœ˜Kšœ Ÿœ!˜0K˜šŸœ!˜#KšŸœŸœ˜#KšŸœ?˜C—KšŸœ˜—K˜Kšœ$Ÿœ ˜0KšŸœ Ÿœ'Ÿœ ˜YK˜—K˜J˜—KšŸœ˜—…— Ν