Ordered Sets

[Alex_Gaynor]

On Mar 31, 5:52 am, pataphor <patap... at gmail.com> wrote:
> On Tue, 31 Mar 2009 10:33:26 +0200
>
> pataphor <patap... at gmail.com> wrote:
> > On Mon, 30 Mar 2009 19:57:39 -0700 (PDT)
> > Alex_Gaynor <alex.gay... 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.

My inclination would be to more or less *just* have it implement the
set API, the way ordered dict does in 2.7/3.1.

Alex