dantro.utils.ordereddict module

Definition of an OrderedDict-subclass that maintains the order key values rather than the insertion order. It can be specialized to use a specific comparison function for ordering keys.

class dantro.utils.ordereddict.KeyOrderedDict(*args, key: Callable = None, **kwds)[source]

Bases: dict

This dict maintains the order of keys not by their insertion but by their value. It is a re-implementation of collections.OrderedDict, because subclassing that class is really difficult.

Ordering is maintained by adjusting those methods of OrderedDict that take care of building and maintaining the doubly-linked list that provides the ordering. See OrderedDict for details, e.g. the weak-referencing.

In effect, this relates only to __setitem__; all other methods rely on this to add elements to the mapping.

For comparison, the key callable given at initialisation can be used to perform a operation on keys, the result of which is used in comparison. If this is not given, the DEFAULT_KEY_COMPARATOR class variable is used; note that this needs to be a binary function, where the first argument is equivalent to self and the second is the actual key to perform the unary operation on.

DEFAULT_KEY_COMPARATOR(k)
__init__(*args, key: Callable = None, **kwds)[source]

Initialize a KeyOrderedDict, which maintains key ordering. If no custom ordering function is given, orders by simple “smaller than” comparison.

Apart from that, the interface is the same as for regular dictionaries.

Parameters
  • *args – a single sequence of (key, value) pairs to insert

  • key (Callable, optional) – The callable used to

  • **kwds – Passed on to update method

Raises

TypeError – on len(args) > 1

_key_comp_lt(k1, k2) → bool[source]

The key comparator. Returns true for k1 < k2.

Before comparison, the unary self._key method is invoked on both keys.

Parameters
  • k1 – lhs of comparison

  • k2 – rhs of comparison

Returns

k1 < k2

Return type

bool

__setitem__(key, value, *, dict_setitem=<slot wrapper '__setitem__' of 'dict' objects>, proxy=<built-in function proxy>, Link=<class 'collections._Link'>, start=None)[source]

Set the item with the provided key to the given value, maintaining the ordering specified by _key_comp_lt.

If the key is not available, this takes care of finding the right place to insert the new link in the doubly-linked list.

Unlike the regular __setitem__, this allows specifying a start element at which to begin the search for an insertion point, which may greatly speed up insertion. By default, it is attempted to insert after the last element; if that is not possible, a full search is done.

Warning

This operation does not scale well with out-of-order insertion!

This behavior is inherent to this data structure, where key ordering has to be maintained during every insertion. While a best guess is made regarding the insertion points (see above), inserting elements completely out of order will require a search time that is proportional to the number of elements for each insertion.

Hint

If you have information about where the element should be stored, use insert() and provide the hint_after argument.

insert(key, value, *, hint_after=None)[source]

Inserts a (key, value) pair using hint information to speed up the search for an insertion point.

If hint information is available, it is highly beneficial to add this

Parameters
  • key – The key at which to insert

  • value – The value to insert

  • hint_after (optional) – A best guess after which key to insert. The requirement here is that the key compares

property _num_comparisons

Total number of comparisons performed between elements, e.g. when finding an insertion point

This number is low, if the insertion order is sequential. For out-of-order insertion, it may become large.

__delitem__(key, dict_delitem=<slot wrapper '__delitem__' of 'dict' objects>)[source]

kod.__delitem__(y) <==> del kod[y]

Deleting an existing item uses self.__map to find the link which gets removed by updating the links in the predecessor and successor nodes.

__iter__() <==> iter(kod)[source]

Traverse the linked list in order.

__reversed__() <==> reversed(kod)[source]

Traverse the linked list in reverse order.

clear()[source]

Remove all items

__sizeof__()[source]

Get the size of this object

update([E, ]**F) → None. Update D from mapping/iterable E and F.

If E present and has a .keys() method, does: for k in E: D[k] = E[k] If E present and lacks .keys() method, does: for (k, v) in E: D[k] = v In either case, this is followed by: for k, v in F.items(): D[k] = v

keys() → a set-like object providing a view on D's keys[source]
items() → a set-like object providing a view on D's items[source]
values() → an object providing a view on D's values[source]
pop(k[, d]) → v, remove specified key and return the[source]

corresponding value. If key is not found, default is returned if given, otherwise KeyError is raised.

setdefault(k[, d]) → kod.get(k,d), also set kod[k]=d if k not[source]

in kod

__reduce__()[source]

Return state information for pickling

copy() → a shallow copy of kod, maintaining the key comparator[source]
classmethod fromkeys(S[, v]) → New key-ordered dictionary with keys from S.[source]

If not specified, the value defaults to None.

__eq__(other)[source]

kod.__eq__(y) <==> kod==y. Comparison to another KeyOrderedDict or OrderedDict is order-sensitive while comparison to a regular mapping is order-insensitive.

_KeyOrderedDict__find_element_to_insert_after(key, *, start=None) → collections._Link

Finds the link in the doubly-linked list after which a new element with the given key may be inserted, i.e. the last element that compares False when invoking the key comparator.

If inserting an element to the back or the front of the key list, the complexity of this method is constant. Otherwise, it scales with the number of already existing elements.

Parameters
  • key – The key to find the insertion spot for

  • start (None, optional) – A key to use to start looking, if not given will use the last element as a best guess.

_KeyOrderedDict__marker = <object object>
_KeyOrderedDict__num_comparisons = 0
_KeyOrderedDict__update(**kwds)

