Example documentation

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.

Skip Lists

A skip-list is a data type equivalent to a balanced (binary) tree.

skip-list Library

The skip list library may be found in the “skip-list” repository.

skip-list Module

The skip-list module exports a number of symbols. Two new symbols are of interest:

• <skip-list>

• element-sequence

The skip-list module also adds to several generic methods. One of the new methods is:

• element

<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., <.

Superclasses:

<stretchy-collection>, <mutable-explicit-key-collection>

Init-Keywords:

• key-test – The collection’s key-test function; should return #t if two keys should be considered equal. Defaults to ==.

• key-order – A function that accepts two keys and returns #t if 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 size and capacity keywords.

• level – The list starts with this number of levels. Defaults to a value based on the size and capacity keywords.

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 forward-by-key-iteration-protocol, element-sequence, and element-sequence-setter.

element-sequence Generic function

Parameters:

• list – A skip list.

Values:

• sequence – An instance of <sequence>.

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 and 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 element.

Parameters:

• collection – An instance of <skip-list>.

• key – The key of an element. An instance of <object>.

• default (#key) – A value to return if the element is not found. If omitted and element not found, signals an error.

Values:

• object – The element associated with the key.