I've updated my library of Python algorithm implementations to include another module: SortedSet. It maintains a set of items (like a Python set data type), but adds a method to report all the items in the set in sorted order.

The obvious ways of doing this are to sort everything at reporting time or to maintain the items in a balanced binary tree data structure. My solution combines the simplicity of the first solution with the asymptotic speed of the second: store, along with the set itself, the sorted output from the last report and smaller lists of changed items. A new report request can be handled by sorting the smaller lists and merging them with the previous output, in constant time for each previously listed item and logarithmic time for each changed item.


Quite nice, I often need a sorted set/map in Python. I'll try the performance of your code. I already use some of your modules. If you don't mind few notes:
self._removals = set()
self._additions = set()
This may be more friendly for the GC:

def __init__(self,comparison=None):
Better to put a space after the commas (as PEP8 too says):
def __init__(self, comparison=None):
Generally in Python it's better to put/define all the attributes used by a class inside the __init__, for documentation purposes too (untested, may be wrong for this program):
def __init__(self, comparison=None):
    """Create a new sorted set with the given comparison function."""
    self._comparison = comparison
    self._set = set()
    self._previous = None
    self._removals = set()
    self._additions = set()
Hi, Your library looks interesting, but I keep getting gateway timed out errors on trying to download it. Is there a mirror anywhere? I'll try again later. Cheers, Jin
I'm not getting a response from the server right now, either, and I don't know of any mirrors. I have a copy on my laptop, so if you're in a hurry you could give me an email address and I could send it that way, but it's likely that everything would be back up by the time we work that out.