Skip to content

Instantly share code, notes, and snippets.

@nathansobo
Created August 23, 2013 20:31
Show Gist options
  • Save nathansobo/6323684 to your computer and use it in GitHub Desktop.
Save nathansobo/6323684 to your computer and use it in GitHub Desktop.
Non-trivial documentation on a skip list helper method.
# Private: searches the skiplist in a stairstep descent, following the highest
# path that doesn't overshoot the index.
#
# * next
# An array that will be populated with the last node visited at every level
#
# Returns the leftmost node whose index is >= the given index
findClosestNode: (index, next) ->
currentNode = @head
for i in [@currentLevel..0]
# move forward as far as possible while keeping the currentNode's index less
# than the index being inserted
while currentNode.next[i].index < index
currentNode = currentNode.next[i]
# when the next node's index would be bigger than the index being inserted,
# record the last node visited at the current level and drop to the next level
next[i] = currentNode
currentNode.next[0]
@mcolyer
Copy link

mcolyer commented Aug 23, 2013

In general I like it. A few things points I'd change:

I think the first letter should be capitalized, so searches becomes Searches.

I think next should have a colon trailing it, as the markdown gets folded onto one line which makes it a bit harder to read without it.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment