A simple proof-of-concept for comment partial ordering

ordering.py

# Let us control the passage of time (magic!)
wall_time = 0

class Comment(object):
    # Used for quick and dirty unique IDs.
    # In a real system, the IDs probably wouldn't be
    # this simple, but it doesn't matter what they are
    # as long as they're unique.
    _instance_counter = 0

    def __init__(self, parent=None, reply=None):
        self.id = self._instance_counter
        Comment._instance_counter += 1

        # You can see that this works with non-counter IDs
        # as well by uncommenting these two lines:

        #import random
        #self.id = hash(random.random())

        self.timestamp = wall_time
        self.parent = parent

        # This field isn't actually used in the ordering algorithm
        # at all - it's just so that we can check the results later
        self.reply = reply

    def __str__(self):
        val = "#%d (t=%d)" % (self.id, self.timestamp)
        if self.reply:
            val += " - reply to #%d" % (self.parent.id if self.parent else 0)
        return val

    def __hash__(self):
        return self.id

#############################################
# Reordering algorithm
#############################################

def reorder(comments):
    """Create an ordered list of comments based on parents and timestamps."""
    comments = set(comments)
    # First, grab all of the comments without a parent, ordered by time.
    added_comments = set(c for c in comments if c.parent is None)
    comments -= added_comments
    result = sorted(added_comments, key=lambda c: c.timestamp)

    # Now, continue grabbing comments whose parents are already present and inserting them
    while comments:
        comments_to_add = set(c for c in comments if c.parent in added_comments)
        comments -= comments_to_add
        for comment in comments_to_add:
            result.insert(get_insertion_point(result, comment), comment)
            added_comments.add(comment)

    return result
            

def get_insertion_point(existing_comments, new_comment):
    """Find the proper position in a list of existing comments to insert a new comment while reordering."""
    after_parent = False
    for index, comment in enumerate(existing_comments):
        # Skip all of the spots before the parent
        if not after_parent:
            if comment != new_comment.parent:
                continue
            else:
                after_parent = True
                continue

        # Once we're past the parent, skip all of the spots with an earlier timestamp
        if comment.timestamp <= new_comment.timestamp:
            continue

        return index

    # If we didn't find an index to insert before, insert at the end
    return len(existing_comments)

#############################################
# Helper methods for simulation
#############################################

def add_comment(client, server, reply=None):
    """Simulate the client posting a new client to the server."""
    parent = client[-1] if client else None
    comment = Comment(parent, reply)

    # The server receives the comment
    server.append(comment)

    # The client also updates locally with the posted comment
    client.append(comment)

    return comment

def refresh_client(client, server):
    """Simulate the client reloading the comment list from the server (F5, etc)."""
    client[:] = reorder(server)

#############################################
# The simulation
#############################################

def main():
    global wall_time

    # The server starts out with no comments.
    server = []

    # Both clients load the page before any comments are added.
    client_a = []
    client_b = []

    # Client A posts a comment
    add_comment(client_a, server)

    wall_time = 2 # Time moves on (you'll see this a lot)

    # Client B posts a comment
    first_b_comment = add_comment(client_b, server)

    wall_time = 4

    # Client A refreshes, and posts a reply to B's comment
    refresh_client(client_a, server)
    add_comment(client_a, server, reply=first_b_comment)

    wall_time = 6

    # Client B refreshes, and posts a new comment
    refresh_client(client_b, server)
    second_b_comment = add_comment(client_b, server)

    # Pretend client A's clock is running slow...
    wall_time = 5
    # and have client A refresh and post a reply to B's comment
    refresh_client(client_a, server)
    add_comment(client_a, server, reply=second_b_comment)

    # Client B posts one more unrelated comment later on
    wall_time = 8
    add_comment(client_b, server)

    # As does Client A, much later on
    wall_time = 16
    add_comment(client_a, server)

    # Finally, display what client B sees if they refresh the page:
    refresh_client(client_b, server)
    print '\n'.join(str(c) for c in client_b)


if __name__ == "__main__":
    main()

# vim: set et ts=4 sts=4 sw=4: