sorteddict

class blist.sorteddict([key,] [arg,] **kw)

A sorteddict provides the same methods as a dict. Additionally, a sorteddict efficiently maintains its keys in sorted order. Consequently, the keys method will return the keys in sorted order, the popitem method will remove the item with the lowest key, etc.

key specifies a function of one argument that is used to extract a comparison sort key from each dict key, e.g. sorteddict(str.lower). If no function is specified, the default compares the elements directly. The key function must always return the same key for an item or the results are unpredictable. The key argument must be provided as a positional argument; if provided as a keyword argument, it will be added to the dictionary instead.

An optional iterable provides an initial series of items to populate the sorteddict. Each item in the series must itself contain to items. The first is used as a key in the new dictionary, and the second as the key’s value. If a given key is seen more than once, the last value associated with it is retained in the new dictionary.

If keyword arguments are given, the keywords themselves with their associated values are added as items to the dictionary. If a key is specified both in the positional argument and as a keyword argument, the value associated with the keyword is retained in the dictionary. For example, these all return a dictionary equal to {"one": 2, "two": 3}:

  • sorteddict(one=2, two=3)
  • sorteddict({'one': 2, 'two': 3})
  • sorteddict(zip(('one', 'two'), (2, 3)))
  • sorteddict([['two', 3], ['one', 2]])

The first example only works for keys that are valid Python identifiers; the others work with any valid keys.

x in d

Returns True if and only if x is a key in the dictionary.

Requires \Theta\left(1\right) operations in the average case.

Return type:bool
del d[key]

Remove d[key] from d. Raises a KeyError if key is not in the dictionary.

Requires \Theta\left(\log n\right) comparisons.

d[key]

Return the item of d with key key. Raises a KeyError if key is not in the dictionary.

If a subclass of dict defines a method __missing__(), if the key key is not present, the d[key] operation calls that method with the key key as argument. The d[key] operation then returns or raises whatever is returned or raised by the __missing__(key) call if the key is not present. No other operations or methods invoke __missing__(). If __missing__() is not defined, KeyError is raised. __missing__() must be a method; it cannot be an instance variable.

Requires \Theta\left(1\right) operations in the average case.

Return type:value
L == L2, L != L2

Test two dictionaries for equality (or inequality). Dictionaries compare equal if and only if they have the same length, if all of the keys of L may be found in L2, and all of the corresponding values compare equal.

In the worst case, requires \Theta\left(n\right) operations and \Theta\left(n\right) comparisons.

Return type:bool
iter(d)

Creates an iterator over the sorted keys of the dictionary.

Requires \Theta\left(\log n\right) operations to create the iterator. Each element from the iterator requires \Theta\left(1\right) operations to retrieve, or \Theta\left(n\right) operations to iterate over the entire dictionary.

Return type:iterator
len(d)

Returns the number of (key, value) pairs in the dictionary.

Requires \Theta\left(1\right) operations.

Return type:int
d[key] = value

Sets d[key] to value.

In the average case, requires \Theta\left(\log^2 n\right) operations and \Theta\left(\log n\right) comparisons.

d.clear()

Remove all elements from the dictionary.

Requires \Theta\left(n\right) total operations in the worst case.

d.copy()

Creates a shallow copy of the dictionary.

Requires \Theta\left(n\right) total operations and no comparisons.

Return type:sorteddict
d.fromkeys(seq[, value[, key]])

Create a new dictionary with keys from seq and values set to value. key specifies a function of one argument that is used to extract a comparison sort key from each dict key.

fromkeys() is a class method that returns a new dictionary. value defaults to None.

Return type:sorteddict
d.get(key[, default])

Return the value for key if key is in the dictionary, else default. If default is not given, it defaults to None, so that this method never raises a KeyError.

Requires \Theta\left(1\right) total operations in the average case.

Return type:value
d.items()

In Python 2, returns a blist of the dictionary’s items ((key, value) pairs).

In Python 3, returns a new ItemsView of the dictionary’s items. In addition to the methods provided by the built-in view, the ItemsView is indexable (e.g., d.items()[5]).

Requires \Theta\left(n\right) operations.

Return type:blist or ItemsView
d.keys()

In Python 2, returns a sortedset of the dictionary’s keys.

In Python 3, returns a new KeysView of the dictionary’s keys. In addition to the methods provided by the built-in view, the KeysView is indexable (e.g., d.keys()[5]).

Requires \Theta\left(1\right) operations.

Return type:sortedset or KeysView
d.pop(key[, default])

If key is in the dictionary, remove it and return its value, else return default. If default is not given and key is not in the dictionary, a KeyError is raised.

