DIRECTORY Alloc USING [Handle, Notifier, AddNotify, DropNotify, FreeChunk, GetChunk], HashTypes USING [HTIndex], Symbols USING [HTIndex, ISEIndex], Tree USING [AttrId, Base, Finger, Id, Index, Info, Link, Map, Node, NodeName, Scan, Test, maxNSons, null, nullIndex, treeType], TreeOps USING []; TreePack: PROGRAM IMPORTS Alloc EXPORTS TreeOps = { LitIndex: TYPE = HashTypes.HTIndex; endIndex: Tree.Index = Tree.Index.LAST; endMark: Tree.Link = [subtree[index: endIndex]]; initialized: BOOL _ FALSE; table: Alloc.Handle; LinkSeq: TYPE = RECORD[SEQUENCE length: CARDINAL OF Tree.Link]; LinkStack: TYPE = REF LinkSeq; stack: LinkStack; sI: CARDINAL; tb: Tree.Base; -- tree base UpdateBase: Alloc.Notifier = {tb _ base[Tree.treeType]}; Initialize: PUBLIC PROC[ownTable: Alloc.Handle] = { IF initialized THEN Finalize[]; stack _ NEW[LinkSeq[250]]; sI _ 0; table _ ownTable; table.AddNotify[UpdateBase]; IF MakeNode[$none,0] # Tree.null THEN ERROR; -- reserve null initialized _ TRUE}; Reset: PUBLIC PROC = { IF initialized AND stack.length > 250 THEN { stack _ NEW[LinkSeq[250]]}}; Finalize: PUBLIC PROC = { table.DropNotify[UpdateBase]; table _ NIL; stack _ NIL; initialized _ FALSE}; ExpandStack: PROC = { newStack: LinkStack = NEW[LinkSeq[stack.length + 256]]; FOR i: CARDINAL IN [0 .. stack.length) DO newStack[i] _ stack[i] ENDLOOP; stack _ newStack}; PushTree: PUBLIC PROC[v: Tree.Link] = { IF sI >= stack.length THEN ExpandStack[]; stack[sI] _ v; sI _ sI+1}; PopTree: PUBLIC PROC RETURNS[Tree.Link] = {RETURN[stack[sI_sI-1]]}; InsertTree: PUBLIC PROC[v: Tree.Link, n: CARDINAL] = { i: CARDINAL; IF sI >= stack.length THEN ExpandStack[]; i _ sI; sI _ sI+1; THROUGH [1 .. n) DO stack[i] _ stack[i-1]; i _ i-1 ENDLOOP; stack[i] _ v}; ExtractTree: PUBLIC PROC[n: CARDINAL] RETURNS[v: Tree.Link] = { i: CARDINAL _ sI - n; v _ stack[i]; THROUGH [1 .. n) DO stack[i] _ stack[i+1]; i _ i+1 ENDLOOP; sI _ sI - 1; RETURN[v]}; MakeNode: PUBLIC PROC[name: Tree.NodeName, count: INTEGER] RETURNS[Tree.Link] = { PushNode[name, count]; RETURN[PopTree[]]}; MakeList: PUBLIC PROC[size: INTEGER] RETURNS[Tree.Link] = { PushList[size]; RETURN[PopTree[]]}; PushNode: PUBLIC PROC[name: Tree.NodeName, count: INTEGER] = { nSons: CARDINAL = count.ABS; node: Tree.Index = table.GetChunk[Tree.Node.SIZE+nSons*Tree.Link.SIZE, Tree.treeType]; i: CARDINAL; tb[node].name _ name; tb[node].nSons _ nSons; tb[node].info _ 0; tb[node].shared _ FALSE; tb[node].attrs _ ALL[FALSE]; IF count >= 0 THEN FOR i _ nSons, i-1 WHILE i >= 1 DO tb[node].son[i] _ stack[sI_sI-1] ENDLOOP ELSE FOR i _ 1, i+1 WHILE i <= nSons DO tb[node].son[i] _ stack[sI_sI-1] ENDLOOP; IF sI >= stack.length THEN ExpandStack[]; stack[sI] _ [subtree[index: node]]; sI _ sI+1}; PushList: PUBLIC PROC[size: INTEGER] = { nSons: CARDINAL = size.ABS; node: Tree.Index; i: CARDINAL; SELECT nSons FROM 1 => NULL; 0 => PushTree[Tree.null]; ENDCASE => { IF nSons IN (0..Tree.maxNSons] THEN node _ table.GetChunk[Tree.Node.SIZE+nSons*Tree.Link.SIZE, Tree.treeType] ELSE { node _ table.GetChunk[Tree.Node.SIZE+(nSons+1)*Tree.Link.SIZE, Tree.treeType]; tb[node].son[nSons+1] _ endMark}; tb[node].name _ $list; tb[node].info _ 0; tb[node].shared _ FALSE; tb[node].attrs _ ALL[FALSE]; tb[node].nSons _ IF nSons IN (0..Tree.maxNSons] THEN nSons ELSE 0; IF size > 0 THEN FOR i _ nSons, i-1 WHILE i >= 1 DO tb[node].son[i] _ stack[sI_sI-1] ENDLOOP ELSE FOR i _ 1, i+1 WHILE i <= nSons DO tb[node].son[i] _ stack[sI_sI-1] ENDLOOP; IF sI >= stack.length THEN ExpandStack[]; stack[sI] _ [subtree[index: node]]; sI _ sI+1}}; PushProperList: PUBLIC PROC[size: INTEGER] = { IF size IN [-1..1] THEN { node: Tree.Index = table.GetChunk[Tree.Node.SIZE+Tree.Link.SIZE, Tree.treeType]; tb[node].name _ $list; tb[node].info _ 0; tb[node].shared _ FALSE; tb[node].attrs _ ALL[FALSE]; tb[node].nSons _ size.ABS; tb[node].son[1] _ IF size = 0 THEN endMark ELSE PopTree[]; PushTree[[subtree[index: node]]]} ELSE PushList[size]}; PushHash: PUBLIC PROC[hti: Symbols.HTIndex] = {PushTree[[hash[index: hti]]]}; PushSe: PUBLIC PROC[sei: Symbols.ISEIndex] = {PushTree[[symbol[index: sei]]]}; PushLit: PUBLIC PROC[lti: LitIndex] = {PushTree[[literal[index: lti]]]}; SetInfo: PUBLIC PROC[info: Tree.Info] = { WITH stack[sI-1] SELECT FROM v: Tree.Link.subtree => IF v # Tree.null THEN tb[v.index].info _ info; ENDCASE}; SetAttr: PUBLIC PROC[attr: Tree.AttrId, value: BOOL] = { WITH stack[sI-1] SELECT FROM v: Tree.Link.subtree => IF v = Tree.null THEN ERROR ELSE tb[v.index].attrs[attr] _ value; ENDCASE => ERROR}; FreeNode: PUBLIC PROC[node: Tree.Index] = { IF node # Tree.nullIndex AND ~tb[node].shared THEN { i: CARDINAL; t: Tree.Link; n: CARDINAL _ tb[node].nSons; IF tb[node].name # $list OR n # 0 THEN FOR i _ 1, i+1 WHILE i <= n DO t _ tb[node].son[i]; WITH t SELECT FROM subtree => FreeNode[index] ENDCASE; ENDLOOP ELSE { n _ 1; FOR i _ 1, i+1 UNTIL (t_tb[node].son[i]) = endMark DO WITH t SELECT FROM subtree => FreeNode[index] ENDCASE; n _ n+1; ENDLOOP}; table.FreeChunk[node, Tree.Node.SIZE+n*Tree.Link.SIZE, Tree.treeType]}}; FreeTree: PUBLIC PROC[t: Tree.Link] RETURNS[Tree.Link] = { WITH t SELECT FROM subtree => FreeNode[index]; ENDCASE; RETURN[Tree.null]}; GetHash: PUBLIC PROC[t: Tree.Link] RETURNS[Symbols.HTIndex] = { RETURN[NARROW[t, Tree.Link.hash].index]}; GetNode: PUBLIC PROC[t: Tree.Link] RETURNS[Tree.Index] = { RETURN[NARROW[t, Tree.Link.subtree].index]}; GetSe: PUBLIC PROC[t: Tree.Link] RETURNS[Symbols.ISEIndex] = { RETURN[NARROW[t, Tree.Link.symbol].index]}; NthSon: PUBLIC PROC[t: Tree.Link, n: CARDINAL] RETURNS[Tree.Link] = { RETURN[IF t = Tree.null THEN ERROR ELSE tb[NARROW[t, Tree.Link.subtree].index].son[n]]}; OpName: PUBLIC PROC[t: Tree.Link] RETURNS[Tree.NodeName] = { RETURN[IF t = Tree.null THEN $none ELSE WITH t SELECT FROM subtree => tb[index].name ENDCASE => $none]}; GetAttr: PUBLIC PROC[t: Tree.Link, attr: Tree.AttrId] RETURNS[BOOL] = { RETURN[IF t # Tree.null THEN tb[NARROW[t, Tree.Link.subtree].index].attrs[attr] ELSE ERROR]}; PutAttr: PUBLIC PROC[t: Tree.Link, attr: Tree.AttrId, value: BOOL] = { IF t = Tree.null THEN ERROR; tb[NARROW[t, Tree.Link.subtree].index].attrs[attr] _ value}; GetInfo: PUBLIC PROC[t: Tree.Link] RETURNS[Tree.Info] = { RETURN[IF t # Tree.null THEN tb[NARROW[t, Tree.Link.subtree].index].info ELSE ERROR]}; PutInfo: PUBLIC PROC[t: Tree.Link, value: Tree.Info] = { IF t = Tree.null THEN ERROR; tb[NARROW[t, Tree.Link.subtree].index].info _ value}; Shared: PUBLIC PROC[t: Tree.Link] RETURNS[BOOL] = { RETURN[WITH t SELECT FROM subtree => IF t = Tree.null THEN FALSE ELSE tb[index].shared, ENDCASE => FALSE]}; MarkShared: PUBLIC PROC[t: Tree.Link, shared: BOOL] = { WITH t SELECT FROM subtree => IF t # Tree.null THEN tb[index].shared _ shared; ENDCASE}; SonCount: PROC[node: Tree.Index] RETURNS[CARDINAL] = INLINE { RETURN[SELECT node FROM Tree.nullIndex, endIndex => 0, ENDCASE => IF tb[node].name = $list AND tb[node].nSons = 0 THEN ListLength[[subtree[index: node]]] ELSE tb[node].nSons]}; ScanSons: PUBLIC PROC[root: Tree.Link, action: Tree.Scan] = { IF root # Tree.null THEN WITH root SELECT FROM subtree => { node: Tree.Index = index; FOR i: CARDINAL IN [1 .. SonCount[node]] DO action[tb[node].son[i]] ENDLOOP}; ENDCASE; RETURN}; UpdateLeaves: PUBLIC PROC[root: Tree.Link, map: Tree.Map] RETURNS[v: Tree.Link] = { IF root = Tree.null THEN v _ Tree.null ELSE WITH root SELECT FROM subtree => { node: Tree.Index = index; FOR i: CARDINAL IN [1 .. SonCount[node]] DO tb[node].son[i] _ map[tb[node].son[i]]; ENDLOOP; v _ root}; ENDCASE => v _ map[root]; RETURN}; ListLength: PUBLIC PROC[t: Tree.Link] RETURNS[CARDINAL] = { IF t = Tree.null THEN RETURN[0]; WITH t SELECT FROM subtree => { node: Tree.Index = index; n: CARDINAL; IF tb[node].name # $list THEN RETURN[1]; n _ tb[node].nSons; IF n # 0 THEN RETURN[n]; FOR i: CARDINAL _ 1, i+1 UNTIL tb[node].son[i] = endMark DO n _ n+1 ENDLOOP; RETURN[n]}; ENDCASE => RETURN[1]}; ListHead: PUBLIC PROC[t: Tree.Link] RETURNS[Tree.Link] = { IF t = Tree.null THEN RETURN[Tree.null]; WITH t SELECT FROM subtree => { node: Tree.Index = index; RETURN[SELECT TRUE FROM (tb[node].name # $list) => t, (tb[node].son[1] # endMark) => tb[node].son[1], ENDCASE => Tree.null]}; ENDCASE => RETURN[t]}; ListTail: PUBLIC PROC[t: Tree.Link] RETURNS[Tree.Link] = { IF t = Tree.null THEN RETURN[Tree.null]; WITH t SELECT FROM subtree => { node: Tree.Index = index; RETURN[SELECT TRUE FROM (tb[node].name # $list) => t, (tb[node].son[1] # endMark) => tb[node].son[ListLength[t]], ENDCASE => Tree.null]}; ENDCASE => RETURN[t]}; ScanList: PUBLIC PROC[root: Tree.Link, action: Tree.Scan] = { IF root # Tree.null THEN WITH root SELECT FROM subtree => { node: Tree.Index = index; i, n: CARDINAL; t: Tree.Link; IF tb[node].name # $list THEN action[root] ELSE IF (n _ tb[node].nSons) # 0 THEN FOR i _ 1, i+1 WHILE i <= n DO action[tb[node].son[i]] ENDLOOP ELSE FOR i _ 1, i+1 UNTIL (t_tb[node].son[i]) = endMark DO action[t] ENDLOOP}; ENDCASE => action[root]}; ReverseScanList: PUBLIC PROC[root: Tree.Link, action: Tree.Scan] = { IF root # Tree.null THEN WITH root SELECT FROM subtree => { node: Tree.Index = index; IF tb[node].name # $list THEN action[root] ELSE FOR i: CARDINAL DECREASING IN [1 .. ListLength[root]] DO action[tb[node].son[i]] ENDLOOP}; ENDCASE => action[root]}; SearchList: PUBLIC PROC[root: Tree.Link, test: Tree.Test] = { IF root # Tree.null THEN WITH root SELECT FROM subtree => { node: Tree.Index = index; i, n: CARDINAL; t: Tree.Link; IF tb[node].name # $list THEN [] _ test[root] ELSE IF (n _ tb[node].nSons) # 0 THEN FOR i _ 1, i+1 WHILE i <= n DO IF test[tb[node].son[i]] THEN EXIT ENDLOOP ELSE FOR i _ 1, i+1 UNTIL (t_tb[node].son[i]) = endMark DO IF test[t] THEN EXIT ENDLOOP}; ENDCASE => [] _ test[root]}; UpdateList: PUBLIC PROC[root: Tree.Link, map: Tree.Map] RETURNS[Tree.Link] = { IF root = Tree.null THEN RETURN[Tree.null]; WITH root SELECT FROM subtree => { node: Tree.Index = index; i, n: CARDINAL; t: Tree.Link; IF tb[node].name # $list THEN RETURN[map[root]]; IF (n _ tb[node].nSons) # 0 THEN FOR i _ 1, i+1 WHILE i <= n DO tb[node].son[i] _ map[tb[node].son[i]] ENDLOOP ELSE FOR i _ 1, i+1 UNTIL (t_tb[node].son[i]) = endMark DO tb[node].son[i] _ map[t] ENDLOOP; RETURN[root]}; ENDCASE => RETURN[map[root]]}; ReverseUpdateList: PUBLIC PROC[root: Tree.Link, map: Tree.Map] RETURNS[Tree.Link] = { IF root = Tree.null THEN RETURN[Tree.null]; WITH root SELECT FROM subtree => { node: Tree.Index = index; IF tb[node].name # $list THEN RETURN[map[root]]; FOR i: CARDINAL DECREASING IN [1..ListLength[root]] DO tb[node].son[i] _ map[tb[node].son[i]] ENDLOOP; RETURN[root]}; ENDCASE => RETURN[map[root]]}; CopyTree: PUBLIC PROC[root: Tree.Id, map: Tree.Map] RETURNS[v: Tree.Link] = { WITH root.link SELECT FROM subtree => { sNode: Tree.Index = index; IF sNode = Tree.nullIndex THEN v _ Tree.null ELSE { size: CARDINAL = NodeSize[root.baseP, sNode]; dNode: Tree.Index = table.GetChunk[size, Tree.treeType]; t: Tree.Link; tb[dNode].name _ root.baseP^[sNode].name; tb[dNode].shared _ FALSE; tb[dNode].nSons _ root.baseP^[sNode].nSons; tb[dNode].info _ root.baseP^[sNode].info; tb[dNode].attrs _ root.baseP^[sNode].attrs; FOR i: CARDINAL IN [1..size-Tree.Node.SIZE] DO tb[dNode].son[i] _ IF (t_root.baseP^[sNode].son[i]) = endMark THEN endMark ELSE map[t]; ENDLOOP; v _ [subtree[index: dNode]]}}; ENDCASE => v _ map[root.link]; RETURN}; IdentityMap: PUBLIC Tree.Map = { RETURN[IF ISTYPE[t, Tree.Link.subtree] AND ~Shared[t] THEN CopyTree[[baseP:@tb, link:t], IdentityMap] ELSE t]}; NodeSize: PUBLIC PROC[baseP: Tree.Finger, node: Tree.Index] RETURNS[size: CARDINAL] = { IF node = Tree.nullIndex THEN size _ 0 ELSE IF baseP^[node].name # $list OR baseP^[node].nSons # 0 THEN size _ Tree.Node.SIZE + baseP^[node].nSons*Tree.Link.SIZE ELSE { size _ Tree.Node.SIZE + Tree.Link.SIZE; FOR i: CARDINAL _ 1, i+1 UNTIL baseP^[node].son[i] = endMark DO size _ size + Tree.Link.SIZE ENDLOOP}; RETURN}; }. nProtoTreePack.mesa Copyright c 1985 by Xerox Corporation. All rights reserved. Satterthwaite, April 17, 1986 1:16:48 pm PST Paul Rovner, September 9, 1983 8:53 am Russ Atkinson (RRA) March 7, 1985 0:54:06 am PST procedures for tree testing procedures for tree traversal procedures for list testing procedures for list traversal cross-table tree manipulation Κœ˜codešœ™Kšœ Οmœ1™Kšœžœ žœ˜Kšœ,žœžœ˜VKšœžœ˜ K˜.Kšœ&žœ˜,Kšœžœžœ˜šžœ ž˜Kšžœžœžœ"ž˜K—šž˜Kšžœ žœ žœ"žœ˜L—Kšžœžœ˜)K˜0K˜—š œžœžœžœ˜(Kšœžœžœ˜K˜Kšœžœ˜ šžœž˜Kšœžœ˜ K˜šžœ˜ šžœžœž˜#Kšœ žœžœ˜I—šžœ˜Kšœ žœžœ˜NK˜!—K˜Kšœ&žœ˜,Kšœžœžœ˜Kš œžœžœžœžœ˜Bšžœ ž˜Kšžœžœžœ"ž˜K—šž˜Kšžœ žœ žœ"žœ˜L—Kšžœžœ˜)K˜1K˜———š œžœžœžœ˜.šžœžœ žœ˜Kšœ,žœ žœ˜PK˜Kšœ&žœ˜,Kšœžœžœ˜Kšœžœ˜Kšœžœ žœ žœ ˜:K˜!—Kšžœ˜K˜K˜—Kš œžœžœ8˜MK˜Kš œžœžœ;˜NK˜Kš œžœžœ4˜HK˜K˜š œžœžœ˜)šžœ žœž˜Kšœžœžœ˜FKšžœ˜ K˜——š œžœžœžœ˜8šžœ žœž˜˜Kšžœžœž˜Kšžœ!˜%—Kšžœžœ˜K˜K˜——š œžœžœ˜+šžœžœžœ˜4Kšœžœ˜ K˜ Kšœžœ˜šžœžœž˜&šžœ žœž˜K˜Kšžœžœžœžœ˜6Kšž˜——šžœ˜K˜šžœ žœž˜5Kšžœžœžœžœ˜6K˜Kšžœ˜ ——Kšœ žœ žœ˜HK˜——š œžœžœžœ˜:Kšžœžœžœžœ˜9Kšžœ ˜K˜K˜——šœ™K˜š œžœžœžœ˜?Kšžœžœ˜)K˜—š œžœžœžœ˜:Kšžœžœ˜,K˜—š œžœžœžœ˜>Kšžœžœ˜+K˜—š  œžœžœžœžœ˜Ešžœžœ˜Kšžœž˜ Kšžœžœ'˜5K˜——š œžœžœžœ˜<šžœžœ˜Kšžœ˜ Kš žœžœžœžœžœ ˜EK˜——š  œžœžœ"žœžœ˜Gšžœžœ˜Kšžœžœ)˜7Kšžœžœ˜ K˜——š œžœžœ)žœ˜FKšžœžœžœ˜Kšœžœ3˜—šž˜Kšžœ žœžœ žœ˜I——Kšžœ˜K˜———š œžœžœ(˜Dšžœž˜šžœžœž˜˜ K˜Kšžœžœ ˜*šž˜š žœžœž œžœž˜8Kšœžœ˜!———Kšžœ˜K˜———š  œžœžœ&˜=šžœž˜šžœžœž˜˜ K˜Kšœžœ˜K˜ Kšžœžœ˜-šžœžœž˜%Kš žœ žœžœžœžœžœž˜I—šž˜šžœ žœž˜5Kšžœ žœžœžœ˜———Kšžœ˜K˜———š  œžœžœ!žœ˜NKšžœžœžœ ˜+šžœžœž˜˜ K˜Kšœžœ˜K˜ Kšžœžœžœ ˜0šžœž˜ Kšžœ žœžœ(ž˜M—šž˜šžœ žœž˜5Kšœžœ˜!——Kšžœ˜—Kšžœžœ ˜K˜——š œžœžœ!žœ˜UKšžœžœžœ ˜+šžœžœž˜˜ K˜Kšžœžœžœ ˜0š žœžœž œžœž˜6Kšœ'žœ˜/—Kšžœ˜—Kšžœžœ ˜K˜K˜———Kšœ™˜š œžœžœžœ˜Mšžœ žœž˜˜ K˜Kšžœžœ˜,šžœ˜Kšœžœ˜-K˜8K˜ K˜)Kšœžœ˜K˜+K˜)K˜+š žœžœžœžœž˜.šœžœ(˜=Kšžœ˜ Kšžœ˜ —Kšžœ˜—K˜——Kšžœ˜—Kšžœ˜K˜—šœ žœ ˜ šžœžœžœžœ ˜5Kšžœ+˜/Kšžœ˜ K˜K˜——š  œžœžœ'žœžœ˜WKšžœžœ ˜&šžœžœžœž˜@Kšœžœ ž˜9—šžœ˜Kšœžœ žœ˜'šžœžœ žœž˜?Kšœžœžœ˜&——Kšžœ˜K˜—K˜K˜——…—.θAς