1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 """ListSet is an internal Muntjac class which implements a combination of
17 a list and a set."""
18
19
21 """ListSet is an internal Muntjac class which implements a combination of
22 a List and a Set. The main purpose of this class is to provide a list with
23 a fast L{contains} method. Each inserted object must by unique (as
24 specified by L{equals}). The L{set} method allows duplicates because of
25 the way L{sort} works.
26
27 This class is subject to change and should not be used outside Muntjac
28 core.
29 """
30
32 self._itemSet = None
33
34
35
36 self._duplicates = dict()
37
38 nargs = len(args)
39 if nargs == 0:
40 super(ListSet, self).__init__()
41 self._itemSet = set()
42 elif nargs == 1:
43 if isinstance(args[0], int):
44 initialCapacity, = args
45 super(ListSet, self).__init__()
46 self._itemSet = set()
47 else:
48 c, = args
49 super(ListSet, self).__init__(c)
50 self._itemSet = set()
51 self._itemSet = self._itemSet.union(c)
52 else:
53 raise ValueError, 'too many arguments'
54
55
56
58 return o in self._itemSet
59
60
63
64
66 for cc in c:
67 if cc not in self._itemSet:
68 return False
69 else:
70 return True
71
72
75
76
78 return self.add(idx, val)
79
80
81
82 - def add(self, *args):
83 """Works as list.append or list.insert but returns
84 immediately if the element is already in the ListSet.
85 """
86 nargs = len(args)
87 if nargs == 1:
88 e, = args
89 if self.contains(e):
90
91 return False
92 if not super(ListSet, self).__contains__(e):
93 super(ListSet, self).append(e)
94 self._itemSet.add(e)
95 return True
96 else:
97 return False
98 elif nargs == 2:
99 index, element = args
100 if self.contains(element):
101
102 return
103 super(ListSet, self).insert(index, element)
104 self._itemSet.add(element)
105 else:
106 raise ValueError, 'invalid number of arguments'
107
108
110 return self.addAll(iterable)
111
112
114 nargs = len(args)
115 if nargs == 1:
116 c, = args
117 modified = False
118 for e in c:
119 if self.contains(e):
120 continue
121
122 if self.add(e):
123 self._itemSet.add(e)
124 modified = True
125
126 return modified
127 elif nargs == 2:
128 index, c = args
129
130 modified = False
131 for e in c:
132 if self.contains(e):
133 continue
134 self.add(index, e)
135 index += 1
136 self._itemSet.add(e)
137 modified = True
138 return modified
139 else:
140 raise ValueError, 'invalid number of arguments'
141
142
144 del self[:]
145 self._itemSet.clear()
146
147
150
151
156
157
159 if not self.contains(o):
160 return -1
161 return self[::-1].index(o)
162
163
165 if isinstance(o, int):
166 index = o
167 e = super(ListSet, self).pop(index)
168 if e is not None:
169 self._itemSet.remove(e)
170 return e
171 else:
172 if super(ListSet, self).remove(o):
173 self._itemSet.remove(o)
174 return True
175 else:
176 return False
177
178
180 toRemove = set()
181 for idx in range(fromIndex, toIndex):
182 toRemove.add(self[idx])
183 del self[fromIndex:toIndex]
184 for r in toRemove:
185 self._itemSet.remove(r)
186
187
188 - def set(self, index, element):
189 if element in self:
190
191 if self[index] == element:
192
193 return element
194 else:
195
196
197
198
199
200
201 self.addDuplicate(element)
202
203 old = self[index] = element
204 self.removeFromSet(old)
205 self._itemSet.add(element)
206
207 return old
208
209
211 """Removes "e" from the set if it no longer exists in the list.
212 """
213 dupl = self._duplicates.get(e)
214 if dupl is not None:
215
216
217 if dupl == 1:
218
219
220 del self._duplicates[e]
221 else:
222 self._duplicates[e] = dupl - 1
223 else:
224
225 self._itemSet.remove(e)
226
227
229 """Marks the "element" can be found more than once from the list.
230 Allowed in L{set} to make sorting work.
231 """
232 nr = self._duplicates.get(element)
233 if nr is None:
234 nr = 1
235 else:
236 nr += 1
237
238
239
240
241 self._duplicates[element] = nr
242
243
245 v = ListSet(self[:])
246 v._itemSet = set(self._itemSet)
247 return v
248