1(* 2 Title: Rebuild the basis library: Arrays and Vectors 3 Copyright David C.J. Matthews 2016 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 version 2.1 as published by the Free Software Foundation. 8 9 This library is distributed in the hope that it will be useful, 10 but WITHOUT ANY WARRANTY; without even the implied warranty of 11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 12 Lesser General Public License for more details. 13 14 You should have received a copy of the GNU Lesser General Public 15 License along with this library; if not, write to the Free Software 16 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 17*) 18 19useBasis "MONO_VECTOR"; 20 21functor MapMonoVector( 22 structure Old: 23 sig 24 type vector 25 type elem 26 val maxLen : FixedInt.int 27 val fromList : elem list -> vector 28 val tabulate : (FixedInt.int * (FixedInt.int -> elem)) -> vector 29 val length : vector -> FixedInt.int 30 val sub : (vector * FixedInt.int) -> elem 31 val update: vector * FixedInt.int * elem -> vector 32 val concat : vector list -> vector 33 val mapi : ((FixedInt.int * elem) -> elem) -> vector -> vector 34 val map : (elem -> elem) -> vector -> vector 35 val appi : ((FixedInt.int * elem) -> unit) -> vector -> unit 36 val app : (elem -> unit) -> vector -> unit 37 val foldli : ((FixedInt.int * elem * 'a) -> 'a) -> 'a -> vector -> 'a 38 val foldri : ((FixedInt.int * elem * 'a) -> 'a) -> 'a -> vector -> 'a 39 val foldl : ((elem * 'a) -> 'a) -> 'a -> vector -> 'a 40 val foldr : ((elem * 'a) -> 'a) -> 'a -> vector -> 'a 41 val findi: (FixedInt.int * elem -> bool) -> vector -> (FixedInt.int * elem) option 42 val find: (elem -> bool) -> vector -> elem option 43 val exists: (elem -> bool) -> vector -> bool 44 val all: (elem -> bool) -> vector -> bool 45 val collate: (elem * elem -> order) -> vector * vector -> order 46 end 47): MONO_VECTOR = 48struct 49 open Old 50 val maxLen = FixedInt.toLarge maxLen 51 val sub = fn (v, i) => sub(v, FixedInt.fromLarge i) 52 val length = FixedInt.toLarge o length 53 val update = fn (v, i, e) => update(v, FixedInt.fromLarge i, e) 54 val foldri = fn f => foldri (fn(i, e, a) => f(FixedInt.toLarge i, e, a)) 55 val foldli = fn f => foldli (fn(i, e, a) => f(FixedInt.toLarge i, e, a)) 56 val tabulate = fn (n, f) => tabulate(FixedInt.fromInt n, fn q => f(FixedInt.toInt q)) 57 val appi = fn f => appi(fn (i, e) => f(FixedInt.toLarge i, e)) 58 val mapi = fn f => mapi(fn (i, e) => f(FixedInt.toLarge i, e)) 59 val findi = fn f => fn v => 60 Option.map (fn(i, e) => (FixedInt.toLarge i, e)) (findi(fn (i, e) => f(FixedInt.toLarge i, e)) v) 61end; 62 63structure CharVector: MONO_VECTOR = MapMonoVector(structure Old = CharVector); 64structure BoolVector: MONO_VECTOR = MapMonoVector(structure Old = BoolVector); 65structure RealVector: MONO_VECTOR = MapMonoVector(structure Old = RealVector); 66structure Word8Vector: MONO_VECTOR = MapMonoVector(structure Old = Word8Vector); 67 68 69useBasis "VectorSignature.sml"; 70 71structure Vector: VECTOR = 72struct 73 open Vector 74 val maxLen = FixedInt.toLarge maxLen 75 val sub = fn (v, i) => sub(v, FixedInt.fromLarge i) 76 val length = fn l => FixedInt.toLarge(length l) 77 val update = fn (v, i, e) => update(v, FixedInt.fromLarge i, e) 78 val foldri = fn f => foldri (fn(i, e, a) => f(FixedInt.toLarge i, e, a)) 79 val foldli = fn f => foldli (fn(i, e, a) => f(FixedInt.toLarge i, e, a)) 80 val tabulate = fn (n, f) => tabulate(FixedInt.fromInt n, fn q => f(FixedInt.toInt q)) 81 val appi = fn f => appi(fn (i, e) => f(FixedInt.toLarge i, e)) 82 val mapi = fn f => mapi(fn (i, e) => f(FixedInt.toLarge i, e)) 83 val findi = fn f => fn v => 84 Option.map (fn(i, e) => (FixedInt.toLarge i, e)) (findi(fn (i, e) => f(FixedInt.toLarge i, e)) v) 85end; 86 87useBasis "MONO_ARRAY"; 88 89functor MapMonoArray( 90 structure Old: 91 sig 92 eqtype array 93 type elem 94 type vector 95 val maxLen : FixedInt.int 96 val array : (FixedInt.int * elem) -> array 97 val fromList : elem list -> array 98 val vector: array -> vector 99 val tabulate : (FixedInt.int * (FixedInt.int -> elem)) -> array 100 val length : array -> FixedInt.int 101 val sub : (array * FixedInt.int) -> elem 102 val update : (array * FixedInt.int * elem) -> unit 103 val copy : {src : array, dst : array, di : FixedInt.int} -> unit 104 val copyVec : {src : vector, dst : array, di : FixedInt.int} -> unit 105 val appi : ((FixedInt.int * elem) -> unit) -> array -> unit 106 val app : (elem -> unit) -> array -> unit 107 val foldli : ((FixedInt.int * elem * 'b) -> 'b) -> 'b -> array -> 'b 108 val foldri : ((FixedInt.int * elem * 'b) -> 'b) -> 'b -> array -> 'b 109 val foldl : ((elem * 'b) -> 'b) -> 'b -> array -> 'b 110 val foldr : ((elem * 'b) -> 'b) -> 'b -> array -> 'b 111 val modifyi : ((FixedInt.int * elem) -> elem) -> array -> unit 112 val modify : (elem -> elem) -> array -> unit 113 val findi: (FixedInt.int * elem -> bool) -> array -> (FixedInt.int * elem) option 114 val find: (elem -> bool) -> array -> elem option 115 val exists: (elem -> bool) -> array -> bool 116 val all: (elem -> bool) -> array -> bool 117 val collate: (elem * elem -> order) -> array * array -> order 118 end 119) : MONO_ARRAY = 120struct 121 open Old 122 val maxLen = FixedInt.toLarge maxLen 123 val array = fn (i, a) => array(FixedInt.fromLarge i, a) 124 val sub = fn (v, i) => sub(v, FixedInt.fromLarge i) 125 val length = fn l => FixedInt.toLarge(length l) 126 val update = fn (v, i, e) => update(v, FixedInt.fromLarge i, e) 127 val copy = fn {di, dst, src} => copy {di=FixedInt.fromLarge di, dst=dst, src=src} 128 val copyVec = fn {di, dst, src} => copyVec {di=FixedInt.fromLarge di, dst=dst, src=src} 129 val foldri = fn f => foldri (fn(i, e, a) => f(FixedInt.toLarge i, e, a)) 130 val foldli = fn f => foldli (fn(i, e, a) => f(FixedInt.toLarge i, e, a)) 131 val tabulate = fn (n, f) => tabulate(FixedInt.fromInt n, fn q => f(FixedInt.toInt q)) 132 val appi = fn f => appi(fn (i, e) => f(FixedInt.toLarge i, e)) 133 val findi = fn f => fn v => 134 Option.map (fn(i, e) => (FixedInt.toLarge i, e)) (findi(fn (i, e) => f(FixedInt.toLarge i, e)) v) 135 val modifyi = fn f => modifyi(fn (i, e) => f(FixedInt.toLarge i, e)) 136end; 137 138structure CharArray: MONO_ARRAY = MapMonoArray(structure Old = CharArray); 139structure BoolArray: MONO_ARRAY = MapMonoArray(structure Old = BoolArray); 140structure RealArray: MONO_ARRAY = MapMonoArray(structure Old = RealArray); 141structure Word8Array: MONO_ARRAY = MapMonoArray(structure Old = Word8Array); 142 143useBasis "ArraySignature.sml"; 144 145structure Array: ARRAY = 146struct 147 open Array 148 val maxLen = FixedInt.toLarge maxLen 149 val array = fn (i, a) => array(FixedInt.fromLarge i, a) 150 val sub = fn (v, i) => sub(v, FixedInt.fromLarge i) 151 val length = fn l => FixedInt.toLarge(length l) 152 val update = fn (v, i, e) => update(v, FixedInt.fromLarge i, e) 153 val copy = fn {di, dst, src} => copy {di=FixedInt.fromLarge di, dst=dst, src=src} 154 val copyVec = fn {di, dst, src} => copyVec {di=FixedInt.fromLarge di, dst=dst, src=src} 155 val foldri = fn f => foldri (fn(i, e, a) => f(FixedInt.toLarge i, e, a)) 156 val foldli = fn f => foldli (fn(i, e, a) => f(FixedInt.toLarge i, e, a)) 157 val tabulate = fn (n, f) => tabulate(FixedInt.fromInt n, fn q => f(FixedInt.toInt q)) 158 val appi = fn f => appi(fn (i, e) => f(FixedInt.toLarge i, e)) 159 val findi = fn f => fn v => 160 Option.map (fn(i, e) => (FixedInt.toLarge i, e)) (findi(fn (i, e) => f(FixedInt.toLarge i, e)) v) 161 val modifyi = fn f => modifyi(fn (i, e) => f(FixedInt.toLarge i, e)) 162end; 163 164useBasis "MONO_VECTOR_SLICE"; 165 166functor MapMonoVectorSlice( 167 structure Old: 168 sig 169 type vector 170 type elem 171 type slice 172 173 val length : slice -> FixedInt.int 174 val sub : (slice * FixedInt.int) -> elem 175 val full: vector -> slice 176 val slice: vector * FixedInt.int * FixedInt.int option -> slice 177 val subslice: slice * FixedInt.int * FixedInt.int option -> slice 178 val base: slice -> vector * FixedInt.int * FixedInt.int 179 val vector: slice -> vector 180 val concat: slice list -> vector 181 val isEmpty: slice -> bool 182 val getItem: slice -> (elem * slice) option 183 val appi : ((FixedInt.int * elem) -> unit) -> slice -> unit 184 val app : (elem -> unit) -> slice -> unit 185 val mapi : ((FixedInt.int * elem) -> elem) -> slice -> vector 186 val map : (elem -> elem) -> slice -> vector 187 val foldli : ((FixedInt.int * elem * 'a) -> 'a) -> 'a -> slice -> 'a 188 val foldri : ((FixedInt.int * elem * 'a) -> 'a) -> 'a -> slice -> 'a 189 val foldl : ((elem * 'a) -> 'a) -> 'a -> slice -> 'a 190 val foldr : ((elem * 'a) -> 'a) -> 'a -> slice -> 'a 191 val findi: (FixedInt.int * elem -> bool) -> slice -> (FixedInt.int * elem) option 192 val find: (elem -> bool) -> slice -> elem option 193 val exists: (elem -> bool) -> slice -> bool 194 val all: (elem -> bool) -> slice -> bool 195 val collate: (elem * elem -> order) -> slice * slice -> order 196 end 197): MONO_VECTOR_SLICE = 198struct 199 open Old 200 val sub = fn (v, i) => sub(v, FixedInt.fromLarge i) 201 val length = FixedInt.toLarge o length 202 val base = fn s => let val (a, i, j) = base s in (a, FixedInt.toInt i, FixedInt.toInt j) end 203 val slice = fn (v, i, l) => slice(v, FixedInt.fromLarge i, Option.map FixedInt.fromInt l) 204 val subslice = fn (v, i, l) => subslice(v, FixedInt.fromLarge i, Option.map FixedInt.fromInt l) 205 val foldri = fn f => foldri (fn(i, e, a) => f(FixedInt.toLarge i, e, a)) 206 val foldli = fn f => foldli (fn(i, e, a) => f(FixedInt.toLarge i, e, a)) 207 val appi = fn f => appi(fn (i, e) => f(FixedInt.toLarge i, e)) 208 val mapi = fn f => mapi(fn (i, e) => f(FixedInt.toLarge i, e)) 209 val findi = fn f => fn v => 210 Option.map (fn(i, e) => (FixedInt.toLarge i, e)) (findi(fn (i, e) => f(FixedInt.toLarge i, e)) v) 211end; 212 213structure CharVectorSlice: MONO_VECTOR_SLICE = MapMonoVectorSlice(structure Old = CharVectorSlice); 214structure RealVectorSlice: MONO_VECTOR_SLICE = MapMonoVectorSlice(structure Old = RealVectorSlice); 215structure Word8VectorSlice: MONO_VECTOR_SLICE = MapMonoVectorSlice(structure Old = Word8VectorSlice); 216 217useBasis "VectorSliceSignature.sml"; 218 219structure VectorSlice: VECTOR_SLICE = 220struct 221 open VectorSlice 222 val sub = fn (v, i) => sub(v, FixedInt.fromLarge i) 223 val length = fn l => FixedInt.toLarge(length l) 224 val base = fn s => let val (a, i, j) = base s in (a, FixedInt.toInt i, FixedInt.toInt j) end 225 val slice = fn (v, i, l) => slice(v, FixedInt.fromLarge i, Option.map FixedInt.fromInt l) 226 val subslice = fn (v, i, l) => subslice(v, FixedInt.fromLarge i, Option.map FixedInt.fromInt l) 227 val foldri = fn f => foldri (fn(i, e, a) => f(FixedInt.toLarge i, e, a)) 228 val foldli = fn f => foldli (fn(i, e, a) => f(FixedInt.toLarge i, e, a)) 229 val appi = fn f => appi(fn (i, e) => f(FixedInt.toLarge i, e)) 230 val mapi = fn f => mapi(fn (i, e) => f(FixedInt.toLarge i, e)) 231 val findi = fn f => fn v => 232 Option.map (fn(i, e) => (FixedInt.toLarge i, e)) (findi(fn (i, e) => f(FixedInt.toLarge i, e)) v) 233end; 234 235 236useBasis "MONO_ARRAY_SLICE"; 237 238functor MapMonoArraySlice( 239 structure Old: 240 sig 241 type elem 242 type array 243 type slice 244 type vector 245 type vector_slice 246 247 val length : slice -> FixedInt.int 248 val sub : (slice * FixedInt.int) -> elem 249 val update: slice * FixedInt.int * elem -> unit 250 val full: array -> slice 251 val slice: array * FixedInt.int * FixedInt.int option -> slice 252 val subslice: slice * FixedInt.int * FixedInt.int option -> slice 253 val base: slice -> array * FixedInt.int * FixedInt.int 254 val vector: slice -> vector 255 val copy : {src : slice, dst : array, di : FixedInt.int} -> unit 256 val copyVec : {src : vector_slice, dst : array, di : FixedInt.int} -> unit 257 val isEmpty: slice -> bool 258 val getItem: slice -> (elem * slice) option 259 val appi : ((FixedInt.int * elem) -> unit) -> slice -> unit 260 val app : (elem -> unit) -> slice -> unit 261 val modifyi : (FixedInt.int * elem -> elem) -> slice -> unit 262 val modify : (elem -> elem) -> slice -> unit 263 val foldli : ((FixedInt.int * elem * 'a) -> 'a) -> 'a -> slice -> 'a 264 val foldri : ((FixedInt.int * elem * 'a) -> 'a) -> 'a -> slice -> 'a 265 val foldl : ((elem * 'a) -> 'a) -> 'a -> slice -> 'a 266 val foldr : ((elem * 'a) -> 'a) -> 'a -> slice -> 'a 267 val findi: (FixedInt.int * elem -> bool) -> slice -> (FixedInt.int * elem) option 268 val find: (elem -> bool) -> slice -> elem option 269 val exists: (elem -> bool) -> slice -> bool 270 val all: (elem -> bool) -> slice -> bool 271 val collate: (elem * elem -> order) -> slice * slice -> order 272 end 273): MONO_ARRAY_SLICE = 274struct 275 open Old 276 val sub = fn (v, i) => sub(v, FixedInt.fromLarge i) 277 val length = FixedInt.toLarge o length 278 val update = fn (v, i, e) => update(v, FixedInt.fromLarge i, e) 279 val copy = fn {di, dst, src} => copy {di=FixedInt.fromLarge di, dst=dst, src=src} 280 val copyVec = fn {di, dst, src} => copyVec {di=FixedInt.fromLarge di, dst=dst, src=src} 281 val base = fn s => let val (a, i, j) = base s in (a, FixedInt.toInt i, FixedInt.toInt j) end 282 val slice = fn (v, i, l) => slice(v, FixedInt.fromLarge i, Option.map FixedInt.fromInt l) 283 val subslice = fn (v, i, l) => subslice(v, FixedInt.fromLarge i, Option.map FixedInt.fromInt l) 284 val foldri = fn f => foldri (fn(i, e, a) => f(FixedInt.toLarge i, e, a)) 285 val foldli = fn f => foldli (fn(i, e, a) => f(FixedInt.toLarge i, e, a)) 286 val appi = fn f => appi(fn (i, e) => f(FixedInt.toLarge i, e)) 287 val findi = fn f => fn v => 288 Option.map (fn(i, e) => (FixedInt.toLarge i, e)) (findi(fn (i, e) => f(FixedInt.toLarge i, e)) v) 289 val modifyi = fn f => modifyi(fn (i, e) => f(FixedInt.toLarge i, e)) 290end; 291 292structure CharArraySlice: MONO_ARRAY_SLICE = MapMonoArraySlice(structure Old = CharArraySlice); 293structure RealArraySlice: MONO_ARRAY_SLICE = MapMonoArraySlice(structure Old = RealArraySlice); 294structure Word8ArraySlice: MONO_ARRAY_SLICE = MapMonoArraySlice(structure Old = Word8ArraySlice); 295 296useBasis "ArraySliceSignature.sml"; (* Depends on VectorSlice. *) 297 298structure ArraySlice: ARRAY_SLICE = 299struct 300 open ArraySlice 301 val sub = fn (v, i) => sub(v, FixedInt.fromLarge i) 302 val length = fn l => FixedInt.toLarge(length l) 303 val update = fn (v, i, e) => update(v, FixedInt.fromLarge i, e) 304 val copy = fn {di, dst, src} => copy {di=FixedInt.fromLarge di, dst=dst, src=src} 305 val copyVec = fn {di, dst, src} => copyVec {di=FixedInt.fromLarge di, dst=dst, src=src} 306 val base = fn s => let val (a, i, j) = base s in (a, FixedInt.toInt i, FixedInt.toInt j) end 307 val slice = fn (v, i, l) => slice(v, FixedInt.fromLarge i, Option.map FixedInt.fromInt l) 308 val subslice = fn (v, i, l) => subslice(v, FixedInt.fromLarge i, Option.map FixedInt.fromInt l) 309 val foldri = fn f => foldri (fn(i, e, a) => f(FixedInt.toLarge i, e, a)) 310 val foldli = fn f => foldli (fn(i, e, a) => f(FixedInt.toLarge i, e, a)) 311 val appi = fn f => appi(fn (i, e) => f(FixedInt.toLarge i, e)) 312 val findi = fn f => fn v => 313 Option.map (fn(i, e) => (FixedInt.toLarge i, e)) (findi(fn (i, e) => f(FixedInt.toLarge i, e)) v) 314 val modifyi = fn f => modifyi(fn (i, e) => f(FixedInt.toLarge i, e)) 315end; 316 317(* Rebuild IntVector etc. They are defined in terms of polymorphic vector, array etc 318 and also we want the "Int" to be arbitrary precision. *) 319useBasis "IntArray"; 320 321useBasis "Text"; (* Rebuild the Text structure that includes Char, String etc. *) 322 323(* Array2 *) 324useBasis "Array2Signature.sml"; 325 326structure Array2: ARRAY2 = 327struct 328 open Array2 329 type 'a region = 330 { 331 base : 'a array, 332 row : int, 333 col : int, 334 nrows : int option, 335 ncols : int option 336 } 337 val array = fn(i, j, a) => array(FixedInt.fromLarge i, FixedInt.fromLarge j, a) 338 val sub = fn (a, i, j) => sub(a, FixedInt.fromLarge i, FixedInt.fromLarge j) 339 val update = fn (a, i, j, v) => update(a, FixedInt.fromLarge i, FixedInt.fromLarge j, v) 340 val tabulate = 341 fn t => 342 fn (i, j, f) => 343 tabulate t (FixedInt.fromLarge i, FixedInt.fromLarge j, fn (q, r) => f(FixedInt.toLarge q, FixedInt.toLarge r) ) 344 val row = fn (a, i) => row(a, FixedInt.fromLarge i) 345 and column = fn (a, i) => row(a, FixedInt.fromLarge i) 346 val dimensions = fn a => let val (x, y) = dimensions a in (FixedInt.toLarge x, FixedInt.toLarge y) end 347 val nCols = fn l => FixedInt.toLarge(nCols l) 348 val nRows = fn l => FixedInt.toLarge(nRows l) 349 350 local 351 fun mapRegion{base, row, col, nrows, ncols} = 352 {base = base, row = FixedInt.fromLarge row, col = FixedInt.fromLarge col, 353 nrows = Option.map FixedInt.fromLarge nrows, 354 ncols = Option.map FixedInt.fromLarge ncols } 355 356 fun modifyi' t f r = 357 modifyi t 358 (fn (i, j, v) => f(FixedInt.toLarge i, FixedInt.toLarge j, v)) 359 (mapRegion r) 360 and foldi' t f b r = 361 foldi t 362 (fn (i, j, a, b) => f(FixedInt.toLarge i, FixedInt.toLarge j, a, b)) 363 b (mapRegion r) 364 and appi' t f r = 365 appi t 366 (fn (i, j, v) => f(FixedInt.toLarge i, FixedInt.toLarge j, v)) 367 (mapRegion r) 368 and copy' {src, dst, dst_row, dst_col} = 369 copy {src = mapRegion src, dst = dst, dst_row = FixedInt.fromLarge dst_row, dst_col = FixedInt.fromLarge dst_col } 370 in 371 val modifyi = modifyi' 372 and foldi = foldi' 373 and appi = appi' 374 and copy = copy' 375 end 376end; 377 378(* Monomorphic two dimensional arrays. They are defined in terms of Array2 and also 379 for IntArray2 we want the base type to be arbitrary precision. *) 380useBasis "IntArray2.sml"; 381