alex.gaynor at gmail.com
Tue Mar 31 15:03:13 CEST 2009
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]
> b = links[key2]
> c = links[start]
> links[key1] = key2
> links[key2] = key1
> links[a] = c
> links[c] = a
> links[b] = start
> links[start] = b
> This takes [key2:] (isn't pseudo slice notation wonderful?) and
> inserts it after key1.
> for example:
> R = OrderedSet(range(10))
> [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.
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.
More information about the Python-list