sorts: github.com/twotwotwo/sorts/index Index | Files

package index

import "github.com/twotwotwo/sorts/index"

Package index uses sorted arrays of integers to assist sorting and searching, particularly of collections of strings.

Index

Package Files

index.go

func BytesKey Uses

func BytesKey(key []byte) uint64

BytesKey generates a uint64 key from the first bytes of key.

func CompareBytesToString Uses

func CompareBytesToString(a []byte, b string) int

CompareBytesToString is a convenience wrapper for CompareStringToBytes.

func CompareStringToBytes Uses

func CompareStringToBytes(a string, b []byte) int

Compares string a to []byte b, returning -1 if a<b, 0 if a==b, and 1 if a>b.

func StringKey Uses

func StringKey(key string) uint64

StringKey generates a uint64 key from the first bytes of key.

type Index Uses

type Index struct {
    Keys    []uint64
    Summary []uint64 // implicit B-tree, if Summarize() was called
    Data    sort.Interface
}

func SortWithIndex Uses

func SortWithIndex(data sort.Interface) *Index

SortWithIndex allocates an Index with space for a uint64 key for each item in data, then sorts items by their uint64 keys, using data.Less as a tie-breaker for equal-keyed items. data may implement index.KeySetter or any of sorts.StringInterface, BytesInterface, or Uint64Interface.

func (*Index) FindBytes Uses

func (idx *Index) FindBytes(key []byte) int

FindBytes finds the first item >= key, returning one after the end if there is none. The collection type must implement Key(i) returning string or []byte.

func (*Index) FindBytesRange Uses

func (idx *Index) FindBytesRange(key []byte) (int, int)

FindBytesRange(key) finds the range (a,b] such that Key() returns key for all items in idx.Data[a:b]. It can return an empty range if the item isn't found; in that case, a is where the item would be inserted (and can be one past the end). Data must implement Key(i) returning string or []byte. To find a single item, use FindBytes.

func (*Index) FindString Uses

func (idx *Index) FindString(key string) int

FindString finds the first item >= key, returning one after the end if there is none. The collection type must implement Key(i) returning string or []byte.

func (*Index) FindStringRange Uses

func (idx *Index) FindStringRange(key string) (int, int)

FindStringRange(key) finds the range (a,b] such that Key() returns key for all items in idx.Data[a:b]. It can return an empty range if the item isn't found; in that case, a and b are both where the item would be inserted (and can be one past the end). Data must implement Key(i) returning string or []byte. To find a single item, use FindString.

func (*Index) FindUint64 Uses

func (idx *Index) FindUint64(key uint64) int

FindUint64 finds the position of the first item >= key in Keys, returning one after the end if there is none. When different values map to the same key, you might want to sort.Search within the returned range to narrow your result down to the desired values.

func (*Index) FindUint64Range Uses

func (idx *Index) FindUint64Range(key uint64) (a, b int)

FindUint64Range looks for a range of keys such that all items in idx.Keys[a:b] equal key. It can return an empty range if the item isn't found; in that case, a and b are both where the item would be inserted (and can be one past the end). To find a single key, use FindUint64.

func (*Index) Key Uses

func (idx *Index) Key(i int) uint64

Key returns the uint64 key at index i.

func (*Index) Len Uses

func (idx *Index) Len() int

Len returns the length of the data underlying an Index

func (*Index) Less Uses

func (idx *Index) Less(i, j int) bool

Less compares Index elements by their Keys, falling back to Data.Less for equal-keyed items.

func (*Index) Summarize Uses

func (idx *Index) Summarize()

Summarize makes an implicit B-tree to speed lookups, using a few percent overhead on top of what's already used for Indices.

func (*Index) Swap Uses

func (idx *Index) Swap(i, j int)

Swap swaps both the Keys and the inderlying data items at indices i and j.

Package index imports 4 packages (graph). Updated 2016-08-14. Refresh now. Tools for package owners.