Initial population.

1 files changed, 339 insertions, 0 deletions

diff --git a/src/algebra/mset.spad.pamphlet b/src/algebra/mset.spad.pamphlet
new file mode 100644
index 00000000..abe5d56d
--- /dev/null
+++ b/src/algebra/mset.spad.pamphlet
@@ -0,0 +1,339 @@
+\documentclass{article}
+\usepackage{axiom}
+\begin{document}
+\title{\$SPAD/src/algebra mset.spad}
+\author{Stephen M. Watt, William H. Burge, Richard D. Jenks, Frederic Lehobey}
+\maketitle
+\begin{abstract}
+\end{abstract}
+\eject
+\tableofcontents
+\eject
+\section{domain MSET Multiset}
+<<domain MSET Multiset>>=
+)abbrev domain MSET Multiset
+++ Author:Stephen M. Watt, William H. Burge, Richard D. Jenks, Frederic Lehobey
+++ Date Created:NK
+++ Date Last Updated: 14 June 1994
+++ Basic Operations:
+++ Related Domains:
+++ Also See:
+++ AMS Classifications:
+++ Keywords:
+++ Examples:
+++ References:
+++ Description: A multiset is a set with multiplicities.
+Multiset(S: SetCategory): MultisetAggregate S with
+        finiteAggregate
+        shallowlyMutable
+        multiset: () -> %
+          ++ multiset()$D creates an empty multiset of domain D.
+        multiset: S -> %
+          ++ multiset(s) creates a multiset with singleton s.
+        multiset: List S -> %
+          ++ multiset(ls) creates a multiset with elements from \spad{ls}.
+        members: % -> List S
+          ++ members(ms) returns a list of the elements of \spad{ms}
+          ++ {\em without} their multiplicity. See also \spadfun{parts}.
+        remove: (S,%,Integer) -> %
+          ++ remove(x,ms,number) removes at most \spad{number} copies of
+          ++ element x if \spad{number} is positive, all of them if
+          ++ \spad{number} equals zero, and all but at most \spad{-number} if
+          ++ \spad{number} is negative.
+        remove: ( S -> Boolean ,%,Integer) -> %
+          ++ remove(p,ms,number) removes at most \spad{number} copies of
+          ++ elements x such that \spad{p(x)} is \spadfun{true}
+          ++ if \spad{number} is positive, all of them if
+          ++ \spad{number} equals zero, and all but at most \spad{-number} if
+          ++ \spad{number} is negative.
+        remove_!: (S,%,Integer) -> %
+          ++ remove!(x,ms,number) removes destructively at most \spad{number}
+          ++ copies of element x if \spad{number} is positive, all
+          ++ of them if \spad{number} equals zero, and all but at most
+          ++ \spad{-number} if \spad{number} is negative.
+        remove_!: ( S -> Boolean ,%,Integer) -> %
+          ++ remove!(p,ms,number) removes destructively at most \spad{number}
+          ++ copies of elements x such that \spad{p(x)} is
+          ++ \spadfun{true} if \spad{number} is positive, all of them if
+          ++ \spad{number} equals zero, and all but at most \spad{-number} if
+          ++ \spad{number} is negative.
+
+    == add
+
+        Tbl ==> Table(S, Integer)
+        tbl ==> table$Tbl
+        Rep := Record(count: Integer, table: Tbl)
+
+        n: Integer
+        ms, m1, m2: %
+        t,  t1, t2: Tbl
+        D ==> Record(entry: S, count: NonNegativeInteger)
+        K ==> Record(key: S, entry: Integer)
+
+        elt(t:Tbl, s:S):Integer ==
+          a := search(s,t)$Tbl
+          a case "failed" => 0
+          a::Integer
+
+        empty():% == [0,tbl()]
+        multiset():% == empty()
+        dictionary():% == empty()			-- DictionaryOperations
+        set():% == empty()
+        brace():% == empty()
+
+        construct(l:List S):% ==
+            t := tbl()
+            n := 0
+            for e in l repeat
+              t.e := inc t.e
+              n := inc n
+            [n, t]
+        multiset(l:List S):% == construct l
+        bag(l:List S):% == construct l			-- BagAggregate
+        dictionary(l:List S):% == construct l		-- DictionaryOperations
+        set(l:List S):% == construct l
+        brace(l:List S):% == construct l
+
+        multiset(s:S):% == construct [s]
+
+        if S has ConvertibleTo InputForm then
+          convert(ms:%):InputForm ==
+            convert [convert("multiset"::Symbol)@InputForm,
+             convert(parts ms)@InputForm]
+
+        members(ms:%):List S == keys ms.table
+
+        coerce(ms:%):OutputForm ==
+            l: List OutputForm := empty()
+            t := ms.table
+            colon := ": " :: OutputForm
+            for e in keys t repeat
+                ex := e::OutputForm
+                n := t.e
+                item :=
+                  n > 1 => hconcat [n :: OutputForm,colon, ex]
+                  ex
+                l := cons(item,l)
+            brace l
+
+        duplicates(ms:%):List D ==			-- MultiDictionary
+          ld : List D := empty()
+          t := ms.table
+          for e in keys t | (n := t.e) > 1 repeat
+            ld := cons([e,n::NonNegativeInteger],ld)
+          ld
+
+        extract_!(ms:%):S ==				-- BagAggregate
+          empty? ms => error "extract: Empty multiset"
+          ms.count := dec ms.count
+          t := ms.table
+          e := inspect(t).key
+          if (n := t.e) > 1 then t.e := dec n
+           else remove_!(e,t)
+          e
+
+        inspect(ms:%):S == inspect(ms.table).key	-- BagAggregate
+
+        insert_!(e:S,ms:%):% ==				-- BagAggregate
+            ms.count   := inc ms.count
+            ms.table.e := inc ms.table.e
+            ms
+
+        member?(e:S,ms:%):Boolean == member?(e,keys ms.table)
+
+        empty?(ms:%):Boolean == ms.count = 0
+
+        #(ms:%):NonNegativeInteger == ms.count::NonNegativeInteger
+
+        count(e:S, ms:%):NonNegativeInteger == ms.table.e::NonNegativeInteger
+
+        remove_!(e:S, ms:%, max:Integer):% ==
+          zero? max => remove_!(e,ms)
+          t := ms.table
+          if member?(e, keys t) then
+            ((n := t.e) <= max) =>
+              remove_!(e,t)
+              ms.count := ms.count-n
+            max > 0 =>
+              t.e := n-max
+              ms.count := ms.count-max
+            (n := n+max) > 0 =>
+              t.e := -max
+              ms.count := ms.count-n
+          ms
+
+        remove_!(p: S -> Boolean, ms:%, max:Integer):% ==
+          zero? max => remove_!(p,ms)
+          t := ms.table
+          for e in keys t | p(e) repeat
+            ((n := t.e) <= max) =>
+              remove_!(e,t)
+              ms.count := ms.count-n
+            max > 0 =>
+              t.e := n-max
+              ms.count := ms.count-max
+            (n := n+max) > 0 =>
+              t.e := -max
+              ms.count := ms.count-n
+          ms
+
+        remove(e:S, ms:%, max:Integer):% == remove_!(e, copy ms, max)
+
+        remove(p: S -> Boolean,ms:%,max:Integer):% == remove_!(p, copy ms, max)
+
+        remove_!(e:S, ms:%):% ==			-- DictionaryOperations
+          t := ms.table
+          if member?(e, keys t) then
+            ms.count := ms.count-t.e
+            remove_!(e, t)
+          ms
+
+        remove_!(p:S ->Boolean, ms:%):% ==		-- DictionaryOperations
+          t := ms.table
+          for e in keys t | p(e) repeat
+            ms.count := ms.count-t.e
+            remove_!(e, t)
+          ms
+
+	select_!(p: S -> Boolean, ms:%):% ==		-- DictionaryOperations
+          remove_!(not p(#1), ms)
+
+        removeDuplicates_!(ms:%):% ==			-- MultiDictionary
+          t := ms.table
+          l := keys t
+          for e in l repeat t.e := 1
+          ms.count := #l
+          ms
+
+        insert_!(e:S,ms:%,more:NonNegativeInteger):% ==	-- MultiDictionary
+            ms.count   := ms.count+more
+            ms.table.e := ms.table.e+more
+            ms
+
+        map_!(f: S->S, ms:%):% ==			-- HomogeneousAggregate
+          t := ms.table
+          t1 := tbl()
+          for e in keys t repeat
+            t1.f(e) := t.e
+            remove_!(e, t)
+          ms.table := t1
+          ms
+
+	map(f: S -> S, ms:%):% == map_!(f, copy ms)	-- HomogeneousAggregate
+
+        parts(m:%):List S ==
+          l := empty()$List(S)
+          t := m.table
+          for e in keys t repeat
+            for i in 1..t.e repeat
+              l := cons(e,l)
+          l
+
+        union(m1:%, m2:%):% ==
+            t := tbl()
+            t1:= m1.table
+            t2:= m2.table
+            for e in keys t1 repeat t.e := t1.e
+            for e in keys t2 repeat t.e := t2.e + t.e
+            [m1.count + m2.count, t]
+
+        intersect(m1:%, m2:%):% ==
+--          if #m1 > #m2 then intersect(m2, m1)
+            t := tbl()
+            t1:= m1.table
+            t2:= m2.table
+            n := 0
+            for e in keys t1 repeat
+              m := min(t1.e,t2.e)
+              m > 0 =>
+                m := t1.e + t2.e
+                t.e := m
+                n := n + m
+            [n, t]
+
+        difference(m1:%, m2:%):% ==
+            t := tbl()
+            t1:= m1.table
+            t2:= m2.table
+            n := 0
+            for e in keys t1 repeat
+              k1 := t1.e
+              k2 := t2.e
+              k1 > 0 and k2 = 0 =>
+                t.e := k1
+                n := n + k1
+            n = 0 => empty()
+            [n, t]
+
+        symmetricDifference(m1:%, m2:%):% ==
+            union(difference(m1,m2), difference(m2,m1))
+
+        m1 = m2 ==
+            m1.count ^= m2.count => false
+            t1 := m1.table
+            t2 := m2.table
+            for e in keys t1 repeat
+                t1.e ^= t2.e => return false
+            for e in keys t2 repeat
+                t1.e ^= t2.e => return false
+            true
+
+        m1 < m2 ==
+            m1.count >= m2.count => false
+            t1 := m1.table
+            t2 := m2.table
+            for e in keys t1 repeat
+                t1.e > t2.e => return false
+            m1.count < m2.count
+
+        subset?(m1:%, m2:%):Boolean ==
+            m1.count > m2.count => false
+            t1 := m1.table
+            t2 := m2.table
+            for e in keys t1 repeat t1.e > t2.e => return false
+            true
+
+@
+\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 MSET Multiset>>
+@
+\eject
+\begin{thebibliography}{99}
+\bibitem{1} nothing
+\end{thebibliography}
+\end{document}