From ab8cc85adde879fb963c94d15675783f2cf4b183 Mon Sep 17 00:00:00 2001 From: dos-reis Date: Tue, 14 Aug 2007 05:14:52 +0000 Subject: Initial population. --- src/algebra/lmdict.spad.pamphlet | 200 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 200 insertions(+) create mode 100644 src/algebra/lmdict.spad.pamphlet (limited to 'src/algebra/lmdict.spad.pamphlet') 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} +<>= +)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} +<>= +--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. +@ +<<*>>= +<> + +<> +@ +\eject +\begin{thebibliography}{99} +\bibitem{1} nothing +\end{thebibliography} +\end{document} -- cgit v1.2.3