path: root/src/algebra/bags.spad.pamphlet

\documentclass{article}
\usepackage{open-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: December 02, 2007
++ 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: Type): 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

    if S has CoercibleTo OutputForm then
      coerce(d:%): OutputForm == 
        bracket [e::OutputForm for e in deref d]

    if S has SetCategory then
      s = t == 
        deref s = deref t

    members s ==                             -- from HOAGG
      deref s
   
    map(f: S -> S, s: %) ==                -- from HOAGG
      ref map(f, deref s)$List(S)

    map!(f: S -> S, s: %) ==               -- from HOAGG
      setref(s, map!(f, deref s)$List(S))
      s

    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 positive? j 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}