World of Shareware - Software Farm 2/wosw_2.zip/wosw_2/PASCAL/SRTKIT11.ZIP/SORTKIT.DOC

Text File | 1992-03-07 | 14KB | 338 lines

 ╔══════════════════════════════════════════════════════════════════════════╗
 ║                                                                          ║
 ║                                 ISoft D&M                                ║
 ║                                 POB. 5517                                ║
 ║                           Coralville IA 52241                            ║
 ║                                   U.S.A                                  ║
 ║                                                                          ║
 ╚══════════════════════════════════════════════════════════════════════════╝

*******************************************************************************
*                                   sortKit V1.1                              *
* sortKit Documentation file, Last Update : Mar. 07, 1992.                    *
*******************************************************************************

File List
---------

 This package contains the following files :

 MERGSORT.PAS   - External sort object - source file.
 QUICKSRT.PAS   - Internal sort object - source file.
 COMBSORT.PAS   - Combined internal + external sort object - source file.
 SORTKIT.DOC    - This file.
 SORTKIT.REG    - Registration file.
 PROGRAMS.TXT   - ISoft D&M shareware products description.

Why Register
------------

  sortKit is a shareware product, if you find this product valuable,
 please register it. This section describes the reasons you should register.

  By registering sortKit you will receive a printed manual with FULL technical
 documentation, loads of program samples printed, and on disk, and the latest
 sortKit version. By registering you will help us to create the next version
 of sortKit that will support faster smarter sorts, and support for PARADOX
 sorts.

  Registered sortKit users get full no-rotality usage permission, and the
 complete RFFSORT sort utility program package.

Whats new
---------

  - Added better documentation in source files.
  - From this version sortKit is distributed by
    ISoft D&M, P.O.B 5517, Coralville IA 52241, U.S.A

*******************************************************************************
*                                Introduction                                 *
*******************************************************************************

  This package provides a Turbo-Pascal 6.0 (and 5.5 probably), OOPS Sort
 library that includes an internal sort (quick sort), and external sort
 (merge sort), and a combined internal and external sort (combined sort).

  With this package you can create simple to use sort objects that only need
 to define a virtual compare function, to sort data fast, in memory, or
 huge data files using a fast internal and external sort algorithm.

*******************************************************************************
*                                Internal Sort                                *
*******************************************************************************

  The unit quicksrt.pas defines an internal quicksort object. In order to
 perform fast sort, the quickSort object uses an array of pointers to the
 sorted data, and when it needs to swap data elements, it only swaps their
 pointers in the array of pointers.

  In order to define a sort that will sort YOUR data you should define a
 descendent of the quickSort object that has one virtual function, the
 compare function. This function receives 2 pointers - a, and b, and
 returns 1 if the data pointed by a is "bigger" then the data pointed by
 b, it returns 0 if the data pointed by a is "equal" to the data pointed
 by b, and it returns 2, otherwise.

  Let us assume that we want to create a simple textSort object that sorts
 strings. The following definition will explain the way to create such an
 object :

 textSort = object(quickSort)

        function compare(a, b : pointer) : byte; virtual;

 end; { textSort object definition }

 function textSort.compare(a, b : pointer) : byte;
 type
        strPtr = ^ string;
 begin
        if (strPtr(a)^ > strPtr(b)^) then
                compare := 1
        else if (strPtr(a)^ = strPtr(b)^) then
                compare := 0
        else
                compare := 2;
 end; {textSort.compare}

 In order to use this object we must perform the following steps :

 1. Declare a variable of the required sort type.
 2. Declare a variable of type arrayOfPointersPtr.
 3. Allocate space from the heap to the variables declared in step 2, in the
    amount of numberOfElementsToSort * sizeOf(pointer).
 4. Assign to the array defined, the pointers to the data elements to be sorted.
 5. Initialize the sort object.
 6. Call the sort object's doYourJob method.

 Let us assume that we want to sort an array of 200 strings that we have in
 memory, in a string array defined as :

 var
        stringArray : array [1.200] of string;

 We will use the following code :

 var
        myInternalSort : textSort;                      { step 1 }
        pointers       : arrayOfPointersPtr;            { step 2 }
 begin
        getmem(pointers, 200 * sizeOf(pointer));        { step 3 }
        {$R-} {This is important !, otherwise we will get range errors }
        for i := 1 to 200 do
                pointers[i] := @stringArray[i];         { step 4 }
        myInternalSort.init(200, pointers, 256);        { step 5 }
        myInternalSort.doYourJob;                       { step 6 }
  ... { some more code .. }

  Notice - At the end of this procedure stringArray is NOT sorted, but
           pointers is a pointer to a sorted array of pointers. If we
           would like to print the sorted array we will use a procedure
           such as :

        for i := 1 to 200 do
                writeln(strPtr(pointers[i])^);

