Last active
May 2, 2022 21:27
-
-
Save eestrada/c801fb85d3221b7208df to your computer and use it in GitHub Desktop.
A collection of useful data structures including a very complete linked list class that implements the full feature set of _collections.MutableSequence.
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
# This is free and unencumbered software released into the public domain. | |
# | |
# Anyone is free to copy, modify, publish, use, compile, sell, or | |
# distribute this software, either in source code form or as a compiled | |
# binary, for any purpose, commercial or non-commercial, and by any | |
# means. | |
# | |
# In jurisdictions that recognize copyright laws, the author or authors | |
# of this software dedicate any and all copyright interest in the | |
# software to the public domain. We make this dedication for the benefit | |
# of the public at large and to the detriment of our heirs and | |
# successors. We intend this dedication to be an overt act of | |
# relinquishment in perpetuity of all present and future rights to this | |
# software under copyright law. | |
# | |
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, | |
# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF | |
# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. | |
# IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR | |
# OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, | |
# ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR | |
# OTHER DEALINGS IN THE SOFTWARE. | |
# | |
# For more information, please refer to <http://unlicense.org/> | |
"""All code in this module is in the public domain unless otherwise noted. | |
A module holding classes either missing from Python. | |
Some classes, such as ChainMap, are simply missing from Python 2.x. | |
Many others are useful classes that are altogether missing when they | |
probably shouldn't be (such as `frozenmap`). Others are useful in building | |
other more complex datastructures. An example of this type of class | |
is the LinkedList class, which is useful in building more complex | |
structures. | |
""" | |
from __future__ import print_function, absolute_import, division | |
# from .py3_fixes import * | |
# from reprlib import recursive_repr as _recursive_repr | |
try: | |
from future_builtins import * | |
except Exception as e: | |
pass | |
import itertools as _itertools | |
import operator as _operator | |
import collections as _collections | |
import weakref as _weakref | |
__all__ = [] | |
def _add_to__all__(val): | |
# print(val) | |
# print(val.__name__) | |
__all__.append(val.__name__) | |
return val | |
@_add_to__all__ | |
class Node(object): | |
"""Node class for use in the LinkedList class implementation.""" | |
__slots__ = ('_container', '_prev', 'value', 'next', '__weakref__') | |
def __init__(self, container=None, prev=None, value=None, next=None): | |
"""Initialize Node instance.""" | |
# "container" and "prev" are not True attributes, but properties. To be | |
# safe, we set their underlying attributes to None, so that if/when | |
# they are accessed in the properties' setter and getter methods, | |
# nothing breaks. | |
self._container = None | |
self._prev = None | |
self.container = container | |
self.prev = prev | |
self.value = value | |
self.next = next | |
def remove(self): | |
"""A convenience function to remove the node from its container. | |
This is the same as calling "node.container.remove_node(node)" if the | |
node's container is not set to None. | |
""" | |
container = self.container | |
if container is not None: | |
container.remove_node(self) | |
return self | |
@property | |
def container(self): | |
"""A (weak) reference to the container that contains this node. | |
This may also be set to None if the node is not associated with any | |
container. | |
>>> ll = LinkedList() | |
>>> n = Node() | |
>>> n.container = ll | |
>>> print(n.container) | |
LinkedList() | |
>>> n.container = None | |
>>> print(n.container) | |
None | |
>>> n.container = 10 | |
Traceback (most recent call last): | |
... | |
TypeError: cannot create weak reference to 'int' object | |
""" | |
return None if self._container is None else self._container() | |
@container.setter | |
def container(self, value): | |
"""Setter for container property.""" | |
if value is None: | |
self._container = None | |
else: | |
self._container = _weakref.ref(value) | |
return value | |
@property | |
def prev(self): | |
"""A (weak) reference to the node that precedes this one in a list. | |
>>> node = Node() | |
>>> other = Node() | |
>>> node.prev = other | |
>>> node.prev is other | |
True | |
>>> node.prev = None | |
>>> print(node.prev) | |
None | |
>>> node.prev = 10 | |
Traceback (most recent call last): | |
... | |
TypeError: cannot create weak reference to 'int' object | |
""" | |
return None if self._prev is None else self._prev() | |
@prev.setter | |
def prev(self, value): | |
"""Setter for prev property.""" | |
if value is None: | |
self._prev = None | |
else: | |
self._prev = _weakref.ref(value) | |
return value | |
@_add_to__all__ | |
class LinkedList(_collections.MutableSequence): | |
"""Basic (but very complete) linked list implementation. | |
The class implements many methods beyond the standard mutable sequence | |
methods. This is to make it easier and more efficient to work with nodes | |
in a linked list instance, or to transfer nodes between instances. | |
""" | |
def __init__(self, iterable=()): | |
"""Initialize LinkedList instance. | |
Expects an iterable object it initialize its contents. May also be | |
passed nothing to initialize empty. | |
>>> LinkedList() | |
LinkedList() | |
>>> LinkedList([0, 1, 2, 3, 4]) | |
LinkedList([0, 1, 2, 3, 4]) | |
>>> LinkedList([[0, 1], [2, 3]]) | |
LinkedList([[0, 1], [2, 3]]) | |
>>> LinkedList([1]) | |
LinkedList([1]) | |
>>> LinkedList([True, False, 1, None]) | |
LinkedList([True, False, 1, None]) | |
""" | |
# TODO: Remove hidden _tail reference and implement as a circularly linked list? | |
self._root = None | |
self._tail = None | |
self._cached_length = 0 | |
self.extend(iterable) | |
@property | |
def root(self): | |
"""Read only attribute referencing the root node of the linked list. | |
Will return None when the list is empty. | |
>>> ll = LinkedList([0, 1, 2, 3, 4]) | |
>>> ll.root is None | |
False | |
>>> ll.root.value == 0 | |
True | |
>>> ll.clear() | |
>>> ll.root is None | |
True | |
>>> ll.append('value') # List now has only one entry | |
>>> ll.root is ll.tail | |
True | |
>>> ll.root = Node() | |
Traceback (most recent call last): | |
... | |
AttributeError: can't set attribute | |
""" | |
return self._root | |
@property | |
def tail(self): | |
"""Read only attribute referencing the tail node of the linked list. | |
Will return None when the list is empty. | |
>>> ll = LinkedList([0, 1, 2, 3, 4]) | |
>>> ll.tail is None | |
False | |
>>> ll.tail.value == 4 | |
True | |
>>> ll.clear() | |
>>> ll.tail is None | |
True | |
>>> ll.tail = Node() | |
Traceback (most recent call last): | |
... | |
AttributeError: can't set attribute | |
""" | |
return self._tail | |
def __len__(self): | |
"""Return length of self.""" | |
return self._cached_length | |
def __repr__(self, _fmt='{0.__class__.__name__}({1})'.format): | |
"""Return useful string representation of self.""" | |
return _fmt(self, list(self) or '') | |
def _prep_slice(self, slc, iter_nodes=False): | |
start = slc.start | |
stop = slc.stop | |
step = slc.step | |
if start is not None and start < 0: | |
start = len(self) + start | |
if stop is not None and stop < 0: | |
stop = len(self) + stop | |
if step is not None and step < 0: | |
step = abs(step) | |
selfiter = reversed(self) if not iter_nodes else self.reverse_iter_nodes() | |
else: | |
selfiter = iter(self) if not iter_nodes else self.iter_nodes() | |
return _itertools.islice(selfiter, start, stop, step) | |
def clear(self): | |
"""Clear all items from the sequence in place. | |
>>> original = ll = LinkedList([0, 1, 2, 3, 4]) | |
>>> ll.clear() | |
>>> ll | |
LinkedList() | |
>>> len(ll) | |
0 | |
>>> original is ll | |
True | |
""" | |
# Since Node objects use weak references, the nodes will clean | |
# themselves up once all references to them disapear. | |
self._root = self._tail = None | |
self._cached_length = 0 | |
def sort(self, key=None, reverse=False): | |
"""Sort sequence in place. | |
This is no more efficient than calling "sorted(linkedlist)". | |
However, this method maintains the identity of the nodes in the list, | |
so it is still useful. | |
>>> original = ll = LinkedList([3, 4, 2, 0, 1]) | |
>>> print(ll) | |
LinkedList([3, 4, 2, 0, 1]) | |
>>> node4 = ll.get_node(1) | |
>>> node0 = ll.get_node(-2) | |
>>> ll.sort() | |
>>> print(ll) | |
LinkedList([0, 1, 2, 3, 4]) | |
>>> original is ll | |
True | |
>>> # node identities are kept (i.e. no nodes are created/discarded) | |
>>> node4 is ll.tail | |
True | |
>>> node0 is ll.root | |
True | |
""" | |
# TODO: test using custom key callables | |
if key is not None: | |
keyfunc = lambda node: key(node.value) | |
else: | |
keyfunc = _operator.attrgetter('value') | |
sortednodes = sorted(self.iter_nodes(), key=keyfunc, reverse=reverse) | |
# references to the nodes are in "sortednodes" so they won't get | |
# garbage collected when we clear the LinkedList. | |
self.clear() | |
for node in sortednodes: | |
self.insert_node(None, node) | |
def __getitem__(self, index): | |
"""__getitem__ indexing. | |
This operation is slow on linked lists and ought to be avoided. | |
>>> ll = LinkedList(range(5)) | |
>>> ll[0] | |
0 | |
>>> ll[-1] | |
4 | |
>>> ll[2] | |
2 | |
>>> ll[1:3] | |
LinkedList([1, 2]) | |
>>> ll[::2] | |
LinkedList([0, 2, 4]) | |
>>> ll[::-1] | |
LinkedList([4, 3, 2, 1, 0]) | |
>>> ll[1::-1] | |
LinkedList([3, 2, 1, 0]) | |
>>> ll[:10] | |
LinkedList([0, 1, 2, 3, 4]) | |
>>> ll[10:] | |
LinkedList() | |
>>> llnew = ll[:] | |
>>> llnew == ll # the contents match | |
True | |
>>> llnew is ll # but the identity does not | |
False | |
""" | |
if isinstance(index, slice): | |
islc = self._prep_slice(index) | |
return self.__class__(islc) | |
else: | |
return self.get_node(index).value | |
def __lt__(self, other): | |
"""Less than comparison. | |
>>> ll1 = LinkedList(range(6, 0, -1)) | |
>>> ll2 = LinkedList(range(0, 6, 1)) | |
>>> (ll1 < ll2) == (list(ll1) < list(ll2)) | |
True | |
>>> (ll1 < ll1) == (list(ll1) < list(ll1)) | |
True | |
>>> ll1 = LinkedList(range(20, 0, -1)) | |
>>> ll2 = LinkedList(range(0, 6, 1)) | |
>>> (ll1 < ll2) == (list(ll1) < list(ll2)) | |
True | |
>>> (ll2 < ll1) == (list(ll2) < list(ll1)) | |
True | |
""" | |
if not isinstance(other, self.__class__): | |
return NotImplemented | |
for si, oi in zip(self, other): | |
if si >= oi: | |
return False | |
return True | |
def __le__(self, other): | |
"""Less than or equal comparison. | |
>>> ll1 = LinkedList(range(6, 0, -1)) | |
>>> ll2 = LinkedList(range(0, 6, 1)) | |
>>> (ll1 <= ll2) == (list(ll1) <= list(ll2)) | |
True | |
>>> (ll1 <= ll1) == (list(ll1) <= list(ll1)) | |
True | |
""" | |
if not isinstance(other, self.__class__): | |
return NotImplemented | |
return self < other or self == other | |
def __eq__(self, other): | |
"""Equal comparison. | |
>>> ll1 = LinkedList(range(6, 0, -1)) | |
>>> ll2 = LinkedList(range(0, 6, 1)) | |
>>> (ll1 == ll2) == (list(ll1) == list(ll2)) | |
True | |
>>> (ll1 == ll1) == (list(ll1) == list(ll1)) | |
True | |
""" | |
if not isinstance(other, self.__class__): | |
return NotImplemented | |
if len(self) != len(other): | |
return False | |
for si, oi in zip(self, other): | |
if si != oi: | |
return False | |
return True # if we have exhausted all items, then we must match | |
def __ne__(self, other): | |
"""Not equal comparison. | |
>>> ll1 = LinkedList(range(6, 0, -1)) | |
>>> ll2 = LinkedList(range(0, 6, 1)) | |
>>> (ll1 != ll2) == (list(ll1) != list(ll2)) | |
True | |
>>> (ll1 != ll1) == (list(ll1) != list(ll1)) | |
True | |
""" | |
result = self == other | |
return result if result is NotImplemented else not result | |
def __gt__(self, other): | |
"""Greater than comparison. | |
>>> ll1 = LinkedList(range(6, 0, -1)) | |
>>> ll2 = LinkedList(range(0, 6, 1)) | |
>>> (ll1 > ll2) == (list(ll1) > list(ll2)) | |
True | |
>>> (ll1 > ll1) == (list(ll1) > list(ll1)) | |
True | |
""" | |
if not isinstance(other, self.__class__): | |
return NotImplemented | |
return not (self < other) and not (self == other) | |
def __ge__(self, other): | |
"""Greater than or equal comparison. | |
>>> ll1 = LinkedList(range(6, 0, -1)) | |
>>> ll2 = LinkedList(range(0, 6, 1)) | |
>>> (ll1 >= ll2) == (list(ll1) >= list(ll2)) | |
True | |
>>> (ll1 >= ll1) == (list(ll1) >= list(ll1)) | |
True | |
""" | |
if not isinstance(other, self.__class__): | |
return NotImplemented | |
return not (self < other) or (self == other) | |
def __setitem__(self, index, value): | |
"""__setitem__ indexing. | |
>>> ll = LinkedList(range(5)) | |
>>> ll | |
LinkedList([0, 1, 2, 3, 4]) | |
>>> ll[2] = None | |
>>> ll | |
LinkedList([0, 1, None, 3, 4]) | |
""" | |
if isinstance(index, slice): | |
if index.start is None and index.stop is None and index.step is None: | |
self.clear() | |
for v in value: | |
self.append(v) | |
return | |
else: | |
raise NotImplementedError('complete slice assignment is not yet implemented') | |
else: | |
self.get_node(index).value = value | |
def __delitem__(self, index): | |
"""delete item(s). | |
>>> ll = LinkedList(range(10)) | |
>>> ll | |
LinkedList([0, 1, 2, 3, 4, 5, 6, 7, 8, 9]) | |
>>> del ll[4] | |
>>> ll | |
LinkedList([0, 1, 2, 3, 5, 6, 7, 8, 9]) | |
>>> del ll[0:2] | |
>>> ll | |
LinkedList([2, 3, 5, 6, 7, 8, 9]) | |
>>> del ll[::2] | |
>>> ll | |
LinkedList([3, 6, 8]) | |
""" | |
if isinstance(index, slice): | |
islc = self._prep_slice(index, iter_nodes=True) | |
for n in islc: | |
self.remove_node(n) | |
else: | |
self.pop(index) | |
def insert(self, index, value): | |
"""Insert value at specified index. | |
>>> ll = LinkedList(range(5)) | |
>>> l = list(ll) | |
>>> ll.insert(2, None) | |
>>> ll | |
LinkedList([0, 1, None, 2, 3, 4]) | |
>>> l.insert(2, None) | |
>>> list(ll) == l | |
True | |
""" | |
if index >= len(self): # append to back | |
self.insert_node(None, value=value) | |
else: | |
node = self.get_node(index) | |
self.insert_node(node, value=value) | |
# The default pop implementation indexes into the sequence twice (once to | |
# retrieve the value and once to delete it). This would be overly expensive | |
# for a linked list. | |
def pop(self, index=-1): | |
"""Remove and return an item from the sequence. | |
Defaults to removing the last item in the sequence. | |
>>> ll = LinkedList(range(5)) | |
>>> ll.pop() # pop from back | |
4 | |
>>> ll | |
LinkedList([0, 1, 2, 3]) | |
>>> ll.pop(0) # pop from front | |
0 | |
>>> ll | |
LinkedList([1, 2, 3]) | |
>>> ll.pop(1) # pop from middle | |
2 | |
>>> ll | |
LinkedList([1, 3]) | |
""" | |
node = self.get_node(index) | |
node = self.remove_node(node) | |
return node.value | |
def reverse(self): | |
"""Reverse sequence in place. | |
>>> original = ll = LinkedList(range(5)) | |
>>> ll | |
LinkedList([0, 1, 2, 3, 4]) | |
>>> ll.reverse() | |
>>> ll | |
LinkedList([4, 3, 2, 1, 0]) | |
>>> original is ll | |
True | |
>>> ll.reverse() | |
>>> ll | |
LinkedList([0, 1, 2, 3, 4]) | |
""" | |
if len(self) <= 1: | |
return | |
nl = list(self.reverse_iter_nodes()) | |
for i, n in enumerate(nl): | |
if i - 1 >= 0: | |
nl[i-1].next = nl[i] | |
nl[i].prev = nl[i-1] | |
if i + 1 < len(self): | |
nl[i+1].prev = nl[i] | |
nl[i].next = nl[i+1] | |
nl[0].prev = nl[-1].next = None | |
self._root = nl[0] | |
self._tail = nl[-1] | |
def remove(self, value): | |
"""Remove node with given value. | |
Raises ValueError if value does not exist in container | |
>>> ll = LinkedList([0, 1, 2, 3, 4]) | |
>>> ll.remove(2) | |
>>> ll | |
LinkedList([0, 1, 3, 4]) | |
>>> ll.remove(5) | |
Traceback (most recent call last): | |
... | |
ValueError: Value '5' not found in container | |
""" | |
for node in self.iter_nodes(): | |
if node.value == value: | |
self.remove_node(node) | |
return | |
raise ValueError("Value '{0!r}' not found in container".format(value)) | |
def __iter__(self): | |
"""Implement in place forward iteration. | |
>>> ll = LinkedList(range(5)) | |
>>> tuple(ll) | |
(0, 1, 2, 3, 4) | |
>>> lliter = iter(ll) | |
>>> list(lliter) | |
[0, 1, 2, 3, 4] | |
""" | |
for node in self.iter_nodes(): | |
yield node.value | |
def __reversed__(self): | |
"""Implement in place reverse iteration. | |
>>> ll = LinkedList(range(5)) | |
>>> ll | |
LinkedList([0, 1, 2, 3, 4]) | |
>>> other = LinkedList(reversed(ll)) | |
>>> other | |
LinkedList([4, 3, 2, 1, 0]) | |
>>> ll is other | |
False | |
""" | |
for node in self.reverse_iter_nodes(): | |
yield node.value | |
def iter_nodes(self): | |
"""Iterate directly thru LinkedList nodes.""" | |
current = self._root | |
while current is not None: | |
# we save a reference to 'next' so that it is possible to remove | |
# 'current' during iteration | |
next = current.next | |
yield current | |
current = next | |
def reverse_iter_nodes(self): | |
"""Reverse iterate directly thru LinkedList nodes.""" | |
current = self._tail | |
while current is not None: | |
# we save a reference to 'prev' so that it is possible to remove | |
# 'current' during iteration | |
prev = current.prev | |
yield current | |
current = prev | |
def insert_node(self, before, node=None, value=None): | |
"""Directly insert node into LinkedList. | |
Return the inserted node object. | |
""" | |
if node is None: | |
node = Node(value=value) | |
elif node is before: | |
raise ValueError('Cannot insert node before itself!') | |
elif not isinstance(node, Node): | |
raise ValueError('"node" parameter must either be None or a Node instance') | |
if node.container is not None and node.container is not self: | |
node.remove() | |
# Special case of container being empty | |
if not self: | |
node.container = self | |
node.prev = node.next = None | |
self._root = self._tail = node | |
self._cached_length += 1 | |
return node | |
# NOTE: in case a node within this same container is simply being moved | |
node.remove() | |
# None is a special value to indicate that we want to append this node | |
# to the end of the chain. | |
if before is None: | |
prev = self._tail | |
next = self._tail.next | |
elif isinstance(before, Node) and before.container is self: | |
prev = before.prev | |
next = before | |
else: | |
raise ValueError('"before" parameter must either be None or a Node in this container') | |
node.container = self | |
node.prev = prev | |
node.next = next | |
if prev is not None: | |
prev.next = node | |
if next is not None: | |
next.prev = node | |
if before is None: | |
self._tail = node | |
elif before is self._root: | |
self._root = node | |
self._cached_length += 1 | |
return node | |
def remove_node(self, node): | |
"""Remove node from container. | |
The return value is the node instance with its container, prev and next | |
properties set to None. | |
If the node is not a member of this container, None is returned. | |
""" | |
if node.container is not self: | |
return None | |
# We place prev and next into local variables to avoid a race condition | |
# since the Node class uses weak references. | |
prev = node.prev | |
next = node.next | |
# reassign prev and/or next references if they exist | |
if prev is not None: | |
prev.next = node.next | |
if next is not None: | |
next.prev = node.prev | |
# deal with the special cases of removing root and tail nodes | |
if prev is None and next is not None: | |
self._root = next | |
elif prev is not None and next is None: | |
self._tail = prev | |
elif prev is None and next is None: | |
self._root = self._tail = None | |
node.container = node.prev = node.next = None | |
self._cached_length -= 1 | |
return node | |
def get_node(self, index): | |
"""Get the node object at the given index.""" | |
# Special case for empty list | |
if len(self) == 0: | |
if self._root is None and self._tail is None: | |
raise IndexError('LinkedList index out of range; sequence is empty') | |
else: | |
raise RuntimeError('The list length cache is reported as being zero, but either root or tail (or both) is not None.') | |
if index < 0: | |
index = len(self) + index | |
if index >= len(self) or index < 0: | |
raise IndexError('LinkedList index out of range') | |
# Special cases for root and tail, since accessing the front and the | |
# back of a sequence are frequent operations. | |
if index == 0: | |
return self._root | |
elif index == len(self)-1: | |
return self._tail | |
current = self._root | |
count = 0 | |
while current is not None: | |
if index == count: | |
return current | |
current = current.next | |
count += 1 | |
# All index errors should be raised before this. Check into this. | |
raise IndexError('How did I get here?.') | |
# NOTE: A large portion of this is sourced from: | |
# https://github.com/python/cpython/blob/2.7/Lib/collections.py | |
# This code is licensed under the PSFL since it was initially taken verbatim | |
# from the Python standard library. | |
@_add_to__all__ | |
class OrderedDict(dict, _collections.MutableMapping): | |
"""A dictionary that remembers insertion order. | |
This is different from the stdlib collections.OrderedDict in that it allows for | |
modification of the underlying order (essentially, restricted access | |
to the underlying linked list). | |
Also, its implementation in faily different; whereas the OrderedDict in collections | |
optimizes for speed of retrieval of items by key, this implementation optimizes | |
for space. | |
""" | |
def __init__(self, *args, **kwargs): | |
if len(args) > 1: | |
raise TypeError('expected at most 1 arguments, got %d' % len(args)) | |
super(OrderedDict, self).__init__() | |
try: | |
self.__llist | |
except AttributeError: | |
self.__llist = LinkedList() | |
self.__update(*args, **kwargs) | |
def __setitem__(self, key, value, _setitem=dict.__setitem__, _getitem=dict.__getitem__): | |
"""Set item in dictionary. | |
New values are placed at the tail of the internal list. | |
>>> od = OrderedDict() | |
>>> od[0] = 1 | |
>>> od[2] = 3 | |
>>> od | |
OrderedDict([(0, 1), (2, 3)]) | |
""" | |
try: | |
_getitem(self, key).value = (key, value) | |
except KeyError as e: | |
# NOTE: append new keys to the tail of the list | |
node = self.__llist.insert_node(before=None, value=(key, value)) | |
_setitem(self, key, node) | |
def __getitem__(self, key, _getitem=dict.__getitem__): | |
"""Get item in dictionary. | |
>>> od = OrderedDict([(0, 1), (2, 3)]) | |
>>> od[0] == 1 | |
True | |
>>> od[2] == 3 | |
True | |
""" | |
try: | |
return _getitem(self, key).value[1] | |
except KeyError as e: | |
raise | |
def __delitem__(self, key, _delitem=dict.__delitem__, _getitem=dict.__getitem__): | |
"""Delete item in dictionary. | |
>>> od = OrderedDict([(0, 1), (2, 3)]) | |
>>> od | |
OrderedDict([(0, 1), (2, 3)]) | |
>>> del od[0] | |
>>> od | |
OrderedDict([(2, 3)]) | |
""" | |
node = _getitem(self, key) | |
node.remove() | |
_delitem(self, key) | |
def __iter__(self): | |
"""Iterate over keys in dictionary. | |
>>> od = OrderedDict([(0, 1), (2, 3)]) | |
>>> list(iter(od)) | |
[0, 2] | |
""" | |
return (item[0] for item in self.__llist) | |
def __reversed__(self): | |
"""Iterate over keys in dictionary in reverse order. | |
>>> od = OrderedDict([(0, 1), (2, 3)]) | |
>>> list(reversed(od)) | |
[2, 0] | |
""" | |
return (item[0] for item in reversed(self.__llist)) | |
def __repr__(self, _fmt="{0.__class__.__name__!s}({1!s})".format): | |
return _fmt(self, list(self.items()) or '') | |
def item_at(self, index): | |
"""Get at item tuple at a certain index. | |
Does not support slice indexing. | |
>>> od = OrderedDict([(12, 24), (-1, -2), ('some key', 'some value')]) | |
>>> od.item_at(2) | |
('some key', 'some value') | |
>>> od.item_at(-1) | |
('some key', 'some value') | |
>>> od.item_at(2) == ('some key', od['some key']) | |
True | |
""" | |
return self.__llist[index] | |
def move_key(self, key, index, _getitem=dict.__getitem__): | |
"""Change ordering of ``key`` to be at ``index``. | |
>>> od = OrderedDict([(12, 24), (-1, -2), ('some key', 'some value')]) | |
>>> od.item_at(2) | |
('some key', 'some value') | |
>>> od.move_key(12, len(od)) # any index beyond the end is treated as the end | |
>>> od.item_at(2) | |
(12, 24) | |
>>> od | |
OrderedDict([(-1, -2), ('some key', 'some value'), (12, 24)]) | |
>>> od.move_key(-1, -1) # move to just before the end using a negative index | |
>>> od.item_at(2) | |
(12, 24) | |
>>> od | |
OrderedDict([('some key', 'some value'), (-1, -2), (12, 24)]) | |
""" | |
node = _getitem(self, key) | |
self_len = len(self) | |
if index < 0: | |
index = self_len + index | |
if index >= self_len: | |
before = None | |
else: | |
before = self.__llist.get_node(index) | |
self.__llist.insert_node(before=before, node=node) | |
# NOTE: methods that can be sourced from elsewhere | |
popitem = _collections.OrderedDict.popitem | |
copy = _collections.OrderedDict.copy | |
fromkeys = _collections.OrderedDict.fromkeys | |
update = _collections.MutableMapping.update | |
__update = update # let subclasses override update without breaking __init__ | |
pop = _collections.MutableMapping.pop | |
get = _collections.MutableMapping.get | |
clear = _collections.MutableMapping.clear | |
setdefault = _collections.MutableMapping.setdefault | |
# NOTE: return views, not lists | |
def keys(self): | |
return _collections.KeysView(self) | |
viewkeys = iterkeys = keys | |
def values(self): | |
return _collections.ValuesView(self) | |
viewvalues = itervalues = values | |
def items(self): | |
return _collections.ItemsView(self) | |
viewitems = iteritems = items | |
# Code for ChainMap sourced from Python 3.4 standard library | |
# https://github.com/python/cpython/blob/3.7/Lib/collections/__init__.py | |
# This code is licensed under the PSFL since it was initially taken verbatim | |
# from the Python standard library. | |
@_add_to__all__ | |
class ChainMap(_collections.MutableMapping): | |
''' A ChainMap groups multiple dicts (or other mappings) together | |
to create a single, updateable view. | |
The underlying mappings are stored in a list. That list is public and can | |
accessed or updated using the *maps* attribute. There is no other state. | |
Lookups search the underlying mappings successively until a key is found. | |
In contrast, writes, updates, and deletions only operate on the first | |
mapping. | |
''' | |
def __init__(self, *maps): | |
'''Initialize a ChainMap by setting *maps* to the given mappings. | |
If no mappings are provided, a single empty dictionary is used. | |
''' | |
self.maps = list(maps) or [{}] # always at least one map | |
def __missing__(self, key): | |
raise KeyError(key) | |
def __getitem__(self, key): | |
for mapping in self.maps: | |
try: | |
return mapping[key] # can't use 'key in mapping' with defaultdict | |
except KeyError: | |
pass | |
return self.__missing__(key) # support subclasses that define __missing__ | |
def get(self, key, default=None): | |
return self[key] if key in self else default | |
def __len__(self): | |
return len(set().union(*self.maps)) # reuses stored hash values if possible | |
def __iter__(self): | |
return iter(set().union(*self.maps)) | |
def __contains__(self, key): | |
return any(key in m for m in self.maps) | |
def __nonzero__(self): | |
return any(self.maps) | |
__bool__ = __nonzero__ | |
def __repr__(self): | |
return '{0.__class__.__name__}({1})'.format(self, | |
', '.join(repr, self.maps)) | |
@classmethod | |
def fromkeys(cls, iterable, *args): | |
'Create a ChainMap with a single dict created from the iterable.' | |
return cls(dict.fromkeys(iterable, *args)) | |
def copy(self): | |
'New ChainMap or subclass with a new copy of maps[0] and refs to maps[1:]' | |
return self.__class__(self.maps[0].copy(), *self.maps[1:]) | |
__copy__ = copy | |
def new_child(self, m=None): # like Django's Context.push() | |
''' | |
New ChainMap with a new map followed by all previous maps. If no | |
map is provided, an empty dict is used. | |
''' | |
if m is None: | |
m = {} | |
return self.__class__(m, *self.maps) | |
@property | |
def parents(self): # like Django's Context.pop() | |
'New ChainMap from maps[1:].' | |
return self.__class__(*self.maps[1:]) | |
def __setitem__(self, key, value): | |
self.maps[0][key] = value | |
def __delitem__(self, key): | |
try: | |
del self.maps[0][key] | |
except KeyError: | |
raise KeyError('Key not found in the first mapping: {!r}'.format(key)) | |
def popitem(self): | |
'Remove and return an item pair from maps[0]. Raise KeyError is maps[0] is empty.' | |
try: | |
return self.maps[0].popitem() | |
except KeyError: | |
raise KeyError('No keys found in the first mapping.') | |
def pop(self, key, *args): | |
'Remove *key* from maps[0] and return its value. Raise KeyError if *key* not in maps[0].' | |
try: | |
return self.maps[0].pop(key, *args) | |
except KeyError: | |
raise KeyError('Key not found in the first mapping: {!r}'.format(key)) | |
def clear(self): | |
'Clear maps[0], leaving maps[1:] intact.' | |
self.maps[0].clear() | |
def in_which(self, key): | |
'Return an iterator/generator yielding the indices of all maps with the given key in self.maps.' | |
for i, m in enumerate(self.maps): | |
if key in m: | |
yield i | |
@_add_to__all__ | |
class frozenmap(_collections.Mapping, _collections.Hashable): | |
"""An immutable, hashable map class. | |
It is analagous to the builtin frozenset. In order for frozenmap to work, | |
both keys AND values must be hashable. Instances of frozenmap can only | |
compare equal to other instances of frozenmap containing the same items; | |
other mapping types with the same items do not compare equal. | |
""" | |
def __init__(self, *args, **kwargs): | |
"""Initialize self. | |
>>> # keys AND values need not be hashable for frozenmap instances to be created | |
>>> class NoHash(object): __hash__ = None # unhashable class | |
>>> nh = NoHash() | |
>>> f1 = frozenmap({'unhashable': nh, 'hashable': 1}) | |
>>> # we can use keyword arguments just like a dictionary | |
>>> f2 = frozenmap(unhashable=nh, hashable=1) | |
>>> # we can use an iterable of pairs just like a dictionary | |
>>> f2 = frozenmap([('unhashable', nh), ('hashable', 1)]) | |
""" | |
# NOTE: Don't worry about unhashable values yet | |
self._map = dict(*args, **kwargs) | |
def __repr__(self): | |
"""Return representation of self. | |
>>> frozenmap({123:456}) | |
frozenmap({123: 456}) | |
>>> frozenmap() | |
frozenmap() | |
""" | |
return '{0.__class__.__name__}({1})'.format(self, self._map or '') | |
def __getitem__(self, key): | |
"""Get value associated with "key" in self.""" | |
return self._map[key] | |
def __iter__(self): | |
"""Iterate thru keys of self.""" | |
return iter(self._map) | |
def __len__(self): | |
"""Return length of self.""" | |
return len(self._map) | |
def __hash__(self): | |
"""Hash implementation. | |
>>> f1 = frozenmap({'k':'v', 'key':'value', '1':2}) | |
>>> f2 = frozenmap(k2='v2', key2='value2', twelve=22) | |
>>> f3 = frozenmap(f1) | |
>>> f1 == f2 | |
False | |
>>> hash(f1) == hash(f2) | |
False | |
>>> f1 == f3 | |
True | |
>>> hash(f1) == hash(f3) | |
True | |
>>> f1 is f3 | |
False | |
""" | |
stype = type(self) | |
itemset = frozenset(self.items()) | |
return hash(stype) ^ hash(itemset) | |
def __eq__(self, other): | |
"""Implement equals comparison operation.""" | |
return isinstance(other, frozenmap) and self._map == other._map | |
if __name__ == '__main__': | |
import doctest | |
doctest.testmod(verbose=True) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment