blob: ff03f9813d478b3c99d8ef57658de958c8cb66d3 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
|
{
This file is part of the Free Pascal FCL library.
Copyright 2013 Mario Ray Mahardhika
Implements a generic Tree.
See the file COPYING.FPC, included in this distribution,
for details about the copyright.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY;without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
**********************************************************************}
unit gtree;
{$mode objfpc}{$H+}
interface
uses
gvector,gstack,gqueue;
type
{ TTreeNode }
generic TTreeNode<T> = class
public type
TTreeNodeList = specialize TVector<TTreeNode>;
protected
FData: T;
FChildren: TTreeNodeList;
public
constructor Create;
constructor Create(const AData: T);
destructor Destroy; override;
property Data: T read FData write FData;
property Children: TTreeNodeList read FChildren;
end;
generic TDepthFirstCallback<T> = procedure (const AData: T);
generic TBreadthFirstCallback<T> = procedure (const AData: T);
generic TTree<T> = class
public type
TTreeNodeType = specialize TTreeNode<T>;
TDepthFirstCallbackType = specialize TDepthFirstCallback<T>;
TBreadthFirstCallbackType = specialize TBreadthFirstCallback<T>;
private type
TStackType = specialize TStack<TTreeNodeType>;
TQueueType = specialize TQueue<TTreeNodeType>;
private
FRoot: TTreeNodeType;
public
constructor Create;
destructor Destroy; override;
procedure DepthFirstTraverse(Callback: TDepthFirstCallbackType);
procedure BreadthFirstTraverse(Callback: TBreadthFirstCallbackType);
property Root: TTreeNodeType read FRoot write FRoot;
end;
implementation
{ TTreeNode }
constructor TTreeNode.Create;
begin
FChildren := TTreeNodeList.Create;
end;
constructor TTreeNode.Create(const AData: T);
begin
FData := AData;
FChildren := TTreeNodeList.Create;
end;
destructor TTreeNode.Destroy;
var
Child: TTreeNode;
begin
for Child in FChildren do begin
Child.Free;
end;
FChildren.Free;
end;
{ TTree }
constructor TTree.Create;
begin
FRoot := nil;
end;
destructor TTree.Destroy;
begin
FRoot.Free;
end;
procedure TTree.DepthFirstTraverse(Callback: TDepthFirstCallbackType);
var
Stack: TStackType;
Node,Child: TTreeNodeType;
begin
if Assigned(FRoot) then begin
Stack := TStackType.Create;
Stack.Push(FRoot);
while Stack.Size > 0 do begin
Node := Stack.Top;
Stack.Pop;
Callback(Node.Data);
for Child in Node.Children do Stack.Push(Child);
end;
Stack.Free;
end;
end;
procedure TTree.BreadthFirstTraverse(Callback: TBreadthFirstCallbackType);
var
Queue: TQueueType;
Node,Child: TTreeNodeType;
begin
if Assigned(FRoot) then begin
Queue := TQueueType.Create;
Queue.Push(FRoot);
while Queue.Size > 0 do begin
Node := Queue.Front;
Queue.Pop;
Callback(Node.Data);
for Child in Node.Children do Queue.Push(Child);
end;
Queue.Free;
end;
end;
end.
|
