Skip to content

Instantly share code, notes, and snippets.

@ayust
Created July 7, 2012 04:22
Show Gist options
  • Save ayust/3064595 to your computer and use it in GitHub Desktop.
Save ayust/3064595 to your computer and use it in GitHub Desktop.
A simple proof-of-concept for comment partial ordering
# 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:
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment