1)abbrev category ARR2CAT TwoDimensionalArrayCategory
2++ Two dimensional array categories and domains
3++ Author:
4++ Date Created: 27 October 1989
5++ Keywords: array, data structure
6++ Examples:
7++ References:
8TwoDimensionalArrayCategory(R, Row, Col) : Category == Definition where
9  ++ TwoDimensionalArrayCategory is a general array category which
10  ++ allows different representations and indexing schemes.
11  ++ Rows and columns may be extracted with rows returned as objects
12  ++ of type Row and columns returned as objects of type Col.
13  ++ The index of the 'first' row may be obtained by calling the
14  ++ function 'minRowIndex'.  The index of the 'first' column may
15  ++ be obtained by calling the function 'minColIndex'.  The index of
16  ++ the first element of a 'Row' is the same as the index of the
17  ++ first column in an array and vice versa.
18  R   : Type
19  Row : IndexedAggregate(Integer, R)
20  Col : IndexedAggregate(Integer, R)
21
22  PI ==> PositiveInteger
23  NNI ==> NonNegativeInteger
24  LNNI ==> List(NNI)
25  LI ==> List(Integer)
26  SI ==> Segment(Integer)
27  LSI ==> List(SI)
28
29  Definition == Join(HomogeneousAggregate(R), _
30      shallowlyMutable, finiteAggregate) with
31
32    if R has Comparable then Comparable
33
34--% Array creation
35
36    new : (NonNegativeInteger, NonNegativeInteger, R) -> %
37      ++ new(m, n, r) is an m-by-n array all of whose entries are r
38    qnew : (NonNegativeInteger, NonNegativeInteger) -> %
39      ++ qnew(m, n) is is an m-by-n uninitilized array
40    fill! : (%, R) -> %
41      ++ fill!(m, r) fills m with r's
42
43--% Size inquiries
44
45    minRowIndex : % -> Integer
46      ++ minRowIndex(m) returns the index of the 'first' row of the array m
47    maxRowIndex : % -> Integer
48      ++ maxRowIndex(m) returns the index of the 'last' row of the array m
49    minColIndex : % -> Integer
50      ++ minColIndex(m) returns the index of the 'first' column of the array m
51    maxColIndex : % -> Integer
52      ++ maxColIndex(m) returns the index of the 'last' column of the array m
53    nrows : % -> NonNegativeInteger
54      ++ nrows(m) returns the number of rows in the array m
55    ncols : % -> NonNegativeInteger
56      ++ ncols(m) returns the number of columns in the array m
57
58--% Part extractions
59
60    elt : (%, Integer, Integer) -> R
61      ++ elt(m, i, j) returns the element in the ith row and jth
62      ++ column of the array m
63      ++ error check to determine if indices are in proper ranges
64    qelt : (%, Integer, Integer) -> R
65      ++ qelt(m, i, j) returns the element in the ith row and jth
66      ++ column of the array m
67      ++ NO error check to determine if indices are in proper ranges
68    elt : (%, Integer, Integer, R) -> R
69      ++ elt(m, i, j, r) returns the element in the ith row and jth
70      ++ column of the array m, if m has an ith row and a jth column,
71      ++ and returns r otherwise
72    row : (%, Integer) -> Row
73      ++ row(m, i) returns the ith row of m
74      ++ error check to determine if index is in proper ranges
75    column : (%, Integer) -> Col
76      ++ column(m, j) returns the jth column of m
77      ++ error check to determine if index is in proper ranges
78    parts : % -> List R
79      ++ parts(m) returns a list of the elements of m in row major order
80    listOfLists : % -> List List R
81       ++ \spad{listOfLists(m)} returns the rows of the array m as a list
82       ++ of lists.
83    subMatrix : (%, Integer, Integer, Integer, Integer) -> %
84       ++ \spad{subMatrix(x, i1, i2, j1, j2)} extracts the submatrix
85       ++ \spad{[x(i, j)]} where the index i ranges from \spad{i1} to \spad{i2}
86       ++ and the index j ranges from \spad{j1} to \spad{j2}.
87    elt : (%, Integer, LI) -> %
88       ++ \spad{elt(x, row, colList)} returns an 1-by-n array consisting
89       ++ of elements of x, where \spad{n = # colList}.
90       ++ If \spad{colList = [j<1>, j<2>, ..., j<n>]}, then the \spad{(k, l)}th
91       ++ entry of \spad{elt(x, row, colList)} is \spad{x(row, j<l>)}.
92    elt : (%, LI, Integer) -> %
93       ++ \spad{elt(x, rowList, col)} returns an m-by-1 array consisting
94       ++ of elements of x, where \spad{m = # rowList}.
95       ++ If \spad{rowList = [i<1>, i<2>, ..., i<m>]}, then the \spad{(k, l)}th
96       ++ entry of \spad{elt(x, rowList, col)} is \spad{x(i<k>, col)}.
97    elt : (%, LI, LI) -> %
98       ++ \spad{elt(x, rowList, colList)} returns an m-by-n array consisting
99       ++ of elements of x, where \spad{m = # rowList} and \spad{n = # colList}.
100       ++ If \spad{rowList = [i<1>, i<2>, ..., i<m>]} and \spad{colList =
101       ++ [j<1>, j<2>, ..., j<n>]}, then the \spad{(k, l)}th entry of
102       ++ \spad{elt(x, rowList, colList)} is \spad{x(i<k>, j<l>)}.
103    elt : (%, SI, SI) -> %
104       ++ \spad{elt(x, s1, s2)} is equivalent to
105       ++ \spad{elt(x, expand(s1), expand(s2))} but should be more
106       ++ convenient and more efficient.
107    elt : (%, LI, SI) -> %
108       ++ \spad{elt(x, rowList, s)} is equivalent to
109       ++ \spad{elt(x, rowList, expand(s))} but should be more
110       ++ convenient and more efficient.
111    elt : (%, SI, LI) -> %
112       ++ \spad{elt(x, s, colList)} is equivalent to
113       ++ \spad{elt(x, expand(s), colList)} but should be more
114       ++ convenient and more efficient.
115    elt : (%, Integer, LSI) -> %
116       ++ \spad{elt(x, row, ls2)} is equivalent to \spad{elt(x, row, l2)}
117       ++ where l2 is obtained appending expansions of elements of ls2,
118       ++ but should be more convenient and more efficient.
119    elt : (%, LSI, Integer) -> %
120       ++ \spad{elt(x, ls1, col)} is equivalent to \spad{elt(x, l1, col)}
121       ++ where l1 is obtained appending expansions of elements of ls1,
122       ++ but should be more convenient and more efficient.
123    setelt! : (%, Integer, LSI, %) -> %
124       ++ \spad{setelt!(x, row, ls2)} is equivalent to
125       ++ \spad{setelt!(x, row, l2)} where l2 is obtained appending
126       ++ expansions of elements of ls2, but should be more convenient
127       ++ and more efficient.
128    setelt! : (%, LSI, Integer, %) -> %
129       ++ \spad{setelt!(x, ls1, col)} is equivalent to
130       ++ \spad{setelt!(x, l1, col)} where l1 is obtained appending
131       ++ expansions of elements of ls1, but should be more convenient
132       ++ and more efficient.
133    -- Works by coercing single integers to segments of integers
134    -- elt : (%, LI, LSI) -> %
135    -- elt : (%, LSI, LI) -> %
136    elt : (%, SI, LSI) -> %
137       ++ \spad{elt(x, s1, ls2)} is equivalent to \spad{elt(x, l1, l2)}
138       ++ where li is obtained appending expansions of elements of lsi,
139       ++ but should be more convenient and more efficient.
140    elt : (%, LSI, SI) -> %
141       ++ \spad{elt(x, ls1, s2)} is equivalent to \spad{elt(x, l1, l2)}
142       ++ where li is obtained appending expansions of elements of lsi,
143       ++ but should be more convenient and more efficient.
144    elt : (%, LSI, LSI) -> %
145       ++ \spad{elt(x, ls1, ls2)} is equivalent to \spad{elt(x, l1, l2)}
146       ++ where li is obtained appending expansions of elements of lsi,
147       ++ but should be more convenient and more efficient.
148    rowSlice : % -> Segment(Integer)
149       ++ \spad{rowSlice(m)} returns a segment s such that for
150       ++ m the access m(s, j) gives the j-th column.
151    colSlice : % -> Segment(Integer)
152       ++ \spad{colSlice(m)} returns a segment s such that for
153       ++ m the access m(i, s) gives the i-th row.
154
155--% Part assignments
156
157    setelt! : (%, Integer, Integer, R) -> R
158      ++ setelt!(m, i, j, r) sets the element in the ith row and jth
159      ++ column of m to r
160      ++ error check to determine if indices are in proper ranges
161    qsetelt! : (%, Integer, Integer, R) -> R
162      ++ qsetelt!(m, i, j, r) sets the element in the ith row and jth
163      ++ column of m to r
164      ++ NO error check to determine if indices are in proper ranges
165    setRow! : (%, Integer, Row) -> %
166      ++ setRow!(m, i, v) sets to ith row of m to v
167    setColumn! : (%, Integer, Col) -> %
168      ++ setColumn!(m, j, v) sets to jth column of m to v
169    setelt! : (%, Integer, LI, %) -> %
170       ++ \spad{setelt!(x, row, colList)} assigns to an 1-by-n selection
171       ++ of the array, where \spad{n = # colList}.
172    setelt! : (%, LI, Integer, %) -> %
173       ++ \spad{setelt!(x, rowList, col)} assigns to an m-by-1 selection
174       ++ of the array, where \spad{m = # rowList}.
175    setelt! : (%, List Integer, List Integer, %) -> %
176       ++ \spad{setelt!(x, rowList, colList, y)} destructively alters
177       ++ the array x.  If y is \spad{m}-by-\spad{n},
178       ++ \spad{rowList = [i<1>, i<2>, ..., i<m>]}
179       ++ and \spad{colList = [j<1>, j<2>, ..., j<n>]}, then
180       ++ \spad{x(i<k>, j<l>)}
181       ++ is set to \spad{y(k, l)} for \spad{k = 1, ..., m} and
182       ++ \spad{l = 1, ..., n}.
183    setelt! : (%, SI, SI, %) -> %
184       ++ \spad{setelt!(x, s1, s2)} is equivalent to
185       ++ \spad{setelt!(x, expand(s1), expand(s2))} but should be more
186       ++ convenient and more efficient.
187    setelt! : (%, LI, SI, %) -> %
188       ++ \spad{setelt!(x, l1, s2)} is equivalent to
189       ++ \spad{setelt!(x, l1, expand(s2))} but should be more
190       ++ convenient and more  efficient.
191    setelt! : (%, SI, LI, %) -> %
192       ++ \spad{setelt!(x, s1, l2)} is equivalent to
193       ++ \spad{setelt!(x, expand(s1), l2)} but should be more
194       ++ convenient and more  efficient.
195    -- Works by coercing single integers to segments of integers
196    -- setelt! : (%, LI, LSI, %) -> %
197    -- setelt! : (%, LSI, LI, %) -> %
198    setelt! : (%, SI, LSI, %) -> %
199       ++ \spad{setelt!(x, s1, ls2)} is equivalent to \spad{setelt!(x, l1, l2)}
200       ++ where li is obtained appending expansions of elements of lsi,
201       ++ but should be more convenient and more efficient.
202    setelt! : (%, LSI, SI, %) -> %
203       ++ \spad{setelt!(x, ls1, s2)} is equivalent to \spad{setelt!(x, l1, l2)}
204       ++ where li is obtained appending expansions of elements of lsi,
205       ++ but should be more convenient and more efficient.
206    setelt! : (%, LSI, LSI, %) -> %
207       ++ \spad{setelt!(x, ls1, ls1)} is equivalent to
208       ++ \spad{setelt!(x, l1, l2)} where li is obtained appending
209       ++ expansions of elements of lsi, but should be more convenient
210       ++ and more efficient.
211    setsubMatrix! : (%, Integer, Integer, %) -> %
212       ++ \spad{setsubMatrix(x, i1, j1, y)} destructively alters the
213       ++ array x. Here \spad{x(i, j)} is set to \spad{y(i-i1+1, j-j1+1)} for
214       ++ \spad{i = i1, ..., i1-1+nrows y} and \spad{j = j1, ..., j1-1+ncols y}.
215
216    -- manipulations
217
218    swapRows! : (%, Integer, Integer) -> %
219       ++ \spad{swapRows!(m, i, j)} interchanges the \spad{i}th and \spad{j}th
220       ++ rows of m. This destructively alters the array.
221    swapColumns! : (%, Integer, Integer) -> %
222       ++ \spad{swapColumns!(m, i, j)} interchanges the \spad{i}th and
223       ++ \spad{j}th columns of m. This destructively alters the array.
224    transpose : % -> %
225       ++ \spad{transpose(m)} returns the transpose of the array m.
226    squareTop : % -> %
227       ++ \spad{squareTop(m)} returns an n-by-n array consisting of the first
228       ++ n rows of the m-by-n array m. Error: if
229       ++ \spad{m < n}.
230    horizConcat : (%, %) -> %
231       ++ \spad{horizConcat(x, y)} horizontally concatenates two arrays with
232       ++ an equal number of rows. The entries of y appear to the right
233       ++ of the entries of x.  Error: if the arrays
234       ++ do not have the same number of rows.
235    horizConcat : (List %) -> %
236      ++ \spad{horizConcat(l)} horizontally concatenates all members of l
237      ++ Error: if the arrays  do not have the same number of rows.
238    vertConcat : (%, %) -> %
239       ++ \spad{vertConcat(x, y)} vertically concatenates two arrays with an
240       ++ equal number of columns. The entries of y appear below
241       ++ of the entries of x.  Error: if the arrays
242       ++ do not have the same number of columns.
243    vertConcat : (List %) -> %
244      ++ \spad{vertConcat(l)} vertically concatenates all members of l
245      ++ Error: if the arrays do not have the same number of columns.
246    blockConcat : (List List %) -> %
247      ++ \spad{blockConcat(ll)} concatenates arrays row and
248      ++ column wise, building a array from blocks. The order
249      ++ is row major as in \spad{matrix}.
250
251    vertSplit : (%, PI) -> List %
252      ++ \spad{vertSplit(a, n)} splits a into n arrays
253      ++ of equal size row wise.
254      ++ Error: if number of rows of a is not divisible by n.
255    vertSplit : (%, LNNI) -> List %
256      ++ \spad{vertSplit(a, [n1, ..., ni])} splits a into
257      ++ arrays having n1, ..., ni rows.
258      ++ Error: if number of rows of a is different than
259      ++ n1+ ... + ni.
260    horizSplit : (%, PI) -> List %
261      ++ \spad{horizSplit(a, n)} splits a into n arrays
262      ++ of equal size column wise.
263      ++ Error: if number of columns of a is not divisible by n.
264    horizSplit : (%, LNNI) -> List %
265      ++ \spad{horizSplit(a, [n1, n2, ..., ni])} splits a into
266      ++ arrays having n1, ..., ni columns.
267      ++ Error: if number of columns of a is different than
268      ++ n1 + ... + ni.
269    blockSplit : (%, PI, PI) -> List List %
270      ++ \spad{blockSplit(a, n, m)} splits a into n*m
271      ++ subarrays of equal size row and column wise, dividing
272      ++ a into blocks.
273      ++ Error: if number of rows of a is not divisible by n
274      ++ or number of columns of a is not divisible by m.
275    blockSplit : (%, LNNI, LNNI) -> List List %
276      ++ \spad{blockSplit(a, [n1,...,ni], [m1,...,mi])} splits a
277      ++ into multiple subarraus row and column wise, such that
278      ++ element at position k, l has nk rows and ml columns.
279      ++ Error: if number of rows of a is different than
280      ++ n1 + ... + ni or  number of columns of a is different
281      ++ than m1 + ... + mj
282
283
284    -- Map and Zip
285
286    map : (R -> R, %) -> %
287      ++ map(f, a) returns \spad{b}, where \spad{b(i, j) = f(a(i, j))} for all \spad{i, j}
288    map! : (R -> R, %) -> %
289      ++ map!(f, a)  assign \spad{a(i, j)} to \spad{f(a(i, j))} for all \spad{i, j}
290    map : ((R, R) -> R, %, %) -> %
291      ++ map(f, a, b) returns \spad{c}, where \spad{c(i, j) = f(a(i, j), b(i, j))}
292      ++ for all \spad{i, j}
293    map : ((R, R) -> R, %, %, R) -> %
294      ++ map(f, a, b, r) returns \spad{c}, where \spad{c(i, j) = f(a(i, j), b(i, j))} when both
295      ++ \spad{a(i, j)} and \spad{b(i, j)} exist;
296      ++ else \spad{c(i, j) = f(r, b(i, j))} when \spad{a(i, j)} does not exist;
297      ++ else \spad{c(i, j) = f(a(i, j), r)} when \spad{b(i, j)} does not exist;
298      ++ otherwise \spad{c(i, j) = f(r, r)}.
299
300   add
301
302    minr ==> minRowIndex
303    maxr ==> maxRowIndex
304    minc ==> minColIndex
305    maxc ==> maxColIndex
306    mini ==> minIndex
307    maxi ==> maxIndex
308
309
310--% Predicates
311
312    import from Integer
313
314    any?(f, m) ==
315      for i in minRowIndex(m)..maxRowIndex(m) repeat
316        for j in minColIndex(m)..maxColIndex(m) repeat
317          f(qelt(m, i, j)) => return true
318      false
319
320    every?(f, m) ==
321      for i in minRowIndex(m)..maxRowIndex(m) repeat
322        for j in minColIndex(m)..maxColIndex(m) repeat
323          not f(qelt(m, i, j)) => return false
324      true
325
326    size?(m, n) == nrows(m) * ncols(m) = n
327    less?(m, n) == nrows(m) * ncols(m) < n
328    more?(m, n) == nrows(m) * ncols(m) > n
329
330    if R has Comparable then
331
332      smaller?(m1, m2) ==
333          mri1 := minRowIndex(m1)
334          mri2 := minRowIndex(m2)
335          mri1 < mri2 => true
336          mri2 < mri1 => false
337          minr := mri1
338          mri1 := maxRowIndex(m1)
339          mri2 := maxRowIndex(m2)
340          mri1 < mri2 => true
341          mri2 < mri1 => false
342          maxr := mri1
343          mci1 := minColIndex(m1)
344          mci2 := minColIndex(m2)
345          mci1 < mci2 => true
346          mci2 < mci1 => false
347          minc := mci1
348          mci1 := maxColIndex(m1)
349          mci2 := maxColIndex(m2)
350          mci1 < mci2 => true
351          mci2 < mci1 => false
352          maxc := mci1
353          for i in minr..maxr repeat
354              for j in minc..maxc repeat
355                  el1 := m1(i, j)
356                  el2 := m2(i, j)
357                  smaller?(el1, el2) => return true
358                  if not(el1 = el2) then return false
359          false
360
361--% Size inquiries
362
363    # m == nrows(m) * ncols(m)
364
365--% Part extractions
366
367    elt(m, i, j, r) ==
368      i < minRowIndex(m) or i > maxRowIndex(m) => r
369      j < minColIndex(m) or j > maxColIndex(m) => r
370      qelt(m, i, j)
371
372    count(f : R -> Boolean, m : %) ==
373      num : NonNegativeInteger := 0
374      for i in minRowIndex(m)..maxRowIndex(m) repeat
375        for j in minColIndex(m)..maxColIndex(m) repeat
376          if f(qelt(m, i, j)) then num := num + 1
377      num
378
379    parts m ==
380      entryList : List R := []
381      for i in maxRowIndex(m)..minRowIndex(m) by -1 repeat
382        for j in maxColIndex(m)..minColIndex(m) by -1 repeat
383          entryList := concat(qelt(m, i, j), entryList)
384      entryList
385
386    listOfLists x ==
387        ll : List List R := []
388        for i in maxr(x)..minr(x) by -1 repeat
389            l : List R := []
390            for j in maxc(x)..minc(x) by -1 repeat
391                l := cons(qelt(x, i, j), l)
392            ll := cons(l, ll)
393        ll
394
395    subMatrix(x, i1, i2, j1, j2) ==
396        (i2 + 1 < i1) => error "subMatrix: bad row indices"
397        (j2 + 1 < j1) => error "subMatrix: bad column indices"
398        rows := qcoerce(i2 - i1 + 1)@NonNegativeInteger
399        cols := qcoerce(j2 - j1 + 1)@NonNegativeInteger
400        y := qnew(rows, cols)
401        rows = 0 or cols = 0 => y
402        (i1 < minr(x)) or (i2 > maxr(x)) =>
403            error "subMatrix: index out of range"
404        (j1 < minc(x)) or (j2 > maxc(x)) =>
405            error "subMatrix: index out of range"
406        for i in minr(y)..maxr(y) for k in i1..i2 repeat
407            for j in minc(y)..maxc(y) for l in j1..j2 repeat
408                qsetelt!(y, i, j, qelt(x, k, l))
409        y
410
411    elt(x : %, row : Integer, colList : LI) ==
412        (row < minr(x)) or (row > maxr(x)) =>
413            error "elt: index out of range"
414        for ej in colList repeat
415            (ej < minc(x)) or (ej > maxc(x)) =>
416                error "elt: index out of range"
417        y := qnew(1, # colList)
418        for ej in colList for j in minc(y)..maxc(y) repeat
419            qsetelt!(y, 1, j, qelt(x, row, ej))
420        y
421
422    elt(x : %, rowList : LI, col : Integer) ==
423        for ei in rowList repeat
424            (ei < minr(x)) or (ei > maxr(x)) =>
425                error "elt: index out of range"
426        (col < minc(x)) or (col > maxc(x)) =>
427            error "elt: index out of range"
428        y := qnew(# rowList, 1)
429        for ei in rowList for i in minr(y)..maxr(y) repeat
430            qsetelt!(y, i, 1, qelt(x, ei, col))
431        y
432
433    elt(x : %, rowList : List Integer, colList : List Integer) ==
434        for ei in rowList repeat
435            (ei < minr(x)) or (ei > maxr(x)) =>
436                error "elt: index out of range"
437        for ej in colList repeat
438            (ej < minc(x)) or (ej > maxc(x)) =>
439                error "elt: index out of range"
440        y := qnew(# rowList, # colList)
441        for ei in rowList for i in minr(y)..maxr(y) repeat
442            for ej in colList for j in minc(y)..maxc(y) repeat
443                qsetelt!(y, i, j, qelt(x, ei, ej))
444        y
445
446    check_seg(s : SI, lb : Integer, ub : Integer) : NonNegativeInteger ==
447        ii := incr(s)
448        i1 := low(s)
449        i2 := high(s)
450        -- Empty segment:
451        (ii > 0 and i2 + 1 < i1) or (ii < 0 and i1 + 1 < i2) =>
452            error "check_seg: bad indices"
453        (i1 > i2 and ii > 0) or (i2 > i1 and ii < 0) => 0
454        -- Regular segment:
455        0 < ii  =>
456            (i2 + 1 < i1) => error "check_seg: index out of range"
457            cc := qcoerce(i2 - i1 + ii)@NonNegativeInteger
458            cc < ii => cc
459            i1 < lb or ub < i2 =>
460                error "check_seg: index out of range"
461            ii = 1 => cc
462            qcoerce(cc quo ii)@NonNegativeInteger
463        ii < 0 =>
464            ii := -ii
465            (i1 + 1 < i2) or i2 < lb or ub < i1 =>
466                error "check_seg: index out of range"
467            cc := qcoerce(i1 - i2 + ii)@NonNegativeInteger
468            cc <  ii => cc
469            i2 < lb or ub < i1 =>
470                error "check_seg: index out of range"
471            ii = 1 => cc
472            qcoerce(cc quo ii)@NonNegativeInteger
473        error "chec_seg: zero increment"
474
475    elt(x : %, rowList : LI, sc : SI) : % ==
476        lc := low(sc)
477        uc := high(sc)
478        ic := incr(sc)
479        nr := # rowList
480        nc := check_seg(sc, minc(x), maxc(x))
481        y := qnew(nr, nc)
482        nr = 0 or nc = 0 => y
483        for i in minr(y)..maxr(y) for k in rowList repeat
484            for j in minc(y)..maxc(y) for l in lc..uc by ic repeat
485                qsetelt!(y, i, j, qelt(x, k, l))
486        y
487
488    elt(x : %, sr : SI, colList : LI) : % ==
489        lr := low(sr)
490        ur := high(sr)
491        ir := incr(sr)
492        nr := check_seg(sr, minr(x), maxr(x))
493        nc := # colList
494        y := qnew(nr, nc)
495        nr = 0 or nc = 0 => y
496        for i in minr(y)..maxr(y) for k in lr..ur by ir repeat
497            for j in minc(y)..maxc(y) for l in colList repeat
498                qsetelt!(y, i, j, qelt(x, k, l))
499        y
500
501    elt(x : %, sr : SI, sc : SI) : % ==
502        lr := low(sr)
503        ur := high(sr)
504        lc := low(sc)
505        uc := high(sc)
506        ir := incr(sr)
507        ic := incr(sc)
508        ir = 1 and ic = 1 => subMatrix(x, lr, ur, lc, uc)
509        nr := check_seg(sr, minr(x), maxr(x))
510        nc := check_seg(sc, minc(x), maxc(x))
511        y := qnew(nr, nc)
512        nr = 0 or nc = 0 => y
513        for i in minr(y)..maxr(y) for k in lr..ur by ir repeat
514            for j in minc(y)..maxc(y) for l in lc..uc by ic repeat
515                qsetelt!(y, i, j, qelt(x, k, l))
516        y
517
518    check_segs(ls : LSI, lb : Integer, ub : Integer) : NonNegativeInteger ==
519        res : NonNegativeInteger := 0
520        for s in ls repeat
521            res := res + check_seg(s, lb, ub)
522        res
523
524    elt(x : %, row : Integer, lsc : LSI) : % ==
525        nc := check_segs(lsc, minc(x), maxc(x))
526        y := qnew(1, nc)
527        nc = 0 => y
528        j := minc(y)
529        for sc in lsc repeat
530            for l in low(sc)..high(sc) by incr(sc) repeat
531                qsetelt!(y, 1, j, qelt(x, row, l))
532                j := j + 1
533        y
534
535    elt(x : %, lsr : LSI, col : Integer) : % ==
536        nr := check_segs(lsr, minr(x), maxr(x))
537        y := qnew(nr, 1)
538        nr = 0 => y
539        i := minr(y)
540        for sr in lsr repeat
541            for k in low(sr)..high(sr) by incr(sr) repeat
542                qsetelt!(y, i, 1, qelt(x, k, col))
543                i := i + 1
544        y
545
546    elt(x : %, sr : SI, lsc : LSI) : % ==
547        lr := low(sr)
548        ur := high(sr)
549        ir := incr(sr)
550        nr := check_seg(sr, minr(x), maxr(x))
551        nc := check_segs(lsc, minc(x), maxc(x))
552        y := qnew(nr, nc)
553        nr = 0 or nc = 0 => y
554        j := minc(y)
555        for sc in lsc repeat
556            for l in low(sc)..high(sc) by incr(sc) repeat
557                for i in minr(y)..maxr(y) for k in lr..ur by ir repeat
558                    qsetelt!(y, i, j, qelt(x, k, l))
559                j := j + 1
560        y
561
562    elt(x : %, lsr : LSI, sc : SI) : % ==
563        lc := low(sc)
564        uc := high(sc)
565        ic := incr(sc)
566        nr := check_segs(lsr, minr(x), maxr(x))
567        nc := check_seg(sc, minc(x), maxc(x))
568        y := qnew(nr, nc)
569        nr = 0 or nc = 0 => y
570        i := minr(y)
571        for sr in lsr repeat
572            for k in low(sr)..high(sr) by incr(sr) repeat
573                for j in minc(y)..maxc(y) for l in lc..uc by ic repeat
574                    qsetelt!(y, i, j, qelt(x, k, l))
575                i := i + 1
576        y
577
578    elt(x : %, lsr : LSI, lsc : LSI) : % ==
579        nr := check_segs(lsr, minr(x), maxr(x))
580        nc := check_segs(lsc, minc(x), maxc(x))
581        y := qnew(nr, nc)
582        nr = 0 or nc = 0 => y
583        i := minr(y)
584        for sr in lsr repeat
585            lr := low(sr)
586            ur := high(sr)
587            ir := incr(sr)
588            for k in lr..ur by ir repeat
589                j := minc(y)
590                for sc in lsc repeat
591                    for l in low(sc)..high(sc) by incr(sc) repeat
592                        qsetelt!(y, i, j, qelt(x, k, l))
593                        j := j + 1
594                i := i + 1
595        y
596
597    rowSlice(x :%) : Segment(Integer) ==
598        minr(x)..maxr(x)
599
600    colSlice(x :%) : Segment(Integer) ==
601        minc(x)..maxc(x)
602
603    -- Setting parts
604
605    setelt!(x : %, row : Integer, colList : LI, y : %) ==
606        (row < minr(x)) or (row > maxr(x)) =>
607            error "setelt!: index out of range"
608        for ej in colList repeat
609            (ej < minc(x)) or (ej > maxc(x)) =>
610                error "setelt!: index out of range"
611        ((nrows y) ~= 1) or ((# colList) ~= (ncols y)) =>
612            error "setelt!: matrix has bad dimensions"
613        rowiy := minr(y)
614        for ej in colList for j in minc(y)..maxc(y) repeat
615            qsetelt!(x, row, ej, qelt(y, rowiy, j))
616        y
617
618    setelt!(x : %, rowList : LI, col : Integer, y : %) ==
619        for ei in rowList repeat
620            (ei < minr(x)) or (ei > maxr(x)) =>
621                error "setelt!: index out of range"
622        (col < minc(x)) or (col > maxc(x)) =>
623            error "setelt!: index out of range"
624        ((# rowList) ~= (nrows y)) or ((ncols y) ~= 1) =>
625            error "setelt!: matrix has bad dimensions"
626        coliy := minc(y)
627        for ei in rowList for i in minr(y)..maxr(y) repeat
628            qsetelt!(x, ei, col, qelt(y, i, coliy))
629        y
630
631    setelt!(x : %, rowList : List Integer, colList : List Integer, y : %) ==
632        for ei in rowList repeat
633            (ei < minr(x)) or (ei > maxr(x)) =>
634                error "setelt!: index out of range"
635        for ej in colList repeat
636            (ej < minc(x)) or (ej > maxc(x)) =>
637                error "setelt!: index out of range"
638        ((# rowList) ~= (nrows y)) or ((# colList) ~= (ncols y)) =>
639            error "setelt!: matrix has bad dimensions"
640        for ei in rowList for i in minr(y)..maxr(y) repeat
641            for ej in colList for j in minc(y)..maxc(y) repeat
642                qsetelt!(x, ei, ej, qelt(y, i, j))
643        y
644
645    setelt!(x : %, sr : SI, sc : SI, y : %) ==
646        lr := low(sr)
647        ur := high(sr)
648        lc := low(sc)
649        uc := high(sc)
650        ir := incr(sr)
651        ic := incr(sc)
652        -- ir = 1 and ic = 1 => subMatrix(x, lr, ur, lc, uc)
653        nr := check_seg(sr, minr(x), maxr(x))
654        nc := check_seg(sc, minc(x), maxc(x))
655        nrows(y) ~= nr or ncols(y) ~= nc =>
656            error "setelt!: matrix has bad dimensions"
657        nr = 0 or nc = 0 => y
658        for i in minr(y)..maxr(y) for k in lr..ur by ir repeat
659            for j in minc(y)..maxc(y) for l in lc..uc by ic repeat
660                qsetelt!(x, k, l, qelt(y, i, j))
661        y
662
663    setelt!(x : %, rowList : LI, sc : SI, y : %) ==
664        lc := low(sc)
665        uc := high(sc)
666        ic := incr(sc)
667        nr := # rowList
668        nc := check_seg(sc, minc(x), maxc(x))
669        nrows(y) ~= nr or ncols(y) ~= nc =>
670            error "setelt!: matrix has bad dimensions"
671        nr = 0 or nc = 0 => y
672        for i in minr(y)..maxr(y) for k in rowList repeat
673            for j in minc(y)..maxc(y) for l in lc..uc by ic repeat
674                qsetelt!(x, k, l, qelt(y, i, j))
675        y
676
677    setelt!(x : %, sr : SI, colList : LI, y : %) ==
678        lr := low(sr)
679        ur := high(sr)
680        ir := incr(sr)
681        nr := check_seg(sr, minr(x), maxr(x))
682        nc := # colList
683        nrows(y) ~= nr or ncols(y) ~= nc =>
684            error "setelt!: matrix has bad dimensions"
685        nr = 0 or nc = 0 => y
686        for i in minr(y)..maxr(y) for k in lr..ur by ir repeat
687            for j in minc(y)..maxc(y) for l in colList repeat
688                qsetelt!(x, k, l, qelt(y, i, j))
689        y
690
691    setelt!(x : %, row : Integer, lsc : LSI, y : %) ==
692        nc := check_segs(lsc, minc(x), maxc(x))
693        nrows(y) ~= 1 or ncols(y) ~= nc =>
694            error "setelt!: matrix has bad dimensions"
695        nc = 0 => y
696        i := minr(y)
697        j := minc(y)
698        for sc in lsc repeat
699            for l in low(sc)..high(sc) by incr(sc) repeat
700                qsetelt!(x, row, l, qelt(y, i, j))
701                j := j + 1
702        y
703
704    setelt!(x : %, lsr : LSI, col : Integer, y : %) ==
705        nr := check_segs(lsr, minr(x), maxr(x))
706        nrows(y) ~= nr or ncols(y) ~= 1 =>
707            error "setelt!: matrix has bad dimensions"
708        nr = 0 => y
709        i := minr(y)
710        j := minc(y)
711        for sr in lsr repeat
712            for k in low(sr)..high(sr) by incr(sr) repeat
713                qsetelt!(x, k, col, qelt(y, i, j))
714                i := i + 1
715        y
716
717    setelt!(x : %, sr : SI, lsc : LSI, y : %) ==
718        lr := low(sr)
719        ur := high(sr)
720        ir := incr(sr)
721        nr := check_seg(sr, minr(x), maxr(x))
722        nc := check_segs(lsc, minc(x), maxc(x))
723        nrows(y) ~= nr or ncols(y) ~= nc =>
724            error "setelt!: matrix has bad dimensions"
725        nr = 0 or nc = 0 => y
726        j := minc(y)
727        for sc in lsc repeat
728            for l in low(sc)..high(sc) by incr(sc) repeat
729                for i in minr(y)..maxr(y) for k in lr..ur by ir repeat
730                    qsetelt!(x, k, l, qelt(y, i, j))
731                j := j + 1
732        y
733
734    setelt!(x : %, lsr : LSI, sc : SI, y : %) ==
735        lc := low(sc)
736        uc := high(sc)
737        ic := incr(sc)
738        nr := check_segs(lsr, minr(x), maxr(x))
739        nc := check_seg(sc, minc(x), maxc(x))
740        nrows(y) ~= nr or ncols(y) ~= nc =>
741            error "setelt!: matrix has bad dimensions"
742        nr = 0 or nc = 0 => y
743        i := minr(y)
744        for sr in lsr repeat
745            for k in low(sr)..high(sr) by incr(sr) repeat
746                for j in minc(y)..maxc(y) for l in lc..uc by ic repeat
747                    qsetelt!(x, k, l, qelt(y, i, j))
748                i := i + 1
749        y
750
751    setelt!(x : %, lsr : LSI, lsc : LSI, y : %) ==
752        nr := check_segs(lsr, minr(x), maxr(x))
753        nc := check_segs(lsc, minc(x), maxc(x))
754        nrows(y) ~= nr or ncols(y) ~= nc =>
755            error "setelt!: matrix has bad dimensions"
756        nr = 0 or nc = 0 => y
757        i := minr(y)
758        for sr in lsr repeat
759            lr := low(sr)
760            ur := high(sr)
761            ir := incr(sr)
762            for k in lr..ur by ir repeat
763                j := minc(y)
764                for sc in lsc repeat
765                    for l in low(sc)..high(sc) by incr(sc) repeat
766                        qsetelt!(x, k, l, qelt(y, i, j))
767                        j := j + 1
768                i := i + 1
769        y
770
771    setsubMatrix!(x, i1, j1, y) ==
772        i2 := i1 + nrows(y) - 1
773        j2 := j1 + ncols(y) - 1
774        (i1 < minr(x)) or (i2 > maxr(x)) =>
775            error "setsubMatrix!: inserted matrix too big, "
776                   "use subMatrix to restrict it"
777        (j1 < minc(x)) or (j2 > maxc(x)) =>
778            error "setsubMatrix!: inserted matrix too big, "
779                   "use subMatrix to restrict it"
780        for i in minr(y)..maxr(y) for k in i1..i2 repeat
781            for j in minc(y)..maxc(y) for l in j1..j2 repeat
782                qsetelt!(x, k, l, qelt(y, i, j))
783        x
784
785    -- Manipulations
786
787    swapRows!(x, i1, i2) ==
788        (i1 < minr(x)) or (i1 > maxr(x)) or (i2 < minr(x)) or _
789            (i2 > maxr(x)) => error "swapRows!: index out of range"
790        i1 = i2 => x
791        for j in minc(x)..maxc(x) repeat
792            r := qelt(x, i1, j)
793            qsetelt!(x, i1, j, qelt(x, i2, j))
794            qsetelt!(x, i2, j, r)
795        x
796
797    swapColumns!(x, j1, j2) ==
798        (j1 < minc(x)) or (j1 > maxc(x)) or (j2 < minc(x)) or _
799            (j2 > maxc(x)) => error "swapColumns!: index out of range"
800        j1 = j2 => x
801        for i in minr(x)..maxr(x) repeat
802            r := qelt(x, i, j1)
803            qsetelt!(x, i, j1, qelt(x, i, j2))
804            qsetelt!(x, i, j2, r)
805        x
806
807    transpose(x : %) ==
808        ans := qnew(ncols x, nrows x)
809        for i in minr(ans)..maxr(ans) repeat
810            for j in minc(ans)..maxc(ans) repeat
811                qsetelt!(ans, i, j, qelt(x, j, i))
812        ans
813
814    squareTop x ==
815        nrows x < (cols := ncols x) =>
816            error "squareTop: number of columns exceeds number of rows"
817        ans := qnew(cols, cols)
818        for i in minr(x)..(minr(x) + cols - 1) repeat
819            for j in minc(x)..maxc(x) repeat
820                qsetelt!(ans, i, j, qelt(x, i, j))
821        ans
822
823    horizConcat(x, y) == horizConcat([x, y])
824
825    horizConcat(la : List %) ==
826        empty?(la) =>
827            error "horizConcat: empty list"
828        a1 := first(la)
829        nr := nrows(a1)
830        nc := ncols(a1)
831        for a in rest(la) repeat
832            nr ~= nrows(a) =>
833                error "horizConcat: array must have same number of rows"
834            nc := nc + ncols(a)
835        ans := qnew(nr, nc)
836        for i in minr(a1)..maxr(a1) repeat
837            l := minc(ans)
838            for a in la repeat
839                for j in minc(a)..maxc(a) repeat
840                    qsetelt!(ans, i, l, qelt(a, i, j))
841                    l := l + 1
842        ans
843
844    vertConcat(x, y) == vertConcat([x, y])
845
846    vertConcat(la : List %) ==
847        empty?(la) =>
848            error "vertConcat: empty list"
849        a1 := first(la)
850        nr := nrows(a1)
851        nc := ncols(a1)
852        for a in rest(la) repeat
853            nc ~= ncols(a) =>
854                error "vertConcat: array must have same number of columns"
855            nr := nr + nrows(a)
856        ans := qnew(nr, nc)
857        l :=  minr(ans)
858        for a in la repeat
859            for i in minr(a)..maxr(a) repeat
860                for j in minc(a)..maxc(a) repeat
861                    qsetelt!(ans, l, j, qelt(a, i, j))
862                l := l + 1
863        ans
864
865    blockConcat(LLA: List List %) : % ==
866        vertConcat([horizConcat(LA) for LA in LLA])
867
868    vertSplit(A : %, r : PI) : List % ==
869      dr := nrows(A) exquo r
870      dr case "failed" => error "split does not result in an equal division"
871      mir := minr A
872      mic := minc A
873      mac := maxc A
874      [ subMatrix(A, mir+i*dr, mir+(i+1)*dr-1, mic, mac) for i in 0..(r-1) ]
875
876    vertSplit(A : %, lr : LNNI) : List % ==
877        reduce("+", lr) ~= nrows(A) =>
878            error "split does not result in proper partition"
879        l : List NNI := cons(1, scan(_+, lr, 1$NNI)$ListFunctions2(NNI, NNI))
880        mir := minr(A) -1   -- additional shift because l starts at 1
881        mic := minc A
882        mac := maxc A
883        [subMatrix(A, mir+l(i-1), mir+l(i)-1, mic, mac) for i in 2..#l]
884
885    horizSplit(A : %, c : PI) : List % ==
886      dc := ncols(A) exquo c
887      dc case "failed" => error "split does not result in an equal division"
888      mir := minr A
889      mar := maxr A
890      mic := minc A
891      [ subMatrix(A, mir, mar, mic+i*dc, mic+(i+1)*dc-1) for i in 0..(c-1) ]
892
893
894    horizSplit(A : %, lc : LNNI) : List % ==
895        reduce("+", lc) ~= ncols(A) =>
896            error "split does not result in proper partition"
897        l : List NNI := cons(1, scan(_+, lc, 1$NNI)$ListFunctions2(NNI, NNI))
898        mir := minr A
899        mar := maxr A
900        mic := minc(A) -1   -- additional shift because l starts at 1
901        [subMatrix(A, mir, mar, mic+l(i-1), mic+l(i)-1) for i in 2..#l]
902
903    blockSplit(A : %, nr : PI, nc : PI) : List List % ==
904      -- The map version does not work with OpenAxiom.
905      --map( (X:M):(List M) +-> horizSplit(X, nc), vertSplit(A, nr) )$ListFunctions2(M, List M)
906      [ horizSplit(X, nc) for X in vertSplit(A, nr) ]
907
908    blockSplit(A : %, lr : LNNI, lc : LNNI) : List List % ==
909      --map( (X:M):(List M) +-> horizSplit(X, lc), vertSplit(A, lr) )$ListFunctions2(M, List M)
910      [horizSplit(X, lc) for X in vertSplit(A, lr)]
911
912--% Creation
913
914    copy m ==
915      ans := qnew(nrows m, ncols m)
916      for i in minRowIndex(m)..maxRowIndex(m) repeat
917        for j in minColIndex(m)..maxColIndex(m) repeat
918          qsetelt!(ans, i, j, qelt(m, i, j))
919      ans
920
921    fill!(m, r) ==
922      for i in minRowIndex(m)..maxRowIndex(m) repeat
923        for j in minColIndex(m)..maxColIndex(m) repeat
924          qsetelt!(m, i, j, r)
925      m
926
927    map(f : R -> R, m : %) : % ==
928      ans := qnew(nrows m, ncols m)
929      for i in minRowIndex(m)..maxRowIndex(m) repeat
930        for j in minColIndex(m)..maxColIndex(m) repeat
931          qsetelt!(ans, i, j, f(qelt(m, i, j)))
932      ans
933
934    map!(f, m) ==
935      for i in minRowIndex(m)..maxRowIndex(m) repeat
936        for j in minColIndex(m)..maxColIndex(m) repeat
937          qsetelt!(m, i, j, f(qelt(m, i, j)))
938      m
939
940    map(f, m, n) ==
941      (nrows(m) ~= nrows(n)) or (ncols(m) ~= ncols(n)) =>
942        error "map: arguments must have same dimensions"
943      ans := qnew(nrows m, ncols m)
944      for i in minRowIndex(m)..maxRowIndex(m) repeat
945        for j in minColIndex(m)..maxColIndex(m) repeat
946          qsetelt!(ans, i, j, f(qelt(m, i, j), qelt(n, i, j)))
947      ans
948
949    map(f, m, n, r) ==
950      -- FIXME: what if minRowIndex differ?
951      maxRow := max(maxRowIndex m, maxRowIndex n)
952      maxCol := max(maxColIndex m, maxColIndex n)
953      ans := qnew(max(nrows m, nrows n), max(ncols m, ncols n))
954      for i in minRowIndex(m)..maxRow repeat
955        for j in minColIndex(m)..maxCol repeat
956          qsetelt!(ans, i, j, f(elt(m, i, j, r), elt(n, i, j, r)))
957      ans
958
959    setRow!(m, i, v) ==
960      i < minRowIndex(m) or i > maxRowIndex(m) =>
961        error "setRow!: index out of range"
962      for j in minColIndex(m)..maxColIndex(m) _
963        for k in minIndex(v)..maxIndex(v) repeat
964          qsetelt!(m, i, j, v.k)
965      m
966
967    setColumn!(m, j, v) ==
968      j < minColIndex(m) or j > maxColIndex(m) =>
969        error "setColumn!: index out of range"
970      for i in minRowIndex(m)..maxRowIndex(m) _
971        for k in minIndex(v)..maxIndex(v) repeat
972          qsetelt!(m, i, j, v.k)
973      m
974
975    if R has _= : (R, R) -> Boolean then
976
977      m = n ==
978        eq?(m, n) => true
979        (nrows(m) ~= nrows(n)) or (ncols(m) ~= ncols(n)) => false
980        for i in minRowIndex(m)..maxRowIndex(m) repeat
981          for j in minColIndex(m)..maxColIndex(m) repeat
982            not (qelt(m, i, j) = qelt(n, i, j)) => return false
983        true
984
985      member?(r, m) ==
986        for i in minRowIndex(m)..maxRowIndex(m) repeat
987          for j in minColIndex(m)..maxColIndex(m) repeat
988            qelt(m, i, j) = r => return true
989        false
990
991      count(r : R, m : %) == count(x +-> x = r, m)
992
993    if Row has shallowlyMutable and Row has LinearAggregate(R) then
994
995      row(m, i) ==
996        i < minRowIndex(m) or i > maxRowIndex(m) =>
997          error "row: index out of range"
998        (nc := ncols m) = 0 => empty()
999        mci := minColIndex(m)
1000        v : Row := new(nc, qelt(m, i, mci))
1001        for j in mci..maxColIndex(m) _
1002          for k in minIndex(v)..maxIndex(v) repeat
1003            qsetelt!(v, k, qelt(m, i, j))
1004        v
1005
1006    if Col has shallowlyMutable and Col has LinearAggregate(R) then
1007
1008      column(m, j) ==
1009        j < minColIndex(m) or j > maxColIndex(m) =>
1010          error "column: index out of range"
1011        (nr := nrows m) = 0 => empty()
1012        mri := minRowIndex(m)
1013        v : Col := new(nr, qelt(m, mri, j))
1014        for i in mri..maxRowIndex(m) _
1015          for k in minIndex(v)..maxIndex(v) repeat
1016            qsetelt!(v, k, qelt(m, i, j))
1017        v
1018
1019    if R has CoercibleTo(OutputForm) then
1020
1021      coerce(m : %) ==
1022        l : List List OutputForm
1023        l := [[qelt(m, i, j) :: OutputForm _
1024                  for j in minColIndex(m)..maxColIndex(m)] _
1025                  for i in minRowIndex(m)..maxRowIndex(m)]
1026        matrix l
1027
1028)abbrev domain IIARRAY2 InnerIndexedTwoDimensionalArray
1029InnerIndexedTwoDimensionalArray(R, mnRow, mnCol, Row, Col) : _
1030       Exports == Implementation where
1031  ++ This is an internal type which provides an implementation of
1032  ++ 2-dimensional arrays as PrimitiveArray's of PrimitiveArray's.
1033  R : Type
1034  mnRow, mnCol : Integer
1035  Row : FiniteLinearAggregate R
1036  Col : FiniteLinearAggregate R
1037
1038  Exports ==> TwoDimensionalArrayCategory(R, Row, Col)
1039
1040  Implementation ==> add
1041
1042    Qsize ==> MATRIX_SIZE$Lisp
1043    Qnew ==> MAKE_MATRIX$Lisp
1044    Qnew1 ==> MAKE_MATRIX1$Lisp
1045    Qnrows ==> ANROWS$Lisp
1046    Qncols ==> ANCOLS$Lisp
1047    Qelt2 ==> QAREF2O$Lisp
1048    Qsetelt2 ==> QSETAREF2O$Lisp
1049
1050
1051
1052--% Primitive array creation
1053
1054    empty() == Qnew(0, 0)
1055
1056    qnew(rows, cols) == Qnew(rows, cols)
1057
1058    new(rows, cols, a) == Qnew1(rows, cols, a)
1059
1060--% Size inquiries
1061
1062    minRowIndex m == mnRow
1063    minColIndex m == mnCol
1064    maxRowIndex m == nrows m + mnRow - 1
1065    maxColIndex m == ncols m + mnCol - 1
1066
1067    nrows m == Qnrows(m)
1068
1069    ncols m == Qncols(m)
1070
1071--% Part selection/assignment
1072
1073    qelt(m, i, j) == Qelt2(m, i, j, mnRow, mnCol)
1074
1075    elt(m : %, i : Integer, j : Integer) ==
1076      i < minRowIndex(m) or i > maxRowIndex(m) =>
1077        error "elt: index out of range"
1078      j < minColIndex(m) or j > maxColIndex(m) =>
1079        error "elt: index out of range"
1080      qelt(m, i, j)
1081
1082    qsetelt!(m, i, j, r) == Qsetelt2(m, i, j, r, mnRow, mnCol)
1083
1084    setelt!(m : %, i : Integer, j : Integer, r : R) ==
1085      i < minRowIndex(m) or i > maxRowIndex(m) =>
1086        error "setelt!: index out of range"
1087      j < minColIndex(m) or j > maxColIndex(m) =>
1088        error "setelt!: index out of range"
1089      qsetelt!(m, i, j, r)
1090
1091    if R has SetCategory then
1092        latex(m : %) : String ==
1093          s : String := "\left[ \begin{array}{"
1094          j : Integer
1095          for j in minColIndex(m)..maxColIndex(m) repeat
1096            s := concat(s,"c")$String
1097          s := concat(s,"} ")$String
1098          i : Integer
1099          for i in minRowIndex(m)..maxRowIndex(m) repeat
1100            for j in minColIndex(m)..maxColIndex(m) repeat
1101              s := concat(s, latex(qelt(m, i, j))$R)$String
1102              if j < maxColIndex(m) then s := concat(s, " & ")$String
1103            if i < maxRowIndex(m) then s := concat(s, " \\ ")$String
1104          concat(s, "\end{array} \right]")$String
1105        hashUpdate!(s : HashState, m : %) : HashState ==
1106          i : Integer
1107          j : Integer
1108          for i in minRowIndex(m)..maxRowIndex(m) repeat
1109            for j in minColIndex(m)..maxColIndex(m) repeat
1110              s := hashUpdate!(s, qelt(m, i, j))$R
1111          s
1112
1113)abbrev domain IARRAY2 IndexedTwoDimensionalArray
1114IndexedTwoDimensionalArray(R, mnRow, mnCol) : Exports == Implementation where
1115  ++ An IndexedTwoDimensionalArray is a 2-dimensional array where
1116  ++ the minimal row and column indices are parameters of the type.
1117  ++ Rows and columns are returned as IndexedOneDimensionalArray's with
1118  ++ minimal indices matching those of the IndexedTwoDimensionalArray.
1119  ++ The index of the 'first' row may be obtained by calling the
1120  ++ function 'minRowIndex'.  The index of the 'first' column may
1121  ++ be obtained by calling the function 'minColIndex'.  The index of
1122  ++ the first element of a 'Row' is the same as the index of the
1123  ++ first column in an array and vice versa.
1124  R : Type
1125  mnRow, mnCol : Integer
1126  Row ==> IndexedOneDimensionalArray(R, mnCol)
1127  Col ==> IndexedOneDimensionalArray(R, mnRow)
1128
1129  Exports ==> TwoDimensionalArrayCategory(R, Row, Col)
1130
1131  Implementation ==>
1132    InnerIndexedTwoDimensionalArray(R, mnRow, mnCol, Row, Col)
1133
1134)abbrev domain ARRAY2 TwoDimensionalArray
1135TwoDimensionalArray(R) : Exports == Implementation where
1136  ++ A TwoDimensionalArray is a two dimensional array with
1137  ++ 1-based indexing for both rows and columns.
1138  R : Type
1139  Row ==> OneDimensionalArray R
1140  Col ==> OneDimensionalArray R
1141
1142  Exports ==> TwoDimensionalArrayCategory(R, Row, Col)
1143
1144  Implementation ==>
1145     InnerIndexedTwoDimensionalArray(R, 1, 1, Row, Col) add
1146         Qelt2 ==> QAREF2O$Lisp
1147         Qsetelt2 ==> QSETAREF2O$Lisp
1148         -- qelt and qsetelt! are logically unnecessary, but good for
1149         -- performance
1150         qelt(m, i, j) == Qelt2(m, i, j, 1@Integer, 1@Integer)
1151         qsetelt!(m, i, j, r) == Qsetelt2(m, i, j, r, 1@Integer, 1@Integer)
1152
1153--Copyright (c) 1991-2002, The Numerical ALgorithms Group Ltd.
1154--All rights reserved.
1155--
1156--Redistribution and use in source and binary forms, with or without
1157--modification, are permitted provided that the following conditions are
1158--met:
1159--
1160--    - Redistributions of source code must retain the above copyright
1161--      notice, this list of conditions and the following disclaimer.
1162--
1163--    - Redistributions in binary form must reproduce the above copyright
1164--      notice, this list of conditions and the following disclaimer in
1165--      the documentation and/or other materials provided with the
1166--      distribution.
1167--
1168--    - Neither the name of The Numerical ALgorithms Group Ltd. nor the
1169--      names of its contributors may be used to endorse or promote products
1170--      derived from this software without specific prior written permission.
1171--
1172--THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
1173--IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
1174--TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
1175--PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
1176--OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
1177--EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
1178--PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
1179--PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
1180--LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
1181--NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
1182--SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1183