A mutable set that remembers the order of its entries. One of Python's missing data types.

I have found that:

1. ordered_set.pyi file is not copied to ordered_set package.
2. #26 is not fixed, OrderedSet[str], for example, gives an error.

This PR fixes both.

After the merge, please release. Sorry, I didn't notice for the first time.

I'm the @Gentoo maintainer for core Python packages. We're currently considering options for bootstrapping setuptools while unvendoring its dependencies in the PEP 517 world. One of the interesting options is to use flit as it has much fewer dependencies than setuptools and we've got its bootstrap trivially covered.

Using flit as ordered-set's build system would mean that we can cleanly install it before building setuptools. Flit can also generate a backwards-compatible setup.py (or be used alongside setup.py, though for this to work for us pyproject.toml would have to specify flit_core as the build-backend). FWICS it is becoming increasingly popular these days.

Would you be interested in this? If yes, then I can prepare a PR either converting the project to flit entirely, or adding it alongside existing setup.py, as you prefer.

There is already a type stub file (ordered_set.pyi), but this was not actually being distributed to end-users, so, they had to use the package ordered-set-stubs.

This uses the mechanisms from PEP 561 to ensure that the type stub file is properly distributed so that type hints work out-of-the-box, rather than requiring ordered-set-stubs.

Per PEP 561, this requires two changes to setup.py:

1. Add a sentinel file py.typed and include this in package_data.
2. Use packages rather than py_modules, as the PEP states:

This PEP does not support distributing typing information as part of module-only distributions. The code should be refactored into a package-based distribution and indicate that the package supports typing as described above.

This is a fairly large PR in terms of text, but I think the content is manageable for review.

It seems like this is the best implementation of OrderedSet on PYPI, but unfortunately it is missing functions implemented by the builtin set object like: intersection, symmetric_difference_update, and issubset. This PR adds implementations for these functions.

A brief summary of changes is:

• Implement all functions exposed in Python's builtin set API.
• Replace nose with pytest
• Add TravisCI and corresponding badges in the README
• Change getitem(slice(None)) to return a copy instead of a self reference.

As for reasoning behind these changes:

• I think OrderedSet should serve as a drop-in replacement for set, and therefore should implement the full API.
• I've replaced nose with pytest, because nose is [deprecated]. (http://nose.readthedocs.io/en/latest/index.html).
• TravisCI serves as a public facing CI, so it can see that all tests pass without having to trust text in the README. This also lets the readme publicly display test coverage, and there is a nice pypi integration badge as well.
• The __getitem__ change may be the most debatable. The previous docs stated that OrderedSet()[:] would return an exact self reference, but I want to argue against this behavior. The main point is that this deviates from a standard behavior taken by other Mutable Python objects. Hopefully this code snippet illustrates my point:

>>> x = [1, 2, 3]
>>> x[:] is x
False

>>> x = np.array([1, 2, 3])
>>> x[:] is x
False

>>> # Why should OrderedSet have behavior different than a list here?
>>> x = OrderedSet([1, 2, 3])
>>> x[:] is x
True

A potential counter point may be that tuple([1, 2, 3])[:], does return a reference to itself, but tuple is an immutable object, where as OrderedSet is not.

Unfortunately, even though this change is relatively minor it is a potentially breaking change that requires a major version update. My PR includes that as well. If I fail to convince you that this is a good idea, it can obviously be taken out and the minor version can be incremented.

Note: I'm submitting the PR in its current state to gauge interest. Some of the code --- especially the tests --- needs a bit of tweaking to match the style of the other code. I will do this work if the maintainers like the general changes.

I have my own implementation of OrderedSet, also based on Raymond Hettiger's original recipe, in my utility package but I'd like to rely on a standard pypi package instead. Also, I agree that nobody wants O(1) deletes in exchange for O(N) lookups. Thus most of this PR was simply copy and pasted from my implementation.

All of the new tests were autogenerated from the doctests in my old package. As such, the stdout way of testing results doesn't work and all tests would need to be updated to actually check for the right values. Lastly, many of the tests might be redundant with existing tests. Again, I do the work to make these fixes if there is any interest in merging this PR.

A summary of the cleanup work that would need to be done is:

• [x] change travis targets in the readme to point at LuminosoInsight instead of Erotemic.
• [x] Ensure that all test outputs are being checked
• [x] Either enable doctests in CI testing? or Remove doctests from the main module?

python setuptools attempt to import ordered_set. Therefore it should be possible to build ordered_set with setuptools uninstalled. Perhaps try something like this:

try:
    from setuptools import setup
except ImportError:
    from distutils.core import setup

Hi, I notice that this package isn't PEP 561 compliant, making mypy (v0.782, Python 3.7) unable to detect type annotations even though they exist in the code. A remedy is to put a py.typed file in the package directory, as explained in https://mypy.readthedocs.io/en/stable/installed_packages.html#making-pep-561-compatible-packages. I may be able to make a PR for this, so let me know if you're OK with it.

Since it requires Python >= 3.5 anyway, OrderedSet can be reduced to an adapter of collections.OrderedDict. One can easily use a dict as a set by ignoring the dict's values.

A synthetic benchmark I ran shows that, if CPU caching does not come into play (a big if), an OrderedDict is faster (especially in the case of deletion, which is O(n) ):

Wrote profile results to set_test.py.lprof
Timer unit: 1e-06 s

