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
|
Metadata-Version: 2.1
Name: ordered-set
Version: 3.1.1
Summary: A MutableSet that remembers its order, so that every entry has an index.
Home-page: https://github.com/LuminosoInsight/ordered-set
Maintainer: Robyn Speer
Maintainer-email: rspeer@luminoso.com
License: MIT-LICENSE
Platform: any
Classifier: Development Status :: 5 - Production/Stable
Classifier: Intended Audience :: Developers
Classifier: License :: OSI Approved :: MIT License
Classifier: Programming Language :: Python
Classifier: Programming Language :: Python :: 2
Classifier: Programming Language :: Python :: 2.7
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.4
Classifier: Programming Language :: Python :: 3.5
Classifier: Programming Language :: Python :: 3.6
Classifier: Programming Language :: Python :: 3.7
Classifier: Programming Language :: Python :: Implementation :: CPython
Classifier: Programming Language :: Python :: Implementation :: PyPy
Requires-Python: >=2.7
Description-Content-Type: text/markdown
License-File: MIT-LICENSE
[](https://travis-ci.org/LuminosoInsight/ordered-set)
[](https://codecov.io/github/LuminosoInsight/ordered-set?branch=master)
[](https://pypi.python.org/pypi/ordered-set)
An OrderedSet is a mutable data structure that is a hybrid of a list and a set.
It remembers the order of its entries, and every entry has an index number that
can be looked up.
## Usage examples
An OrderedSet is created and used like a set:
>>> from ordered_set import OrderedSet
>>> letters = OrderedSet('abracadabra')
>>> letters
OrderedSet(['a', 'b', 'r', 'c', 'd'])
>>> 'r' in letters
True
It is efficient to find the index of an entry in an OrderedSet, or find an
entry by its index. To help with this use case, the `.add()` method returns
the index of the added item, whether it was already in the set or not.
>>> letters.index('r')
2
>>> letters[2]
'r'
>>> letters.add('r')
2
>>> letters.add('x')
5
OrderedSets implement the union (`|`), intersection (`&`), and difference (`-`)
operators like sets do.
>>> letters |= OrderedSet('shazam')
>>> letters
OrderedSet(['a', 'b', 'r', 'c', 'd', 'x', 's', 'h', 'z', 'm'])
>>> letters & set('aeiou')
OrderedSet(['a'])
>>> letters -= 'abcd'
>>> letters
OrderedSet(['r', 'x', 's', 'h', 'z', 'm'])
The `__getitem__()` and `index()` methods have been extended to accept any
iterable except a string, returning a list, to perform NumPy-like "fancy
indexing".
>>> letters = OrderedSet('abracadabra')
>>> letters[[0, 2, 3]]
['a', 'r', 'c']
>>> letters.index(['a', 'r', 'c'])
[0, 2, 3]
OrderedSet implements `__getstate__` and `__setstate__` so it can be pickled,
and implements the abstract base classes `collections.MutableSet` and
`collections.Sequence`.
## Interoperability with NumPy and Pandas
An OrderedSet can be used as a bi-directional mapping between a sparse
vocabulary and dense index numbers. As of version 3.1, it accepts NumPy arrays
of index numbers as well as lists.
This combination of features makes OrderedSet a simple implementation of many
of the things that `pandas.Index` is used for, and many of its operations are
faster than the equivalent pandas operations.
For further compatibility with pandas.Index, `get_loc` (the pandas method for
looking up a single index) and `get_indexer` (the pandas method for fancy
indexing in reverse) are both aliases for `index` (which handles both cases
in OrderedSet).
## Type hinting
To use type hinting features install `ordered-set-stubs` package from
[PyPI](https://pypi.org/project/ordered-set-stubs/):
$ pip install ordered-set-stubs
## Authors
OrderedSet was implemented by Robyn Speer. Jon Crall contributed changes and
tests to make it fit the Python set API.
## Comparisons
The original implementation of OrderedSet was a [recipe posted to ActiveState
Recipes][recipe] by Raymond Hettiger, released under the MIT license.
[recipe]: https://code.activestate.com/recipes/576694-orderedset/
Hettiger's implementation kept its content in a doubly-linked list referenced by a
dict. As a result, looking up an item by its index was an O(N) operation, while
deletion was O(1).
This version makes different trade-offs for the sake of efficient lookups. Its
content is a standard Python list instead of a doubly-linked list. This
provides O(1) lookups by index at the expense of O(N) deletion, as well as
slightly faster iteration.
In Python 3.6 and later, the built-in `dict` type is inherently ordered. If you
ignore the dictionary values, that also gives you a simple ordered set, with
fast O(1) insertion, deletion, iteration and membership testing. However, `dict`
does not provide the list-like random access features of OrderedSet. You
would have to convert it to a list in O(N) to look up the index of an entry or
look up an entry by its index.
## Compatibility
OrderedSet is automatically tested on Python 2.7, 3.4, 3.5, 3.6, and 3.7.
We've checked more informally that it works on PyPy and PyPy3.
|
