/usr/share/axiom-20170501/src/algebra/LMDICT.spad is in axiom-source 20170501-3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 | )abbrev domain LMDICT ListMultiDictionary
++ Author: Mark Botch
++ Date Last Updated: 13 June 1994 Frederic Lehobey
++ 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.
++ If the objects in the dictionary belong to an ordered set,
++ the entries are maintained in ascending order.
ListMultiDictionary(S) : SIG == CODE where
S : SetCategory
NNI ==> NonNegativeInteger
D ==> Record(entry:S, count:NonNegativeInteger)
SIG ==> 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.
CODE ==> 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(z1 +-> sub(x, y, z1), 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_!((z:S):Boolean+->not p(z), 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
|