------------------------->  GNU Sather - sourcefile  <-------------------------
-- Copyright (C) 1995 by International Computer Science Institute            --
-- This file is part of the GNU Sather library. It is free software; you may --
-- redistribute  and/or modify it under the terms of the GNU Library General --
-- Public  License (LGPL)  as published  by the  Free  Software  Foundation; --
-- either version 2 of the license, or (at your option) any later version.   --
-- This  library  is distributed  in the  hope that it will  be  useful, but --
-- WITHOUT ANY WARRANTY without even the implied warranty of MERCHANTABILITY --
-- or FITNESS FOR A PARTICULAR PURPOSE. See Doc/LGPL for more details.       --
-- The license text is also available from:  Free Software Foundation, Inc., --
-- 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA                     --
-------------->  Please email comments to <bug-sather@gnu.org>  <--------------

-- Author: Benedict A. Gomes <gomes@tiramisu.ICSI.Berkeley.EDU>

class ARR_PERMUTE_ALG{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: ARR_PERMUTE_ALG{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 ARR_SORT_ALG{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;
------------------------------------------------------------------------------
