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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
|
.. py:currentmodule:: collections_extended
bags (Multisets)
================
`bag` is a multiset_ implementation for Python.
Currently, bags have constant time inclusion testing but can only contain
hashable elements due to the implementation.
.. _multiset: http://en.wikipedia.org/wiki/Multiset
There are three classes provided:
:class:`Bag`
An abstract base class for bags.
:class:`bag`
A mutable (unhashable) bag.
:class:`frozenbag`
An immutable (implements :class:`collections.abc.Hashable`) version of a bag.
Both classes implement :class:`collections.abc.Sized`,
:class:`collections.abc.Iterable` and :class:`collections.abc.Container`.
Both classes implement :class:`collections.abc.Collection` starting in Python
3.6 and the polyfilled :class:`Collection` for Python < 3.6.
Set Operations
--------------
:class:`bag` and :class:`frozenbag` use python operators for multiset
operations:
* `__add__` (`a + b`): The sum of two multisets
* `__sub__` (`a - b`): The difference between a and b
* `__and__` (`a & b`): The intersection of a and b
* `__or__` (`a | b`): The union of a and b
* `__xor__` (`a ^ b`): The symmetric difference between a and b
:class:`bag` has the equivalent in-place operators defined.
Comparison Methods
------------------
Bags are comparable only to other bags.
Ordering comparisons are done setwise.
.. testsetup::
>>> from collections_extended import bag
.. code-block:: python
>>> bag('ac') <= bag('ab')
False
>>> bag('ac') >= bag('ab')
False
>>> bag('a') <= bag('a') < bag('aa')
True
>>> bag('aa') <= bag('a')
False
Compared to existing similar implementations
--------------------------------------------
collections.Counter
^^^^^^^^^^^^^^^^^^^
Counters don't really behave like Collections - Sized, Iterable, Containers
.. testsetup::
>>> from collections import Counter
>>> from collections_extended import bag
Adding and Removing
"""""""""""""""""""
.. code-block:: python
>>> c = Counter()
>>> c['a'] += 1
>>> c['a'] -= 1
>>> 'a' in c
True
>>> b = bag()
>>> b.add('a')
>>> 'a' in b
True
>>> b.remove('a')
>>> 'a' in b
False
``len``
"""""""
.. code-block:: python
>>> c = Counter()
>>> c['a'] += 1
>>> len(c)
1
>>> c['a'] -= 1
>>> len(c)
1
>>> c['a'] += 2
>>> len(c)
1
>>> len(Counter('aaabbc'))
3
>>> b = bag()
>>> b.add('a')
>>> len(b)
1
>>> b.remove('a')
>>> len(b)
0
>>> len(bag('aaabbc'))
6
Iterating
"""""""""
.. code-block:: python
>>> for item in Counter('aaa'): print(item)
a
>>> for item in bag('aaa'): print(item)
a
a
a
Compared to Standard Types
--------------------------
bag vs. list
^^^^^^^^^^^^
* Inclusion testing is O(1)
* Adding and removing elements is O(1)
* Cannot add mutable elements
* Elements aren't ordered
bag vs. set
^^^^^^^^^^^
* Can add multiple instances of equal elements
New Methods
-----------
These are `bag` methods that are not implementing an abstract method from a
standard Python ABC.
``num_unique_elements``
Returns the number of unique elements in the bag. O(1)
``unique_elements()``
Returns a set of all the unique elements in the bag. O(1)
``nlargest(n=None)``
Returns the n most common elements and their counts from most common to
least. If n is None then all elements are returned. O(n log n)
``copy()``
Returns a shallow copy of self. O(self.num_unique_elements())
``isdisjoint(other: Iterable)``
Tests if self is disjoint with any other Iterable. O(len(other))
``issubset(other: Iterable)``
Tests if self is a subset of another Iterable.
``issuperset(other: Iterable)``
Tests if self is a superset of another Iterable.
``from_mapping(map: Mapping)``
Classmethod to create a bag from a Mapping that maps elements to counts.
The following are only for mutable bags (not frozenbags).
- ``pop()``
- ``add(elem)``
- ``discard(elem)``
- ``remove(elem)``
- ``clear()``
API
---
Bag
^^^
.. autoclass:: Bag
bag
^^^
.. autoclass:: bag
frozenbag
^^^^^^^^^
.. autoclass:: frozenbag
Views
^^^^^
.. autoclass:: CountsView
:no-undoc-members:
.. autoclass:: UniqueElementsView
:no-undoc-members:
|
