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