eset

Extended sets - support for set complement

Overview

An eset works like a normal python set except that you can invert it to generate its complement. For example, let's say you have the following:

>>> from esets import oset
>>> s = oset(['hello', 'there'])
>>> s_invert = ~s
>>> s_invert
~oset(['hello', 'there'])

In this example, s_invert contains everything except 'hello' and 'there'.

Logic

All the logic operations you'd expect from sets are available in esets, including intersection, union, difference, and symmetric difference. Use the &, |, -, and ^ operators respectively.

Similarly, conditional expressions are available to determine subset relationships. If A <= B, that A is a subset of B.

The named forms of these operations are there too -- union, intersection, difference, symmetric_difference, isdisjoint, issubset, issuperset -- along with their in-place counterparts (update, intersection_update, difference_update, symmetric_difference_update) and the usual add, discard, remove, pop, clear and copy. As with the builtin set, the operators accept only sets, dicts and esets, while the named methods raise TypeError on anything else.

Membership is what mutates

Mutation is defined in terms of membership, not storage, so it reads the same either side of an inversion: after s.add(x), x in s is always true, and after s.discard(x) it is always false -- even when s is a complement, where the item is dropped from (or added to) the excluded items to make that hold.

>>> s = ~oset(['hello'])
>>> s.add('hello')
~oset()
>>> 'hello' in s
True

Iteration and length

A complement eset has infinitely many members, so it can neither be iterated nor measured with len(); both raise TypeError. Invert it to walk the finite set of items it excludes, and use abs() for its cardinality.

>>> list(~~oset(['hello', 'there']))
['hello', 'there']

Ordered and unordered

eset is the type; oset and uset build the two kinds. An oset keeps insertion order and is backed by a dict; a uset doesn't and is backed by a set, which lets the C set operations do the work.

>>> from esets import oset, uset
>>> uset(['hello', 'there']).ordered
False

Pick uset for intersection-heavy work. At 100k elements it's ~2.2x faster, and where the operands are lopsided the gap is enormous -- oset must scan its left operand to order the result, while set.__and__ walks the shorter side:

	oset	uset
A & B, 100k & 10	1.39ms	668ns
A & B, 100k each	1.95ms	886us
construction, 100k	1.34ms	669us
A | B, 100k | 10	222us	306us

Unions are the other way round, so oset is not simply the slower choice -- cloning a dict beats rebuilding a set.

Mixing the two is allowed. A result keeps the mode of its left operand whenever any of that operand's stored items survive into it; when none do, the right operand's mode governs, because there's nothing on the left to take an order from. That is just what A op= B has to do -- an in-place update can't change A's kind.

>>> (oset(['a', 'b']) & uset(['b'])).ordered      # A supplies the result
True
>>> (~oset(['a']) & uset(['a', 'b'])).ordered     # B \ A -- only B supplies
False

oset(x) and uset(x) also convert, preserving complement and frozen state.

Frozen esets

frozen() returns an immutable eset, which -- unlike a plain one -- is hashable and so can be a dict key or live inside another set. A frozen eset hashes the same as the frozenset it compares equal to.

>>> from esets import frozen
>>> frozen(['hello']) in {frozen(['hello'])}
True

Anything that would mutate one -- add, discard, clear, update and the other *_update methods -- raises TypeError. The augmented operators are the exception, and behave as they do for frozenset: f &= x never mutated anything to begin with, it rebound the name, so it yields a new frozen eset and leaves the original alone.

>>> f = frozen(['hello', 'there'])
>>> f &= {'hello'}
>>> f
frozen(oset(['hello']))

Use freeze() and thaw() to flip an existing eset between the two states.

Frozen means the container is never mutated in place, which lets it be shared rather than copied -- so ~f and f.copy() are constant time however large f is (149ns at 100k, against 220us unfrozen). thaw() rebinds to a fresh container rather than mutating the old one, so anything still sharing it is unaffected. For a uset the frozen container is an actual frozenset, so the immutability is enforced by the container rather than by convention.

Infinities

You'll note there's an inf.py module that implement א0 and א1 infinities, that is, countable and uncountable infinities. This was implemented so that cardinality calculations would be correct for complement sets: discussed below.

>>> from esets import inf
>>> inf.countable, inf.uncountable
(א0, א1)
>>> inf.countable < inf.uncountable
True

Indeterminate forms such as א0 - א0 yield inf.nan, which propagates through any further arithmetic and compares False against everything ordered -- but, unlike float('nan'), equals itself so results can be checked against it.

>>> inf.countable - inf.countable
nan
>>> inf.countable - inf.countable == inf.nan
True

Cardinality

The abs expression (also cardinality method) will return a countably infinite scalar if in complement mode; otherwise it returns the count of items in set.

>>> from esets import oset, inf
>>> s = oset(['hello', 'there'])
>>> abs(s)
2
>>> abs(~s)
א0