Package muntjac :: Package data :: Package util :: Module list_set
[hide private]
[frames] | no frames]

Source Code for Module muntjac.data.util.list_set

  1  # Copyright (C) 2012 Vaadin Ltd.  
  2  # Copyright (C) 2012 Richard Lincoln 
  3  #  
  4  # Licensed under the Apache License, Version 2.0 (the "License");  
  5  # you may not use this file except in compliance with the License.  
  6  # You may obtain a copy of the License at  
  7  #  
  8  #     http://www.apache.org/licenses/LICENSE-2.0  
  9  #  
 10  # Unless required by applicable law or agreed to in writing, software  
 11  # distributed under the License is distributed on an "AS IS" BASIS,  
 12  # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.  
 13  # See the License for the specific language governing permissions and  
 14  # limitations under the License. 
 15   
 16  """ListSet is an internal Muntjac class which implements a combination of 
 17  a list and a set.""" 
 18   
 19   
20 -class ListSet(list):
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
31 - def __init__(self, *args):
32 self._itemSet = None 33 34 # Contains a map from an element to the number of duplicates it has. 35 # Used to temporarily allow duplicates in the list. 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__()#initialCapacity) 46 self._itemSet = set()#initialCapacity) 47 else: 48 c, = args 49 super(ListSet, self).__init__(c) 50 self._itemSet = set()#len(c)) 51 self._itemSet = self._itemSet.union(c) 52 else: 53 raise ValueError, 'too many arguments'
54 55 # Delegate contains operations to the set 56
57 - def contains(self, o):
58 return o in self._itemSet
59 60
61 - def __contains__(self, item):
62 return self.contains(item)
63 64
65 - def containsAll(self, c):
66 for cc in c: 67 if cc not in self._itemSet: 68 return False 69 else: 70 return True
71 72
73 - def append(self, val):
74 return self.add(val)
75 76
77 - def insert(self, idx, val):
78 return self.add(idx, val)
79 80 81 # Methods for updating the set when the list is updated.
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 # Duplicates are not allowed 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 # Duplicates are not allowed 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
109 - def extend(self, iterable):
110 return self.addAll(iterable)
111 112
113 - def addAll(self, *args):
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 #self.ensureCapacity(len(self) + len(c)) 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
143 - def clear(self):
144 del self[:] 145 self._itemSet.clear()
146 147
148 - def index(self, val):
149 return self.indexOf(val)
150 151
152 - def indexOf(self, o):
153 if not self.contains(o): 154 return -1 155 return super(ListSet, self).index(o)
156 157
158 - def lastIndexOf(self, o):
159 if not self.contains(o): 160 return -1 161 return self[::-1].index(o)
162 163
164 - def remove(self, o):
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
179 - def removeRange(self, fromIndex, toIndex):
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): #@PydevCodeAnalysisIgnore
189 if element in self: 190 # Element already exist in the list 191 if self[index] == element: 192 # At the same position, nothing to be done 193 return element 194 else: 195 # Adding at another position. We assume this is a sort 196 # operation and temporarily allow it. 197 # We could just remove (null) the old element and keep the list 198 # unique. This would require finding the index of the old 199 # element (indexOf(element)) which is not a fast operation in a 200 # list. So we instead allow duplicates temporarily. 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
210 - def removeFromSet(self, e):
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 # A duplicate was present so we only decrement the duplicate count 216 # and continue 217 if dupl == 1: 218 # This is what always should happen. A sort sets the items one 219 # by one, temporarily breaking the uniqueness requirement. 220 del self._duplicates[e] 221 else: 222 self._duplicates[e] = dupl - 1 223 else: 224 # The "old" value is no longer in the list. 225 self._itemSet.remove(e)
226 227
228 - def addDuplicate(self, element):
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 # Store the number of duplicates of this element so we know later on if 239 # we should remove an element from the set or if it was a duplicate (in 240 # removeFromSet) 241 self._duplicates[element] = nr
242 243
244 - def clone(self):
245 v = ListSet(self[:]) 246 v._itemSet = set(self._itemSet) 247 return v
248