Documentation ¶
Overview ¶
Package skiplist implements fast indexable ordered multimaps.
This skip list has some features that make it special: It supports position-index addressing. It can act as a map or as a multimap. It automatically adjusts its depth. It mimics Go's container/list interface where possible. It automatically and efficiently supports int*, float*, uint*, string, and []byte keys. It supports externally defined key types via the FastKey and SlowKey interfaces.
Get, Set, Insert, Remove*, Element*, and Pos operations all require O(log(N)) time or less, where N is the number of entries in the list. GetAll() requires O(log(N)+V) time where V is the number of values returned. The skiplist requires O(N) space.
Example ¶
// Create a skiplist and add some entries: s := New().Set("one", "un").Set("two", nil).Set("three", "trois") // Retrieve a mapping: fmt.Println(1, s.Get("two")) // Replace a mapping: s.Set("two", "deux") // Print the skiplist: fmt.Println(2, s) // Add more than one value for a key, even of different value-type: s.Insert("three", 3) // Retrieve all values for the key: fmt.Println(3, s.GetAll("three")) // Or just the youngest: fmt.Println(4, s.Get("three")) // Iterate over all values in the map: fmt.Print(5) for e := s.Front(); nil != e; e = e.Next() { fmt.Print(" ", e.Key(), "->", e.Value) } fmt.Println() // Pop the first entry: s.RemoveN(0) // Pop the last entry: s.RemoveN(s.Len() - 1) fmt.Println(6, s)
Output: 1 <nil> 2 {one:un three:trois two:deux} 3 [3 trois] 4 3 5 one->un three->3 three->trois two->deux 6 {three:3 three:trois}
Index ¶
- type Element
- type FastKey
- type SlowKey
- type T
- func (l *T) Element(key interface{}) (e *Element)
- func (l *T) ElementN(index int) *Element
- func (l *T) ElementPos(key interface{}) (e *Element, pos int)
- func (l *T) Front() *Element
- func (l *T) Get(key interface{}) (value interface{})
- func (l *T) GetAll(key interface{}) (values []interface{})
- func (l *T) GetOk(key interface{}) (value interface{}, ok bool)
- func (l *T) Insert(key interface{}, value interface{}) *T
- func (l *T) Len() int
- func (l *T) Pos(key interface{}) (pos int)
- func (l *T) Remove(key interface{}) *Element
- func (l *T) RemoveElement(e *Element) *Element
- func (l *T) RemoveN(index int) *Element
- func (l *T) Set(key interface{}, value interface{}) *T
- func (l *T) String() string
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Element ¶
type Element struct { Value interface{} // contains filtered or unexported fields }
Element is an key/value pair inserted into the list. Use element.Key() to access the protected key.
func (*Element) Key ¶
func (e *Element) Key() interface{}
Key returns the key used to insert the value in the list element in O(1) time.
func (*Element) Next ¶
Next returns the next-higher-indexed list element or nil in O(1) time.
Example ¶
This example demonstrates iteration over all list elements.
s := New().Insert(0, 0).Insert(1, 1).Insert(1, 2).Insert(2, 4) // Efficiently iterate over all entries: fmt.Print("A") for e := s.Front(); e != nil; e = e.Next() { fmt.Print(" ", e) } fmt.Println() // Efficiently iterate over entries for a single key: fmt.Print("B") for e := s.Element(1); e != nil && e.Key().(int) == 1; e = e.Next() { fmt.Print(" ", e) }
Output: A 0:0 1:2 1:1 2:4 B 1:2 1:1
type FastKey ¶
The FastKey interface allows externally-defined types to be used as keys, efficiently. An a.Less(b) call should return true iff a < b. key.Score() must increase monotonically as key increases.
Example ¶
Any type implementing the FastKey interface can be used as a key.
package main import "fmt" // For any old type: type FastType struct{ a, b int } // Implement the SlowKey interface: func (a *FastType) Less(b interface{}) bool { // For example, sort by the sum of the elements in the struct: mb := b.(*FastType) return (a.a + a.b) < (mb.a + mb.b) } func (*FastType) Score(i interface{}) float64 { // Score(i) increase monotonically with increasing key value. m := i.(*FastType) return float64(m.a + m.b) } // Any type implementing the FastKey interface can be used as a key. func main() { keys := []FastType{{1, 2}, {5, 6}, {3, 4}} s := New().Insert(&keys[0], 1).Insert(&keys[1], 2).Insert(&keys[2], 3) fmt.Print(s) }
Output: {&{1 2}:1 &{3 4}:3 &{5 6}:2}
type SlowKey ¶
type SlowKey interface {
Less(interface{}) bool
}
The SlowKey interface allows externally-defined types to be used as keys. An a.Less(b) call should return true iff a < b.
Example ¶
Any type implementing the SlowKey interface can be used as a key.
package main import "fmt" // For any old type: type MyType struct{ a, b int } // Implement the SlowKey interface: func (a *MyType) Less(b interface{}) bool { // For example, sort by the sum of the elements in the struct: mb := b.(*MyType) return (a.a + a.b) < (mb.a + mb.b) } // Any type implementing the SlowKey interface can be used as a key. func main() { keys := []MyType{{1, 2}, {5, 6}, {3, 4}} s := New().Insert(&keys[0], 1).Insert(&keys[1], 2).Insert(&keys[2], 3) fmt.Print(s) }
Output: {&{1 2}:1 &{3 4}:3 &{5 6}:2}
type T ¶
type T struct {
// contains filtered or unexported fields
}
A skiplist.T is a skiplist. A skiplist is linked at multiple levels. The bottom level (L0) is a sorted linked list of entries, and each link has a link at the next higher level added with probability P at insertion. Since this is a position-addressable skip-list, each link has an associated 'width' specifying the number of nodes it skips, so nodes can also be referenced by position.
For example, a skiplist containing values from 0 to 0x16 might be structured like this:
L4 |---------------------------------------------------------------------->/ L3 |------------------------------------------->|------------------------->/ L2 |---------->|---------->|---------->|------->|---------------->|---->|->/ L1 |---------->|---------->|---------->|->|---->|->|->|->|------->|->|->|->/ L0 |->|->|->|->|->|->|->|->|->|->|->|->|->|->|->|->|->|->|->|->|->|->|->|->/ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 1 2 3 4 5 6 7 8 9 a b c d e f 0 1 2 3 4 5 6
The skiplist is searched starting at the top level, going as far right as possible without passing the desired Element, dropping down one level, and repeating for each level.
func New ¶
func New() *T
New returns a new skiplist in O(1) time. The list will be sorted from least to greatest key.
func NewDescending ¶
func NewDescending() *T
NewDescending is like New, except keys are sorted from greatest to least.
func (*T) Element ¶
Element returns the youngest list element for key, without modifying the list, in O(log(N)) time. If there is no match, nil is returned.
func (*T) ElementN ¶
ElementN returns the Element at position pos in the skiplist, in O(log(index)) time. If no such entry exists, nil is returned.
func (*T) ElementPos ¶
Element returns the youngest list element for key and its position, If there is no match, nil and -1 are returned.
Consider using Get or GetAll instead if you only want Values.
func (*T) Get ¶
func (l *T) Get(key interface{}) (value interface{})
Get returns the value corresponding to key in the table in O(log(N)) time. If there is no corresponding value, nil is returned. If there are multiple corresponding values, the youngest is returned.
If the list might contain an nil value, you may want to use GetOk instead.
func (*T) GetAll ¶
func (l *T) GetAll(key interface{}) (values []interface{})
GetAll returns all values coresponding to key in the list, starting with the youngest. If no value corresponds, an empty slice is returned. O(log(N)+V) time is required, where M is the number of values returned.
Example ¶
s := New().Insert(0, 0).Insert(1, 1).Insert(1, 2).Insert(2, 4) // Conveniently iterate over values for a single key: for _, ee := range s.GetAll(1) { fmt.Print(" ", ee) }
Output: 2 1
func (*T) GetOk ¶
GetOk returns the value corresponding to key in the table in O(log(N)) time. The return value ok is true iff the key was present. If there is no corresponding value, nil and false are returned. If there are multiple corresponding values, the youngest is returned.
func (*T) Pos ¶
ElementPos returns the position of the youngest list element for key, without modifying the list, in O(log(N)) time. If there is no match, -1 is returned.
Consider using Get or GetAll instead if you only want Values.
func (*T) Remove ¶
Remove the youngest Element associate with Key, if any, in O(log(N)) time. Return the removed element or nil.
Example ¶
One may Remove() during iteration.
skip := New().Insert(1, 10).Insert(2, 20).Insert(3, 30) for e := skip.Front(); nil != e; e = e.Next() { fmt.Println(skip.Remove(e.Key())) }
Output: 1:10 2:20 3:30
func (*T) RemoveElement ¶
Remove the specified element from the table, in O(log(N)) time. If the element is one of M multiple entries for the key, and additional O(M) time is required. This is useful for removing a specific element in a multimap, or removing elements during iteration.
Example ¶
One may RemoveElement() during iteration.
skip := New().Insert(1, 10).Insert(2, 20).Insert(3, 30) for e := skip.Front(); nil != e; e = e.Next() { fmt.Println(skip.RemoveElement(e)) }
Output: 1:10 2:20 3:30
func (*T) RemoveN ¶
RemoveN removes any element at position pos in O(log(N)) time, returning it or nil.