[Design] Interface of SkipList

[rapiz1]

SkipList / SkipListMap

Red-Black Tree alternative.

I'm also proposing a kind of Map built on SkipList.

Used in many popular projects like LevelDB, Reddis, Bigtable

vs Red-Black Tree

SkipList	Red-Black Tree
Larger constant factor, but fast in practice
Easy to implement	Very difficut to implement
Could be lock-free	Need a lock
With expected time complexity, not stable	With upper bound complexity

And Skip List will on expectation use less space than all balanced trees.

In practice, it's fairly fast

So between Skip List and Treap, it's a time-space trade off ( though SkipList sometimes is actually faster )

Interface

• eltType
• record comparator
• size
• insert(x: eltType): insert an element.
• contains(x: eltType): bool: return if x is in the list
• lower_bound(x: eltType, out result: eltType): bool same as std::lower_bound(), return false if no occurence.
• upper_bound(x: eltType, out result: eltType): bool same as std::upper_bound(), return false if no occurence.
• remove(x: eltType): bool: remove x in the list. Does nothing if not present
• these(): iterate over the list
• kth(idx: int): return k-th element in the sorted sequence, throw an error if out of range
• toArray: convert to an array
• clear()
• predecessor(x: eltType, out result: eltType): bool return the predecessor of one element, return false if it's the first one.
• successor(x: eltType, out result: eltType): bool return the successor of one element, return false if it's the last one.

SkipListMap same as Map but with SkipList as the underlying structure

[rapiz1]

One question: How can lower_bound and upper_bound return nullable value? This is also a problem for SearchTree. We can only apply ? to class, but many times users would use these structures that support quick search with integers. In that case, when users search the structure but with no occurrence, we couldn't return a nil value. One solution could be that passing a reference to the procedure and store the result in that if there's an occurrence. Meanwhile, the procedure returns bool to indicate whether there is indeed an occurrence.

[e-kayrakli]

Issues somewhat related to your questions:

https://github.com/chapel-lang/chapel/issues/15394 https://github.com/chapel-lang/chapel/issues/14423

[cassella]

Why are lower_bound() and upper_bound() here?

[rapiz1]

Why are lower_bound() and upper_bound() here?

SkipList has all the functionality of a search tree. Or think it as a sorted array. lower_bound and upper_bound are useful for searching elements closest to the target.

[rapiz1]

Closed by https://github.com/chapel-lang/chapel/issues/15921