Requires \Theta\left(1\right) operations if key is not in the dictionary. Otherwise, requires \Theta\left(\log n\right) comparisons.

Return type:value
d.popitem()

Remove and return the (key, value) pair with the least key from the dictionary.

If the dictionary is empty, calling popitem() raises a KeyError.

Requires \Theta\left(\log n\right) operations and no comparisons.

Return type:(key, value) tuple
d.setdefault(key[, default])

If key is in the dictionary, return its value. If not, insert key with a value of default and return default. default defaults to None.

Requires \Theta\left(1\right) operations if key is already in the dictionary. Otherwise, requires \Theta\left(\log n\right) comparisons.

d.update(other, ...)

Update the dictionary with the key/value pairs from other, overwriting existing keys.

update() accepts either another dictionary object or an iterable of key/value pairs (as a tuple or other iterable of length two). If keyword arguments are specified, the dictionary is then updated with those key/value pairs: d.update(red=1, blue=2).

In the average case, requires \Theta\left(m \log^2
\left(n + m\right)\right) operations and \Theta\left(m \log\left(n + m\right)\right) comparisons, where m is the combined size of all the other sets and n is the initial size of d.

d.values()

In Python 2, returns a blist of the dictionary’s values.

In Python 3, returns a new ValuesView of the dictionary’s values. In addition to the methods provided by the built-in view, the ValuesView is indexable (e.g., d.values()[5]).

Requires \Theta\left(n\right) operations.

Return type:blist or ValuesView
class blist.KeysView

A KeysView object is a dynamic view of the dictionary’s keys, which means that when the dictionary’s keys change, the view reflects those changes.

The KeysView class implements the Set and Sequence Abstract Base Classes.

len(keysview)

Returns the number of entries in the dictionary.

Requires \Theta\left(1\right) operations.

Return type:int
iter(keysview)

Returns an iterator over the keys in the dictionary. Keys are iterated over in their sorted order.

Iterating views while adding or deleting entries in the dictionary may raise a RuntimeError or fail to iterate over all entries.

Requires \Theta\left(\log n\right) operations to create the iterator. Each element from the iterator requires \Theta\left(1\right) operations to retrieve, or \Theta\left(n\right) operations to iterate over the entire dictionary.

Return type:iterator
x in keysview

Returns True iff x is one of the underlying dictionary’s keys.

Requires \Theta\left(1\right) operations.

Return type:bool
keysview[i]

Returns the key at position i.

Requires \Theta\left(1\right) operations if the dictionary’s size has not been changed recently. Otherwise, requires \Theta\left(\log n\right) operations.

Return type:value
keysview & other

Returns the intersection of the keys and the other object as a new set.

Requires \Theta\left(m \log^2
\left(n + m\right)\right) operations and \Theta\left(m \log\left(n + m\right)\right) comparisons, where m is the size of other and n is the size of keysview.

Return type:sortedset
keysview | other

Returns the union of the keys and the other object as a new set.

Requires \Theta\left(m \log^2
\left(n + m\right)\right) operations or \Theta\left(m \log\left(n + m\right)\right) comparisons, where m is the size of other and n is the size of S.

Return type:sortedset
keysview - other

Return the difference between the keys and the other object (all keys that aren’t in other) as a new set.

Requires \Theta\left(m \log^2
\left(n + m\right)\right) operations and \Theta\left(m \log\left(n + m\right)\right) comparisons, where m is the size of other and n is the size of keysview.

Rtype:sortedset
keysview ^ other

Return the symmetric difference (all elements either in the keys or other, but not in both) of the keys and the other object as a new set.

Requires \Theta\left(m \log^2
\left(n + m\right)\right) operations and \Theta\left(m \log\left(n + m\right)\right) comparisons, where m is the size of other and n is the size of keysview.

Rtype:sortedset
L.bisect_left(value)

Similarly to the bisect module in the standard library, this returns an appropriate index to insert value in L. If value is already present in L, the insertion point will be before (to the left of) any existing entries.

Requires \Theta\left(\log^2 n\right) total operations or \Theta\left(\log n\right) comparisons.

L.bisect(value)

Same as bisect_left.

L.bisect_right(value)

Same thing as bisect_left, but if value is already present in L, the insertion point will be after (to the right of) any existing entries.

keysview.count(key)

Returns the number of occurrences of key in the set.

Requires \Theta\left(1\right) operations.

Return type:int
keysview.index(key[, start[, stop]])

Returns the smallest k such that keysview[k] == x and i <= k < j. Raises KeyError if key is not present. stop defaults to the end of the set. start defaults to the beginning. Negative indexes are supported, as for slice indices.

Requires \Theta\left(1\right) operations.

