| from __future__ import unicode_literals |
| from __future__ import absolute_import |
| from . import util |
| from copy import deepcopy |
| |
| |
| class OrderedDict(dict): |
| """ |
| A dictionary that keeps its keys in the order in which they're inserted. |
| |
| Copied from Django's SortedDict with some modifications. |
| |
| """ |
| def __new__(cls, *args, **kwargs): |
| instance = super(OrderedDict, cls).__new__(cls, *args, **kwargs) |
| instance.keyOrder = [] |
| return instance |
| |
| def __init__(self, data=None): |
| if data is None or isinstance(data, dict): |
| data = data or [] |
| super(OrderedDict, self).__init__(data) |
| self.keyOrder = list(data) if data else [] |
| else: |
| super(OrderedDict, self).__init__() |
| super_set = super(OrderedDict, self).__setitem__ |
| for key, value in data: |
| # Take the ordering from first key |
| if key not in self: |
| self.keyOrder.append(key) |
| # But override with last value in data (dict() does this) |
| super_set(key, value) |
| |
| def __deepcopy__(self, memo): |
| return self.__class__([(key, deepcopy(value, memo)) |
| for key, value in self.items()]) |
| |
| def __copy__(self): |
| # The Python's default copy implementation will alter the state |
| # of self. The reason for this seems complex but is likely related to |
| # subclassing dict. |
| return self.copy() |
| |
| def __setitem__(self, key, value): |
| if key not in self: |
| self.keyOrder.append(key) |
| super(OrderedDict, self).__setitem__(key, value) |
| |
| def __delitem__(self, key): |
| super(OrderedDict, self).__delitem__(key) |
| self.keyOrder.remove(key) |
| |
| def __iter__(self): |
| return iter(self.keyOrder) |
| |
| def __reversed__(self): |
| return reversed(self.keyOrder) |
| |
| def pop(self, k, *args): |
| result = super(OrderedDict, 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(OrderedDict, self).popitem() |
| self.keyOrder.remove(result[0]) |
| return result |
| |
| def _iteritems(self): |
| for key in self.keyOrder: |
| yield key, self[key] |
| |
| def _iterkeys(self): |
| for key in self.keyOrder: |
| yield key |
| |
| def _itervalues(self): |
| for key in self.keyOrder: |
| yield self[key] |
| |
| if util.PY3: # pragma: no cover |
| items = _iteritems |
| keys = _iterkeys |
| values = _itervalues |
| else: # pragma: no cover |
| iteritems = _iteritems |
| iterkeys = _iterkeys |
| itervalues = _itervalues |
| |
| def items(self): |
| return [(k, self[k]) for k in self.keyOrder] |
| |
| def keys(self): |
| return self.keyOrder[:] |
| |
| def values(self): |
| return [self[k] for k in self.keyOrder] |
| |
| def update(self, dict_): |
| for k in dict_: |
| self[k] = dict_[k] |
| |
| def setdefault(self, key, default): |
| if key not in self: |
| self.keyOrder.append(key) |
| return super(OrderedDict, 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(OrderedDict, 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. |
| return self.__class__(self) |
| |
| def __repr__(self): |
| """ |
| Replaces the normal dict.__repr__ with a version that returns the keys |
| in their Ordered order. |
| """ |
| return '{%s}' % ', '.join( |
| ['%r: %r' % (k, v) for k, v in self._iteritems()] |
| ) |
| |
| def clear(self): |
| super(OrderedDict, self).clear() |
| self.keyOrder = [] |
| |
| def index(self, key): |
| """ Return the index of a given key. """ |
| try: |
| return self.keyOrder.index(key) |
| except ValueError: |
| raise ValueError("Element '%s' was not found in OrderedDict" % key) |
| |
| def index_for_location(self, location): |
| """ Return index or None for a given location. """ |
| if location == '_begin': |
| i = 0 |
| elif location == '_end': |
| i = None |
| elif location.startswith('<') or location.startswith('>'): |
| i = self.index(location[1:]) |
| if location.startswith('>'): |
| if i >= len(self): |
| # last item |
| i = None |
| else: |
| i += 1 |
| else: |
| raise ValueError('Not a valid location: "%s". Location key ' |
| 'must start with a ">" or "<".' % location) |
| return i |
| |
| def add(self, key, value, location): |
| """ Insert by key location. """ |
| i = self.index_for_location(location) |
| if i is not None: |
| self.insert(i, key, value) |
| else: |
| self.__setitem__(key, value) |
| |
| def link(self, key, location): |
| """ Change location of an existing item. """ |
| n = self.keyOrder.index(key) |
| del self.keyOrder[n] |
| try: |
| i = self.index_for_location(location) |
| if i is not None: |
| self.keyOrder.insert(i, key) |
| else: |
| self.keyOrder.append(key) |
| except Exception as e: |
| # restore to prevent data loss and reraise |
| self.keyOrder.insert(n, key) |
| raise e |