diff --git a/src/shared/binheap.pas b/src/shared/binheap.pas
index 968c5f94221e63a73ced2a96a109eda6ff99daf0..50531ed6f453d79044597739bf48d813dfe96c6f 100644 (file)
--- a/src/shared/binheap.pas
+++ b/src/shared/binheap.pas
type
- TBinaryHeapLessFn = function (a, b: TObject): Boolean;
+ // WARNING! don't put structures into heap, use ponters or ids!
+ generic TBinaryHeapBase<ITP> = class(TObject)
+ private
+ type
+ TBinaryHeapLessFn = function (a, b: ITP): Boolean;
- TBinaryHeapObj = class(TObject)
private
- elem: array of TObject;
+ elem: array of ITP;
elemUsed: Integer;
lessfn: TBinaryHeapLessFn;
procedure clear ();
- procedure insert (val: TObject);
+ procedure insert (val: ITP);
- function front (): TObject;
+ function front (): ITP;
procedure popFront ();
property count: Integer read elemUsed;
end;
+type
+ TBinaryHeapObj = specialize TBinaryHeapBase<TObject>;
+ TBinaryHeapInt = specialize TBinaryHeapBase<Integer>;
+
+
+function binHeapNewIntLess (): TBinaryHeapInt;
+function binHeapNewIntGreat (): TBinaryHeapInt;
+
+
implementation
uses
// ////////////////////////////////////////////////////////////////////////// //
-constructor TBinaryHeapObj.Create (alessfn: TBinaryHeapLessFn);
+function intLess (a, b: Integer): Boolean; begin result := (a < b); end;
+function intGreat (a, b: Integer): Boolean; begin result := (a > b); end;
+
+
+function binHeapNewIntLess (): TBinaryHeapInt; begin result := TBinaryHeapInt.Create(@intLess); end;
+function binHeapNewIntGreat (): TBinaryHeapInt; begin result := TBinaryHeapInt.Create(@intGreat); end;
+
+
+// ////////////////////////////////////////////////////////////////////////// //
+constructor TBinaryHeapBase.Create (alessfn: TBinaryHeapLessFn);
begin
if not assigned(alessfn) then raise Exception.Create('wutafuck?!');
lessfn := alessfn;
- SetLength(elem, 8192); // 'cause why not?
+ SetLength(elem, 128); // 'cause why not?
elemUsed := 0;
end;
-destructor TBinaryHeapObj.Destroy ();
+destructor TBinaryHeapBase.Destroy ();
begin
elem := nil;
inherited;
end;
-procedure TBinaryHeapObj.clear ();
+procedure TBinaryHeapBase.clear ();
begin
elemUsed := 0;
end;
-procedure TBinaryHeapObj.heapify (root: Integer);
+procedure TBinaryHeapBase.heapify (root: Integer);
var
smallest, right: Integer;
- tmp: TObject;
+ tmp: ITP;
begin
while true do
begin
end;
-procedure TBinaryHeapObj.insert (val: TObject);
+procedure TBinaryHeapBase.insert (val: ITP);
var
i, par: Integer;
begin
- if (val = nil) then exit;
+ //if (val = nil) then exit;
i := elemUsed;
- if (i = Length(elem)) then SetLength(elem, Length(elem)+16384); // arbitrary number
+ // grow?
+ if (i = Length(elem)) then
+ begin
+ if (i <= 65536) then par := i*2 else par := i+65536; // arbitrary numbers
+ SetLength(elem, par);
+ end;
+ // increase counter
Inc(elemUsed);
+ // insert element
while (i <> 0) do
begin
par := (i-1) div 2; // parent
elem[i] := val;
end;
-function TBinaryHeapObj.front (): TObject;
+function TBinaryHeapBase.front (): ITP;
begin
- if elemUsed > 0 then result := elem[0] else result := nil;
+ if elemUsed > 0 then result := elem[0] else result := Default(ITP);
end;
-procedure TBinaryHeapObj.popFront ();
+procedure TBinaryHeapBase.popFront ();
begin
if (elemUsed > 0) then
begin