home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / pascal / library / dos / arrays / generics / generics.doc
Encoding:
Text File  |  1989-07-29  |  6.9 KB  |  133 lines
  1.                Eric C. Wentz
  2.  
  3.                1-703-860-3807  {evenings before 11 p.m. Eastern}
  4.  
  5.                CompuServe ID: 72070,1015
  6.  
  7.                2374 Antiqua Court
  8.                Reston, Va.  22091
  9.  
  10.  
  11.  
  12. General Notes on the Included Archives:
  13.  
  14.    One of the most important ideas behind OOP is that of code
  15. re-useability.  One important facet of this concept that seems to
  16. be missing in Turbo's OOP extensions is that of Genericity.  To
  17. produce generally useful, re-usable code, it is important to be
  18. able to implement abstract concepts (or datastructures) that are
  19. independent of datatype.  For example, consider the simple abstract
  20. concept of a Stack.  The operations needed for a Stack are well known
  21. to all programmers.  All Stacks implement Push,Pop,Top,Full,Empty and
  22. maybe Depth.  Genericity gives us a way to define this abstractly,
  23. and Inheritance gives us the way to implement useable Stacks, such
  24. as IntStacks, RealStacks, RecordStacks etc., with minimal extra coding.
  25. In other words, by defining the abstract concept and utilizing it,
  26. we can forget about the implementation details and achieve yet another
  27. useful layer of abstraction in program design.
  28.  
  29.    As the designer of the Eiffel programming language, Dr. Bertrand Meyer
  30. argues, the true strengths of OOP will be realized by a Bottom-Up approach
  31. to programming design (I can hear the Priests of Top-Down design chanting
  32. evil thoughts even now!).  By designing and implementing low-level,
  33. generally useable Objects, we can avoid constantly reinventing that which
  34. has already been adequately designed and implemented elsewhere.  The true
  35. power of OOP will not be realized until such time as there exists a large
  36. body of such Objects from which to draw upon when coding specific
  37. applications.  The included packages are my (first) contribution to this
  38. idea.  I give them to the public domain in the hopes that others will also
  39. undertake to build such low level, generally useable Objects to an ever
  40. growing library of such code.
  41.  
  42. SPECIFIC NOTES:
  43.  
  44. FlexArrays.
  45.  
  46. The FlexArray is a simple analog of the native Array structure.  It (as with
  47. the native array) is limited by Turbo to a length of 65521 bytes, but
  48. it is somewhat more flexible in that it is dynamically sized, and may
  49. be dynamically resized as well.  A FlexArray can be initialized to any
  50. datatype.  In fact, through reinitializing, it is possible to use one
  51. FlexArray variable to contain any number of different datatypes (one at
  52. a time) within the same program, though from a Software Engineering
  53. viewpoint, I don't recommend this practice.  If FlexArrays perform
  54. slower then native arrays, it is only marginally so, and due to the
  55. difference between Data Segment access times vs. Heap access times.
  56.  
  57. FlexStacks.
  58.  
  59. The FlexStack uses the FlexArray as its base type, and is subject to the
  60. same limitations and capabilities as the FlexArray.
  61.  
  62. MaxArray.
  63.  
  64. The MaxArray is (sort of) an extension of the FlexArray.  MaxArrays can
  65. be allocated to a maximum size of 655210 bytes (theoretically), as
  66. currently implemented.  As this maximum will not be available to any
  67. programs running under DOS, the MaxArray is actually limited only by
  68. available Heap space.  The only FlexArray method unsupported by MaxArrays
  69. is that of resizing.  MaxArrays are implemented by mapping the virtual
  70. (visible) index onto one of 10 distinct FlexArrays.  This makes the resize
  71. operation extremely complex, and in my judgement impractical and unnecessary.
  72. Further, this mapping will also slow the MaxArray's performance, perhaps by
  73. a noticeable margin over that of the FlexArray.  The old trade-off again,
  74. Space vs. Speed, but the MaxArray is not really too bad.
  75.  
  76. GenericHeap.
  77.  
  78. The GenericHeap uses the MaxArray as its base type, and is subject to the
  79. same limitations and capabilities as the MaxArray.  Additionally, when
  80. initializing a GenericHeap, a function must be provided which determines
  81. the sequencing of items in the GenericHeap.  This function may be changed
  82. during run-time to provide sorting or prioritization by different keys
  83. when the Heaped items are records -- see unit SortFunc for examples.
  84. In a test program, I used the GenericHeap to sort 250,000 integers on my
  85. humble little 8088 based clone (6.44 mhz of BLAZING "Turbo" speed!).  The
  86. sort took just over 9 hours, which I thought was pretty good, all things
  87. considered!  The Heap structure itself was built (using the SiftUp operation)
  88. in under an hour, which implies to me that priority queues of such titanic
  89. size would be found to be quite practical.  Certainly such queues of only
  90. say, 10,000 records will have very satisfying performance.
  91.  
  92.  
  93. A COMMENT ON "PROPRIETARY" CODE INCLUDED WITH THE ABOVE PACKAGES:
  94.  
  95. I feel that the above packages are complete, with no benefits to be had
  96. by modification.  In the spirit of creating a "global" library of generally
  97. useable objects, they SHOULD not EVER be modified, but should remain
  98. "Private".  Distributing them only as TPU's guarantees this.  You may
  99. cynically note that I have offered the source code for a small sum, but this
  100. is intended only to discourage the distribution.  Keeping modifications
  101. out of existence will only serve to enhance the standardization of code
  102. using such a library.  I don't want your money, I want you to use my
  103. packages as they were intended to be used!
  104.  
  105.  
  106. To seemingly reverse myself immediately, I have included ALL the source code
  107. for the GenDatum,GenList and derivative Objects.  This is because I am NOT
  108. so convinced of their completeness as with the others.  For example, the
  109. SWAP method in Unit LGenHeap is quite slow, and could no doubt be improved
  110. {I have noted this in the source file}.  Additionally, you may have need of
  111. only a singly-linked list, and having the source for the GenDatum object
  112. and the DoubLink derivative, AND the GenList Object should help you design
  113. it.  For that matter, what about Generic Trees (Binary and otherwise)? Again,
  114. having the source for these units should provide useful design methods.
  115. The only code here I would like to see remain untampered-with is the GenDatum
  116. itself, but even there somebody wiser than I may be able to truly improve it,
  117. so I have included it as well.
  118.  
  119. FINAL NOTE:
  120.  
  121. The truly important aspect of all these packages is that of Genericity.  By
  122. utilizing this concept in the design of other Objects, we can (hopefully)
  123. create a foundation of standardized, powerful, reliable Objects upon which
  124. we can build easily maintained and modifiable applications.  As the Prophets
  125. of OOP would say, "welcome to the future of Software Engineering"!
  126.  
  127. FINAL FINAL NOTE:
  128.  
  129. I am currently working on a derivative of the MaxArray which will allow
  130. N-Dimensional arrays, and on a similar (but not derivative) Object which
  131. will be a Virtual array limited only by disksize (NOT 32 Mbytes!).  The
  132. former is almost complete, but the latter is only embryonic.  Look for
  133. them sometime around Mid-August. -- ECW