home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Source Code / Pascal / Libraries / DBL Pascal Library / Fast-BV / Fast-BV Test.p next >
Encoding:
Text File  |  1992-01-28  |  3.6 KB  |  192 lines  |  [TEXT/PJMM]
  1. program FastBVTest;
  2.  
  3.     uses
  4.         FastBitVector;
  5.  
  6.     const
  7.         BigSize = 10000;
  8.         BigLimit = BigSize - 1;
  9.  
  10.     type
  11.         BigRange = 0..BigLimit;
  12.  
  13.     var
  14.         bv: BitVector;
  15.         s: set of BigRange;
  16.         i: Integer;
  17.         err: OSErr;
  18.  
  19. {$PUSH}
  20. {$R-}
  21. {$D-}
  22. {$V-}
  23.     function Quick_MemberOfSet (theIDSetPtr: PTR; theMember: INTEGER): BOOLEAN;
  24.         const
  25.             idSize = (8 * SIZEOF(s)) - 1;    {Bit size, 0-based}
  26.     begin
  27.         Quick_MemberOfSet := BitTst(theIDSetPtr, idSize - theMember);
  28.     end;
  29. {$POP}
  30.  
  31.     procedure BasicDemo;
  32.  
  33.         procedure DisplayBV (theBV: BitVector);
  34.             var
  35.                 i: Integer;
  36.         begin
  37.             writeln('---');
  38.             for i := 0 to BVLength(bv) - 1 do
  39.                 writeln(i : 2, ' ', BVTestBit(bv, i));
  40.             writeln('---');
  41.         end;
  42.  
  43.         var
  44.             i: Integer;
  45.     begin
  46.         bv := NewBV(10);
  47.         BVClearAllBits(bv);
  48.         BVSetBit(bv, 0);
  49.         BVSetBit(bv, 3);
  50.         BVSetBit(bv, 5);
  51.         BVSetBit(bv, 9);
  52.         DisplayBV(bv);
  53.         i := -1;
  54.         repeat
  55.             BVFindNextSetBit(bv, i);
  56.             writeln(i : 2)
  57.         until i = -1;
  58.         BVSetAllBits(bv);
  59.         BVClearBit(bv, 2);
  60.         BVClearBit(bv, 7);
  61.         BVClearBit(bv, 8);
  62.         DisplayBV(bv);
  63.         err := BVExtend0(bv, 15);
  64.         DisplayBV(bv);
  65.         err := BVExtend1(bv, 18);
  66.         DisplayBV(bv);
  67.         BVTruncate(bv, 3);
  68.         DisplayBV(bv);
  69.         DisposeBV(bv);
  70.     end;
  71.  
  72.     procedure RunTimeTrial (n: Integer);
  73.         var
  74.             expectedCount, count: Integer;
  75.  
  76.         procedure InitTestVector;
  77.             var
  78.                 i: Integer;
  79.         begin
  80.             bv := NewBV(BigSize);
  81.             if bv = nil then
  82.                 begin
  83.                     writeln('NewBV failed');
  84.                     Halt;
  85.                 end;
  86.             BVClearAllBits(bv);
  87.             expectedCount := BigLimit div n + 1;
  88.             count := 0;
  89.             for i := 0 to BigLimit div n do
  90.                 BVSetBit(bv, i);
  91.         end;
  92.  
  93.         procedure InitTestSet;
  94.             var
  95.                 i: Integer;
  96.         begin
  97.             s := [];
  98.             expectedCount := BigLimit div n + 1;
  99.             count := 0;
  100.             for i := 0 to BigLimit div n do
  101.                 s := s + [i];
  102.         end;
  103.  
  104.         procedure CheckCount;
  105.         begin
  106.             if count <> expectedCount then
  107.                 writeln('Count is wrong: ', count : 1, ' vs ', expectedCount : 1);
  108.         end;
  109.  
  110.         const
  111.             Passes = 5;
  112.         var
  113.             i, pass: Integer;
  114.             t: Longint;
  115.     begin
  116.         writeln('Time trial, density = 1/', n : 1);
  117.  
  118. {Find all set bits using BVFindNextSetBit}
  119.         t := TickCount;
  120.         for pass := 1 to Passes do
  121.             begin
  122.                 InitTestVector;
  123.                 i := -1;
  124.                 repeat
  125.                     BVFindNextSetBit(bv, i);
  126.                     if i >= 0 then
  127.                         count := count + 1;
  128.                 until i = -1;
  129.                 CheckCount;
  130.                 DisposeBV(bv);
  131.             end;
  132.         writeln((TickCount - t) / Passes : 6 : 1, ' BVFindNextSetBit');
  133.  
  134. {Find all set bits using BVTestBit}
  135.         t := TickCount;
  136.         for pass := 1 to Passes do
  137.             begin
  138.                 InitTestVector;
  139.                 for i := 0 to BigLimit do
  140.                     if BVTestBit(bv, i) then
  141.                         count := count + 1;
  142.                 CheckCount;
  143.                 DisposeBV(bv);
  144.             end;
  145.         writeln((TickCount - t) / Passes : 6 : 1, ' BVTestBit');
  146.  
  147. {Find all set bits using Quick_MemberOfSet}
  148.         t := TickCount;
  149.         for pass := 1 to Passes do
  150.             begin
  151.                 InitTestSet;
  152.                 for i := 0 to BigLimit do
  153.                     if Quick_MemberOfSet(@s, i) then
  154.                         count := count + 1;
  155.                 CheckCount;
  156.                 s := [];
  157.             end;
  158.         writeln((TickCount - t) / Passes : 6 : 1, ' Quick_MemberOfSet');
  159.  
  160. {Find all set bits using intrinsic 'IN' function}
  161.         t := TickCount;
  162.         for pass := 1 to Passes do
  163.             begin
  164.                 InitTestSet;
  165.                 for i := 0 to BigLimit do
  166.                     if i in s then
  167.                         count := count + 1;
  168.                 CheckCount;
  169.                 s := [];
  170.             end;
  171.         writeln((TickCount - t) / Passes : 6 : 1, ' IN');
  172.     end;
  173.  
  174. begin
  175. {Do the customary and mandatory initializations, respectively}
  176.     ShowText;
  177.     InitFastBitVector;
  178.  
  179. {Demonstrate the most basic functions}
  180.     BasicDemo;
  181.  
  182. {Demonstrate time performance relative to other approaches}
  183.     RunTimeTrial(1000);
  184.     RunTimeTrial(100);
  185.     RunTimeTrial(20);
  186.     RunTimeTrial(10);
  187.     RunTimeTrial(5);
  188.     RunTimeTrial(4);
  189.     RunTimeTrial(3);
  190.     RunTimeTrial(2);
  191.     RunTimeTrial(1);
  192. end.