Return type:int
class blist.ValuesView

A ValuesView object is a dynamic view of the dictionary’s values, which means that when the dictionary’s values change, the view reflects those changes.

The ValuesView class implements the Sequence Abstract Base Class.

len(valuesview)

Returns the number of entries in the dictionary.

Requires \Theta\left(1\right) operations.

Return type:int
iter(valuesview)

Returns an iterator over the values in the dictionary. Values are iterated over in sorted order of the keys.

Iterating views while adding or deleting entries in the dictionary may raise a RuntimeError or fail to iterate over all entries.

Requires \Theta\left(\log n\right) operations to create the iterator. Each element from the iterator requires \Theta\left(1\right) operations to retrieve, or \Theta\left(n\right) operations to iterate over the entire dictionary.

Return type:iterator
x in valuesview

Returns True iff x is one of the underlying dictionary’s values.

Requires \Theta\left(n\right) operations.

Return type:bool
valuesview[i]

Returns the value at position i.

Requires \Theta\left(1\right) operations if the dictionary’s size has not been changed recently. Otherwise, requires \Theta\left(\log n\right) operations.

Return type:value
valuesview.count(value)

Returns the number of occurrences of value in the set.

Requires \Theta\left(n\right) operations and \Theta\left(n\right) comparisons in the worst case.

Return type:int
valuesview.index(value[, start[, stop]])

Returns the smallest k such that valuesview[k] == x and i <= k < j. Raises KeyError if value is not present. stop defaults to the end of the set. start defaults to the beginning. Negative indexes are supported, as for slice indices.

In the worst case, requires \Theta\left(\textrm{start}-\textrm{stop}\right) operations and \Theta\left(\textrm{start}-\textrm{stop}\right) comparisons.

Return type:int
class blist.ItemsView

A ItemsView object is a dynamic view of the dictionary’s (key, value) pairs, which means that when the dictionary changes, the view reflects those changes.

The ItemsView class implements the Set and Sequence Abstract Base Classes. However, the set-like operations (&, |, -, ^) will only operate correctly if all of the dictionary’s values are hashable.

len(itemsview)

Returns the number of entries in the dictionary.

Requires \Theta\left(1\right) operations.

Return type:int
iter(itemsview)

Returns an iterator over the items in the dictionary. Items are iterated over in sorted order of the keys.

Iterating views while adding or deleting entries in the dictionary may raise a RuntimeError or fail to iterate over all entries.

Requires \Theta\left(\log n\right) operations to create the iterator. Each element from the iterator requires \Theta\left(1\right) operations to retrieve, or \Theta\left(n\right) operations to iterate over the entire dictionary.

Return type:iterator
x in itemsview

Returns True iff x is one of the underlying dictionary’s items.

Requires \Theta\left(1\right) operations.

Return type:bool
itemsview[i]

Returns the (key, value) pair at position i.

Requires \Theta\left(1\right) operations if the dictionary’s size has not been changed recently. Otherwise, requires \Theta\left(\log n\right) operations.

Return type:item
itemsview & other

Returns the intersection of the items and the other object as a new set.

Requires \Theta\left(m \log^2
\left(n + m\right)\right) operations and \Theta\left(m \log\left(n + m\right)\right) comparisons, where m is the size of other and n is the size of itemsview.

Return type:sortedset
itemsview | other

Returns the union of the items and the other object as a new set.

Requires \Theta\left(m \log^2
\left(n + m\right)\right) operations or \Theta\left(m \log\left(n + m\right)\right) comparisons, where m is the size of other and n is the size of S.

Return type:sortedset
itemsview - other

Return the difference between the items and the other object (all items that aren’t in other) as a new set.

Requires \Theta\left(m \log^2
\left(n + m\right)\right) operations and \Theta\left(m \log\left(n + m\right)\right) comparisons, where m is the size of other and n is the size of itemsview.

Rtype:sortedset
itemsview ^ other

Return the symmetric difference (all elements either in the items or other, but not in both) of the items and the other object as a new set.

Requires \Theta\left(m \log^2
\left(n + m\right)\right) operations and \Theta\left(m \log\left(n + m\right)\right) comparisons, where m is the size of other and n is the size of itemsview.

Rtype:sortedset
itemsview.count(item)

Returns the number of occurrences of item in the set.

Requires \Theta\left(1\right) operations.

Return type:int
itemsview.index(item[, start[, stop]])

Returns the smallest k such that itemsview[k] == x and i <= k < j. Raises KeyError if item is not present. stop defaults to the end of the set. start defaults to the beginning. Negative indexes are supported, as for slice indices.

Requires \Theta\left(1\right) operations.

Return type:int