TreeSlice.mesa; written by Bill Paxton, June 1981
edited by McGregor, February 7, 1983 9:44 am
edited by Bill Paxton, July 18, 1983 3:32 pm
DIRECTORY TiogaNode, TiogaTreeOps;
TreeSlice: CEDAR DEFINITIONS = BEGIN
Ref: TYPE = TiogaNode.Ref;
RefBranchNode: TYPE = TiogaNode.RefBranchNode;
***** Declarations
Slice: TYPE = REF SliceArray;
SliceArray:
TYPE =
RECORD [
next: Slice, -- for free list
kind: OfSlice, -- before/after
length: NAT ← 0,
nodes:
SEQUENCE maxLength:
NAT
OF Ref
nodes[0] can be RefBranchNode or RefListNode or RefBoxNode
nodes[i} for i>0 is always a RefBranchNode
];
OfSlice: TYPE = { before, after };
Order: TYPE = { same, before, after, disjoint };
***** Operations
GetSlice: PROC [len: NAT] RETURNS [slice: Slice];
FreeSlice: PROC [slice: Slice];
MakeSlices: PROC [node: RefBranchNode] RETURNS [before, after: Slice];
InsertPrefix:
PROC [first, last: Slice, firstLen:
NAT]
RETURNS [new: Slice];
new[i]=first[i] for i in [0..firstLen)
new[i+firstLen]=last[i] for i in [0..last.length)
new.length=last.length+firstLen
DeletePrefix:
PROC [slice: Slice, depth:
NAT];
SliceLength: PROC [slice: Slice] RETURNS [length: NAT] = INLINE { RETURN [slice.length] };
SliceNode:
PROC [slice: Slice, index:
NAT]
RETURNS [Ref] =
INLINE {
RETURN [slice[index]] };
LastOfSlice:
PROC [slice: Slice]
RETURNS [Ref] =
INLINE {
RETURN [slice[slice.length-1]] };
CompareSliceOrder: PROC [s1, s2: Slice] RETURNS [order: Order];
SliceOrder:
PROC [alpha, beta: TiogaTreeOps.BranchSpan, aBefore, aBottom, bBefore, bBottom: Slice]
RETURNS [overlap: BOOLEAN, head, tail: TiogaTreeOps.BranchSpan, startOrder, endOrder: Order];
END.