*******************************************************************************
*                                External Sort                                *
*******************************************************************************

  The unit mergsort.pas defines an external mergesort object. This sort is
 used as the basis of file sort routines.

  In order to define a sort that will sort YOUR data files you should define
 a descendent of mergeSort that has one virtual function, the compare
 function. This function compares to pointer variables named block1 and
 block2 and returns 1 if the data pointed by block1 is "bigger" then the
 data pointed by block2, 0 if the data pointed by block1 is "equal" to the
 data pointed by block2, and 2, otherwise.

  Let us assume that we have a file of myRecord, where myRecord is defined
 as :

 type
        myRecord = record
                myNum : word;
                myStatus : integer;
                myName : string[20];
        end; { myRecord definition }

  We will have to use the following code in order to define a sort object
 that will sort according to the myNum field :

 type
        myExternalSort = object(mergeSort)

                function compare : byte; virtual;

        end; { myExternalSort object definition }

 function myExternalSort.compare : byte;
 type
        myRecordPtr = ^ myRecord;
 begin
        if (myRecordPtr(block1)^.myNum > myRecordPtr(block2)^.myNum) then
                compare := 1
        else if (myRecordPtr(block1)^.myNum = myRecordPtr(block2)^.myNum) then
                compare := 0
        else
                compare := 2;
 end; {myExternalSort.compare}

 In order to use this object we must perform the following steps :

 1. Declare a variable of the required sort type.
 2. Initialize the sort object.
 3. Call the sort object's doYourJob method.
 4. Call the sort object's done destructor.

 Let us assume we want to sort the file ORGFIL.DTA, which is a file of myRecord,
 to the file SRTFIL.DTA. The code we will use will be :

 var
        fileSort : myExternalSort;                      { step 1 }
 begin
        fileSort.init('ORGFIL.DTA', sizeOf(myRecord),
                      '', 'SRTFIL.DTA');                { step 2 }
        fileSort.doYourJob;                             { step 3 }
        fileSort.done;                                  { step 4 }
  .. { some more code .. }

  Notice - The 3rd parameter of the init constructor is the temporary
 path to use during the sort. If we have a RAM disk, large enough to hold
 two files the size of the original file, in drive d:, we can replace
 step 2 with the following code :

        fileSort.init('ORGFIL.DTA', sizeOf(myRecord),
                      'D:\', 'SRTFIL.DTA');             { step 2 }

 And the sort will be much faster. Notice - The output file will be on
 drive D:\ at the end of the sort.

*******************************************************************************
*                                Combined Sort                                *
*******************************************************************************

  A combined sort is an external merge sort that uses an internal quick sort
 object descendent at the first phase of the sort. Because of this feature
 a combined sort is faster then then the "classic" merge sort - internal sort
 is fast, there are fewer passes on the temporary files, and thus less I/O
 operations are performed. The only problem with combined sort is the added
 complexity to define and code it. I have tried to minimize this problem
 in the implementation of the combinedSort object provided in the combsort.pas
 unit file.

  Let us use the same example we used in the merge sort section, and try to
 sort the same data file using a combined sort. In order to achieve this
 goal we will have to follow the followin procedure :

 1. Declare a variable of the required sort type, where the sort object is
    a descendent of the combinedSort object, and it is defined the same way
    the merge sort descendent was defined.
 2. Declare a pointer internal sort variable, which performs a compare
    function similar to the external sort compare function.
 3. Initialize the internal sort, with a nil parameter for the array of
    pointers.
 4. Initalize the variable declared in step 1 passing the variable declared
    in step 2 as a parameter.
 5. Call the external sort doYourJob method.
 6. Call the external sort done destructor.

 Given the same example as the merge sort file the code needed will be :

 type
        myInternalSortPtr = ^ myInternalSort;
        myInternalSort = object(quickSort)

                function compare(a, b : pointer) : byte; virtual;

        end; { myInternalSort object definition }

        myCombinedSort = object(combinedSort)

                function compare : byte; virtual;

        end; { myCombinedSort object definition }

 var
        misp : myInternalSortPtr;
        mcs  : myCombinedSort;

 function doCompare(p1, p2 : pointer) : byte;
 { this function will compare for both the internal and external sorts }
 type
        myRecordPtr = ^ myRecord;
 begin
        if (myRecordPtr(p1)^.myNum > myRecordPtr(p2)^.myNum) then
                doCompare := 1
        else if (myRecordPtr(p1)^.myNum = myRecordPtr(p2)^.myNum) then
                doCompare := 0
        else
                doCompare := 2;
 end; {doCompare}

 function myCombinedSort.compare : byte;
 begin
        compare := doCompare(block1, block2);
 end; {myCombinedSort.compare}

 function myInternalSort.compare(a, b : pointer) : byte;
 begin
        compare := doCompare(a, b);
 end; {myInternalSort.compare}

 begin
        new(misp, init(1, nil, sizeof(myRecord)));
        { notice that the first  parameter is not important, put 1 always }
        { notice that the second parameter is not important, put nil }
        myCombinedSort.init('ORGFIL.DTA', sizeOf(myRecord),
                            'D:\', 'SRTFIL.DTA', misp);
        myCombinedSort.doYourJob;
        myCombinedSort.done;
        ... { rest of code .. }

*******************************************************************************
*                                  Warranty                                   *
*******************************************************************************

  There is no warranty what so ever, This software package is supplied as is,
 The distributer (ISoft D&M), or the author (Loewy Ron), are not,
 and will not be responsible for any damages, lost profits,
 or inconveniences caused by the use, or inability to use this package.
 The use of the package is at your own risk.
 By using (or attempting to use) the package you agree to this.

*******************************************************************************
*                                   General                                   *
*******************************************************************************

  sortKit is distributed by ISoft D&M, P.O.B. 5517 CORALVILLE IA 52241, U.S.A.

  sortKit is (c) copyrighted by Loewy Ron, 1991, 92.

  mouseLib is a shareware package, please register your copy.
  To register your copy of mouseLib please refer to the supplied
  SORTKIT.REG file.

  Other programs distributed by ISoft D&M are described in the supplied
  PROGRAMS.TXT file.

*******************************************************************************
*                                   Contact                                   *
*******************************************************************************

  Please contact :

  ISoft D&M,
  P.O.B 5517
  Coralville IA 52241,
  U.S.A

*******************************************************************************
*                                   Credits                                   *
*******************************************************************************

  Turbo-Pascal and Paradox are copyrights of Borland International.