>>> t = Tree()
>>> d = {}
>>> d["hoge"] = 1
>>> d["fuga"] = 2
>>> d["piyo"] = 3
>>> d
{'fuga': 2, 'piyo': 3, 'hoge': 1}
>>> t["a"]["b"]["hoge"]=1
>>> t["a"]["b"]["fuga"]=2
>>> t["a"]["b"]["piyo"]=3
>>> t
{'a': {'b': {'hoge': 1, 'fuga': 2, 'piyo': 3}}}
>>> t["a"]["c"]["hoge"]=1
>>> t["a"]["c"]["fuga"]=2
>>> t["a"]["c"]["piyo"]=3
>>> t
{'a': {'b': {'hoge': 1, 'fuga': 2, 'piyo': 3}, 'c': {'hoge': 1, 'fuga': 2, 'piyo': 3}}}
>>> tt = Tree()
>>> tt["501"]["miyafuji"]=11
>>> tt["501"]["trude"]=12
>>> tt
{'501': {'miyafuji': 11, 'trude': 12}}
>>> t["a"]["b"]["c"].update(tt)
>>> t
{'a': {'b': {'hoge': 1, 'fuga': 2, 'piyo': 3, 'c': {'501': {'miyafuji': 11, 'trude': 12}}}, 'c': {'hoge': 1, 'fuga': 2, 'piyo': 3}}}
Last active
December 14, 2015 06:49
-
-
Save non117/5045791 to your computer and use it in GitHub Desktop.
SortedDictの機能をもった木構造のdict
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import copy | |
from types import GeneratorType | |
class SortedDict(dict): | |
""" | |
A dictionary that keeps its keys in the order in which they're inserted. | |
""" | |
def __new__(cls, *args, **kwargs): | |
instance = super(SortedDict, cls).__new__(cls, *args, **kwargs) | |
instance.keyOrder = [] | |
return instance | |
def __init__(self, data=None): | |
if data is None: | |
data = {} | |
elif isinstance(data, GeneratorType): | |
# Unfortunately we need to be able to read a generator twice. Once | |
# to get the data into self with our super().__init__ call and a | |
# second time to setup keyOrder correctly | |
data = list(data) | |
super(SortedDict, self).__init__(data) | |
if isinstance(data, dict): | |
self.keyOrder = data.keys() | |
else: | |
self.keyOrder = [] | |
seen = set() | |
for key, value in data: | |
if key not in seen: | |
self.keyOrder.append(key) | |
seen.add(key) | |
def __deepcopy__(self, memo): | |
return self.__class__([(key, copy.deepcopy(value, memo)) | |
for key, value in self.iteritems()]) | |
def __setitem__(self, key, value): | |
if key not in self: | |
self.keyOrder.append(key) | |
super(SortedDict, self).__setitem__(key, value) | |
def __delitem__(self, key): | |
super(SortedDict, self).__delitem__(key) | |
self.keyOrder.remove(key) | |
def __iter__(self): | |
return iter(self.keyOrder) | |
def pop(self, k, *args): | |
result = super(SortedDict, self).pop(k, *args) | |
try: | |
self.keyOrder.remove(k) | |
except ValueError: | |
# Key wasn't in the dictionary in the first place. No problem. | |
pass | |
return result | |
def popitem(self): | |
result = super(SortedDict, self).popitem() | |
self.keyOrder.remove(result[0]) | |
return result | |
def items(self): | |
return zip(self.keyOrder, self.values()) | |
def iteritems(self): | |
for key in self.keyOrder: | |
yield key, self[key] | |
def keys(self): | |
return self.keyOrder[:] | |
def iterkeys(self): | |
return iter(self.keyOrder) | |
def values(self): | |
return map(self.__getitem__, self.keyOrder) | |
def itervalues(self): | |
for key in self.keyOrder: | |
yield self[key] | |
def update(self, dict_): | |
for k, v in dict_.iteritems(): | |
self[k] = v | |
def setdefault(self, key, default): | |
if key not in self: | |
self.keyOrder.append(key) | |
return super(SortedDict, self).setdefault(key, default) | |
def value_for_index(self, index): | |
"""Returns the value of the item at the given zero-based index.""" | |
return self[self.keyOrder[index]] | |
def insert(self, index, key, value): | |
"""Inserts the key, value pair before the item with the given index.""" | |
if key in self.keyOrder: | |
n = self.keyOrder.index(key) | |
del self.keyOrder[n] | |
if n < index: | |
index -= 1 | |
self.keyOrder.insert(index, key) | |
super(SortedDict, self).__setitem__(key, value) | |
def copy(self): | |
"""Returns a copy of this object.""" | |
# This way of initializing the copy means it works for subclasses, too. | |
obj = self.__class__(self) | |
obj.keyOrder = self.keyOrder[:] | |
return obj | |
def __repr__(self): | |
""" | |
Replaces the normal dict.__repr__ with a version that returns the keys | |
in their sorted order. | |
""" | |
return '{%s}' % ', '.join(['%r: %r' % (k, v) for k, v in self.items()]) | |
def clear(self): | |
super(SortedDict, self).clear() | |
self.keyOrder = [] | |
class Tree(SortedDict): | |
def __init__(self, value=None): | |
super(Tree, self).__init__() | |
self.value = value | |
def __missing__(self, key): | |
self[key] = value = Tree() | |
return value |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment