1(* VectorSlice -- SML Basis Library 2 sestoft@dina.kvl.dk 2000-10-18 3*) 4 5local 6 type 'a vector = 'a Vector.vector; 7 8 prim_val vector_ : int -> 'x -> 'a vector = 2 "make_vect"; 9 prim_val subv_ : 'a vector -> int -> 'a = 2 "get_vect_item"; 10 prim_val updatev : 'a vector -> int -> 'a -> unit = 3 "set_vect_item"; 11in 12 13type 'a slice = 'a vector * int * int 14 15(* Invariant on values (a, i, n) of type 'a slice: 16 * 0 <= i <= i+n <= Vector.length a, 17 * or equivalently, 0 <= i and 0 <= n and i+n <= Vector.length a. 18 *) 19 20fun length (a, i, n) = n; 21 22fun sub((a', i', n'), i) = 23 if i<0 orelse i >= n' then raise Subscript 24 else subv_ a' (i'+i); 25 26fun slice (a, i, len) = 27 let val alen = Vector.length a 28 in 29 case len of 30 NONE => if 0<=i andalso i<=alen then (a, i, alen - i) 31 else raise Subscript 32 | SOME n => if 0<=i andalso 0<=n andalso n<=alen-i then (a, i, n) 33 else raise Subscript 34 end; 35 36fun full a = (a, 0, Vector.length a); 37 38fun subslice ((a, i, n), i', NONE) = 39 if 0<=i' andalso i'<=n then (a, i+i', n-i') 40 else raise Subscript 41 | subslice ((a, i, n), i', SOME n') = 42 if 0<=i' andalso 0<=n' andalso n'<=n-i' then (a, i+i', n') 43 else raise Subscript; 44 45fun base sli = sli; 46 47fun vector (a : 'a vector, i, n) = 48 let val newvec = vector_ n () : 'a vector 49 fun copy j = 50 if j<n then 51 (updatev newvec j (subv_ a (i+j)); copy (j+1)) 52 else 53 () 54 in copy 0; newvec end; 55 56fun isEmpty (_, _, n) = n=0; 57 58fun concat slis = 59 let fun acc [] len = len 60 | acc ((_, _, len1)::vr) len = acc vr (len1 + len) 61 val len = acc slis 0 62 val newvec = if len > Vector.maxLen then raise Size 63 else vector_ len () : 'a vector 64 fun copyall to [] = () (* Now: to = len *) 65 | copyall to ((v1, i1, n1)::slir) = 66 let fun copyv1 j = 67 if j<n1 then 68 (updatev newvec (to+j) (subv_ v1 (i1+j)); copyv1 (j+1)) 69 else 70 () 71 in 72 (copyv1 0; copyall (to+n1) slir) 73 end 74 in copyall 0 slis; newvec end; 75 76fun getItem (a, i, 0) = NONE 77 | getItem (a, i, n) = SOME(subv_ a i, (a, i+1, n-1)); 78 79fun find (p : 'a -> bool) ((a,i,n) : 'a slice) : 'a option = 80 let val stop = i+n 81 fun lr j = 82 if j < stop then 83 if p (subv_ a j) then SOME (subv_ a j) else lr (j+1) 84 else NONE 85 in lr i end; 86 87fun exists (p : 'a -> bool) ((a,i,n) : 'a slice) : bool = 88 let val stop = i+n 89 fun lr j = j < stop andalso (p (subv_ a j) orelse lr (j+1)) 90 in lr i end; 91 92fun all (p : 'a -> bool) ((a,i,n) : 'a slice) : bool = 93 let val stop = i+n 94 fun lr j = j >= stop orelse (p (subv_ a j) andalso lr (j+1)) 95 in lr i end; 96 97fun app f (a, i, n) = 98 let val stop = i+n 99 fun lr j = if j < stop then (f(subv_ a j); lr (j+1)) 100 else () 101 in lr i end; 102 103fun map (f : 'a -> 'b) (a : 'a vector, i, n) = 104 let val newvec = vector_ n () : 'b vector 105 val stop = i+n 106 fun lr j = 107 if j < stop then 108 (updatev newvec (j-i) (f(subv_ a j)); lr (j+1)) 109 else 110 () 111 in lr i; newvec end; 112 113fun foldl f e (a, i, n) = 114 let val stop = i+n 115 fun lr j res = if j < stop then lr (j+1) (f(subv_ a j, res)) 116 else res 117 in lr i e end; 118 119fun foldr f e (a, i, n) = 120 let fun rl j res = if j >= i then rl (j-1) (f(subv_ a j, res)) 121 else res 122 in rl (i+n-1) e end; 123 124fun findi (p : int * 'a -> bool) ((a,i,n) : 'a slice) : (int * 'a) option = 125 let val stop = i+n 126 fun lr j = 127 if j < stop then 128 if p (j, subv_ a j) then SOME (j, subv_ a j) else lr (j+1) 129 else 130 NONE 131 in lr i end; 132 133fun appi f (a, i, n) = 134 let val stop = i+n 135 fun lr j = 136 if j < stop then (f(j, subv_ a j); lr (j+1)) 137 else () 138 in lr i end; 139 140fun mapi (f : int * 'a -> 'b) (a : 'a vector, i, n) = 141 let val newvec = vector_ n () : 'b vector 142 val stop = i+n 143 fun lr j = 144 if j < stop then 145 (updatev newvec (j-i) (f(j, subv_ a j)); lr (j+1)) 146 else 147 () 148 in lr i; newvec end; 149 150fun foldli f e (a, i, n) = 151 let val stop = i+n 152 fun lr j res = 153 if j < stop then lr (j+1) (f(j, subv_ a j, res)) 154 else res 155 in lr i e end; 156 157fun foldri f e (a, i, n) = 158 let fun rl j res = 159 if j >= i then rl (j-1) (f(j, subv_ a j, res)) 160 else res 161 in rl (i+n-1) e end; 162 163fun collate cmp ((a1,i1,n1), (a2,i2,n2)) = 164 let val stop = if n1 < n2 then n1 else n2 165 fun h j = (* At this point a1[i1..i1+j-1] = a2[i2..i2+j-1] *) 166 if j = stop then if n1 < n2 then LESS 167 else if n1 > n2 then GREATER 168 else EQUAL 169 else 170 case cmp(subv_ a1 (i1+j), subv_ a2 (i2+j)) of 171 EQUAL => h (j+1) 172 | res => res 173 in h 0 end; 174 175end 176