home *** CD-ROM | disk | FTP | other *** search
/ CD Actual 13 / CDA13.ISO / cdactual / demobin / share / program / Pascal / ASORTS.ZIP / ASORTS.MAN next >
Encoding:
Text File  |  1991-02-28  |  10.3 KB  |  270 lines
  1.                              ASORTS
  2.  
  3.    General-purpose routines for sorting, searching and moving
  4.                   arrays of arbitrary elements.
  5.  
  6.                  Copyright 1991, by J. W. Rider
  7.  
  8.  
  9. ASORTS provides the Turbo Pascal programmer with type
  10. definitions, functions and procedures to handle a variety of
  11. array sorting and searching tasks.  Several of these are
  12. analogous to functions of the same name in the C programming
  13. language:
  14.  
  15.     qsort   --  sort an array
  16.  
  17.     bsearch --  do a binary search of a sorted array for an
  18.                 element that satisfies some key
  19.  
  20.     lfind   --  do a sequential ("linear") search of an unsorted
  21.                 (or sorted) array for an element that satisfies
  22.                 some key
  23.  
  24.     lsearch --  do a sequential search of an unsorted (or sorted)
  25.                 array for an element that satisfies some key.  If
  26.                 the element is not found, then it is appended to
  27.                 the end of the array.
  28.  
  29.     (Non-C programmers: please note that "bsearch" and "lfind" do
  30.     the equivalent task for sorted and unsorted arrays,
  31.     respectively.  It would make more sense to define "bfind" to
  32.     search through a sorted array, and make "bsearch" insert a
  33.     missing element into the array at the right location.
  34.     However, these routines are provided for compatibility in
  35.     converting C programs.)
  36.  
  37. There are some routines that are provided for utility above and
  38. beyond what is available in standard C libraries:
  39.  
  40.     bfind    -- do a binary search of a sorted array for an
  41.                 element that satisfies some key. (This differs
  42.                 from "bsearch" in that is "bfind" reports the
  43.                 "insertion index" if the key element is not
  44.                 found.)
  45.  
  46.     binsert  -- do a binary search of a sorted array for an
  47.                 element that satisfies some key.  If the element
  48.                 is not found, then the key element is inserted in
  49.                 the proper location in the array to maintain the
  50.                 sorted order.
  51.  
  52.     fill     -- moves a single item into all of the elements of
  53.                 an array
  54.  
  55.     shuffle  -- randomly permutes ("unsorts") the elements of an
  56.                 array
  57.  
  58.     subfill  -- moves a single item into all of the elements of a
  59.                 subarray of the base array
  60.  
  61.     submove  -- moves the elements of the source array into a
  62.                 subarray of the destination array (or, the
  63.                 elements of a subarray of the source to the
  64.                 destination array)
  65.  
  66.     xsubmove -- moves the elements of a subarray of the source
  67.                 array into the elements of a subarray of the
  68.                 destination.
  69.  
  70.  
  71. CONCEPTS
  72.  
  73. The ARRAYs to be manipulated are passed as "untyped vars" to
  74. these routines.  (In the "Interface" section, these arrays are
  75. called "base", "source" or "destination".)  These routines will
  76. treat the ARRAYs as if they were declared to be of type:
  77.  
  78.          ArrayType = ARRAY [1..MaxArray] OF ElementType
  79.  
  80. Each ELEMENT of the ARRAY is presumed to be fixed size, and this
  81. size must be passed to the routines.  (In the "Interface"
  82. section, if an ELEMENT needs to passed directly to a routine as
  83. an argument, it is passed as an untyped var called "key".) Also,
  84. the number of elements in the ARRAY must also be passed.  For
  85. instance, to fill an array of real numbers with 0:
  86.  
  87.     var RealArray : array [1..10] of Real;
  88.         x         : real;
  89.  
  90.     x:=0;
  91.     fill(RealArray,10,sizeof(real),x);
  92.  
  93. A SUBARRAY is a "byte-slice" of an array.  For instance, if
  94. "ElementType" is an "array [1..8] of byte", then a "subelement"
  95. would be any contiguous collection of bytes within the
  96. element, like 3,4 and 5.  The SUBARRAY would be the collection of
  97. all of the subelements stored in an ARRAY.  If "ElementType" is a
  98. record of fields, then a "subelement" would be any contigous
  99. group of fields.
  100.  
  101. For sorting and searching, a COMPARISON FUNCTION must be passed
  102. to the routines.  COMPARISON FUNCTIONs take two untyped vars,
  103. return a longint value, and must be declared "far" at
  104. compilation. (DIFFERENT! In C, only an integer-sized value is
  105. returned.)  For instance, to sort the array of real numbers
  106. declared earlier:
  107.  
  108.     function RealCompare(var a,b):longint; far;
  109.     begin
  110.        if real(a)>real(b) then realcompare:=1
  111.        else if real(a)<real(b) then realcompare:=-1
  112.        else realcompare:=0;
  113.     end;
  114.  
  115.     qsort(realarray,10,sizeof(real),realcompare);
  116.  
  117.  
  118.  
  119. INTERFACE
  120.  
  121. type comparefunc = function (var a,b{:element}):longint; {far;}
  122.  
  123.     Declares the type of the comparison function to passed to
  124.     sorting and searching routines. CompareFunc's are
  125.     user-defined functions that takes two arguments a and b. A
  126.     and B must be typeless in the declaration, but otherwise are
  127.     of the same type as the elements of the "base" array. For
  128.     "qsort" and "bsearch", the function needs to return a
  129.     negative integer if "A<B"; a positive integer if "A>B"; and 0
  130.     if "A=B". For "lfind" and "lsearch", the function needs to
  131.     return 0 if "A=B", and some non-zero integer if "A<>B".
  132.  
  133.  
  134. function bfind(var key{:element}, base{:array};
  135.                    length_base, sizeof_element:word;
  136.                    f:comparefunc):longint;
  137.  
  138.     Searches a sorted array for a "key" element. Return the index
  139.     of its location, or the negative of the index of the largest
  140.     element in the array that is smaller than the key (i.e., the
  141.     element that you want to insert the new element after).
  142.  
  143.  
  144. function binsert(var key{:element}, base{:array};
  145.                      length_base, sizeof_element:word;
  146.                      f:comparefunc):longint;
  147.  
  148.    WARNING: This routine overwrites memory if used incorrectly.
  149.  
  150.     Inserts the key element into the correct position of an
  151.     ordered array. Unlike "lsearch", which only adds the key if
  152.     it's not already present, "binsert" ALWAYS inserts a new
  153.     element into the array. "Binsert" returns the index where the
  154.     element is inserted.
  155.  
  156.  
  157. function bsearch(var key{:element}, base{:array};
  158.                      length_base, sizeof_element:word;
  159.                      f:comparefunc):word;
  160.  
  161.     "Bsearch" attempts to locate the "key" element within the previously
  162.     SORTED array "base".  If successful, the index of the found element is
  163.     returned; otherwise, 0 is returned to indicate that the
  164.     element is not present.
  165.  
  166.  
  167. procedure fill(var key{:element}, destination{:array};
  168.                    count, sizeof_element:word);
  169.  
  170.    WARNING: This routine overwrites memory if used incorrectly.
  171.  
  172.     Moves the "key" element to the first "count" indices in the
  173.     "destination" array.
  174.  
  175.  
  176. function lfind(var key{:element}, base{:array};
  177.                    length_base, sizeof_element:word;
  178.                    f:comparefunc):word;
  179.  
  180.     "Lfind" attempts to locate the "key" element within the array "base".
  181.     If successful, the index of the found element is returned; otherwise, 0
  182.     is returnd to indicate the element is not present.
  183.  
  184.  
  185. function lsearch(var key{:element}, base{:array};
  186.                      length_base, sizeof_element:word;
  187.                      f:comparefunc):word;
  188.  
  189.    WARNING: This routine overwrites memory if used incorrectly.
  190.  
  191.  
  192. var monitor : procedure;
  193. procedure nullmonitor;
  194.  
  195.     "Monitor" and "NullMonitor" were debugging devices developed
  196.     in the process of putting together the ASORTS unit. They can
  197.     be optionally declared by defining a compilation variable
  198.     "MONITOR". Every time that the "Qsort" algorithm swaps a pair
  199.     of array elements, the "monitor" procedure is called. This
  200.     will allow the user to watch the progress of the sort. This
  201.     is of marginal practical value, and by default, these two
  202.     identifiers are not declared. Calling "NullMonitor" will turn
  203.     off monitoring even if the "monitor" procedure variable is
  204.     present.
  205.  
  206.  
  207. procedure qsort(var base {:array};
  208.                     length_base, sizeof_element:word;
  209.                     f:comparefunc);
  210.  
  211.    WARNING: This routine overwrites memory if used incorrectly.
  212.  
  213.     "Qsort" reorders the elements of the "base" array using a quicksort
  214.     algorithm.  The function "f" is used to compare two elements of the
  215.     array, and must return a negative number if the first argument is "less
  216.     than" the second, a postive number if the first argument is "greater
  217.     than" the second, and zero if the two arguments are "equal".
  218.  
  219.  
  220. procedure shuffle(var base{:array};
  221.                       length_base, sizeof_element:word);
  222.  
  223.    WARNING: This routine overwrites memory if used incorrectly.
  224.  
  225.     Randomly permutes ("unsorts") the elements of an array. The
  226.     SYSTEM "Randomize" procedure should be called at least once
  227.     in a program that shuffles an array.
  228.  
  229.  
  230. procedure subfill(var key{:subelement}, destination{:subarray};
  231.                   count, sizeof_key, sizeof_element:word);
  232.  
  233.    WARNING: This routine overwrites memory if used incorrectly.
  234.  
  235.     Partially fills an array with the "key". The address of
  236.     "Destination" should be the address of the first byte in the
  237.     subarray. The portion of the array outside of the subarray is
  238.     left unchanged.
  239.  
  240.  
  241. procedure submove(var source{:[sub]array},
  242.                       destination{:[sub]array};
  243.                       count,
  244.                       sizeof_source_element,
  245.                       sizeof_destination_element:word);
  246.  
  247.    WARNING: This routine overwrites memory if used incorrectly.
  248.  
  249.     If the size of the source elements are smaller than that of
  250.     the destination elements, moves the first "count" elements of
  251.     the source into a subarray of the same size in destination.
  252.     If larger, only moves that portion of the source that will
  253.     fill the first "count" elements of the destination. If equal
  254.     in size, does a simple "move" of the bytes.
  255.  
  256.  
  257. procedure xsubmove(var source{:subarray}, destination{:subarray};
  258.                        count, sizeof_source_element,
  259.                        sizeof_destination_element,
  260.                        sizeof_subelement:word);
  261.  
  262.    WARNING: This routine overwrites memory if used incorrectly.
  263.  
  264.     Moves a subarray from the source to the destination. The size
  265.     of the subelements is presumed to be the same in both
  266.     subarrays. "XsubMove" does not check to make sure that the
  267.     sizes are consistent.
  268.  
  269.  
  270.