Created
August 23, 2013 20:31
-
-
Save nathansobo/6323684 to your computer and use it in GitHub Desktop.
Non-trivial documentation on a skip list helper method.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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] |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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.