open-axiom repository from github
\documentclass{article}
\usepackage{open-axiom}
\begin{document}
\title{\$SPAD/src/algebra array1.spad}
\author{Gabriel Dos Reis, Michael Monagan, Stephen Watt}
\maketitle
\begin{abstract}
\end{abstract}
\eject
\tableofcontents
\eject
\section{domain PRIMARR PrimitiveArray}
<<domain PRIMARR PrimitiveArray>>=
)abbrev domain PRIMARR PrimitiveArray
++ This provides a fast array type with no bound checking on elt's.
++ Minimum index is 0 in this type, cannot be changed
PrimitiveArray(S:Type): OneDimensionalArrayAggregate S == add
macro NNI == NonNegativeInteger
import %icst0: Integer from Foreign Builtin
import %icst1: Integer from Foreign Builtin
import %vlength: % -> NNI from Foreign Builtin
import %vcopy: % -> % from Foreign Builtin
import %vfill: (%,S) -> % from Foreign Builtin
import %aref: (%,Integer) -> S from Foreign Builtin
import %emptyArray: Type -> % from Foreign Builtin
import %list2array: (List S,Type) -> % from Foreign Builtin
import %array2list: % -> List S from Foreign Builtin
import %simpleArray: (Type,NNI,S) -> % from Foreign Builtin
#x == %vlength x
minIndex x == %icst0
empty() == %emptyArray S
construct l == %list2array(l,S)
new(n, x) == %simpleArray(S,n,x)
qelt(x, i) == %aref(x,i)
elt(x:%, i:Integer) == %aref(x,i)
qsetelt!(x, i, s) == %store(%aref(x,i),s)$Foreign(Builtin)
setelt(x:%, i:Integer, s:S) == %store(%aref(x,i),s)$Foreign(Builtin)
fill!(x, s) == %vfill(x,s)
copy x == %vcopy x
maxIndex x == #x - %icst1
members x == %array2list x
@
\section{package PRIMARR2 PrimitiveArrayFunctions2}
<<package PRIMARR2 PrimitiveArrayFunctions2>>=
)abbrev package PRIMARR2 PrimitiveArrayFunctions2
++ This package provides tools for operating on primitive arrays
++ with unary and binary functions involving different underlying types
PrimitiveArrayFunctions2(A, B): Exports == Implementation where
A, B: Type
VA ==> PrimitiveArray A
VB ==> PrimitiveArray B
O2 ==> FiniteLinearAggregateFunctions2(A, VA, B, VB)
Exports ==> with
scan : ((A, B) -> B, VA, B) -> VB
++ scan(f,a,r) successively applies
++ \spad{reduce(f,x,r)} to more and more leading sub-arrays
++ x of primitive array \spad{a}.
++ More precisely, if \spad{a} is \spad{[a1,a2,...]}, then
++ \spad{scan(f,a,r)} returns
++ \spad{[reduce(f,[a1],r),reduce(f,[a1,a2],r),...]}.
reduce : ((A, B) -> B, VA, B) -> B
++ reduce(f,a,r) applies function f to each
++ successive element of the
++ primitive array \spad{a} and an accumulant initialized to r.
++ For example,
++ \spad{reduce(_+$Integer,[1,2,3],0)}
++ does \spad{3+(2+(1+0))}. Note: third argument r
++ may be regarded as the
++ identity element for the function f.
map : (A -> B, VA) -> VB
++ map(f,a) applies function f to each member of primitive array
++ \spad{a} resulting in a new primitive array over a
++ possibly different underlying domain.
Implementation ==> add
map(f, v) == map(f, v)$O2
scan(f, v, b) == scan(f, v, b)$O2
reduce(f, v, b) == reduce(f, v, b)$O2
@
\section{domain TUPLE Tuple}
<<domain TUPLE Tuple>>=
)abbrev domain TUPLE Tuple
++ This domain is used to interface with the interpreter's notion
++ of comma-delimited sequences of values.
Tuple(S:Type): HomotopicTo (PrimitiveArray S) with
select: (%, NonNegativeInteger) -> S
++ select(x,n) returns the n-th element of tuple x.
++ tuples are 0-based
length: % -> NonNegativeInteger
++ length(x) returns the number of elements in tuple x
if S has CoercibleTo(OutputForm) then CoercibleTo(OutputForm)
if S has SetCategory then SetCategory
== add
Rep := Record(len : NonNegativeInteger, elts : PrimitiveArray S)
coerce(x: PrimitiveArray S): % == [#x, x]
coerce(x:%): PrimitiveArray(S) == x.elts
length x == x.len
select(x, n) ==
n >= x.len => error "Index out of bounds"
x.elts.n
if S has SetCategory then
x = y == (x.len = y.len) and (x.elts =$PrimitiveArray(S) y.elts)
if S has CoercibleTo(OutputForm) then
coerce(x : %): OutputForm ==
paren [(x.elts.i)::OutputForm
for i in minIndex x.elts .. maxIndex x.elts]$List(OutputForm)
@
\section{domain IFARRAY IndexedFlexibleArray}
<<domain IFARRAY IndexedFlexibleArray>>=
)abbrev domain IFARRAY IndexedFlexibleArray
++ Author: Michael Monagan July/87, modified SMW June/91
++ A FlexibleArray is the notion of an array intended to allow for growth
++ at the end only. Hence the following efficient operations
++ \spad{append(x,a)} meaning append item x at the end of the array \spad{a}
++ \spad{delete(a,n)} meaning delete the last item from the array \spad{a}
++ Flexible arrays support the other operations inherited from
++ \spadtype{ExtensibleLinearAggregate}. However, these are not efficient.
++ Flexible arrays combine the \spad{O(1)} access time property of arrays
++ with growing and shrinking at the end in \spad{O(1)} (average) time.
++ This is done by using an ordinary array which may have zero or more
++ empty slots at the end. When the array becomes full it is copied
++ into a new larger (50% larger) array. Conversely, when the array
++ becomes less than 1/2 full, it is copied into a smaller array.
++ Flexible arrays provide for an efficient implementation of many
++ data structures in particular heaps, stacks and sets.
IndexedFlexibleArray(S:Type, mn: Integer): Exports == Implementation where
A ==> PrimitiveArray S
I ==> Integer
N ==> NonNegativeInteger
U ==> UniversalSegment Integer
Exports ==
Join(OneDimensionalArrayAggregate S,ExtensibleLinearAggregate S) with
flexibleArray : List S -> %
++ flexibleArray(l) creates a flexible array from the list of elements l
physicalLength : % -> NonNegativeInteger
++ physicalLength(x) returns the number of elements x can accomodate before growing
physicalLength!: (%, I) -> %
++ physicalLength!(x,n) changes the physical length of x to be n and returns the new array.
shrinkable: Boolean -> Boolean
++ shrinkable(b) sets the shrinkable attribute of flexible arrays to b and returns the previous value
Implementation == add
Rep := Record(physLen:I, logLen:I, f:A)
shrinkable? : Boolean := true
growAndFill : (%, I, S) -> %
growWith : (%, I, S) -> %
growAdding : (%, I, %) -> %
shrink: (%, I) -> %
newa : (N, A) -> A
physicalLength(r) == (r.physLen) pretend NonNegativeInteger
physicalLength!(r, n) ==
r.physLen = 0 => error "flexible array must be non-empty"
growWith(r, n, r.f.0)
empty() == [0, 0, empty()]
#r == (r.logLen)::N
fill!(r, x) == (fill!(r.f, x); r)
maxIndex r == r.logLen - 1 + mn
minIndex r == mn
new(n, a) == [n, n, new(n, a)]
shrinkable(b) ==
oldval := shrinkable?
shrinkable? := b
oldval
flexibleArray l ==
n := #l
n = 0 => empty()
x := l.1
a := new(n,x)
for i in mn + 1..mn + n-1 for y in rest l repeat a.i := y
a
-- local utility operations
newa(n, a) ==
zero? n => empty()
new(n, a.0)
growAdding(r, b, s) ==
b = 0 => r
positive?(#r) => growAndFill(r, b, (r.f).0)
positive?(#s) => growAndFill(r, b, (s.f).0)
error "no default filler element"
growAndFill(r, b, x) ==
(r.logLen := r.logLen + b) <= r.physLen => r
-- enlarge by 50% + b
n := r.physLen + r.physLen quo 2 + 1
if r.logLen > n then n := r.logLen
growWith(r, n, x)
growWith(r, n, x) ==
y := new(n::N, x)$PrimitiveArray(S)
a := r.f
for k in 0 .. r.physLen-1 repeat y.k := a.k
r.physLen := n
r.f := y
r
shrink(r, i) ==
r.logLen := r.logLen - i
negative?(n := r.logLen) => error "internal bug in flexible array"
2*n+2 > r.physLen => r
not shrinkable? => r
if n < r.logLen then error "cannot shrink flexible array to indicated size"
n = 0 => empty()
r.physLen := n
y := newa(n::N, a := r.f)
for k in 0 .. n-1 repeat y.k := a.k
r.f := y
r
copy r ==
n := #r
a := r.f
v := newa(n, a := r.f)
for k in 0..n-1 repeat v.k := a.k
[n, n, v]
elt(r:%, i:I) ==
i < mn or i >= r.logLen + mn =>
error "index out of range"
r.f.(i-mn)
setelt(r:%, i:I, x:S) ==
i < mn or i >= r.logLen + mn =>
error "index out of range"
r.f.(i-mn) := x
-- operations inherited from extensible aggregate
merge(g, a, b) == merge!(g, copy a, b)
concat(x:S, r:%) == insert!(x, r, mn)
concat!(r:%, x:S) ==
growAndFill(r, 1, x)
r.f.(r.logLen-1) := x
r
concat!(a:%, b:%) ==
if eq?(a, b) then b := copy b
n := #a
growAdding(a, #b, b)
copyInto!(a, b, n + mn)
remove!(g:(S->Boolean), a:%) ==
k:I := 0
for i in 0..maxIndex a - mn repeat
if not g(a.i) then (a.k := a.i; k := k+1)
shrink(a, #a - k)
delete!(r:%, i1:I) ==
i := i1 - mn
negative? i or i > r.logLen => error "index out of range"
for k in i..r.logLen-2 repeat r.f.k := r.f.(k+1)
shrink(r, 1)
delete!(r:%, i:U) ==
l := lo i - mn; m := maxIndex r - mn
h := (hasHi i => hi i - mn; m)
negative? l or h > m => error "index out of range"
for j in l.. for k in h+1..m repeat r.f.j := r.f.k
shrink(r, max(0,h-l+1))
insert!(x:S, r:%, i1:I):% ==
i := i1 - mn
n := r.logLen
negative? i or i > n => error "index out of range"
growAndFill(r, 1, x)
for k in n-1 .. i by -1 repeat r.f.(k+1) := r.f.k
r.f.i := x
r
insert!(a:%, b:%, i1:I):% ==
i := i1 - mn
if eq?(a, b) then b := copy b
m := #a; n := #b
negative? i or i > n => error "index out of range"
growAdding(b, m, a)
for k in n-1 .. i by -1 repeat b.f.(m+k) := b.f.k
for k in m-1 .. 0 by -1 repeat b.f.(i+k) := a.f.k
b
merge!(g, a, b) ==
m := #a; n := #b; growAdding(a, n, b)
for i in m-1..0 by -1 for j in m+n-1.. by -1 repeat a.f.j := a.f.i
i := n; j := 0
k : Integer := 0
while i < n+m and j < n repeat
if g(a.f.i,b.f.j) then (a.f.k := a.f.i; i := i+1)
else (a.f.k := b.f.j; j := j+1)
k := k + 1
for j' in j..n-1 repeat
a.f.k := b.f.j'
k := k + 1
a
select!(g:(S->Boolean), a:%) ==
k:I := 0
for i in 0..maxIndex a - mn repeat if g(a.f.i) then (a.f.k := a.f.i;k := k+1)
shrink(a, #a - k)
if S has SetCategory then
removeDuplicates! a ==
ct := #a
ct < 2 => a
i := mn
nlim := mn + ct
nlim0 := nlim
while i < nlim repeat
j := i+1
for k in j..nlim-1 | a.k ~= a.i repeat
a.j := a.k
j := j+1
nlim := j
i := i+1
nlim ~= nlim0 => delete!(a, i..)
a
@
\section{domain FARRAY FlexibleArray}
<<domain FARRAY FlexibleArray>>=
)abbrev domain FARRAY FlexibleArray
++ A FlexibleArray is the notion of an array intended to allow for growth
++ at the end only. Hence the following efficient operations
++ \spad{append(x,a)} meaning append item x at the end of the array \spad{a}
++ \spad{delete(a,n)} meaning delete the last item from the array \spad{a}
++ Flexible arrays support the other operations inherited from
++ \spadtype{ExtensibleLinearAggregate}. However, these are not efficient.
++ Flexible arrays combine the \spad{O(1)} access time property of arrays
++ with growing and shrinking at the end in \spad{O(1)} (average) time.
++ This is done by using an ordinary array which may have zero or more
++ empty slots at the end. When the array becomes full it is copied
++ into a new larger (50% larger) array. Conversely, when the array
++ becomes less than 1/2 full, it is copied into a smaller array.
++ Flexible arrays provide for an efficient implementation of many
++ data structures in particular heaps, stacks and sets.
FlexibleArray(S: Type) == Implementation where
ARRAYMININDEX ==> 1 -- if you want to change this, be my guest
Implementation ==> IndexedFlexibleArray(S, ARRAYMININDEX)
-- Join(OneDimensionalArrayAggregate S, ExtensibleLinearAggregate S)
@
\section{domain IARRAY1 IndexedOneDimensionalArray}
<<domain IARRAY1 IndexedOneDimensionalArray>>=
)abbrev domain IARRAY1 IndexedOneDimensionalArray
++ Author Micheal Monagan Aug/87
++ This is the basic one dimensional array data type.
IndexedOneDimensionalArray(S:Type, mn:Integer):
OneDimensionalArrayAggregate S == PrimitiveArray S add
macro I == Integer
import %icst0: I from Foreign Builtin
import %icst1: I from Foreign Builtin
import %ilt: (I,I) -> Boolean from Foreign Builtin
import %vlength: % -> NonNegativeInteger from Foreign Builtin
import %aref: (%,Integer) -> S from Foreign Builtin
minIndex x == mn
if zero? mn then
qelt(x, i) == %aref(x, i)
qsetelt!(x, i, s) == %store(%aref(x, i), s)$Foreign(Builtin)
elt(x:%, i:I) ==
negative? i or i > maxIndex(x) => error "index out of range"
qelt(x, i)
setelt(x:%, i:I, s:S) ==
negative? i or i > maxIndex(x) => error "index out of range"
qsetelt!(x, i, s)
else if one? mn then
maxIndex x == %vlength x
qelt(x, i) == %aref(x, i - %icst1)
qsetelt!(x, i, s) == %store(%aref(x, i - %icst1), s)$Foreign(Builtin)
elt(x:%, i:I) ==
%ilt(i,%icst1) or %ilt(%vlength x,i) =>
error "index out of range"
%aref(x, i - %icst1)
setelt(x:%, i:I, s:S) ==
%ilt(i,%icst1) or %ilt(%vlength x,i) =>
error "index out of range"
qsetelt!(x,i,s)
else
qelt(x, i) == %aref(x, i - mn)
qsetelt!(x, i, s) == %store(%aref(x, i - mn), s)$Foreign(Builtin)
elt(x:%, i:I) ==
i < mn or i > maxIndex(x) => error "index out of range"
qelt(x, i)
setelt(x:%, i:I, s:S) ==
i < mn or i > maxIndex(x) => error "index out of range"
qsetelt!(x, i, s)
@
\section{domain ARRAY1 OneDimensionalArray}
<<domain ARRAY1 OneDimensionalArray>>=
)abbrev domain ARRAY1 OneDimensionalArray
++ This is the domain of 1-based one dimensional arrays
OneDimensionalArray(S:Type): Exports == Implementation where
Exports == OneDimensionalArrayAggregate S with
oneDimensionalArray: List S -> %
++ oneDimensionalArray(l) creates an array from a list of elements l
oneDimensionalArray: (NonNegativeInteger, S) -> %
++ oneDimensionalArray(n,s) creates an array from n copies of element s
Implementation == IndexedOneDimensionalArray(S, 1) add
oneDimensionalArray(u) == construct u
oneDimensionalArray(n,s) == new(n,s)
@
\section{package ARRAY12 OneDimensionalArrayFunctions2}
<<package ARRAY12 OneDimensionalArrayFunctions2>>=
)abbrev package ARRAY12 OneDimensionalArrayFunctions2
++ This package provides tools for operating on one-dimensional arrays
++ with unary and binary functions involving different underlying types
OneDimensionalArrayFunctions2(A, B): Exports == Implementation where
A, B: Type
VA ==> OneDimensionalArray A
VB ==> OneDimensionalArray B
O2 ==> FiniteLinearAggregateFunctions2(A, VA, B, VB)
Exports ==> with
scan : ((A, B) -> B, VA, B) -> VB
++ scan(f,a,r) successively applies
++ \spad{reduce(f,x,r)} to more and more leading sub-arrays
++ x of one-dimensional array \spad{a}.
++ More precisely, if \spad{a} is \spad{[a1,a2,...]}, then
++ \spad{scan(f,a,r)} returns
++ \spad{[reduce(f,[a1],r),reduce(f,[a1,a2],r),...]}.
reduce : ((A, B) -> B, VA, B) -> B
++ reduce(f,a,r) applies function f to each
++ successive element of the
++ one-dimensional array \spad{a} and an accumulant initialized to r.
++ For example,
++ \spad{reduce(_+$Integer,[1,2,3],0)}
++ does \spad{3+(2+(1+0))}. Note: third argument r
++ may be regarded as the
++ identity element for the function f.
map : (A -> B, VA) -> VB
++ map(f,a) applies function f to each member of one-dimensional array
++ \spad{a} resulting in a new one-dimensional array over a
++ possibly different underlying domain.
Implementation ==> add
map(f, v) == map(f, v)$O2
scan(f, v, b) == scan(f, v, b)$O2
reduce(f, v, b) == reduce(f, v, b)$O2
@
\section{License}
<<license>>=
--Copyright (c) 1991-2002, The Numerical ALgorithms Group Ltd.
--All rights reserved.
-- Copyright (C) 2007-2013, Gabriel Dos Reis.
-- 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>>
<<domain PRIMARR PrimitiveArray>>
<<package PRIMARR2 PrimitiveArrayFunctions2>>
<<domain TUPLE Tuple>>
<<domain IFARRAY IndexedFlexibleArray>>
<<domain FARRAY FlexibleArray>>
<<domain IARRAY1 IndexedOneDimensionalArray>>
<<domain ARRAY1 OneDimensionalArray>>
<<package ARRAY12 OneDimensionalArrayFunctions2>>
--%% TupleFunctions2
--TupleFunctions2(A:Type, B:Type): with
-- map: (A -> B, Tuple A) -> Tuple B
-- == add
-- map(f, t) ==
-- p:PrimitiveArray(B) := new length t
-- for i in minIndex p .. maxIndex p repeat
-- p.i := f select(t, i)
-- p::Tuple(B)
@
\eject
\begin{thebibliography}{99}
\bibitem{1} nothing
\end{thebibliography}
\end{document}