home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / pascal / library / dos / arrays / generics / maxarray / maxarray.doc < prev    next >
Encoding:
Text File  |  1989-07-24  |  10.7 KB  |  256 lines
  1. {
  2.  
  3. ******  The MaxArray and GenericHeap Objects (and Descendants) *****
  4.  
  5.  
  6. Design and Implementation ---  Eric C. Wentz
  7.  
  8.                                1-703-860-3807
  9.  
  10.                                2374 Antiqua Court
  11.                                Reston, Va. 22091
  12.  
  13.  
  14. Last Modification Date : 7-22-89
  15.  
  16.  
  17. ********************************************************************
  18.  
  19.  
  20. Design Objective(s):
  21.  
  22.        (1) {MaxArray}
  23.  
  24.            Implementation of a fully Generic Array-like Object,
  25.            Capable of all Array functions, but not limited by the
  26.            Segment-size limitation imposed by Turbo Pascal (65521 bytes).
  27.            Additionally, the Object should be capable of Dynamic
  28.            allocation and de-allocation to enhance RAM utilization efficiency.
  29.  
  30.        (2) {GenericHeap}
  31.  
  32.            Implementation of a fully Generic Heap Object, capable
  33.            of all Heap functions for any Data type (including a
  34.            user-defineable collating sequence), including Records and Objects,
  35.            to facilatate sorting, creation of Priority-Queues and other
  36.            uses for which a Heap is a useful Data structure.
  37.  
  38.  
  39. Limitations:
  40.  
  41.            As the MaxArray and the GenericHeap are fundamentally defined
  42.            by use of Dynamically allocated arrays of un-typed bytes, it is
  43.            only possible to define them for similar-sized constituents.  In
  44.            particular it will not be possible to declare a MaxArray of
  45.            Ancestor-Objects and then use it to contain different-sized
  46.            Descendant Objects.  The user should be able to get around this by
  47.            declaring a MaxArray of pointers to such objects, but I have not
  48.            made any attempts to test this.
  49.  
  50.            As (I believe) Turbo allocates the same number of bytes for each
  51.            variant of a Variant record, there should be no problems with
  52.            variant records.
  53.  
  54. ***************************************************************************
  55. Implementation {MaxArray} :
  56. ***************************************************************************
  57.  
  58.   Unit HugeAray; { Huge Generic Dynamic Arrays }
  59.  
  60.   { NOTE: MaxArrays are Indexed 0..MaxSize-1 }
  61.  
  62.   { All similarities to the FlexArray Object are entirely deliberate. With }
  63.   { the notable exception of the lack of Re-Sizing capability, MaxArrays   }
  64.   { should be entirely trivial substitutions for FlexArrays.               }
  65.  
  66.   INTERFACE {NOT the complete Interface of Unit HugeAray, but all needed
  67.                  definitions are reproduced here.}
  68.   Type
  69.     MaxArray = Object
  70.  
  71.       Procedure Create; {All MaxArrays *MUST* be CREATEd exactly ONCE,
  72.                          and BEFORE ANY other operations are performed!!!!}
  73.  
  74.       Procedure Init (MaxElements : LongInt; ElementSize : Word);
  75.  
  76.                      {Once CREATEd, or DESTROYed, a MaxArray may be
  77.                       INITed to any desired number of elements}
  78.  
  79.       Procedure Destroy; {Return all memory for given MaxArray to the Heap.}
  80.  
  81.       Procedure Accept (Var El; Index : LongInt; Size : Word);
  82.                                        {Assign the Indexth El}
  83.  
  84.       Procedure Retrieve (Var El; Index : LongInt; Size : Word);
  85.                                          {Get the Indexth El}
  86.  
  87.       Procedure Copy (From : MaxArray);
  88.                               {Target *MUST* already be initialized}
  89.                               {to the EXACT same parameters as From}
  90.                               {this will save checking for sufficent}
  91.                               {available Memory!}
  92.  
  93.       Procedure Swap (I,J : LongInt); {Swap the Ith and Jth Elements}
  94.  
  95.       Function MaxSize : LongInt;   {Report Array Length}
  96.       Function ElemSize : Word;  {Report Element Size}
  97.  
  98.     End;
  99.  
  100. IMPLEMENTATION { Not Reproduced }
  101.  
  102.  
  103. ***************************************************************************
  104. Implementation {GenericHeap} :
  105. ***************************************************************************
  106.  
  107. Unit MGenHeap; { MaxArray-Based Generic Heaps }
  108.  
  109. { GenericHeaps are indexed 1..MaxElements, rather then 0..MaxElements-1 }
  110.  
  111.  
  112. INTERFACE {NOT the complete Interface of the MGenHeap unit,
  113.                but all needed definitions are reproduced.}
  114. Type
  115.   GenericHeap = Object (MaxArray)
  116.  
  117.                   Procedure Init (MaxElements : LongInt; ElementSize : Word;
  118.                                   GreaterFunc : SortFunc);
  119.  
  120.                   { Accept, Retrieve, and Swap are only redefined to      }
  121.                   { implement the 1..MaxElement indexing needed for Heaps }
  122.  
  123.                   Procedure Accept (Var El; Index : LongInt; Size : Word);
  124.  
  125.                   Procedure Retrieve (Var El; Index : LongInt; Size : Word);
  126.  
  127.                   Procedure Swap (I,J : LongInt);
  128.  
  129.                   Procedure SiftDown (I,J : LongInt);
  130.                                      { While I can think of No reason to  }
  131.                                      { Use SiftDown externally, there may }
  132.                                      { be a reason, so I have exported it }
  133.  
  134.                   Procedure SiftUp (Var El; Index : LongInt; Size : Word);
  135.                                    { SiftUp can be used in place of Accept }
  136.                                    { In order to Create/Maintain a Heap as }
  137.                                    { a Heap while adding elements, thus    }
  138.                                    { allowing the use of Sort instead of   }
  139.                                    { HeapSort which structures a Heap by   }
  140.                                    { using BuildHeap.                      }
  141.  
  142.                   Procedure BuildHeap;
  143.                                    { Creates the Heap structure from }
  144.                                    { the ground up.                  }
  145.                   Procedure Sort;
  146.                             { Sorts a Heap into Ascending order    }
  147.                             { Assumes HEAP is built or maintained. }
  148.  
  149.                   Procedure ChangeSort (NewSort : SortFunc);
  150.  
  151.                             { Permits the changing of sorting methods   }
  152.                             { such as might be required for sorting     }
  153.                             { records by a different field, for example }
  154.  
  155.                   { NOTE: This will require use of HeapSort to re-sort. }
  156.  
  157.                   Procedure HeapSort;
  158.                             { Sorts a Heap into Ascending order     }
  159.                             { Assumes nothing about Heap structure. }
  160.  
  161.                   Procedure Copy (From : GenericHeap);
  162.                             { Target Heap *MUST* be initialized  }
  163.                             { to EXACTLY same parameters as From }
  164.                 End;
  165.  
  166. IMPLEMENTATION { Not Reproduced }
  167.  
  168. **************************************************************************
  169.  { UNIT DEPENDENCIES }
  170. **************************************************************************
  171.  
  172.         FlexPntr          SrtFuncs
  173.            |    \          /  |
  174.            |     \        /   |
  175.         HugeAray  \      /    |
  176.         /      \   \    /     |
  177.        /        \   \  /      |
  178.       /          \   \/       |
  179.    H_Arrays      MGenHeap     |
  180.                          \    |
  181.                           \   |
  182.                            \  |
  183.                             \ |
  184.                              \|
  185.                             Heaps
  186.  
  187. ****************************************************************************
  188.  { ERROR MESSAGES }
  189. ****************************************************************************
  190.  
  191.     I have made considerable effort to anticipate all possible errors when
  192. manipulating MaxArrays, and have incorporated a simple error procedure into
  193. the implementation section of unit HugeAray.  It prints a simple diagnostic
  194. message to the screen and HALTs the program.  This "bonehead" strategy seems
  195. to be sufficient for three reasons: (1) I BELIEVE that ALL conceivable errors
  196. will be due to developmental errors.  (2) I dislike the necessity of passing
  197. boolean "fail" variables.  (3) Enough statistical information methods are
  198. provided to enable the user to define more sophisticated error checking and
  199. recovery methods, if such is desired or needed by some situation which I have
  200. not anticipated.
  201.  
  202. POSSIBLE ERROR MESSAGES:
  203.  
  204.             Attempted Init on Un-Created or Initialized MaxArray.
  205.  
  206.             Insufficient Memory for Requested MaxArray.
  207.  
  208.             Attempted Accept with Incorrect Size Variable.
  209.  
  210.             Attempted Accept on Un-Initialized MaxArray.
  211.  
  212.             Attempted Retrieve with Incorrect Size Variable.
  213.  
  214.             Attempted Retrieve with Un-Initialized MaxArray.
  215.  
  216.             ***** INDEX OUT OF BOUNDS *****
  217.  
  218.             Attempted Copy on Un-Created or Initialized MaxArray.
  219.  
  220.             Attempted Illegal Copy operation. { PROBABLY wrong data size... }
  221.  
  222.             Insufficient Memory for requested MaxArray.
  223.  
  224.  
  225.   { To be honest, I must add that I may very easily have overlooked something.
  226.     If you find such an error, please write and let me know!!! }
  227.  
  228.  
  229. ******************************************************************************
  230.  { PROPRIETARY CODE }
  231. ******************************************************************************
  232.  
  233. Since the only significantly original work in these units is in MGenHeap and
  234. HugeAray, I have elected not to distribute these in source form.  In fact, the
  235. source for these should be completely unnecessary.  However, if you really
  236. want it, you can convince me by sending me a check for $20.00 at the above
  237. address.
  238.  
  239. As to the FlexPntr unit.  ALL the code in it was either directly taken from
  240. an article in PROGRAMMERS JOURNAL by Tom Swann or inspired by the same article
  241. (Programming on the Variant Express PJ V6.5 Sept/Oct 1988), and is of such a
  242. fundamental nature that no changes are really possible or desireable in ANY
  243. context.  I have distributed it as a TPU simply because Turbo has no other
  244. method available for PRIVATE declarations (ala ADA).  Therefore, since I did
  245. not really originate the code, and since there is no reason to ever change
  246. any of it, I will NOT distribute the source code for any reason.  Those
  247. incureably interested individuals should look up the above article, paying
  248. particular attention to Mr. Swann's definitions of IntPtr and IntRec, which
  249. I have renamed "FlexPtr" and "FlxArray" respectively.  NOTE: the array which
  250. Mr. Swann defines within the IntRec is referenced with field name "Flex" in
  251. my version of the construct, and is an array of Bytes, not Integers.
  252.  
  253. ******************************************************************************
  254. ******************************************************************************
  255. ******************************************************************************
  256.