Python: Creating a Set with Xor-like behavior

Question

I have a use-case for an efficient implementation of a Set with XOR-like behaviour.

A set that, if an element is added, removes the element from the set if it is already contained in the set, but adds it in case it is not. See the below code:

# Create set `a`
a = xorset((0,0,0,1,1,2))
assert a == {0,2}
a.add(0)
assert a == {2}
a.add(0)
assert a == {0,2}

a.update((0,0))
assert a == {0,2}
a.update((0,0,0,2,1))
assert a == {1}

My best attempt so far has been to use the collections Counter object to create sets like so:

from collections import Counter
def xorset(it):
    return set(k for k,v in Counter(it) if v % 2 == 1)

and then to manually implement the add & update operations:

import itertools
def xorset_add(s,e):
    if e in s:
         s.remove(e)
    else:
         s.add(e)
    return s # not necessary as works in place
def xorset_update(s,it):
    return set(k for k,v in Counter(itertools.chain(s,it)) if v % 2 == 1)

I would imagine there'd be significant speed-ups possible if there was a lib that handled the addition/removal of new elements, but I have not been able to find any. Does anyone know of the existence of one?

Thanks!

Answer 1

Unless I've misunderstood you, it sounds like the set method symmetric_difference_update does what you're looking for, and as it's a built-in, it's about as fast as you're going to get.

>>> s = set((1,2,3))
>>> s
{1, 2, 3}
>>> s.symmetric_difference_update(set((2,)))         ["add" 2, but removes 2]
>>> s
{1, 3}
>>> s.symmetric_difference_update(set((2,)))         ["add" 2 back]
>>> s
{1, 2, 3}
>>> s.symmetric_difference_update(set((3,4)))        ["add" 3 and 4, but removes 3]
>>> s
{1, 4}

You can perform the same operation with the ^= operator:

>>> s
{1, 4}
>>> s ^= set((4,))
>>> s
{1}
>>> s ^= set((4,))
>>> s
{1, 4}

Update: implementation of xorset class provided by @Erwin Haasnoot

A full immutable xorset implementation, subclassing frozenset, will look like below:

import itertools
from collections import Counter

class xorset(frozenset):
    def __new__(cls, it=()):
        it = (k for k, v in Counter(it).items() if v & 1)
        return super().__new__(cls, it)

    def add(self, v):
        return self ^ {v}

    def update(self, it):
        return self.__class__(itertools.chain(self, it))```