setlists

A setlist is an ordered, indexed collection with unique elements. It it more than just an ordered Set in that the elements are accessible by index (ie. not just a linked set).

However, setlist’s are not comparable like sets or lists. Equality testing still works, but setlist(('a', 'c')) < setlist(('a', 'b')) does not because we’d have to choose to compare by order or by set comparison.

There are two classes provided:

collections_extended.setlist

This is a mutable setlist

collections_extended.frozensetlist

This is a frozen (implements collections.abc.Hashable) version of a setlist.

Both classes implement collections.abc.Sequence, collections.abc.Set

Examples

>>> from collections_extended import setlist
>>> import string
>>> sl = setlist(string.ascii_lowercase)
>>> sl
setlist(('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'))
>>> sl[3]
'd'
>>> sl[-1]
'z'
>>> 'r' in sl   # testing for inclusion is fast
True
>>> sl.index('m')       # so is finding the index of an element
12
>>> sl.insert(1, 'd')   # inserting an element already in raises a ValueError
Traceback (most recent call last):
...
        raise ValueError
ValueError
>>> sl.index('d')
3

Compared to existing similar implementations

Most implementations I’ve see are ordered sets where items are not accessible by index.

Compared to Standard Types

setlist vs. list

• Inclusion testing is O(1)

• Finding an element is O(1)

• Adding an element that is already present raises a ValueError

setlist vs. set

• Elements are ordered and accessible by index

• Adding an element is as slow as adding to a list

  • Amortized O(n) for arbitrary insertions

  • O(1) for appending

New Methods

Swapping values doesn’t work (see Quirks) so some things don’t work. To work around that a couple of methods were added:

• setlist.swap(i, j)() to swap elements

• setlist.shuffle(random=None)() instead of random.shuffle(setlist)

Errors

Some methods will raise a ValueError when trying to add or remove elements when they respectively already or do not currently exist in the setlist. Each method has an analogous version that does/doesn’t raise a ValueError. Methods implementing the Set methods do not raise ValueError while the one’s implementing Sequence do. All will raise TypeError if you use unhashable values. The bulk operations are atomic, if any single value is unhashable or a duplicate, no changes will be made to the setlist.

Raises ValueError	No	Yes
Interface	Set	Sequence
Add a single value	add	append
Add multiple values	update	extend
Remove a single value	discard	remove
Remove multiple values	discard_all	remove_all

The setlist constructor by defualt does not raise ValueError on duplicate values because we have to choose one or the other and this matches the behavior of Set. There is a flag raise_on_duplicate that can be passed to __init__ to raise a ValueError if duplicate values are passed.

Quirks

• Swapping elements, eg. sl[0], sl[1] = sl[1], sl[0], doesn’t work because

  it is implemented by first setting one element then the other. But since the first element it tries to set is still in the setlist, nothing happens. This causes random.shuffle not to work on a setlist.

API

SetList

class collections_extended.SetList(iterable=None, raise_on_duplicate=False)

Bases: collections.abc.Sequence, collections.abc.Set

A setlist is an ordered Collection of unique elements.

SetList is the superclass of setlist and frozensetlist. It is immutable and unhashable.

__init__(iterable=None, raise_on_duplicate=False)

Create a setlist, initializing from iterable if present.

Parameters

• iterable (Iterable) – Values to initialize the setlist with.

• raise_on_duplicate – Raise a ValueError if any duplicate values are present.

count(value)

Return the number of occurrences of value in self.

This runs in O(1)

Parameters

value – The value to count

Returns

1 if the value is in the setlist, otherwise 0

Return type

int

index(value, start=0, end=None)

Return the index of value between start and end.

By default, the entire setlist is searched.

This runs in O(1)

Parameters

• value – The value to find the index of

• start (int) – The index to start searching at (defaults to 0)

• end (int) – The index to stop searching at (defaults to the end of the list)

Returns

The index of the value

Return type

int

Raises

• ValueError – If the value is not in the list or outside of start - end

• IndexError – If start or end are out of range

issubset(other)

Report whether another set contains this set.

issuperset(other)

Report whether this set contains another set.

union(other)

Return the union of sets as a new set.

(i.e. all elements that are in either set.)

intersection(other)

Return the intersection of two sets as a new set.

(i.e. all elements that are in both sets.)

difference(other)

