(* 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.mod by Mark Manasse                       *)
(* Last modified on Fri Nov  1 14:45:57 PST 1991 by kalsow     *)
(*      modified on Mon Jan 29 21:16:45 PST 1990 by stolfi     *)
(*      modified on Thu Nov  2 18:28:00 1989 by muller         *)


MODULE RandomPerm;

IMPORT Word, Random;

REVEAL
  T = BRANDED REF RECORD
        num   : CARDINAL; (* Permutation size *)
        count : CARDINAL; (* Num of elements remaining *)
        qual  : Quality; (* Low or high *)

        (* If LowQuality: *)
        state : INTEGER; (* Current state *)
        mult  : INTEGER; (* Multiplier *)
        bits  : CARDINAL; (* CEILING(LOG2(num)), or 0 if num=0. *)

        (* If HighQuality: *)
        deck  : REF ARRAY OF CARDINAL; (* Current permutation *)
      END;

EXCEPTION ASSERT_FAILED;

PROCEDURE New (source  : Random.T;
               num     : CARDINAL;
               quality := Quality.HighQuality): T RAISES {} =
  <*FATAL ASSERT_FAILED*>
  VAR t: T; m, bits: CARDINAL;
  BEGIN
    t := NEW (T);
    t.qual := quality;
    t.num := num;
    t.count := num;
    CASE quality OF
    | Quality.LowQuality =>
        IF num = 0 THEN
          t.bits := 0
        ELSE
          m := num - 1;
          bits := 0;
          WHILE m # 0 DO m := m DIV 2; INC (bits) END;
          IF (bits > 30) THEN RAISE ASSERT_FAILED END;
          t.bits := bits;
        END;
        t.state := Word.Plus (Word.Times (Random.Cardinal (source), 2), 1);
        t.mult := Word.Plus (Word.Times (Random.Cardinal (source), 8), 3);
        IF ((Random.Cardinal (source) MOD 2) # 0) THEN INC (t.mult, 2) END
    | Quality.HighQuality =>
        t.deck := NEW (REF ARRAY OF CARDINAL, num);
        Fill (source, t.deck^, num);
    END;
    RETURN t
  END New;

PROCEDURE Next (t: T): CARDINAL RAISES {Exhausted} =
  VAR res: CARDINAL;
  BEGIN
    WITH z = t^ DO
      IF z.count = 0 THEN z.count := z.num; RAISE Exhausted END;
      DEC (z.count);
      CASE z.qual OF
      | Quality.LowQuality =>
          REPEAT
            z.state := Word.Times (z.state, z.mult);
            res := Word.Extract (Word.Plus (z.state, 1), 2, z.bits)
          UNTIL res < z.num
      | Quality.HighQuality =>
          res := z.deck[z.count]
      END
    END;
    RETURN res
  END Next;

PROCEDURE Size (t: T): CARDINAL RAISES {} =
  BEGIN
    RETURN t.num
  END Size;

PROCEDURE Index (t: T): CARDINAL RAISES {} =
  BEGIN
    RETURN t.num - t.count
  END Index;

PROCEDURE Copy (t: T): T RAISES {} =
  VAR s: T;
  BEGIN
    s := NEW (T);
    s^ := t^;
    RETURN s
  END Copy;

PROCEDURE NewArr (source: Random.T; num: CARDINAL): (REF ARRAY OF CARDINAL)
                                                                   RAISES {} =
  VAR perm: REF ARRAY OF CARDINAL;
  BEGIN
    perm := NEW (REF ARRAY OF CARDINAL, num);
    Fill (source, perm^, num);
    RETURN perm
  END NewArr;

PROCEDURE Fill (source : Random.T;
    VAR (*OUT*) perm   : ARRAY OF CARDINAL;
                num    : CARDINAL := LAST (CARDINAL)) RAISES {} =
  VAR j, t: CARDINAL;
  BEGIN
    IF num = LAST (CARDINAL) THEN num := NUMBER (perm) END;
    FOR i := 0 TO num - 1 DO perm[i] := i END;
    FOR i := 0 TO num - 2 DO
      j := Random.Subrange (source, i, num - 1);
      IF j # i THEN t := perm[j]; perm[j] := perm[i]; perm[i] := t END
    END
  END Fill;


BEGIN
END RandomPerm.