\documentclass{article} \usepackage{open-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} <>= )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): Join(MultiDictionary S,FiniteAggregate S) with 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 members s]) #s == # members s copy s == dictionary copy members s empty? s == empty? members 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(members lmd)@InputForm] map(f, s) == dictionary map(f, members s) map!(f, s) == dictionary map!(f, members s) members 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), members s) removeDuplicates! s == dictionary removeDuplicates! members s inspect s == empty? s => error "empty dictionary" first members s extract! s == empty? s => error "empty dictionary" x := first(p := members s) setref(s, rest p) x duplicates? s == empty?(p := members 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 members 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 members lmd | (n := count(x, lmd)) > 1$NonNegativeInteger repeat ld := cons([x, n], ld) ld if S has OrderedSet then s = t == members s = members 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, members 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} <>= --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. @ <<*>>= <> <> @ \eject \begin{thebibliography}{99} \bibitem{1} nothing \end{thebibliography} \end{document}