## Documentation

### Overview ¶

Package xfast provides access to a sorted tree that treats integers as if they were words of m bits, where m can be 8, 16, 32, or 64. The advantage to storing integers as a trie of words is that operations can be performed in constant time depending on the size of the universe and not on the number of items in the trie.

The time complexity is as follows: Space: O(n log M) Insert: O(log M) Delete: O(log M) Search: O(log log M) Get: O(1)

where n is the number of items in the trie and M is the size of the universe, ie, 2^63-1 for 64 bit ints.

As you can see, for 64 bit ints, inserts and deletes can be performed in O(64), constant time which provides very predictable behavior in the best case.

A get by key can be performed in O(1) time and searches can be performed in O(6) time for 64 bit integers.

While x-tries have relatively slow insert, deletions, and consume a large amount of space, they form the top half of a y-fast trie which can insert and delete in O(log log M) time and consumes O(n) space.

### Index ¶

- type Entries
- type Entry
- type Iterator
- type XFastTrie
- func (xft *XFastTrie) Delete(keys ...uint64)
- func (xft *XFastTrie) Exists(key uint64) bool
- func (xft *XFastTrie) Get(key uint64) Entry
- func (xft *XFastTrie) Insert(entries ...Entry)
- func (xft *XFastTrie) Iter(key uint64) *Iterator
- func (xft *XFastTrie) Len() uint64
- func (xft *XFastTrie) Max() Entry
- func (xft *XFastTrie) Min() Entry
- func (xft *XFastTrie) Predecessor(key uint64) Entry
- func (xft *XFastTrie) Successor(key uint64) Entry

### Constants ¶

### Variables ¶

### Functions ¶

### Types ¶

#### 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 x-fast trie.

#### type Iterator ¶

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

Iterator will iterate of the results of a query.

#### type XFastTrie ¶

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

XFastTrie is a datastructure for storing integers in a known universe, where universe size is determined by the bit size of the desired keys. This structure should be faster than binary search tries for very large datasets and slower for smaller datasets.

#### func New ¶

func New(ifc interface{}) *XFastTrie

New will construct a new X-Fast Trie with the given "size," that is the size of the universe of the trie. This expects a uint of some sort, ie, uint8, uint16, etc. The size of the universe will be 2^n-1 and will affect the speed of all operations. IFC MUST be a uint type.

#### func (*XFastTrie) Delete ¶

Delete will delete the provided keys from the trie. If an entry associated with a provided key cannot be found, that deletion is a no-op. Each deletion is an O(log M) operation.

#### func (*XFastTrie) Exists ¶

Exists returns a bool indicating if the provided key exists in the trie. This is an O(1) operation.

#### func (*XFastTrie) Get ¶

Get will return a value in the trie associated with the provided key if it exists. Returns nil if the key does not exist. This is expected to take O(1) time.

#### func (*XFastTrie) Insert ¶

Insert will insert the provided entries into the trie. Any entry with an existing key will cause an overwrite. This is an O(log M) operation, for each entry.

#### func (*XFastTrie) Iter ¶

Iter will return an iterator that will iterate over all values equal to or immediately greater than the provided key. Iterator will iterate successor relationships.

#### func (*XFastTrie) Max ¶

Max will return the highest keyed value in the trie. This is an O(1) operation.

#### func (*XFastTrie) Min ¶

Min will return the lowest keyed value in the trie. This is an O(1) operation.

#### func (*XFastTrie) Predecessor ¶

Predecessor will return an Entry which matches the provided key or its immediate predecessor. Will return nil if a predecessor does not exist. This is an O(log log M) operation.