home *** CD-ROM | disk | FTP | other *** search
/ Delphi Magazine Collection 2001 / Delphi Magazine Collection 20001 (2001).iso / DISKS / Issue70 / alfresco / AAIntDeq.pas next >
Encoding:
Pascal/Delphi Source File  |  2001-05-08  |  2.9 KB  |  120 lines
  1. {*********************************************************}
  2. {* AAIntDeq                                              *}
  3. {* Copyright (c) Julian M Bucknall 2001                  *}
  4. {* All rights reserved.                                  *}
  5. {*********************************************************}
  6. {* Algorithms Alfresco: A deque for integers             *}
  7. {*********************************************************}
  8.  
  9. {Note: this unit is released as freeware. In other words, you are free
  10.        to use this unit in your own applications, however I retain all
  11.        copyright to the code. JMB}
  12.  
  13. unit AAIntDeq;
  14.  
  15. interface
  16.  
  17. uses
  18.   Classes;
  19.  
  20. type
  21.   TaaIntDeque = class
  22.     private
  23.       FList : TList;
  24.       FHead : integer;
  25.       FTail : integer;
  26.     protected
  27.       procedure idGrow;
  28.     public
  29.       constructor Create(aCapacity : integer);
  30.       destructor Destroy; override;
  31.  
  32.       function IsEmpty : boolean;
  33.  
  34.       procedure Enqueue(aValue : integer);
  35.       procedure Push(aValue : integer);
  36.       function Pop : integer;
  37.   end;
  38.  
  39. implementation
  40.  
  41. uses
  42.   SysUtils;
  43.  
  44. {===TaaIntDeque======================================================}
  45. constructor TaaIntDeque.Create(aCapacity : integer);
  46. begin
  47.   inherited Create;
  48.   FList := TList.Create;
  49.   FList.Count := aCapacity;
  50.   {let's help out the user of the deque by putting the head and tail
  51.    pointers in the middle: it's probably more efficient}
  52.   FHead := aCapacity div 2;
  53.   FTail := FHead;
  54. end;
  55. {--------}
  56. destructor TaaIntDeque.Destroy;
  57. begin
  58.   FList.Free;
  59.   inherited Destroy;
  60. end;
  61. {--------}
  62. procedure TaaIntDeque.Enqueue(aValue : integer);
  63. begin
  64.   FList.List^[FTail] := pointer(aValue);
  65.   inc(FTail);
  66.   if (FTail = FList.Count) then
  67.     FTail := 0;
  68.   if (FTail = FHead) then
  69.     idGrow;
  70. end;
  71. {--------}
  72. procedure TaaIntDeque.idGrow;
  73. var
  74.   OldCount : integer;
  75.   i, j     : integer;
  76. begin
  77.   {grow the list by 50%}
  78.   OldCount := FList.Count;
  79.   FList.Count := (OldCount * 3) div 2;
  80.   {expand the data into the increased space, maintaining the deque}
  81.   if (FHead = 0) then
  82.     FTail := OldCount
  83.   else begin
  84.     j := FList.Count;
  85.     for i := pred(OldCount) downto FHead do begin
  86.       dec(j);
  87.       FList.List^[j] := FList.List^[i]
  88.     end;
  89.     FHead := j;
  90.   end;
  91. end;
  92. {--------}
  93. function TaaIntDeque.IsEmpty : boolean;
  94. begin
  95.   Result := FHead = FTail;
  96. end;
  97. {--------}
  98. procedure TaaIntDeque.Push(aValue : integer);
  99. begin
  100.   if (FHead = 0) then
  101.     FHead := FList.Count;
  102.   dec(FHead);
  103.   FList.List^[FHead] := pointer(aValue);
  104.   if (FTail = FHead) then
  105.     idGrow;
  106. end;
  107. {--------}
  108. function TaaIntDeque.Pop : integer;
  109. begin
  110.   if FHead = FTail then
  111.     raise Exception.Create('Integer deque is empty: cannot pop');
  112.   Result := integer(FList.List^[FHead]);
  113.   inc(FHead);
  114.   if (FHead = FList.Count) then
  115.     FHead := 0;
  116. end;
  117. {====================================================================}
  118.  
  119. end.
  120.