Skip List in Golang

Skip list is an ordered map. See wikipedia page skip list to learn algorithm details about this data structure.

Highlights in this implementation:

- Built-in types can be used as key with predefined key types. See Int and related constants as a sample.
- Support custom comparable function so that any type can be used as key.
- Key sort order can be changed quite easily. See Reverse and LessThanFunc.
- Rand source and max level can be changed per list. It can be useful in performance critical scenarios.

Install

Install this package through `go get`

.

` go get github.com/huandu/skiplist`

Basic Usage

Here is a quick sample.

```
package main
import (
"fmt"
"github.com/huandu/skiplist"
)
func main() {
// Create a skip list with int key.
list := skiplist.New(skiplist.Int)
// Add some values. Value can be anything.
list.Set(12, "hello world")
list.Set(34, 56)
list.Set(78, 90.12)
// Get element by index.
elem := list.Get(34) // Value is stored in elem.Value.
fmt.Println(elem.Value) // Output: 56
next := elem.Next() // Get next element.
prev := next.Prev() // Get previous element.
fmt.Println(next.Value, prev.Value) // Output: 90.12 56
// Or, directly get value just like a map
val, ok := list.GetValue(34)
fmt.Println(val, ok) // Output: 56 true
// Remove an element for key.
list.Remove(34)
}
```

`GreaterThanFunc`

and `LessThanFunc`

Define your own `GreaterThanFunc`

or `LessThanFunc`

to use any custom type as the key in a skip list.

The signature of `GreaterThanFunc`

are `LessThanFunc`

are the same. The only difference between them is that `LessThanFunc`

reverses result returned by custom func to make the list ordered by key in a reversed order.

```
type T struct {
Rad float64
}
list := New(GreaterThanFunc(func(k1, k2 interface{}) int {
s1 := math.Sin(k1.(T).Rad)
s2 := math.Sin(k2.(T).Rad)
if s1 > s2 {
return 1
} else if s1 < s2 {
return -1
}
return 0
}))
list.Set(T{math.Pi / 8}, "sin(π/8)")
list.Set(T{math.Pi / 2}, "sin(π/2)")
list.Set(T{math.Pi}, "sin(π)")
fmt.Println(list.Front().Value) // Output: sin(π)
fmt.Println(list.Back().Value) // Output: sin(π/2)
```

License

This library is licensed under MIT license. See LICENSE for details.