open-axiom repository from github
\documentclass{article}
\usepackage{open-axiom}
\begin{document}
\title{src/algebra aggcat.spad}
\author{Michael Monagan, Manuel Bronstein, Richard Jenks, Stephen Watt}
\maketitle
\begin{abstract}
\end{abstract}
\tableofcontents
\eject
\section{category AGG Aggregate}
<<category AGG Aggregate>>=
import Type
import Boolean
import NonNegativeInteger
)abbrev category AGG Aggregate
++ Author: Michael Monagan; revised by Manuel Bronstein and Richard Jenks
++ Date Created: August 87 through August 88
++ Date Last Updated: April 1991
++ Basic Operations:
++ Related Constructors:
++ Also See:
++ AMS Classifications:
++ Keywords:
++ References:
++ Description:
++ The notion of aggregate serves to model any data structure aggregate,
++ designating any collection of objects,
++ with heterogenous or homogeneous members,
++ with a finite or infinite number
++ of members, explicitly or implicitly represented.
++ An aggregate can in principle
++ represent everything from a string of characters to abstract sets such
++ as "the set of x satisfying relation {\em r(x)}"
Aggregate: Category == Type with
eq?: (%,%) -> Boolean
++ eq?(u,v) tests if u and v are same objects.
copy: % -> %
++ copy(u) returns a top-level (non-recursive) copy of u.
++ Note: for collections, \axiom{copy(u) == [x for x in u]}.
empty: () -> %
++ empty()$D creates an aggregate of type D with 0 elements.
++ Note: The {\em $D} can be dropped if understood by context,
++ e.g. \axiom{u: D := empty()}.
empty?: % -> Boolean
++ empty?(u) tests if u has 0 elements.
sample: constant -> % ++ sample yields a value of type %
add
eq?(a,b) == %peq(a,b)$Foreign(Builtin)
sample() == empty()
@
\section{}
\section{category HOAGG HomogeneousAggregate}
<<category HOAGG HomogeneousAggregate>>=
import Boolean
import OutputForm
import SetCategory
import Aggregate
import CoercibleTo OutputForm
import Evalable
)abbrev category HOAGG HomogeneousAggregate
++ Author: Michael Monagan; revised by Manuel Bronstein and Richard Jenks
++ Further revision by Gabriel Dos Reis.
++ Date Created: August 87 through August 88
++ Date Last Updated: May 17, 2013.
++ Basic Operations:
++ Related Constructors: Aggregate, Functorial
++ Also See:
++ AMS Classifications:
++ Keywords:
++ References:
++ Description:
++ A homogeneous aggregate is an aggregate of elements all of the
++ same type, and is functorial in stored elements..
++ In the current system, all aggregates are homogeneous.
++ Two attributes characterize classes of aggregates.
HomogeneousAggregate(S:Type): Category == Join(Aggregate,Functorial S) with
if S has CoercibleTo(OutputForm) then CoercibleTo(OutputForm)
if S has BasicType then BasicType
if S has SetCategory then SetCategory
if S has SetCategory then
if S has Evalable S then Evalable S
add
if S has Evalable S then
eval(u:%,l:List Equation S):% == map(eval(#1,l),u)
@
\section{Aggregates of finite extent}
<<category FINAGG FiniteAggregate>>=
)abbrev category FINAGG FiniteAggregate
++ Author: Gabriel Dos Reis
++ Date Created: May 15, 2013
++ Date Last Modified: May 15, 2013
++ Description:
++ A finite aggregate is a homogeneous aggregate with a finite
++ number of elements.
FiniteAggregate(S: Type): Category == Exports where
Exports == HomogeneousAggregate S with
#: % -> NonNegativeInteger
++ \spad{#u} returns the number of items in u.
any?: (S->Boolean,%) -> Boolean
++ \spad{any?(p,u)} tests if \spad{p(x)} is true for
++ any element \spad{x} of \spad{u}.
++ Note: for collections,
++ \axiom{any?(p,u) = reduce(or,map(f,u),false,true)}.
every?: (S->Boolean,%) -> Boolean
++ \spad{every?(f,u)} tests if p(x) holds for all
++ elements \spad{x} of \spad{u}.
++ Note: for collections,
++ \axiom{every?(p,u) = reduce(and,map(f,u),true,false)}.
count: (S->Boolean,%) -> NonNegativeInteger
++ \spad{count(p,u)} returns the number of elements \spad{x}
++ in \spad{u} such that \axiom{p(x)} holds. For collections,
++ \axiom{count(p,u) = reduce(+,[1 for x in u | p(x)],0)}.
members: % -> List S
++ \spad{members(u)} returns a list of the consecutive elements of u.
++ For collections, \axiom{members([x,y,...,z]) = (x,y,...,z)}.
reduce: ((S,S)->S,%) -> S
++ \spad{reduce(f,u)} reduces the binary operation \spad{f}
++ across \spad{u}. For example, if \spad{u} is \spad{[x,y,...,z]}
++ then \spad{reduce(f,u)} returns \spad{f(..f(f(x,y),...),z)}.
++ Note: if \spad{u} has one element \spad{x},
++ \spad{reduce(f,u)} returns \spad{x}. Error: if \spad{u} is empty.
reduce: ((S,S)->S,%,S) -> S
++ \spad{reduce(f,u,x)} reduces the binary operation \spad{f}
++ across \spad{u}, where \spad{x} is the starting value, usually
++ the identity operation of \spad{f}. Same as
++ \spad{reduce(f,u)} if \spad{u} has 2 or more elements.
++ Returns \spad{f(x,y)} if \spad{u} has one element \spad{y},
++ \spad{x} if \spad{u} is empty. For example,
++ \spad{reduce(+,u,0)} returns the sum of the elements of \spad{u}.
find: (S->Boolean, %) -> Union(S, "failed")
++ \spad{find(p,u)} returns the first \spad{x} in \spad{u} such
++ that \spad{p(x)} is true, and \spad{"failed"} otherwise.
if S has BasicType then
count: (S,%) -> NonNegativeInteger
++ \spad{count(x,u)} returns the number of occurrences
++ of \spad{x} in \spad{u}.
++ For collections, \axiom{count(x,u) = reduce(+,[x=y for y in u],0)}.
member?: (S,%) -> Boolean
++ \spad{member?(x,u)} tests if \spad{x} is a member of \spad{u}.
++ For collections,
++ \axiom{member?(x,u) = reduce(or,[x=y for y in u],false)}.
reduce: ((S,S)->S,%,S,S) -> S
++ \spad{reduce(f,u,x,z)} reduces the binary operation \spad{f}
++ across \spad{u}, stopping when an "absorbing element"
++ \spad{z} is encountered. As for \spad{reduce(f,u,x)},
++ \spad{x} is the identity operation of \spad{f}.
++ Same as \spad{reduce(f,u,x)} when \spad{u} contains no
++ element \spad{z}. Thus the third argument \spad{x} is
++ returned when u is empty.
add
empty? x == #x = 0
#x == # members x
any?(f, x) == or/[f e for e in members x]
every?(f, x) == and/[f e for e in members x]
count(f:S -> Boolean, x:%) == +/[1 for e in members x | f e]
find(f:S -> Boolean, c:%) == find(f, members c)
if S has BasicType then
count(s:S, x:%) == count(s = #1, x)
member?(e, x) == any?(e = #1,x)
reduce(f,x,e,z) == reduce(f,members x,e,z)
x = y == members x = members y
if S has CoercibleTo OutputForm then
coerce(x:%):OutputForm ==
bracket
commaSeparate [a::OutputForm for a in members x]$List(OutputForm)
@
\section{}
<<category SMAGG ShallowlyMutableAggregate>>=
)abbrev category SMAGG ShallowlyMutableAggregate
++ Author: Gabriel Dos Reis
++ Date Created: May 17, 2013
++ Date Last Created: May 17, 2013
++ Description:
++ This category describes the class of homogeneous aggregates
++ that support in place mutation that do not change their general
++ shapes.
ShallowlyMutableAggregate(S: Type): Category == Exports where
Exports == Aggregate with
map!: (S->S,%) -> %
++ \spad{map!(f,u)} destructively replaces each element
++ \spad{x} of \spad{u} by \spad{f(x)}
@
\section{category CLAGG Collection}
<<category CLAGG Collection>>=
import Boolean
import HomogeneousAggregate
)abbrev category CLAGG Collection
++ Author: Michael Monagan; revised by Manuel Bronstein and Richard Jenks
++ Date Created: August 87 through August 88
++ Date Last Updated: April 1991
++ Basic Operations:
++ Related Constructors:
++ Also See:
++ AMS Classifications:
++ Keywords:
++ References:
++ Description:
++ A collection is a homogeneous aggregate which can built from
++ list of members. The operation used to build the aggregate is
++ generically named \spadfun{construct}. However, each collection
++ provides its own special function with the same name as the
++ data type, except with an initial lower case letter, e.g.
++ \spadfun{list} for \spadtype{List},
++ \spadfun{flexibleArray} for \spadtype{FlexibleArray}, and so on.
Collection(S:Type): Category == HomogeneousAggregate(S) with
construct: List S -> %
++ \axiom{construct(x,y,...,z)} returns the collection of elements \axiom{x,y,...,z}
++ ordered as given. Equivalently written as \axiom{[x,y,...,z]$D}, where
++ D is the domain. D may be omitted for those of type List.
if % has FiniteAggregate S then
remove: (S->Boolean,%) -> %
++ remove(p,u) returns a copy of u removing all elements x such that
++ \axiom{p(x)} is true.
++ Note: \axiom{remove(p,u) == [x for x in u | not p(x)]}.
select: (S->Boolean,%) -> %
++ select(p,u) returns a copy of u containing only those elements such
++ \axiom{p(x)} is true.
++ Note: \axiom{select(p,u) == [x for x in u | p(x)]}.
if S has BasicType then
remove: (S,%) -> %
++ remove(x,u) returns a copy of u with all
++ elements \axiom{y = x} removed.
++ Note: \axiom{remove(y,c) == [x for x in c | x ~= y]}.
removeDuplicates: % -> %
++ removeDuplicates(u) returns a copy of u with all duplicates removed.
if S has ConvertibleTo InputForm then ConvertibleTo InputForm
add
if % has FiniteAggregate S then
remove(f:S->Boolean, x:%) ==
construct remove(f, members x)
select(f:S->Boolean, x:%) ==
construct select(f, members x)
if S has BasicType then
remove(s:S, x:%) == remove(#1 = s, x)
removeDuplicates(x) == construct removeDuplicates members x
@
\section{category BGAGG BagAggregate}
<<category BGAGG BagAggregate>>=
import HomogeneousAggregate
import List
)abbrev category BGAGG BagAggregate
++ Author: Michael Monagan; revised by Manuel Bronstein and Richard Jenks
++ Date Created: August 87 through August 88
++ Date Last Updated: April 1991
++ Basic Operations:
++ Related Constructors:
++ Also See:
++ AMS Classifications:
++ Keywords:
++ References:
++ Description:
++ A bag aggregate is an aggregate for which one can insert and extract objects,
++ and where the order in which objects are inserted determines the order
++ of extraction.
++ Examples of bags are stacks, queues, and dequeues.
BagAggregate(S:Type): Category == Join(HomogeneousAggregate S,ShallowlyMutableAggregate S) with
bag: List S -> %
++ bag([x,y,...,z]) creates a bag with elements x,y,...,z.
extract!: % -> S
++ extract!(u) destructively removes a (random) item from bag u.
insert!: (S,%) -> %
++ insert!(x,u) inserts item x into bag u.
inspect: % -> S
++ inspect(u) returns an (random) element from a bag.
add
bag(l) ==
x:=empty()
for s in l repeat x:=insert!(s,x)
x
@
\section{category SKAGG StackAggregate}
<<category SKAGG StackAggregate>>=
import NonNegativeInteger
import BagAggregate
)abbrev category SKAGG StackAggregate
++ Author: Michael Monagan; revised by Manuel Bronstein and Richard Jenks
++ Date Created: August 87 through August 88
++ Date Last Updated: April 1991
++ Basic Operations:
++ Related Constructors:
++ Also See:
++ AMS Classifications:
++ Keywords:
++ References:
++ Description:
++ A stack is a bag where the last item inserted is the first item extracted.
StackAggregate(S:Type): Category == Join(BagAggregate S,FiniteAggregate S) with
push!: (S,%) -> S
++ push!(x,s) pushes x onto stack s, i.e. destructively changing s
++ so as to have a new first (top) element x.
++ Afterwards, pop!(s) produces x and pop!(s) produces the original s.
pop!: % -> S
++ pop!(s) returns the top element x, destructively removing x from s.
++ Note: Use \axiom{top(s)} to obtain x without removing it from s.
++ Error: if s is empty.
top: % -> S
++ top(s) returns the top element x from s; s remains unchanged.
++ Note: Use \axiom{pop!(s)} to obtain x and remove it from s.
depth: % -> NonNegativeInteger
++ depth(s) returns the number of elements of stack s.
++ Note: \axiom{depth(s) = #s}.
@
\section{category QUAGG QueueAggregate}
<<category QUAGG QueueAggregate>>=
import NonNegativeInteger
import BagAggregate
)abbrev category QUAGG QueueAggregate
++ Author: Michael Monagan; revised by Manuel Bronstein and Richard Jenks
++ Date Created: August 87 through August 88
++ Date Last Updated: April 1991
++ Basic Operations:
++ Related Constructors:
++ Also See:
++ AMS Classifications:
++ Keywords:
++ References:
++ Description:
++ A queue is a bag where the first item inserted is the first item extracted.
QueueAggregate(S:Type): Category == Join(BagAggregate S,FiniteAggregate S) with
enqueue!: (S, %) -> S
++ enqueue!(x,q) inserts x into the queue q at the back end.
dequeue!: % -> S
++ dequeue! s destructively extracts the first (top) element from queue q.
++ The element previously second in the queue becomes the first element.
++ Error: if q is empty.
rotate!: % -> %
++ rotate! q rotates queue q so that the element at the front of
++ the queue goes to the back of the queue.
++ Note: rotate! q is equivalent to enqueue!(dequeue!(q)).
length: % -> NonNegativeInteger
++ length(q) returns the number of elements in the queue.
++ Note: \axiom{length(q) = #q}.
front: % -> S
++ front(q) returns the element at the front of the queue.
++ The queue q is unchanged by this operation.
++ Error: if q is empty.
back: % -> S
++ back(q) returns the element at the back of the queue.
++ The queue q is unchanged by this operation.
++ Error: if q is empty.
@
\section{category DQAGG DequeueAggregate}
<<category DQAGG DequeueAggregate>>=
import StackAggregate
import QueueAggregate
)abbrev category DQAGG DequeueAggregate
++ Author: Michael Monagan; revised by Manuel Bronstein and Richard Jenks
++ Date Created: August 87 through August 88
++ Date Last Updated: April 1991
++ Basic Operations:
++ Related Constructors:
++ Also See:
++ AMS Classifications:
++ Keywords:
++ References:
++ Description:
++ A dequeue is a doubly ended stack, that is, a bag where first items
++ inserted are the first items extracted, at either the front or the back end
++ of the data structure.
DequeueAggregate(S:Type):
Category == Join(StackAggregate S,QueueAggregate S) with
dequeue: () -> %
++ dequeue()$D creates an empty dequeue of type D.
dequeue: List S -> %
++ dequeue([x,y,...,z]) creates a dequeue with first (top or front)
++ element x, second element y,...,and last (bottom or back) element z.
height: % -> NonNegativeInteger
++ height(d) returns the number of elements in dequeue d.
++ Note: \axiom{height(d) = # d}.
top!: % -> S
++ top!(d) returns the element at the top (front) of the dequeue.
bottom!: % -> S
++ bottom!(d) returns the element at the bottom (back) of the dequeue.
insertTop!: (S,%) -> S
++ insertTop!(x,d) destructively inserts x into the dequeue d, that is,
++ at the top (front) of the dequeue.
++ The element previously at the top of the dequeue becomes the
++ second in the dequeue, and so on.
insertBottom!: (S,%) -> S
++ insertBottom!(x,d) destructively inserts x into the dequeue d
++ at the bottom (back) of the dequeue.
extractTop!: % -> S
++ extractTop!(d) destructively extracts the top (front) element
++ from the dequeue d.
++ Error: if d is empty.
extractBottom!: % -> S
++ extractBottom!(d) destructively extracts the bottom (back) element
++ from the dequeue d.
++ Error: if d is empty.
reverse!: % -> %
++ reverse!(d) destructively replaces d by its reverse dequeue, i.e.
++ the top (front) element is now the bottom (back) element, and so on.
@
\section{category PRQAGG PriorityQueueAggregate}
<<category PRQAGG PriorityQueueAggregate>>=
import BagAggregate
)abbrev category PRQAGG PriorityQueueAggregate
++ Author: Michael Monagan; revised by Manuel Bronstein and Richard Jenks
++ Date Created: August 87 through August 88
++ Date Last Updated: April 1991
++ Basic Operations:
++ Related Constructors:
++ Also See:
++ AMS Classifications:
++ Keywords:
++ References:
++ Description:
++ A priority queue is a bag of items from an ordered set where the item
++ extracted is always the maximum element.
PriorityQueueAggregate(S:OrderedSet): Category == Join(BagAggregate S,FiniteAggregate S) with
max: % -> S
++ max(q) returns the maximum element of priority queue q.
merge: (%,%) -> %
++ merge(q1,q2) returns combines priority queues q1 and q2 to return
++ a single priority queue q.
merge!: (%,%) -> %
++ merge!(q,q1) destructively changes priority queue q to include the
++ values from priority queue q1.
@
\section{category DIOPS DictionaryOperations}
<<category DIOPS DictionaryOperations>>=
import Boolean
import Collection
import BagAggregate
)abbrev category DIOPS DictionaryOperations
++ Author: Michael Monagan; revised by Manuel Bronstein and Richard Jenks
++ Date Created: August 87 through August 88
++ Date Last Updated: April 1991
++ Basic Operations:
++ Related Constructors:
++ Also See:
++ AMS Classifications:
++ Keywords:
++ References:
++ Description:
++ This category is a collection of operations common to both
++ categories \spadtype{Dictionary} and \spadtype{MultiDictionary}
DictionaryOperations(S:SetCategory): Category ==
Join(BagAggregate S, Collection(S)) with
dictionary: () -> %
++ dictionary()$D creates an empty dictionary of type D.
dictionary: List S -> %
++ dictionary([x,y,...,z]) creates a dictionary consisting of
++ entries \axiom{x,y,...,z}.
-- insert: (S,%) -> S ++ insert an entry
-- member?: (S,%) -> Boolean ++ search for an entry
-- remove!: (S,%,NonNegativeInteger) -> %
-- ++ remove!(x,d,n) destructively changes dictionary d by removing
-- ++ up to n entries y such that \axiom{y = x}.
-- remove!: (S->Boolean,%,NonNegativeInteger) -> %
-- ++ remove!(p,d,n) destructively changes dictionary d by removing
-- ++ up to n entries x such that \axiom{p(x)} is true.
if % has FiniteAggregate S then
remove!: (S,%) -> %
++ remove!(x,d) destructively changes dictionary d by removing
++ all entries y such that \axiom{y = x}.
remove!: (S->Boolean,%) -> %
++ remove!(p,d) destructively changes dictionary d by removeing
++ all entries x such that \axiom{p(x)} is true.
select!: (S->Boolean,%) -> %
++ select!(p,d) destructively changes dictionary d by removing
++ all entries x such that \axiom{p(x)} is not true.
add
construct l == dictionary l
dictionary() == empty()
if % has FiniteAggregate S then
copy d == dictionary members d
coerce(s:%):OutputForm ==
prefix("dictionary"@String :: OutputForm,
[x::OutputForm for x in members s])
@
\section{category DIAGG Dictionary}
<<category DIAGG Dictionary>>=
import Boolean
import DictionaryOperations
)abbrev category DIAGG Dictionary
++ Author: Michael Monagan; revised by Manuel Bronstein and Richard Jenks
++ Date Created: August 87 through August 88
++ Date Last Updated: April 1991
++ Basic Operations:
++ Related Constructors:
++ Also See:
++ AMS Classifications:
++ Keywords:
++ References:
++ Description:
++ A dictionary is an aggregate in which entries can be inserted,
++ searched for and removed. Duplicates are thrown away on insertion.
++ This category models the usual notion of dictionary which involves
++ large amounts of data where copying is impractical.
++ Principal operations are thus destructive (non-copying) ones.
Dictionary(S:SetCategory): Category ==
DictionaryOperations S add
dictionary l ==
d := dictionary()
for x in l repeat insert!(x, d)
d
if % has FiniteAggregate S then
-- remove(f:S->Boolean,t:%) == remove!(f, copy t)
-- select(f, t) == select!(f, copy t)
select!(f, t) == remove!(not f #1, t)
--extract! d ==
-- empty? d => error "empty dictionary"
-- remove!(x := first members d, d, 1)
-- x
s = t ==
eq?(s,t) => true
#s ~= #t => false
and/[member?(x, t) for x in members s]
remove!(f:S->Boolean, t:%) ==
for m in members t repeat if f m then remove!(m, t)
t
@
\section{category MDAGG MultiDictionary}
<<category MDAGG MultiDictionary>>=
import NonNegativeInteger
import DictionaryOperations
)abbrev category MDAGG MultiDictionary
++ Author: Michael Monagan; revised by Manuel Bronstein and Richard Jenks
++ Date Created: August 87 through August 88
++ Date Last Updated: April 1991
++ Basic Operations:
++ Related Constructors:
++ Also See:
++ AMS Classifications:
++ Keywords:
++ References:
++ Description:
++ A multi-dictionary is a dictionary which may contain duplicates.
++ As for any dictionary, its size is assumed large so that
++ copying (non-destructive) operations are generally to be avoided.
MultiDictionary(S:SetCategory): Category == DictionaryOperations S with
-- count: (S,%) -> NonNegativeInteger ++ multiplicity count
insert!: (S,%,NonNegativeInteger) -> %
++ insert!(x,d,n) destructively inserts n copies of x into dictionary d.
-- remove!: (S,%,NonNegativeInteger) -> %
-- ++ remove!(x,d,n) destructively removes (up to) n copies of x from
-- ++ dictionary d.
removeDuplicates!: % -> %
++ removeDuplicates!(d) destructively removes any duplicate values
++ in dictionary d.
duplicates: % -> List Record(entry:S,count:NonNegativeInteger)
++ duplicates(d) returns a list of values which have duplicates in d
-- ++ duplicates(d) returns a list of ++ duplicates iterator
-- to become duplicates: % -> Iterator(D,D)
@
\section{category SETAGG SetAggregate}
<<category SETAGG SetAggregate>>=
import SetCategory
import Collection
)abbrev category SETAGG SetAggregate
++ Author: Michael Monagan; revised by Manuel Bronstein and Richard Jenks
++ Date Created: August 87 through August 88
++ Date Last Updated: 14 Oct, 1993 by RSS
++ Basic Operations:
++ Related Constructors:
++ Also See:
++ AMS Classifications:
++ Keywords:
++ References:
++ Description:
++ A set category lists a collection of set-theoretic operations
++ useful for both finite sets and multisets.
++ Note however that finite sets are distinct from multisets.
++ Although the operations defined for set categories are
++ common to both, the relationship between the two cannot
++ be described by inclusion or inheritance.
SetAggregate(S:SetCategory):
Category == Join(SetCategory, Collection(S)) with
partiallyOrderedSet
part? : (%, %) -> Boolean
++ s < t returns true if all elements of set aggregate s are also
++ elements of set aggregate t.
brace : () -> %
++ brace()$D (otherwise written {}$D)
++ creates an empty set aggregate of type D.
++ This form is considered obsolete. Use \axiomFun{set} instead.
brace : List S -> %
++ brace([x,y,...,z])
++ creates a set aggregate containing items x,y,...,z.
++ This form is considered obsolete. Use \axiomFun{set} instead.
set : () -> %
++ set()$D creates an empty set aggregate of type D.
set : List S -> %
++ set([x,y,...,z]) creates a set aggregate containing items x,y,...,z.
intersect: (%, %) -> %
++ intersect(u,v) returns the set aggregate w consisting of
++ elements common to both set aggregates u and v.
++ Note: equivalent to the notation (not currently supported)
++ {x for x in u | member?(x,v)}.
difference : (%, %) -> %
++ difference(u,v) returns the set aggregate w consisting of
++ elements in set aggregate u but not in set aggregate v.
++ If u and v have no elements in common, \axiom{difference(u,v)}
++ returns a copy of u.
++ Note: equivalent to the notation (not currently supported)
++ \axiom{{x for x in u | not member?(x,v)}}.
difference : (%, S) -> %
++ difference(u,x) returns the set aggregate u with element x removed.
++ If u does not contain x, a copy of u is returned.
++ Note: \axiom{difference(s, x) = difference(s, {x})}.
symmetricDifference : (%, %) -> %
++ symmetricDifference(u,v) returns the set aggregate of elements x which
++ are members of set aggregate u or set aggregate v but not both.
++ If u and v have no elements in common, \axiom{symmetricDifference(u,v)}
++ returns a copy of u.
++ Note: \axiom{symmetricDifference(u,v) = union(difference(u,v),difference(v,u))}
subset? : (%, %) -> Boolean
++ subset?(u,v) tests if u is a subset of v.
++ Note: equivalent to
++ \axiom{reduce(and,{member?(x,v) for x in u},true,false)}.
union : (%, %) -> %
++ union(u,v) returns the set aggregate of elements which are members
++ of either set aggregate u or v.
union : (%, S) -> %
++ union(u,x) returns the set aggregate u with the element x added.
++ If u already contains x, \axiom{union(u,x)} returns a copy of u.
union : (S, %) -> %
++ union(x,u) returns the set aggregate u with the element x added.
++ If u already contains x, \axiom{union(x,u)} returns a copy of u.
add
symmetricDifference(x, y) == union(difference(x, y), difference(y, x))
union(s:%, x:S) == union(s, {x})
union(x:S, s:%) == union(s, {x})
difference(s:%, x:S) == difference(s, {x})
@
\section{category FSAGG FiniteSetAggregate}
<<category FSAGG FiniteSetAggregate>>=
import Dictionary
import SetAggregate
)abbrev category FSAGG FiniteSetAggregate
++ Author: Michael Monagan; revised by Manuel Bronstein and Richard Jenks
++ Date Created: August 87 through August 88
++ Date Last Updated: 14 Oct, 1993 by RSS
++ Basic Operations:
++ Related Constructors:
++ Also See:
++ AMS Classifications:
++ Keywords:
++ References:
++ Description:
++ A finite-set aggregate models the notion of a finite set, that is,
++ a collection of elements characterized by membership, but not
++ by order or multiplicity.
++ See \spadtype{Set} for an example.
FiniteSetAggregate(S:SetCategory): Category ==
Join(Dictionary S, SetAggregate S,FiniteAggregate S) with
cardinality: % -> NonNegativeInteger
++ cardinality(u) returns the number of elements of u.
++ Note: \axiom{cardinality(u) = #u}.
if S has Finite then
Finite
complement: % -> %
++ complement(u) returns the complement of the set u,
++ i.e. the set of all values not in u.
universe: () -> %
++ universe()$D returns the universal set for finite set aggregate D.
if S has OrderedSet then
max: % -> S
++ max(u) returns the largest element of aggregate u.
min: % -> S
++ min(u) returns the smallest element of aggregate u.
add
part?(s,t) == #s < #t and s = intersect(s,t)
s = t == #s = #t and empty? difference(s,t)
brace l == construct l
set l == construct l
cardinality s == #s
construct l == (s := set(); for x in l repeat insert!(x,s); s)
count(x:S, s:%) == (member?(x, s) => 1; 0)
subset?(s, t) == #s < #t and (and/[member?(x, t) for x in members s])
coerce(s:%):OutputForm ==
brace [x::OutputForm for x in members s]$List(OutputForm)
intersect(s, t) ==
i := {}
for x in members s | member?(x, t) repeat insert!(x, i)
i
difference(s:%, t:%) ==
m := copy s
for x in members t repeat remove!(x, m)
m
symmetricDifference(s, t) ==
d := copy s
for x in members t repeat
if member?(x, s) then remove!(x, d) else insert!(x, d)
d
union(s:%, t:%) ==
u := copy s
for x in members t repeat insert!(x, u)
u
if S has Finite then
universe() == {index(i::PositiveInteger) for i in 1..size()$S}
complement s == difference(universe(), s )
size() == 2 ** size()$S
index i == {index(j::PositiveInteger)$S for j in 1..size()$S | bit?(i-1,j-1)}
random() == index((1 + random(size()$%)$Integer)::PositiveInteger)
lookup s ==
n:PositiveInteger := 1
for x in members s repeat n := n + 2 ** ((lookup(x) - 1)::NonNegativeInteger)
n
if S has OrderedSet then
max s ==
l := members s
empty? l => error "Empty set"
reduce("max", l)
min s ==
l := members s
empty? l => error "Empty set"
reduce("min", l)
@
\section{category MSETAGG MultisetAggregate}
<<category MSETAGG MultisetAggregate>>=
import MultiDictionary
import SetAggregate
)abbrev category MSETAGG MultisetAggregate
++ Author: Michael Monagan; revised by Manuel Bronstein and Richard Jenks
++ Date Created: August 87 through August 88
++ Date Last Updated: April 1991
++ Basic Operations:
++ Related Constructors:
++ Also See:
++ AMS Classifications:
++ Keywords:
++ References:
++ Description:
++ A multi-set aggregate is a set which keeps track of the multiplicity
++ of its elements.
MultisetAggregate(S:SetCategory):
Category == Join(MultiDictionary S, SetAggregate S)
@
\section{category OMSAGG OrderedMultisetAggregate}
<<category OMSAGG OrderedMultisetAggregate>>=
import MultisetAggregate
import PriorityQueueAggregate
import List
)abbrev category OMSAGG OrderedMultisetAggregate
++ Author: Michael Monagan; revised by Manuel Bronstein and Richard Jenks
++ Date Created: August 87 through August 88
++ Date Last Updated: April 1991
++ Basic Operations:
++ Related Constructors:
++ Also See:
++ AMS Classifications:
++ Keywords:
++ References:
++ Description:
++ An ordered-multiset aggregate is a multiset built over an ordered set S
++ so that the relative sizes of its entries can be assessed.
++ These aggregates serve as models for priority queues.
OrderedMultisetAggregate(S:OrderedSet): Category ==
Join(MultisetAggregate S,PriorityQueueAggregate S) with
-- max: % -> S ++ smallest entry in the set
-- duplicates: % -> List Record(entry:S,count:NonNegativeInteger)
++ to become an in order iterator
min: % -> S
++ min(u) returns the smallest entry in the multiset aggregate u.
@
\section{category KDAGG KeyedDictionary}
<<category KDAGG KeyedDictionary>>=
import Dictionary
import List
)abbrev category KDAGG KeyedDictionary
++ Author: Michael Monagan; revised by Manuel Bronstein and Richard Jenks
++ Date Created: August 87 through August 88
++ Date Last Updated: April 1991
++ Basic Operations:
++ Related Constructors:
++ Also See:
++ AMS Classifications:
++ Keywords:
++ References:
++ Description:
++ A keyed dictionary is a dictionary of key-entry pairs for which there is
++ a unique entry for each key.
KeyedDictionary(Key:SetCategory, Entry:SetCategory): Category ==
Join(Dictionary Record(key:Key,entry:Entry),IndexedAggregate(Key,Entry),_
ShallowlyMutableAggregate Entry) with
key?: (Key, %) -> Boolean
++ key?(k,t) tests if k is a key in table t.
keys: % -> List Key
++ keys(t) returns the list the keys in table t.
-- to become keys: % -> Key* and keys: % -> Iterator(Entry,Entry)
remove!: (Key, %) -> Union(Entry,"failed")
++ remove!(k,t) searches the table t for the key k removing
++ (and return) the entry if there.
++ If t has no such key, \axiom{remove!(k,t)} returns "failed".
search: (Key, %) -> Union(Entry,"failed")
++ search(k,t) searches the table t for the key k,
++ returning the entry stored in t for key k.
++ If t has no such key, \axiom{search(k,t)} returns "failed".
add
key?(k, t) == search(k, t) case Entry
member?(p: Record(key: Key,entry: Entry), t: %): Boolean ==
r := search(p.key, t)
r case Entry and r::Entry = p.entry
if % has FiniteAggregate Record(key:Key,entry:Entry) then
keys t == [x.key for x in members t]
elt(t, k) ==
(r := search(k, t)) case Entry => r::Entry
error "key not in table"
elt(t, k, e) ==
(r := search(k, t)) case Entry => r::Entry
e
@
\section{category ELTAB Eltable}
<<category ELTAB Eltable>>=
import Type
import SetCategory
)abbrev category ELTAB Eltable
++ Author: Michael Monagan; revised by Manuel Bronstein
++ Date Created: August 87 through August 88
++ Date Last Updated: April 25, 2010
++ Basic Operations:
++ Related Constructors:
++ Also See:
++ AMS Classifications:
++ Keywords:
++ References:
++ Description:
++ An eltable over domains \spad{S} and \spad{T} is a structure which
++ can be viewed as a function from \spad{S} to \spad{T}.
++ Examples of eltable structures range from data structures, e.g. those
++ of type \spadtype{List}, to algebraic structures, e.g. \spadtype{Polynomial}.
Eltable(S: Type, T: Type): Category == Type with
elt : (%, S) -> T
++ \spad{elt(u,s)} (also written: \spad{u.s}) returns the value
++ of \spad{u} at \spad{s}.
++ Error: if \spad{u} is not defined at \spad{s}.
@
\section{category ELTAGG EltableAggregate}
<<category ELTAGG EltableAggregate>>=
import Type
import SetCategory
)abbrev category ELTAGG EltableAggregate
++ Author: Michael Monagan; revised by Manuel Bronstein and Richard Jenks
++ Date Created: August 87 through August 88
++ Date Last Updated: April 1991
++ Basic Operations:
++ Related Constructors:
++ Also See:
++ AMS Classifications:
++ Keywords:
++ References:
++ Description:
++ An eltable aggregate is one which can be viewed as a function.
++ For example, the list \axiom{[1,7,4]} can applied to 0,1, and 2 respectively
++ will return the integers 1,7, and 4; thus this list may be viewed
++ as mapping 0 to 1, 1 to 7 and 2 to 4. In general, an aggregate
++ can map members of a domain {\em Dom} to an image domain {\em Im}.
EltableAggregate(Dom: BasicType, Im:Type): Category ==
Eltable(Dom, Im) with
elt : (%, Dom, Im) -> Im
++ elt(u, x, y) applies u to x if x is in the domain of u,
++ and returns y otherwise.
++ For example, if u is a polynomial in \axiom{x} over the rationals,
++ \axiom{elt(u,n,0)} may define the coefficient of \axiom{x}
++ to the power n, returning 0 when n is out of range.
qelt: (%, Dom) -> Im
++ qelt(u, x) applies \axiom{u} to \axiom{x} without checking whether
++ \axiom{x} is in the domain of \axiom{u}. If \axiom{x} is not in the
++ domain of \axiom{u} a memory-access violation may occur. If a check
++ on whether \axiom{x} is in the domain of \axiom{u} is required, use
++ the function \axiom{elt}.
if % has ShallowlyMutableAggregate Im then
setelt : (%, Dom, Im) -> Im
++ setelt(u,x,y) sets the image of x to be y under u,
++ assuming x is in the domain of u.
++ Error: if x is not in the domain of u.
-- this function will soon be renamed as setelt!.
qsetelt!: (%, Dom, Im) -> Im
++ qsetelt!(u,x,y) sets the image of \axiom{x} to be \axiom{y} under
++ \axiom{u}, without checking that \axiom{x} is in the domain of
++ \axiom{u}.
++ If such a check is required use the function \axiom{setelt}.
add
qelt(a, x) == elt(a, x)
if % has ShallowlyMutableAggregate Im then
qsetelt!(a, x, y) == (a.x := y)
@
\section{category IXAGG IndexedAggregate}
<<category IXAGG IndexedAggregate>>=
import Type
import SetCategory
import HomogeneousAggregate
import EltableAggregate
import List
)abbrev category IXAGG IndexedAggregate
++ Author: Michael Monagan; revised by Manuel Bronstein and Richard Jenks
++ Date Created: August 87 through August 88
++ Date Last Updated: April 1991
++ Basic Operations:
++ Related Constructors:
++ Also See:
++ AMS Classifications:
++ Keywords:
++ References:
++ Description:
++ An indexed aggregate is a many-to-one mapping of indices to entries.
++ For example, a one-dimensional-array is an indexed aggregate where
++ the index is an integer. Also, a table is an indexed aggregate
++ where the indices and entries may have any type.
IndexedAggregate(Index: BasicType, Entry: Type): Category ==
Join(HomogeneousAggregate(Entry), EltableAggregate(Index, Entry)) with
entries: % -> List Entry
++ entries(u) returns a list of all the entries of aggregate u
++ in no assumed order.
-- to become entries: % -> Entry* and entries: % -> Iterator(Entry,Entry)
index?: (Index,%) -> Boolean
++ index?(i,u) tests if i is an index of aggregate u.
indices: % -> List Index
++ indices(u) returns a list of indices of aggregate u in no
++ particular order.
-- to become indices: % -> Index* and indices: % -> Iterator(Index,Index).
-- map: ((Entry,Entry)->Entry,%,%,Entry) -> %
-- ++ exists c = map(f,a,b,x), i:Index where
-- ++ c.i = f(a(i,x),b(i,x)) | index?(i,a) or index?(i,b)
if Entry has BasicType and % has FiniteAggregate Entry then
entry?: (Entry,%) -> Boolean
++ entry?(x,u) tests if x equals \axiom{u . i} for some index i.
if Index has OrderedSet then
maxIndex: % -> Index
++ maxIndex(u) returns the maximum index i of aggregate u.
++ Note: in general,
++ \axiom{maxIndex(u) = reduce(max,[i for i in indices u])};
++ if u is a list, \axiom{maxIndex(u) = #u}.
minIndex: % -> Index
++ minIndex(u) returns the minimum index i of aggregate u.
++ Note: in general,
++ \axiom{minIndex(a) = reduce(min,[i for i in indices a])};
++ for lists, \axiom{minIndex(a) = 1}.
first : % -> Entry
++ first(u) returns the first element x of u.
++ Note: for collections, \axiom{first([x,y,...,z]) = x}.
++ Error: if u is empty.
if % has ShallowlyMutableAggregate Entry then
fill!: (%,Entry) -> %
++ fill!(u,x) replaces each entry in aggregate u by x.
++ The modified u is returned as value.
swap!: (%,Index,Index) -> Void
++ swap!(u,i,j) interchanges elements i and j of aggregate u.
++ No meaningful value is returned.
add
elt(a, i, x) == (index?(i, a) => qelt(a, i); x)
if % has FiniteAggregate Entry then
entries x == members x
if Entry has BasicType then
entry?(x, a) == member?(x, a)
if Index has OrderedSet then
maxIndex a == "max"/indices(a)
minIndex a == "min"/indices(a)
first a == a minIndex a
if % has ShallowlyMutableAggregate Entry then
map(f, a) == map!(f, copy a)
map!(f, a) ==
for i in indices a repeat qsetelt!(a, i, f qelt(a, i))
a
fill!(a, x) ==
for i in indices a repeat qsetelt!(a, i, x)
a
swap!(a, i, j) ==
t := a.i
qsetelt!(a, i, a.j)
qsetelt!(a, j, t)
@
\section{category TBAGG TableAggregate}
<<category TBAGG TableAggregate>>=
import SetCategory
import KeyedDictionary
import IndexedAggregate
import Boolean
import OutputForm
import List
)abbrev category TBAGG TableAggregate
++ Author: Michael Monagan, Stephen Watt; revised by Manuel Bronstein and Richard Jenks
++ Date Created: August 87 through August 88
++ Date Last Updated: May 17, 2013.
++ Basic Operations:
++ Related Constructors:
++ Also See:
++ AMS Classifications:
++ Keywords:
++ References:
++ Description:
++ A table aggregate is a model of a table, i.e. a discrete many-to-one
++ mapping from keys to entries.
TableAggregate(Key:SetCategory, Entry:SetCategory): Category ==
Join(KeyedDictionary(Key,Entry), FiniteAggregate Record(key:Key,entry:Entry)) with
table: () -> %
++ table()$T creates an empty table of type T.
table: List Record(key:Key,entry:Entry) -> %
++ table([x,y,...,z]) creates a table consisting of entries
++ \axiom{x,y,...,z}.
-- to become table: Record(key:Key,entry:Entry)* -> %
map: ((Entry, Entry) -> Entry, %, %) -> %
++ map(fn,t1,t2) creates a new table t from given tables t1 and t2 with
++ elements fn(x,y) where x and y are corresponding elements from t1
++ and t2 respectively.
add
table() == empty()
table l == dictionary l
-- empty() == dictionary()
insert!(p,t) == (t(p.key) := p.entry; t)
indices t == keys t
coerce(t:%):OutputForm ==
prefix("table"::OutputForm,
[k::OutputForm = (t.k)::OutputForm for k in keys t])
map!(f: Entry->Entry, t: %) ==
for k in keys t repeat t.k := f t.k
t
map(f:(Entry, Entry) -> Entry, s:%, t:%) ==
z := table()
for k in keys s | key?(k, t) repeat z.k := f(s.k, t.k)
z
-- map(f, s, t, x) ==
-- z := table()
-- for k in keys s repeat z.k := f(s.k, t(k, x))
-- for k in keys t | not key?(k, s) repeat z.k := f(t.k, x)
-- z
members(t:%):List Record(key:Key,entry:Entry) == [[k, t.k] for k in keys t]
entries(t:%):List Entry == [t.k for k in keys t]
s:% = t:% ==
eq?(s,t) => true
#s ~= #t => false
for k in keys s repeat
(e := search(k, t)) case "failed" or (e::Entry) ~= s.k =>
return false
true
map(f: Record(key:Key,entry:Entry)->Record(key:Key,entry:Entry), t: %): % ==
z := table()
for k in keys t repeat
ke: Record(key:Key,entry:Entry) := f [k, t.k]
z ke.key := ke.entry
z
map!(f: Record(key:Key,entry:Entry)->Record(key:Key,entry:Entry), t: %): % ==
lke: List Record(key:Key,entry:Entry) := nil()
for k in keys t repeat
lke := cons(f [k, remove!(k,t)::Entry], lke)
for ke in lke repeat
t ke.key := ke.entry
t
inspect(t: %): Record(key:Key,entry:Entry) ==
ks := keys t
empty? ks => error "Cannot extract from an empty aggregate"
[first ks, t first ks]
find(f: Record(key:Key,entry:Entry)->Boolean, t:%): Union(Record(key:Key,entry:Entry), "failed") ==
for ke in members(t)@List(Record(key:Key,entry:Entry)) repeat if f ke then return ke
"failed"
index?(k: Key, t: %): Boolean ==
search(k,t) case Entry
remove!(x:Record(key:Key,entry:Entry), t:%) ==
if member?(x, t) then remove!(x.key, t)
t
extract!(t: %): Record(key:Key,entry:Entry) ==
k: Record(key:Key,entry:Entry) := inspect t
remove!(k.key, t)
k
@
\section{category RCAGG RecursiveAggregate}
<<category RCAGG RecursiveAggregate>>=
import Type
import SetCategory
import List
import Boolean
)abbrev category RCAGG RecursiveAggregate
++ Author: Michael Monagan; revised by Manuel Bronstein and Richard Jenks
++ Date Created: August 87 through August 88
++ Date Last Updated: April 1991
++ Basic Operations:
++ Related Constructors:
++ Also See:
++ AMS Classifications:
++ Keywords:
++ References:
++ Description:
++ A recursive aggregate over a type S is a model for a
++ a directed graph containing values of type S.
++ Recursively, a recursive aggregate is a {\em node}
++ consisting of a \spadfun{value} from S and 0 or more \spadfun{children}
++ which are recursive aggregates.
++ A node with no children is called a \spadfun{leaf} node.
++ A recursive aggregate may be cyclic for which some operations as noted
++ may go into an infinite loop.
RecursiveAggregate(S:Type): Category == HomogeneousAggregate(S) with
children: % -> List %
++ children(u) returns a list of the children of aggregate u.
-- should be % -> %* and also needs children: % -> Iterator(S,S)
nodes: % -> List %
++ nodes(u) returns a list of all of the nodes of aggregate u.
-- to become % -> %* and also nodes: % -> Iterator(S,S)
leaf?: % -> Boolean
++ leaf?(u) tests if u is a terminal node.
value: % -> S
++ value(u) returns the value of the node u.
elt: (%,"value") -> S
++ elt(u,"value") (also written: \axiom{a. value}) is
++ equivalent to \axiom{value(a)}.
cyclic?: % -> Boolean
++ cyclic?(u) tests if u has a cycle.
leaves: % -> List S
++ leaves(t) returns the list of values in obtained by visiting the
++ nodes of tree \axiom{t} in left-to-right order.
distance: (%,%) -> Integer
++ distance(u,v) returns the path length (an integer) from node u to v.
if S has BasicType then
child?: (%,%) -> Boolean
++ child?(u,v) tests if node u is a child of node v.
node?: (%,%) -> Boolean
++ node?(u,v) tests if node u is contained in node v
++ (either as a child, a child of a child, etc.).
if % has ShallowlyMutableAggregate S then
setchildren!: (%,List %)->%
++ setchildren!(u,v) replaces the current children of node u
++ with the members of v in left-to-right order.
setelt: (%,"value",S) -> S
++ setelt(a,"value",x) (also written \axiom{a . value := x})
++ is equivalent to \axiom{setvalue!(a,x)}
setvalue!: (%,S) -> S
++ setvalue!(u,x) sets the value of node u to x.
add
elt(x,"value") == value x
if % has ShallowlyMutableAggregate S then
setelt(x,"value",y) == setvalue!(x,y)
if S has BasicType then
child?(x,l) == member?(x,children(l))
@
\section{category BRAGG BinaryRecursiveAggregate}
<<category BRAGG BinaryRecursiveAggregate>>=
import Type
import RecursiveAggregate
)abbrev category BRAGG BinaryRecursiveAggregate
++ Author: Michael Monagan; revised by Manuel Bronstein and Richard Jenks
++ Date Created: August 87 through August 88
++ Date Last Updated: April 1991
++ Basic Operations:
++ Related Constructors:
++ Also See:
++ AMS Classifications:
++ Keywords:
++ References:
++ Description:
++ A binary-recursive aggregate has 0, 1 or 2 children and
++ serves as a model for a binary tree or a doubly-linked aggregate structure
BinaryRecursiveAggregate(S:Type):Category == RecursiveAggregate S with
-- needs preorder, inorder and postorder iterators
left: % -> %
++ left(u) returns the left child.
elt: (%,"left") -> %
++ elt(u,"left") (also written: \axiom{a . left}) is
++ equivalent to \axiom{left(a)}.
right: % -> %
++ right(a) returns the right child.
elt: (%,"right") -> %
++ elt(a,"right") (also written: \axiom{a . right})
++ is equivalent to \axiom{right(a)}.
if % has ShallowlyMutableAggregate S then
setelt: (%,"left",%) -> %
++ setelt(a,"left",b) (also written \axiom{a . left := b}) is equivalent
++ to \axiom{setleft!(a,b)}.
setleft!: (%,%) -> %
++ setleft!(a,b) sets the left child of \axiom{a} to be b.
setelt: (%,"right",%) -> %
++ setelt(a,"right",b) (also written \axiom{b . right := b})
++ is equivalent to \axiom{setright!(a,b)}.
setright!: (%,%) -> %
++ setright!(a,x) sets the right child of t to be x.
add
cycleMax ==> 1000
elt(x,"left") == left x
elt(x,"right") == right x
leaf? x == empty? x or empty? left x and empty? right x
leaves t ==
empty? t => empty()$List(S)
leaf? t => [value t]
concat(leaves left t,leaves right t)
nodes x ==
l := empty()$List(%)
empty? x => l
concat(nodes left x,concat([x],nodes right x))
children x ==
l := empty()$List(%)
empty? x => l
empty? left x => [right x]
empty? right x => [left x]
[left x, right x]
if % has SetAggregate(S) and S has BasicType then
node?(u,v) ==
empty? v => false
u = v => true
for y in children v repeat node?(u,y) => return true
false
x = y ==
empty?(x) => empty?(y)
empty?(y) => false
value x = value y and left x = left y and right x = right y
if % has FiniteAggregate S then
member?(x,u) ==
empty? u => false
x = value u => true
member?(x,left u) or member?(x,right u)
if S has CoercibleTo(OutputForm) then
coerce(t:%): OutputForm ==
empty? t => bracket(empty()$OutputForm)
v := value(t):: OutputForm
empty? left t =>
empty? right t => v
r := (right t)::OutputForm
bracket ["."::OutputForm, v, r]
l := (left t)::OutputForm
r :=
empty? right t => "."::OutputForm
(right t)::OutputForm
bracket [l, v, r]
if % has FiniteAggregate S then
aggCount: (%,NonNegativeInteger) -> NonNegativeInteger
#x == aggCount(x,0)
aggCount(x,k) ==
empty? x => 0
k := k + 1
k = cycleMax and cyclic? x => error "cyclic tree"
for y in children x repeat k := aggCount(y,k)
k
isCycle?: (%, List %) -> Boolean
eqMember?: (%, List %) -> Boolean
cyclic? x == not empty? x and isCycle?(x,empty()$(List %))
isCycle?(x,acc) ==
empty? x => false
eqMember?(x,acc) => true
for y in children x | not empty? y repeat
isCycle?(y,acc) => return true
false
eqMember?(y,l) ==
for x in l repeat eq?(x,y) => return true
false
if % has ShallowlyMutableAggregate S then
setelt(x,"left",b) == setleft!(x,b)
setelt(x,"right",b) == setright!(x,b)
@
\section{category DLAGG DoublyLinkedAggregate}
<<category DLAGG DoublyLinkedAggregate>>=
import Type
import RecursiveAggregate
)abbrev category DLAGG DoublyLinkedAggregate
++ Author: Michael Monagan; revised by Manuel Bronstein and Richard Jenks
++ Date Created: August 87 through August 88
++ Date Last Updated: April 1991
++ Basic Operations:
++ Related Constructors:
++ Also See:
++ AMS Classifications:
++ Keywords:
++ References:
++ Description:
++ A doubly-linked aggregate serves as a model for a doubly-linked
++ list, that is, a list which can has links to both next and previous
++ nodes and thus can be efficiently traversed in both directions.
DoublyLinkedAggregate(S:Type): Category == RecursiveAggregate S with
last: % -> S
++ last(l) returns the last element of a doubly-linked aggregate l.
++ Error: if l is empty.
head: % -> %
++ head(l) returns the first element of a doubly-linked aggregate l.
++ Error: if l is empty.
tail: % -> %
++ tail(l) returns the doubly-linked aggregate l starting at
++ its second element.
++ Error: if l is empty.
previous: % -> %
++ previous(l) returns the doubly-link list beginning with its previous
++ element.
++ Error: if l has no previous element.
++ Note: \axiom{next(previous(l)) = l}.
next: % -> %
++ next(l) returns the doubly-linked aggregate beginning with its next
++ element.
++ Error: if l has no next element.
++ Note: \axiom{next(l) = rest(l)} and \axiom{previous(next(l)) = l}.
if % has ShallowlyMutableAggregate S then
concat!: (%,%) -> %
++ concat!(u,v) destructively concatenates doubly-linked aggregate v to the end of doubly-linked aggregate u.
setprevious!: (%,%) -> %
++ setprevious!(u,v) destructively sets the previous node of doubly-linked aggregate u to v, returning v.
setnext!: (%,%) -> %
++ setnext!(u,v) destructively sets the next node of doubly-linked aggregate u to v, returning v.
@
\section{category URAGG UnaryRecursiveAggregate}
<<category URAGG UnaryRecursiveAggregate>>=
import Type
import RecursiveAggregate
import NonNegativeInteger
)abbrev category URAGG UnaryRecursiveAggregate
++ Author: Michael Monagan; revised by Manuel Bronstein and Richard Jenks
++ Date Created: August 87 through August 88
++ Date Last Updated: April 1991
++ Basic Operations:
++ Related Constructors:
++ Also See:
++ AMS Classifications:
++ Keywords:
++ References:
++ Description:
++ A unary-recursive aggregate is a one where nodes may have either
++ 0 or 1 children.
++ This aggregate models, though not precisely, a linked
++ list possibly with a single cycle.
++ A node with one children models a non-empty list, with the
++ \spadfun{value} of the list designating the head, or \spadfun{first}, of the
++ list, and the child designating the tail, or \spadfun{rest}, of the list.
++ A node with no child then designates the empty list.
++ Since these aggregates are recursive aggregates, they may be cyclic.
UnaryRecursiveAggregate(S:Type): Category == RecursiveAggregate S with
concat: (%,%) -> %
++ concat(u,v) returns an aggregate w consisting of the elements of u
++ followed by the elements of v.
++ Note: \axiom{v = rest(w,#a)}.
concat: (S,%) -> %
++ concat(x,u) returns aggregate consisting of x followed by
++ the elements of u.
++ Note: if \axiom{v = concat(x,u)} then \axiom{x = first v}
++ and \axiom{u = rest v}.
first: % -> S
++ first(u) returns the first element of u
++ (equivalently, the value at the current node).
elt: (%,"first") -> S
++ elt(u,"first") (also written: \axiom{u . first}) is equivalent to first u.
first: (%,NonNegativeInteger) -> %
++ first(u,n) returns a copy of the first n (\axiom{n >= 0}) elements of u.
rest: % -> %
++ rest(u) returns an aggregate consisting of all but the first
++ element of u
++ (equivalently, the next node of u).
elt: (%,"rest") -> %
++ elt(%,"rest") (also written: \axiom{u.rest}) is
++ equivalent to \axiom{rest u}.
rest: (%,NonNegativeInteger) -> %
++ rest(u,n) returns the \axiom{n}th (n >= 0) node of u.
++ Note: \axiom{rest(u,0) = u}.
last: % -> S
++ last(u) resturn the last element of u.
++ Note: for lists, \axiom{last(u) = u . (maxIndex u) = u . (# u - 1)}.
elt: (%,"last") -> S
++ elt(u,"last") (also written: \axiom{u . last}) is equivalent to last u.
last: (%,NonNegativeInteger) -> %
++ last(u,n) returns a copy of the last n (\axiom{n >= 0}) nodes of u.
++ Note: \axiom{last(u,n)} is a list of n elements.
tail: % -> %
++ tail(u) returns the last node of u.
++ Note: if u is \axiom{shallowlyMutable},
++ \axiom{setrest(tail(u),v) = concat(u,v)}.
second: % -> S
++ second(u) returns the second element of u.
++ Note: \axiom{second(u) = first(rest(u))}.
third: % -> S
++ third(u) returns the third element of u.
++ Note: \axiom{third(u) = first(rest(rest(u)))}.
cycleEntry: % -> %
++ cycleEntry(u) returns the head of a top-level cycle contained in
++ aggregate u, or \axiom{empty()} if none exists.
cycleLength: % -> NonNegativeInteger
++ cycleLength(u) returns the length of a top-level cycle
++ contained in aggregate u, or 0 is u has no such cycle.
cycleTail: % -> %
++ cycleTail(u) returns the last node in the cycle, or
++ empty if none exists.
if % has ShallowlyMutableAggregate S then
concat!: (%,%) -> %
++ concat!(u,v) destructively concatenates v to the end of u.
++ Note: \axiom{concat!(u,v) = setlast!(u,v)}.
concat!: (%,S) -> %
++ concat!(u,x) destructively adds element x to the end of u.
++ Note: \axiom{concat!(a,x) = setlast!(a,[x])}.
cycleSplit!: % -> %
++ cycleSplit!(u) splits the aggregate by dropping off the cycle.
++ The value returned is the cycle entry, or nil if none exists.
++ For example, if \axiom{w = concat(u,v)} is the cyclic list where v is
++ the head of the cycle, \axiom{cycleSplit!(w)} will drop v off w thus
++ destructively changing w to u, and returning v.
setfirst!: (%,S) -> S
++ setfirst!(u,x) destructively changes the first element of a to x.
setelt: (%,"first",S) -> S
++ setelt(u,"first",x) (also written: \axiom{u.first := x}) is
++ equivalent to \axiom{setfirst!(u,x)}.
setrest!: (%,%) -> %
++ setrest!(u,v) destructively changes the rest of u to v.
setelt: (%,"rest",%) -> %
++ setelt(u,"rest",v) (also written: \axiom{u.rest := v}) is equivalent to
++ \axiom{setrest!(u,v)}.
setlast!: (%,S) -> S
++ setlast!(u,x) destructively changes the last element of u to x.
setelt: (%,"last",S) -> S
++ setelt(u,"last",x) (also written: \axiom{u.last := b})
++ is equivalent to \axiom{setlast!(u,v)}.
split!: (%,Integer) -> %
++ split!(u,n) splits u into two aggregates: \axiom{v = rest(u,n)}
++ and \axiom{w = first(u,n)}, returning \axiom{v}.
++ Note: afterwards \axiom{rest(u,n)} returns \axiom{empty()}.
add
cycleMax ==> 1000
findCycle: % -> %
elt(x, "first") == first x
elt(x, "last") == last x
elt(x, "rest") == rest x
second x == first rest x
third x == first rest rest x
cyclic? x == not empty? x and not empty? findCycle x
last x == first tail x
nodes x ==
l := empty()$List(%)
while not empty? x repeat
l := concat(x, l)
x := rest x
reverse! l
children x ==
l := empty()$List(%)
empty? x => l
concat(rest x,l)
leaf? x == empty? x
value x ==
empty? x => error "value of empty object"
first x
if % has FiniteAggregate S then
#x ==
k: NonNegativeInteger := 0
while not empty? x repeat
k = cycleMax and cyclic? x => error "cyclic list"
x := rest x
k := k + 1
k
tail x ==
empty? x => error "empty list"
y := rest x
for k in 0.. while not empty? y repeat
k = cycleMax and cyclic? x => error "cyclic list"
y := rest(x := y)
x
findCycle x ==
y := rest x
while not empty? y repeat
if eq?(x, y) then return x
x := rest x
y := rest y
if empty? y then return y
if eq?(x, y) then return y
y := rest y
y
cycleTail x ==
empty?(y := x := cycleEntry x) => x
z := rest x
while not eq?(x,z) repeat (y := z; z := rest z)
y
cycleEntry x ==
empty? x => x
empty?(y := findCycle x) => y
z := rest y
l: NonNegativeInteger := 1
while not eq?(y,z) repeat
z := rest z
l := l + 1
y := x
for k in 1..l repeat y := rest y
while not eq?(x,y) repeat (x := rest x; y := rest y)
x
cycleLength x ==
empty? x => 0
empty?(x := findCycle x) => 0
y := rest x
k: NonNegativeInteger := 1
while not eq?(x,y) repeat
y := rest y
k := k + 1
k
rest(x, n) ==
for i in 1..n repeat
empty? x => error "Index out of range"
x := rest x
x
if % has FiniteAggregate S then
last(x, n) ==
n > (m := #x) => error "index out of range"
copy rest(x, (m - n)::NonNegativeInteger)
if S has BasicType then
x = y ==
eq?(x, y) => true
for k in 0.. while not empty? x and not empty? y repeat
k = cycleMax and cyclic? x => error "cyclic list"
first x ~= first y => return false
x := rest x
y := rest y
empty? x and empty? y
node?(u, v) ==
for k in 0.. while not empty? v repeat
u = v => return true
k = cycleMax and cyclic? v => error "cyclic list"
v := rest v
u=v
if % has ShallowlyMutableAggregate S then
setelt(x, "first", a) == setfirst!(x, a)
setelt(x, "last", a) == setlast!(x, a)
setelt(x, "rest", a) == setrest!(x, a)
concat(x:%, y:%) == concat!(copy x, y)
setlast!(x, s) ==
empty? x => error "setlast: empty list"
setfirst!(tail x, s)
s
setchildren!(u,lv) ==
#lv=1 => setrest!(u, first lv)
error "wrong number of children specified"
setvalue!(u,s) == setfirst!(u,s)
split!(p, n) ==
n < 1 => error "index out of range"
p := rest(p, (n - 1)::NonNegativeInteger)
q := rest p
setrest!(p, empty())
q
cycleSplit! x ==
empty?(y := cycleEntry x) or eq?(x, y) => y
z := rest x
while not eq?(z, y) repeat (x := z; z := rest z)
setrest!(x, empty())
y
map!(f,x) ==
y := x
while not empty? y repeat
setfirst!(y,f first y)
y := rest y
x
@
\section{category STAGG StreamAggregate}
<<category STAGG StreamAggregate>>=
import Type
import UnaryRecursiveAggregate
import LinearAggregate
import Boolean
)abbrev category STAGG StreamAggregate
++ Author: Michael Monagan; revised by Manuel Bronstein and Richard Jenks
++ Date Created: August 87 through August 88
++ Date Last Updated: April 1991
++ Basic Operations:
++ Related Constructors:
++ Also See:
++ AMS Classifications:
++ Keywords:
++ References:
++ Description:
++ A stream aggregate is a linear aggregate which possibly has an infinite
++ number of elements. A basic domain constructor which builds stream
++ aggregates is \spadtype{Stream}. From streams, a number of infinite
++ structures such power series can be built. A stream aggregate may
++ also be infinite since it may be cyclic.
++ For example, see \spadtype{DecimalExpansion}.
StreamAggregate(S:Type): Category ==
Join(UnaryRecursiveAggregate S, LinearAggregate S) with
explicitlyFinite?: % -> Boolean
++ explicitlyFinite?(s) tests if the stream has a finite
++ number of elements, and false otherwise.
++ Note: for many datatypes, \axiom{explicitlyFinite?(s) = not possiblyInfinite?(s)}.
possiblyInfinite?: % -> Boolean
++ possiblyInfinite?(s) tests if the stream s could possibly
++ have an infinite number of elements.
++ Note: for many datatypes, \axiom{possiblyInfinite?(s) = not explictlyFinite?(s)}.
less?: (%,NonNegativeInteger) -> Boolean
++ less?(u,n) tests if u has less than n elements.
more?: (%,NonNegativeInteger) -> Boolean
++ more?(u,n) tests if u has greater than n elements.
size?: (%,NonNegativeInteger) -> Boolean
++ size?(u,n) tests if u has exactly n elements.
add
c2: (%, %) -> S
explicitlyFinite? x == not cyclic? x
possiblyInfinite? x == cyclic? x
first(x, n) == construct [c2(x, x := rest x) for i in 1..n]
c2(x, r) ==
empty? x => error "Index out of range"
first x
elt(x:%, i:Integer) ==
i := i - minIndex x
negative? i or empty?(x := rest(x, i::NonNegativeInteger)) =>
error "index out of range"
first x
elt(x:%, i:UniversalSegment(Integer)) ==
l := lo(i) - minIndex x
negative? l => error "index out of range"
not hasHi i => copy(rest(x, l::NonNegativeInteger))
(h := hi(i) - minIndex x) < l => empty()
first(rest(x, l::NonNegativeInteger), (h - l + 1)::NonNegativeInteger)
if % has ShallowlyMutableAggregate S then
concat(x:%, y:%) == concat!(copy x, y)
concat l ==
empty? l => empty()
concat!(copy first l, concat rest l)
fill!(x, s) ==
y := x
while not empty? y repeat (setfirst!(y, s); y := rest y)
x
setelt(x:%, i:Integer, s:S) ==
i := i - minIndex x
negative? i or empty?(x := rest(x,i::NonNegativeInteger)) =>
error "index out of range"
setfirst!(x, s)
setelt(x:%, i:UniversalSegment(Integer), s:S) ==
negative?(l := lo(i) - minIndex x) => error "index out of range"
h := if hasHi i then hi(i) - minIndex x else maxIndex x
h < l => s
y := rest(x, l::NonNegativeInteger)
z := rest(y, (h - l + 1)::NonNegativeInteger)
while not eq?(y, z) repeat (setfirst!(y, s); y := rest y)
s
concat!(x:%, y:%) ==
empty? x => y
setrest!(tail x, y)
x
@
\section{category LNAGG LinearAggregate}
<<category LNAGG LinearAggregate>>=
import Type
import Collection
import IndexedAggregate
import NonNegativeInteger
import Integer
)abbrev category LNAGG LinearAggregate
++ Author: Michael Monagan; revised by Manuel Bronstein and Richard Jenks
++ Date Created: August 87 through August 88
++ Date Last Updated: April 1991
++ Basic Operations:
++ Related Constructors:
++ Also See:
++ AMS Classifications:
++ Keywords:
++ References:
++ Description:
++ A linear aggregate is an aggregate whose elements are indexed by integers.
++ Examples of linear aggregates are strings, lists, and
++ arrays.
++ Most of the exported operations for linear aggregates are non-destructive
++ but are not always efficient for a particular aggregate.
++ For example, \spadfun{concat} of two lists needs only to copy its first
++ argument, whereas \spadfun{concat} of two arrays needs to copy both arguments.
++ Most of the operations exported here apply to infinite objects (e.g. streams)
++ as well to finite ones.
++ For finite linear aggregates, see \spadtype{FiniteLinearAggregate}.
LinearAggregate(S:Type): Category ==
Join(IndexedAggregate(Integer, S), Collection(S),_
Eltable(UniversalSegment Integer, %)) with
new : (NonNegativeInteger,S) -> %
++ new(n,x) returns \axiom{fill!(new n,x)}.
concat: (%,S) -> %
++ concat(u,x) returns aggregate u with additional element x at the end.
++ Note: for lists, \axiom{concat(u,x) == concat(u,[x])}
concat: (S,%) -> %
++ concat(x,u) returns aggregate u with additional element at the front.
++ Note: for lists: \axiom{concat(x,u) == concat([x],u)}.
concat: (%,%) -> %
++ concat(u,v) returns an aggregate consisting of the elements of u
++ followed by the elements of v.
++ Note: if \axiom{w = concat(u,v)} then \axiom{w.i = u.i for i in indices u}
++ and \axiom{w.(j + maxIndex u) = v.j for j in indices v}.
concat: List % -> %
++ concat(u), where u is a lists of aggregates \axiom{[a,b,...,c]}, returns
++ a single aggregate consisting of the elements of \axiom{a}
++ followed by those
++ of b followed ... by the elements of c.
++ Note: \axiom{concat(a,b,...,c) = concat(a,concat(b,...,c))}.
map: ((S,S)->S,%,%) -> %
++ map(f,u,v) returns a new collection w with elements \axiom{z = f(x,y)}
++ for corresponding elements x and y from u and v.
++ Note: for linear aggregates, \axiom{w.i = f(u.i,v.i)}.
delete: (%,Integer) -> %
++ delete(u,i) returns a copy of u with the \axiom{i}th element deleted.
++ Note: for lists, \axiom{delete(a,i) == concat(a(0..i - 1),a(i + 1,..))}.
delete: (%,UniversalSegment(Integer)) -> %
++ delete(u,i..j) returns a copy of u with the \axiom{i}th through
++ \axiom{j}th element deleted.
++ Note: \axiom{delete(a,i..j) = concat(a(0..i-1),a(j+1..))}.
insert: (S,%,Integer) -> %
++ insert(x,u,i) returns a copy of u having x as its \axiom{i}th element.
++ Note: \axiom{insert(x,a,k) = concat(concat(a(0..k-1),x),a(k..))}.
insert: (%,%,Integer) -> %
++ insert(v,u,k) returns a copy of u having v inserted beginning at the
++ \axiom{i}th element.
++ Note: \axiom{insert(v,u,k) = concat( u(0..k-1), v, u(k..) )}.
if % has ShallowlyMutableAggregate S then
setelt: (%,UniversalSegment(Integer),S) -> S
++ setelt(u,i..j,x) (also written: \axiom{u(i..j) := x}) destructively
++ replaces each element in the segment \axiom{u(i..j)} by x.
++ The value x is returned.
++ Note: u is destructively change so
++ that \axiom{u.k := x for k in i..j};
++ its length remains unchanged.
add
indices a == [i for i in minIndex a .. maxIndex a]
index?(i, a) == i >= minIndex a and i <= maxIndex a
concat(a:%, x:S) == concat(a, new(1, x))
concat(x:S, y:%) == concat(new(1, x), y)
insert(x:S, a:%, i:Integer) == insert(new(1, x), a, i)
if % has FiniteAggregate S then
maxIndex l == #l - 1 + minIndex l
--if % has ShallowlyMutableAggregate S then new(n, s) == fill!(new n, s)
@
\section{category FLAGG FiniteLinearAggregate}
<<category FLAGG FiniteLinearAggregate>>=
import Type
import SetCategory
import OrderedSet
import LinearAggregate
import Boolean
import Integer
)abbrev category FLAGG FiniteLinearAggregate
++ Author: Michael Monagan; revised by Manuel Bronstein and Richard Jenks
++ Date Created: August 87 through August 88
++ Date Last Updated: April 1991
++ Basic Operations:
++ Related Constructors:
++ Also See:
++ AMS Classifications:
++ Keywords:
++ References:
++ Description:
++ A finite linear aggregate is a linear aggregate of finite length.
++ The finite property of the aggregate adds several exports to the
++ list of exports from \spadtype{LinearAggregate} such as
++ \spadfun{reverse}, \spadfun{sort}, and so on.
FiniteLinearAggregate(S:Type): Category == Join(LinearAggregate S,FiniteAggregate S) with
merge: ((S,S)->Boolean,%,%) -> %
++ merge(p,a,b) returns an aggregate c which merges \axiom{a} and b.
++ The result is produced by examining each element x of \axiom{a} and y
++ of b successively. If \axiom{p(x,y)} is true, then x is inserted into
++ the result; otherwise y is inserted. If x is chosen, the next element
++ of \axiom{a} is examined, and so on. When all the elements of one
++ aggregate are examined, the remaining elements of the other
++ are appended.
++ For example, \axiom{merge(<,[1,3],[2,7,5])} returns \axiom{[1,2,3,7,5]}.
reverse: % -> %
++ reverse(a) returns a copy of \axiom{a} with elements in reverse order.
sort: ((S,S)->Boolean,%) -> %
++ sort(p,a) returns a copy of \axiom{a} sorted using total ordering predicate p.
sorted?: ((S,S)->Boolean,%) -> Boolean
++ sorted?(p,a) tests if \axiom{a} is sorted according to predicate p.
position: (S->Boolean, %) -> Integer
++ position(p,a) returns the index i of the first x in \axiom{a} such that
++ \axiom{p(x)} is true, and \axiom{minIndex(a) - 1} if there is no such x.
if S has BasicType then
position: (S, %) -> Integer
++ position(x,a) returns the index i of the first occurrence of x in a,
++ and \axiom{minIndex(a) - 1} if there is no such x.
position: (S,%,Integer) -> Integer
++ position(x,a,n) returns the index i of the first occurrence of x in
++ \axiom{a} where \axiom{i >= n}, and \axiom{minIndex(a) - 1} if no such x is found.
if S has OrderedSet then
OrderedSet
merge: (%,%) -> %
++ merge(u,v) merges u and v in ascending order.
++ Note: \axiom{merge(u,v) = merge(<=,u,v)}.
sort: % -> %
++ sort(u) returns an u with elements in ascending order.
++ Note: \axiom{sort(u) = sort(<=,u)}.
sorted?: % -> Boolean
++ sorted?(u) tests if the elements of u are in ascending order.
if % has ShallowlyMutableAggregate S then
copyInto!: (%,%,Integer) -> %
++ copyInto!(u,v,i) returns aggregate u containing a copy of
++ v inserted at element i.
reverse!: % -> %
++ reverse!(u) returns u with its elements in reverse order.
sort!: ((S,S)->Boolean,%) -> %
++ sort!(p,u) returns u with its elements ordered by p.
if S has OrderedSet then sort!: % -> %
++ sort!(u) returns u with its elements in ascending order.
add
if S has BasicType then
position(x:S, t:%) == position(x, t, minIndex t)
if S has OrderedSet then
-- sorted? l == sorted?(_<$S, l)
sorted? l == sorted?(#1 < #2 or #1 = #2, l)
merge(x, y) == merge(_<$S, x, y)
sort l == sort(_<$S, l)
if % has ShallowlyMutableAggregate S then
reverse x == reverse! copy x
sort(f, l) == sort!(f, copy l)
if S has OrderedSet then
sort! l == sort!(_<$S, l)
@
\section{category A1AGG OneDimensionalArrayAggregate}
<<category A1AGG OneDimensionalArrayAggregate>>=
import Type
import FiniteLinearAggregate
)abbrev category A1AGG OneDimensionalArrayAggregate
++ Author: Michael Monagan; revised by Manuel Bronstein and Richard Jenks
++ Date Created: August 87 through August 88
++ Date Last Updated: April 1991
++ Basic Operations:
++ Related Constructors:
++ Also See:
++ AMS Classifications:
++ Keywords:
++ References:
++ Description:
++ One-dimensional-array aggregates serves as models for one-dimensional arrays.
++ Categorically, these aggregates are finite linear aggregates
++ with the shallowly mutable property, that is, any component of
++ the array may be changed without affecting the
++ identity of the overall array.
++ Array data structures are typically represented by a fixed area in storage and
++ therefore cannot efficiently grow or shrink on demand as can list structures
++ (see however \spadtype{FlexibleArray} for a data structure which
++ is a cross between a list and an array).
++ Iteration over, and access to, elements of arrays is extremely fast
++ (and often can be optimized to open-code).
++ Insertion and deletion however is generally slow since an entirely new
++ data structure must be created for the result.
OneDimensionalArrayAggregate(S:Type): Category ==
Join(FiniteLinearAggregate S,ShallowlyMutableAggregate S)
add
members x == [qelt(x, i) for i in minIndex x .. maxIndex x]
sort!(f, a) == quickSort(f, a)$FiniteLinearAggregateSort(S, %)
any?(f, a) ==
for i in minIndex a .. maxIndex a repeat
f qelt(a, i) => return true
false
every?(f, a) ==
for i in minIndex a .. maxIndex a repeat
not(f qelt(a, i)) => return false
true
position(f:S -> Boolean, a:%) ==
for i in minIndex a .. maxIndex a repeat
f qelt(a, i) => return i
minIndex(a) - 1
find(f, a) ==
for i in minIndex a .. maxIndex a repeat
f qelt(a, i) => return qelt(a, i)
"failed"
count(f:S->Boolean, a:%) ==
n:NonNegativeInteger := 0
for i in minIndex a .. maxIndex a repeat
if f(qelt(a, i)) then n := n+1
n
map!(f, a) ==
for i in minIndex a .. maxIndex a repeat
qsetelt!(a, i, f qelt(a, i))
a
setelt(a:%, s:UniversalSegment(Integer), x:S) ==
l := lo s; h := if hasHi s then hi s else maxIndex a
l < minIndex a or h > maxIndex a => error "index out of range"
for k in l..h repeat qsetelt!(a, k, x)
x
reduce(f, a) ==
empty? a => error "cannot reduce an empty aggregate"
r := qelt(a, m := minIndex a)
for k in m+1 .. maxIndex a repeat r := f(r, qelt(a, k))
r
reduce(f, a, identity) ==
for k in minIndex a .. maxIndex a repeat
identity := f(identity, qelt(a, k))
identity
if S has BasicType then
reduce(f, a, identity,absorber) ==
for k in minIndex a .. maxIndex a while identity ~= absorber
repeat identity := f(identity, qelt(a, k))
identity
-- this is necessary since new has disappeared.
stupidnew: (NonNegativeInteger, %, %) -> %
stupidget: List % -> S
-- a and b are not both empty if n > 0
stupidnew(n, a, b) ==
zero? n => empty()
new(n, (empty? a => qelt(b, minIndex b); qelt(a, minIndex a)))
-- at least one element of l must be non-empty
stupidget l ==
for a in l repeat
not empty? a => return first a
error "Should not happen"
map(f, a, b) ==
m := max(minIndex a, minIndex b)
n := min(maxIndex a, maxIndex b)
l := max(0, n - m + 1)::NonNegativeInteger
c := stupidnew(l, a, b)
for i in minIndex(c).. for j in m..n repeat
qsetelt!(c, i, f(qelt(a, j), qelt(b, j)))
c
-- map(f, a, b, x) ==
-- m := min(minIndex a, minIndex b)
-- n := max(maxIndex a, maxIndex b)
-- l := (n - m + 1)::NonNegativeInteger
-- c := new l
-- for i in minIndex(c).. for j in m..n repeat
-- qsetelt!(c, i, f(a(j, x), b(j, x)))
-- c
merge(f, a, b) ==
r := stupidnew(#a + #b, a, b)
i := minIndex a
m := maxIndex a
j := minIndex b
n := maxIndex b
k := minIndex(r)
while i <= m and j <= n repeat
if f(qelt(a, i), qelt(b, j)) then
qsetelt!(r, k, qelt(a, i))
i := i+1
else
qsetelt!(r, k, qelt(b, j))
j := j+1
k := k + 1
while i <= m repeat
qsetelt!(r, k, elt(a, i))
k := k + 1
i := i + 1
while j <= n repeat
qsetelt!(r, k, elt(b, j))
k := k + 1
j := j + 1
r
elt(a:%, s:UniversalSegment(Integer)) ==
l := lo s
h := if hasHi s then hi s else maxIndex a
l < minIndex a or h > maxIndex a => error "index out of range"
r := stupidnew(max(0, h - l + 1)::NonNegativeInteger, a, a)
for k in minIndex r.. for i in l..h repeat
qsetelt!(r, k, qelt(a, i))
r
insert(a:%, b:%, i:Integer) ==
m := minIndex b
n := maxIndex b
i < m or i > n => error "index out of range"
y := stupidnew(#a + #b, a, b)
k := minIndex y
for j in m..i-1 repeat
qsetelt!(y, k, qelt(b, j))
k := k + 1
for j in minIndex a .. maxIndex a repeat
qsetelt!(y, k, qelt(a, j))
k := k + 1
for j in i..n repeat
qsetelt!(y, k, qelt(b, j))
k := k + 1
y
copy x ==
y := stupidnew(#x, x, x)
for i in minIndex x .. maxIndex x for j in minIndex y .. repeat
qsetelt!(y, j, qelt(x, i))
y
copyInto!(y, x, s) ==
s < minIndex y or s + #x > maxIndex y + 1 =>
error "index out of range"
for i in minIndex x .. maxIndex x for j in s.. repeat
qsetelt!(y, j, qelt(x, i))
y
construct l ==
-- a := new(#l)
empty? l => empty()
a := new(#l, first l)
for i in minIndex(a).. for x in l repeat qsetelt!(a, i, x)
a
delete(a:%, s:UniversalSegment(Integer)) ==
l := lo s; h := if hasHi s then hi s else maxIndex a
l < minIndex a or h > maxIndex a => error "index out of range"
h < l => copy a
r := stupidnew((#a - h + l - 1)::NonNegativeInteger, a, a)
k := minIndex(r)
for i in minIndex a..l-1 repeat
qsetelt!(r, k, qelt(a, i))
k := k + 1
for i in h+1 .. maxIndex a repeat
qsetelt!(r, k, qelt(a, i))
k := k + 1
r
delete(x:%, i:Integer) ==
i < minIndex x or i > maxIndex x => error "index out of range"
y := stupidnew((#x - 1)::NonNegativeInteger, x, x)
k := minIndex y
for j in minIndex x..i-1 repeat
qsetelt!(y, k, qelt(x, j))
k := k + 1
for j in i+1 .. maxIndex x repeat
qsetelt!(y, k, qelt(x, j))
k := k + 1
y
reverse! x ==
m := minIndex x
n := maxIndex x
for i in 0..((n-m) quo 2) repeat swap!(x, m+i, n-i)
x
concat l ==
empty? l => empty()
n := +/[#a for a in l]
i := minIndex(r := new(n, stupidget l))
for a in l repeat
copyInto!(r, a, i)
i := i + #a
r
sorted?(f, a) ==
for i in minIndex(a)..maxIndex(a)-1 repeat
not f(qelt(a, i), qelt(a, i + 1)) => return false
true
concat(x:%, y:%) ==
z := stupidnew(#x + #y, x, y)
copyInto!(z, x, i := minIndex z)
copyInto!(z, y, i + #x)
z
if S has CoercibleTo(OutputForm) then
coerce(r:%):OutputForm ==
bracket commaSeparate
[qelt(r, k)::OutputForm for k in minIndex r .. maxIndex r]
if S has BasicType then
x = y ==
#x ~= #y => false
for i in minIndex x .. maxIndex x repeat
not(qelt(x, i) = qelt(y, i)) => return false
true
position(x:S, t:%, s:Integer) ==
n := maxIndex t
s < minIndex t or s > n => error "index out of range"
for k in s..n repeat
qelt(t, k) = x => return k
minIndex(t) - 1
if S has OrderedSet then
a < b ==
for i in minIndex a .. maxIndex a
for j in minIndex b .. maxIndex b repeat
qelt(a, i) ~= qelt(b, j) => return a.i < b.j
#a < #b
@
\section{category ELAGG ExtensibleLinearAggregate}
<<category ELAGG ExtensibleLinearAggregate>>=
import Type
import LinearAggregate
import OrderedSet
import Integer
)abbrev category ELAGG ExtensibleLinearAggregate
++ Author: Michael Monagan; revised by Manuel Bronstein and Richard Jenks
++ Date Created: August 87 through August 88
++ Date Last Updated: April 1991
++ Basic Operations:
++ Related Constructors:
++ Also See:
++ AMS Classifications:
++ Keywords:
++ References:
++ Description:
++ An extensible aggregate is one which allows insertion and deletion of entries.
++ These aggregates are models of lists and streams which are represented
++ by linked structures so as to make insertion, deletion, and
++ concatenation efficient. However, access to elements of these
++ extensible aggregates is generally slow since access is made from the end.
++ See \spadtype{FlexibleArray} for an exception.
ExtensibleLinearAggregate(S:Type):Category == Join(LinearAggregate S,ShallowlyMutableAggregate S) with
concat!: (%,S) -> %
++ concat!(u,x) destructively adds element x to the end of u.
concat!: (%,%) -> %
++ concat!(u,v) destructively appends v to the end of u.
++ v is unchanged
delete!: (%,Integer) -> %
++ delete!(u,i) destructively deletes the \axiom{i}th element of u.
delete!: (%,UniversalSegment(Integer)) -> %
++ delete!(u,i..j) destructively deletes elements u.i through u.j.
remove!: (S->Boolean,%) -> %
++ remove!(p,u) destructively removes all elements x of
++ u such that \axiom{p(x)} is true.
insert!: (S,%,Integer) -> %
++ insert!(x,u,i) destructively inserts x into u at position i.
insert!: (%,%,Integer) -> %
++ insert!(v,u,i) destructively inserts aggregate v into u at position i.
merge!: ((S,S)->Boolean,%,%) -> %
++ merge!(p,u,v) destructively merges u and v using predicate p.
select!: (S->Boolean,%) -> %
++ select!(p,u) destructively changes u by keeping only values x such that
++ \axiom{p(x)}.
if S has BasicType then
remove!: (S,%) -> %
++ remove!(x,u) destructively removes all values x from u.
removeDuplicates!: % -> %
++ removeDuplicates!(u) destructively removes duplicates from u.
if S has OrderedSet then merge!: (%,%) -> %
++ merge!(u,v) destructively merges u and v in ascending order.
add
delete(x:%, i:Integer) == delete!(copy x, i)
delete(x:%, i:UniversalSegment(Integer)) == delete!(copy x, i)
remove(f:S -> Boolean, x:%) == remove!(f, copy x)
insert(s:S, x:%, i:Integer) == insert!(s, copy x, i)
insert(w:%, x:%, i:Integer) == insert!(copy w, copy x, i)
select(f, x) == select!(f, copy x)
concat(x:%, y:%) == concat!(copy x, y)
concat(x:%, y:S) == concat!(copy x, new(1, y))
concat!(x:%, y:S) == concat!(x, new(1, y))
if S has BasicType then
remove(s:S, x:%) == remove!(s, copy x)
remove!(s:S, x:%) == remove!(#1 = s, x)
removeDuplicates(x:%) == removeDuplicates!(copy x)
if S has OrderedSet then
merge!(x, y) == merge!(_<$S, x, y)
@
\section{category LSAGG ListAggregate}
<<category LSAGG ListAggregate>>=
import Type
import StreamAggregate
import FiniteLinearAggregate
import ExtensibleLinearAggregate
)abbrev category LSAGG ListAggregate
++ Author: Michael Monagan; revised by Manuel Bronstein and Richard Jenks
++ Date Created: August 87 through August 88
++ Date Last Updated: April 1991
++ Basic Operations:
++ Related Constructors:
++ Also See:
++ AMS Classifications:
++ Keywords:
++ References:
++ Description:
++ A list aggregate is a model for a linked list data structure.
++ A linked list is a versatile
++ data structure. Insertion and deletion are efficient and
++ searching is a linear operation.
ListAggregate(S:Type): Category == Join(StreamAggregate S,
FiniteLinearAggregate S, ExtensibleLinearAggregate S) with
list: S -> %
++ list(x) returns the list of one element x.
add
cycleMax ==> 1000
mergeSort: ((S, S) -> Boolean, %, Integer) -> %
sort!(f, l) == mergeSort(f, l, #l)
list x == concat(x, empty())
reduce(f, x) ==
empty? x => error "reducing over an empty list needs the 3 argument form"
reduce(f, rest x, first x)
merge(f, p, q) == merge!(f, copy p, copy q)
select!(f, x) ==
while not empty? x and not f first x repeat x := rest x
empty? x => x
y := x
z := rest y
while not empty? z repeat
if f first z then (y := z; z := rest z)
else (z := rest z; setrest!(y, z))
x
merge!(f, p, q) ==
empty? p => q
empty? q => p
eq?(p, q) => error "cannot merge a list into itself"
r: %
t: %
if f(first p, first q)
then (r := t := p; p := rest p)
else (r := t := q; q := rest q)
while not empty? p and not empty? q repeat
if f(first p, first q)
then (setrest!(t, p); t := p; p := rest p)
else (setrest!(t, q); t := q; q := rest q)
setrest!(t, if empty? p then q else p)
r
insert!(s:S, x:%, i:Integer) ==
i < (m := minIndex x) => error "index out of range"
i = m => concat(s, x)
y := rest(x, (i - 1 - m)::NonNegativeInteger)
z := rest y
setrest!(y, concat(s, z))
x
insert!(w:%, x:%, i:Integer) ==
i < (m := minIndex x) => error "index out of range"
i = m => concat!(w, x)
y := rest(x, (i - 1 - m)::NonNegativeInteger)
z := rest y
setrest!(y, w)
concat!(y, z)
x
remove!(f:S -> Boolean, x:%) ==
while not empty? x and f first x repeat x := rest x
empty? x => x
p := x
q := rest x
while not empty? q repeat
if f first q then q := setrest!(p, rest q)
else (p := q; q := rest q)
x
delete!(x:%, i:Integer) ==
i < (m := minIndex x) => error "index out of range"
i = m => rest x
y := rest(x, (i - 1 - m)::NonNegativeInteger)
setrest!(y, rest(y, 2))
x
delete!(x:%, i:UniversalSegment(Integer)) ==
(l := lo i) < (m := minIndex x) => error "index out of range"
h := if hasHi i then hi i else maxIndex x
h < l => x
l = m => rest(x, (h + 1 - m)::NonNegativeInteger)
t := rest(x, (l - 1 - m)::NonNegativeInteger)
setrest!(t, rest(t, (h - l + 2)::NonNegativeInteger))
x
find(f, x) ==
while not empty? x and not f first x repeat x := rest x
empty? x => "failed"
first x
position(f:S -> Boolean, x:%) ==
k := minIndex(x)
while not empty? x and not f first x repeat
x := rest x
k := k + 1
empty? x => minIndex(x) - 1
k
mergeSort(f, p, n) ==
if n = 2 and f(first rest p, first p) then p := reverse! p
n < 3 => p
l := (n quo 2)::NonNegativeInteger
q := split!(p, l)
p := mergeSort(f, p, l)
q := mergeSort(f, q, n - l)
merge!(f, p, q)
sorted?(f, l) ==
empty? l => true
p := rest l
while not empty? p repeat
not f(first l, first p) => return false
p := rest(l := p)
true
reduce(f, x, i) ==
r := i
while not empty? x repeat (r := f(r, first x); x := rest x)
r
if S has BasicType then
reduce(f, x, i,a) ==
r := i
while not empty? x and r ~= a repeat
r := f(r, first x)
x := rest x
r
new(n, s) ==
l := empty()
for k in 1..n repeat l := concat(s, l)
l
map(f, x, y) ==
z := empty()
while not empty? x and not empty? y repeat
z := concat(f(first x, first y), z)
x := rest x
y := rest y
reverse! z
-- map(f, x, y, d) ==
-- z := empty()
-- while not empty? x and not empty? y repeat
-- z := concat(f(first x, first y), z)
-- x := rest x
-- y := rest y
-- z := reverseInPlace z
-- if not empty? x then
-- z := concat!(z, map(f(#1, d), x))
-- if not empty? y then
-- z := concat!(z, map(f(d, #1), y))
-- z
reverse! x ==
empty? x => x
empty?(y := rest x) => x
setrest!(x, empty())
while not empty? y repeat
z := rest y
setrest!(y, x)
x := y
y := z
x
copy x ==
y := empty()
for k in 0.. while not empty? x repeat
k = cycleMax and cyclic? x => error "cyclic list"
y := concat(first x, y)
x := rest x
reverse! y
copyInto!(y, x, s) ==
s < (m := minIndex y) => error "index out of range"
z := rest(y, (s - m)::NonNegativeInteger)
while not empty? z and not empty? x repeat
setfirst!(z, first x)
x := rest x
z := rest z
y
if S has BasicType then
position(w, x, s) ==
s < (m := minIndex x) => error "index out of range"
x := rest(x, (s - m)::NonNegativeInteger)
k := s
while not empty? x and w ~= first x repeat
x := rest x
k := k + 1
empty? x => minIndex x - 1
k
removeDuplicates! l ==
p := l
while not empty? p repeat
p := setrest!(p, remove!(#1 = first p, rest p))
l
if S has OrderedSet then
x < y ==
while not empty? x and not empty? y repeat
first x ~= first y => return(first x < first y)
x := rest x
y := rest y
empty? x => not empty? y
false
@
\section{category ALAGG AssociationListAggregate}
<<category ALAGG AssociationListAggregate>>=
import SetCategory
import TableAggregate
import ListAggregate
)abbrev category ALAGG AssociationListAggregate
++ Author: Michael Monagan; revised by Manuel Bronstein and Richard Jenks
++ Date Created: August 87 through August 88
++ Date Last Updated: April 1991
++ Basic Operations:
++ Related Constructors:
++ Also See:
++ AMS Classifications:
++ Keywords:
++ References:
++ Description:
++ An association list is a list of key entry pairs which may be viewed
++ as a table. It is a poor mans version of a table:
++ searching for a key is a linear operation.
AssociationListAggregate(Key:SetCategory,Entry:SetCategory): Category ==
Join(TableAggregate(Key, Entry),ListAggregate Record(key:Key,entry:Entry),_
ShallowlyMutableAggregate Entry) with
assoc: (Key, %) -> Maybe Record(key:Key,entry:Entry)
++ assoc(k,u) returns the element x in association list u stored
++ with key k, or \spad{nothing} if u has no key k.
@
\section{category SRAGG StringAggregate}
<<category SRAGG StringAggregate>>=
import OneDimensionalArrayAggregate Character
import UniversalSegment
import Boolean
import Character
import CharacterClass
import Integer
)abbrev category SRAGG StringAggregate
++ Author: Stephen Watt and Michael Monagan. revised by Manuel Bronstein and Richard Jenks
++ Date Created: August 87 through August 88
++ Date Last Updated: April 1991
++ Basic Operations:
++ Related Constructors:
++ Also See:
++ AMS Classifications:
++ Keywords:
++ References:
++ Description:
++ A string aggregate is a category for strings, that is,
++ one dimensional arrays of characters.
StringAggregate: Category == OneDimensionalArrayAggregate Character with
lowerCase : % -> %
++ lowerCase(s) returns the string with all characters in lower case.
lowerCase!: % -> %
++ lowerCase!(s) destructively replaces the alphabetic characters
++ in s by lower case.
upperCase : % -> %
++ upperCase(s) returns the string with all characters in upper case.
upperCase!: % -> %
++ upperCase!(s) destructively replaces the alphabetic characters
++ in s by upper case characters.
prefix? : (%, %) -> Boolean
++ prefix?(s,t) tests if the string s is the initial substring of t.
++ Note: \axiom{prefix?(s,t) == reduce(and,[s.i = t.i for i in 0..maxIndex s])}.
suffix? : (%, %) -> Boolean
++ suffix?(s,t) tests if the string s is the final substring of t.
++ Note: \axiom{suffix?(s,t) == reduce(and,[s.i = t.(n - m + i) for i in 0..maxIndex s])}
++ where m and n denote the maxIndex of s and t respectively.
substring?: (%, %, Integer) -> Boolean
++ substring?(s,t,i) tests if s is a substring of t beginning at
++ index i.
++ Note: \axiom{substring?(s,t,0) = prefix?(s,t)}.
match: (%, %, Character) -> NonNegativeInteger
++ match(p,s,wc) tests if pattern \axiom{p} matches subject \axiom{s}
++ where \axiom{wc} is a wild card character. If no match occurs,
++ the index \axiom{0} is returned; otheriwse, the value returned
++ is the first index of the first character in the subject matching
++ the subject (excluding that matched by an initial wild-card).
++ For example, \axiom{match("*to*","yorktown","*")} returns \axiom{5}
++ indicating a successful match starting at index \axiom{5} of
++ \axiom{"yorktown"}.
match?: (%, %, Character) -> Boolean
++ match?(s,t,c) tests if s matches t except perhaps for
++ multiple and consecutive occurrences of character c.
++ Typically c is the blank character.
replace : (%, UniversalSegment(Integer), %) -> %
++ replace(s,i..j,t) replaces the substring \axiom{s(i..j)} of s by string t.
position : (%, %, Integer) -> Integer
++ position(s,t,i) returns the position j of the substring s in string t,
++ where \axiom{j >= i} is required.
position : (CharacterClass, %, Integer) -> Integer
++ position(cc,t,i) returns the position \axiom{j >= i} in t of
++ the first character belonging to cc.
coerce : Character -> %
++ coerce(c) returns c as a string s with the character c.
split: (%, Character) -> List %
++ split(s,c) returns a list of substrings delimited by character c.
split: (%, CharacterClass) -> List %
++ split(s,cc) returns a list of substrings delimited by characters in cc.
trim: (%, Character) -> %
++ trim(s,c) returns s with all characters c deleted from right
++ and left ends.
++ For example, \axiom{trim(" abc ", char " ")} returns \axiom{"abc"}.
trim: (%, CharacterClass) -> %
++ trim(s,cc) returns s with all characters in cc deleted from right
++ and left ends.
++ For example, \axiom{trim("(abc)", charClass "()")} returns \axiom{"abc"}.
leftTrim: (%, Character) -> %
++ leftTrim(s,c) returns s with all leading characters c deleted.
++ For example, \axiom{leftTrim(" abc ", char " ")} returns \axiom{"abc "}.
leftTrim: (%, CharacterClass) -> %
++ leftTrim(s,cc) returns s with all leading characters in cc deleted.
++ For example, \axiom{leftTrim("(abc)", charClass "()")} returns \axiom{"abc)"}.
rightTrim: (%, Character) -> %
++ rightTrim(s,c) returns s with all trailing occurrences of c deleted.
++ For example, \axiom{rightTrim(" abc ", char " ")} returns \axiom{" abc"}.
rightTrim: (%, CharacterClass) -> %
++ rightTrim(s,cc) returns s with all trailing occurences of
++ characters in cc deleted.
++ For example, \axiom{rightTrim("(abc)", charClass "()")} returns \axiom{"(abc"}.
elt: (%, %) -> %
++ elt(s,t) returns the concatenation of s and t. It is provided to
++ allow juxtaposition of strings to work as concatenation.
++ For example, \axiom{"smoo" "shed"} returns \axiom{"smooshed"}.
add
trim(s: %, c: Character) == leftTrim(rightTrim(s, c), c)
trim(s: %, cc: CharacterClass) == leftTrim(rightTrim(s, cc), cc)
lowerCase s == lowerCase! copy s
upperCase s == upperCase! copy s
prefix?(s, t) == substring?(s, t, minIndex t)
coerce(c:Character):% == new(1, c)
elt(s:%, t:%): % == concat(s,t)$%
@
\section{category BTAGG BitAggregate}
<<category BTAGG BitAggregate>>=
import OrderedSet
import Logic
import OneDimensionalArrayAggregate Boolean
)abbrev category BTAGG BitAggregate
++ Author: Michael Monagan; revised by Manuel Bronstein and Richard Jenks
++ Date Created: August 87 through August 88
++ Date Last Updated: April 1991
++ Basic Operations:
++ Related Constructors:
++ Also See:
++ AMS Classifications:
++ Keywords:
++ References:
++ Description:
++ The bit aggregate category models aggregates representing large
++ quantities of Boolean data.
BitAggregate(): Category ==
Join(OrderedSet, BooleanLogic, Logic, OneDimensionalArrayAggregate Boolean) with
nand : (%, %) -> %
++ nand(a,b) returns the logical {\em nand} of bit aggregates \axiom{a}
++ and \axiom{b}.
nor : (%, %) -> %
++ nor(a,b) returns the logical {\em nor} of bit aggregates \axiom{a} and
++ \axiom{b}.
xor : (%, %) -> %
++ xor(a,b) returns the logical {\em exclusive-or} of bit aggregates
++ \axiom{a} and \axiom{b}.
add
not v == map(_not, v)
~ v == map(_~, v)
v /\ u == map(_/_\, v, u)
v \/ u == map(_\_/, v, u)
nand(v, u) == map(nand, v, u)
nor(v, u) == map(nor, v, u)
@
\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>>
<<category AGG Aggregate>>
<<category HOAGG HomogeneousAggregate>>
<<category SMAGG ShallowlyMutableAggregate>>
<<category FINAGG FiniteAggregate>>
<<category CLAGG Collection>>
<<category BGAGG BagAggregate>>
<<category SKAGG StackAggregate>>
<<category QUAGG QueueAggregate>>
<<category DQAGG DequeueAggregate>>
<<category PRQAGG PriorityQueueAggregate>>
<<category DIOPS DictionaryOperations>>
<<category DIAGG Dictionary>>
<<category MDAGG MultiDictionary>>
<<category SETAGG SetAggregate>>
<<category FSAGG FiniteSetAggregate>>
<<category MSETAGG MultisetAggregate>>
<<category OMSAGG OrderedMultisetAggregate>>
<<category KDAGG KeyedDictionary>>
<<category ELTAB Eltable>>
<<category ELTAGG EltableAggregate>>
<<category IXAGG IndexedAggregate>>
<<category TBAGG TableAggregate>>
<<category RCAGG RecursiveAggregate>>
<<category BRAGG BinaryRecursiveAggregate>>
<<category DLAGG DoublyLinkedAggregate>>
<<category URAGG UnaryRecursiveAggregate>>
<<category STAGG StreamAggregate>>
<<category LNAGG LinearAggregate>>
<<category FLAGG FiniteLinearAggregate>>
<<category A1AGG OneDimensionalArrayAggregate>>
<<category ELAGG ExtensibleLinearAggregate>>
<<category LSAGG ListAggregate>>
<<category ALAGG AssociationListAggregate>>
<<category SRAGG StringAggregate>>
<<category BTAGG BitAggregate>>
@
\eject
\begin{thebibliography}{99}
\bibitem{1} nothing
\end{thebibliography}
\end{document}