Changeset 447 for trunk/IPQ.pas

Timestamp:

May 19, 2022, 10:39:34 PM (2 years ago)

Author:

chronos

Message:

• Modified: Use first capital letter in identifiers.

File:

• trunk/IPQ.pas (modified) (6 diffs)

trunk/IPQ.pas

@@ -1 +1 @@
 { binary heap priority queue
-  code contributed by Rassim Eminli }
+  Code contributed by Rassim Eminli }
 
 {$INCLUDE Switches.inc}
@@ -8 +8 @@
 
 type
-  TIntegerArray = array [0 .. $40000000 div sizeof(integer)] of integer;
+  TIntegerArray = array [0 .. $40000000 div SizeOf(Integer)] of Integer;
   PIntegerArray = ^TIntegerArray;
 
   TheapItem = record
-    Item: integer;
-    Value: integer;
+    Item: Integer;
+    Value: Integer;
   end;
 
-  TItemArray = array [0 .. $40000000 div sizeof(TheapItem)] of TheapItem;
+  TItemArray = array [0 .. $40000000 div SizeOf(TheapItem)] of TheapItem;
   PItemArray = ^TItemArray;
 
   TIPQ = class
-    constructor Create(max: integer);
+    constructor Create(Max: Integer);
     destructor Destroy; override;
     procedure Empty;
-    function Put(Item, Value: integer): boolean;
-    function TestPut(Item, Value: integer): boolean;
-    function Get(var Item, Value: integer): boolean;
+    function Put(Item, Value: Integer): Boolean;
+    function TestPut(Item, Value: Integer): Boolean;
+    function Get(var Item, Value: Integer): Boolean;
   private
     // n - is the size of the heap.
     // fmax - is the max size of the heap.
-    n, fmax: integer;
+    N, fmax: Integer;
 
     // bh - stores (Value, Item) pairs of the heap.
@@ -39 +39 @@
 implementation
 
-constructor TIPQ.Create(max: integer);
+constructor TIPQ.Create(Max: Integer);
 begin
   inherited Create;
-  fmax := max;
-  GetMem(bh, fmax * sizeof(TheapItem));
-  GetMem(Ix, fmax * sizeof(integer));
-  n := -1;
+  fmax := Max;
+  GetMem(bh, fmax * SizeOf(TheapItem));
+  GetMem(Ix, fmax * SizeOf(Integer));
+  N := -1;
   Empty;
 end;
@@ -58 +58 @@
 procedure TIPQ.Empty;
 begin
-  if n <> 0 then
+  if N <> 0 then
   begin
-    FillChar(Ix^, fmax * sizeof(integer), 255);
-    n := 0;
+    FillChar(Ix^, fmax * SizeOf(Integer), 255);
+    N := 0;
   end;
 end;
 
 // Parent(i) = (i-1)/2.
-function TIPQ.Put(Item, Value: integer): boolean; // O(lg(n))
+function TIPQ.Put(Item, Value: Integer): Boolean; // O(lg(n))
 var
-  i, j: integer;
+  I, J: Integer;
   lbh: PItemArray;
   lIx: PIntegerArray;
@@ -74 +74 @@
   lIx := Ix;
   lbh := bh;
-  i := lIx[Item];
-  if i >= 0 then
+  I := lIx[Item];
+  if I >= 0 then
   begin
-    if lbh[i].Value <= Value then
+    if lbh[I].Value <= Value then
     begin
-      result := False;
-      exit;
+      Result := False;
+      Exit;
     end;
   end
   else
   begin
-    i := n;
-    Inc(n);
+    I := N;
+    Inc(N);
   end;
 
-  while i > 0 do
+  while I > 0 do
   begin
-    j := (i - 1) shr 1; // Parent(i) = (i-1)/2
-    if Value >= lbh[j].Value then
-      break;
-    lbh[i] := lbh[j];
-    lIx[lbh[i].Item] := i;
-    i := j;
+    J := (I - 1) shr 1; // Parent(i) = (i-1)/2
+    if Value >= lbh[J].Value then
+      Break;
+    lbh[I] := lbh[J];
+    lIx[lbh[I].Item] := I;
+    I := J;
   end;
   // Insert the new Item at the insertion point found.
-  lbh[i].Value := Value;
-  lbh[i].Item := Item;
-  lIx[lbh[i].Item] := i;
-  result := True;
+  lbh[I].Value := Value;
+  lbh[I].Item := Item;
+  lIx[lbh[I].Item] := I;
+  Result := True;
 end;
 
-function TIPQ.TestPut(Item, Value: integer): boolean;
+function TIPQ.TestPut(Item, Value: Integer): Boolean;
 var
-  i: integer;
+  I: Integer;
 begin
-  i := Ix[Item];
-  result := (i < 0) or (bh[i].Value > Value);
+  I := Ix[Item];
+  Result := (I < 0) or (bh[I].Value > Value);
 end;
 
 // Left(i) = 2*i+1.
 // Right(i) = 2*i+2 => Left(i)+1
-function TIPQ.Get(var Item, Value: integer): boolean; // O(lg(n))
+function TIPQ.Get(var Item, Value: Integer): Boolean; // O(lg(n))
 var
-  i, j: integer;
-  last: TheapItem;
+  I, J: Integer;
+  Last: TheapItem;
   lbh: PItemArray;
 begin
-  if n = 0 then
+  if N = 0 then
   begin
-    result := False;
-    exit;
+    Result := False;
+    Exit;
   end;
 
@@ -133 +133 @@
   Ix[Item] := -1;
 
-  dec(n);
-  if n > 0 then
+  Dec(N);
+  if N > 0 then
   begin
-    last := lbh[n];
-    i := 0;
-    j := 1;
-    while j < n do
+    Last := lbh[N];
+    I := 0;
+    J := 1;
+    while J < N do
     begin
       // Right(i) = Left(i)+1
-      if (j < n - 1) and (lbh[j].Value > lbh[j + 1].Value) then
-        Inc(j);
-      if last.Value <= lbh[j].Value then
-        break;
+      if (J < N - 1) and (lbh[J].Value > lbh[J + 1].Value) then
+        Inc(J);
+      if Last.Value <= lbh[J].Value then
+        Break;
 
-      lbh[i] := lbh[j];
-      Ix[lbh[i].Item] := i;
-      i := j;
-      j := j shl 1 + 1; // Left(j) = 2*j+1
+      lbh[I] := lbh[J];
+      Ix[lbh[I].Item] := I;
+      I := J;
+      J := J shl 1 + 1; // Left(j) = 2*j+1
     end;
 
     // Insert the root in the correct place in the heap.
-    lbh[i] := last;
-    Ix[last.Item] := i;
+    lbh[I] := Last;
+    Ix[Last.Item] := I;
   end;
-  result := True;
+  Result := True;
 end;