Power-Programmierung/CD1.mdf/pascal/library/dos/btree/tree/setops.pas

Pascal/Delphi Source File | 1989-07-13 | 11.8 KB | 314 lines

(* TBTree16             Copyright (c)  1988,1989       Dean H. Farwell II    *)

unit SetOps;

(*****************************************************************************)
(*                                                                           *)
(*               S E T   O P E R A T I O N   R O U T I N E S                 *)
(*                                                                           *)
(*****************************************************************************)

(* This unit contains procedures to perform the set operations Intersection,
   Union, and Difference on a pair of logical record lists.  The two lists
   passed into the routines (lrLst1 and lrLst2) contain zero or more logical
   record numbers from the SAME (very important) data file.  A third logical
   record list (lrLst3) will be produced.  The third list will contain the
   resulting logical record numbers depending on the set operation performed.
   Intersection produces a list that contains all record numbers which are in
   both input lists.  Union produces a list containing all record numbers which
   are in either or both lists.  Difference produces a list coantaining all
   records in the first list but not in the second list.  Obviously, these are
   extremely useful routines.  Queries using multiple selection criteria can
   now be accomplished.  For example, you can now easily retrieve all records
   for which filed1 <= 10 and field2 = 'MANAGER' by doing a query on field1
   and a separate query on field2 and then taking the intersection of the two
   resulting lists.  One note, theis is not the preferred method for doing
   retrievals on range.  If a retrieval on range is desired, use
   GetRangeFromBTree instead.  This will be significantly faster.            *)

(* Version Information

   Version 1.1 - Unit did not exist.

   Version 1.2 - Entire unit added.

   Version 1.3 - No Changes

   Version 1.4 - No Changes

   Version 1.5 - No Changes

   Version 1.6 - No Changes                                                  *)

