Mercurial > kallithea

annotate rhodecode/lib/compat.py @ 3797:d7488551578e beta

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
synced vcs with upstream - moved subprocessio module to VCS - many small changes to make embedded vcs as similar to to external lib - use only absolute imports - patch vcs config during load pylons env
author Marcin Kuzminski <marcin@python-works.com>
date Sat, 27 Apr 2013 11:24:25 +0200
parents 4b7ad342e53b
children 2b9da8749065
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
1514
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
1 # -*- coding: utf-8 -*-
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
2 """
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
3 rhodecode.lib.compat
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
4 ~~~~~~~~~~~~~~~~~~~~
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
5
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
6 Python backward compatibility functions and common libs
1818
cf51bbfb120e auto white-space removal
Marcin Kuzminski <marcin@python-works.com>
parents: 1549
diff changeset
7
cf51bbfb120e auto white-space removal
Marcin Kuzminski <marcin@python-works.com>
parents: 1549
diff changeset
8
1514
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
9 :created_on: Oct 7, 2011
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
10 :author: marcink
1824
89efedac4e6c 2012 copyrights
Marcin Kuzminski <marcin@python-works.com>
parents: 1818
diff changeset
11 :copyright: (C) 2010-2010 Marcin Kuzminski <marcin@python-works.com>
1514
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
12 :license: GPLv3, see COPYING for more details.
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
13 """
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
14 # This program is free software: you can redistribute it and/or modify
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
15 # it under the terms of the GNU General Public License as published by
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
16 # the Free Software Foundation, either version 3 of the License, or
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
17 # (at your option) any later version.
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
18 #
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
19 # This program is distributed in the hope that it will be useful,
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
20 # but WITHOUT ANY WARRANTY; without even the implied warranty of
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
21 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
22 # GNU General Public License for more details.
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
23 #
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
24 # You should have received a copy of the GNU General Public License
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
25 # along with this program. If not, see <http://www.gnu.org/licenses/>.
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
26
1549
d6cb805c92fd moved kill function to compat
Marcin Kuzminski <marcin@python-works.com>
parents: 1514
diff changeset
27 import os
3797
d7488551578e synced vcs with upstream
Marcin Kuzminski <marcin@python-works.com>
parents: 2826
diff changeset
28 from rhodecode import __py_version__, is_windows
1549
d6cb805c92fd moved kill function to compat
Marcin Kuzminski <marcin@python-works.com>
parents: 1514
diff changeset
29
1514
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
30 #==============================================================================
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
31 # json
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
32 #==============================================================================
2173
775a7672d363 add ext_json module
Marcin Kuzminski <marcin@python-works.com>
parents: 2160
diff changeset
33 from rhodecode.lib.ext_json import json
2151
12ceeda33339 #404 API extensions for showing permission for users
Marcin Kuzminski <marcin@python-works.com>
parents: 2068
diff changeset
34
1514
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
35
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
36 #==============================================================================
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
37 # izip_longest
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
38 #==============================================================================
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
39 try:
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
40 from itertools import izip_longest
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
41 except ImportError:
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
42 import itertools
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
43
2151
12ceeda33339 #404 API extensions for showing permission for users
Marcin Kuzminski <marcin@python-works.com>
parents: 2068
diff changeset
44 def izip_longest(*args, **kwds):
1514
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
45 fillvalue = kwds.get("fillvalue")
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
46
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
47 def sentinel(counter=([fillvalue] * (len(args) - 1)).pop):
2151
12ceeda33339 #404 API extensions for showing permission for users
Marcin Kuzminski <marcin@python-works.com>
parents: 2068
diff changeset
48 yield counter() # yields the fillvalue, or raises IndexError
1514
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
49
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
50 fillers = itertools.repeat(fillvalue)
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
51 iters = [itertools.chain(it, sentinel(), fillers)
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
52 for it in args]
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
53 try:
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
54 for tup in itertools.izip(*iters):
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
55 yield tup
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
56 except IndexError:
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
57 pass
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
58
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
59
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
60 #==============================================================================
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
61 # OrderedDict
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
62 #==============================================================================
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
63
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
64 # Python Software Foundation License
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
65
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
66 # XXX: it feels like using the class with "is" and "is not" instead of "==" and
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
67 # "!=" should be faster.
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
68 class _Nil(object):
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
69
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
70 def __repr__(self):
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
71 return "nil"
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
72
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
73 def __eq__(self, other):
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
74 if (isinstance(other, _Nil)):
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
75 return True
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
76 else:
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
77 return NotImplemented
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
78
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
79 def __ne__(self, other):
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
80 if (isinstance(other, _Nil)):
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
81 return False
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
82 else:
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
83 return NotImplemented
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
84
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
85 _nil = _Nil()
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
86
1890
a3efaaa6ed4f fixes issue #271
Marcin Kuzminski <marcin@python-works.com>
parents: 1824
diff changeset
87
1514
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
88 class _odict(object):
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
89 """Ordered dict data structure, with O(1) complexity for dict operations
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
90 that modify one element.
1818
cf51bbfb120e auto white-space removal
Marcin Kuzminski <marcin@python-works.com>
parents: 1549
diff changeset
91
1514
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
92 Overwriting values doesn't change their original sequential order.
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
93 """
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
94
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
95 def _dict_impl(self):
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
96 return None
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
97
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
98 def __init__(self, data=(), **kwds):
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
99 """This doesn't accept keyword initialization as normal dicts to avoid
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
100 a trap - inside a function or method the keyword args are accessible
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
101 only as a dict, without a defined order, so their original order is
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
102 lost.
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
103 """
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
104 if kwds:
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
105 raise TypeError("__init__() of ordered dict takes no keyword "
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
106 "arguments to avoid an ordering trap.")
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
107 self._dict_impl().__init__(self)
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
108 # If you give a normal dict, then the order of elements is undefined
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
109 if hasattr(data, "iteritems"):
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
110 for key, val in data.iteritems():
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
111 self[key] = val
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
112 else:
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
113 for key, val in data:
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
114 self[key] = val
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
115
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
116 # Double-linked list header
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
117 def _get_lh(self):
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
118 dict_impl = self._dict_impl()
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
119 if not hasattr(self, '_lh'):
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
120 dict_impl.__setattr__(self, '_lh', _nil)
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
121 return dict_impl.__getattribute__(self, '_lh')
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
122
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
123 def _set_lh(self, val):
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
124 self._dict_impl().__setattr__(self, '_lh', val)
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
125
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
126 lh = property(_get_lh, _set_lh)
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
127
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
128 # Double-linked list tail
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
129 def _get_lt(self):
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
130 dict_impl = self._dict_impl()
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
131 if not hasattr(self, '_lt'):
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
132 dict_impl.__setattr__(self, '_lt', _nil)
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
133 return dict_impl.__getattribute__(self, '_lt')
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
134
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
135 def _set_lt(self, val):
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
136 self._dict_impl().__setattr__(self, '_lt', val)
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
137
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
138 lt = property(_get_lt, _set_lt)
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
139
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
140 def __getitem__(self, key):
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
141 return self._dict_impl().__getitem__(self, key)[1]
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
142
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
143 def __setitem__(self, key, val):
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
144 dict_impl = self._dict_impl()
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
145 try:
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
146 dict_impl.__getitem__(self, key)[1] = val
1890
a3efaaa6ed4f fixes issue #271
Marcin Kuzminski <marcin@python-works.com>
parents: 1824
diff changeset
147 except KeyError:
1514
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
148 new = [dict_impl.__getattribute__(self, 'lt'), val, _nil]
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
149 dict_impl.__setitem__(self, key, new)
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
150 if dict_impl.__getattribute__(self, 'lt') == _nil:
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
151 dict_impl.__setattr__(self, 'lh', key)
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
152 else:
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
153 dict_impl.__getitem__(
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
154 self, dict_impl.__getattribute__(self, 'lt'))[2] = key
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
155 dict_impl.__setattr__(self, 'lt', key)
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
156
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
157 def __delitem__(self, key):
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
158 dict_impl = self._dict_impl()
1890
a3efaaa6ed4f fixes issue #271
Marcin Kuzminski <marcin@python-works.com>
parents: 1824
diff changeset
159 pred, _, succ = self._dict_impl().__getitem__(self, key)
1514
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
160 if pred == _nil:
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
161 dict_impl.__setattr__(self, 'lh', succ)
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
162 else:
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
163 dict_impl.__getitem__(self, pred)[2] = succ
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
164 if succ == _nil:
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
165 dict_impl.__setattr__(self, 'lt', pred)
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
166 else:
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
167 dict_impl.__getitem__(self, succ)[0] = pred
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
168 dict_impl.__delitem__(self, key)
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
169
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
170 def __contains__(self, key):
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
171 return key in self.keys()
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
172
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
173 def __len__(self):
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
174 return len(self.keys())
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
175
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
176 def __str__(self):
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
177 pairs = ("%r: %r" % (k, v) for k, v in self.iteritems())
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
178 return "{%s}" % ", ".join(pairs)
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
179
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
180 def __repr__(self):
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
181 if self:
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
182 pairs = ("(%r, %r)" % (k, v) for k, v in self.iteritems())
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
183 return "odict([%s])" % ", ".join(pairs)
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
184 else:
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
185 return "odict()"
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
186
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
187 def get(self, k, x=None):
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
188 if k in self:
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
189 return self._dict_impl().__getitem__(self, k)[1]
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
190 else:
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
191 return x
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
192
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
193 def __iter__(self):
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
194 dict_impl = self._dict_impl()
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
195 curr_key = dict_impl.__getattribute__(self, 'lh')
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
196 while curr_key != _nil:
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
197 yield curr_key
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
198 curr_key = dict_impl.__getitem__(self, curr_key)[2]
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
199
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
200 iterkeys = __iter__
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
201
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
202 def keys(self):
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
203 return list(self.iterkeys())
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
204
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
205 def itervalues(self):
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
206 dict_impl = self._dict_impl()
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
207 curr_key = dict_impl.__getattribute__(self, 'lh')
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
208 while curr_key != _nil:
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
209 _, val, curr_key = dict_impl.__getitem__(self, curr_key)
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
210 yield val
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
211
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
212 def values(self):
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
213 return list(self.itervalues())
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
214
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
215 def iteritems(self):
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
216 dict_impl = self._dict_impl()
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
217 curr_key = dict_impl.__getattribute__(self, 'lh')
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
218 while curr_key != _nil:
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
219 _, val, next_key = dict_impl.__getitem__(self, curr_key)
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
220 yield curr_key, val
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
221 curr_key = next_key
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
222
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
223 def items(self):
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
224 return list(self.iteritems())
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
225
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
226 def sort(self, cmp=None, key=None, reverse=False):
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
227 items = [(k, v) for k, v in self.items()]
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
228 if cmp is not None:
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
229 items = sorted(items, cmp=cmp)
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
230 elif key is not None:
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
231 items = sorted(items, key=key)
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
232 else:
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
233 items = sorted(items, key=lambda x: x[1])
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
234 if reverse:
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
235 items.reverse()
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
236 self.clear()
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
237 self.__init__(items)
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
238
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
239 def clear(self):
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
240 dict_impl = self._dict_impl()
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
241 dict_impl.clear(self)
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
242 dict_impl.__setattr__(self, 'lh', _nil)
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
243 dict_impl.__setattr__(self, 'lt', _nil)
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
244
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
245 def copy(self):
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
246 return self.__class__(self)
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
247
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
248 def update(self, data=(), **kwds):
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
249 if kwds:
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
250 raise TypeError("update() of ordered dict takes no keyword "
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
251 "arguments to avoid an ordering trap.")
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
252 if hasattr(data, "iteritems"):
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
253 data = data.iteritems()
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
254 for key, val in data:
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
255 self[key] = val
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
256
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
257 def setdefault(self, k, x=None):
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
258 try:
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
259 return self[k]
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
260 except KeyError:
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
261 self[k] = x
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
262 return x
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
263
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
264 def pop(self, k, x=_nil):
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
265 try:
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
266 val = self[k]
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
267 del self[k]
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
268 return val
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
269 except KeyError:
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
270 if x == _nil:
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
271 raise
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
272 return x
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
273
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
274 def popitem(self):
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
275 try:
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
276 dict_impl = self._dict_impl()
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
277 key = dict_impl.__getattribute__(self, 'lt')
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
278 return key, self.pop(key)
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
279 except KeyError:
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
280 raise KeyError("'popitem(): ordered dictionary is empty'")
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
281
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
282 def riterkeys(self):
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
283 """To iterate on keys in reversed order.
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
284 """
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
285 dict_impl = self._dict_impl()
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
286 curr_key = dict_impl.__getattribute__(self, 'lt')
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
287 while curr_key != _nil:
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
288 yield curr_key
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
289 curr_key = dict_impl.__getitem__(self, curr_key)[0]
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
290
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
291 __reversed__ = riterkeys
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
292
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
293 def rkeys(self):
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
294 """List of the keys in reversed order.
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
295 """
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
296 return list(self.riterkeys())
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
297
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
298 def ritervalues(self):
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
299 """To iterate on values in reversed order.
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
300 """
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
301 dict_impl = self._dict_impl()
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
302 curr_key = dict_impl.__getattribute__(self, 'lt')
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
303 while curr_key != _nil:
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
304 curr_key, val, _ = dict_impl.__getitem__(self, curr_key)
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
305 yield val
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
306
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
307 def rvalues(self):
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
308 """List of the values in reversed order.
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
309 """
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
310 return list(self.ritervalues())
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
311
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
312 def riteritems(self):
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
313 """To iterate on (key, value) in reversed order.
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
314 """
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
315 dict_impl = self._dict_impl()
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
316 curr_key = dict_impl.__getattribute__(self, 'lt')
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
317 while curr_key != _nil:
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
318 pred_key, val, _ = dict_impl.__getitem__(self, curr_key)
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
319 yield curr_key, val
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
320 curr_key = pred_key
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
321
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
322 def ritems(self):
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
323 """List of the (key, value) in reversed order.
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
324 """
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
325 return list(self.riteritems())
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
326
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
327 def firstkey(self):
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
328 if self:
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
329 return self._dict_impl().__getattribute__(self, 'lh')
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
330 else:
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
331 raise KeyError("'firstkey(): ordered dictionary is empty'")
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
332
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
333 def lastkey(self):
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
334 if self:
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
335 return self._dict_impl().__getattribute__(self, 'lt')
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
336 else:
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
337 raise KeyError("'lastkey(): ordered dictionary is empty'")
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
338
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
339 def as_dict(self):
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
340 return self._dict_impl()(self.items())
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
341
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
342 def _repr(self):
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
343 """_repr(): low level repr of the whole data contained in the odict.
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
344 Useful for debugging.
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
345 """
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
346 dict_impl = self._dict_impl()
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
347 form = "odict low level repr lh,lt,data: %r, %r, %s"
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
348 return form % (dict_impl.__getattribute__(self, 'lh'),
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
349 dict_impl.__getattribute__(self, 'lt'),
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
350 dict_impl.__repr__(self))
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
351
1890
a3efaaa6ed4f fixes issue #271
Marcin Kuzminski <marcin@python-works.com>
parents: 1824
diff changeset
352
1514
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
353 class OrderedDict(_odict, dict):
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
354
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
355 def _dict_impl(self):
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
356 return dict
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
357
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
358
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
359 #==============================================================================
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
360 # OrderedSet
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
361 #==============================================================================
87ec80c280bb fixed issues with python2.5
Marcin Kuzminski <marcin@python-works.com>
parents:
diff changeset
362 from sqlalchemy.util import OrderedSet
1549
d6cb805c92fd moved kill function to compat
Marcin Kuzminski <marcin@python-works.com>
parents: 1514
diff changeset
363
d6cb805c92fd moved kill function to compat
Marcin Kuzminski <marcin@python-works.com>
parents: 1514
diff changeset
364
d6cb805c92fd moved kill function to compat
Marcin Kuzminski <marcin@python-works.com>
parents: 1514
diff changeset
365 #==============================================================================
d6cb805c92fd moved kill function to compat
Marcin Kuzminski <marcin@python-works.com>
parents: 1514
diff changeset
366 # kill FUNCTIONS
d6cb805c92fd moved kill function to compat
Marcin Kuzminski <marcin@python-works.com>
parents: 1514
diff changeset
367 #==============================================================================
3797
d7488551578e synced vcs with upstream
Marcin Kuzminski <marcin@python-works.com>
parents: 2826
diff changeset
368 if is_windows:
1549
d6cb805c92fd moved kill function to compat
Marcin Kuzminski <marcin@python-works.com>
parents: 1514
diff changeset
369 import ctypes
d6cb805c92fd moved kill function to compat
Marcin Kuzminski <marcin@python-works.com>
parents: 1514
diff changeset
370
d6cb805c92fd moved kill function to compat
Marcin Kuzminski <marcin@python-works.com>
parents: 1514
diff changeset
371 def kill(pid, sig):
d6cb805c92fd moved kill function to compat
Marcin Kuzminski <marcin@python-works.com>
parents: 1514
diff changeset
372 """kill function for Win32"""
d6cb805c92fd moved kill function to compat
Marcin Kuzminski <marcin@python-works.com>
parents: 1514
diff changeset
373 kernel32 = ctypes.windll.kernel32
d6cb805c92fd moved kill function to compat
Marcin Kuzminski <marcin@python-works.com>
parents: 1514
diff changeset
374 handle = kernel32.OpenProcess(1, 0, pid)
d6cb805c92fd moved kill function to compat
Marcin Kuzminski <marcin@python-works.com>
parents: 1514
diff changeset
375 return (0 != kernel32.TerminateProcess(handle, 0))
d6cb805c92fd moved kill function to compat
Marcin Kuzminski <marcin@python-works.com>
parents: 1514
diff changeset
376
d6cb805c92fd moved kill function to compat
Marcin Kuzminski <marcin@python-works.com>
parents: 1514
diff changeset
377 else:
d6cb805c92fd moved kill function to compat
Marcin Kuzminski <marcin@python-works.com>
parents: 1514
diff changeset
378 kill = os.kill
2068
f664d3b57fa4 p2.5 fixes
Marcin Kuzminski <marcin@python-works.com>
parents: 1890
diff changeset
379
f664d3b57fa4 p2.5 fixes
Marcin Kuzminski <marcin@python-works.com>
parents: 1890
diff changeset
380
f664d3b57fa4 p2.5 fixes
Marcin Kuzminski <marcin@python-works.com>
parents: 1890
diff changeset
381 #==============================================================================
f664d3b57fa4 p2.5 fixes
Marcin Kuzminski <marcin@python-works.com>
parents: 1890
diff changeset
382 # itertools.product
f664d3b57fa4 p2.5 fixes
Marcin Kuzminski <marcin@python-works.com>
parents: 1890
diff changeset
383 #==============================================================================
f664d3b57fa4 p2.5 fixes
Marcin Kuzminski <marcin@python-works.com>
parents: 1890
diff changeset
384
f664d3b57fa4 p2.5 fixes
Marcin Kuzminski <marcin@python-works.com>
parents: 1890
diff changeset
385 try:
f664d3b57fa4 p2.5 fixes
Marcin Kuzminski <marcin@python-works.com>
parents: 1890
diff changeset
386 from itertools import product
f664d3b57fa4 p2.5 fixes
Marcin Kuzminski <marcin@python-works.com>
parents: 1890
diff changeset
387 except ImportError:
f664d3b57fa4 p2.5 fixes
Marcin Kuzminski <marcin@python-works.com>
parents: 1890
diff changeset
388 def product(*args, **kwds):
f664d3b57fa4 p2.5 fixes
Marcin Kuzminski <marcin@python-works.com>
parents: 1890
diff changeset
389 # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
f664d3b57fa4 p2.5 fixes
Marcin Kuzminski <marcin@python-works.com>
parents: 1890
diff changeset
390 # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
f664d3b57fa4 p2.5 fixes
Marcin Kuzminski <marcin@python-works.com>
parents: 1890
diff changeset
391 pools = map(tuple, args) * kwds.get('repeat', 1)
f664d3b57fa4 p2.5 fixes
Marcin Kuzminski <marcin@python-works.com>
parents: 1890
diff changeset
392 result = [[]]
f664d3b57fa4 p2.5 fixes
Marcin Kuzminski <marcin@python-works.com>
parents: 1890
diff changeset
393 for pool in pools:
f664d3b57fa4 p2.5 fixes
Marcin Kuzminski <marcin@python-works.com>
parents: 1890
diff changeset
394 result = [x + [y] for x in result for y in pool]
f664d3b57fa4 p2.5 fixes
Marcin Kuzminski <marcin@python-works.com>
parents: 1890
diff changeset
395 for prod in result:
f664d3b57fa4 p2.5 fixes
Marcin Kuzminski <marcin@python-works.com>
parents: 1890
diff changeset
396 yield tuple(prod)
2552
e8650fbc4d4e Moved BytesIO into compat because of py25 compatibility issue
Marcin Kuzminski <marcin@python-works.com>
parents: 2173
diff changeset
397
e8650fbc4d4e Moved BytesIO into compat because of py25 compatibility issue
Marcin Kuzminski <marcin@python-works.com>
parents: 2173
diff changeset
398
e8650fbc4d4e Moved BytesIO into compat because of py25 compatibility issue
Marcin Kuzminski <marcin@python-works.com>
parents: 2173
diff changeset
399 #==============================================================================
e8650fbc4d4e Moved BytesIO into compat because of py25 compatibility issue
Marcin Kuzminski <marcin@python-works.com>
parents: 2173
diff changeset
400 # BytesIO
e8650fbc4d4e Moved BytesIO into compat because of py25 compatibility issue
Marcin Kuzminski <marcin@python-works.com>
parents: 2173
diff changeset
401 #==============================================================================
e8650fbc4d4e Moved BytesIO into compat because of py25 compatibility issue
Marcin Kuzminski <marcin@python-works.com>
parents: 2173
diff changeset
402
e8650fbc4d4e Moved BytesIO into compat because of py25 compatibility issue
Marcin Kuzminski <marcin@python-works.com>
parents: 2173
diff changeset
403 try:
e8650fbc4d4e Moved BytesIO into compat because of py25 compatibility issue
Marcin Kuzminski <marcin@python-works.com>
parents: 2173
diff changeset
404 from io import BytesIO
e8650fbc4d4e Moved BytesIO into compat because of py25 compatibility issue
Marcin Kuzminski <marcin@python-works.com>
parents: 2173
diff changeset
405 except ImportError:
e8650fbc4d4e Moved BytesIO into compat because of py25 compatibility issue
Marcin Kuzminski <marcin@python-works.com>
parents: 2173
diff changeset
406 from cStringIO import StringIO as BytesIO
2729
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
407
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
408
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
409 #==============================================================================
2790
3c0ae44557c4 more py2.5 compatibility patches
Marcin Kuzminski <marcin@python-works.com>
parents: 2730
diff changeset
410 # bytes
3c0ae44557c4 more py2.5 compatibility patches
Marcin Kuzminski <marcin@python-works.com>
parents: 2730
diff changeset
411 #==============================================================================
3c0ae44557c4 more py2.5 compatibility patches
Marcin Kuzminski <marcin@python-works.com>
parents: 2730
diff changeset
412 if __py_version__ >= (2, 6):
3c0ae44557c4 more py2.5 compatibility patches
Marcin Kuzminski <marcin@python-works.com>
parents: 2730
diff changeset
413 _bytes = bytes
3c0ae44557c4 more py2.5 compatibility patches
Marcin Kuzminski <marcin@python-works.com>
parents: 2730
diff changeset
414 else:
3c0ae44557c4 more py2.5 compatibility patches
Marcin Kuzminski <marcin@python-works.com>
parents: 2730
diff changeset
415 # in py2.6 bytes is a synonim for str
3c0ae44557c4 more py2.5 compatibility patches
Marcin Kuzminski <marcin@python-works.com>
parents: 2730
diff changeset
416 _bytes = str
3c0ae44557c4 more py2.5 compatibility patches
Marcin Kuzminski <marcin@python-works.com>
parents: 2730
diff changeset
417
2826
4b7ad342e53b python2.5 fixes !
Marcin Kuzminski <marcin@python-works.com>
parents: 2815
diff changeset
418 if __py_version__ >= (2, 6):
4b7ad342e53b python2.5 fixes !
Marcin Kuzminski <marcin@python-works.com>
parents: 2815
diff changeset
419 _bytearray = bytearray
4b7ad342e53b python2.5 fixes !
Marcin Kuzminski <marcin@python-works.com>
parents: 2815
diff changeset
420 else:
3797
d7488551578e synced vcs with upstream
Marcin Kuzminski <marcin@python-works.com>
parents: 2826
diff changeset
421 import array
2826
4b7ad342e53b python2.5 fixes !
Marcin Kuzminski <marcin@python-works.com>
parents: 2815
diff changeset
422 # no idea if this is correct but all integration tests are passing
4b7ad342e53b python2.5 fixes !
Marcin Kuzminski <marcin@python-works.com>
parents: 2815
diff changeset
423 # i think we never use bytearray anyway
4b7ad342e53b python2.5 fixes !
Marcin Kuzminski <marcin@python-works.com>
parents: 2815
diff changeset
424 _bytearray = array
4b7ad342e53b python2.5 fixes !
Marcin Kuzminski <marcin@python-works.com>
parents: 2815
diff changeset
425
4b7ad342e53b python2.5 fixes !
Marcin Kuzminski <marcin@python-works.com>
parents: 2815
diff changeset
426
2790
3c0ae44557c4 more py2.5 compatibility patches
Marcin Kuzminski <marcin@python-works.com>
parents: 2730
diff changeset
427 #==============================================================================
2729
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
428 # deque
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
429 #==============================================================================
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
430
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
431 if __py_version__ >= (2, 6):
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
432 from collections import deque
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
433 else:
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
434 #need to implement our own deque with maxlen
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
435 class deque(object):
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
436
2790
3c0ae44557c4 more py2.5 compatibility patches
Marcin Kuzminski <marcin@python-works.com>
parents: 2730
diff changeset
437 def __init__(self, iterable=(), maxlen= -1):
2729
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
438 if not hasattr(self, 'data'):
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
439 self.left = self.right = 0
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
440 self.data = {}
2790
3c0ae44557c4 more py2.5 compatibility patches
Marcin Kuzminski <marcin@python-works.com>
parents: 2730
diff changeset
441 self.maxlen = maxlen or -1
2729
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
442 self.extend(iterable)
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
443
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
444 def append(self, x):
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
445 self.data[self.right] = x
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
446 self.right += 1
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
447 if self.maxlen != -1 and len(self) > self.maxlen:
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
448 self.popleft()
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
449
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
450 def appendleft(self, x):
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
451 self.left -= 1
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
452 self.data[self.left] = x
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
453 if self.maxlen != -1 and len(self) > self.maxlen:
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
454 self.pop()
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
455
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
456 def pop(self):
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
457 if self.left == self.right:
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
458 raise IndexError('cannot pop from empty deque')
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
459 self.right -= 1
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
460 elem = self.data[self.right]
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
461 del self.data[self.right]
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
462 return elem
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
463
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
464 def popleft(self):
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
465 if self.left == self.right:
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
466 raise IndexError('cannot pop from empty deque')
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
467 elem = self.data[self.left]
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
468 del self.data[self.left]
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
469 self.left += 1
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
470 return elem
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
471
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
472 def clear(self):
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
473 self.data.clear()
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
474 self.left = self.right = 0
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
475
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
476 def extend(self, iterable):
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
477 for elem in iterable:
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
478 self.append(elem)
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
479
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
480 def extendleft(self, iterable):
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
481 for elem in iterable:
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
482 self.appendleft(elem)
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
483
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
484 def rotate(self, n=1):
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
485 if self:
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
486 n %= len(self)
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
487 for i in xrange(n):
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
488 self.appendleft(self.pop())
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
489
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
490 def __getitem__(self, i):
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
491 if i < 0:
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
492 i += len(self)
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
493 try:
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
494 return self.data[i + self.left]
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
495 except KeyError:
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
496 raise IndexError
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
497
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
498 def __setitem__(self, i, value):
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
499 if i < 0:
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
500 i += len(self)
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
501 try:
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
502 self.data[i + self.left] = value
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
503 except KeyError:
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
504 raise IndexError
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
505
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
506 def __delitem__(self, i):
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
507 size = len(self)
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
508 if not (-size <= i < size):
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
509 raise IndexError
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
510 data = self.data
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
511 if i < 0:
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
512 i += size
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
513 for j in xrange(self.left + i, self.right - 1):
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
514 data[j] = data[j + 1]
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
515 self.pop()
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
516
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
517 def __len__(self):
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
518 return self.right - self.left
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
519
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
520 def __cmp__(self, other):
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
521 if type(self) != type(other):
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
522 return cmp(type(self), type(other))
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
523 return cmp(list(self), list(other))
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
524
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
525 def __repr__(self, _track=[]):
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
526 if id(self) in _track:
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
527 return '...'
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
528 _track.append(id(self))
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
529 r = 'deque(%r, maxlen=%s)' % (list(self), self.maxlen)
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
530 _track.remove(id(self))
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
531 return r
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
532
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
533 def __getstate__(self):
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
534 return (tuple(self),)
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
535
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
536 def __setstate__(self, s):
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
537 self.__init__(s[0])
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
538
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
539 def __hash__(self):
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
540 raise TypeError
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
541
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
542 def __copy__(self):
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
543 return self.__class__(self)
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
544
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
545 def __deepcopy__(self, memo={}):
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
546 from copy import deepcopy
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
547 result = self.__class__()
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
548 memo[id(self)] = result
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
549 result.__init__(deepcopy(tuple(self), memo))
e9e7c40b4f1a added deque with maxlen for py2.5 compat
Marcin Kuzminski <marcin@python-works.com>
parents: 2552
diff changeset
550 return result