Total time: 6.21423 s
File: set_test.py
Function: bench at line 13

Line #      Hits         Time  Per Hit   % Time  Line Contents
==============================================================
    13                                           @profile
    14                                           def bench():
    15                                               # Creation
    16         1       5228.0   5228.0      0.1      s = OrderedSet(included)
    17         1      17110.0  17110.0      0.3      d = OrderedDict({i: 1 for i in included})
    18                                           
    19                                               # Insertion
    20      3001       1518.0      0.5      0.0      for i in missing:
    21      3000       5976.0      2.0      0.1          s.add(i)
    22      3001       1518.0      0.5      0.0      for i in missing:
    23      3000       2231.0      0.7      0.0          d[i] = 1
    24                                           
    25                                               # Deletion
    26      3001       2161.0      0.7      0.0      for i in missing:
    27      3000    6159236.0   2053.1     99.1          s.remove(i)
    28      3001       1483.0      0.5      0.0      for i in missing:
    29      3000       2533.0      0.8      0.0          d.pop(i)
    30                                           
    31                                               # Membership test (included)
    32      3001       1492.0      0.5      0.0      for i in included:
    33      3000       2764.0      0.9      0.0          assert i in s
    34      3001       1534.0      0.5      0.0      for i in included:
    35      3000       1786.0      0.6      0.0          assert i in d
    36                                           
    37                                               # Membership test (missing)
    38      3001       1510.0      0.5      0.0      for i in missing:
    39      3000       2836.0      0.9      0.0          assert i not in s
    40      3001       1519.0      0.5      0.0      for i in missing:
    41      3000       1795.0      0.6      0.0          assert i not in d

I am quite convinced there would be performance improvements, if we changed the implementation to use an OrderedDict instead of a set and a list (or a Python 3.6 dict, which is ordered, as @Eric-Arellano suggests).

Edit: However, this would make the access by index (like OrderedSet[1]) much slower (complexity O(n) instead of the current O(1)).

Would you accept a PR doing so?

Equality with set is not commutative:

>>> s = {'x', 'y'}
>>> os = OrderedSet(['x', 'y'])
>>> s == os
False
>>> os == s
True

It will be difficult to fix because this returns False instead of NotImplemented

>>> s.__eq__(os)
False

I'm not sure the best way forward. You can allow OrderedSet.__eq__ to take the precedence if it is a proper set subclass..

This changes equality comparisons completely to make them more consistent with how all the other data structures in Python stdlib behave.

• Comparisons with regular set and frozenset are order agnostic.
• Comparisons with other OrderedSet (and other ordered-set-like-things) are order sensitive.
• Previous equality comparison with list/deque/sequence was removed (this was unpythonic and had no precedent)
• Comparisons with unrelated types return NotImplemented - this is allowing the other type a chance to potentially handle the operation (as opposed to returning False)
• Major version number is bumped up because this is a backwards-incompat change.

The behaviour of equality comparison was modeled after the way collections.OrderedDict behaves (order agnostic vs regular dict, order sensitive vs other ordered dict).

Did this as an exercise to see if it would look cleaner to implement this using collections.OrderedDict.

Use multiple inheritance (Sequence in addition to MutableSet) to get indexing.

This implementation doesn't have to keep track of two different objects self.items and self.map (though maybe collections.OrderedDict might be doing that internally)... either way, the code looks cleaner. Look at the implementation of the abstract methods.

The index method has this feature where you can pass it an iterable. Was able to implement this feature without having to re-implement index... we can just call super() and use the one we get from collections.Sequence

All tests pass without modifying test.py

The inherited bitwise and func (__and__) returns values in reverse order. This PR adds a fix and a test. Removing my change causes test_bitwise_and to fail (because the order of result2 will be incorrect).

The fix simply overrides __and__ to call self.intersection directly.

Hello, I am interested to know if the maintainers of this package would have interest in including this functionality in the python standard library. It seems natural for OrderedSet to sit next to OrderedDict in the collections package. There is a discussion on the Python Discussion Forums. It is not clear-cut that it should be added but I wanted to gauge the interest of the folks maintaining the current Python ordered set implementations.

https://discuss.python.org/t/add-orderedset-to-stdlib/12730/15

Current:

    def update(self, sequence: Union[Sequence[T], Set[T]]) -> int:

Proposed:

    def update(self, sequence: Iterable[T]) -> int:

The reason is that I push in a generator, which works just fine. But the IDE complains because it's neither a Sequence, nor a Set.

>>> from ordered_set import OrderedSet
>>> a = OrderedSet(["a", "b", "c"])
>>> a.index("b")
1
>>> a.pop(0)
'a'
>>> a.index("b")
1
>>> a[1]
'c'

This was revealed by looking into #79. pop() would need to rebuild the mapping in place, like discard() does. Its current behavior, which only works for index=-1, would be an optimization.

Since OrderedSet supports indexing, it's natural to assume that assignments and del would work as well, but they don't:

>>> s = OrderedSet(['foo'])
>>> s[0]
'foo'
>>> s[0] = 'bar'
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'OrderedSet' object does not support item assignment
>>> del s[0]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'OrderedSet' object doesn't support item deletion

There's an easy workaround for del (s.remove(s[0])), but not for item assignments. As far as I can tell, there is no way to reorder items at all, so it's impossible to replace an element with another one (while preserving its index).