import "github.com/fumin/skiplist"
Package skiplist is an implementation of the Skiplist data structure. The API of this package follows closely that of Redis Sorted Sets. For example, the function Range returns elements by their indices, and the function RangeByScore returns elements whose score lie within an interval. In fact, most of the actual implementation is copied from Redis https://github.com/antirez/redis.
The unique feature of this package though, is SampleInRange which is an optimized way of randomly sampling elements from a given range. According to the benchmarks, SampleInRange is around 12% faster than the naive implementation.
const (
MaxLevel = 32
)Sample randomly selects k integers from the range [0, max). Given that Sample's algorithm is to run Fisher-Yates shuffle k times, it's complexity is O(k).
type Ordered interface {
// Less reports whether we are *strictly* less than other.
Less(other Ordered) bool
}The Ordered interface should be implemented by types that wish to be added into skiplists.
type RangeSpec struct {
Min, Max Ordered
Minex, Maxex bool // End points are excluded if Minex or Maxex is true.
}RangeSpec is an interval with information about the inclusiveness of its boundaries.
type Skiplist struct {
// contains filtered or unexported fields
}New creates a new skiplist
Cardinality returns the number of elements in the skiplist
Delete removes an element from the Skiplist. If the removal is successful, Delete returns true, otherwise, false.
Insert adds an item to a Skiplist
Code:
rand.Seed(1)
z := New()
for i := 0; i < 20; i++ {
z.Insert(Int(i))
}
z.PrintDebug()
Output:
length: 20, level: 5 head____________ 6________________________ head____________ 6__________12____________ head____________ 6__ 8______12____15______ head__________ 5 6 7 8____1112____15__17__ head 0 1 2 3 4 5 6 7 8 910111213141516171819
Range returns elements whose rank is between start and stop. Both arguments, start and stop are inclusive, and are 0 based.
RangeByScore returns elements within the range spec in accending order.
RankOfFirstInRange returns the rank of the first node in the range spec. A rank of -1 means that no node exists in the range spec.
RankOfLastInRange returns the rank of the last node in the range spec. A rank of -1 means that no node exists in the range spec.
SampleInRange is similar to RangeByScore in that it also returns elements within the range spec. The difference is however, the elements returned by RangeSample are randomly and evenly sampled from the range.
Code:
rand.Seed(1)
z := New()
for i := 0; i < 20; i++ {
z.Insert(Int(i))
}
sampled := z.SampleInRange(RangeSpec{Min: Int(4), Max: Int(17)}, 5)
fmt.Println(sampled)
Output:
[5 8 10 13 14]
Package skiplist imports 3 packages (graph). Updated 2016-07-27. Refresh now. Tools for package owners.