Datastructures

This module provides various datastructures.

brownie.datastructures.missing

Sentinel object which can be used instead of None. This is useful if you have optional parameters to which a user can pass None e.g. in datastructures.

brownie.datastructures.iter_multi_items(mapping)

Iterates over the items of the given mapping.

If a key has multiple values a (key, value) item is yielded for each:

>>> for key, value in iter_multi_items({1: [2, 3]}):
...     print key, value
1 2
1 3
>>> for key, value in iter_multi_items(MultiDict({1: [2, 3]})):
...     print key, value
1 2
1 3

class brownie.datastructures.StackedObject(mappings)

An object whose attributes are looked up in a mapping residing in an internal stack.

If an attribute is accessed, the value of the first mapping, which contains the appropriate attribute, is returned.

New in version 0.6.

top

The top-most object.

push(mapping)

Pushes the given mapping on the stack.

pop()

Pops the given mapping from the stack.

If the stack is empty a RuntimeError is raised.

Mappings

class brownie.datastructures.MultiDict(*args, **kwargs)

A MultiDict is a dictionary customized to deal with multiple values for the same key.

Internally the values for each key are stored as a list, but the standard dict methods will only return the first value of those lists. If you want to gain access to every value associated with a key, you have to use the list methods, specific to a MultiDict.

add(key, value)

Adds the value for the given key.

getlist(key)

Returns the list of values for the given key. If there are none an empty list is returned.

setlist(key, values)

Sets the values associated with the given key to the given values.

setlistdefault(key, default_list=None)

Like setdefault() but sets multiple values and returns the list associated with the key.

lists()

Returns a list of (key, values) pairs, where values is the list of values associated with the key.

listvalues()

Returns a list of all values.

iterlists()

Like lists() but returns an iterator.

iterlistvalues()

Like listvalues() but returns an iterator.

poplist(key)

Returns the list of values associated with the given key, if the key does not exist in the MultiDict an empty list is returned.

popitemlist()

Like popitem() but returns all associated values.

class brownie.datastructures.OrderedDict(*args, **kwargs)

A dict which remembers insertion order.

Big-O times for every operation are equal to the ones dict has however this comes at the cost of higher memory usage.

This dictionary is only equal to another dictionary of this type if the items on both dictionaries were inserted in the same order.

popitem(last=True)

Pops the last or first item from the dict depending on last.

move_to_end(key, last=True)

Moves the item with the given key to the end of the dictionary if last is True otherwise to the beginning.

Raises KeyError if no item with the given key exists.

New in version 0.4.

class brownie.datastructures.Counter(countable=None, **kwargs)

dict subclass for counting hashable objects. Elements are stored as keys with the values being their respective counts.

Parameters:countable – An iterable of elements to be counted or a dict-like object mapping elements to their respective counts.

This object supports several operations returning a new Counter object from the common elements of c1 and c2, in any case the new counter will not contain negative counts.

Operation	Result contains...
c1 + c2	sums of common element counts.
c1 - c2	difference of common element counts.
c1 | c2	maximum of common element counts.
c1 & c2	minimum of common element counts.

Furthermore it is possible to multiply the counter with an int as scalar.

Accessing a non-existing element will always result in an element count of 0, accordingly get() uses 0 and setdefault() uses 1 as default value.

most_common(n=None)

Returns a list of all items sorted from the most common to the least.

Parameters:n – If given only the items of the n-most common elements are returned.

>>> from brownie.datastructures import Counter
>>> Counter('Hello, World!').most_common(2)
[('l', 3), ('o', 2)]

elements()

Iterator over the elements in the counter, repeating as many times as counted.

>>> from brownie.datastructures import Counter
>>> sorted(Counter('abcabc').elements())
['a', 'a', 'b', 'b', 'c', 'c']

update(countable=None, **kwargs)

Updates the counter from the given countable and kwargs.

class brownie.datastructures.OrderedMultiDict(*args, **kwargs)

An ordered MultiDict.

class brownie.datastructures.FixedDict

A dict whose items can only be created or deleted not changed.

If you attempt to change an item a KeyError is raised.

New in version 0.5.

Immutable Mappings

class brownie.datastructures.ImmutableDict

An immutable dict.

New in version 0.5: ImmutableDict is now hashable, given the content is.

class brownie.datastructures.ImmutableMultiDict(*args, **kwargs)

An immutable MultiDict.

New in version 0.5: ImmutableMultiDict is now hashable, given the content is.

class brownie.datastructures.ImmutableOrderedDict(*args, **kwargs)

