(* Array2 -- as of 1995-09-12, 1997-03-12, 1998-04-07 *) (* Representation of an m * n array: an m-vector of n-arrays (rows),   and the dimensions (m, n), m = number of rows, n = number of columns. *) (* The implementation below is pretty naive, using the Array and Vector    operations and doing more bounds checks than strictly necessary.  *) type 'a array = ('a Array.array Vector.vector * int * int) ref  datatype traversal = RowMajor | ColMajor type 'a region = { base : 'a array, row : int, col : int, 		   nrows : int option, ncols : int option} fun fromList [] = ref (Vector.fromList [], 0, 0)  | fromList (xs1 :: xsr) =    let val row1 = Array.fromList xs1	val rowr = List.map Array.fromList xsr	val cols = Array.length row1	val vec = 	    if List.all (fn r => Array.length r = cols) rowr then		Vector.fromList (row1 :: rowr)	    else		raise Size    in 	ref (vec, Vector.length vec, cols)    end fun array (m, n, x) =     ref (Vector.tabulate(m, fn _ => Array.array(n, x)), m, n); fun tabulate RowMajor (m, n, f) =     ref (Vector.tabulate(m, fn i => Array.tabulate(n, fn j => f(i,j))), m, n)  | tabulate ColMajor (m, n, f) =     if m > 0 andalso n > 0 then 	let val f00 = f(0, 0)	    val arr = Vector.tabulate(m, fn i => Array.array(n, f00))	    (* Column 0: do not apply f to (0,0) again: *)	    val _ = Vector.appi (fn (r, a) => Array.update(a, 0, f(r, 0))) 		                (arr, 1, NONE); 			    (* Remaining columns: loop, updating all rows: *)	    fun loop c = 		if c < n then  		    (Vector.appi (fn (r, a) => Array.update(a, c, f(r, c))) 		                 (arr, 0, NONE); 		     loop (c+1))		else ()	in loop 1; ref (arr, m, n) end    else	tabulate RowMajor (m, n, f) fun dimensions (ref (a,m,n)) = (m,n); fun nRows (ref (a,m,n)) = m; fun nCols (ref (a,m,n)) = n; fun sub(ref (a,m,n), i, j) = Array.sub(Vector.sub(a, i), j); fun update(ref (a,m,n), i, j, x) = Array.update(Vector.sub(a, i), j, x); fun row (ref (a, _, _), i) =     Array.extract(Vector.sub(a, i), 0, NONE); fun column (ref (a, m, n), j) =     if j<0 orelse j>=n then raise Subscript    else Vector.tabulate(m, fn k => Array.sub(Vector.sub(a, k), j)) fun fold RowMajor f b (ref (a, _, _)) =     Vector.foldl (fn (xs, res) => Array.foldl f res xs) b a  | fold ColMajor f b (ref (a, m, n)) =     let fun rows j i b = 	    if i >= m then b 	    else rows j (i+1) (f(Array.sub(Vector.sub(a, i), j), b))	fun cols j b =	    if j >= n then b 	    else cols (j+1) (rows j 0 b)    in cols 0 b end fun stop len i NONE =     if i<0 orelse i>len then raise Subscript    else len  | stop len i (SOME n) =     if i<0 orelse n<0 orelse i+n>len then raise Subscript    else i+n; fun foldi RowMajor f b { base = ref (a, m, n), row, col, nrows, ncols } =     Vector.foldli            (fn (i, xs, res) => 	       Array.foldli (fn (j,x,res) => f(i,j,x,res)) res (xs,col,ncols))	   b (a, row, nrows)  | foldi ColMajor f b { base = ref (a, m, n), row, col, nrows, ncols } =     let val stoprow = stop m row nrows	val stopcol = stop n col ncols	fun rows j i b = 	    if i >= stoprow then b 	    else rows j (i+1) (f(i, j, Array.sub(Vector.sub(a, i), j), b))	fun cols j b =	    if j >= stopcol then b 	    else cols (j+1) (rows j row b)    in cols col b end fun app RowMajor f (ref (a, _, _)) =     Vector.app (Array.app f) a  | app ColMajor f arr  =    fold ColMajor (fn (a, _) => f a) () arr fun appi RowMajor f { base = ref (a, _, _), row, col, nrows, ncols } =    Vector.appi           (fn (i, xs) => Array.appi (fn (j, x) => f(i, j, x)) (xs, col, ncols))	  (a, row, nrows)  | appi ColMajor f reg =    foldi ColMajor (fn (i, j, a, _) => f (i, j, a)) () reg fun modify RowMajor f (ref (a, _, _)) =     Vector.app (Array.modify f) a  | modify ColMajor f arr =    foldi ColMajor (fn (i, j, a, _) => update(arr, i, j, f a)) ()          {base=arr, row=0, col=0, nrows=NONE, ncols=NONE} fun modifyi RowMajor f { base = ref (a, _, _), row, col, nrows, ncols } =    Vector.appi           (fn (i, xs) => Array.modifyi (fn (j, x) => f(i, j, x)) 	                               (xs, col, ncols))	  (a, row, nrows)  | modifyi ColMajor f (reg as {base, ...}) =    foldi ColMajor (fn (i, j, a, _) => update(base, i, j, f (i, j, a))) () reg fun copy { src = { base = ref (sa, sm, sn), row = src_row, col = src_col, 		   nrows, ncols }, 	   dst = ref (da, dm, dn), dst_row, dst_col } =    let val stoprow = stop sm src_row nrows	fun bottomUp from_row to_row = 	    if from_row < src_row then ()	    else		(Array.copy { src = Vector.sub(sa, from_row), 			      si = src_col, len = ncols,			      dst = Vector.sub(da, to_row),			      di = dst_col };		 bottomUp (from_row-1) (to_row-1))	fun topDown from_row to_row = 	    if from_row >= stoprow then ()	    else		(Array.copy { src = Vector.sub(sa, from_row), 			      si = src_col, len = ncols,			      dst = Vector.sub(da, to_row),			      di = dst_col };		 topDown (from_row+1) (to_row+1))    in	if src_row <= dst_row then (* top dst overlaps with bot src; 				      copy bottom-up *)	    bottomUp (stoprow-1) (stoprow-1+dst_row-src_row)	else (* bot dst overlaps with top src; copy top-down *)	    topDown src_row dst_row    end