1"""compatibility layer for collections (Python standard library)""" 2from __future__ import absolute_import 3from collections import * 4 5 6try: 7 namedtuple('x', ['x'], rename=True) # Argument 'rename' new in 2.7 8except TypeError: 9 # Copyright 2007 Raymond Hettinger 10 # From http://code.activestate.com/recipes/500261-named-tuples/ 11 # Released under the Python Software Foundation License 12 # <http://www.opensource.org/licenses/Python-2.0>. 13 from operator import itemgetter as _itemgetter 14 from keyword import iskeyword as _iskeyword 15 import sys as _sys 16 17 namedtuple_orig = namedtuple 18 19 def namedtuple(typename, field_names, verbose=False, rename=False): 20 # Parse and validate the field names. Validation serves two purposes, 21 # generating informative error messages and preventing template injection attacks. 22 if isinstance(field_names, basestring): 23 field_names = field_names.replace(',', ' ').split() # names separated by whitespace and/or commas 24 #field_names = tuple(map(str, field_names)) # <- Bad recursion behavior in Python 2.5 25 field_names = tuple([str(x) for x in field_names]) 26 if rename: 27 names = list(field_names) 28 seen = set() 29 for i, name in enumerate(names): 30 if (not min(c.isalnum() or c=='_' for c in name) or _iskeyword(name) 31 or not name or name[0].isdigit() or name.startswith('_') 32 or name in seen): 33 names[i] = '_%d' % i 34 seen.add(name) 35 field_names = tuple(names) 36 for name in (typename,) + field_names: 37 if not min(c.isalnum() or c=='_' for c in name): 38 raise ValueError('Type names and field names can only contain alphanumeric characters and underscores: %r' % name) 39 if _iskeyword(name): 40 raise ValueError('Type names and field names cannot be a keyword: %r' % name) 41 if name[0].isdigit(): 42 raise ValueError('Type names and field names cannot start with a number: %r' % name) 43 seen_names = set() 44 for name in field_names: 45 if name.startswith('_') and not rename: 46 raise ValueError('Field names cannot start with an underscore: %r' % name) 47 if name in seen_names: 48 raise ValueError('Encountered duplicate field name: %r' % name) 49 seen_names.add(name) 50 # Create and fill-in the class template 51 numfields = len(field_names) 52 argtxt = repr(field_names).replace("'", "")[1:-1] # tuple repr without parens or quotes 53 reprtxt = ', '.join('%s=%%r' % name for name in field_names) 54 template = '''class %(typename)s(tuple): 55 '%(typename)s(%(argtxt)s)' \n 56 __slots__ = () \n 57 _fields = %(field_names)r \n 58 def __new__(_cls, %(argtxt)s): 59 return _tuple.__new__(_cls, (%(argtxt)s)) \n 60 @classmethod 61 def _make(cls, iterable, new=tuple.__new__, len=len): 62 'Make a new %(typename)s object from a sequence or iterable' 63 result = new(cls, iterable) 64 if len(result) != %(numfields)d: 65 raise TypeError('Expected %(numfields)d arguments, got %%d' %% len(result)) 66 return result \n 67 def __repr__(self): 68 return '%(typename)s(%(reprtxt)s)' %% self \n 69 def _asdict(self): 70 'Return a new dict which maps field names to their values' 71 return dict(zip(self._fields, self)) \n 72 def _replace(_self, **kwds): 73 'Return a new %(typename)s object replacing specified fields with new values' 74 result = _self._make(map(kwds.pop, %(field_names)r, _self)) 75 if kwds: 76 raise ValueError('Got unexpected field names: %%r' %% kwds.keys()) 77 return result \n 78 def __getnewargs__(self): 79 return tuple(self) \n\n''' % locals() 80 for i, name in enumerate(field_names): 81 template += ' %s = _property(_itemgetter(%d))\n' % (name, i) 82 if verbose: 83 print(template) 84 # Execute the template string in a temporary namespace 85 namespace = dict(_itemgetter=_itemgetter, __name__='namedtuple_%s' % typename, 86 _property=property, _tuple=tuple) 87 try: 88 exec(template, namespace) 89 except SyntaxError as e: 90 raise SyntaxError(str(e) + ':\n' + template) 91 result = namespace[typename] 92 # For pickling to work, the __module__ variable needs to be set to the frame 93 # where the named tuple is created. Bypass this step in enviroments where 94 # sys._getframe is not defined (Jython for example) or sys._getframe is not 95 # defined for arguments greater than 0 (IronPython). 96 try: 97 result.__module__ = _sys._getframe(1).f_globals.get('__name__', '__main__') 98 except (AttributeError, ValueError): 99 pass 100 return result 101 102 namedtuple.__doc__ = namedtuple_orig.__doc__ 103 104 105try: 106 Counter # New in Python 2.7 107except NameError: 108 # Copyright 2009 Raymond Hettinger 109 # From http://code.activestate.com/recipes/576611-counter-class/ 110 # Released under the MIT License 111 # <http://www.opensource.org/licenses/MIT>. 112 from operator import itemgetter 113 from itertools import repeat 114 from heapq import nlargest 115 ifilter = filter 116 117 class Counter(dict): 118 '''Dict subclass for counting hashable objects. Sometimes called a bag 119 or multiset. Elements are stored as dictionary keys and their counts 120 are stored as dictionary values. 121 122 >>> Counter('zyzygy') 123 Counter({'y': 3, 'z': 2, 'g': 1}) 124 125 ''' 126 127 def __init__(self, iterable=None, **kwds): 128 '''Create a new, empty Counter object. And if given, count elements 129 from an input iterable. Or, initialize the count from another mapping 130 of elements to their counts. 131 132 >>> c = Counter() # a new, empty counter 133 >>> c = Counter('gallahad') # a new counter from an iterable 134 >>> c = Counter({'a': 4, 'b': 2}) # a new counter from a mapping 135 >>> c = Counter(a=4, b=2) # a new counter from keyword args 136 137 ''' 138 self.update(iterable, **kwds) 139 140 def __getitem__(self, key): 141 # This try/except was added for Python 2.4 support since 142 # builtin __missing__ support was added in Python 2.5. 143 try: 144 return dict.__getitem__(self, key) 145 except KeyError: 146 self[key] = value = self.__missing__(key) 147 return value 148 149 def __missing__(self, key): 150 return 0 151 152 def most_common(self, n=None): 153 '''List the n most common elements and their counts from the most 154 common to the least. If n is None, then list all element counts. 155 156 >>> Counter('abracadabra').most_common(3) 157 [('a', 5), ('r', 2), ('b', 2)] 158 159 ''' 160 if n is None: 161 return sorted(self.iteritems(), key=itemgetter(1), reverse=True) 162 return nlargest(n, self.iteritems(), key=itemgetter(1)) 163 164 def elements(self): 165 '''Iterator over elements repeating each as many times as its count. 166 167 >>> c = Counter('ABCABC') 168 >>> sorted(c.elements()) 169 ['A', 'A', 'B', 'B', 'C', 'C'] 170 171 If an element's count has been set to zero or is a negative number, 172 elements() will ignore it. 173 174 ''' 175 for elem, count in self.iteritems(): 176 for _ in repeat(None, count): 177 yield elem 178 179 # Override dict methods where the meaning changes for Counter objects. 180 181 @classmethod 182 def fromkeys(cls, iterable, v=None): 183 raise NotImplementedError( 184 'Counter.fromkeys() is undefined. Use Counter(iterable) instead.') 185 186 def update(self, iterable=None, **kwds): 187 '''Like dict.update() but add counts instead of replacing them. 188 189 Source can be an iterable, a dictionary, or another Counter instance. 190 191 >>> c = Counter('which') 192 >>> c.update('witch') # add elements from another iterable 193 >>> d = Counter('watch') 194 >>> c.update(d) # add elements from another counter 195 >>> c['h'] # four 'h' in which, witch, and watch 196 4 197 198 ''' 199 if iterable is not None: 200 if hasattr(iterable, 'iteritems'): 201 if self: 202 self_get = self.get 203 for elem, count in iterable.iteritems(): 204 self[elem] = self_get(elem, 0) + count 205 else: 206 dict.update(self, iterable) # fast path when counter is empty 207 else: 208 self_get = self.get 209 for elem in iterable: 210 self[elem] = self_get(elem, 0) + 1 211 if kwds: 212 self.update(kwds) 213 214 def copy(self): 215 'Like dict.copy() but returns a Counter instance instead of a dict.' 216 return Counter(self) 217 218 def __delitem__(self, elem): 219 'Like dict.__delitem__() but does not raise KeyError for missing values.' 220 if elem in self: 221 dict.__delitem__(self, elem) 222 223 def __repr__(self): 224 if not self: 225 return '%s()' % self.__class__.__name__ 226 items = ', '.join(map('%r: %r'.__mod__, self.most_common())) 227 return '%s({%s})' % (self.__class__.__name__, items) 228 229 # Multiset-style mathematical operations discussed in: 230 # Knuth TAOCP Volume II section 4.6.3 exercise 19 231 # and at http://en.wikipedia.org/wiki/Multiset 232 # 233 # Outputs guaranteed to only include positive counts. 234 # 235 # To strip negative and zero counts, add-in an empty counter: 236 # c += Counter() 237 238 def __add__(self, other): 239 '''Add counts from two counters. 240 241 >>> Counter('abbb') + Counter('bcc') 242 Counter({'b': 4, 'c': 2, 'a': 1}) 243 244 245 ''' 246 if not isinstance(other, Counter): 247 return NotImplemented 248 result = Counter() 249 for elem in set(self) | set(other): 250 #newcount = self[elem] + other[elem] 251 selfelem = self[elem] 252 otherelem = other[elem] 253 newcount = selfelem + otherelem 254 255 if newcount > 0: 256 result[elem] = newcount 257 return result 258 259 def __sub__(self, other): 260 ''' Subtract count, but keep only results with positive counts. 261 262 >>> Counter('abbbc') - Counter('bccd') 263 Counter({'b': 2, 'a': 1}) 264 265 ''' 266 if not isinstance(other, Counter): 267 return NotImplemented 268 result = Counter() 269 for elem in set(self) | set(other): 270 newcount = self[elem] - other[elem] 271 if newcount > 0: 272 result[elem] = newcount 273 return result 274 275 def __or__(self, other): 276 '''Union is the maximum of value in either of the input counters. 277 278 >>> Counter('abbb') | Counter('bcc') 279 Counter({'b': 3, 'c': 2, 'a': 1}) 280 281 ''' 282 if not isinstance(other, Counter): 283 return NotImplemented 284 _max = max 285 result = Counter() 286 for elem in set(self) | set(other): 287 newcount = _max(self[elem], other[elem]) 288 if newcount > 0: 289 result[elem] = newcount 290 return result 291 292 def __and__(self, other): 293 ''' Intersection is the minimum of corresponding counts. 294 295 >>> Counter('abbb') & Counter('bcc') 296 Counter({'b': 1}) 297 298 ''' 299 if not isinstance(other, Counter): 300 return NotImplemented 301 _min = min 302 result = Counter() 303 if len(self) < len(other): 304 self, other = other, self 305 for elem in ifilter(self.__contains__, other): 306 newcount = _min(self[elem], other[elem]) 307 if newcount > 0: 308 result[elem] = newcount 309 return result 310