(* Copyright (C) 1989, Digital Equipment Corporation           *)
(* All rights reserved.                                        *)
(* See the file COPYRIGHT for a full description.              *)

(* Created September 1989 by Bill Kalsow                       *)
(* Based on RandPerm.def by Mark Manasse                       *)
(* Last modified on Thu Jan 25 21:34:26 PST 1990 by stolfi     *)
(*      modified on Thu Nov  2 18:28:01 1989 by muller         *)
(*      modified on Fri Sep 29 09:33:36 1989 by kalsow         *)

INTERFACE RandomPerm;

(* Pseudo-random permutations.

   This module exports procedures for creating and enumerating
   pseudo-random permutations.

   Index: random permutations; permutations, random *)

IMPORT Random;

EXCEPTION Exhausted;

TYPE T <: REFANY;

TYPE Quality = {LowQuality, HighQuality};

PROCEDURE New (source  : Random.T;
               num     : CARDINAL;
               quality := Quality.HighQuality): T RAISES {};
  (* Create a permutation object /t/. Sucessive calls to Next(t) will
     returns elements in [0..num-1] in some permuted order.
     HighQuality permutations use the standard card-shuffling
     algorithm, and thus require space O(num).  LowQuality permutations
     are not really very random but use constant space, and work for
     num up to 2^30-1. *)

PROCEDURE Next (t: T): CARDINAL RAISES {Exhausted};
  (* Return the next element of the permutation /t/.  Raises Exhausted
     if every element has been enumerated; subsequent calls will repeat
     the same sequence. Don't call this concurrently for the same
     permutation. *)

PROCEDURE Size (t: T): CARDINAL RAISES {};
  (* Returns the number of elements in the permutation /t/. *)

PROCEDURE Index (t: T): CARDINAL RAISES {};
  (* Returns the index of the next element. It starts at 0 and is
     incremented at each sucessful Next(t). When Index(t) = Size(t),
     calling Next(t) will raise Exhausted and reset Index(t) to 0. *)

PROCEDURE Copy (t: T): T RAISES {};
  (* Duplicate an existing permutation. The result will start out
  with same Index as /t/. *)

PROCEDURE NewArr (source: Random.T; num: CARDINAL): (REF ARRAY OF CARDINAL)
  RAISES {};
  (* Returns a new HighQuality random permutation of [0..num-1] as
     an array. *)

PROCEDURE Fill (source : Random.T;
    VAR (*OUT*) perm   : ARRAY OF CARDINAL;
                num    : CARDINAL := LAST (CARDINAL)) RAISES {};
  (* Fills perm[0..num-1] with a new HighQuality random permutation
     of [0..num-1]. If /num/ is not specified, it defaults to
     NUMBER(perm). *)

END RandomPerm.