Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Python User Controlable Ordered Dictionary: one can actually control the item order.
"""Class that represents an ordered dict over which
the user can actually control the item order, and
replace keys already in the dicionary in their
original insertion place.
It also does that in O[1]
If used intenselly, where memory leak of
items deleted might be a problem, the
".compact" method should be called from
time to time to reindex the dictionary
"""
from collections.abc import MutableMapping
_deleted = object()
class SuperOrdered(MutableMapping):
def __init__(self):
self.data = {}
self.order = []
def __setitem__(self, key, value):
if key not in self.data:
self.order.append(key)
position = len(self.order) - 1
self.data[key] = (position, value)
else:
self.data[key] = (self.data[key][0], value)
def __getitem__(self, key):
return self.data[key][1]
def __delitem__(self, key):
position = self.data[key][0]
del self.data[key]
self.order[position] = _deleted
def __len__(self):
return len(self.data)
def __iter__(self):
for value in self.order:
if value is not _deleted:
yield value
def replace_key(self, oldkey, newkey, value):
if newkey in self.data:
del self[newkey]
position = self.order.index(oldkey)
self.order[position] = newkey
self.data[newkey] = position, value
def compact(self):
"""Removes deleted item information from order metadata"""
offset = 0
keys = iter(self)
new_index = 0
new_indexes = []
for index in self.order:
if index is _deleted:
offset += 1
continue
new_indexes.append(new_index)
key = next(keys)
if offset:
self.data[key] = new_index, self.data[key][1]
new_index += 1
self.order = new_indexes
def __repr__(self):
return f"{self.__class__.__name__}({{{', '.join('{}:{}'.format(key, self[key]) for key in self)}}})"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment