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