btree_test.sa

 
---------------------------> Sather 1.1 source file <--------------------------
-- Test classes for B_TREEs.
-- To avoid debugging routines in the classes they are hooked into here.
-- @(#) 1995/1996 Holger Klawitter


class BT_NODE_DBG{KEY<$IS_LT{KEY},ELT} < $BT_NODE{KEY,ELT,BT_NODE_DBG{KEY,ELT}} 
class BT_NODE_DBG{KEY<$IS_LT{KEY},ELT} < $BT_NODE{KEY,ELT,BT_NODE_DBG{KEY,ELT}} is
   include BT_NODE{KEY,ELT};
   
   debug: STR
   is
      res: STR;
      if void(self) then return "." end;
      loop
	  i ::= 0.upto!(maxSize);
	  res := res + [i].node.debug;
	  if i = size then res := res + "|" end;
	  if ~void([i].item) then
	      key ::= [i].item.t1;
	      typecase key
	      when $STR then res := res + key
	      end;
	  end;
      end;
      return "[" + res + "]"
   end;
   
end; -- class BT_NODE_DBG


class B_TREE_DBG{KEY<$IS_LT{KEY},ELT}<$MAP{KEY,ELT}
class B_TREE_DBG{KEY<$IS_LT{KEY},ELT}<$MAP{KEY,ELT}
is
   include B_TREE{KEY,ELT,BT_NODE_DBG{KEY,ELT}};
   debug: STR is return root.debug end;
end; -- class B_TREE_DBG


class TEST_BTREE
class TEST_BTREE
is
   -- This test checks the internal representation of btrees.
   -- Especially the removal of useless references is being checked.
   include TEST;
   
   main
   is
      tree ::= #B_TREE_DBG{INT,INT};
      
      class_name("B_TREE_DBG");
      
      test("",tree.size.str,"0");
      tree[200] := 42;
      test("",tree.size.str,"1");
      tree[200] := 37;
      test("",tree.size.str,"1");
      test("",tree.debug,"[.200.|...]");
      tree[400] := 42;
      test("",tree.debug,"[.200.400.|..]");
      tree[300] := 42;
      test("",tree.debug,"[.200.300.400.|.]");
      tree[100] := 42;
      test("",tree.debug,"[.100.200.300.400.|]");
      tree[500] := 42;
      test("",tree.debug,"[[.100.200.|..]300[.400.500.|..]|...]");
      test("",tree.has_ind(200),"true");
      test("",tree.has_ind(250),"false");
      test("",tree[200].str,"37");
      tree[220] := 42;
      test("",tree.debug,"[[.100.200.220.|.]300[.400.500.|..]|...]");
      tree[240] := 42;
      test("",tree.debug,"[[.100.200.220.240.|]300[.400.500.|..]|...]");
      tree[260] := 42;
      test("",tree.debug,"[[.100.200.220.240.|]260[.300.400.500.|.]|...]");
      tree[120] := 42;
      test("",tree.debug,"[[.100.120.200.220.|]240[.260.300.400.500.|]|...]");
      tree[140] := 42;
      test("",tree.debug,
	   "[[.100.120.|..]140[.200.220.|..]240[.260.300.400.500.|]|..]"
	   );
      tree[600] := 42;
      test("",tree.debug,
	   "[[.100.120.|..]140[.200.220.240.|.]260[.300.400.500.600.|]|..]"
	   );
      tree[280] := 42;
      test("",tree.debug,
	   "[[.100.120.|..]140[.200.220.240.260.|]280[.300.400.500.600.|]|..]"
	   );
      tree[180] := 42;
      test("",tree.debug,
	   "[[.100.120.140.|.]180[.200.220.240.260.|]280[.300.400.500.600.|]|..]"
	   );
      test("",tree.size.str,"13");
      tree.delete(240);
      test("",tree.size.str,"12");
      test("",tree.debug,
	   "[[.100.120.140.|.]180[.200.220.260.|.]280[.300.400.500.600.|]|..]"
	   );
      tree.delete(240);
      test("",tree.size.str,"12");
      test("",tree.debug,
	   "[[.100.120.140.|.]180[.200.220.260.|.]280[.300.400.500.600.|]|..]"
	   );
      tree.delete(280);
      test("",tree.debug,
	   "[[.100.120.140.|.]180[.200.220.|..]260[.300.400.500.600.|]|..]"
	   );
      tree[280] := 42;
      test("",tree.debug,
	   "[[.100.120.140.|.]180[.200.220.260.|.]280[.300.400.500.600.|]|..]"
	   );
      tree[160] := 42;
      test("",tree.debug,
	   "[[.100.120.140.160.|]180[.200.220.260.|.]280[.300.400.500.600.|]|..]"
	   );
      tree[170] := 42;
      test("",tree.debug,
	   "[[.100.120.140.160.|]170[.180.200.220.260.|]280[.300.400.500.600.|]|..]"
	   );
      s ::= ""; loop s := s + tree.ind! + " " end;
      test("",s,"100 120 140 160 170 180 200 220 260 280 300 400 500 600 ");
      tree.delete(180);
      test("",tree.debug,
	   "[[.100.120.140.160.|]170[.200.220.260.|.]280[.300.400.500.600.|]|..]"
	   );
      tree.delete(260);
      test("",tree.debug,
	   "[[.100.120.140.160.|]170[.200.220.|..]280[.300.400.500.600.|]|..]"
	   );
      tree.delete(200);
      test("",tree.debug,
	   "[[.100.120.140.|.]160[.170.220.|..]280[.300.400.500.600.|]|..]"
	   );
      tree.delete(220);
      test("",tree.debug,
	   "[[.100.120.|..]140[.160.170.|..]280[.300.400.500.600.|]|..]"
	   );
      tree.delete(160);
      test("",tree.debug,
	   "[[.100.120.|..]140[.170.280.|..]300[.400.500.600.|.]|..]"
	   );
      tree.delete(170);
      test("",tree.debug,
	   "[[.100.120.|..]140[.280.300.|..]400[.500.600.|..]|..]"
	   );
      tree.delete(100);
      test("",tree.debug,
	   "[[.120.140.280.300.|]400[.500.600.|..]|...]"
	   );
      tree.delete(500);
      test("",tree.debug,
	   "[[.120.140.280.|.]300[.400.600.|..]|...]"
	   );
      tree.delete(400);
      test("",tree.debug,"[[.120.140.|..]280[.300.600.|..]|...]");
      tree.delete(600);
      finish
   end; -- main
   
end; -- class TEST_BTREE