Ordered Sets

pataphor pataphor at gmail.com
Mon Mar 30 18:27:11 CEST 2009

```On Mon, 30 Mar 2009 03:30:04 -0500
Nick Craig-Wood <nick at craig-wood.com> wrote:

> >>> class Node(object):
> ...     __slots__ = ["prev", "next", "this"]
> ...     def __init__(self, prev, next, this):
> ...         self.prev = prev
> ...         self.next = next
> ...         self.this = this

[...]

> So the Node class actually takes less memory 38 Mbytes vs 53 Mbytes
> for the list.

Well OK, but if we're going to start optimizing, it seems we don't need
to store the key itself in the Node or the list. Here's a version of my
script that stores only prev and next. Another twist is that it is now
possible to arbitrarily set the starting point for the iteration. (Just
in case someone needed a cue for further ranting)

P.

import collections

class OrderedSet(collections.MutableSet):
'Set that remembers the order elements were added'
# Big-O running times for all methods are the same as for regular
sets.
def __init__(self, iterable=None):
self.links = {}                     # key --> [prev,next]
if iterable is not None:
self |= iterable

def __len__(self):

def __contains__(self, key):

if not self:
self.start = key
start = self.start

if key  == self.start:
self.start = next
else:
del self.start

def __iter__(self):
start = self.start
yield start
while next != start:
yield next

def __reversed__(self):
start = self.start
while prev != start:
yield prev
yield start

def pop(self, last=True):
if not self:
raise KeyError('set is empty')
key = next(reversed(self)) if last else next(iter(self))
return key

def __repr__(self):
if not self:
return '%s()' % (self.__class__.__name__,)
return '%s(%r)' % (self.__class__.__name__, list(self))

def __eq__(self, other):
if isinstance(other, OrderedSet):
return len(self) == len(other) and list(self) == list(other)
return not self.isdisjoint(other)

def test():
D = OrderedSet('abcd')
R = OrderedSet()
for x in list(D):
print(D,R)