tree

Documentation

Index

• func KmerPrefix(code uint64, k uint8, n uint8) uint64
• func RecycleTree(t *Tree)
• type SearchResult
• type Tree
  • func NewTree(k uint8) *Tree
  • func (t *Tree) Insert(key uint64, v uint32) bool
  • func (t *Tree) K() int
  • func (idx *Tree) RecycleSearchResult(sr *[]*SearchResult)
  • func (t *Tree) Search(key uint64, p uint8) (*[]*SearchResult, bool)
  • func (t *Tree) Walk(fn WalkFn)
• type WalkFn

Functions

func KmerPrefix

func KmerPrefix(code uint64, k uint8, n uint8) uint64

KmerPrefix returns the first n bases. n needs to be > 0. The length of the prefix is n.

func RecycleTree

func RecycleTree(t *Tree)

RecycleTree recycles the tree object.

Types

type SearchResult

type SearchResult struct {
	Kmer      uint64   // searched kmer
	LenPrefix uint8    // length of common prefix between the query and this k-mer
	Values    []uint32 // value of this key
}

SearchResult records information of a search result.

type Tree

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

Tree is a radix tree for storing bit-packed k-mer information.

func NewTree

func NewTree(k uint8) *Tree

NewTree implements a radix tree for k-mer extractly or prefix querying.

func (*Tree) Insert

func (t *Tree) Insert(key uint64, v uint32) bool

Insert is used to add a new entry or update an existing entry. Returns true if an existing record is updated.

func (*Tree) K

func (t *Tree) K() int

K returns the K value of k-mers.

func (*Tree) RecycleSearchResult

func (idx *Tree) RecycleSearchResult(sr *[]*SearchResult)

RecycleSearchResult recycles search results objects.

func (*Tree) Search

func (t *Tree) Search(key uint64, p uint8) (*[]*SearchResult, bool)

Search finds keys that shared prefixes at least p bases. We assume the k values of the query k-mer and k-mers in the tree are the same. After using the result, do not forget to call RecycleSearchResult().

func (*Tree) Walk

func (t *Tree) Walk(fn WalkFn)

Walk is used to walk the whole tree.

type WalkFn

type WalkFn func(key uint64, v []uint32) bool

WalkFn is used for walking the tree. Takes a key and value, returning if iteration should be terminated. type WalkFn func(key uint64, k uint8, v []uint64) bool