-- File: ScriptTreeImpl.mesa - last edit by
-- Karlton:	16-Aug-82 15:49:42

DIRECTORY
  ScriptTree USING [
    Direction, EnumerateOrder, ErrorCode, Handle, Object];
  
  ScriptTreeImpl: PROGRAM EXPORTS ScriptTree = {
  
  Error: PUBLIC ERROR [code: ScriptTree.ErrorCode] = CODE;
  
  Handle: TYPE = ScriptTree.Handle;
  TreeHandle: TYPE = LONG POINTER TO TreeObject;
  TreeObject: PUBLIC TYPE = RECORD [
    enumerators: CARDINAL ← 0,
    root: Handle ← NIL,
    z: UNCOUNTED ZONE];
    
  Create: PUBLIC PROCEDURE [z: UNCOUNTED ZONE] RETURNS [tree: TreeHandle] = {
    tree ← z.NEW[TreeObject ← [z: z]]};
    
  Destroy: PUBLIC PROCEDURE [tree: TreeHandle] = {
    z: UNCOUNTED ZONE = tree.z;
    IF tree.enumerators # 0 THEN ERROR Error[outstandingEnumerator];
    z.FREE[@tree]};
  
  RootNode: PUBLIC PROCEDURE [tree: TreeHandle] RETURNS [node: Handle] = {
    RETURN[tree.root]};
  
  AddNode: PUBLIC PROCEDURE [tree: TreeHandle, parent, leftSibling: Handle]
    RETURNS [node: Handle] = {
    node ← tree.z.NEW[ScriptTree.Object ← []];
    EnlinkNode[tree, node, parent, leftSibling]};
      
  EnlinkNode: PROCEDURE [tree: TreeHandle, node, parent, leftSibling: Handle] = {
    node.parent ← parent;
    node.leftSibling ← leftSibling;
    IF parent = NIL THEN {
      IF leftSibling # NIL THEN ERROR Error[siblingNotChildOfParent];
      IF tree.root # NIL THEN ERROR Error[alreadyHasRoot];
      tree.root ← node;
      RETURN};
    IF tree.root = NIL THEN ERROR Error[noRoot];
    IF leftSibling # NIL AND leftSibling.parent # parent THEN
      ERROR Error[siblingNotChildOfParent];
    IF leftSibling = NIL THEN {
      node.rightSibling ← parent.child; parent.child ← node}
    ELSE {
      node.rightSibling ← leftSibling.rightSibling;
      leftSibling.rightSibling ← node};
    IF node.rightSibling # NIL THEN node.rightSibling.leftSibling ← node};
      
  MoveNode: PUBLIC PROCEDURE [
    tree: TreeHandle, node, newParent, newLeftSibling: Handle] = {
    DelinkNode[tree, node];
    EnlinkNode[tree, node, newParent, newLeftSibling]};
      
  DelinkNode: PROCEDURE [tree: TreeHandle, node: Handle] = {
    IF node.rightSibling # NIL THEN
      node.rightSibling.leftSibling ← node.leftSibling;
    IF node.leftSibling # NIL THEN
      node.leftSibling.rightSibling ← node.rightSibling;
    IF node.parent = NIL THEN tree.root ← NIL
    ELSE IF node.parent.child = node THEN node.parent.child ← node.rightSibling;
    node.parent ← node.leftSibling ← node.rightSibling ← NIL};
  
  RemoveNode: PUBLIC PROCEDURE [tree: TreeHandle, node: Handle] = {
    IF node = NIL THEN RETURN;
    WHILE node.child # NIL DO RemoveNode[tree, node.child] ENDLOOP;
    DelinkNode[tree, node];
    tree.z.FREE[@node]};
  
  Enumerator: TYPE = LONG POINTER TO EnumerateState;
  EnumerateState: PUBLIC TYPE = RECORD [
    last: Handle ← NIL,
    order: ScriptTree.EnumerateOrder,
    done: BOOLEAN ← FALSE,
    origin: Handle,
    tree: TreeHandle];
    
  Enumerate: PUBLIC PROCEDURE [state: Enumerator] RETURNS [Handle] = {
    IF state = NIL OR state.done THEN RETURN[NIL];
    SELECT state.order FROM
      pre => state.last ← FindNextPreOrder[state];
      end => state.last ← FindNextEndOrder[state];
      ENDCASE => ERROR Error[implementationBug];
    RETURN[state.last]};
    
  FindNextPreOrder: PROCEDURE [state: Enumerator] RETURNS [node: Handle] = {
    SELECT TRUE FROM
      state.last = NIL => RETURN[state.origin];
      state.last.child # NIL => RETURN[state.last.child];
      state.last.rightSibling # NIL => RETURN[state.last.rightSibling];
      ENDCASE;
    WHILE (state.last ← state.last.parent) # state.origin DO
      IF state.last.rightSibling # NIL THEN RETURN[state.last.rightSibling]
      ENDLOOP;
    state.done ← TRUE;
    RETURN[NIL]};
    
  FindEnd: PROCEDURE [node: Handle] RETURNS [son: Handle] = {
    son ← node;
    WHILE son.child # NIL DO son ← son.child ENDLOOP};
    
  FindNextEndOrder: PROCEDURE [state: Enumerator] RETURNS [node: Handle] = {
    tree: TreeHandle = state.tree;
    SELECT TRUE FROM
      state.last = NIL => RETURN[FindEnd[state.origin]];
      state.last.rightSibling # NIL => RETURN[FindEnd[state.last.rightSibling]];
      ENDCASE => {
	state.done ← (state.last.parent = state.origin);
	RETURN[state.last.parent]}};
    
  CreateEnumerator: PUBLIC PROCEDURE [
    tree: TreeHandle, order: ScriptTree.EnumerateOrder, origin: Handle]
    RETURNS [state: Enumerator] = {
    IF tree = NIL THEN RETURN[NIL];
    tree.enumerators ← tree.enumerators + 1;
    state ← tree.z.NEW[EnumerateState ← [
      tree: tree,
      order: order,
      origin: IF origin = NIL THEN tree.root ELSE origin]]};
    
  DestroyEnumerator: PUBLIC PROCEDURE [state: Enumerator] = {
    tree: TreeHandle;
    IF state = NIL THEN RETURN;
    tree ← state.tree;
    tree.enumerators ← tree.enumerators - 1;
    tree.z.FREE[@state]};
    
  SetEnumerator: PUBLIC PROCEDURE [
    state: Enumerator, order: ScriptTree.EnumerateOrder, origin: Handle] = {
    state.origin ← IF origin = NIL THEN state.tree.root ELSE origin;
    state.order ← order;
    state.done ← FALSE};
    
  Walk: PUBLIC PROCEDURE [node: Handle, direction: ScriptTree.Direction]
    RETURNS [newNode: Handle] = {
    IF node = NIL THEN RETURN[NIL];
    RETURN[SELECT direction FROM
      left => node.leftSibling,
      right => node.rightSibling,
      up => node.parent,
      down => node.child,
      ENDCASE => ERROR]};
  
  }. -- of ScriptTreeImpl