\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} <>= )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} <>= )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} <>= )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} <>= )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} <>= )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} <>= )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} <>= )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} <>= )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} <>= --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. @ <<*>>= <> <> <> <> <> <> <> <> <> --%% 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}