An immutable OrderedDict.

New in version 0.2.

New in version 0.5: ImmutableOrderedDict is now hashable, given the content is.

class brownie.datastructures.ImmutableOrderedMultiDict(*args, **kwargs)

An immutable OrderedMultiDict.

Combining Mappings

class brownie.datastructures.CombinedDict(dicts=None)

An immutable dict which combines the given dicts into one.

You can use this class to combine dicts of any type, however different interfaces as provided by e.g. MultiDict or Counter are not supported, the same goes for additional keyword arguments.

New in version 0.2.

New in version 0.5: CombinedDict is now hashable, given the content is.

class brownie.datastructures.CombinedMultiDict(dicts=None)

An ImmutableMultiDict which combines the given dicts into one.

New in version 0.2.

Sequences

class brownie.datastructures.LazyList(iterable)

Implements a lazy list which computes items based on the given iterable.

This allows you to create list-like objects of unlimited size. However although most operations don’t exhaust the internal iterator completely some of them do, so if the given iterable is of unlimited size making such an operation will eventually cause a MemoryError.

Cost in terms of laziness of supported operators, this does not include supported operators without any cost:

Operation	Result
list[i]	This exhausts the list up until the given index.
list[i] = x
del list[i]
len(list)	Exhausts the internal iterator.
x in list	Exhausts the list up until x or until the list is exhausted.
l1 == l2	Exhausts both lists.
l1 != l2	Exhausts both lists.
bool(list)	Exhausts the list up to the first item.
l1 < l2	Exhausts the list up to the first item which shows the result. In the worst case this exhausts both lists.
l1 > l2
l1 + l2	Creates a new LazyList without exhausting l1 or l2.
list * n	Exhausts the list.
list *= n

New in version 0.5: It is now possible to pickle LazyLists, however this will exhaust the list.

classmethod factory(callable)

Returns a wrapper for a given callable which takes the return value of the wrapped callable and converts it into a LazyList.

insert(index, object)

Inserts the given object at the given index.

This method exhausts the internal iterator up until the given index.

pop(index=None)

Removes and returns the item at the given index, if no index is given the last item is used.

This method exhausts the internal iterator up until the given index.

remove(object)

Looks for the given object in the list and removes the first occurrence.

If the item is not found a ValueError is raised.

This method exhausts the internal iterator up until the first occurrence of the given object or entirely if it is not found.

reverse(*args, **kwargs)

Reverses the list.

This method exhausts the internal iterator.

sort(*args, **kwargs)

Sorts the list using the given cmp or key function and reverses it if reverse is True.

This method exhausts the internal iterator.

count(*args, **kwargs)

Counts the occurrences of the given object in the list.

This method exhausts the internal iterator.

index(object)

Returns first index of the object in list

This method exhausts the internal iterator up until the given object.

class brownie.datastructures.CombinedSequence(sequences)

A sequence combining other sequences.

New in version 0.5.

at_index(index)

Returns the sequence and the ‘sequence local’ index:

>>> foo = [1, 2, 3]
>>> bar = [4, 5, 6]
>>> cs = CombinedSequence([foo, bar])
>>> cs[3]
4
>>> cs.at_index(3)
([4, 5, 6], 0)

class brownie.datastructures.CombinedList(sequences)

A list combining other lists.

New in version 0.5.

count(item)

Returns the number of occurrences of the given item.

index(item, start=None, stop=None)

Returns the index of the first occurence of the given item between start and stop.

append(item)

Appends the given item to the end of the list.

extend(items)

Extends the list by appending from the given iterable.

insert(index, item)

Inserts the given item before the item at the given index.

pop(index=-1)

Removes and returns the item at the given index.

An IndexError is raised if the index is out of range.

remove(item)

Removes the first occurence of the given item from the list.

reverse()

Reverses the list in-place:

>>> a = [1, 2, 3]
>>> b = [4, 5, 6]
>>> l = CombinedList([a, b])
>>> l.reverse()
>>> a
[6, 5, 4]

sort(cmp=None, key=None, reverse=False)

Sorts the list in-place, see list.sort().

brownie.datastructures.namedtuple(typename, field_names, verbose=False, rename=False, doc=None)

Returns a tuple subclass named typename with a limited number of possible items who are accessible under their field name respectively.

Due to the implementation typename as well as all field_names have to be valid python identifiers also the names used in field_names may not repeat themselves.

You can solve the latter issue for field_names by passing rename=True, any given name which is either a keyword or a repetition is then replaced with _n where n is an integer increasing with every rename starting by 1.

