Simtel MSDOS - Coast to Coast/simteldosarchivecoasttocoast2.iso/turbopas/sortkit1.zip/SORTKIT.DOC

Text File | 1991-09-16 | 12KB | 288 lines

*******************************************************************************
*                                   sortKit                                   *
* sortKit Documentation file, Last Update : Sep. 16, 1991.                    *
*******************************************************************************


*******************************************************************************
*                                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, The units and docs. are supplied as is,
 The author (Loewy Ron), is not, and will not be responsible for any damages,
 lost profits, or inconveniences caused by the use, or inability to
 use this unit. The use of the unit is at your own risk. By using the unit
 you agree to this.

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

  sortKit is copyrighted by myself, (c) Loewy Ron, 1991. If you find sortKit
 valuable, please register your copy. Notice - sortKit is not a free or
 public domain package. It is a shareware package, please refer to the
 supplied order form in the file ORDER.TXT.

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

  You can contact me on what-ever you want to at my address at :

          Loewy Ron,                            Loewy Ron
          9 Haneveem st.            Or          20 Smolanskin st.
          Herzeliya, 46465,                     Haifa, 34366,
          Israel.                               Israel.

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

  Turbo-Pascal is a copyright of Borland International.