ordered-set

ordered-set provides OrderedSet, a Python data structure that behaves like a set but remembers the order items were inserted in and lets you look them up by index. It’s a hybrid of Python’s list and set built-in types: elements are kept in a list for ordering and indexed access, while a parallel dict gives O(1) membership testing, so it avoids the tradeoffs of using either type alone.

Beyond basic set algebra (union, intersection, difference, symmetric_difference, with both copying and in-place variants), OrderedSet supports NumPy-style fancy indexing, pickling, and pandas.Index-compatible aliases (get_loc, get_indexer), making it a natural fit for data-science code that needs a lightweight, dependency-free ordered vocabulary or ID mapping.

What You Get

• Drop-in set replacement: OrderedSet subclasses collections.abc.MutableSet and Sequence, so it works anywhere a set or sequence is expected.
• Index-aware operations: .add() and .append() return the index of the inserted item; .index() looks up positions, including “fancy indexing” with lists or arrays.
• Full set algebra: union, intersection, difference, and symmetric_difference, plus their in-place *_update variants and the |, &, - operators.
• Pandas-style aliases: get_loc and get_indexer mirror pandas.Index methods for interop with data-science code.
• Pickling support via custom getstate/setstate, including the empty-set edge case.

Common Use Cases

• Deduplicating a list while preserving the order items first appeared in.
• Building a bidirectional vocabulary-to-index mapping (word to integer id) for NLP or ML pipelines.
• Maintaining an ordered collection of unique event or task IDs where membership tests are frequent.
• Replacing the dict.fromkeys(x) ordered-set-as-a-dict idiom with an explicit, purpose-built type.

Under The Hood

Architecture ordered-set is a single-class library: OrderedSet in ordered_set/init.py subclasses both collections.abc.MutableSet and collections.abc.Sequence, giving it dual set-and-list semantics from Python’s own ABC machinery rather than a bespoke interface. Internally it keeps two parallel structures — a self.items list for order and index-based access, and a self.map dict from element to its position — so membership tests and index lookups are both O(1) while insertion order is preserved by the list. Mutating operations like discard() and difference_update() have to rebuild or shift the map’s index values (an internal _update_items() helper recomputes self.map from a fresh items list), which is the deliberate tradeoff the README explains versus the original linked-list-based recipe it descends from: this design favors fast indexed access over fast arbitrary deletion. There are no other modules, classes, or layers — the entire abstraction lives in one class, so the core invariant every mutating method has to preserve is simply that items and map stay in sync.

Tech Stack The library is pure Python with zero runtime dependencies, targeting Python 3.7+ and typed throughout with the typing module (overloaded getitem and index signatures, a generic TypeVar T). It’s packaged with flit (pyproject.toml, build-backend flit_core.buildapi) rather than setuptools, which is why it ships as a wheel-only, single-module distribution without setup.py doing real work (the setup.py present is a thin compatibility shim). Development dependencies are pytest, black, and mypy, declared as an optional dev extra. Tests are run via tox across pypy3 and CPython 3.7-3.10, with coverage tracked through .coveragerc and a Codecov configuration.

Code Quality Testing is substantial for the library’s size: a 387-line test/test_ordered_set.py exercises pickling, ordering, set algebra, indexing (including NumPy fancy-indexing and pandas-interop edge cases), and in-place update methods, and pytest.ini additionally configures every docstring example to run as a doctest across both the module and README.md — meaning the README’s usage examples are executable tests, not just prose. flake8 enforces a 100-character line limit, and the codebase is fully type-annotated for mypy. No .github/workflows configuration exists in the repository, so CI enforcement beyond local tox/pytest runs and the Codecov integration isn’t verifiable from the repo alone.

API Design The public API deliberately mirrors Python’s built-in set and list so it requires almost no learning curve: OrderedSet(iterable) constructs like set(), and it supports the same |, &, -, in, len(), and iteration idioms. Where it goes further, it does so with unusually convenient return values: .add() returns the inserted item’s index instead of None, letting a single call build a vocabulary and its index simultaneously. get_loc and get_indexer are deliberate aliases of index(), added purely for drop-in compatibility with pandas.Index consumers — real attention to a specific integration use case rather than a generic feature. The tradeoff is stated plainly rather than hidden: deletion (discard, pop) is O(N) because the position map has to be recomputed.