trie

Documentation

Index

• func Equal(p, q *Trie) bool
• func IntersectKeySlices(p, q []key.Key) []key.Key
• func UnionKeySlices(left, right []key.Key) []key.Key
• type InvariantDiscrepancy
• type Trie
  • func Add(trie *Trie, q key.Key) *Trie
  • func AddAtDepth(depth int, trie *Trie, q key.Key) *Trie
  • func FromKeys(k []key.Key) *Trie
  • func FromKeysAtDepth(depth int, k []key.Key) *Trie
  • func Intersect(p, q *Trie) *Trie
  • func IntersectAtDepth(depth int, p, q *Trie) *Trie
  • func New() *Trie
  • func Remove(trie *Trie, q key.Key) *Trie
  • func RemoveAtDepth(depth int, trie *Trie, q key.Key) *Trie
  • func Union(left, right *Trie) *Trie
  • func UnionAtDepth(depth int, left, right *Trie) *Trie
  • func (trie *Trie) Add(q key.Key) (insertedDepth int, insertedOK bool)
  • func (trie *Trie) AddAtDepth(depth int, q key.Key) (insertedDepth int, insertedOK bool)
  • func (trie *Trie) CheckInvariant() *InvariantDiscrepancy
  • func (trie *Trie) Copy() *Trie
  • func (trie *Trie) Depth() int
  • func (trie *Trie) DepthAtDepth(depth int) int
  • func (trie *Trie) Find(q key.Key) (reachedDepth int, found bool)
  • func (trie *Trie) FindAtDepth(depth int, q key.Key) (reachedDepth int, found bool)
  • func (trie *Trie) IsEmpty() bool
  • func (trie *Trie) IsEmptyLeaf() bool
  • func (trie *Trie) IsLeaf() bool
  • func (trie *Trie) IsNonEmptyLeaf() bool
  • func (trie *Trie) List() []key.Key
  • func (trie *Trie) Remove(q key.Key) (removedDepth int, removed bool)
  • func (trie *Trie) RemoveAtDepth(depth int, q key.Key) (reachedDepth int, removed bool)
  • func (trie *Trie) Size() int
  • func (trie *Trie) SizeAtDepth(depth int) int
  • func (trie *Trie) String() string

Functions

func Equal

func Equal(p, q *Trie) bool

func IntersectKeySlices

func IntersectKeySlices(p, q []key.Key) []key.Key

func UnionKeySlices

func UnionKeySlices(left, right []key.Key) []key.Key

Types

type InvariantDiscrepancy

type InvariantDiscrepancy struct {
	Reason            string
	PathToDiscrepancy string
	KeyAtDiscrepancy  string
}

type Trie

type Trie struct {
	Branch [2]*Trie
	Key    key.Key
}

Trie is a trie for equal-length bit vectors, which stores values only in the leaves. Trie node invariants: (1) Either both branches are nil, or both are non-nil. (2) If branches are non-nil, key must be nil. (3) If both branches are leaves, then they are both non-empty (have keys).

func Add

func Add(trie *Trie, q key.Key) *Trie

Add adds the key q to trie, returning a new trie. Add is immutable/non-destructive: The original trie remains unchanged.

func AddAtDepth

func AddAtDepth(depth int, trie *Trie, q key.Key) *Trie

func FromKeys

func FromKeys(k []key.Key) *Trie

func FromKeysAtDepth

func FromKeysAtDepth(depth int, k []key.Key) *Trie

func Intersect

func Intersect(p, q *Trie) *Trie

Intersect computes the intersection of the keys in p and q. p and q must be non-nil. The returned trie is never nil.

func IntersectAtDepth

func IntersectAtDepth(depth int, p, q *Trie) *Trie

func New

func New() *Trie

func Remove

func Remove(trie *Trie, q key.Key) *Trie

func RemoveAtDepth

func RemoveAtDepth(depth int, trie *Trie, q key.Key) *Trie

func Union

func Union(left, right *Trie) *Trie

func UnionAtDepth

func UnionAtDepth(depth int, left, right *Trie) *Trie

func (*Trie) Add

func (trie *Trie) Add(q key.Key) (insertedDepth int, insertedOK bool)

Add adds the key q to the trie. Add mutates the trie.

func (*Trie) AddAtDepth

func (trie *Trie) AddAtDepth(depth int, q key.Key) (insertedDepth int, insertedOK bool)

func (*Trie) CheckInvariant

func (trie *Trie) CheckInvariant() *InvariantDiscrepancy

CheckInvariant panics of the trie does not meet its invariant.

func (*Trie) Copy

func (trie *Trie) Copy() *Trie

func (*Trie) Depth

func (trie *Trie) Depth() int

func (*Trie) DepthAtDepth

func (trie *Trie) DepthAtDepth(depth int) int

func (*Trie) Find

func (trie *Trie) Find(q key.Key) (reachedDepth int, found bool)

Find looks for the key q in the trie. It returns the depth of the leaf reached along the path of q, regardless of whether q was found in that leaf. It also returns a boolean flag indicating whether the key was found.

func (*Trie) FindAtDepth

func (trie *Trie) FindAtDepth(depth int, q key.Key) (reachedDepth int, found bool)

func (*Trie) IsEmpty

func (trie *Trie) IsEmpty() bool

func (*Trie) IsEmptyLeaf

func (trie *Trie) IsEmptyLeaf() bool

func (*Trie) IsLeaf

func (trie *Trie) IsLeaf() bool

func (*Trie) IsNonEmptyLeaf

func (trie *Trie) IsNonEmptyLeaf() bool

func (*Trie) List

func (trie *Trie) List() []key.Key

List returns a list of all keys in the trie.

func (*Trie) Remove

func (trie *Trie) Remove(q key.Key) (removedDepth int, removed bool)

Remove removes the key q from the trie. Remove mutates the trie. TODO: Also implement an immutable version of Remove.

func (*Trie) RemoveAtDepth

func (trie *Trie) RemoveAtDepth(depth int, q key.Key) (reachedDepth int, removed bool)

func (*Trie) Size

func (trie *Trie) Size() int

Size returns the number of keys added to the trie. In other words, it returns the number of non-empty leaves in the trie.

func (*Trie) SizeAtDepth

func (trie *Trie) SizeAtDepth(depth int) int

func (*Trie) String

func (trie *Trie) String() string