Initial population.

1 files changed, 329 insertions, 0 deletions

diff --git a/src/algebra/bags.spad.pamphlet b/src/algebra/bags.spad.pamphlet
new file mode 100644
index 00000000..8e1c3356
--- /dev/null
+++ b/src/algebra/bags.spad.pamphlet
@@ -0,0 +1,329 @@
+\documentclass{article}
+\usepackage{axiom}
+\begin{document}
+\title{\$SPAD/src/algebra bags.spad}
+\author{Michael Monagan, Stephen Watt}
+\maketitle
+\begin{abstract}
+\end{abstract}
+\eject
+\tableofcontents
+\eject
+\section{domain STACK Stack}
+<<domain STACK Stack>>=
+)abbrev domain STACK Stack
+++ Author: Michael Monagan and Stephen Watt
+++ Date Created:June 86 and July 87
+++ Date Last Updated:Feb 92
+++ Basic Operations:
+++ Related Domains:
+++ Also See:
+++ AMS Classifications:
+++ Keywords:
+++ Examples:
+++ References:
+++ Description:
+ 
+++ Linked List implementation of a Stack
+--% Dequeue and Heap data types
+ 
+Stack(S:SetCategory): StackAggregate S with
+    stack: List S -> %
+      ++ stack([x,y,...,z]) creates a stack with first (top)
+      ++ element x, second element y,...,and last element z.
+  == add
+    Rep := Reference List S
+    s = t == deref s = deref t
+    coerce(d:%): OutputForm == bracket [e::OutputForm for e in deref d]
+    copy s == ref copy deref s
+    depth s == # deref s
+    # s == depth s
+    pop_! (s:%):S ==
+        empty? s => error "empty stack"
+        e := first deref s
+        setref(s,rest deref s)
+        e
+    extract_! (s:%):S == pop_! s
+    top (s:%):S ==
+        empty? s => error "empty stack"
+        first deref s
+    inspect s == top s
+    push_!(e,s) == (setref(s,cons(e,deref s));e)
+    insert_!(e:S,s:%):% == (push_!(e,s);s)
+    empty() == ref nil()$List(S)
+    empty? s == null deref s
+    stack s == ref copy s
+
+@
+\section{domain ASTACK ArrayStack}
+<<domain ASTACK ArrayStack>>=
+)abbrev domain ASTACK ArrayStack
+++ Author: Michael Monagan and Stephen Watt
+++ Date Created:June 86 and July 87
+++ Date Last Updated:Feb 92
+++ Basic Operations:
+++ Related Domains:
+++ Also See:
+++ AMS Classifications:
+++ Keywords:
+++ Examples:
+++ References:
+++ Description:
+ 
+++ A stack represented as a flexible array.
+--% Dequeue and Heap data types
+ 
+ArrayStack(S:SetCategory): StackAggregate(S) with
+    arrayStack: List S -> %
+      ++ arrayStack([x,y,...,z]) creates an array stack with first (top)
+      ++ element x, second element y,...,and last element z.
+  == add
+    Rep := IndexedFlexibleArray(S,0)
+ 
+    -- system operations
+    # s == _#(s)$Rep
+    s = t == s =$Rep t
+    copy s == copy(s)$Rep
+    coerce(d):OutputForm ==
+        empty? d => empty()$(List S) ::OutputForm
+        [(d.i::OutputForm) for i in 0..#d-1] ::OutputForm
+ 
+    -- stack operations
+    depth s == # s
+    empty? s == empty?(s)$Rep 
+    extract_! s == pop_! s
+    insert_!(e,s) == (push_!(e,s);s)
+    push_!(e,s) == (concat(e,s); e)
+    pop_! s ==
+        if empty? s then error "empty stack"
+        m := maxIndex s
+        r := s.m
+        delete_!(s,m)
+        r
+    top s == if empty? s then error "empty stack" else s.maxIndex(s)
+    arrayStack l == construct(l)$Rep
+    empty() == new(0,0 pretend S)
+
+@
+\section{domain QUEUE Queue}
+<<domain QUEUE Queue>>=
+)abbrev domain QUEUE Queue
+++ Author: Michael Monagan and Stephen Watt
+++ Date Created:June 86 and July 87
+++ Date Last Updated:Feb 92
+++ Basic Operations:
+++ Related Domains:
+++ Also See:
+++ AMS Classifications:
+++ Keywords:
+++ Examples:
+++ References:
+++ Description:
+ 
+++ Linked List implementation of a Queue
+--% Dequeue and Heap data types
+ 
+Queue(S:SetCategory): QueueAggregate S with
+    queue: List S -> %
+      ++ queue([x,y,...,z]) creates a queue with first (top)
+      ++ element x, second element y,...,and last (bottom) element z.
+  == Stack S add
+    Rep := Reference List S
+    lastTail==> LAST$Lisp
+    enqueue_!(e,q) ==
+        if null deref q then setref(q, list e)
+        else lastTail.(deref q).rest := list e
+        e
+    insert_!(e,q) == (enqueue_!(e,q);q)
+    dequeue_! q ==
+        empty? q => error "empty queue"
+        e := first deref q
+        setref(q,rest deref q)
+        e
+    extract_! q == dequeue_! q
+    rotate_! q == if empty? q then q else (enqueue_!(dequeue_! q,q); q)
+    length q == # deref q
+    front q == if empty? q then error "empty queue" else first deref q
+    inspect q == front q
+    back q == if empty? q then error "empty queue" else last deref q
+    queue q == ref copy q
+
+@
+\section{domain DEQUEUE Dequeue}
+<<domain DEQUEUE Dequeue>>=
+)abbrev domain DEQUEUE Dequeue
+++ Author: Michael Monagan and Stephen Watt
+++ Date Created:June 86 and July 87
+++ Date Last Updated:Feb 92
+++ Basic Operations:
+++ Related Domains:
+++ Also See:
+++ AMS Classifications:
+++ Keywords:
+++ Examples:
+++ References:
+++ Description:
+ 
+++ Linked list implementation of a Dequeue
+--% Dequeue and Heap data types
+ 
+Dequeue(S:SetCategory): DequeueAggregate S with
+     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.
+  == Queue S add
+    Rep := Reference List S
+    bottom_! d ==
+         if empty? d then error "empty dequeue" else last deref d
+    dequeue d == ref copy d
+    extractBottom_! d ==
+        if empty? d then error "empty dequeue"
+        p := deref d
+        n := maxIndex p
+        n = 1 =>
+           r := first p
+           setref(d,[])
+           r
+        q := rest(p,(n-2)::NonNegativeInteger)
+        r := first rest q
+        q.rest := []
+        r
+    extractTop_! d ==
+        e := top d
+        setref(d,rest deref d)
+        e
+    height d == # deref d
+    insertTop_!(e,d) == (setref(d,cons(e,deref d)); e)
+    lastTail==> LAST$Lisp
+    insertBottom_!(e,d) ==
+        if empty? d then setref(d, list e)
+        else lastTail.(deref d).rest := list e
+        e
+    top d == if empty? d then error "empty dequeue" else first deref d
+    reverse_! d == (setref(d,reverse deref d); d)
+
+@
+\section{domain HEAP Heap}
+<<domain HEAP Heap>>=
+)abbrev domain HEAP Heap
+++ Author: Michael Monagan and Stephen Watt
+++ Date Created:June 86 and July 87
+++ Date Last Updated:Feb 92
+++ Basic Operations:
+++ Related Domains:
+++ Also See:
+++ AMS Classifications:
+++ Keywords:
+++ Examples:
+++ References:
+++ Description:
+ 
+++ Heap implemented in a flexible array to allow for insertions
+++ Complexity: O(log n) insertion, extraction and O(n) construction
+--% Dequeue and Heap data types
+ 
+Heap(S:OrderedSet): Exports == Implementation where 
+  Exports == PriorityQueueAggregate S with
+    heap : List S -> %
+      ++ heap(ls) creates a heap of elements consisting of the 
+      ++ elements of ls.
+  Implementation == IndexedFlexibleArray(S,0) add
+    Rep := IndexedFlexibleArray( S,0)
+    empty() == empty()$Rep
+    heap l == 
+      n := #l
+      h := empty()
+      n = 0 => h
+      for x in l repeat insert_!(x,h)
+      h
+    siftUp: (%,Integer,Integer) -> Void
+    siftUp(r,i,n) ==
+       -- assertion 0 <= i < n
+       t := r.i
+       while (j := 2*i+1) < n repeat
+          if (k := j+1) < n and r.j < r.k then j := k
+          if t < r.j then (r.i := r.j; r.j := t; i := j) else leave
+ 
+    extract_! r ==
+       -- extract the maximum from the heap O(log n)
+       n := #r :: Integer
+       n = 0 => error "empty heap"
+       t := r(0)
+       r(0) := r(n-1)
+       delete_!(r,n-1)
+       n = 1 => t
+       siftUp(r,0,n-1)
+       t
+ 
+    insert_!(x,r) ==
+       -- Williams' insertion algorithm O(log n)
+       j := (#r) :: Integer
+       r:=concat_!(r,concat(x,empty()$Rep))
+       while j > 0 repeat
+          i := (j-1) quo 2
+          if r(i) >= x then leave
+          r(j) := r(i)
+          j := i
+       r(j):=x
+       r
+ 
+    max r == if #r = 0 then error "empty heap" else r.0
+    inspect r == max r
+ 
+    makeHeap(r:%):% ==
+       -- Floyd's heap construction algorithm O(n)
+       n := #r
+       for k in n quo 2 -1 .. 0 by -1 repeat siftUp(r,k,n)
+       r
+    bag l == makeHeap construct(l)$Rep
+    merge(a,b) == makeHeap concat(a,b)
+    merge_!(a,b) == makeHeap concat_!(a,b)
+
+@
+\section{License}
+<<license>>=
+--Copyright (c) 1991-2002, The Numerical ALgorithms Group Ltd.
+--All rights reserved.
+--
+--Redistribution and use in source and binary forms, with or without
+--modification, are permitted provided that the following conditions are
+--met:
+--
+--    - Redistributions of source code must retain the above copyright
+--      notice, this list of conditions and the following disclaimer.
+--
+--    - Redistributions in binary form must reproduce the above copyright
+--      notice, this list of conditions and the following disclaimer in
+--      the documentation and/or other materials provided with the
+--      distribution.
+--
+--    - Neither the name of The Numerical ALgorithms Group Ltd. nor the
+--      names of its contributors may be used to endorse or promote products
+--      derived from this software without specific prior written permission.
+--
+--THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
+--IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+--TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
+--PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
+--OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+--EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+--PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+--PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+--LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+--NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+--SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+@
+<<*>>=
+<<license>>
+ 
+<<domain STACK Stack>>
+<<domain ASTACK ArrayStack>>
+<<domain QUEUE Queue>>
+<<domain DEQUEUE Dequeue>>
+<<domain HEAP Heap>>
+@
+\eject
+\begin{thebibliography}{99}
+\bibitem{1} nothing
+\end{thebibliography}
+\end{document}