Ordered Sets

[pataphor]

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.