namedtuple() creates the code for the subclass and executes it internally you can view that code by passing verbose==True, which will print the code.

Unlike tuple a named tuple provides several methods as helpers:

class brownie.datastructures.SomeNamedTuple(foo, bar)

classmethod _make(iterable)

Returns a SomeNamedTuple populated with the items from the given iterable.

_asdict()

Returns a dict mapping the field names to their values.

_replace(**kwargs)

Returns a SomeNamedTuple values replaced with the given ones:

>>> t = SomeNamedTuple(1, 2)
>>> t._replace(bar=3)
SomeNamedTuple(foo=1, bar=3)

Note

namedtuple() is compatible with collections.namedtuple().

New in version 0.5.

Sets

class brownie.datastructures.OrderedSet(iterable=None)

A set which remembers insertion order.

New in version 0.2.

pop(last=True)

Returns the last element if last is True, the first otherwise.

Queues

class brownie.datastructures.SetQueue(maxsize=0)

Bases: Queue.Queue

Thread-safe implementation of an ordered set queue, which coalesces duplicate items into a single item if the older occurrence has not yet been read and maintains the order of items in the queue.

Ordered set queues are useful when implementing data structures like event buses or event queues where duplicate events need to be coalesced into a single event. An example use case is the inotify API in the Linux kernel which shares the same behaviour.

Queued items must be immutable and hashable so that they can be used as dictionary keys or added to sets. Items must have only read-only properties and must implement the __hash__(), __eq__(), and __ne__() methods to be hashable.

An example item class implementation follows:

class QueuedItem(object):
    def __init__(self, a, b):
        self._a = a
        self._b = b

    @property
    def a(self):
        return self._a

    @property
    def b(self):
        return self._b

    def _key(self):
        return (self._a, self._b)

    def __eq__(self, item):
        return self._key() == item._key()

    def __ne__(self, item):
        return self._key() != item._key()

    def __hash__(self):
        return hash(self._key())

Note

This ordered set queue leverages locking already present in the queue.Queue class redefining only internal primitives. The order of items is maintained because the internal queue is not replaced. An internal set is used merely to check for the existence of an item in the queue.

New in version 0.3.

Author :Gora Khargosh <gora.khargosh@gmail.com> Author :Lukáš Lalinský <lalinsky@gmail.com>

empty()

Return True if the queue is empty, False otherwise (not reliable!).

full()

Return True if the queue is full, False otherwise (not reliable!).

get(block=True, timeout=None)

Remove and return an item from the queue.

If optional args ‘block’ is true and ‘timeout’ is None (the default), block if necessary until an item is available. If ‘timeout’ is a positive number, it blocks at most ‘timeout’ seconds and raises the Empty exception if no item was available within that time. Otherwise (‘block’ is false), return an item if one is immediately available, else raise the Empty exception (‘timeout’ is ignored in that case).

get_nowait()

Remove and return an item from the queue without blocking.

Only get an item if one is immediately available. Otherwise raise the Empty exception.

join()

Blocks until all items in the Queue have been gotten and processed.

The count of unfinished tasks goes up whenever an item is added to the queue. The count goes down whenever a consumer thread calls task_done() to indicate the item was retrieved and all work on it is complete.

When the count of unfinished tasks drops to zero, join() unblocks.

put(item, block=True, timeout=None)

Put an item into the queue.

If optional args ‘block’ is true and ‘timeout’ is None (the default), block if necessary until a free slot is available. If ‘timeout’ is a positive number, it blocks at most ‘timeout’ seconds and raises the Full exception if no free slot was available within that time. Otherwise (‘block’ is false), put an item on the queue if a free slot is immediately available, else raise the Full exception (‘timeout’ is ignored in that case).

put_nowait(item)

Put an item into the queue without blocking.

Only enqueue the item if a free slot is immediately available. Otherwise raise the Full exception.

qsize()

Return the approximate size of the queue (not reliable!).

task_done()

Indicate that a formerly enqueued task is complete.

Used by Queue consumer threads. For each get() used to fetch a task, a subsequent call to task_done() tells the queue that the processing on the task is complete.

If a join() is currently blocking, it will resume when all items have been processed (meaning that a task_done() call was received for every item that had been put() into the queue).

Raises a ValueError if called more times than there were items placed in the queue.

Iterators

class brownie.datastructures.PeekableIterator(iterable)

An iterator which allows peeking.

New in version 0.6.

peek(n=1)

Returns the next n items without consuming the iterator, if the iterator has less than n items these are returned.

Raises ValueError if n is lower than 1.