## Description

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.

## Examples

package yfast import "github.com/Workiva/go-datastructures/trie/xfast" // iteratorExhausted is a magic value for an index to tell us

// Iterator will iterate of the results of a query. type Iterator struct { xfastIterator *xfast.Iterator index int entries *entriesWrapper

package yfast import "github.com/Workiva/go-datastructures/trie/xfast" // YFastTrie implements all the methods available to the y-fast

## xfast is referenced in 1 repository

**github.com/Workiva/go-datastructures**

- 3 references in trie/yfast/yfast.go
- 2 references in trie/yfast/iterator.go
- 1 reference in trie/xfast/iterator.go
- 1 reference in trie/xfast/iterator_test.go
- 1 reference in trie/xfast/mock_test.go