program rec_vs_nonrec;
{$mode objfpc}{$H+}
{$MODESWITCH ADVANCEDRECORDS}
uses
SysUtils, DateUtils, gtree, gstack;
type
TIntTree = specialize TTree<Integer>;
TTreeNode = TIntTree.TTreeNodeType;
TStack = specialize TStack<TTreeNode>;
TChildEnum = TTreeNode.TTreeNodeList.TEnumerator;
TEnumNode = record
Node: TTreeNode;
Enum: TChildEnum;
Visited: Boolean;
constructor Create(aNode: TTreeNode);
end;
PEnumNode = ^TEnumNode;
TEnumStack = specialize TStack<TEnumNode>;
constructor TEnumNode.Create(aNode: TTreeNode);
begin
Node := aNode;
Visited := False;
end;
var
Tree: TIntTree = nil;
TreeSize, I: Integer;
StartTime: TDateTime;
function GenRandomTree: TIntTree;
var
NodeStack, ChildStack, Tmp: TStack;
Node, Child: TTreeNode;
I, J: Integer;
begin
Result := TIntTree.Create;
Result.Root := TTreeNode.Create;
Inc(TreeSize);
NodeStack := TStack.Create;
ChildStack := TStack.Create;
try
NodeStack.Push(Result.Root);
for I := 1 to 10 do
begin
while NodeStack.Size > 0 do
begin
Node := NodeStack.Top;
NodeStack.Pop;
for J := 1 to Random(9)+1 do
begin
Child := TTreeNode.Create;
Inc(TreeSize);
Node.Children.PushBack(Child);
ChildStack.Push(Child);
end;
end;
Tmp := NodeStack;
NodeStack := ChildStack;
ChildStack := Tmp;
end;
finally
NodeStack.Free;
ChildStack.Free;
end;
end;
procedure DfsTraversal(aTree: TIntTree); //iterative
var
Stack: TEnumStack;
Next: TTreeNode;
Curr: PEnumNode;
begin
if not Assigned(aTree.Root) then
exit;
Stack := TEnumStack.Create;
try
Stack.Push(TEnumNode.Create(aTree.Root));
while Stack.Size > 0 do
begin
Curr := Stack.TopItem;
if not Curr^.Visited then
begin
Curr^.Visited := True;
Curr^.Enum := Curr^.Node.Children.GetEnumerator;
end;
if Curr^.Enum.MoveNext then
begin
Next := Curr^.Enum.Current;
Stack.Push(TEnumNode.Create(Next));
end
else
begin
Curr^.Enum.Free;
Stack.Pop;
end;
end;
finally
Stack.Free;
end;
end;
procedure DfsTraversalR(aTree: TIntTree);
procedure Dfs(aNode: TTreeNode);
var
Child: TTreeNode;
begin
for Child in aNode.Children do
Dfs(Child);
end;
begin
if Assigned(aTree.Root) then
Dfs(aTree.Root);
end;
begin
Randomize;
for I := 1 to 10 do
begin
TreeSize := 0;
Tree := GenRandomTree;
try
WriteLn('generated new tree with ', TreeSize, ' nodes');
StartTime := Time;
DfsTraversal(Tree);
WriteLn('non-recursive DFS: ', MillisecondsBetween(Time, StartTime), 'ms');
StartTime := Time;
DfsTraversalR(Tree);
WriteLn('recursive DFS: ', MillisecondsBetween(Time, StartTime), 'ms');
WriteLn;
finally
Tree.Free;
end;
end;
end.