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. This is an inactive package (no imports and no commits in at least two years).