Hi all, About the new OrderedDict and how to support `move_to_end(last=False)` in the py3k branch: an implementation of the correct complexity is possible. It would piggy-back on the part of `lookup_function_no` that acts as counter for how many entries at the start are known to be deleted. This number is present to allow for a good implementation of `popitem(last=False)`, so that it doesn't have to scan a larger and larger area of deleted items.
So you can use the same number in reverse. As long as this number is greater than zero, you can insert the new item at position "this number minus one". When it is zero, you resize and reindex the dictionary by adding an extra argument to the relevant functions which would force it to artificially reserve n free entries at the start. If n is proportional to "num_live_items", maybe 1/8 or 1/16 of it, it should be enough to give amortized constant time to the operation. A bientôt, Armin. _______________________________________________ pypy-dev mailing list pypy-dev@python.org https://mail.python.org/mailman/listinfo/pypy-dev
