Initial population.

1 files changed, 451 insertions, 0 deletions

diff --git a/src/algebra/array2.spad.pamphlet b/src/algebra/array2.spad.pamphlet
new file mode 100644
index 00000000..ef540c42
--- /dev/null
+++ b/src/algebra/array2.spad.pamphlet
@@ -0,0 +1,451 @@
+\documentclass{article}
+\usepackage{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}
+<<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?(m,n) == nrows(m) * ncols(m) = n
+    less?(m,n) == nrows(m) * ncols(m) < n
+    more?(m,n) == nrows(m) * ncols(m) > n
+
+--% 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
+
+    copy m ==
+      ans := new(nrows m,ncols m,NIL$Lisp)
+      for i in minRowIndex(m)..maxRowIndex(m) repeat
+        for j in minColIndex(m)..maxColIndex(m) repeat
+          qsetelt_!(ans,i,j,qelt(m,i,j))
+      ans
+
+    fill_!(m,r) ==
+      for i in minRowIndex(m)..maxRowIndex(m) repeat
+        for j in minColIndex(m)..maxColIndex(m) repeat
+          qsetelt_!(m,i,j,r)
+      m
+
+    map(f,m) ==
+      ans := new(nrows m,ncols m,NIL$Lisp)
+      for i in minRowIndex(m)..maxRowIndex(m) repeat
+        for j in minColIndex(m)..maxColIndex(m) repeat
+          qsetelt_!(ans,i,j,f(qelt(m,i,j)))
+      ans
+
+    map_!(f,m) ==
+      for i in minRowIndex(m)..maxRowIndex(m) repeat
+        for j in minColIndex(m)..maxColIndex(m) repeat
+          qsetelt_!(m,i,j,f(qelt(m,i,j)))
+      m
+
+    map(f,m,n) ==
+      (nrows(m) ^= nrows(n)) or (ncols(m) ^= ncols(n)) =>
+        error "map: arguments must have same dimensions"
+      ans := new(nrows m,ncols m,NIL$Lisp)
+      for i in minRowIndex(m)..maxRowIndex(m) repeat
+        for j in minColIndex(m)..maxColIndex(m) repeat
+          qsetelt_!(ans,i,j,f(qelt(m,i,j),qelt(n,i,j)))
+      ans
+
+    map(f,m,n,r) ==
+      maxRow := max(maxRowIndex m,maxRowIndex n)
+      maxCol := max(maxColIndex m,maxColIndex n)
+      ans := new(max(nrows m,nrows n),max(ncols m,ncols n),NIL$Lisp)
+      for i in minRowIndex(m)..maxRow repeat
+        for j in minColIndex(m)..maxCol repeat
+          qsetelt_!(ans,i,j,f(elt(m,i,j,r),elt(n,i,j,r)))
+      ans
+
+    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 Row has shallowlyMutable then
+
+      row(m,i) ==
+        i < minRowIndex(m) or i > maxRowIndex(m) =>
+          error "row: index out of range"
+        v : Row := new(ncols m,NIL$Lisp)
+        for j in minColIndex(m)..maxColIndex(m) _
+          for k in minIndex(v)..maxIndex(v) repeat
+            qsetelt_!(v,k,qelt(m,i,j))
+        v
+
+    if Col has shallowlyMutable then
+
+      column(m,j) ==
+        j < minColIndex(m) or j > maxColIndex(m) =>
+          error "column: index out of range"
+        v : Col := new(nrows m,NIL$Lisp)
+        for i in minRowIndex(m)..maxRowIndex(m) _
+          for k in minIndex(v)..maxIndex(v) repeat
+            qsetelt_!(v,k,qelt(m,i,j))
+        v
+
+    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 IIARRAY2 InnerIndexedTwoDimensionalArray}
+<<domain IIARRAY2 InnerIndexedTwoDimensionalArray>>=
+)abbrev domain IIARRAY2 InnerIndexedTwoDimensionalArray
+InnerIndexedTwoDimensionalArray(R,mnRow,mnCol,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
+  mnRow, mnCol : Integer
+  Row : FiniteLinearAggregate R
+  Col : FiniteLinearAggregate R
+
+  Exports ==> TwoDimensionalArrayCategory(R,Row,Col)
+
+  Implementation ==> add
+
+    Rep := PrimitiveArray PrimitiveArray R
+
+--% Predicates
+
+    empty? m == empty?(m)$Rep
+
+--% Primitive array creation
+
+    empty() == empty()$Rep
+
+    new(rows,cols,a) ==
+      rows = 0 =>
+        error "new: arrays with zero rows are not supported"
+--      cols = 0 =>
+--        error "new: arrays with zero columns are not supported"
+      arr : PrimitiveArray PrimitiveArray R := new(rows,empty())
+      for i in minIndex(arr)..maxIndex(arr) repeat
+        qsetelt_!(arr,i,new(cols,a))
+      arr
+
+--% Size inquiries
+
+    minRowIndex m == mnRow
+    minColIndex m == mnCol
+    maxRowIndex m == nrows m + mnRow - 1
+    maxColIndex m == ncols m + mnCol - 1
+
+    nrows m == (# m)$Rep
+
+    ncols m ==
+      empty? m => 0
+      # m(minIndex(m)$Rep)
+
+--% Part selection/assignment
+
+    qelt(m,i,j) ==
+      qelt(qelt(m,i - minRowIndex m)$Rep,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(m,i - minRowIndex m)$Rep,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}{"
+          j : Integer
+          for j in minColIndex(m)..maxColIndex(m) repeat
+            s := concat(s,"c")$String
+          s := concat(s,"} ")$String
+          i : Integer
+          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
+
+@
+\section{domain IARRAY2 IndexedTwoDimensionalArray}
+<<domain IARRAY2 IndexedTwoDimensionalArray>>=
+)abbrev domain IARRAY2 IndexedTwoDimensionalArray
+IndexedTwoDimensionalArray(R,mnRow,mnCol):Exports == Implementation where
+  ++ An IndexedTwoDimensionalArray is a 2-dimensional array where
+  ++ the minimal row and column indices are parameters of the type.
+  ++ Rows and columns are returned as IndexedOneDimensionalArray's with
+  ++ minimal indices matching those of the IndexedTwoDimensionalArray.
+  ++ 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
+  mnRow, mnCol : Integer
+  Row ==> IndexedOneDimensionalArray(R,mnCol)
+  Col ==> IndexedOneDimensionalArray(R,mnRow)
+
+  Exports ==> TwoDimensionalArrayCategory(R,Row,Col)
+
+  Implementation ==>
+    InnerIndexedTwoDimensionalArray(R,mnRow,mnCol,Row,Col)
+
+@
+\section{domain ARRAY2 TwoDimensionalArray}
+<<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
+  Row ==> OneDimensionalArray R
+  Col ==> OneDimensionalArray R
+
+  Exports ==> TwoDimensionalArrayCategory(R,Row,Col) with
+    shallowlyMutable
+      ++ One may destructively alter TwoDimensionalArray's.
+
+  Implementation ==> InnerIndexedTwoDimensionalArray(R,1,1,Row,Col)
+
+@
+\section{License}
+<<license>>=
+--Copyright (c) 1991-2002, The Numerical ALgorithms Group Ltd.
+--All rights reserved.
+--
+--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.
+@
+<<*>>=
+<<license>>
+
+<<category ARR2CAT TwoDimensionalArrayCategory>>
+<<domain IIARRAY2 InnerIndexedTwoDimensionalArray>>
+<<domain IARRAY2 IndexedTwoDimensionalArray>>
+<<domain ARRAY2 TwoDimensionalArray>>
+@
+\eject
+\begin{thebibliography}{99}
+\bibitem{1} nothing
+\end{thebibliography}
+\end{document}