test/unionfind_test.cc
changeset 2538 7bdd328de87a
parent 2391 14a343be7a5a
child 2553 bfced05fa852
equal deleted inserted replaced
7:5b1948606c87 8:c7cb639f330a
    47   UFE U(base);
    47   UFE U(base);
    48 
    48 
    49   U.insert(1);
    49   U.insert(1);
    50   U.insert(2);
    50   U.insert(2);
    51 
    51 
    52   check(U.join(1,2),"Test failed.");
    52   check(U.join(1,2) != -1,"Test failed.");
    53 
    53 
    54   U.insert(3);
    54   U.insert(3);
    55   U.insert(4);
    55   U.insert(4);
    56   U.insert(5);
    56   U.insert(5);
    57   U.insert(6);
    57   U.insert(6);
    58   U.insert(7);
    58   U.insert(7);
    59 
    59 
    60   check(U.join(1,4),"Test failed.");
       
    61   check(!U.join(2,4),"Test failed.");
       
    62   check(U.join(3,5),"Test failed.");
       
    63 
    60 
    64   U.insert(8,5);
    61   check(U.join(1,4) != -1,"Test failed.");
       
    62   check(U.join(2,4) == -1,"Test failed.");
       
    63   check(U.join(3,5) != -1,"Test failed.");
    65 
    64 
    66   check(U.size(4) == 3,"Test failed.");
    65 
    67   check(U.size(5) == 3,"Test failed.");
    66   U.insert(8,U.find(5));
    68   check(U.size(6) == 1,"Test failed.");
    67 
    69   check(U.size(2) == 3,"Test failed.");
    68 
       
    69   check(U.size(U.find(4)) == 3,"Test failed.");
       
    70   check(U.size(U.find(5)) == 3,"Test failed.");
       
    71   check(U.size(U.find(6)) == 1,"Test failed.");
       
    72   check(U.size(U.find(2)) == 3,"Test failed.");
       
    73 
    70 
    74 
    71   U.insert(9);
    75   U.insert(9);
    72   U.insert(10,9);
    76   U.insert(10,U.find(9));
    73 
    77 
    74   check(U.join(8,10),"Test failed.");
       
    75 
    78 
    76   check(U.move(9,4),"Test failed.");
    79   check(U.join(8,10) != -1,"Test failed.");
    77   check(!U.move(9,2),"Test failed.");
       
    78 
    80 
    79   check(U.size(4) == 4,"Test failed.");
       
    80   check(U.size(9) == 4,"Test failed.");
       
    81 
    81 
    82   check(U.move(5,6),"Test failed.");
    82   check(U.size(U.find(4)) == 3,"Test failed.");
       
    83   check(U.size(U.find(9)) == 5,"Test failed.");
    83 
    84 
    84   check(U.size(5) == 2,"Test failed.");
    85   check(U.size(U.find(8)) == 5,"Test failed.");
    85   check(U.size(8) == 3,"Test failed.");
       
    86 
       
    87   check(U.move(7,10),"Test failed.");
       
    88   check(U.size(7) == 4,"Test failed.");
       
    89 
    86 
    90   U.erase(9);
    87   U.erase(9);
    91   U.erase(1);
    88   U.erase(1);
    92 
    89 
    93   check(U.size(4) == 2,"Test failed.");
    90   check(U.size(U.find(10)) == 4,"Test failed.");
    94   check(U.size(2) == 2,"Test failed.");
    91   check(U.size(U.find(2)) == 2,"Test failed.");
    95 
    92 
    96   U.erase(6);
    93   U.erase(6);
    97   U.split(8);
    94   U.split(U.find(8));
    98 
       
    99   check(U.size(4) == 2,"Test failed.");
       
   100   check(U.size(3) == 1,"Test failed.");
       
   101   check(U.size(2) == 2,"Test failed.");
       
   102 
       
   103   check(U.join(3,4),"Test failed.");
       
   104   check(!U.join(2,4),"Test failed.");
       
   105 
       
   106   check(U.size(4) == 3,"Test failed.");
       
   107   check(U.size(3) == 3,"Test failed.");
       
   108   check(U.size(2) == 3,"Test failed.");
       
   109 
       
   110   U.makeRep(4);
       
   111   U.makeRep(3);
       
   112   U.makeRep(2);
       
   113 
       
   114   check(U.size(4) == 3,"Test failed.");
       
   115   check(U.size(3) == 3,"Test failed.");
       
   116   check(U.size(2) == 3,"Test failed.");
       
   117 
    95 
   118 
    96 
   119   U.eraseClass(4);
    97   check(U.size(U.find(4)) == 2,"Test failed.");
   120   U.eraseClass(7);
    98   check(U.size(U.find(3)) == 1,"Test failed.");
       
    99   check(U.size(U.find(2)) == 2,"Test failed.");
   121 
   100 
       
   101 
       
   102   check(U.join(3,4) != -1,"Test failed.");
       
   103   check(U.join(2,4) == -1,"Test failed.");
       
   104 
       
   105 
       
   106   check(U.size(U.find(4)) == 3,"Test failed.");
       
   107   check(U.size(U.find(3)) == 3,"Test failed.");
       
   108   check(U.size(U.find(2)) == 3,"Test failed.");
       
   109 
       
   110   U.eraseClass(U.find(4));
       
   111   U.eraseClass(U.find(7));
       
   112 
       
   113   return 0;
   122 }
   114 }