home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / misc / volume35 / m2-splay22 / part01 / splayTest.mod < prev   
Text File  |  1993-01-20  |  4KB  |  217 lines
  1. MODULE splayTest; 
  2. (*
  3.     Title:        
  4.     Last Edit:    Mon Dec 21 11:43:13 1992
  5.     Author:        Johan Persson at my9
  6.  
  7.     SCCS:        %Z%%M%       %I%     %E%        
  8.  
  9. *)
  10.  
  11. IMPORT splay, splayItem, std, string, int, card, randomstrm;
  12.  
  13. CONST 
  14.  
  15.  MaxC = 25000;
  16.  MaxR = 25000.0;
  17.  
  18.  
  19. VAR t:splay.T;
  20.     i,r,rank,tests:CARDINAL;
  21.     tmp:splayItem.T;
  22.     bf:BOOLEAN;
  23.     v : ARRAY [1..MaxC] OF BOOLEAN;
  24.     rnd : randomstrm.Obj;
  25.     idx:CARDINAL;
  26.     
  27.    
  28. PROCEDURE printsplayItem(i:splayItem.T);
  29.    
  30.    BEGIN (* printsplayItem *)
  31.      int.write(std.out,i,0);
  32.      string.writef(std.out,",");   
  33.    END printsplayItem;
  34.  
  35.  
  36. PROCEDURE msg(s:ARRAY OF CHAR);
  37.    BEGIN (* msg *)
  38.      string.writef(std.out,s);
  39.    END msg;
  40.  
  41. PROCEDURE testRank ();
  42.    VAR i,idx:CARDINAL;
  43.    BEGIN (* testRank *)
  44.      idx:=1;
  45.      FOR i := 1 TO MaxC DO
  46.         IF v[i] THEN
  47.           rank:=splay.getRank(t,i);
  48.           IF idx#rank THEN 
  49.             string.writef(std.out,"** ERROR IN RANK.\n");
  50.         string.writef(std.out," (i=");
  51.         card.write(std.out,i,0);
  52.         string.writef(std.out,")\n");
  53.         string.writef(std.out," rank=");
  54.         card.write(std.out,rank,0);
  55.         string.writef(std.out,"\n");
  56.         string.writef(std.out," idx=");
  57.         card.write(std.out,idx,0);
  58.         string.writef(std.out,"\n");
  59.         msg("Number OF tests: ");
  60.         card.write(std.out,tests,0);
  61.         string.writef(std.out,"\n");
  62.         splay.mapIn(t,printsplayItem);
  63.         HALT;
  64.       END;
  65.       INC(idx); 
  66.        ELSE
  67.      (* card.write(std.out,i,0);
  68.       msg(": F, ");*)
  69.         END;
  70.       END;
  71.    END testRank;
  72.  
  73. BEGIN
  74.  
  75. msg("Create the structure ...");
  76.  
  77. splay.create(t);
  78.  
  79. msg("done.\n");
  80.  
  81. msg("Beginning with insertions\n");
  82.  
  83. FOR i := 0 TO 255 DO
  84.   splay.insert(t,i);   
  85. END (* for *);
  86.  
  87. msg("Done with insertions\n");
  88.  
  89. IF splay.find(t,13,tmp) THEN
  90.    msg("found 13 (tmp=");
  91.    int.write(std.out,tmp,0);
  92.    msg(") OK.\n");
  93.    splay.mapPre(t,printsplayItem);
  94.    msg("\n");
  95. ELSE
  96.    msg("****** ERROR IN find routine!\n");
  97. END (* if *);
  98.  
  99. IF splay.find(t,18,tmp) THEN
  100.    msg("found 18 (tmp=");
  101.    int.write(std.out,tmp,0);
  102.    msg(") OK.\n");
  103.    splay.mapPre(t,printsplayItem);
  104.    msg("\n");
  105. ELSE
  106.    msg("**** ERROR IN exist routine!\n");
  107. END (* if *);
  108.  
  109. IF splay.find(t,300,tmp) THEN
  110.    msg("ERROR IN exist routine!  ");
  111.    msg("found 300 (tmp=");
  112.    int.write(std.out,tmp,0);
  113.    msg(")\n");
  114. ELSE
  115.    msg("Didn't find 300. OK.\n");
  116.    splay.mapPre(t,printsplayItem);
  117.    msg("\n");
  118. END (* if *);
  119.  
  120.  
  121. msg("Print a sorted version ...\n");
  122.  
  123. splay.mapIn(t,printsplayItem);
  124.  
  125. msg("\n\n Print some rank's\n");
  126.  
  127. IF splay.getRankElement(t,3,tmp) THEN 
  128.    msg("3=> "); int.write(std.out,tmp,0); msg("\n");
  129. ELSE 
  130.    msg("ERROR didn't find rank 3\n\n");
  131. END;
  132.  
  133. IF splay.getRankElement(t,1,tmp) THEN 
  134.    msg("1=> "); int.write(std.out,tmp,0); msg("\n");
  135. ELSE 
  136.    msg("ERROR didn't find rank 1\n\n");
  137. END;
  138.  
  139. IF splay.getRankElement(t,6,tmp) THEN 
  140.    msg("6=> "); int.write(std.out,tmp,0); msg("\n");
  141. ELSE 
  142.    msg("ERROR didn't find rank 6\n\n");
  143. END;
  144.  
  145. IF splay.getRank(t,255)#256 THEN 
  146.    msg("**** ERROR IN getRank\n");
  147. ELSE 
  148.    msg("\n 255 has rank 256\n");
  149. END;
  150.  
  151. msg("\n and now we delete som element");
  152.  
  153. msg("\n 6 ..");
  154.  
  155. splay.delete(t,6);
  156.  
  157. msg("\n Print a sorted version ...\n");
  158.  
  159. splay.mapIn(t,printsplayItem);
  160.  
  161. msg("\n");
  162.  
  163. splay.destroy(t);
  164.  
  165. msg("\n Finished first part. Starting exhaustive test (hit Ctrl-C TO abort)\n");
  166.  
  167.  
  168. splay.create(t);
  169.  
  170. msg("Beginning with insertions ... \n");
  171.  
  172. FOR i := 1 TO MaxC  DO
  173.   splay.insert(t,i); 
  174.   v[i]:=TRUE;  
  175. END (* for *);
  176.  
  177. msg("done.\n");
  178.  
  179. IF splay.find(t,MaxC DIV 2,tmp) THEN 
  180.   msg("Starting test: of insert... ");
  181.   testRank;
  182.   msg("done.\n Passed test 1.\n");
  183. ELSE
  184.   msg("Failed 'find' test 1\n");
  185. END;
  186.  
  187. msg("Starting test sequence ...\n");
  188. tests:=0;
  189. rnd:=randomstrm.uniform(1.0, MaxR, 837 );
  190.  
  191. LOOP
  192.   INC(tests);
  193.   IF tests=10000 THEN 
  194.      msg(".\n");
  195.      tests:=0;
  196.   END;
  197.   r:= TRUNC(randomstrm.next(rnd));
  198.   IF v[r] THEN
  199.      IF TRUNC(randomstrm.next(rnd)) > (MaxC DIV 2) THEN 
  200.        IF NOT splay.find(t,r,tmp) THEN 
  201.          msg("Error 'find'\n");
  202.        END;
  203.      ELSE
  204.        splay.delete(t,r);
  205.        v[r]:=FALSE;
  206.      END;
  207.      testRank;
  208.   ELSE
  209.      splay.insert(t,r);
  210.      v[r]:=TRUE;
  211.      testRank;
  212.   END (* if *);
  213. END (* loop *);
  214.  
  215.  
  216. END splayTest.
  217.