## Documentation

### Overview ¶

Package yfast implements a y-fast trie. Instead of a red-black BBST for the leaves, this implementation uses a simple ordered list. This package should have searches that are as performant as the x-fast trie while having faster inserts/deletes and linear space consumption.

Performance characteristics: Space: O(n) Get: O(log log M) Search: O(log log M) Insert: O(log log M) Delete: O(log log M)

where n is the number of items in the trie and M is the size of the universe, ie, 2^m where m is the number of bits in the specified key size.

This particular implementation also uses fixed bucket sizes as this should aid in multithreading these functions for performance optimization.

### Index ¶

- type Entries
- type Entry
- type Iterator
- type YFastTrie
- func (yfast *YFastTrie) Delete(keys ...uint64) Entries
- func (yfast *YFastTrie) Get(key uint64) Entry
- func (yfast *YFastTrie) Insert(entries ...Entry) Entries
- func (yfast *YFastTrie) Iter(key uint64) *Iterator
- func (yfast *YFastTrie) Len() uint64
- func (yfast *YFastTrie) Predecessor(key uint64) Entry
- func (yfast *YFastTrie) Successor(key uint64) Entry

### Constants ¶

### Variables ¶

### Functions ¶

### Types ¶

#### type Entries ¶

type Entries []Entry

Entries is a typed list of Entry. The size of entries will be limited to 1/2log M to 2log M where M is the size of the universe.

#### type Entry ¶

type Entry interface { // Key is the key for this entry. If the trie has been // given bit size n, only the last n bits of this key // will matter. Use a bit size of 64 to enable all // 2^64-1 keys. Key() uint64 }

Entry defines items that can be inserted into the y-fast trie.

#### type Iterator ¶

```
type Iterator struct {
// contains filtered or unexported fields
}
```

Iterator will iterate of the results of a query.

#### type YFastTrie ¶

```
type YFastTrie struct {
// contains filtered or unexported fields
}
```

YFastTrie implements all the methods available to the y-fast trie datastructure. The top half is composed of an x-fast trie while the leaves are composed of ordered lists of type Entry, an interface found in this package.

#### func New ¶

func New(ifc interface{}) *YFastTrie

New constructs, initializes, and returns a new y-fast trie. Provided should be a uint type that specifies the number of bits in the desired universe. This will affect the time complexity of all lookup and mutate operations.

#### func (*YFastTrie) Delete ¶

Delete will delete the provided keys from the y-fast trie and return a list of entries that were deleted.

#### func (*YFastTrie) Get ¶

Get will look for the provided key in the y-fast trie and return the associated value if it is found. If it is not found, this method returns nil.

#### func (*YFastTrie) Insert ¶

Insert will insert the provided entries into the y-fast trie and return a list of entries that were overwritten.

#### func (*YFastTrie) Iter ¶

Iter will return an iterator that will iterate across all values that start or immediately proceed the provided key. Iteration happens in ascending order.

#### func (*YFastTrie) Predecessor ¶

Predecessor returns an Entry with a key equal to or immediately preceeding than the provided key. If such an Entry does not exist this returns nil.