kallithea: rhodecode/lib/odict.py annotate

annotate rhodecode/lib/odict.py @ 1340:cbdd583f1e58 beta

reverted copy of cached instance: CPython changelog total_time 39.7253162861 average on req 0.993132907152 changesets total_time 42.5156304836 average on req 0.425156304836 Total: 546 MB changelog total_time 35.5851216316 average on req 0.889628040791 changesets total_time 30.3608012199 average on req 0.303608012199 Total: 475 MB

author	Marcin Kuzminski <marcin@python-works.com>
date	Sun, 15 May 2011 18:29:33 +0200
parents	37625d304a16
children

rev	line source
1337 37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	1 # Python Software Foundation License
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	2
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	3 # XXX: it feels like using the class with "is" and "is not" instead of "==" and
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	4 # "!=" should be faster.
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	5 class _Nil(object):
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	6
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	7 def __repr__(self):
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	8 return "nil"
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	9
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	10 def __eq__(self, other):
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	11 if (isinstance(other, _Nil)):
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	12 return True
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	13 else:
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	14 return NotImplemented
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	15
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	16 def __ne__(self, other):
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	17 if (isinstance(other, _Nil)):
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	18 return False
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	19 else:
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	20 return NotImplemented
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	21
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	22 _nil = _Nil()
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	23
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	24 class _odict(object):
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	25 """Ordered dict data structure, with O(1) complexity for dict operations
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	26 that modify one element.
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	27
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	28 Overwriting values doesn't change their original sequential order.
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	29 """
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	30
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	31 def _dict_impl(self):
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	32 return None
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	33
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	34 def __init__(self, data=(), **kwds):
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	35 """This doesn't accept keyword initialization as normal dicts to avoid
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	36 a trap - inside a function or method the keyword args are accessible
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	37 only as a dict, without a defined order, so their original order is
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	38 lost.
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	39 """
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	40 if kwds:
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	41 raise TypeError("__init__() of ordered dict takes no keyword "
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	42 "arguments to avoid an ordering trap.")
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	43 self._dict_impl().__init__(self)
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	44 # If you give a normal dict, then the order of elements is undefined
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	45 if hasattr(data, "iteritems"):
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	46 for key, val in data.iteritems():
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	47 self[key] = val
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	48 else:
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	49 for key, val in data:
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	50 self[key] = val
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	51
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	52 # Double-linked list header
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	53 def _get_lh(self):
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	54 dict_impl = self._dict_impl()
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	55 if not hasattr(self, '_lh'):
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	56 dict_impl.__setattr__(self, '_lh', _nil)
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	57 return dict_impl.__getattribute__(self, '_lh')
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	58
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	59 def _set_lh(self, val):
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	60 self._dict_impl().__setattr__(self, '_lh', val)
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	61
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	62 lh = property(_get_lh, _set_lh)
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	63
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	64 # Double-linked list tail
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	65 def _get_lt(self):
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	66 dict_impl = self._dict_impl()
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	67 if not hasattr(self, '_lt'):
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	68 dict_impl.__setattr__(self, '_lt', _nil)
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	69 return dict_impl.__getattribute__(self, '_lt')
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	70
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	71 def _set_lt(self, val):
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	72 self._dict_impl().__setattr__(self, '_lt', val)
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	73
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	74 lt = property(_get_lt, _set_lt)
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	75
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	76 def __getitem__(self, key):
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	77 return self._dict_impl().__getitem__(self, key)[1]
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	78
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	79 def __setitem__(self, key, val):
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	80 dict_impl = self._dict_impl()
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	81 try:
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	82 dict_impl.__getitem__(self, key)[1] = val
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	83 except KeyError, e:
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	84 new = [dict_impl.__getattribute__(self, 'lt'), val, _nil]
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	85 dict_impl.__setitem__(self, key, new)
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	86 if dict_impl.__getattribute__(self, 'lt') == _nil:
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	87 dict_impl.__setattr__(self, 'lh', key)
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	88 else:
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	89 dict_impl.__getitem__(
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	90 self, dict_impl.__getattribute__(self, 'lt'))[2] = key
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	91 dict_impl.__setattr__(self, 'lt', key)
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	92
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	93 def __delitem__(self, key):
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	94 dict_impl = self._dict_impl()
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	95 pred, _ , succ = self._dict_impl().__getitem__(self, key)
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	96 if pred == _nil:
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	97 dict_impl.__setattr__(self, 'lh', succ)
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	98 else:
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	99 dict_impl.__getitem__(self, pred)[2] = succ
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	100 if succ == _nil:
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	101 dict_impl.__setattr__(self, 'lt', pred)
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	102 else:
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	103 dict_impl.__getitem__(self, succ)[0] = pred
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	104 dict_impl.__delitem__(self, key)
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	105
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	106 def __contains__(self, key):
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	107 return key in self.keys()
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	108
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	109 def __len__(self):
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	110 return len(self.keys())
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	111
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	112 def __str__(self):
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	113 pairs = ("%r: %r" % (k, v) for k, v in self.iteritems())
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	114 return "{%s}" % ", ".join(pairs)
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	115
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	116 def __repr__(self):
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	117 if self:
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	118 pairs = ("(%r, %r)" % (k, v) for k, v in self.iteritems())
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	119 return "odict([%s])" % ", ".join(pairs)
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	120 else:
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	121 return "odict()"
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	122
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	123 def get(self, k, x=None):
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	124 if k in self:
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	125 return self._dict_impl().__getitem__(self, k)[1]
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	126 else:
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	127 return x
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	128
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	129 def __iter__(self):
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	130 dict_impl = self._dict_impl()
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	131 curr_key = dict_impl.__getattribute__(self, 'lh')
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	132 while curr_key != _nil:
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	133 yield curr_key
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	134 curr_key = dict_impl.__getitem__(self, curr_key)[2]
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	135
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	136 iterkeys = __iter__
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	137
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	138 def keys(self):
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	139 return list(self.iterkeys())
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	140
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	141 def itervalues(self):
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	142 dict_impl = self._dict_impl()
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	143 curr_key = dict_impl.__getattribute__(self, 'lh')
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	144 while curr_key != _nil:
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	145 _, val, curr_key = dict_impl.__getitem__(self, curr_key)
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	146 yield val
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	147
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	148 def values(self):
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	149 return list(self.itervalues())
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	150
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	151 def iteritems(self):
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	152 dict_impl = self._dict_impl()
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	153 curr_key = dict_impl.__getattribute__(self, 'lh')
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	154 while curr_key != _nil:
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	155 _, val, next_key = dict_impl.__getitem__(self, curr_key)
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	156 yield curr_key, val
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	157 curr_key = next_key
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	158
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	159 def items(self):
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	160 return list(self.iteritems())
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	161
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	162 def sort(self, cmp=None, key=None, reverse=False):
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	163 items = [(k, v) for k, v in self.items()]
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	164 if cmp is not None:
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	165 items = sorted(items, cmp=cmp)
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	166 elif key is not None:
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	167 items = sorted(items, key=key)
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	168 else:
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	169 items = sorted(items, key=lambda x: x[1])
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	170 if reverse:
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	171 items.reverse()
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	172 self.clear()
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	173 self.__init__(items)
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	174
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	175 def clear(self):
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	176 dict_impl = self._dict_impl()
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	177 dict_impl.clear(self)
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	178 dict_impl.__setattr__(self, 'lh', _nil)
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	179 dict_impl.__setattr__(self, 'lt', _nil)
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	180
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	181 def copy(self):
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	182 return self.__class__(self)
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	183
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	184 def update(self, data=(), **kwds):
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	185 if kwds:
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	186 raise TypeError("update() of ordered dict takes no keyword "
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	187 "arguments to avoid an ordering trap.")
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	188 if hasattr(data, "iteritems"):
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	189 data = data.iteritems()
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	190 for key, val in data:
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	191 self[key] = val
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	192
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	193 def setdefault(self, k, x=None):
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	194 try:
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	195 return self[k]
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	196 except KeyError:
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	197 self[k] = x
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	198 return x
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	199
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	200 def pop(self, k, x=_nil):
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	201 try:
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	202 val = self[k]
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	203 del self[k]
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	204 return val
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	205 except KeyError:
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	206 if x == _nil:
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	207 raise
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	208 return x
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	209
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	210 def popitem(self):
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	211 try:
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	212 dict_impl = self._dict_impl()
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	213 key = dict_impl.__getattribute__(self, 'lt')
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	214 return key, self.pop(key)
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	215 except KeyError:
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	216 raise KeyError("'popitem(): ordered dictionary is empty'")
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	217
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	218 def riterkeys(self):
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	219 """To iterate on keys in reversed order.
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	220 """
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	221 dict_impl = self._dict_impl()
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	222 curr_key = dict_impl.__getattribute__(self, 'lt')
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	223 while curr_key != _nil:
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	224 yield curr_key
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	225 curr_key = dict_impl.__getitem__(self, curr_key)[0]
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	226
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	227 __reversed__ = riterkeys
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	228
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	229 def rkeys(self):
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	230 """List of the keys in reversed order.
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	231 """
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	232 return list(self.riterkeys())
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	233
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	234 def ritervalues(self):
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	235 """To iterate on values in reversed order.
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	236 """
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	237 dict_impl = self._dict_impl()
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	238 curr_key = dict_impl.__getattribute__(self, 'lt')
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	239 while curr_key != _nil:
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	240 curr_key, val, _ = dict_impl.__getitem__(self, curr_key)
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	241 yield val
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	242
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	243 def rvalues(self):
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	244 """List of the values in reversed order.
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	245 """
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	246 return list(self.ritervalues())
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	247
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	248 def riteritems(self):
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	249 """To iterate on (key, value) in reversed order.
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	250 """
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	251 dict_impl = self._dict_impl()
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	252 curr_key = dict_impl.__getattribute__(self, 'lt')
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	253 while curr_key != _nil:
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	254 pred_key, val, _ = dict_impl.__getitem__(self, curr_key)
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	255 yield curr_key, val
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	256 curr_key = pred_key
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	257
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	258 def ritems(self):
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	259 """List of the (key, value) in reversed order.
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	260 """
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	261 return list(self.riteritems())
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	262
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	263 def firstkey(self):
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	264 if self:
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	265 return self._dict_impl().__getattribute__(self, 'lh')
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	266 else:
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	267 raise KeyError("'firstkey(): ordered dictionary is empty'")
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	268
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	269 def lastkey(self):
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	270 if self:
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	271 return self._dict_impl().__getattribute__(self, 'lt')
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	272 else:
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	273 raise KeyError("'lastkey(): ordered dictionary is empty'")
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	274
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	275 def as_dict(self):
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	276 return self._dict_impl()(self.items())
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	277
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	278 def _repr(self):
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	279 """_repr(): low level repr of the whole data contained in the odict.
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	280 Useful for debugging.
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	281 """
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	282 dict_impl = self._dict_impl()
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	283 form = "odict low level repr lh,lt,data: %r, %r, %s"
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	284 return form % (dict_impl.__getattribute__(self, 'lh'),
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	285 dict_impl.__getattribute__(self, 'lt'),
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	286 dict_impl.__repr__(self))
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	287
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	288 class OrderedDict(_odict, dict):
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	289
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	290 def _dict_impl(self):
37625d304a16 Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation. Marcin Kuzminski <marcin@python-works.com> parents: diff changeset	291 return dict

Mercurial > kallithea

annotate rhodecode/lib/odict.py @ 1340:cbdd583f1e58 beta