Go package implementing an indexable ordered multimap

Overview
PACKAGE

package skiplist
    import "github.com/glenn-brown/skiplist"

    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.

TYPES

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 (e *Element) Key() interface{}
    Key returns the key used to insert the value in the list element in O(1)
    time.

func (e *Element) Next() *Element
    Next returns the next-higher-indexed list element or nil in O(1) time.

func (e *Element) String() string
    String returns a Key:Value string representation of the element.

type FastKey interface {
    Less(interface{}) bool
    Score() float64
}
    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.

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.

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() *T
    New returns a new skiplist in O(1) time. The list will be sorted from
    least to greatest key.

func NewDescending() *T
    NewDescending is like New, except keys are sorted from greatest to
    least.

func (l *T) Element(key interface{}) (e *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 (l *T) ElementN(index int) *Element
    ElementN returns the Element at position pos in the skiplist, in
    O(log(index)) time. If no such entry exists, nil is returned.

func (l *T) ElementPos(key interface{}) (e *Element, pos int)
    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 (l *T) Front() *Element
    Return the first list element in O(1) time.

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 (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.

func (l *T) GetOk(key interface{}) (value interface{}, ok bool)
    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 (l *T) Insert(key interface{}, value interface{}) *T
    Insert a {key,value} pair into the skip list in O(log(N)) time.

func (l *T) Len() int
    Len returns the number of elements in the T.

func (l *T) Pos(key interface{}) (pos int)
    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 (l *T) Remove(key interface{}) *Element
    Remove the youngest Element associate with Key, if any, in O(log(N))
    time. Return the removed element or nil.

func (l *T) RemoveElement(e *Element) *Element
    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.

func (l *T) RemoveN(index int) *Element
    RemoveN removes any element at position pos in O(log(N)) time, returning
    it or nil.

func (l *T) Set(key interface{}, value interface{}) *T
    Insert a {key,value} pair into the skip list in O(log(N)) time,
    replacing the youngest entry for key, if any.

func (l *T) String() string
    Function String prints only the key/value pairs in the skip list.


Issues
  • Bugs fixed. Convinient function added.

    Bugs fixed. Convinient function added.

    There was two bugs: -one appeares when one tries to Get or Remove from empty list. (prevs function returns empty slice in this case, and there wasn't a check for this before prev[0] indexing) -the other appeares when one tries RemoveElement with a key, which have several elements in the list. (infinite loop because of changing copy of variable)

    Besides there was a lack of Insert function that returns the newly created Element (issue #2 )

    opened by pashaosipyants 0
  • Removing from an empty skiplist panics

    Removing from an empty skiplist panics

    If I call Remove on a skiplist with no items, there's a panic

    panic: runtime error: index out of range

    github.com/glenn-brown/skiplist.(*T).Remove(0xc208036140, 0x4fbf80, 0xc20800a4d0, 0xc20800a4d0) /home/matt/gopath/src/github.com/glenn-brown/skiplist/skiplist.go:262 +0x1ad

    opened by anacrolix 0
Owner
Glenn Brown
Glenn Brown
BTree provides a simple, ordered, in-memory data structure for Go programs.

BTree implementation for Go This package provides an in-memory B-Tree implementation for Go, useful as an ordered, mutable data structure. The API is

Google 2.7k May 17, 2022
Go package implementing bitsets

bitset Go language library to map between non-negative integers and boolean values Description Package bitset implements bitsets, a mapping between no

Will Fitzgerald 881 May 17, 2022
Go package implementing Bloom filters

Bloom filters A Bloom filter is a representation of a set of n items, where the main requirement is to make membership queries; i.e., whether an item

Will Fitzgerald 1.6k May 15, 2022
Go package implementing Bloom filters

Bloom filters A Bloom filter is a concise/compressed representation of a set, where the main requirement is to make membership queries; i.e., whether

Go language BitSet and Bloom filter 1.6k May 20, 2022
Go library implementing xor filters

xorfilter: Go library implementing xor filters Bloom filters are used to quickly check whether an element is part of a set. Xor filters are a faster a

null 569 May 16, 2022
Package set is a small wrapper around the official reflect package that facilitates loose type conversion and assignment into native Go types.

Package set is a small wrapper around the official reflect package that facilitates loose type conversion and assignment into native Go types. Read th

null 30 Apr 28, 2022
Go package for mapping values to and from space-filling curves, such as Hilbert and Peano curves.

Hilbert Go package for mapping values to and from space-filling curves, such as Hilbert and Peano curves. Documentation available here This is not an

Google 250 Apr 20, 2022
Package ring provides a high performance and thread safe Go implementation of a bloom filter.

ring - high performance bloom filter Package ring provides a high performance and thread safe Go implementation of a bloom filter. Usage Please see th

Tanner Ryan 126 May 10, 2022
A package for Go that can be used for range queries on large number of intervals

go-stree go-stree is a package for Go that can be used to process a large number of intervals. The main purpose of this module is to solve the followi

Thomas Oberndörfer 40 Apr 12, 2022
parody of some of the basic python core features (collections package)

collections import "github.com/marcsantiago/collections" Overview Index Subdirectories Overview Index func StringEncoder(encoder *bytes.Buffer, data D

Marc Santiago 18 Jan 14, 2022
Package mafsa implements Minimal Acyclic Finite State Automata in Go, essentially a high-speed, memory-efficient, Unicode-friendly set of strings.

MA-FSA for Go Package mafsa implements Minimal Acyclic Finite State Automata (MA-FSA) with Minimal Perfect Hashing (MPH). Basically, it's a set of str

SmartyStreets (Archives) 287 Apr 5, 2022
Package for indexing zip files and storing a compressed index

zipindex zipindex provides a size optimized representation of a zip file to allow decompressing the file without reading the zip file index. It will o

High Performance, Kubernetes Native Object Storage 27 May 10, 2022
peanut is a Go package to write tagged data structs to disk in a variety of formats.

peanut peanut is a Go package to write tagged data structs to disk in a variety of formats. Its primary purpose is to provide a single consistent inte

Jim Smart 3 Apr 21, 2021
graph package by golang

graph-go sample package main import ( "fmt" "github.com/Iovesophy/graph-go" ) func main() { samplePlace := []graph.Node{ {ID: 1, Element: "plac

Iovesophy 4 Oct 24, 2021
Package iter provides generic, lazy iterators, functions for producing them from primitive types, as well as functions and methods for transforming and consuming them.

iter Package iter provides generic, lazy iterators, functions for producing them from primitive types, as well as functions and methods for transformi

Matthew Toohey 21 May 6, 2022
Advanced linked list package for go.

golib/list ライブラリ 可変長の連結リストを提供するライブラリーです。 状況によらず、メモリ開放処理を一貫性した書き方で実装できるので、メモリ解放をプログラマが管理しやすい作りになっています。 list.List 片方向連結リストを提供するモジュールです。 list.Nodeが使われていま

null 0 Jan 21, 2022
GoIntervalTree - An IntervalTree package for Go

GoIntervalTree An IntervalTree package for Go Inspired by Centered Interval Tree implementation in Python This package provides functionality for inde

Kirill Danilov 1 Feb 5, 2022
Type-agnostic partitioning for Go's indexable collections and strings.

Go Type-Agnostic Collection Partitioning Type-agnostic partitioning for anything that can be indexed in Go - slices, arrays,strings. Inspired by Guava

Meir Fischer 35 Aug 11, 2021
Peimports - based on golang's debug/pe this package gives quick access to the ordered imports of pe files with ordinal support

This code is almost entirely derived from the Go standard library's debug/pe package. It didn't provide access to ordinal based entries in the IAT and

Mike Wiacek 0 Jan 5, 2022
BTree provides a simple, ordered, in-memory data structure for Go programs.

BTree implementation for Go This package provides an in-memory B-Tree implementation for Go, useful as an ordered, mutable data structure. The API is

Google 2.7k May 17, 2022
moss - a simple, fast, ordered, persistable, key-val storage library for golang

moss moss provides a simple, fast, persistable, ordered key-val collection implementation as a 100% golang library. moss stands for "memory-oriented s

null 866 May 20, 2022
Simple, ordered, key-value persistence library for the Go Language

gkvlite gkvlite is a simple, ordered, ACID, key-value persistence library for Go. Overview gkvlite is a library that provides a simple key-value persi

Steve Yen 252 Apr 18, 2022
moss - a simple, fast, ordered, persistable, key-val storage library for golang

moss provides a simple, fast, persistable, ordered key-val collection implementation as a 100% golang library.

null 866 May 20, 2022
Optimal implementation of ordered maps for Golang - ie maps that remember the order in which keys were inserted.

Goland Ordered Maps Same as regular maps, but also remembers the order in which keys were inserted, akin to Python's collections.OrderedDicts. It offe

Jean Rougé 183 May 17, 2022
searchHIBP is a golang tool that implements binary search over a hash ordered binary file.

searchHIBP is a golang tool that implements binary search over a hash ordered binary file.

fblz 0 Nov 9, 2021
Easy to use arbitrarily-ordered encoding/binary.ByteOrder

byteorder byteorder is a Go module for working with arbitrarily-ordered byte slices. It is useful e.g. when dealing with Modbus wire formats. Installa

andig 0 Dec 5, 2021
Drop-in replacement for Go's flag package, implementing POSIX/GNU-style --flags.

Description pflag is a drop-in replacement for Go's flag package, implementing POSIX/GNU-style --flags. pflag is compatible with the GNU extensions to

Steve Francia 1.8k May 19, 2022
Drop-in replacement for Go's flag package, implementing POSIX/GNU-style --flags.

Description pflag is a drop-in replacement for Go's flag package, implementing POSIX/GNU-style --flags. pflag is compatible with the GNU extensions to

Alex Ogier 511 May 7, 2022
Go package implementing bitsets

bitset Go language library to map between non-negative integers and boolean values Description Package bitset implements bitsets, a mapping between no

Will Fitzgerald 881 May 17, 2022