blob: ca8c58df657485a47fa99febac59327a0e24529e (
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
|
unit graphunit;
{$mode objfpc}{$H+}
interface
uses
Classes, SysUtils;
type
tKnoten = class
id: int64;
sigs: tList;
constructor create(i: int64);
destructor destroy; override;
procedure addSig(var bm: tList; i: int64);
end;
function findeKnoten(var bm: tList; id: int64): tKnoten; overload;
function findeKnoten(var bm: tList; kn: tKnoten): tKnoten; overload;
implementation
uses
lowlevelunit;
constructor tKnoten.create(i: int64);
begin
inherited create;
id:=i;
sigs:=tList.create;
end;
destructor tKnoten.destroy;
begin
sigs.free;
end;
procedure tKnoten.addSig(var bm: tList; i: int64);
begin
findeKnoten(sigs,findeKnoten(bm,i));
end;
function findeKnoten(var bm: tList; id: int64): tKnoten; overload;
var
kn: tKnoten;
begin
kn:=tKnoten.create(id);
result:=findeKnoten(bm,kn);
if result<>kn then
kn.free;
end;
function findeKnoten(var bm: tList; kn: tKnoten): tKnoten; overload;
var
mi,ma,i: longint;
begin
mi:=0;
ma:=bm.count-1;
while mi<=ma do begin
i:=(mi+ma) div 2;
if tKnoten(bm[i]).id<kn.id then begin
mi:=i+1;
continue;
end;
if tKnoten(bm[i]).id>kn.id then begin
ma:=i-1;
continue;
end;
if tKnoten(bm[i]).id=kn.id then begin
result:=tKnoten(bm[i]);
exit;
end;
end;
if (mi>=0) and (mi<bm.count) and (tKnoten(bm[mi]).id=kn.id) then begin
result:=tKnoten(bm[mi]);
exit;
end;
if (ma>=0) and (ma<bm.count) and (tKnoten(bm[ma]).id=kn.id) then begin
result:=tKnoten(bm[ma]);
exit;
end;
if mi<>ma+1 then
fehler('Bisektionsfehler: mi<>ma+1!');
result:=kn;
bm.insert(mi,kn);
end;
end.
|
