Instantly share code, notes, and snippets.

# non117/test.md Last active Dec 14, 2015

SortedDictの機能をもった木構造のdict
```>>> 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}}}```
 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