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;