\documentclass{article}
\usepackage{open-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): Join(MultisetAggregate S,FiniteAggregate S,ShallowlyMutableAggregate S) with
        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}.
        unique: % -> List S
          ++ \spad{unique ms} returns a list of the elements of \spad{ms}
          ++ {\em without} their multiplicity. See also \spadfun{members}.
        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)@InputForm,
             convert(members ms)@InputForm]

        unique(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
            positive? max =>
              t.e := n-max
              ms.count := ms.count-max
            positive?(n := n+max) =>
              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
            positive? max =>
              t.e := n-max
              ms.count := ms.count-max
            positive?(n := n+max) =>
              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

        members(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)
              positive? m =>
                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
              positive? k1 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

        part?(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.
--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 MSET Multiset>>
@
\eject
\begin{thebibliography}{99}
\bibitem{1} nothing
\end{thebibliography}
\end{document}