arrays_test.sa
Generated by gen_html_sa_files from ICSI. Contact gomes@icsi.berkeley.edu for details
---------------------------> Sather 1.1 source file <--------------------------
-- test_arrays.sa: Test array classes and related algorithms
-- Author: Benedict A. Gomes <gomes@tiramisu.ICSI.Berkeley.EDU>
-- Copyright (C) 1995, International Computer Science Institute
-- $Id: arrays_test.sa,v 1.5 1996/05/08 08:35:22 borisv Exp $
--
-- COPYRIGHT NOTICE: This code is provided WITHOUT ANY WARRANTY
-- and is subject to the terms of the SATHER LIBRARY GENERAL PUBLIC
-- LICENSE contained in the file: Sather/Doc/License of the
-- Sather distribution. The license is also available from ICSI,
-- 1947 Center St., Suite 600, Berkeley CA 94704, USA.
class TEST_ARRAY
class TEST_ARRAY is
-- Test of ARRAY{T}::insertion_sort_range and ::quicksort range.
include TEST;
main is
class_name("ARRAY{FLTD} and ARRAY{INT}");
a ::= #ARRAY{INT}(5);
a[0] := 0; a[1] := 1; a[2] := 2; a[3]:=3; a[4]:=4;
test("size",a.size,"5");
test("aset and aget",a[2].str,"2");
res::=""; loop res := res+" "+a.elt!; end;
test("elt!",res," 0 1 2 3 4");
res:=""; loop res := res+" "+a.elt!(1); end;
test("elt!(beg)",res," 1 2 3 4");
res:=""; loop res := res+" "+a.elt!(1,2); end;
test("elt!(1,2)",res," 1 2");
res:=""; loop res := res+" "+a.elt!(1,2,2); end;
test("elt!(1,2,2)",res," 1 3");
res:=""; loop res := res+" "+a.ind!; end;
test("ind!",res," 0 1 2 3 4");
res:=""; loop res := res+" "+a.ind1!; end;
test("ind1!",res," 0 1 2 3 4");
v:ARRAY{INT}:=void;
test("void.size",v.size,"0");
res:=""; loop res := res+"-"+v.elt!; end;
test("elt!",res,"");
res:=""; loop res := res+"-"+v.ind!; end;
test("void.ind!",res,"");
res:=""; loop res := res+"-"+v.elt!; end;
test("void.elt!",res,"");
res:=""; loop res:=res+"-";v.set!(9);res:=res+"-"; end;
test("void.set!",res,"-");
v.copy(v); -- will crash if it does not work
if void(v) then test("void.copy(void)","-","-");
else test("void.copy(void)","-","+"); end;
b ::=#ARRAY{INT}(a.asize);
b.copy(a);
res:=""; loop res := res+" "+b.elt!; end;
test("copy",res," 0 1 2 3 4");
b.copy(v);
res:=""; loop res := res+" "+b.elt!; end;
test("copy(void)",res," 0 1 2 3 4");
c ::= #ARRAY{INT}(3);
c.copy(a);
res:=""; loop res := res+" "+c.elt!; end;
test("copy",res," 0 1 2");
loop b.set!(1); end;
res:=""; loop res := res+" "+b.elt!; end;
test("set!",res," 1 1 1 1 1");
b.copy(a);
loop b.set!(3,1); end;
res:=""; loop res := res+" "+b.elt!; end;
test("set!(3,1)",res," 0 1 2 1 1");
b.copy(a);
loop b.set!(2,2,7); end;
res:=""; loop res := res+" "+b.elt!; end;
test("set!(2,2,7)",res," 0 1 7 7 4");
b.copy(a);
loop b.set!(1,2,2,9); end;
res:=""; loop res := res+" "+b.elt!; end;
test("set!(1,2,2,9)",res," 0 9 2 9 4");
b.copy(1,a);
res:=""; loop res := res+" "+b.elt!; end;
test("copy(1)",res," 0 0 1 2 3");
b.copy(1,v);
res:=""; loop res := res+" "+b.elt!; end;
test("copy(1,void)",res," 0 0 1 2 3");
b.clear;
res:=""; loop res := res+" "+b.elt!; end;
test("clear",res," 0 0 0 0 0");
b.copy(2,2,a);
res:=""; loop res := res+" "+b.elt!; end;
test("copy(2,2)",res," 0 0 0 1 0");
b.copy(2,2,2,a);
res:=""; loop res := res+" "+b.elt!; end;
test("copy(2,2)",res," 0 0 2 3 0");
f::=#ARRAY{FLTD}(20); ok::=0;
loop 100.times!; loop f.set!(RND::uniform) end;
f.insertion_sort_range(0,f.size-1);
if f.is_sorted then ok:=ok+1 end end;
test("No. of times insertion_sort_range was ok",ok.str,"100");
f:=#ARRAY{FLTD}(50); ok:=0;
loop 100.times!; loop f.set!(RND::uniform) end;
f.quicksort_range(0,f.asize-1);
if f.is_sorted then ok:=ok+1 end end;
test("No. of times quicksort_range was ok",ok.str,"100");
finish;
end;
end;
class TEST_SORT
class TEST_SORT is
-- Actually test it out in its incarnation in ARRAY
include TEST;
shared isorter: A_SORT{INT,ARRAY{INT}};
shared fsorter: A_SORT{FLTD,ARRAY{FLTD}};
main is
class_name("SORT");
a1:ARRAY{INT} := |1,2,3,4,5,6|;
test("is_sorted",isorter.is_sorted(a1),true);
a2:ARRAY{INT} := |1,2,3,4,6,5|;
test("is_sorted",isorter.is_sorted(a2),false);
test("is_sorted",isorter.is_sorted(a2,0,4),true);
test("is_sorted",isorter.is_sorted(a2,0,5),false);
a::=#ARRAY{FLTD}(20);
fail::=0;
loop
50.times!;
loop a.set!(RND::uniform) end;
fsorter.insertion_sort(a,0,a.size-1);
if ~fsorter.is_sorted(a) then fail:=fail+1 end
end;
test("No. of times insertion_sort fails",fail,0);
b ::= #ARRAY{FLTD}(100);
ind ::= b.inds;
loop
50.times!;
loop b.set!(RND::uniform) end;
fsorter.insertion_sort(b,ind,0,b.size-1);
if ~fsorter.is_sorted(b,ind,0,b.size-1) then fail:=fail+1 end
end;
test("No. of times indirect insertion_sort fails",fail,0);
c::=#ARRAY{FLTD}(100); fail:=0;
loop
100.times!;
loop c.set!(RND::uniform) end;
fsorter.quicksort(c,0,c.size-1);
if ~fsorter.is_sorted(c) then fail:=fail+1 end
end;
test("No. of times quick sort fails",fail,0);
finish;
end;
end;
class TEST_ARR_ALG
class TEST_ARR_ALG is
-- Tests of other array algorithms
include TEST;
shared ipermute: A_PERMUTE{INT,ARRAY{INT}};
shared isort: A_SORT{INT,ARRAY{INT}};
shared iselect: A_SELECT{INT,ARRAY{INT}};
shared isearch: A_SEARCH{INT,ARRAY{INT}};
shared ialg: A_ALG{INT,ARRAY{INT}};
shared imember: MEMBER{INT,ARRAY{INT}};
main is
-- Tests for permutation etc.
class_name("A_ALGetc.");
l: ARRAY{INT} := |5,4,5,4,3,6,100|;
l2: ARRAY{INT} := |4,5,5,4,100,6,3|;
l3: ARRAY{INT} := |4,4,5,4,100,6,3|;
l4: ARRAY{INT} := |4,100,5,4,100,6,3|;
l5: ARRAY{INT} := |100,6,3,5,5,4|;
test("perm 1",is_permutation(l,l2),true);
test("perm 2",is_permutation(l,l3),false);
test("perm 3",is_permutation(l,l4),false);
test("perm 4",is_permutation(l,l5),false);
lp: ARRAY{INT} := |5,4,5,4,3,6,9|;
map: ARRAY{INT} := |3,2,1,5,6,4,0|;
should: ARRAY{INT} := |9,5,4,5,6,4,3|;
does: ARRAY{INT} := #(7);
ipermute.permute_into(lp,map,does);
-- #PERMUTE_ALG{INT}(lp).permute_into(map,does);
test("permute", does.str,should.str);
m1: ARRAY{INT} := |2,3,5|;
m2: ARRAY{INT} := |3,4,7,8,8|;
mshould: ARRAY{INT} := |2,3,3,4, 5, 7,8,8|;
mdoes: ARRAY{INT} := #(8);
isort.merge_sort(mdoes,m1,m2);
test("Merge",mdoes.str,mshould.str);
mmedianshould: ARRAY{INT} := |2,3,3,4, 5, 6,7,8,8|;
test("Median",iselect.median_modifying(mmedianshould),5);
-- munsorted: ARRAY{INT} := |9,8,6,5,4,3,2,8,7|;
-- Sorted = 2,3,4,5, 6, 7,8,8,9
-- test("Unsortd Median",iselect.medianmunsorted.median,6);
ipermute.shuffle(mshould);
unchecked_test("shuffle",mshould.str,"");
test("perm 5, shuffle",is_permutation(mshould,mdoes),true);
isort.sort(mshould);
test("binary search",isearch.binary_search(mshould,7),5);
test("index_of",isearch.index_of(mshould,7),5);
test("index_if",isearch.index_if(mshould,bind(_.is_eq(7))),5);
test("count",ialg.count(mshould,3),2);
-- test("count_if",ialg.count_if(mshould,bind(_:INT.is_eq(3))),2);
res: ARRAY{INT};
res := m1.copy; res.map((bind(_.times(3))));
mapres:ARRAY{INT} := |6,9,15|; -- untested?
test("some",imember.some(m1,bind(_.is_eq(3))),true);
test("some",imember.some(m1,bind(_.is_eq(15))),false);
test("every",imember.every(m1,bind(_.is_eq(3))),false);
test("every",imember.every(m1,bind(_.is_lt(15))),true);
test("notany",imember.notany(m1,bind(_.is_eq(3))),false);
test("notany",imember.notany(m1,bind(_.is_eq(15))),true);
test("notevery",imember.notevery(m1,bind(_.is_eq(3))),true);
test("notevery",imember.notevery(m1,bind(_.is_lt(15))),false);
test("reduce",ialg.reduce(m1,bind(_.times(_)),1),30);
res := m1.copy; res.scan(bind(_.times(_)));
scanres: ARRAY{INT} := |2,6,30|;
test("scan",res.str,scanres.str);
m1new: ARRAY{INT} := |4,7,9|;
res := m1.copy; res.copy(m1new);
test("to",res.str,m1new.str);
a2: ARRAY{INT} := |1,2,3,5,5|;
a1: ARRAY{INT} := |1,2,3,4,5|;
test("mismatch",ialg.mismatch(a1,a2),3);
finish;
end;
is_permutation(p1,p2: ARRAY{INT}): BOOL is
l1 ::= p1.copy; isort.sort(p1);
l2 ::= p2.copy; isort.sort(p2);
return ipermute.sorted_is_permutation(p1,p2);
end;
end;
class TEST_LIST
class TEST_LIST is
include TEST;
main is
class_name("LIST");
e ::= LIST{INT}::create_from(|5,2,1,4|);
test("copy",e,e.copy);
test("size",e.size,4);
e.append(12);
r1: ARRAY{INT} := |5,2,1,4,12|;
test("append",e.str,r1.str);
ra:ARRAY{INT} := |3,-1,2|;
e.append_all(ra);
r2: ARRAY{INT} := |5,2,1,4,12,3,-1,2|;
test("apend_elts",e,r2.str);
f: LIST{INT} := LIST{INT}::create_sized(4);
test("size",f.size,4);
f[1] := 3;
f.resize(15);
test("resize",f.size,15);
test("aget",f[1],3);
f[12] := 13;
test("aget",f[12],13);
f.remove_index(10);
test("remove_index",f.size,14);
test("aget remove",f[11],13);
finish;
end;
end;