home *** CD-ROM | disk | FTP | other *** search
/ World of Shareware - Software Farm 2 / wosw_2.zip / wosw_2 / PASCAL / TBTREE16.ZIP / SETOPS.PAS < prev    next >
Pascal/Delphi Source File  |  1989-07-13  |  12KB  |  314 lines
  1. (* TBTree16             Copyright (c)  1988,1989       Dean H. Farwell II    *)
  2.  
  3. unit SetOps;
  4.  
  5. (*****************************************************************************)
  6. (*                                                                           *)
  7. (*               S E T   O P E R A T I O N   R O U T I N E S                 *)
  8. (*                                                                           *)
  9. (*****************************************************************************)
  10.  
  11. (* This unit contains procedures to perform the set operations Intersection,
  12.    Union, and Difference on a pair of logical record lists.  The two lists
  13.    passed into the routines (lrLst1 and lrLst2) contain zero or more logical
  14.    record numbers from the SAME (very important) data file.  A third logical
  15.    record list (lrLst3) will be produced.  The third list will contain the
  16.    resulting logical record numbers depending on the set operation performed.
  17.    Intersection produces a list that contains all record numbers which are in
  18.    both input lists.  Union produces a list containing all record numbers which
  19.    are in either or both lists.  Difference produces a list coantaining all
  20.    records in the first list but not in the second list.  Obviously, these are
  21.    extremely useful routines.  Queries using multiple selection criteria can
  22.    now be accomplished.  For example, you can now easily retrieve all records
  23.    for which filed1 <= 10 and field2 = 'MANAGER' by doing a query on field1
  24.    and a separate query on field2 and then taking the intersection of the two
  25.    resulting lists.  One note, theis is not the preferred method for doing
  26.    retrievals on range.  If a retrieval on range is desired, use
  27.    GetRangeFromBTree instead.  This will be significantly faster.            *)
  28.  
  29. (* Version Information
  30.  
  31.    Version 1.1 - Unit did not exist.
  32.  
  33.    Version 1.2 - Entire unit added.
  34.  
  35.    Version 1.3 - No Changes
  36.  
  37.    Version 1.4 - No Changes
  38.  
  39.    Version 1.5 - No Changes
  40.  
  41.    Version 1.6 - No Changes                                                  *)
  42.  
  43. (*\*)
  44. (*////////////////////////// I N T E R F A C E //////////////////////////////*)
  45.  
  46. interface
  47.  
  48. uses
  49.     FileDecs,
  50.     Logical,
  51.     LRecList;
  52.  
  53.  
  54. (* This routine will take two logical record lists and create a new list
  55.    (lrLst3) which contains all logical record numbers which are in both
  56.    the first and second lists.  The original lists, lrLst1 and lrLst2, are
  57.    not affected at all.  The resulting list, lrLst3, will have the record
  58.    numbers in the same order as lrLst1.  Therefore, if lrLst1 was in some
  59.    special order, lrLst3 will also be in that order (except of course it won't
  60.    have all the entries that lrLst1 has unless lrLst2 is a superset of
  61.    LrLst1.                                                                   *)
  62.  
  63. procedure Intersection(lrLst1 : LrList;
  64.                        lrLst2 : LrList;
  65.                        var lrLst3 : LrList);
  66.  
  67.  
  68. (* This routine will take two logical record lists and create a new list
  69.    (lrLst3) which contains all logical record numbers which are in either
  70.    the first and second lists or both.  The original lists, lrLst1 and lrLst2,
  71.    are not affected at all.  The resulting list, lrLst3, will have the record
  72.    numbers in the same order as lrLst1.  Therefore, if lrLst1 was in some
  73.    special order, lrLst3 will also be in that order.  Any record numbers
  74.    which are in lrLst2 and not in lrLst1 will appear after all entries which
  75.    are in lrLst1.                                                            *)
  76.  
  77. procedure Union(lrLst1 : LrList;
  78.                 lrLst2 : LrList;
  79.                 var lrLst3 : LrList);
  80.  
  81.  
  82. (* This routine will take two logical record lists and create a new list
  83.    (lrLst3) which contains all logical record numbers which are in the first
  84.    list but not in the second list.  The original lists, lrLst1 and lrLst2,
  85.    are not affected at all.  The resulting list, lrLst3, will have the record
  86.    numbers in the same order as lrLst1.  Therefore, if lrLst1 was in some
  87.    special order, lrLst3 will also be in that order.  Any record numbers
  88.    which are in lrLst1 and lrLst2 will be missing from the resulting list.   *)
  89.  
  90. procedure Difference(lrLst1 : LrList;
  91.                      lrLst2 : LrList;
  92.                      var lrLst3 : LrList);
  93.  
  94. (*!*)
  95. (*\*)
  96. (*///////////////////// I M P L E M E N T A T I O N /////////////////////////*)
  97.  
  98. implementation
  99.  
  100. type
  101.     EntryPointer = ^EntryArray;
  102.  
  103.     EntryArray = Array[DataSizeRange] of Boolean;
  104.  
  105. (*\*)
  106. (* This internal routine will build an array of Boolean (bitmap) which will be
  107.    used to keep track of record numbers which are in a logical record list.
  108.    The list is built in memory using the heap if there is enough room.
  109.    Keeping this list in memory speeds up processing.  If the list is created
  110.    then inMemory is set to TRUE and FALSE otherwise.  If the list is not
  111.    built in memory then the calling routine will have to use a slower method
  112.    to process the lists.                                                     *)
  113.  
  114. procedure PutList2InBitMap(lrLst1 : LrList;
  115.                            lrLst2 : LrList;
  116.                            var entryPtr : EntryPointer;
  117.                            var entriesNeeded : LrNumber;
  118.                            var inMemory : Boolean);
  119.  
  120. var
  121.     lrNum,
  122.     largestLr1,
  123.     largestLr2 : LrNumber;
  124.  
  125.     begin
  126.     largestLr1 := FindLargestLr(lrLst1);
  127.     largestLr2 := FindLargestLr(lrLst2);
  128.     if largestLr1 > largestLr2 then
  129.         begin
  130.         entriesNeeded := largestLr1;
  131.         end
  132.     else
  133.         begin
  134.         entriesNeeded := largestLr2;
  135.         end;
  136.     if MaxAvail > entriesNeeded then
  137.         begin
  138.         GetMem(entryPtr,entriesNeeded);
  139.         FillChar(entryPtr^,entriesNeeded,0);
  140.         lrNum := GetFirstLr(lrLst2);
  141.         while lrNum <> 0 do
  142.             begin
  143.             entryPtr^[lrNum] := TRUE;
  144.             lrNum := GetNextLr(lrLst2);
  145.             end;
  146.         inMemory := TRUE;
  147.         end
  148.     else
  149.         begin
  150.         inMemory := FALSE;
  151.         end;
  152.     end;                                  (* end of PutList2InBitMap routine *)
  153.  
  154. (*\*)
  155. (* This routine will take two logical record lists and create a new list
  156.    (lrLst3) which contains all logical record numbers which are in both
  157.    the first and second lists.  The original lists, lrLst1 and lrLst2, are
  158.    not affected at all.  The resulting list, lrLst3, will have the record
  159.    numbers in the same order as lrLst1.  Therefore, if lrLst1 was in some
  160.    special order, lrLst3 will also be in that order (except of course it won't
  161.    have all the entries that lrLst1 has unless lrLst2 is a superset of
  162.    LrLst1.                                                                   *)
  163.  
  164. procedure Intersection(lrLst1 : LrList;
  165.                        lrLst2 : LrList;
  166.                        var lrLst3 : LrList);
  167.  
  168. var
  169.     lrNum,
  170.     entriesNeeded : LrNumber;
  171.     entryPtr : EntryPointer;
  172.     inMemory : Boolean;   (* set TRUE iff the intersection can be done using
  173.                              the heap as a bit map.  ie enough heap space
  174.                              exists                                          *)
  175.  
  176.     begin
  177.     CreateLrList(lrLst3);
  178.     PutList2InBitMap(lrLst1,lrLst2,entryPtr,entriesNeeded,inMemory);
  179.     lrNum := GetFirstLr(lrLst1);
  180.     while lrNum <> 0 do
  181.         begin
  182.         if inMemory then
  183.             begin
  184.             if entryPtr^[lrNum] then
  185.                 begin
  186.                 AddToLrList(lrNum,lrLst3);
  187.                 end;
  188.             end
  189.         else
  190.             begin
  191.             if FindLrInList(lrNum,lrLst2) then
  192.                 begin
  193.                 AddToLrList(lrNum,lrLst3);
  194.                 end;
  195.             end;
  196.         lrNum := GetNextLr(lrLst1);
  197.         end;
  198.     if inMemory then
  199.         begin
  200.         FreeMem(entryPtr,entriesNeeded);
  201.         end;
  202.     end;                                      (* end of Intersection routine *)
  203.  
  204. (*\*)
  205. (* This routine will take two logical record lists and create a new list
  206.    (lrLst3) which contains all logical record numbers which are in either
  207.    the first and second lists or both.  The original lists, lrLst1 and lrLst2,
  208.    are not affected at all.  The resulting list, lrLst3, will have the record
  209.    numbers in the same order as lrLst1.  Therefore, if lrLst1 was in some
  210.    special order, lrLst3 will also be in that order.  Any record numbers
  211.    which are in lrLst2 and not in lrLst1 will appear after all entries which
  212.    are in lrLst1.                                                            *)
  213.  
  214. procedure Union(lrLst1 : LrList;
  215.                 lrLst2 : LrList;
  216.                 var lrLst3 : LrList);
  217.  
  218. var
  219.     lrNum,
  220.     entriesNeeded : LrNumber;
  221.     entryPtr : EntryPointer;
  222.     inMemory : Boolean;   (* set TRUE iff the union can be done using
  223.                              the heap as a bit map.  ie enough heap space
  224.                              exists                                          *)
  225.  
  226.     begin
  227.     CreateLrList(lrLst3);
  228.     PutList2InBitMap(lrLst1,lrLst2,entryPtr,entriesNeeded,inMemory);
  229.     lrNum := GetFirstLr(lrLst1);
  230.     while lrNum <> 0 do
  231.         begin
  232.         AddToLrList(lrNum,lrLst3);
  233.         if inMemory then
  234.             begin
  235.             entryPtr^[lrNum] := FALSE;
  236.             end;
  237.         lrNum := GetNextLr(lrLst1);
  238.         end;
  239.     if inMemory then
  240.         begin
  241.         for lrNum := 1 to entriesNeeded do
  242.             begin
  243.             if entryPtr^[lrNum] then
  244.                 begin
  245.                 AddToLrList(lrNum,lrLst3);
  246.                 end;
  247.             end;
  248.         FreeMem(entryPtr,entriesNeeded);
  249.         end
  250.     else
  251.         begin
  252.         lrNum := GetFirstLr(lrLst2);
  253.         while lrNum <> 0 do
  254.             begin
  255.             if not FindLrInList(lrNum,lrLst3) then
  256.                 begin
  257.                 AddToLrList(lrNum,lrLst3);
  258.                 end;
  259.             lrNum := GetNextLr(lrLst2);
  260.             end;
  261.         end;
  262.     end;                                             (* end of Union routine *)
  263.  
  264. (*\*)
  265. (* This routine will take two logical record lists and create a new list
  266.    (lrLst3) which contains all logical record numbers which are in the first
  267.    list but not in the second list.  The original lists, lrLst1 and lrLst2,
  268.    are not affected at all.  The resulting list, lrLst3, will have the record
  269.    numbers in the same order as lrLst1.  Therefore, if lrLst1 was in some
  270.    special order, lrLst3 will also be in that order.  Any record numbers
  271.    which are in lrLst1 and lrLst2 will be missing from the resulting list.   *)
  272.  
  273. procedure Difference(lrLst1 : LrList;
  274.                      lrLst2 : LrList;
  275.                      var lrLst3 : LrList);
  276.  
  277. var
  278.     lrNum,
  279.     entriesNeeded : LrNumber;
  280.     entryPtr : EntryPointer;
  281.     inMemory : Boolean;   (* set TRUE iff the difference can be done using
  282.                              the heap as a bit map.  ie enough heap space
  283.                              exists                                          *)
  284.  
  285.     begin
  286.     CreateLrList(lrLst3);
  287.     PutList2InBitMap(lrLst1,lrLst2,entryPtr,entriesNeeded,inMemory);
  288.     lrNum := GetFirstLr(lrLst1);
  289.     while lrNum <> 0 do
  290.         begin
  291.         if inMemory then
  292.             begin
  293.             if not entryPtr^[lrNum] then
  294.                 begin
  295.                 AddToLrList(lrNum,lrLst3);
  296.                 end;
  297.             end
  298.         else
  299.             begin
  300.             if not FindLrInList(lrNum,lrLst2) then
  301.                 begin
  302.                 AddToLrList(lrNum,lrLst3);
  303.                 end;
  304.             end;
  305.         lrNum := GetNextLr(lrLst1);
  306.         end;
  307.     if inMemory then
  308.         begin
  309.         FreeMem(entryPtr,entriesNeeded);
  310.         end;
  311.     end;                                        (* end of Difference routine *)
  312.  
  313. end.                                                   (* end of SETOPS unit *)
  314.