1(*
2    Title:      Standard Basis Library: Vector and Array 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_ARRAY and MONO_VECTOR signatures contain a number of functions for operating over
21   vectors and arrays.  Many of these do not require bounds checking so they can be implemented
22   without the checks.  This functor provides basic implementations which can be overridden if
23   necessary.
24   unsafeSet is used only in the modify functions which are only exported from arrays. *)
25
26functor VectorOperations(
27    type vector
28    type elem
29    val length: vector -> word
30    val unsafeSub: vector * word -> elem
31    val unsafeSet: vector * word * elem -> unit (* Array only *)
32):
33    sig
34    val appi : ((int * elem) -> unit) -> vector -> unit
35    val app : (elem -> unit) -> vector -> unit
36    val foldli : ((int * elem * 'b) -> 'b) -> 'b -> vector -> 'b
37    val foldri : ((int * elem * 'b) -> 'b) -> 'b -> vector -> 'b
38    val foldl : ((elem * 'b) -> 'b) -> 'b -> vector -> 'b
39    val foldr : ((elem * 'b) -> 'b) -> 'b -> vector -> 'b
40    val modifyi : ((int * elem) -> elem) -> vector -> unit (* Array only *)
41    val modify : (elem -> elem) -> vector -> unit (* Array only *)
42    val findi: (int * elem -> bool) -> vector -> (int * elem) option
43    val find: (elem -> bool) -> vector -> elem option
44    val exists: (elem -> bool) -> vector -> bool
45    val all: (elem -> bool) -> vector -> bool
46    val collate: (elem * elem -> order) -> vector * vector -> order
47    end =
48struct
49        val wordAsInt: word -> int = RunCall.unsafeCast
50        
51        (* Apply a function to each element in turn *)
52        fun appi f vec =
53        let
54            val len = length vec
55            fun doapp j =
56                if j >= len then ()
57                else (f(wordAsInt j, unsafeSub(vec, j)); doapp(j+0w1))
58        in
59            doapp 0w0
60        end
61    
62        fun app f vec =
63        let     
64            val len = length vec
65            fun doapp j = 
66                if j >= len then ()
67                else (f(unsafeSub(vec, j)); doapp(j+0w1))
68        in
69            doapp 0w0
70        end
71        
72        (* Fold a function over a array. *)
73        (* foldl - increasing index *)
74        fun foldl f init vec =
75        let
76            val len = length vec
77            fun dofold j acc = 
78                if j >= len then acc
79                else dofold (j+0w1) (f (unsafeSub(vec, j), acc))
80        in
81            dofold 0w0 init
82        end
83    
84        fun foldli f init vec =
85        let 
86            val len = length vec
87            fun dofold j acc = 
88                if j >= len then acc
89                else dofold (j+0w1) (f (wordAsInt j, unsafeSub(vec, j), acc))
90        in
91            dofold 0w0 init
92        end
93    
94        (* foldr - decreasing index *)
95        fun foldr f init vec =
96        let
97            val len = length vec
98            fun dofold j acc = 
99                if j = 0w0 then acc
100                else dofold (j-0w1) (f (unsafeSub(vec, j-0w1), acc))
101        in
102            dofold len init
103        end
104        
105        fun foldri f init vec =
106        let
107            val len = length vec
108            fun dofold j acc = 
109                if j = 0w0 then acc
110                else dofold (j-0w1) (f (wordAsInt(j-0w1), unsafeSub(vec, j-0w1), acc))
111        in
112            dofold len init
113        end
114        
115        (* Apply a function to each element in turn and update the array with the
116           new values. *)
117        fun modifyi f vec =
118        let                     
119            val len = length vec
120            fun doupdate j =
121                if j >= len then ()
122                else (unsafeSet(vec, j, f(wordAsInt j, unsafeSub(vec, j)));
123                      doupdate(j+0w1))
124        in
125            doupdate 0w0
126        end
127    
128        fun modify f vec =
129        let
130            val len = length vec
131            fun doupdate j = 
132                if j >= len then ()
133                else (unsafeSet(vec, j, f(unsafeSub(vec, j))); doupdate(j+0w1))
134        in
135            doupdate 0w0
136        end
137
138        (* Find a character that matches the predicate. *)
139        fun findi pred vec =
140        let 
141            val len = length vec
142            fun dofind j = 
143                if j >= len then NONE
144                else
145                let
146                    val v = unsafeSub(vec, j)
147                in
148                    if pred(wordAsInt j, v)
149                    then SOME (wordAsInt j, v)
150                    else dofind (j+0w1)
151                end
152        in
153            dofind 0w0
154        end
155        
156        fun find pred vec =
157        let
158            val len = length vec
159            fun dofind j = 
160                if j >= len then NONE
161                else
162                let
163                    val v = unsafeSub(vec, j)
164                in
165                    if pred v
166                    then SOME v
167                    else dofind (j+0w1)
168                end
169        in
170            dofind 0w0
171        end
172
173        fun exists f arr = Option.isSome(find f arr)
174        
175        fun all pred arr = not (exists (not o pred) arr)
176
177        fun collate cmp (vec1, vec2) =
178        let 
179            val len1 = length vec1 and len2 = length vec2
180            (* Keep comparing items until either we come to the end of one of the arrays or
181               we find a mismatch. *)
182            fun dotest j =
183                if j >= len1 then if len1 = len2 then EQUAL else (* j < len2 *) LESS
184                else if j >= len2 then (* But j < len1, so a1 is longer *) GREATER
185                else case cmp(unsafeSub(vec1, j), unsafeSub(vec2, j)) of
186                    LESS => LESS
187                |   GREATER => GREATER
188                |   EQUAL => dotest (j+0w1)
189        in
190            dotest 0w0
191        end
192end;
193