lib/mlton/basic/array.fun

   1 (* Copyright (C) 1999-2006 Henry Cejtin, Matthew Fluet, Suresh
   2  *    Jagannathan, and Stephen Weeks.
   3  *
   4  * MLton is released under a BSD-style license.
   5  * See the file MLton-LICENSE for details.
   6  *)
   7
   8 functor Array (S: sig
   9                      include ARRAY_STRUCTS
  10                      val unsafeSub: 'a t * int -> 'a
  11                      val unsafeUpdate: 'a t * int * 'a -> unit
  12                   end): ARRAY =
  13 struct
  14
  15 open S
  16
  17 local
  18    structure V = Vector (S)
  19 in
  20    open V
  21 end
  22
  23 val array = new
  24
  25 fun modify (a, f) = foreachi (a, fn (i, x) => unsafeUpdate (a, i, f x))
  26
  27 fun swap (a, i, j) =
  28    let val t = sub (a, i)
  29    in unsafeUpdate (a, i, sub (a, j))
  30       ; unsafeUpdate (a, j, t)
  31    end
  32
  33 fun shuffleN (a, n) =
  34    let
  35       val m = length a
  36    in
  37       Int.for (0, n, fn i => swap (a, i, i + Random.natLessThan (m - i)))
  38    end
  39
  40 fun shuffle a = shuffleN (a, length a)
  41
  42 fun getAndSet a = (fn i => sub (a, i),
  43                    fn (i, x) => update (a, i, x))
  44
  45 fun fromListRev l =
  46    case l of
  47       [] => new0 ()
  48     | x :: l =>
  49          let
  50             val n = List.length l
  51             val a = new (n + 1, x)
  52             fun loop (l, i) =
  53                case l of
  54                   [] => ()
  55                 | x :: l => (unsafeUpdate (a, i, x)
  56                              ; loop (l, i - 1))
  57             val _ = loop (l, n - 1)
  58          in a
  59          end
  60
  61 fun toVectorMap (a, f) = Vector.tabulate (length a, fn i => f (sub (a, i)))
  62
  63 fun toVector a = toVectorMap (a, fn x => x)
  64
  65 fun fromVector v = tabulate (Vector.length v, fn i => Vector.sub (v, i))
  66
  67 end