1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
|
.. currentmodule:: collections_extended
setlists
========
A :class:`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, :class:`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:
:class:`collections_extended.setlist`
This is a mutable setlist
:class:`collections_extended.frozensetlist`
This is a frozen (implements :class:`collections.abc.Hashable`) version of a setlist.
Both classes implement :class:`collections.abc.Sequence`, :class:`collections.abc.Set`
Examples
--------
.. code-block:: python
>>> 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:
* :meth:`setlist.swap(i, j)` to swap elements
* :meth:`setlist.shuffle(random=None)` instead of `random.shuffle(setlist)`
Errors
------
Some methods will raise a :exc:`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 :exc:`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 :class:`setlist`.
======================== =============== =================
Raises :exc:`ValueError` No Yes
Interface :class:`Set` :class:`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 :exc:`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 :exc:`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
^^^^^^^
.. autoclass:: collections_extended.SetList
setlist
^^^^^^^
.. autoclass:: collections_extended.setlist
frozensetlist
^^^^^^^^^^^^^
.. autoclass:: collections_extended.frozensetlist
|
