home *** CD-ROM | disk | FTP | other *** search
/ World of Shareware - Software Farm 2 / wosw_2.zip / wosw_2 / PASCAL / SORTKIT1.ZIP / COMBSORT.PAS next >
Pascal/Delphi Source File  |  1991-09-07  |  4KB  |  110 lines
  1. (******************************************************************************
  2. *                                  combSort                                   *
  3. * a combined sort is a mergsort that uses an internal quicksort in the        *
  4. * splitFile phase to create long telems.                                      *
  5. ******************************************************************************)
  6. unit combSort;
  7.  
  8. {$R-}
  9.  
  10. interface
  11.  
  12. uses
  13.    mergSort
  14.    ,quickSrt
  15.    ;
  16.  
  17. type
  18.    combinedSortPtr = ^ combinedSort;
  19.    combinedSort = object(mergeSort)
  20.       qs : quickSortPtr;
  21.       ap : arrayOfPointersPtr;
  22.       
  23.       constructor init( fn : string;   { file name }
  24.                         bs : word;     { block size }
  25.                         tp : string;   { temp path }
  26.                         on : string;   { outfile name }
  27.                         q  : quickSortPtr { how to do the internal sort }
  28.                         );
  29.       function    splitFile : longInt; virtual;
  30.  
  31.    end; { combinedSort object definition }
  32.  
  33. implementation
  34.  
  35. (******************************************************************************
  36. *                              combinedSort.init                              *
  37. ******************************************************************************)
  38. constructor combinedSort.init;
  39. begin
  40.    mergeSort.init(fn, bs, tp, on);
  41.    qs := q;
  42. end; {combinedSort.init}
  43.  
  44. (******************************************************************************
  45. *                           combinedSort.splitFile                            *
  46. ******************************************************************************)
  47. function combinedSort.splitFile;
  48. var
  49.    initialSize   : longInt;
  50.    { maximum number of sort records that can be performed by an internal sort }
  51.    recordsToSort : longInt; 
  52.    { number of records to sort in a specific phase of the internal sort }
  53.    reachedEOF    : boolean;
  54.    writeTo1      : boolean; { trigger, when true write to t1, else write to t2 }
  55.    i             : longint; { used to count total number of records in file }
  56.    j             : longint; 
  57. begin                 
  58.    writeTo1 := true;
  59.    i := 0;
  60.    reachedEOF := false;
  61.    assign(t1, tempPath + 'mrgsrtt1.$$$');
  62.    rewrite(t1, blokSize);
  63.    if (ioResult <> 0) then
  64.       reachedEOF := true;
  65.    assign(t2, tempPath + 'mrgsrtt2.$$$');
  66.    rewrite(t2, blokSize);
  67.    if (ioResult <> 0) then
  68.       reachedEOF := true;
  69.    initialSize := maxAvail div (blokSize + sizeOf(pointer)) - 1; 
  70.    { one used internally by quicksort .. }
  71.    getMem(ap, initialSize * sizeOf(pointer)); 
  72.    { ap points to start of the array of pointers to block data }
  73.    while (not reachedEOF) do begin
  74.       recordsToSort := 0; { number of records to pass for internal sort .. }
  75.       while ((recordsToSort < initialSize) and (not eof(mergFile))) do begin
  76.          inc(recordsToSort);
  77.          getMem(block1, blokSize);
  78.          blockRead(mergFile, block1^, 1);
  79.          ap^[recordsToSort] := block1;
  80.       end; { read more blocks to be sorted in this phase }
  81.       if (eof(mergFile)) then
  82.          reachedEOF := true;
  83.       if (recordsToSort <> 0) then begin
  84.          qs^.numberOfElements := recordsToSort;
  85.          qs^.ptrArray := ap; { set parameters for this phase of the internal sort }
  86.          qs^.doYourJob;
  87.          for j := 1 to recordsToSort do begin
  88.             if (writeTo1) then 
  89.                blockWrite(t1, ap^[j]^, 1)
  90.             else
  91.                blockWrite(t2, ap^[j]^, 1);
  92.             freemem(ap^[j], blokSize);
  93.          end; { writing the telem to the file }
  94.          writeTo1 := not writeTo1;
  95.          i := i + recordsToSort;
  96.       end; { there were records to sort .. }
  97.    end; { while .. for read }
  98.    freemem(ap, initialSize * sizeof(pointer));
  99.    splitFile := i; { we return the number of records in the file .. }
  100.    close(mergFile);
  101.    close(t1);
  102.    close(t2);
  103.    telem := initialSize; { this is the catch, here we have an initial size .. }
  104. end; {combinedSort.splitFile}
  105.  
  106. (******************************************************************************
  107. *                                    MAIN                                     *
  108. ******************************************************************************)
  109. end.
  110.