8000 Implementation of OrderedDict for python 2.6 · fariza/matplotlib@043d32f · GitHub
[go: up one dir, main page]
Skip to content

Commit 043d32f

Browse files
OceanWolfOceanWolf
committed
Implementation of OrderedDict for python 2.6
1 parent a756229 commit 043d32f

File tree

2 files changed

+267
-1
lines changed

2 files changed

+267
-1
lines changed

‎lib/matplotlib/backend_bases.py

Lines changed: 5 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -46,7 +46,11 @@
4646
import warnings
4747
import time
4848
import io
49-
from collections import OrderedDict
49+
try:
50+
from collections import OrderedDict
51+
except:
52+
# simple python 2.6 implementation, core-features only
53+
from matplotlib.cbook import OrderedDict
5054

5155
import numpy as np
5256
import matplotlib.cbook as cbook

‎lib/matplotlib/cbook.py

Lines changed: 262 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2327,3 +2327,265 @@ def get_instancemethod(self):
23272327
else:
23282328
def _putmask(a, mask, values):
23292329
return np.copyto(a, values, where=mask)
2330+
2331+
# TODO Remove when the following code when we no longer support python-2.6
2332+
# Code taken from http://code.activestate.com/recipes/576693/ referenced from
2333+
# https://docs.python.org/2/library/collections.html#collections.OrderedDict
2334+
# Backport of OrderedDict() class that runs on Python 2.4, 2.5, 2.6, 2.7 and pypy.
2335+
# Passes Python2.7's test suite and incorporates all the latest updates.
2336+
2337+
try:
2338+
from thread import get_ident as _get_ident
2339+
except ImportError:
2340+
from dummy_thread import get_ident as _get_ident
2341+
2342+
try:
2343+
from _abcoll import KeysView, ValuesView, ItemsView
2344+
except ImportError:
2345+
pass
2346+
2347+
2348+
class OrderedDict(dict):
2349+
'Dictionary that remembers insertion order'
2350+
# An inherited dict maps keys to values.
2351+
# The inherited dict provides __getitem__, __len__, __contains__, and get.
2352+
# The remaining methods are order-aware.
2353+
# Big-O running times for all methods are the same as for regular dictionaries.
2354+
2355+
# The internal self.__map dictionary maps keys to links in a doubly linked list.
2356+
# The circular doubly linked list starts and ends with a sentinel element.
2357+
# The sentinel element never gets deleted (this simplifies the algorithm).
2358+
# Each link is stored as a list of length three: [PREV, NEXT, KEY].
2359+
2360+
def __init__(self, *args, **kwds):
2361+
'''Initialize an ordered dictionary. Signature is the same as for
2362+
regular dictionaries, but keyword arguments are not recommended
2363+
because their insertion order is arbitrary.
2364+
2365+
'''
2366+
if len(args) > 1:
2367+
raise TypeError('expected at most 1 arguments, got %d' % len(args))
2368+
try:
2369+
self.__root
2370+
except AttributeError:
2371+
self.__root = root = [] # sentinel node
2372+
root[:] = [root, root, None]
2373+
self.__map = {}
2374+
self.__update(*args, **kwds)
2375+
2376+
def __setitem__(self, key, value, dict_setitem=dict.__setitem__):
2377+
'od.__setitem__(i, y) <==> od[i]=y'
2378+
# Setting a new item creates a new link which goes at the end of the linked
2379+
# list, and the inherited dictionary is updated with the new key/value pair.
2380+
if key not in self:
2381+
root = self.__root
2382+
last = root[0]
2383+
last[1] = root[0] = self.__map[key] = [last, root, key]
2384+
dict_setitem(self, key, value)
2385+
2386+
def __delitem__(self, key, dict_delitem=dict.__delitem__):
2387+
'od.__delitem__(y) <==> del od[y]'
2388+
# Deleting an existing item uses self.__map to find the link which is
2389+
# then removed by updating the links in the predecessor and successor nodes.
2390+
dict_delitem(self, key)
2391+
link_prev, link_next, key = self.__map.pop(key)
2392+
link_prev[1] = link_next
2393+
link_next[0] = link_prev
2394+
2395+
def __iter__(self):
2396+
'od.__iter__() <==> iter(od)'
2397+
root = self.__root
2398+
curr = root[1]
2399+
while curr is not root:
2400+
yield curr[2]
2401+
curr = curr[1]
2402+
2403+
def __reversed__(self):
2404+
'od.__reversed__() <==> reversed(od)'
2405+
root = self.__root
2406+
curr = root[0]
2407+
while curr is not root:
2408+
yield curr[2]
2409+
curr = curr[0]
2410+
2411+
def clear(self):
2412+
'od.clear() -> None. Remove all items from od.'
2413+
try:
2414+
for node in self.__map.itervalues():
2415+
del node[:]
2416+
root = self.__root
2417+
root[:] = [root, root, None]
2418+
self.__map.clear()
2419+
except AttributeError:
2420+
pass
2421+
dict.clear(self)
2422+
2423+
def popitem(self, last=True):
2424+
'''od.popitem() -> (k, v), return and remove a (key, value) pair.
2425+
Pairs are returned in LIFO order if last is true or FIFO order if false.
2426+
2427+
'''
2428+
if not self:
2429+
raise KeyError('dictionary is empty')
2430+
root = self.__root
2431+
if last:
2432+
link = root[0]
2433+
link_prev = link[0]
2434+
link_prev[1] = root
2435+
root[0] = link_prev
2436+
else:
2437+
link = root[1]
2438+
link_next = link[1]
2439+
root[1] = link_next
2440+
link_next[0] = root
2441+
key = link[2]
2442+
del self.__map[key]
2443+
value = dict.pop(self, key)
2444+
return key, value
2445+
2446+
# -- the following methods do not depend on the internal structure --
2447+
2448+
def keys(self):
2449+
'od.keys() -> list of keys in od'
2450+
return list(self)
2451+
2452+
def values(self):
2453+
'od.values() -> list of values in od'
2454+
return [self[key] for key in self]
2455+
2456+
def items(self):
2457+
'od.items() -> list of (key, value) pairs in od'
2458+
return [(key, self[key]) for key in self]
2459+
2460+
def iterkeys(self):
2461+
'od.iterkeys() -> an iterator over the keys in od'
2462+
return iter(self)
2463+
2464+
def itervalues(self):
2465+
'od.itervalues -> an iterator over the values in od'
2466+
for k in self:
2467+
yield self[k]
2468+
2469+
def iteritems(self):
2470+
'od.iteritems -> an iterator over the (key, value) items in od'
2471+
for k in self:
2472+
yield (k, self[k])
2473+
2474+
def update(*args, **kwds):
2475+
'''od.update(E, **F) -> None. Update od from dict/iterable E and F.
2476+
2477+
If E is a dict instance, does: for k in E: od[k] = E[k]
2478+
If E has a .keys() method, does: for k in E.keys(): od[k] = E[k]
2479+
Or if E is an iterable of items, does: for k, v in E: od[k] = v
2480+
In either case, this is followed by: for k, v in F.items(): od[k] = v
2481+
2482+
'''
2483+
if len(args) > 2:
2484+
raise TypeError('update() takes at most 2 positional '
2485+
'arguments (%d given)' % (len(args),))
2486+
elif not args:
2487+
raise TypeError('update() takes at least 1 argument (0 given)')
2488+
self = args[0]
2489+
# Make progressively weaker assumptions about "other"
2490+
other = ()
2491+
if len(args) == 2:
2492+
other = args[1]
2493+
if isinstance(other, dict):
2494+
for key in other:
2495+
self[key] = other[key]
2496+
elif hasattr(other, 'keys'):
2497+
for key in other.keys():
2498+
self[key] = other[key]
2499+
else:
2500+
for key, value in other:
2501+
self[key] = value
2502+
for key, value in kwds.items():
2503+
self[key] = value
2504+
2505+
__update = update # let subclasses override update without breaking __init__
2506+
2507+
__marker = object()
2508+
2509+
def pop(self, key, default=__marker):
2510+
'''od.pop(k[,d]) -> v, remove specified key and return the corresponding value.
2511+
If key is not found, d is returned if given, otherwise KeyError is raised.
2512+
2513+
'''
2514+
if key in self:
2515+
result = self[key]
2516+
del self[key]
2517+
return result
2518+
if default is self.__marker:
2519+
raise KeyError(key)
2520+
return default
2521+
2522+
def setdefault(self, key, default=None):
2523+
'od.setdefault(k[,d]) -> od.get(k,d), also set od[k]=d if k not in od'
2524+
if key in self:
2525+
return self[key]
2526+
self[key] = default
2527+
return default
2528+
2529+
def __repr__(self, _repr_running={}):
2530+
'od.__repr__() <==> repr(od)'
2531+
call_key = id(self), _get_ident()
2532+
if call_key in _repr_running:
2533+
return '...'
2534+
_repr_running[call_key] = 1
2535+
try:
2536+
if not self:
2537+
return '%s()' % (self.__class__.__name__,)
2538+
return '%s(%r)' % (self.__class__.__name__, self.items())
2539+
finally:
2540+
del _repr_running[call_key]
2541+
2542+
def __reduce__(self):
2543+
'Return state information for pickling'
2544+
items = [[k, self[k]] for k in self]
2545+
inst_dict = vars(self).copy()
2546+
for k in vars(OrderedDict()):
2547+
inst_dict.pop(k, None)
2548+
if inst_dict:
2549+
return (self.__class__, (items,), inst_dict)
2550+
return self.__class__, (items,)
2551+
2552+
def copy(self):
2553+
'od.copy() -> a shallow copy of od'
2554+
return self.__class__(self)
2555+
2556+
@classmethod
2557+
def fromkeys(cls, iterable, value=None):
2558+
'''OD.fromkeys(S[, v]) -> New ordered dictionary with keys from S
2559+
and values equal to v (which defaults to None).
2560+
2561+
'''
2562+
d = cls()
2563+
for key in iterable:
2564+
d[key] = value
2565+
return d
2566+
2567+
def __eq__(self, other):
2568+
'''od.__eq__(y) <==> od==y. Comparison to another OD is order-sensitive
2569+
while comparison to a regular mapping is order-insensitive.
2570+
2571+
'''
2572+
if isinstance(other, OrderedDict):
2573+
return len(self)==len(other) and self.items() == other.items()
2574+
return dict.__eq__(self, other)
2575+
2576+
def __ne__(self, other):
2577+
return not self == other
2578+
2579+
# -- the following methods are only used in Python 2.7 --
2580+
2581+
def viewkeys(self):
2582+
"od.viewkeys() -> a set-like object providing a view on od's keys"
2583+
return KeysView(self)
2584+
2585+
def viewvalues(self):
2586+
"od.viewvalues() -> an object providing a view on od's values"
2587+
return ValuesView(self)
2588+
2589+
def viewitems(self):
2590+
"od.viewitems() -> a set-like object providing a view on od's items"
2591+
return ItemsView(self)

0 commit comments

Comments
 (0)
0