Initial population.

1 files changed, 200 insertions, 0 deletions

diff --git a/src/algebra/lmdict.spad.pamphlet b/src/algebra/lmdict.spad.pamphlet
new file mode 100644
index 00000000..cba196e2
--- /dev/null
+++ b/src/algebra/lmdict.spad.pamphlet
@@ -0,0 +1,200 @@
+\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"::Symbol)@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)
+               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.
+--
+--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}