skiplist: github.com/fumin/skiplist Index | Examples | Files

package skiplist

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.

Index

Examples

Package Files

skiplist.go

Constants

const (
    MaxLevel = 32
)

func Sample Uses

func Sample(k, max int) (sampled []int)

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 Uses

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 Uses

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 Uses

type Skiplist struct {
    // contains filtered or unexported fields
}

func New Uses

func New() *Skiplist

New creates a new skiplist

func (*Skiplist) Cardinality Uses

func (z *Skiplist) Cardinality() int

Cardinality returns the number of elements in the skiplist

func (*Skiplist) Delete Uses

func (z *Skiplist) Delete(ordered Ordered) bool

Delete removes an element from the Skiplist. If the removal is successful, Delete returns true, otherwise, false.

func (*Skiplist) Insert Uses

func (z *Skiplist) Insert(ordered Ordered)

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

func (*Skiplist) PrintDebug Uses

func (z *Skiplist) PrintDebug()

func (*Skiplist) Range Uses

func (z *Skiplist) Range(start, stop int) (reply []Ordered)

Range returns elements whose rank is between start and stop. Both arguments, start and stop are inclusive, and are 0 based.

func (*Skiplist) RangeByScore Uses

func (z *Skiplist) RangeByScore(spec RangeSpec, offset, limit int) (reply []Ordered)

RangeByScore returns elements within the range spec in accending order.

func (*Skiplist) RankOfFirstInRange Uses

func (z *Skiplist) RankOfFirstInRange(spec RangeSpec) int

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.

func (*Skiplist) RankOfLastInRange Uses

func (z *Skiplist) RankOfLastInRange(spec RangeSpec) int

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.

func (*Skiplist) SampleInRange Uses

func (z *Skiplist) SampleInRange(spec RangeSpec, limit int) (reply []Ordered)

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]

func (*Skiplist) SampleInRange_Slow Uses

func (z *Skiplist) SampleInRange_Slow(spec RangeSpec, limit int) (reply []Ordered)

Package skiplist imports 3 packages (graph). Updated 2016-07-27. Refresh now. Tools for package owners.