home *** CD-ROM | disk | FTP | other *** search
/ PsL Monthly 1993 December / PSL Monthly Shareware CD-ROM (December 1993).iso / prgmming / dos / pascal / exarray.com / XHEAPS.PAS < prev    next >
Encoding:
Pascal/Delphi Source File  |  1989-08-19  |  2.9 KB  |  99 lines
  1. Unit XHeaps;
  2.  
  3. { PERFORMANCE ISSUES }
  4. { The biggest performance drawback to this method of "virtual" array }
  5. { implementation is encountered when each Lobe of the array must be  }
  6. { accessed in turn for a given operation.  This is the case for the  }
  7. { SiftDown operation, in particular.  Thus, BuildHeap and SiftDown   }
  8. { both suffer from large performance problems.  These problems are   }
  9. { decreased as the size of array elements grows, and as the "load    }
  10. { factor" (percent of array in Buffer) increases.  Though I have not }
  11. { tested it, I expect that an array of 1000 records, each of 1000 or }
  12. { more bytes, would have very satisfactory performance, for example. }
  13.  
  14. { If you attempt such a test, I would be very interested in the results! }
  15.  
  16. INTERFACE
  17. Uses XGenHeap,SrtFuncs;
  18.  
  19. { All Heaps additionally inherit the following Methods:
  20.  
  21.   (* ExtendedArray Methods *)
  22.                              Procedure Create;
  23.                              Procedure Destroy;
  24.  
  25.                              Function MaxSize;
  26.                              Function ElemSize;
  27.  
  28.   (* XGenericHeap Methods *)
  29.                              Procedure Swap (I,J : LongInt);
  30.                              Procedure SiftDown (I,J : LongInt);
  31.                              Procedure BuidHeap;
  32.                              Procedure ChangeSort (NewSort : SortFunc);
  33.                              Procedure Sort;
  34.                              Procedure HeapSort;
  35. }
  36.  
  37. Type
  38.   RealHeap = Object (XGenericHeap)
  39.  
  40.                    { Re-Defining these methods re-introduces Types and }
  41.                    { most importantly, Type-Checking to the Generic    }
  42.                    { (typeless) Heap, as well as making the calls more }
  43.                    { "natural" for the actual applications Heaps.      }
  44.  
  45.                    { Follow this pattern when defining your descendant Heaps }
  46.  
  47.  
  48.                    Procedure Init (MaxElements : LongInt);
  49.  
  50.                    Procedure Accept (I : Real; Index : LongInt);
  51.  
  52.                    Function Retrieve (Index : LongInt) : Real;
  53.  
  54.                             { Retrieve will nead to be a procedure for
  55.                               records or objects. }
  56.  
  57.                    Procedure SiftUp (I : Real; Index : LongInt);
  58.  
  59.                    Procedure Copy (From : RealHeap);
  60.             End;
  61.  
  62. IMPLEMENTATION
  63.  
  64. Procedure RealHeap.Init;
  65. Begin
  66.   XGenericHeap.Init (MaxElements,SizeOf(Real),SortReal)
  67. End;
  68.  
  69. Procedure RealHeap.Accept;
  70. Var
  71.   J : Real;
  72. Begin
  73.   J := I;
  74.   XGenericHeap.Accept (J,Index,SizeOf(Real))
  75. End;
  76.  
  77. Function RealHeap.Retrieve;
  78. Var
  79.   J : Real;
  80. Begin
  81.   XGenericHeap.Retrieve (J,Index,SizeOf(Real));
  82.   Retrieve := J
  83. End;
  84.  
  85. Procedure RealHeap.SiftUp;
  86. Var
  87.   J : Real;
  88. Begin
  89.   J := I;
  90.   XGenericHeap.SiftUp (J,Index,SizeOf(Real))
  91. End;
  92.  
  93. Procedure RealHeap.Copy (From : RealHeap);
  94. Begin
  95.   XGenericHeap.Copy (From)
  96. End;
  97.  
  98. BEGIN
  99. END.