DIRECTORY IMatrix, Process; IMatrixImpl: CEDAR PROGRAM IMPORTS Process EXPORTS IMatrix ~ BEGIN OPEN IMatrix; ConformanceCheck: PUBLIC SIGNAL = CODE; DisallowedPath: PUBLIC SIGNAL [from, to: NAT] = CODE; 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; }; 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; }; 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; }; 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]; 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 imSeq.buf.first _ imSeq.buf.last _ 0; FOR i: NAT IN [0..imSeq.buf.size) DO imSeq.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 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; }; END. vIMatrixImpl.mesa Copyright c 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 Implementation of Incidence matrices. Public Procs Creates an IMatrix and initializes it to all 0's Multiplies left by right according to the rules for incidence matrices Returns the size of im1 and im2 if they conform, otherwise generates a signal Creates a sequence of Cardinality[im] Incidence Matrices and initalizes them to im, im**2, ... First create the matrices in a list, then copy them to a sequence Initialize buffer Initialize imSeq Κ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šŸœ˜—…— Ο