\documentclass{article}
\usepackage{axiom}
\begin{document}
\title{\$SPAD/src/algebra lmdict.spad}
\author{Michael Monagan, Frederic Lehobey}
\maketitle
\begin{abstract}
\end{abstract}
\eject
\tableofcontents
\eject
\section{domain LMDICT ListMultiDictionary}
<<domain LMDICT ListMultiDictionary>>=
)abbrev domain LMDICT ListMultiDictionary
++ Author: MBM Nov/87, MB Oct/89
++ Date Created:
++ Date Last Updated: 13 June 1994 Frederic Lehobey
++ Basic Operations:
++ Related Constructors:
++ Also See:
++ AMS Classifications:
++ Keywords:
++ References:
++ Description: The \spadtype{ListMultiDictionary} domain implements a
++ dictionary with duplicates
++ allowed.  The representation is a list with duplicates represented
++ explicitly.  Hence most operations will be relatively inefficient
++ when the number of entries in the dictionary becomes large.
-- The operations \spadfun{pick}, \spadfun{count} and \spadfun{delete} can be used to iterate
-- over the objects in the dictionary.
-- [FDLL : those functions have not been implemented in the parent Categories]
++ If the objects in the
++ dictionary belong to an ordered set, the entries are maintained in
++ ascending order.

NNI ==> NonNegativeInteger
D ==> Record(entry:S, count:NonNegativeInteger)

ListMultiDictionary(S:SetCategory): MultiDictionary(S) with
   finiteAggregate
   duplicates?: % -> Boolean
     ++ duplicates?(d) tests if dictionary d has duplicate entries.
   substitute : (S, S, %) -> %
     ++ substitute(x,y,d) replace x's with y's in dictionary d.
 == add
   Rep := Reference List S

   sub: (S, S, S) -> S

   coerce(s:%):OutputForm ==
     prefix("dictionary"::OutputForm, [x::OutputForm for x in parts s])

   #s                 == # parts s
   copy s             == dictionary copy parts s
   empty? s           == empty? parts s
   bag l              == dictionary l
   dictionary()       == dictionary empty()

   empty():% == ref empty()

   dictionary(ls:List S):% ==
     empty? ls => empty()
     lmd := empty()
     for x in ls repeat insert!(x,lmd)
     lmd

   if S has ConvertibleTo InputForm then
     convert(lmd:%):InputForm ==
       convert [convert('dictionary)@InputForm,
        convert(parts lmd)@InputForm]

   map(f, s)          == dictionary map(f, parts s)
   map!(f, s)        == dictionary map!(f, parts s)
   parts s            == deref s
   sub(x, y, z)       == (z = x => y; z)
   insert!(x, s, n)  == (for i in 1..n repeat insert!(x, s); s)
   substitute(x, y, s) == dictionary map(sub(x, y, #1), parts s)
   removeDuplicates! s == dictionary removeDuplicates! parts s

   inspect s ==
     empty? s => error "empty dictionary"
     first parts s

   extract! s ==
     empty? s => error "empty dictionary"
     x := first(p := parts s)
     setref(s, rest p)
     x

   duplicates? s ==
     empty?(p := parts s) => false
     q := rest p
     while not empty? q repeat
       first p = first q => return true
       p := q
       q := rest q
     false

   remove!(p: S->Boolean, lmd:%):% ==
     for x in removeDuplicates parts lmd | p(x) repeat remove!(x,lmd)
     lmd

   select!(p: S->Boolean, lmd:%):% == remove!(not p(#1), lmd)

   duplicates(lmd:%):List D ==
     ld: List D := empty()
     for x in removeDuplicates parts lmd | (n := count(x, lmd)) >
      1$NonNegativeInteger repeat
       ld := cons([x, n], ld)
     ld

   if S has OrderedSet then
      s = t == parts s = parts t

      remove!(x:S, s:%) ==
         p := deref s
         while not empty? p and x = first p repeat p := rest p
         setref(s, p)
         empty? p => s
         q := rest p
         while not empty? q and x > first q repeat (p := q; q := rest q)
         while not empty? q and x = first q repeat q := rest q
         p.rest := q
         s

      insert!(x, s) ==
         p := deref s
         empty? p or x < first p =>
            setref(s, concat(x, p))
            s
         q := rest p
         while not empty? q and x > first q repeat (p := q; q := rest q)
         p.rest := concat(x, q)
         s

   else
      remove!(x:S, s:%) == (setref(s, remove!(x, parts s)); s)

      s = t ==
         a := copy s
         while not empty? a repeat
            x := inspect a
            count(x, s) ~= count(x, t) => return false
            remove!(x, a)
         true

      insert!(x, s) ==
         p := deref s
         while not empty? p repeat
            x = first p =>
               p.rest := concat(x, rest p)
               return s
            p := rest p
         setref(s, concat(x, deref s))
         s

@
\section{License}
<<license>>=
--Copyright (c) 1991-2002, The Numerical ALgorithms Group Ltd.
--All rights reserved.
--Copyright (C) 2007-2009, Gabriel Dos Reis.
--All rights reserved.
--
--Redistribution and use in source and binary forms, with or without
--modification, are permitted provided that the following conditions are
--met:
--
--    - Redistributions of source code must retain the above copyright
--      notice, this list of conditions and the following disclaimer.
--
--    - Redistributions in binary form must reproduce the above copyright
--      notice, this list of conditions and the following disclaimer in
--      the documentation and/or other materials provided with the
--      distribution.
--
--    - Neither the name of The Numerical ALgorithms Group Ltd. nor the
--      names of its contributors may be used to endorse or promote products
--      derived from this software without specific prior written permission.
--
--THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
--IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
--TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
--PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
--OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
--EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
--PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
--PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
--LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
--NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
--SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
@
<<*>>=
<<license>>

<<domain LMDICT ListMultiDictionary>>
@
\eject
\begin{thebibliography}{99}
\bibitem{1} nothing
\end{thebibliography}
\end{document}