settrie

Documentation

Overview

Implements a modified version of SetTrie that acts like a Map[Word, Data]. Reference: Savnik, Iztok. "Efficient subset and superset queries." DB&Local Proceedings. 2012.

Index

• func EqualsWord[Alpha comparable](left, right Word[Alpha]) bool
• type ExistedBefore
• type Multi
  • func NewMulti[Alpha Ordered[Alpha], Subkey comparable, Data any]() *Multi[Alpha, Subkey, Data]
  • func (multi *Multi[Alphabet, Subkey, Data]) Insert(word Word[Alphabet], subkey Subkey, data Data) ExistedBefore
  • func (multi *Multi[Alphabet, Subkey, Data]) Remove(word Word[Alphabet], subkey Subkey) ExistedBefore
  • func (multi *Multi[Alphabet, Subkey, Data]) Subsets(word Word[Alphabet]) iter.Iter[iter.Pair[Subkey, Data]]
• type Ordered
• type SetTrie
  • func New[Alpha Ordered[Alpha], Data any]() *SetTrie[Alpha, Data]
  • func (trie *SetTrie[Alpha, Data]) CreateOrUpdate(word Word[Alpha], initNode func() Data, updateNode func(*Data))
  • func (trie *SetTrie[Alpha, Data]) Get(word Word[Alpha]) optional.Optional[Data]
  • func (trie *SetTrie[Alpha, Data]) RetainOrDrop(word Word[Alpha], process func(Data) optional.Optional[Data])
  • func (trie *SetTrie[Alpha, Data]) Subsets(word Word[Alpha]) iter.Iter[iter.Pair[Word[Alpha], Data]]
  • func (trie *SetTrie[Alpha, Data]) Supersets(word Word[Alpha]) iter.Iter[iter.Pair[Word[Alpha], Data]]
• type Word
  • func NewWord[Alpha Ordered[Alpha]](unsorted []Alpha) Word[Alpha]
  • func (word Word[Alpha]) Append(alpha Alpha) Word[Alpha]
  • func (word *Word[Alpha]) PopFirst() (Alpha, bool)
  • func (word Word[Alpha]) Sorted() []Alpha

Functions

func EqualsWord

func EqualsWord[Alpha comparable](left, right Word[Alpha]) bool

Types

type ExistedBefore

type ExistedBefore bool

type Multi

type Multi[Alpha Ordered[Alpha], Subkey comparable, Data any] struct {
	// contains filtered or unexported fields
}

A multimap that stores multiple items in each SetTrie node, analogous to map[Word]map[Subkey]Data.

func NewMulti

func NewMulti[Alpha Ordered[Alpha], Subkey comparable, Data any]() *Multi[Alpha, Subkey, Data]

func (*Multi[Alphabet, Subkey, Data]) Insert

func (multi *Multi[Alphabet, Subkey, Data]) Insert(
	word Word[Alphabet],
	subkey Subkey,
	data Data,
) ExistedBefore

func (*Multi[Alphabet, Subkey, Data]) Remove

func (multi *Multi[Alphabet, Subkey, Data]) Remove(
	word Word[Alphabet],
	subkey Subkey,
) ExistedBefore

func (*Multi[Alphabet, Subkey, Data]) Subsets

func (multi *Multi[Alphabet, Subkey, Data]) Subsets(
	word Word[Alphabet],
) iter.Iter[iter.Pair[Subkey, Data]]

type Ordered

type Ordered[Self any] interface {
	comparable
	Less(other Self) bool
}

type SetTrie

type SetTrie[Alpha Ordered[Alpha], Data any] struct {
	// contains filtered or unexported fields
}

func New

func New[Alpha Ordered[Alpha], Data any]() *SetTrie[Alpha, Data]

func (*SetTrie[Alpha, Data]) CreateOrUpdate

func (trie *SetTrie[Alpha, Data]) CreateOrUpdate(
	word Word[Alpha],
	initNode func() Data,
	updateNode func(*Data),
)

func (*SetTrie[Alpha, Data]) Get

func (trie *SetTrie[Alpha, Data]) Get(word Word[Alpha]) optional.Optional[Data]

func (*SetTrie[Alpha, Data]) RetainOrDrop

func (trie *SetTrie[Alpha, Data]) RetainOrDrop(
	word Word[Alpha],
	process func(Data) optional.Optional[Data],
)

func (*SetTrie[Alpha, Data]) Subsets

func (trie *SetTrie[Alpha, Data]) Subsets(
	word Word[Alpha],
) iter.Iter[iter.Pair[Word[Alpha], Data]]

func (*SetTrie[Alpha, Data]) Supersets

func (trie *SetTrie[Alpha, Data]) Supersets(
	word Word[Alpha],
) iter.Iter[iter.Pair[Word[Alpha], Data]]

Supersets is currently unused as it is very inefficient for tries with many children under the same node.

type Word

type Word[Alpha any] struct {
	// contains filtered or unexported fields
}

func NewWord

func NewWord[Alpha Ordered[Alpha]](unsorted []Alpha) Word[Alpha]

Creates a new word from an unsorted slice. The input slice is not mutated nor leaked.

func (Word[Alpha]) Append

func (word Word[Alpha]) Append(alpha Alpha) Word[Alpha]

Non-mutating function that might mutate underlying shared capacity beyond length, similar to append().

func (*Word[Alpha]) PopFirst

func (word *Word[Alpha]) PopFirst() (Alpha, bool)

func (Word[Alpha]) Sorted

func (word Word[Alpha]) Sorted() []Alpha