a_permute.sa
Generated by gen_html_sa_files from ICSI. Contact gomes@icsi.berkeley.edu for details
---------------------------> Sather 1.1 source file <--------------------------
-- permute_alg.sa: Permutations of an array
-- Author: Benedict A. Gomes <gomes@tiramisu.ICSI.Berkeley.EDU>
-- Copyright (C) 1995, International Computer Science Institute
-- $Id: a_permute.sa,v 1.4 1996/06/01 21:36:06 gomes 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 A_PERMUTE{ETP,ATP<$ARR{ETP}}
class A_PERMUTE{ETP,ATP<$ARR{ETP}} is
-- Permutation algorithms - a bit bare right now.
-- Usage:
-- src: ARRAY{INT} := |1,2,5|;
-- p: FLIST{INT} := #(|2,1,0|);
-- dest: ARRAY{INT} := #(3);
-- i.e. first element of "src" s[0]=1 goes to dest[2]
-- 2nd elt of src (2) goes to dest[1]
-- 3rd elt of src (5) goes to dest[0]
-- perm_alg: A_PERMUTE{INT,ARRAY{INT}};
-- perm_alg.permute_into(src,p,dest);
-- Should permute src into |5,2,1|;
include COMPARE{ETP};
private is_sorted(a: ATP): BOOL is
return A_SORT{ETP,ATP}::is_sorted(a);
end;
-- ------------------- Queries -------------------------
sorted_is_permutation(p1,p2: ATP): BOOL
-- Inputs must be sorted
-- True if p1 is a permutation of p2.
-- Requires self and p2 to both be pre-sorted
pre is_sorted(p1) and is_sorted(p2)
is
sz: INT := p1.size;
if p2.size /= sz then return false end;
i: INT := 0; loop until!(i >= sz);
if ~elt_eq(p1[i],p2[i]) then return false end;
i := i + 1;
end;
return true;
end;
-- ------------------- Basic Operations ----------------
to_reverse(a:ATP) is
-- Reverse the order of the elements in self. Self may be void.
if ~void(a) then
loop
i::=(a.size/2).times!;
u::=a.size-i-1;
t::=a[i]; a[i]:=a[u]; a[u]:=t;
end
end
end;
shuffle(a:ATP)
-- Shuffle the elements of self. This is a trivial, obvious
-- implementation, but not sure if it is sufficient for good randomness
is
loop i ::= a.size.times!;
s ::= RND::int(0,a.size-1);
t::= a[s]; a[s] := a[i]; a[i] := t;
end;
end;
permute_into(src:ATP,new_pos:$ARR{INT},dest:ATP)
-- Copy the entries from src into dest using
-- the permutation array "new_positions"
-- src[i] -> dest[new_pos[i]]
-- Look at new_pos as a mapping from domain indices to range indices
-- src: ARRAY{INT} := |1,2,5|;
-- p: FLIST{INT} := #(|2,1,0|);
-- dest: ARRAY{INT} := #(3);
-- i.e. first element of "src" s[0]=1 goes to dest[2]
-- 2nd elt of src (2) goes to dest[1]
-- 3rd elt of src (5) goes to dest[0]
-- permute_into(src,p,dest); -- Destination= |5,2,1|;
is
i ::= 0; sz ::= src.size;
loop until!(i>=sz);
new_i: INT := new_pos[i];
assert(valid_ind(dest,new_i));
dest[new_i] := src[i];
i := i +1;
end;
end;
private valid_ind(dest: ATP,i: INT): BOOL is
if i.is_bet(0,dest.size-1) then return true
else
#ERR+"Invalid index:"+i+" for array of size:"+dest.size+"\n";
return false;
end;
end;
end;