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

    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. 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.

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

                  func (yfast *YFastTrie) Delete(keys ...uint64) Entries

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

                    func (*YFastTrie) Get

                    func (yfast *YFastTrie) Get(key uint64) Entry

                      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

                      func (yfast *YFastTrie) Insert(entries ...Entry) Entries

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

                        func (*YFastTrie) Iter

                        func (yfast *YFastTrie) Iter(key uint64) *Iterator

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

                          func (yfast *YFastTrie) Len() uint64

                            Len returns the number of items in the y-fast trie.

                            func (*YFastTrie) Predecessor

                            func (yfast *YFastTrie) Predecessor(key uint64) Entry

                              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.

                              func (*YFastTrie) Successor

                              func (yfast *YFastTrie) Successor(key uint64) Entry

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