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