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

    Constants

    This section is empty.

    Variables

    This section is empty.

    Functions

    This section is empty.

    Types

    type Entries

    type Entries []Entry

      Entries is a typed list of Entry interfaces.

      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.

          func (*Iterator) Next

          func (iter *Iterator) Next() bool

            Next will return a bool indicating if another value exists in the iterator.

            func (*Iterator) Value

            func (iter *Iterator) Value() Entry

              Value will return the Entry representing the iterator's current position. If no Entry exists at the present condition, the iterator is exhausted and this method will return nil.

              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

                  func (xft *XFastTrie) Delete(keys ...uint64)

                    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

                    func (xft *XFastTrie) Exists(key uint64) bool

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

                      func (*XFastTrie) Get

                      func (xft *XFastTrie) Get(key uint64) Entry

                        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

                        func (xft *XFastTrie) Insert(entries ...Entry)

                          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

                          func (xft *XFastTrie) Iter(key uint64) *Iterator

                            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) Len

                            func (xft *XFastTrie) Len() uint64

                              Len returns the number of items in this trie. This is an O(1) operation.

                              func (*XFastTrie) Max

                              func (xft *XFastTrie) Max() Entry

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

                                func (*XFastTrie) Min

                                func (xft *XFastTrie) Min() Entry

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

                                  func (*XFastTrie) Predecessor

                                  func (xft *XFastTrie) Predecessor(key uint64) Entry

                                    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.

                                    func (*XFastTrie) Successor

                                    func (xft *XFastTrie) Successor(key uint64) Entry

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