Here is an example of documentation to get a feel for how it works. Use the “View page source” link at the top of the page to see it in RST markup form.
A skip-list is a data type equivalent to a balanced (binary) tree.
- skip-list Module#
The skip-list module exports a number of symbols. Two new symbols are of interest:
The skip-list module also adds to several generic methods. One of the new methods is:
- <skip-list> Open Primary Class#
A skip-list is a data type equivalent to a balanced (binary) tree. All keys must be comparable by some kind of ordering function, e.g.,
key-test – The collection’s key-test function; should return
#tif two keys should be considered equal. Defaults to
key-order – A function that accepts two keys and returns
#tif the first key sorts before the second. Defaults to
size – Preallocates enough memory to hold this number of objects. Optional.
capacity – Sets the maximum capacity of the skip list. Optional.
probability – The probability to create a new level of the list. Equivalent to the fan-out of a tree. Defaults to 0.25.
max-level – The list will not grow beyond this number of levels. Defaults to a value based on the
level – The list starts with this number of levels. Defaults to a value based on the
In general, a skip list operates like a stretchy mutable key collection. But a skip list can also act as an ordered stretchy mutable key collection where the iteration order is the key order. To take advantage of this, the library defines
- element-sequence Generic function#
list – A skip list.
sequence – An instance of
One of the useful features of skip lists is that they can be ordered. However, most of the useful operations that can be performed on ordered collections, such as sort, are only defined for sequences. To solve this problem, I add
element-sequence-setter. The client may call the former to obtain a sequence, operate on it, and call the latter to fix the results in the skip list. The setter ensures that no elements have been added or removed from the skip list, only reordered.
- element(<skip-list>) Method#
A specialization of