D.update([E, ]**F) -> None. Update D from mapping/iterable E and F. If E present and has a .keys() method, does: for k in E: D[k] = E[k] If E present and lacks .keys() method, does: for (k, v) in E: D[k] = v In either case, this is followed by: for k, v in F.items(): D[k] = v

get()

Return the value for key if key is in the dictionary, else default.

popitem() → (k, v), remove and return some (key, value) pair as a

2-tuple; but raise KeyError if D is empty.

class dantro.utils.ordereddict.IntOrderedDict(*args, key: Callable = None, **kwds)[source]

Bases: dantro.utils.ordereddict.KeyOrderedDict

A KeyOrderedDict specialization that assumes keys to be castable to integer and using the comparison of the resulting integer values for maintaining the order

DEFAULT_KEY_COMPARATOR(k)
_KeyOrderedDict__find_element_to_insert_after(key, *, start=None) → collections._Link

Finds the link in the doubly-linked list after which a new element with the given key may be inserted, i.e. the last element that compares False when invoking the key comparator.

If inserting an element to the back or the front of the key list, the complexity of this method is constant. Otherwise, it scales with the number of already existing elements.

Parameters
  • key – The key to find the insertion spot for

  • start (None, optional) – A key to use to start looking, if not given will use the last element as a best guess.

_KeyOrderedDict__marker = <object object>
_KeyOrderedDict__num_comparisons = 0
_KeyOrderedDict__update(**kwds)

D.update([E, ]**F) -> None. Update D from mapping/iterable E and F. If E present and has a .keys() method, does: for k in E: D[k] = E[k] If E present and lacks .keys() method, does: for (k, v) in E: D[k] = v In either case, this is followed by: for k, v in F.items(): D[k] = v

__delitem__(key, dict_delitem=<slot wrapper '__delitem__' of 'dict' objects>)

kod.__delitem__(y) <==> del kod[y]

Deleting an existing item uses self.__map to find the link which gets removed by updating the links in the predecessor and successor nodes.

__eq__(other)

kod.__eq__(y) <==> kod==y. Comparison to another KeyOrderedDict or OrderedDict is order-sensitive while comparison to a regular mapping is order-insensitive.

__init__(*args, key: Callable = None, **kwds)

Initialize a KeyOrderedDict, which maintains key ordering. If no custom ordering function is given, orders by simple “smaller than” comparison.

Apart from that, the interface is the same as for regular dictionaries.

Parameters
  • *args – a single sequence of (key, value) pairs to insert

  • key (Callable, optional) – The callable used to

  • **kwds – Passed on to update method

Raises

TypeError – on len(args) > 1

__iter__() <==> iter(kod)

Traverse the linked list in order.

__reduce__()

Return state information for pickling

__reversed__() <==> reversed(kod)

Traverse the linked list in reverse order.

__setitem__(key, value, *, dict_setitem=<slot wrapper '__setitem__' of 'dict' objects>, proxy=<built-in function proxy>, Link=<class 'collections._Link'>, start=None)

Set the item with the provided key to the given value, maintaining the ordering specified by _key_comp_lt.

If the key is not available, this takes care of finding the right place to insert the new link in the doubly-linked list.

Unlike the regular __setitem__, this allows specifying a start element at which to begin the search for an insertion point, which may greatly speed up insertion. By default, it is attempted to insert after the last element; if that is not possible, a full search is done.

Warning

This operation does not scale well with out-of-order insertion!

This behavior is inherent to this data structure, where key ordering has to be maintained during every insertion. While a best guess is made regarding the insertion points (see above), inserting elements completely out of order will require a search time that is proportional to the number of elements for each insertion.

Hint

If you have information about where the element should be stored, use insert() and provide the hint_after argument.

__sizeof__()

Get the size of this object

_key_comp_lt(k1, k2) → bool

The key comparator. Returns true for k1 < k2.

Before comparison, the unary self._key method is invoked on both keys.

Parameters
  • k1 – lhs of comparison

  • k2 – rhs of comparison

Returns

k1 < k2

Return type

bool

property _num_comparisons

Total number of comparisons performed between elements, e.g. when finding an insertion point

This number is low, if the insertion order is sequential. For out-of-order insertion, it may become large.

clear()

Remove all items

copy() → a shallow copy of kod, maintaining the key comparator
classmethod fromkeys(S[, v]) → New key-ordered dictionary with keys from S.

If not specified, the value defaults to None.

get()

Return the value for key if key is in the dictionary, else default.

insert(key, value, *, hint_after=None)

Inserts a (key, value) pair using hint information to speed up the search for an insertion point.

If hint information is available, it is highly beneficial to add this

Parameters
  • key – The key at which to insert

  • value – The value to insert

  • hint_after (optional) – A best guess after which key to insert. The requirement here is that the key compares

items() → a set-like object providing a view on D's items
keys() → a set-like object providing a view on D's keys
pop(k[, d]) → v, remove specified key and return the

corresponding value. If key is not found, default is returned if given, otherwise KeyError is raised.

popitem() → (k, v), remove and return some (key, value) pair as a

2-tuple; but raise KeyError if D is empty.

setdefault(k[, d]) → kod.get(k,d), also set kod[k]=d if k not

in kod

update([E, ]**F) → None. Update D from mapping/iterable E and F.

If E present and has a .keys() method, does: for k in E: D[k] = E[k] If E present and lacks .keys() method, does: for (k, v) in E: D[k] = v In either case, this is followed by: for k, v in F.items(): D[k] = v

values() → an object providing a view on D's values