11.10 Skip Lists

Like association lists or property lists, a skip list is another dictionary data type. That is skip lists can be used to represent a finite key-value mapping. See See Association Lists, and See Property Lists.

However, alists and plists are very inefficient at almost any operation for large key spaces. For instance, looking up the value of a given key is accomplished by linear probing. This implies that searching for a key not in the key space is a worst case, the list has to be traversed in its entirety as it contains no superior structure or indicators which help to identify keys not belonging to the key space.

On the other hand, given an alist or plist this lack of structure induces a class of equivalent alists or plists with respect to the storage representation. This would make it possible to add new elements in constant time by just prepending them to the front of the list.

Anyway, without manual intervention SXEmacs’ association and property lists cannot add elements in constant time. Instead they try to avoid duplicate keys and thence crawl the entire list to make sure the key to be added is not already there.

Function: make-skiplist

Return a new empty skiplist object.

Function: skiplistp object

Return non-nil if object is a skiplist, nil otherwise.

Function: skiplist-empty-p skiplist

Return non-nil if skiplist is empty, nil otherwise.

Function: put-skiplist skiplist key value

Add key to the skiplist and assign value. Hereby, the skiplist object is modified by side-effect.

Function: get-skiplist skiplist key &optional default

Return the value of key in skiplist. If key is not an element, return nil instead or – if specified – default.

Function: remove-skiplist skiplist key

Remove the element specified by key from skiplist. If key is not an element, this is a no-op.

Function: skiplist-owns-p skiplist key

Return non-nil if key is associated with a value in skiplist, nil otherwise.

Function: skiplist-size skiplist

Return the size of skiplist, that is the number of elements.

Function: copy-skiplist skiplist

Return a copy of skiplist skiplist. The elements of skiplist are not copied; they are shared with the original.

Function: skiplist-to-alist skiplist

Return the ordinary association list induced by skiplist.

Function: skiplist-to-plist skiplist

Return the ordinary property list induced by skiplist.

Function: alist-to-skiplist alist

Return a skiplist from alist with equal key space and image.

Function: plist-to-skiplist plist

Return a skiplist from plist with equal key space and image.

Function: skiplist-union &rest skiplists

Return the union skiplist of skiplists, that is a skiplist containing all key-value-pairs which are in at least one skiplist of skiplists.

Note: Key-value-pairs with equal keys and distinct values are processed from left to right, that is the final union for such pairs contains the value of the rightmost skiplist in skiplists.

Function: skiplist-intersection &rest skiplists

Return the intersection skiplist of skiplists, that is a skiplist containing all key-value-pairs which are in all skiplists of skiplists.

Note: Key-value-pairs with equal keys and distinct values are processed from right to left, that is the final intersection for such pairs contains the value of the leftmost skiplist in skiplists.

Function: map-skiplist function skiplist

Map function over entries in skiplist, calling it with two args, each key and value in skiplist.

function may not modify skiplist, with the one exception that function may remove or reput the entry currently being processed by function.