A => persistent-array-slice.sig +23 -0
@@ 0,0 1,23 @@
+
+signature PERSISTENT_ARRAY_SLICE = sig
+
+ structure PersistentArray : PERSISTENT_ARRAY
+
+ type 'a slice
+
+ val length : 'a slice -> int
+ val sub : 'a slice * int -> 'a
+ val full : 'a PersistentArray.array -> 'a slice
+ val slice : 'a PersistentArray.array * int * int option -> 'a slice
+ val subslice : 'a slice * int * int option -> 'a slice
+ val base : 'a slice -> 'a PersistentArray.array * int * int
+ val array : 'a slice -> 'a PersistentArray.array
+ val isEmpty : 'a slice -> bool
+ val app : ('a -> unit) -> 'a slice -> unit
+ val appi : (int * 'a -> unit) -> 'a slice -> unit
+ val foldl : ('a * 'b -> 'b) -> 'b -> 'a slice -> 'b
+ val foldli : (int * 'a * 'b -> 'b) -> 'b -> 'a slice -> 'b
+ val foldr : ('a * 'b -> 'b) -> 'b -> 'a slice -> 'b
+ val foldri : (int * 'a * 'b -> 'b) -> 'b -> 'a slice -> 'b
+
+end
A => persistent-array-slice.sml +107 -0
@@ 0,0 1,107 @@
+
+structure PersistentArraySlice :>
+ PERSISTENT_ARRAY_SLICE
+ where type 'a PersistentArray.array = 'a PersistentArray.array
+= struct
+
+ structure PersistentArray = PersistentArray
+ structure A = PersistentArrayImpl
+ structure T = Word32TrieMap
+
+ datatype 'a slice = S of {
+ array : 'a A.array,
+ start : int,
+ count : int
+ }
+
+ fun makeRange (S { array, start, count }) =
+ (SOME (Word32.fromInt start),
+ if start + count = A.length array
+ then NONE
+ else (* Trie range is inclusive *)
+ SOME (Word32.fromInt (start + count - 1))
+ )
+
+ fun length (S { count, ... }) = count
+
+ fun sub (S { array, start, count }, i) =
+ if i < 0 orelse i >= count
+ then raise Subscript
+ else A.sub (array, start + i)
+
+ fun full array = S {
+ array = array,
+ start = 0,
+ count = A.length array
+ }
+
+ fun slice (array, start, countOpt) =
+ let val len = A.length array
+ in
+ if start < 0 orelse len < start (* start = len may be a valid
+ empty slice *)
+ then raise Subscript
+ else case countOpt of
+ NONE => S { array = array,
+ start = start,
+ count = len - start
+ }
+ | SOME count =>
+ if count < 0 orelse len < start + count
+ then raise Subscript
+ else S { array = array,
+ start = start,
+ count = count
+ }
+ end
+
+ fun subslice (S { array, start, count }, subStart, subCountOpt) =
+ if subStart < 0 orelse count < subStart
+ then raise Subscript
+ else case subCountOpt of
+ NONE => S { array = array,
+ start = start + subStart,
+ count = count - subStart
+ }
+ | SOME subCount =>
+ if subCount < 0 orelse count < subStart + subCount
+ then raise Subscript
+ else S { array = array,
+ start = start + subStart,
+ count = subCount
+ }
+
+ fun base (S { array, start, count }) = (array, start, count)
+
+ fun isEmpty (S { array, start, count }) = count = 0
+
+ fun array (s as S { array = { size, trie }, start, count }) =
+ { size = Word32.fromInt count,
+ trie = T.extractRange (trie, makeRange s)
+ }
+
+ fun foldl f acc (s as S { array = { size, trie }, start, count }) =
+ T.foldliRange (fn (_, x, acc) => f (x, acc))
+ acc (trie, makeRange s)
+
+ fun foldli f acc (s as S { array = { size, trie }, start, count }) =
+ T.foldliRange (fn (w, x, acc) => f (Word32.toInt w, x, acc))
+ acc (trie, makeRange s)
+
+ fun foldr f acc (s as S { array = { size, trie }, start, count }) =
+ T.foldriRange (fn (_, x, acc) => f (x, acc))
+ acc (trie, makeRange s)
+
+ fun foldri f acc (s as S { array = { size, trie }, start, count }) =
+ T.foldriRange (fn (w, x, acc) => f (Word32.toInt w, x, acc))
+ acc (trie, makeRange s)
+
+ fun app f (s as S { array = { size, trie }, start, count }) =
+ T.foldliRange (fn (_, x, _) => f x)
+ () (trie, makeRange s)
+
+ fun appi f (s as S { array = { size, trie }, start, count }) =
+ T.foldliRange (fn (w, x, _) => f (Word32.toInt w, x))
+ () (trie, makeRange s)
+
+end
M persistent-array.sml +4 -1
@@ 1,5 1,5 @@
-structure PersistentArray :> PERSISTENT_ARRAY = struct
+structure PersistentArrayImpl = struct
structure T = Word32TrieMap
@@ 149,3 149,6 @@ structure PersistentArray :> PERSISTENT_
tabulate (n, fn _ => x)
end
+
+structure PersistentArray : PERSISTENT_ARRAY = PersistentArrayImpl
+
M test.sml +114 -0
@@ 1006,6 1006,119 @@ structure PersistentArrayTest :> TESTS =
]
end
+
+structure PersistentArraySliceTest :> TESTS = struct
+
+ open TestSupport
+
+ val name = "persistent-array-slice"
+
+ structure A = PersistentArray
+ structure S = PersistentArraySlice
+
+ fun tests () = [
+ ( "empty",
+ fn () =>
+ S.isEmpty (S.full A.empty) andalso
+ S.isEmpty (S.slice (A.fromList ["hello", "world"], 1, SOME 0))
+ ),
+ ( "length",
+ fn () =>
+ check Int.toString (S.length (S.full A.empty), 0) andalso
+ check Int.toString (S.length (S.full (A.fromList ["hello", "world"])),
+ 2) andalso
+ check Int.toString (S.length (S.slice (A.fromList ["hello", "world"],
+ 1, NONE)),
+ 1) andalso
+ check Int.toString (S.length (S.slice (A.fromList ["hello", "world"],
+ 0, SOME 1)),
+ 1)
+ ),
+ ( "sub",
+ fn () =>
+ let val a = A.fromList [ "a", "b", "c", "d", "banana" ]
+ val s = S.slice (a, 2, SOME 2)
+ in
+ check_pairs id [(S.sub (s, 0), "c"),
+ (S.sub (s, 1), "d")]
+ andalso
+ ((S.sub (s, 2); false) handle Subscript => true)
+ andalso
+ ((S.sub (s, ~1); false) handle Subscript => true)
+ end
+ ),
+ ( "array",
+ fn () =>
+ let val a = A.fromList [ "a", "b", "c", "d", "banana" ]
+ in
+ check_lists id
+ (A.toList (S.array (S.full a)),
+ A.toList a)
+ andalso
+ check_lists id
+ (A.toList (S.array (S.slice (a, 1, NONE))),
+ [ "b", "c", "d", "banana" ])
+ andalso
+ check_lists id
+ (A.toList (S.array (S.slice (a, 1, SOME 2))),
+ [ "b", "c" ])
+ andalso
+ check_lists id
+ (A.toList (S.array (S.slice (a, 2, SOME 1))),
+ [ "c" ])
+ andalso
+ check_lists id
+ (A.toList (S.array (S.slice (a, 2, SOME 0))),
+ [ ])
+ end
+ ),
+ ( "base",
+ fn () =>
+ let val a = A.fromList [ "a", "b", "c", "d", "banana" ]
+ val (arr, s, c) = S.base (S.slice (a, 2, SOME 2))
+ in
+ check Int.toString (s, 2) andalso
+ check Int.toString (c, 2) andalso
+ check_lists id (A.toList arr, A.toList a)
+ end
+ ),
+ ( "foldl",
+ fn () =>
+ let val a = A.fromList [ "a", "b", "c", "d", "banana" ]
+ in
+ check_lists id
+ (S.foldl (op::) [] (S.slice (a, 2, NONE)),
+ [ "banana", "d", "c" ])
+ andalso
+ check_lists id
+ (S.foldl (op::) [] (S.slice (a, 0, SOME 3)),
+ [ "c", "b", "a" ])
+ andalso
+ check_lists id
+ (S.foldl (op::) [] (S.slice (a, 2, SOME 0)),
+ [ ])
+ end
+ ),
+ ( "foldr",
+ fn () =>
+ let val a = A.fromList [ "a", "b", "c", "d", "banana" ]
+ in
+ check_lists id
+ (S.foldr (op::) [] (S.slice (a, 2, NONE)),
+ [ "c", "d", "banana" ])
+ andalso
+ check_lists id
+ (S.foldr (op::) [] (S.slice (a, 0, SOME 3)),
+ [ "a", "b", "c" ])
+ andalso
+ check_lists id
+ (S.foldr (op::) [] (S.slice (a, 2, SOME 0)),
+ [ ])
+ end
+ )
+ ]
+
+end
structure PersistentQueueTest :> TESTS = struct
@@ 1116,6 1229,7 @@ val trie_tests = [
(StringBTrieLocateTest.name, StringBTrieLocateTest.tests ()),
(HashMapTest.name, HashMapTest.tests ()),
(PersistentArrayTest.name, PersistentArrayTest.tests ()),
+ (PersistentArraySliceTest.name, PersistentArraySliceTest.tests ()),
(PersistentQueueTest.name, PersistentQueueTest.tests ())
]
M trie.mlb +2 -0
@@ 23,5 23,7 @@ string-tries.sml
string-hash-map.sml
persistent-array.sig
persistent-array.sml
+persistent-array-slice.sig
+persistent-array-slice.sml
persistent-queue.sig
persistent-queue.sml