collections.py (12909B)
1 #Embedded file name: C:\BuildAgent\work\20d73f1b24eed06e\eve\release\V24.01\carbon\common\stdlib\collections.py 2 __all__ = ['Counter', 3 'deque', 4 'defaultdict', 5 'namedtuple', 6 'OrderedDict'] 7 from _abcoll import * 8 import _abcoll 9 __all__ += _abcoll.__all__ 10 from _collections import deque, defaultdict 11 from operator import itemgetter as _itemgetter, eq as _eq 12 from keyword import iskeyword as _iskeyword 13 import sys as _sys 14 import heapq as _heapq 15 from itertools import repeat as _repeat, chain as _chain, starmap as _starmap, ifilter as _ifilter, imap as _imap 16 try: 17 from thread import get_ident 18 except ImportError: 19 from dummy_thread import get_ident 20 21 def _recursive_repr(user_function): 22 repr_running = set() 23 24 def wrapper(self): 25 key = (id(self), get_ident()) 26 if key in repr_running: 27 return '...' 28 repr_running.add(key) 29 try: 30 result = user_function(self) 31 finally: 32 repr_running.discard(key) 33 34 return result 35 36 wrapper.__module__ = getattr(user_function, '__module__') 37 wrapper.__doc__ = getattr(user_function, '__doc__') 38 wrapper.__name__ = getattr(user_function, '__name__') 39 return wrapper 40 41 42 class OrderedDict(dict, MutableMapping): 43 44 def __init__(self, *args, **kwds): 45 if len(args) > 1: 46 raise TypeError('expected at most 1 arguments, got %d' % len(args)) 47 try: 48 self.__root 49 except AttributeError: 50 self.__root = root = [None, None, None] 51 PREV = 0 52 NEXT = 1 53 root[PREV] = root[NEXT] = root 54 self.__map = {} 55 56 self.update(*args, **kwds) 57 58 def __setitem__(self, key, value, PREV = 0, NEXT = 1, dict_setitem = dict.__setitem__): 59 if key not in self: 60 root = self.__root 61 last = root[PREV] 62 last[NEXT] = root[PREV] = self.__map[key] = [last, root, key] 63 dict_setitem(self, key, value) 64 65 def __delitem__(self, key, PREV = 0, NEXT = 1, dict_delitem = dict.__delitem__): 66 dict_delitem(self, key) 67 link = self.__map.pop(key) 68 link_prev = link[PREV] 69 link_next = link[NEXT] 70 link_prev[NEXT] = link_next 71 link_next[PREV] = link_prev 72 73 def __iter__(self, NEXT = 1, KEY = 2): 74 root = self.__root 75 curr = root[NEXT] 76 while curr is not root: 77 yield curr[KEY] 78 curr = curr[NEXT] 79 80 def __reversed__(self, PREV = 0, KEY = 2): 81 root = self.__root 82 curr = root[PREV] 83 while curr is not root: 84 yield curr[KEY] 85 curr = curr[PREV] 86 87 def __reduce__(self): 88 items = [ [k, self[k]] for k in self ] 89 tmp = (self.__map, self.__root) 90 del self.__map 91 del self.__root 92 inst_dict = vars(self).copy() 93 self.__map, self.__root = tmp 94 if inst_dict: 95 return (self.__class__, (items,), inst_dict) 96 return (self.__class__, (items,)) 97 98 def clear(self): 99 try: 100 for node in self.__map.itervalues(): 101 del node[:] 102 103 self.__root[:] = [self.__root, self.__root, None] 104 self.__map.clear() 105 except AttributeError: 106 pass 107 108 dict.clear(self) 109 110 setdefault = MutableMapping.setdefault 111 update = MutableMapping.update 112 pop = MutableMapping.pop 113 keys = MutableMapping.keys 114 values = MutableMapping.values 115 items = MutableMapping.items 116 iterkeys = MutableMapping.iterkeys 117 itervalues = MutableMapping.itervalues 118 iteritems = MutableMapping.iteritems 119 __ne__ = MutableMapping.__ne__ 120 121 def viewkeys(self): 122 return KeysView(self) 123 124 def viewvalues(self): 125 return ValuesView(self) 126 127 def viewitems(self): 128 return ItemsView(self) 129 130 def popitem(self, last = True): 131 if not self: 132 raise KeyError('dictionary is empty') 133 key = next(reversed(self) if last else iter(self)) 134 value = self.pop(key) 135 return (key, value) 136 137 @_recursive_repr 138 def __repr__(self): 139 if not self: 140 return '%s()' % (self.__class__.__name__,) 141 return '%s(%r)' % (self.__class__.__name__, self.items()) 142 143 def copy(self): 144 return self.__class__(self) 145 146 @classmethod 147 def fromkeys(cls, iterable, value = None): 148 d = cls() 149 for key in iterable: 150 d[key] = value 151 152 return d 153 154 def __eq__(self, other): 155 if isinstance(other, OrderedDict): 156 return len(self) == len(other) and all(_imap(_eq, self.iteritems(), other.iteritems())) 157 return dict.__eq__(self, other) 158 159 160 def namedtuple(typename, field_names, verbose = False, rename = False): 161 if isinstance(field_names, basestring): 162 field_names = field_names.replace(',', ' ').split() 163 field_names = tuple(map(str, field_names)) 164 if rename: 165 names = list(field_names) 166 seen = set() 167 for i, name in enumerate(names): 168 if not all((c.isalnum() or c == '_' for c in name)) or _iskeyword(name) or not name or name[0].isdigit() or name.startswith('_') or name in seen: 169 names[i] = '_%d' % i 170 seen.add(name) 171 172 field_names = tuple(names) 173 for name in (typename,) + field_names: 174 if not all((c.isalnum() or c == '_' for c in name)): 175 raise ValueError('Type names and field names can only contain alphanumeric characters and underscores: %r' % name) 176 if _iskeyword(name): 177 raise ValueError('Type names and field names cannot be a keyword: %r' % name) 178 if name[0].isdigit(): 179 raise ValueError('Type names and field names cannot start with a number: %r' % name) 180 181 seen_names = set() 182 for name in field_names: 183 if name.startswith('_') and not rename: 184 raise ValueError('Field names cannot start with an underscore: %r' % name) 185 if name in seen_names: 186 raise ValueError('Encountered duplicate field name: %r' % name) 187 seen_names.add(name) 188 189 numfields = len(field_names) 190 argtxt = repr(field_names).replace("'", '')[1:-1] 191 reprtxt = ', '.join(('%s=%%r' % name for name in field_names)) 192 template = "class %(typename)s(tuple):\n '%(typename)s(%(argtxt)s)' \n\n __slots__ = () \n\n _fields = %(field_names)r \n\n def __new__(_cls, %(argtxt)s):\n 'Create new instance of %(typename)s(%(argtxt)s)'\n return _tuple.__new__(_cls, (%(argtxt)s)) \n\n @classmethod\n def _make(cls, iterable, new=tuple.__new__, len=len):\n 'Make a new %(typename)s object from a sequence or iterable'\n result = new(cls, iterable)\n if len(result) != %(numfields)d:\n raise TypeError('Expected %(numfields)d arguments, got %%d' %% len(result))\n return result \n\n def __repr__(self):\n 'Return a nicely formatted representation string'\n return '%(typename)s(%(reprtxt)s)' %% self \n\n def _asdict(self):\n 'Return a new OrderedDict which maps field names to their values'\n return OrderedDict(zip(self._fields, self)) \n\n def _replace(_self, **kwds):\n 'Return a new %(typename)s object replacing specified fields with new values'\n result = _self._make(map(kwds.pop, %(field_names)r, _self))\n if kwds:\n raise ValueError('Got unexpected field names: %%r' %% kwds.keys())\n return result \n\n def __getnewargs__(self):\n 'Return self as a plain tuple. Used by copy and pickle.'\n return tuple(self) \n\n" % locals() 193 for i, name in enumerate(field_names): 194 template += " %s = _property(_itemgetter(%d), doc='Alias for field number %d')\n" % (name, i, i) 195 196 if verbose: 197 print template 198 namespace = dict(_itemgetter=_itemgetter, __name__='namedtuple_%s' % typename, OrderedDict=OrderedDict, _property=property, _tuple=tuple) 199 try: 200 exec template in namespace 201 except SyntaxError as e: 202 raise SyntaxError(e.message + ':\n' + template) 203 204 result = namespace[typename] 205 try: 206 result.__module__ = _sys._getframe(1).f_globals.get('__name__', '__main__') 207 except (AttributeError, ValueError): 208 pass 209 210 return result 211 212 213 try: 214 eval 215 except NameError: 216 217 def namedtuple(typename, field_names, verbose = False, rename = False): 218 return type(typename, (tuple,), {}) 219 220 221 class Counter(dict): 222 223 def __init__(self, iterable = None, **kwds): 224 self.update(iterable, **kwds) 225 226 def __missing__(self, key): 227 return 0 228 229 def most_common(self, n = None): 230 if n is None: 231 return sorted(self.iteritems(), key=_itemgetter(1), reverse=True) 232 return _heapq.nlargest(n, self.iteritems(), key=_itemgetter(1)) 233 234 def elements(self): 235 return _chain.from_iterable(_starmap(_repeat, self.iteritems())) 236 237 @classmethod 238 def fromkeys(cls, iterable, v = None): 239 raise NotImplementedError('Counter.fromkeys() is undefined. Use Counter(iterable) instead.') 240 241 def update(self, iterable = None, **kwds): 242 if iterable is not None: 243 if isinstance(iterable, Mapping): 244 if self: 245 self_get = self.get 246 for elem, count in iterable.iteritems(): 247 self[elem] = self_get(elem, 0) + count 248 249 else: 250 dict.update(self, iterable) 251 else: 252 self_get = self.get 253 for elem in iterable: 254 self[elem] = self_get(elem, 0) + 1 255 256 if kwds: 257 self.update(kwds) 258 259 def subtract(self, iterable = None, **kwds): 260 if iterable is not None: 261 self_get = self.get 262 if isinstance(iterable, Mapping): 263 for elem, count in iterable.items(): 264 self[elem] = self_get(elem, 0) - count 265 266 else: 267 for elem in iterable: 268 self[elem] = self_get(elem, 0) - 1 269 270 if kwds: 271 self.subtract(kwds) 272 273 def copy(self): 274 return Counter(self) 275 276 def __delitem__(self, elem): 277 if elem in self: 278 dict.__delitem__(self, elem) 279 280 def __repr__(self): 281 if not self: 282 return '%s()' % self.__class__.__name__ 283 items = ', '.join(map('%r: %r'.__mod__, self.most_common())) 284 return '%s({%s})' % (self.__class__.__name__, items) 285 286 def __add__(self, other): 287 if not isinstance(other, Counter): 288 return NotImplemented 289 result = Counter() 290 for elem in set(self) | set(other): 291 newcount = self[elem] + other[elem] 292 if newcount > 0: 293 result[elem] = newcount 294 295 return result 296 297 def __sub__(self, other): 298 if not isinstance(other, Counter): 299 return NotImplemented 300 result = Counter() 301 for elem in set(self) | set(other): 302 newcount = self[elem] - other[elem] 303 if newcount > 0: 304 result[elem] = newcount 305 306 return result 307 308 def __or__(self, other): 309 if not isinstance(other, Counter): 310 return NotImplemented 311 result = Counter() 312 for elem in set(self) | set(other): 313 p, q = self[elem], other[elem] 314 newcount = q if p < q else p 315 if newcount > 0: 316 result[elem] = newcount 317 318 return result 319 320 def __and__(self, other): 321 if not isinstance(other, Counter): 322 return NotImplemented 323 result = Counter() 324 if len(self) < len(other): 325 self, other = other, self 326 for elem in _ifilter(self.__contains__, other): 327 p, q = self[elem], other[elem] 328 newcount = p if p < q else q 329 if newcount > 0: 330 result[elem] = newcount 331 332 return result 333 334 335 if __name__ == '__main__': 336 from cPickle import loads, dumps 337 Point = namedtuple('Point', 'x, y', True) 338 p = Point(x=10, y=20) 339 340 class Point(namedtuple('Point', 'x y')): 341 __slots__ = () 342 343 @property 344 def hypot(self): 345 return (self.x ** 2 + self.y ** 2) ** 0.5 346 347 def __str__(self): 348 return 'Point: x=%6.3f y=%6.3f hypot=%6.3f' % (self.x, self.y, self.hypot) 349 350 351 for p in (Point(3, 4), Point(14, 5 / 7.0)): 352 print p 353 354 class Point(namedtuple('Point', 'x y')): 355 __slots__ = () 356 _make = classmethod(tuple.__new__) 357 358 def _replace(self, _map = map, **kwds): 359 return self._make(_map(kwds.get, ('x', 'y'), self)) 360 361 362 print Point(11, 22)._replace(x=100) 363 Point3D = namedtuple('Point3D', Point._fields + ('z',)) 364 print Point3D.__doc__ 365 import doctest 366 TestResults = namedtuple('TestResults', 'failed attempted') 367 print TestResults(*doctest.testmod())