Return the difference of two or more sets as a new set.

(i.e. all elements that are in this set but not the others.)

symmetric_difference(other)

Return the symmetric difference (disjuntive union) of two sets.

(i.e. all elements that are in one set but not both.)

sub_index(sub, start=0, end=None)

Return the index of a subsequence.

This runs in O(len(sub))

Parameters

• sub (Sequence) – An Iterable to search for

• start (int) – The index at which to start the search

• end (int) – The index at which to end the search

Returns

The index of the first element of sub

Return type

int

Raises

• ValueError – If sub isn’t a subsequence

• TypeError – If sub isn’t iterable

• IndexError – If start or end are out of range

copy()

Return a shallow copy of the setlist.

setlist

class collections_extended.setlist(iterable=None, raise_on_duplicate=False)

Bases: collections_extended.setlists.SetList, collections.abc.MutableSequence, collections.abc.MutableSet

A mutable (unhashable) setlist.

__init__(iterable=None, raise_on_duplicate=False)

Create a setlist, initializing from iterable if present.

Parameters

• iterable (Iterable) – Values to initialize the setlist with.

• raise_on_duplicate – Raise a ValueError if any duplicate values are present.

pop(index=- 1)

Remove and return the item at index.

clear()

Remove all elements from self.

insert(index, value)

Insert value at index.

Parameters

• index (int) – Index to insert value at

• value – Value to insert

Raises

• ValueError – If value already in self

• IndexError – If start or end are out of range

append(value)

Append value to the end.

Parameters

value – Value to append

Raises

• ValueError – If value alread in self

• TypeError – If value isn’t hashable

extend(values)

Append all values to the end.

If any of the values are present, ValueError will be raised and none of the values will be appended.

Parameters

values (Iterable) – Values to append

Raises

• ValueError – If any values are already present or there are duplicates in the passed values.

• TypeError – If any of the values aren’t hashable.

__iadd__(values)

Add all values to the end of self.

Parameters

values (Iterable) – Values to append

Raises

ValueError – If any values are already present

remove(value)

Remove value from self.

Parameters

value – Element to remove from self

Raises

ValueError – if element is already present

remove_all(elems_to_delete)

Remove all elements from elems_to_delete, raises ValueErrors.

See also

discard_all

Parameters

elems_to_delete (Iterable) – Elements to remove.

Raises

• ValueError – If the count of any element is greater in elems_to_delete than self.

• TypeError – If any of the values aren’t hashable.

reverse()

Reverse the setlist in-place.

add(item)

Add an item.

Note

This does not raise a ValueError for an already present value like append does. This is to match the behavior of set.add

Parameters

item – Item to add

Raises

TypeError – If item isn’t hashable.

update(values)

Add all values to the end.

If any of the values are present, silently ignore them (as opposed to extend which raises an Error).

See also

extend

Parameters

values (Iterable) – Values to add

Raises

TypeError – If any of the values are unhashable.

discard_all(elems_to_delete)

Discard all the elements from elems_to_delete.

This is much faster than removing them one by one. This runs in O(len(self) + len(elems_to_delete))

Parameters

elems_to_delete (Iterable) – Elements to discard.

Raises

TypeError – If any of the values aren’t hashable.

discard(value)

Discard an item.

Note

This does not raise a ValueError for a missing value like remove does. This matches the behavior of set.discard

difference_update(other)

Update self to include only the difference with other.

intersection_update(other)

Update self to include only the intersection with other.

symmetric_difference_update(other)

Update self to include only the symmetric difference with other.

shuffle(random=None)

Shuffle all of the elements in self in place.

Parameters

random – A function returning a random float in [0.0, 1.0). If none is passed, the default from random.shuffle will be used.

sort(*args, **kwargs)

Sort this setlist in place.

swap(i, j)

Swap the values at indices i & j.

New in version 1.0.3.

frozensetlist

class collections_extended.frozensetlist(iterable=None, raise_on_duplicate=False)

Bases: collections_extended.setlists.SetList, collections.abc.Hashable

An immutable (hashable) setlist.

__init__(iterable=None, raise_on_duplicate=False)

Create a setlist, initializing from iterable if present.

Parameters

• iterable (Iterable) – Values to initialize the setlist with.

• raise_on_duplicate – Raise a ValueError if any duplicate values are present.