(*\*)
(*////////////////////////// I N T E R F A C E //////////////////////////////*)

interface

uses
    FileDecs,
    Logical,
    LRecList;


(* This routine will take two logical record lists and create a new list
   (lrLst3) which contains all logical record numbers which are in both
   the first and second lists.  The original lists, lrLst1 and lrLst2, are
   not affected at all.  The resulting list, lrLst3, will have the record
   numbers in the same order as lrLst1.  Therefore, if lrLst1 was in some
   special order, lrLst3 will also be in that order (except of course it won't
   have all the entries that lrLst1 has unless lrLst2 is a superset of
   LrLst1.                                                                   *)

procedure Intersection(lrLst1 : LrList;
                       lrLst2 : LrList;
                       var lrLst3 : LrList);


(* This routine will take two logical record lists and create a new list
   (lrLst3) which contains all logical record numbers which are in either
   the first and second lists or both.  The original lists, lrLst1 and lrLst2,
   are not affected at all.  The resulting list, lrLst3, will have the record
   numbers in the same order as lrLst1.  Therefore, if lrLst1 was in some
   special order, lrLst3 will also be in that order.  Any record numbers
   which are in lrLst2 and not in lrLst1 will appear after all entries which
   are in lrLst1.                                                            *)

procedure Union(lrLst1 : LrList;
                lrLst2 : LrList;
                var lrLst3 : LrList);


(* This routine will take two logical record lists and create a new list
   (lrLst3) which contains all logical record numbers which are in the first
   list but not in the second list.  The original lists, lrLst1 and lrLst2,
   are not affected at all.  The resulting list, lrLst3, will have the record
   numbers in the same order as lrLst1.  Therefore, if lrLst1 was in some
   special order, lrLst3 will also be in that order.  Any record numbers
   which are in lrLst1 and lrLst2 will be missing from the resulting list.   *)

procedure Difference(lrLst1 : LrList;
                     lrLst2 : LrList;
                     var lrLst3 : LrList);

(*!*)
(*\*)
(*///////////////////// I M P L E M E N T A T I O N /////////////////////////*)

implementation

type
    EntryPointer = ^EntryArray;

    EntryArray = Array[DataSizeRange] of Boolean;

(*\*)
(* This internal routine will build an array of Boolean (bitmap) which will be
   used to keep track of record numbers which are in a logical record list.
   The list is built in memory using the heap if there is enough room.
   Keeping this list in memory speeds up processing.  If the list is created
   then inMemory is set to TRUE and FALSE otherwise.  If the list is not
   built in memory then the calling routine will have to use a slower method
   to process the lists.                                                     *)

procedure PutList2InBitMap(lrLst1 : LrList;
                           lrLst2 : LrList;
                           var entryPtr : EntryPointer;
                           var entriesNeeded : LrNumber;
                           var inMemory : Boolean);

var
    lrNum,
    largestLr1,
    largestLr2 : LrNumber;

    begin
    largestLr1 := FindLargestLr(lrLst1);
    largestLr2 := FindLargestLr(lrLst2);
    if largestLr1 > largestLr2 then
        begin
        entriesNeeded := largestLr1;
        end
    else
        begin
        entriesNeeded := largestLr2;
        end;
    if MaxAvail > entriesNeeded then
        begin
        GetMem(entryPtr,entriesNeeded);
        FillChar(entryPtr^,entriesNeeded,0);
        lrNum := GetFirstLr(lrLst2);
        while lrNum <> 0 do
            begin
            entryPtr^[lrNum] := TRUE;
            lrNum := GetNextLr(lrLst2);
            end;
        inMemory := TRUE;
        end
    else
        begin
        inMemory := FALSE;
        end;
    end;                                  (* end of PutList2InBitMap routine *)

(*\*)
(* This routine will take two logical record lists and create a new list
   (lrLst3) which contains all logical record numbers which are in both
   the first and second lists.  The original lists, lrLst1 and lrLst2, are
   not affected at all.  The resulting list, lrLst3, will have the record
   numbers in the same order as lrLst1.  Therefore, if lrLst1 was in some
   special order, lrLst3 will also be in that order (except of course it won't
   have all the entries that lrLst1 has unless lrLst2 is a superset of
   LrLst1.                                                                   *)

procedure Intersection(lrLst1 : LrList;
                       lrLst2 : LrList;
                       var lrLst3 : LrList);

var
    lrNum,
    entriesNeeded : LrNumber;
    entryPtr : EntryPointer;
    inMemory : Boolean;   (* set TRUE iff the intersection can be done using
                             the heap as a bit map.  ie enough heap space
                             exists                                          *)

    begin
    CreateLrList(lrLst3);
    PutList2InBitMap(lrLst1,lrLst2,entryPtr,entriesNeeded,inMemory);
    lrNum := GetFirstLr(lrLst1);
    while lrNum <> 0 do
        begin
        if inMemory then
            begin
            if entryPtr^[lrNum] then
                begin
                AddToLrList(lrNum,lrLst3);
                end;
            end
        else
            begin
            if FindLrInList(lrNum,lrLst2) then
                begin
                AddToLrList(lrNum,lrLst3);
                end;
            end;
        lrNum := GetNextLr(lrLst1);
        end;
    if inMemory then
        begin
        FreeMem(entryPtr,entriesNeeded);
        end;
    end;                                      (* end of Intersection routine *)

(*\*)
(* This routine will take two logical record lists and create a new list
   (lrLst3) which contains all logical record numbers which are in either
   the first and second lists or both.  The original lists, lrLst1 and lrLst2,
   are not affected at all.  The resulting list, lrLst3, will have the record
   numbers in the same order as lrLst1.  Therefore, if lrLst1 was in some
   special order, lrLst3 will also be in that order.  Any record numbers
   which are in lrLst2 and not in lrLst1 will appear after all entries which
   are in lrLst1.                                                            *)

procedure Union(lrLst1 : LrList;
                lrLst2 : LrList;
                var lrLst3 : LrList);

var
    lrNum,
    entriesNeeded : LrNumber;
    entryPtr : EntryPointer;
    inMemory : Boolean;   (* set TRUE iff the union can be done using
                             the heap as a bit map.  ie enough heap space
                             exists                                          *)

    begin
    CreateLrList(lrLst3);
    PutList2InBitMap(lrLst1,lrLst2,entryPtr,entriesNeeded,inMemory);
    lrNum := GetFirstLr(lrLst1);
    while lrNum <> 0 do
        begin
        AddToLrList(lrNum,lrLst3);
        if inMemory then
            begin
            entryPtr^[lrNum] := FALSE;
            end;
        lrNum := GetNextLr(lrLst1);
        end;
    if inMemory then
        begin
        for lrNum := 1 to entriesNeeded do
            begin
            if entryPtr^[lrNum] then
                begin
                AddToLrList(lrNum,lrLst3);
                end;
            end;
        FreeMem(entryPtr,entriesNeeded);
        end
    else
        begin
        lrNum := GetFirstLr(lrLst2);
        while lrNum <> 0 do
            begin
            if not FindLrInList(lrNum,lrLst3) then
                begin
                AddToLrList(lrNum,lrLst3);
                end;
            lrNum := GetNextLr(lrLst2);
            end;
        end;
    end;                                             (* end of Union routine *)

(*\*)
(* This routine will take two logical record lists and create a new list
   (lrLst3) which contains all logical record numbers which are in the first
   list but not in the second list.  The original lists, lrLst1 and lrLst2,
   are not affected at all.  The resulting list, lrLst3, will have the record
   numbers in the same order as lrLst1.  Therefore, if lrLst1 was in some
   special order, lrLst3 will also be in that order.  Any record numbers
   which are in lrLst1 and lrLst2 will be missing from the resulting list.   *)

procedure Difference(lrLst1 : LrList;
                     lrLst2 : LrList;
                     var lrLst3 : LrList);

var
    lrNum,
    entriesNeeded : LrNumber;
    entryPtr : EntryPointer;
    inMemory : Boolean;   (* set TRUE iff the difference can be done using
                             the heap as a bit map.  ie enough heap space
                             exists                                          *)

    begin
    CreateLrList(lrLst3);
    PutList2InBitMap(lrLst1,lrLst2,entryPtr,entriesNeeded,inMemory);
    lrNum := GetFirstLr(lrLst1);
    while lrNum <> 0 do
        begin
        if inMemory then
            begin
            if not entryPtr^[lrNum] then
                begin
                AddToLrList(lrNum,lrLst3);
                end;
            end
        else
            begin
            if not FindLrInList(lrNum,lrLst2) then
                begin
                AddToLrList(lrNum,lrLst3);
                end;
            end;
        lrNum := GetNextLr(lrLst1);
        end;
    if inMemory then
        begin
        FreeMem(entryPtr,entriesNeeded);
        end;
    end;                                        (* end of Difference routine *)

end.                                                   (* end of SETOPS unit *)