IndexedDicts

IndexedDict is an ordered mapping whose elements can be accessed using index, in addition to key. The interface is mostly a generalization of collections.OrderedDict.

Differences from OrderedDict

Methods get, pop and move_to_end have a different signature from OrderedDict, allowing exactly one of index or key argument to be used. This causes the IndexedDict to not be a drop in replacement to OrderedDict.

New Methods

fast_pop

Remove an item with given key and value from the IndexedDict by first swapping the item to the last position and then removing it. Returns tuple of (popped_value, new_moved_index, moved_key, moved_value). Time complexity of this operation is O(1).

index

Return index of a record with given key.

key

Return key of a record at given index.

Time Complexity

IndexedDict generally combines time complexity of dict and list. Indexed lookups cost list’s O(1), keyed lookups cost average case O(1) and worst case O(n) of dict. Deleting an element has a time complexity of O(1) if it is the last added one, or O(n) in general, in addition to the lookup cost.

API

class collections_extended.IndexedDict(iterable=None, **kwargs)

Bases: collections.abc.MutableMapping

A Mapping that preserves insertion order and allows access by item index.

The API is an extension of OrderedDict.

__init__(iterable=None, **kwargs)

Create an IndexedDict and initialize it like a dict.

clear()

Remove all items.

get(key=<not_set>, index=<not_set>, default=<not_set>, d=<not_set>)

Return value with given key or index.

If no value is found, return default (None by default).

Deprecated since version 1.0.3.

The d parameter has been renamed default. d will be removed in some future version.

Parameters

• key – The key of the value to get

• index – The index of the value to get

• default – The value to return if key is not found or index is out of bounds. If it is NOT_SET, None is returned.

• d – DEPRECATED: Old parameter name for default

pop(key=<not_set>, index=<not_set>, default=<not_set>, d=<not_set>)

Remove and return value.

Optionally, specify the key or index of the value to pop. If key is specified and is not found a KeyError is raised unless default is specified. Likewise, if index is specified that is out of bounds, an IndexError is raised unless default is specified.

Both index and key cannot be specified. If neither is specified, then the last value is popped.

This is generally O(N) unless removing last item, then O(1).

Deprecated since version 1.0.3.

The d parameter has been renamed default. d will be removed in some future version.

Parameters

• key – The key of the value to pop

• index – The index of the value to pop

• default – The value to return if the key is not found or the index is out of bounds

• d – DEPRECATED: Old parameter name for default

fast_pop(key=<not_set>, index=<not_set>)

Pop a specific item quickly by swapping it to the end.

Remove value with given key or index (last item by default) fast by swapping it to the last place first.

Changes order of the remaining items (item that used to be last goes to the popped location). Returns tuple of (poped_value, new_moved_index, moved_key, moved_value). If key is not found raises KeyError or IndexError.

Runs in O(1).

popitem(last=<not_set>, *, key=<not_set>, index=<not_set>)

Remove and return a (key, value) tuple.

By default, the last item is popped. Optionally, specify the key or index of the value to pop. The last parameter is included to match the OrderedDict API. If last is passed then the first or last item is returned based on its truthiness.

At most one of index, last and key can be specified.

This is generally O(N) unless removing last item, then O(1).

Parameters

• key – The key of the value to pop

• index – The index of the value to pop

• last – Whether or not to pip the last item

Raises

• KeyError – If the dictionary is empty or a key is specified that is not present

• IndexError – If index is specified and is out of bounds

• ValueError – If more than one of last, index and key are specified

move_to_end(key=<not_set>, index=<not_set>, last=True)

Move an existing element to the end (or beginning if last==False).

Runs in O(N).

copy()

Return a shallow copy.

index(key)

Return index of a record with given key.

Runs in O(1).

key(index)

Return key of a record at given index.

Runs in O(1).

__len__()

Return number of elements stored.

__getitem__(key)

Return value corresponding to given key.

Raises KeyError when the key is not present in the mapping.

Runs in O(1).

__setitem__(key, value)

Set item with given key to given value.

If the key is already present in the mapping its order is unchanged, if it is not then it’s added to the last place.

Runs in O(1).

__delitem__(key)

Remove item with given key from the mapping.

Runs in O(n), unless removing last item, then in O(1).

__contains__(key)

Check if a key is present in the mapping.

Runs in O(1).

__iter__()

Return iterator over the keys of the mapping in order.