# Ordered Sets

pataphor pataphor at gmail.com
Tue Mar 31 11:52:45 CEST 2009

```On Tue, 31 Mar 2009 10:33:26 +0200
pataphor <pataphor at gmail.com> wrote:

> On Mon, 30 Mar 2009 19:57:39 -0700 (PDT)
> Alex_Gaynor <alex.gaynor at gmail.com> wrote:
>
> > I really like the Ordered Set class(I've been thinking about one
> > ever since ordered dict hit the std lib), is there any argument
> > against adding one to the collections module?  I'd be willing to
> > write a PEP up for it.
>
> Suppose the implementation would use a circular linked list. Then the
> iteration could start from any point, the thing is symmetric after
> all. But this would also mean we could add items to the left of that
> new starting point, since that would now be the 'end' of the circle.
> This is something different from merely remembering insertion order.
> How do you feel about that?

And in case that didn't confuse you enough, how about this method?

def move(self,key1,key2):
#self ==> key1,(key2 ... end), (key1+1... key2-1)
links = self.links
if set([key1,key2]) and self :
start = self.start
a = links[key1][1]
b = links[key2][0]
c  = links[start][0]
links[key1][1] = key2
links[key2][0] = key1
links[a][0] = c
links[c][1] = a
links[b][1] = start
links[start][0] = b

This takes [key2:]  (isn't pseudo slice notation wonderful?) and
inserts it after key1.

for example:

R = OrderedSet(range(10))
print(list(R))
R.move(3,7)
print(list(R))

gives:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 7, 8, 9, 4, 5, 6]

All in O(1) of course.

P.

```

More information about the Python-list mailing list