Commit | Line | Data |
---|---|---|
7f918cf1 CE |
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 |