\documentclass{article} \usepackage{open-axiom} \begin{document} \title{\$SPAD/src/algebra array2.spad} \author{The Axiom Team} \maketitle \begin{abstract} \end{abstract} \eject \tableofcontents \eject \section{category ARR2CAT TwoDimensionalArrayCategory} <>= )abbrev category ARR2CAT TwoDimensionalArrayCategory ++ Two dimensional array categories and domains ++ Author: ++ Date Created: 27 October 1989 ++ Date Last Updated: 27 June 1990 ++ Keywords: array, data structure ++ Examples: ++ References: TwoDimensionalArrayCategory(R,Row,Col): Category == Definition where ++ TwoDimensionalArrayCategory is a general array category which ++ allows different representations and indexing schemes. ++ Rows and columns may be extracted with rows returned as objects ++ of type Row and columns returned as objects of type Col. ++ The index of the 'first' row may be obtained by calling the ++ function 'minRowIndex'. The index of the 'first' column may ++ be obtained by calling the function 'minColIndex'. The index of ++ the first element of a 'Row' is the same as the index of the ++ first column in an array and vice versa. R : Type Row : FiniteLinearAggregate R Col : FiniteLinearAggregate R Definition == HomogeneousAggregate(R) with shallowlyMutable ++ one may destructively alter arrays finiteAggregate ++ two-dimensional arrays are finite --% Array creation new: (NonNegativeInteger,NonNegativeInteger,R) -> % ++ new(m,n,r) is an m-by-n array all of whose entries are r fill!: (%,R) -> % ++ fill!(m,r) fills m with r's --% Size inquiries minRowIndex : % -> Integer ++ minRowIndex(m) returns the index of the 'first' row of the array m maxRowIndex : % -> Integer ++ maxRowIndex(m) returns the index of the 'last' row of the array m minColIndex : % -> Integer ++ minColIndex(m) returns the index of the 'first' column of the array m maxColIndex : % -> Integer ++ maxColIndex(m) returns the index of the 'last' column of the array m nrows : % -> NonNegativeInteger ++ nrows(m) returns the number of rows in the array m ncols : % -> NonNegativeInteger ++ ncols(m) returns the number of columns in the array m --% Part extractions elt: (%,Integer,Integer) -> R ++ elt(m,i,j) returns the element in the ith row and jth ++ column of the array m ++ error check to determine if indices are in proper ranges qelt: (%,Integer,Integer) -> R ++ qelt(m,i,j) returns the element in the ith row and jth ++ column of the array m ++ NO error check to determine if indices are in proper ranges elt: (%,Integer,Integer,R) -> R ++ elt(m,i,j,r) returns the element in the ith row and jth ++ column of the array m, if m has an ith row and a jth column, ++ and returns r otherwise row: (%,Integer) -> Row ++ row(m,i) returns the ith row of m ++ error check to determine if index is in proper ranges column: (%,Integer) -> Col ++ column(m,j) returns the jth column of m ++ error check to determine if index is in proper ranges parts: % -> List R ++ parts(m) returns a list of the elements of m in row major order --% Part assignments setelt: (%,Integer,Integer,R) -> R -- will become setelt! ++ setelt(m,i,j,r) sets the element in the ith row and jth ++ column of m to r ++ error check to determine if indices are in proper ranges qsetelt!: (%,Integer,Integer,R) -> R ++ qsetelt!(m,i,j,r) sets the element in the ith row and jth ++ column of m to r ++ NO error check to determine if indices are in proper ranges setRow!: (%,Integer,Row) -> % ++ setRow!(m,i,v) sets to ith row of m to v setColumn!: (%,Integer,Col) -> % ++ setColumn!(m,j,v) sets to jth column of m to v --% Map and Zip map: (R -> R,%) -> % ++ map(f,a) returns \spad{b}, where \spad{b(i,j) = f(a(i,j))} for all \spad{i, j} map!: (R -> R,%) -> % ++ map!(f,a) assign \spad{a(i,j)} to \spad{f(a(i,j))} for all \spad{i, j} map:((R,R) -> R,%,%) -> % ++ map(f,a,b) returns \spad{c}, where \spad{c(i,j) = f(a(i,j),b(i,j))} ++ for all \spad{i, j} map:((R,R) -> R,%,%,R) -> % ++ map(f,a,b,r) returns \spad{c}, where \spad{c(i,j) = f(a(i,j),b(i,j))} when both ++ \spad{a(i,j)} and \spad{b(i,j)} exist; ++ else \spad{c(i,j) = f(r, b(i,j))} when \spad{a(i,j)} does not exist; ++ else \spad{c(i,j) = f(a(i,j),r)} when \spad{b(i,j)} does not exist; ++ otherwise \spad{c(i,j) = f(r,r)}. add --% Predicates any?(f,m) == for i in minRowIndex(m)..maxRowIndex(m) repeat for j in minColIndex(m)..maxColIndex(m) repeat f(qelt(m,i,j)) => return true false every?(f,m) == for i in minRowIndex(m)..maxRowIndex(m) repeat for j in minColIndex(m)..maxColIndex(m) repeat not f(qelt(m,i,j)) => return false true --% Size inquiries # m == nrows(m) * ncols(m) --% Part extractions elt(m,i,j,r) == i < minRowIndex(m) or i > maxRowIndex(m) => r j < minColIndex(m) or j > maxColIndex(m) => r qelt(m,i,j) count(f:R -> Boolean,m:%) == num : NonNegativeInteger := 0 for i in minRowIndex(m)..maxRowIndex(m) repeat for j in minColIndex(m)..maxColIndex(m) repeat if f(qelt(m,i,j)) then num := num + 1 num parts m == entryList : List R := nil() for i in maxRowIndex(m)..minRowIndex(m) by -1 repeat for j in maxColIndex(m)..minColIndex(m) by -1 repeat entryList := concat(qelt(m,i,j),entryList) entryList --% Creation setRow!(m,i,v) == i < minRowIndex(m) or i > maxRowIndex(m) => error "setRow!: index out of range" for j in minColIndex(m)..maxColIndex(m) _ for k in minIndex(v)..maxIndex(v) repeat qsetelt!(m,i,j,v.k) m setColumn!(m,j,v) == j < minColIndex(m) or j > maxColIndex(m) => error "setColumn!: index out of range" for i in minRowIndex(m)..maxRowIndex(m) _ for k in minIndex(v)..maxIndex(v) repeat qsetelt!(m,i,j,v.k) m if R has _= : (R,R) -> Boolean then m = n == eq?(m,n) => true (nrows(m) ~= nrows(n)) or (ncols(m) ~= ncols(n)) => false for i in minRowIndex(m)..maxRowIndex(m) repeat for j in minColIndex(m)..maxColIndex(m) repeat not (qelt(m,i,j) = qelt(n,i,j)) => return false true member?(r,m) == for i in minRowIndex(m)..maxRowIndex(m) repeat for j in minColIndex(m)..maxColIndex(m) repeat qelt(m,i,j) = r => return true false count(r:R,m:%) == count(#1 = r,m) if R has CoercibleTo(OutputForm) then coerce(m:%) == l : List List OutputForm l := [[qelt(m,i,j) :: OutputForm _ for j in minColIndex(m)..maxColIndex(m)] _ for i in minRowIndex(m)..maxRowIndex(m)] matrix l @ \section{domain IARRAY2 InnerTwoDimensionalArray} <>= )abbrev domain IARRAY2 InnerTwoDimensionalArray InnerTwoDimensionalArray(R,Row,Col):_ Exports == Implementation where ++ This is an internal type which provides an implementation of ++ 2-dimensional arrays as PrimitiveArray's of PrimitiveArray's. R : Type Row : FiniteLinearAggregate R Col : FiniteLinearAggregate R Exports == TwoDimensionalArrayCategory(R,Row,Col) Implementation == PrimitiveArray PrimitiveArray R add --% Primitive array creation new(rows,cols,a) == rows = 0 => error "new: arrays with zero rows are not supported" arr : Rep := new(rows,empty()) for i in 0..rows-1 repeat arr.i := new(cols,a) per arr --% Size inquiries minRowIndex m == 1 minColIndex m == 1 maxRowIndex m == nrows m maxColIndex m == ncols m nrows m == # rep m ncols m == empty? m => 0 # rep(m).0 --% Part selection/assignment qelt(m,i,j) == qelt(qelt(rep m,i - minRowIndex m),j - minColIndex m) elt(m:%,i:Integer,j:Integer) == i < minRowIndex(m) or i > maxRowIndex(m) => error "elt: index out of range" j < minColIndex(m) or j > maxColIndex(m) => error "elt: index out of range" qelt(m,i,j) qsetelt!(m,i,j,r) == setelt(qelt(rep m,i - minRowIndex m),j - minColIndex m,r) setelt(m:%,i:Integer,j:Integer,r:R) == i < minRowIndex(m) or i > maxRowIndex(m) => error "setelt: index out of range" j < minColIndex(m) or j > maxColIndex(m) => error "setelt: index out of range" qsetelt!(m,i,j,r) if R has SetCategory then latex(m : %) : String == s : String := "\left[ \begin{array}{" for j in minColIndex(m)..maxColIndex(m) repeat s := concat(s,"c")$String s := concat(s,"} ")$String for i in minRowIndex(m)..maxRowIndex(m) repeat for j in minColIndex(m)..maxColIndex(m) repeat s := concat(s, latex(qelt(m,i,j))$R)$String if j < maxColIndex(m) then s := concat(s, " & ")$String if i < maxRowIndex(m) then s := concat(s, " \\ ")$String concat(s, "\end{array} \right]")$String row(m,i) == i < 1 or i > nrows m => error "row: index out of range" i := dec i [[rep(m).i.j for j in 0..ncols m - 1]]$Row column(m,j) == j < 1 or j > ncols m => error "column: index out of range" j := dec j [[rep(m).i.j for i in 0..nrows m - 1]]$Col copy m == t: Rep := new(nrows m,sample$PrimitiveArray(R)) for i in 0..maxIndex rep m repeat t.i := copy rep(m).i per t fill!(m,r) == for i in 0..maxIndex rep m repeat fill!(rep(m).i,r) m map(f,m) == t: Rep := new(nrows m,sample$PrimitiveArray(R)) for i in 0..maxIndex rep m repeat t.i := map(f,rep(m).i) per t map!(f,m) == for i in 0..maxIndex rep m repeat map!(f,rep(m).i) m map(f,m,n) == nrows(m) ~= nrows(n) or ncols(m) ~= ncols(n) => error "map: arguments must have same dimensions" t: Rep := new(nrows m,sample$PrimitiveArray(R)) for i in 0..maxIndex rep m repeat t.i := map(f,rep(m).i,rep(n).i) per t map(f,m,n,r) == nrows m = nrows n and ncols m = ncols n => map(f,m,n) nr := max(nrows m,nrows n) nc := max(ncols m,ncols n) t: Rep := new(nr,sample$PrimitiveArray(R)) for i in 1..nr repeat t.i := [[f(elt(m,i,j,r),elt(n,i,j,r)) for j in 1..nc]]$PrimitiveArray(R) per t @ \section{domain ARRAY2 TwoDimensionalArray} <>= )abbrev domain ARRAY2 TwoDimensionalArray TwoDimensionalArray(R):Exports == Implementation where ++ A TwoDimensionalArray is a two dimensional array with ++ 1-based indexing for both rows and columns. R : Type macro V == OneDimensionalArray R Exports == TwoDimensionalArrayCategory(R,V,V) Implementation == InnerTwoDimensionalArray(R,V,V) @ \section{License} <>= --Copyright (c) 1991-2002, The Numerical ALgorithms Group Ltd. --All rights reserved. --Copyright (C) 2007-2013, Gabriel Dos Reis. --All rights reversed. -- --Redistribution and use in source and binary forms, with or without --modification, are permitted provided that the following conditions are --met: -- -- - Redistributions of source code must retain the above copyright -- notice, this list of conditions and the following disclaimer. -- -- - Redistributions in binary form must reproduce the above copyright -- notice, this list of conditions and the following disclaimer in -- the documentation and/or other materials provided with the -- distribution. -- -- - Neither the name of The Numerical ALgorithms Group Ltd. nor the -- names of its contributors may be used to endorse or promote products -- derived from this software without specific prior written permission. -- --THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS --IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED --TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A --PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER --OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, --EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, --PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR --PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF --LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING --NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS --SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. @ <<*>>= <> <> <> <> @ \eject \begin{thebibliography}{99} \bibitem{1} nothing \end{thebibliography} \end{document}