1(*
2    Title:      Standard Basis Library: Vector and Array slice functor
3    Copyright   David C.J. Matthews 2005
4
5    This library is free software; you can redistribute it and/or
6    modify it under the terms of the GNU Lesser General Public
7    License as published by the Free Software Foundation; either
8    version 2.1 of the License, or (at your option) any later version.
9
10    This library is distributed in the hope that it will be useful,
11    but WITHOUT ANY WARRANTY; without even the implied warranty of
12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13    Lesser General Public License for more details.
14
15    You should have received a copy of the GNU Lesser General Public
16    License along with this library; if not, write to the Free Software
17    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
18*)
19
20(* The mono vector slice and mono array slice operations can all be combined
21   into this functor fairly easily.  Where appropriate functions can be
22   redefined in the calling structure. *)
23
24functor VectorSliceOperations(
25    type vector
26    type elem
27    val vecLength: vector -> word
28    val unsafeVecSub: vector * word -> elem
29    val unsafeVecUpdate: vector * word * elem -> unit (* Array only *)
30):
31    sig
32    (*type slice*)
33    datatype slice = Slice of { vector: vector,  start: word, length: word };
34
35    val length : slice -> int
36    val sub : (slice * int) -> elem
37    val full: vector -> slice
38    val slice: vector * int * int option -> slice
39    val subslice: slice * int * int option -> slice
40    val base: slice -> vector * int * int
41    val isEmpty: slice -> bool
42    val getItem: slice -> (elem * slice) option
43
44    val appi : ((int * elem) -> unit) -> slice -> unit
45    val app : (elem -> unit) -> slice -> unit
46    val foldli : ((int * elem * 'a) -> 'a) -> 'a -> slice -> 'a
47    val foldri : ((int * elem * 'a) -> 'a) -> 'a -> slice -> 'a
48    val foldl : ((elem * 'a) -> 'a) -> 'a -> slice -> 'a
49    val foldr : ((elem * 'a) -> 'a) -> 'a -> slice -> 'a
50    val findi: (int * elem -> bool) -> slice -> (int * elem) option
51    val find: (elem -> bool) -> slice -> elem option
52    val exists: (elem -> bool) -> slice -> bool
53    val all: (elem -> bool) -> slice -> bool
54    val collate: (elem * elem -> order) -> slice * slice -> order
55
56    (* These functions modify the vector or array. They aren't used for vectors. *)
57    val update: slice * int * elem -> unit
58    val modifyi : (int * elem -> elem) -> slice -> unit
59    val modify : (elem -> elem) -> slice -> unit
60    end =
61struct
62        val wordAsInt: word -> int = RunCall.unsafeCast
63
64        type elem = elem
65        type vector = vector
66        datatype slice = Slice of { vector: vector,  start: word, length: word };
67
68        fun length(Slice{length, ...}) = wordAsInt length
69
70        fun op sub (Slice{vector, start, length}, i: int) =
71        let
72            (* Check that the value is non-negative and short and cast it to word. *)
73            val iW = LibrarySupport.unsignedShortOrRaiseSubscript i
74        in
75            if iW >= length then raise General.Subscript
76            else unsafeVecSub(vector, iW+start)
77        end
78
79        (* update obviously doesn't apply to vector slices which are immutable. This function
80           is filtered out by the caller's signature. *)
81        fun update(Slice{vector, start, length}, i: int, x: elem) =
82        let
83            (* Check that the value is non-negative and short and cast it to word. *)
84            val iW = LibrarySupport.unsignedShortOrRaiseSubscript i
85        in
86            if iW >= length then raise General.Subscript
87            else unsafeVecUpdate(vector, iW+start, x)
88        end
89
90        (* Slice from the whole vector. *)
91        fun full v = Slice{vector=v, start=0w0, length=vecLength v}
92
93        (* Create a slice from a vector. *)
94        fun slice(vec: vector, i: int, NONE) =
95            let
96                val iW = LibrarySupport.unsignedShortOrRaiseSubscript i
97                val len = vecLength vec
98            in
99                if iW <= len
100                then Slice{vector=vec, start=iW, length=len-iW} (* Length is rest of vector. *)
101                else raise General.Subscript
102            end
103         |  slice(vec: vector, i: int, SOME l) =
104            let
105                val len = vecLength vec
106                val iW = LibrarySupport.unsignedShortOrRaiseSubscript i
107                val lW = LibrarySupport.unsignedShortOrRaiseSubscript l
108            in
109                if iW+lW <= len
110                then Slice{vector=vec, start=iW, length=lW} (* Length is as given. *)
111                else raise General.Subscript
112            end
113
114        (* Slice from existing slice *)
115        fun subslice(Slice{vector, start, length}, i: int, NONE) =
116            let
117                val iW = LibrarySupport.unsignedShortOrRaiseSubscript i
118            in
119                if iW <= length
120                then Slice{vector=vector, start=iW+start, length=length-iW} (* Length is rest of array. *)
121                else raise General.Subscript
122            end
123
124         |  subslice(Slice{vector, start, length}, i: int, SOME l) =
125            let
126                val iW = LibrarySupport.unsignedShortOrRaiseSubscript i
127                val lW = LibrarySupport.unsignedShortOrRaiseSubscript l
128            in
129                if iW+lW <= length
130                then Slice{vector=vector, start=iW+start, length=lW} (* Length is as given. *)
131                else raise General.Subscript
132            end
133
134        fun base(Slice{vector, start, length}) = (vector, wordAsInt start, wordAsInt length)
135
136        fun isEmpty(Slice{length, ...}) = length = 0w0
137
138        (* Return the first item of the slice and the rest of the slice. *)
139        fun getItem(Slice{length=0w0, ...}) = NONE
140         |  getItem(Slice{vector, start, length}) =
141                SOME(unsafeVecSub(vector, start), Slice{vector=vector, start=start+0w1, length=length-0w1})
142
143        (* Standard vector operations. *)
144        structure VectorOps =
145            VectorOperations(
146                struct
147                    type vector = slice and elem = elem
148                    fun length(Slice{length, ...}) = length
149                    fun unsafeSub (Slice{vector, start, ...}, i) = unsafeVecSub(vector, start + i)
150                    fun unsafeSet (Slice{vector, start, ...}, i, x) = unsafeVecUpdate(vector, start + i, x)
151                end);
152
153        open VectorOps;
154end;
155