// Generic CLR stacks are defined in the System assembly. <pragma:references("system")> <pragma:target("dll")> // We are using pragmas as a temporal measure. // In the final version, we'll do this using "projects". using System, System.Collections.Generic; namespace Freya.DataStructures.Trees; public BinaryTree = class[X(IComparable)] public Visitor = method(Obj: X; Level: Integer); protected TreeNode = class; Root: TreeNode; public method Add(AValue: X); ensures Contains(AValue); method Contains(AValue: X): Boolean; iterator Preorder: X; method Visit(Action: Visitor); end; BinaryTree[X].TreeNode = class public constructor(AValue: X); property Value: X; readonly; property Left, Right: TreeNode; method Contains(AValue: X): TreeNode; method Visit(Action: Visitor; Level: Integer); end; implementation for BinaryTree[X].TreeNode is constructor(AValue: X); begin Value := AValue; end; method Contains(AValue: X): TreeNode; begin var Rslt := AValue.CompareTo(Self.Value); if Rslt = 0 then Result := Self else begin Result := nil; if Rslt < 0 then begin if Left <> nil then Result := Left.Contains(AValue); end else if Right <> nil then Result := Right.Contains(AValue); end; end; method Visit(Action: Visitor; Level: Integer); begin if Left <> nil then Left.Visit(Action, Level + 1); Action(Value, Level); if Right <> nil then Right.Visit(Action, Level + 1); end; implementation for BinaryTree[X] is method Contains(AValue: X): Boolean; // Click here for the compiled IL code! begin Result := Root <> nil and Root.Contains(AValue) <> nil; end; method Add(AValue: X); var Parent, Current: TreeNode; begin Parent := nil; Current := Root; while Current <> nil and Current.Value.CompareTo(AValue) <> 0 do begin Parent := Current; if AValue.CompareTo(Current.Value) < 0 then Current := Current.Left else Current := Current.Right; end; if Current = nil then begin Current := new TreeNode(AValue); if Parent = nil then Root := Current else if AValue.CompareTo(Parent.Value) < 0 then Parent.Left := Current else Parent.Right := Current; end; end; method Visit(Action: Visitor); begin if Root <> nil then Root.Visit(Action, 0); end; iterator PreOrder: X; var St: Stack[TreeNode]; begin if Root <> nil then begin St := new Stack[TreeNode]; St.Push(Root); repeat var t := St.Pop; if t.Right <> nil then St.Push(t.Right); if t.Left <> nil then St.Push(t.Left); yield t.Value; until St.Count = 0; end; end; end.