tree

package
v1.2.3 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Sep 21, 2023 License: Apache-2.0 Imports: 8 Imported by: 1

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func AddedNodesTreeString added in v1.2.0 

func AddedNodesTreeString[E TrieKey[E], V any](addedTree *BinTrieNode[E, AddedSubnodeMapping]) string

AddedNodesTreeString provides a flattened version of the trie showing only the contained added nodes and their containment structure, which is non-binary. The root node is included, which may or may not be added.

func BlockSizeCompare 

func BlockSizeCompare[E TrieKey[E]](key1, key2 E, reverseBlocksEqualSize bool) int

BlockSizeCompare compares keys by block size and then by prefix value if block sizes are equal

func NodeString added in v1.2.0 

func NodeString[E Key, V any](node nodePrinter[E, V]) string

NodeString returns a visual representation of the given node including the key, with an open circle indicating this node is not an added node, a closed circle indicating this node is an added node.

func TreesString 

func TreesString[E TrieKey[E], V any](withNonAddedKeys bool, tries ...*BinTrie[E, V]) string

func TrieDecrement 

func TrieDecrement[E TrieKey[E]](key E) (next E, hasNext bool)

TrieDecrement returns the previous key according to the trie ordering The zero value is returned when there is no previous key.

func TrieIncrement 

func TrieIncrement[E TrieKey[E]](key E) (next E, hasNext bool)

TrieIncrement returns the next key according to the trie ordering. The zero value is returned when there is no next key.

Types

type AddedSubnodeMapping added in v1.2.0 

type AddedSubnodeMapping any // AddedSubnodeMapping / any is always SubNodesMapping[E,V]

type BinTrie 

type BinTrie[E TrieKey[E], V any] struct {
	// contains filtered or unexported fields
}

BinTrie is a binary trie.

To use BinTrie, your keys implement TrieKey.

All keys are either fixed, in which the key value does not change, or comprising of a prefix in which an initial sequence of bits does not change, and the the remaining bits represent all bit values. The length of the initial fixed sequence of bits is the prefix length. The total bit length is the same for all keys.

A key with a prefix is also known as a prefix block, and represents all bit sequences with the same prefix.

The zero value for BinTrie is a binary trie ready for use.

Each node can be associated with a value, making BinTrie an associative binary trie. If you do not wish to associate values to nodes, then use the type EmptyValueType, in which case the value will be ignored in functions that print node strings.

func NewBinTrie 

func NewBinTrie[E TrieKey[E], V any](key E) BinTrie[E, V]

NewBinTrie creates a new trie with root key.ToPrefixBlockLen(0). If the key argument is not Equal to its zero-length prefix block, then the key will be added as well.

func (*BinTrie[E, V]) Add 

func (trie *BinTrie[E, V]) Add(key E) bool

Add adds the given key to the trie, returning true if not there already.

func (*BinTrie[E, V]) AddNode 

func (trie *BinTrie[E, V]) AddNode(key E) *BinTrieNode[E, V]

AddNode is similar to Add but returns the new or existing node.

func (*BinTrie[E, V]) AddTrie 

func (trie *BinTrie[E, V]) AddTrie(trieNode *BinTrieNode[E, V]) *BinTrieNode[E, V]

func (*BinTrie[E, V]) AddedNodesTreeString 

func (trie *BinTrie[E, V]) AddedNodesTreeString() string

AddedNodesTreeString provides a flattened version of the trie showing only the contained added nodes and their containment structure, which is non-binary. The root node is included, which may or may not be added.

func (*BinTrie[E, V]) AllNodeIterator 

func (trie *BinTrie[E, V]) AllNodeIterator(forward bool) TrieNodeIteratorRem[E, V]

AllNodeIterator returns an iterator that iterates through all the nodes of the trie in forward or reverse tree order.

func (*BinTrie[E, V]) BlockSizeAllNodeIterator 

func (trie *BinTrie[E, V]) BlockSizeAllNodeIterator(lowerSubNodeFirst bool) TrieNodeIteratorRem[E, V]

BlockSizeAllNodeIterator returns an iterator that iterates all nodes in the trie, ordered by keys from largest prefix blocks to smallest, and then to individual addresses.

If lowerSubNodeFirst is true, for blocks of equal size the lower is first, otherwise the reverse order

func (*BinTrie[E, V]) BlockSizeCachingAllNodeIterator 

func (trie *BinTrie[E, V]) BlockSizeCachingAllNodeIterator() CachingTrieNodeIterator[E, V]

BlockSizeCachingAllNodeIterator returns an iterator that iterates all nodes, ordered by keys from largest prefix blocks to smallest, and then to individual addresses.

func (*BinTrie[E, V]) BlockSizeNodeIterator 

func (trie *BinTrie[E, V]) BlockSizeNodeIterator(lowerSubNodeFirst bool) TrieNodeIteratorRem[E, V]

BlockSizeNodeIterator returns an iterator that iterates the added nodes in the trie, ordered by keys from largest prefix blocks to smallest, and then to individual addresses.

If lowerSubNodeFirst is true, for blocks of equal size the lower is first, otherwise the reverse order

func (*BinTrie[E, V]) CeilingAddedNode 

func (trie *BinTrie[E, V]) CeilingAddedNode(key E) *BinTrieNode[E, V]

func (*BinTrie) Clear 

func (tree *BinTrie) Clear()

Clear removes all added nodes from the tree, after which IsEmpty() will return true

func (*BinTrie[E, V]) Clone 

func (trie *BinTrie[E, V]) Clone() *BinTrie[E, V]

func (*BinTrie[E, V]) ConstructAddedNodesTree 

func (trie *BinTrie[E, V]) ConstructAddedNodesTree() BinTrie[E, AddedSubnodeMapping]

ConstructAddedNodesTree provides an associative trie in which the root and each added node of this trie are mapped to a list of their respective direct added sub-nodes. This trie provides an alternative non-binary tree structure of the added nodes. It is used by ToAddedNodesTreeString to produce a string showing the alternative structure. If there are no non-added nodes in this trie, then the alternative tree structure provided by this method is the same as the original trie. The trie values of this trie are of type []*BinTrieNode

func (*BinTrie[E, V]) ContainedFirstAllNodeIterator 

func (trie *BinTrie[E, V]) ContainedFirstAllNodeIterator(forwardSubNodeOrder bool) TrieNodeIterator[E, V]

func (*BinTrie[E, V]) ContainedFirstIterator 

func (trie *BinTrie[E, V]) ContainedFirstIterator(forwardSubNodeOrder bool) TrieNodeIteratorRem[E, V]

func (*BinTrie[E, V]) ContainingFirstAllNodeIterator 

func (trie *BinTrie[E, V]) ContainingFirstAllNodeIterator(forwardSubNodeOrder bool) CachingTrieNodeIterator[E, V]

func (*BinTrie[E, V]) ContainingFirstIterator 

func (trie *BinTrie[E, V]) ContainingFirstIterator(forwardSubNodeOrder bool) CachingTrieNodeIterator[E, V]

func (*BinTrie[E, V]) Contains 

func (trie *BinTrie[E, V]) Contains(key E) bool

func (*BinTrie[E, V]) DeepEqual 

func (trie *BinTrie[E, V]) DeepEqual(other *BinTrie[E, V]) bool

DeepEqual returns whether the given argument is a trie with a set of nodes with the same keys as in this trie according to the Compare method, and the same values according to the reflect.DeepEqual method

func (*BinTrie[E, V]) DescendingIterator 

func (trie *BinTrie[E, V]) DescendingIterator() TrieKeyIterator[E]

DescendingIterator returns an iterator that iterates through the elements of the subtrie with this node as the root. The iteration is in reverse sorted element order.

func (*BinTrie[E, V]) ElementContains 

func (trie *BinTrie[E, V]) ElementContains(key E) bool

func (*BinTrie[E, V]) ElementsContainedBy 

func (trie *BinTrie[E, V]) ElementsContainedBy(key E) *BinTrieNode[E, V]

func (*BinTrie[E, V]) ElementsContaining 

func (trie *BinTrie[E, V]) ElementsContaining(key E) *Path[E, V]

func (*BinTrie[E, V]) Equal 

func (trie *BinTrie[E, V]) Equal(other *BinTrie[E, V]) bool

Equal returns whether the given argument is a trie with a set of nodes with the same keys as in this trie according to the Compare method

func (*BinTrie[E, V]) FirstAddedNode 

func (trie *BinTrie[E, V]) FirstAddedNode() *BinTrieNode[E, V]

func (*BinTrie[E, V]) FirstNode 

func (trie *BinTrie[E, V]) FirstNode() *BinTrieNode[E, V]

func (*BinTrie[E, V]) FloorAddedNode 

func (trie *BinTrie[E, V]) FloorAddedNode(key E) *BinTrieNode[E, V]

func (BinTrie[E, V]) Format 

func (trie BinTrie[E, V]) Format(state fmt.State, verb rune)

Format implements the fmt.Formatter interface

func (*BinTrie[E, V]) Get 

func (trie *BinTrie[E, V]) Get(key E) (V, bool)

func (*BinTrie[E, V]) GetAddedNode 

func (trie *BinTrie[E, V]) GetAddedNode(key E) *BinTrieNode[E, V]

GetAddedNode gets trie nodes representing added elements.

Use Contains to check for the existence of a given address in the trie, as well as GetNode to search for all nodes including those not-added but also auto-generated nodes for subnet blocks.

func (*BinTrie[E, V]) GetNode 

func (trie *BinTrie[E, V]) GetNode(key E) *BinTrieNode[E, V]

GetNode gets the node in the sub-trie corresponding to the given address, or returns nil if not such element exists.

It returns any node, whether added or not, including any prefix block node that was not added.

func (*BinTrie[E, V]) GetRoot 

func (trie *BinTrie[E, V]) GetRoot() (root *BinTrieNode[E, V])

GetRoot returns the root of this trie (in the case of bounded tries, this would be the bounded root)

func (*BinTrie[E, V]) HigherAddedNode 

func (trie *BinTrie[E, V]) HigherAddedNode(key E) *BinTrieNode[E, V]

func (*BinTrie) IsEmpty 

func (tree *BinTrie) IsEmpty() bool

IsEmpty returns true if there are not any added nodes within this tree

func (*BinTrie[E, V]) Iterator 

func (trie *BinTrie[E, V]) Iterator() TrieKeyIterator[E]

Iterator returns an iterator that iterates through the elements of the sub-tree with this node as the root. The iteration is in sorted element order.

func (*BinTrie[E, V]) LastAddedNode 

func (trie *BinTrie[E, V]) LastAddedNode() *BinTrieNode[E, V]

func (*BinTrie[E, V]) LastNode 

func (trie *BinTrie[E, V]) LastNode() *BinTrieNode[E, V]

func (*BinTrie[E, V]) LongestPrefixMatch 

func (trie *BinTrie[E, V]) LongestPrefixMatch(key E) (E, bool)

LongestPrefixMatch finds the added key with the longest matching prefix.

func (*BinTrie[E, V]) LongestPrefixMatchNode 

func (trie *BinTrie[E, V]) LongestPrefixMatchNode(key E) *BinTrieNode[E, V]

LongestPrefixMatchNode finds the added node with the longest matching prefix.

func (*BinTrie[E, V]) LowerAddedNode 

func (trie *BinTrie[E, V]) LowerAddedNode(key E) *BinTrieNode[E, V]

func (*BinTrie[E, V]) NodeIterator 

func (trie *BinTrie[E, V]) NodeIterator(forward bool) TrieNodeIteratorRem[E, V]

NodeIterator returns an iterator that iterates through the added nodes of the trie in forward or reverse tree order.

func (*BinTrie[E, V]) NodeSize 

func (trie *BinTrie[E, V]) NodeSize() int

NodeSize returns the number of nodes in the tree, which is always more than the number of elements.

func (*BinTrie[E, V]) Put 

func (trie *BinTrie[E, V]) Put(key E, value V) (V, bool)

Put associates the specified value with the specified key in this map.

If the argument is not a single address nor prefix block, this method will panic. The Partition type can be used to convert the argument to single addresses and prefix blocks before calling this method.

If this map previously contained a mapping for a key, the old value is replaced by the specified value, and false is returned along with the old value, which may be the zero value. If this map did not previously contain a mapping for the key, true is returned along with the zero value.

func (*BinTrie[E, V]) PutNode 

func (trie *BinTrie[E, V]) PutNode(key E, value V) *BinTrieNode[E, V]

func (*BinTrie[E, V]) PutTrie 

func (trie *BinTrie[E, V]) PutTrie(trieNode *BinTrieNode[E, V]) *BinTrieNode[E, V]

func (*BinTrie[E, V]) Remap 

func (trie *BinTrie[E, V]) Remap(key E, remapper func(existing V, found bool) (mapped V, mapIt bool)) *BinTrieNode[E, V]

func (*BinTrie[E, V]) RemapIfAbsent 

func (trie *BinTrie[E, V]) RemapIfAbsent(key E, supplier func() V) *BinTrieNode[E, V]

func (*BinTrie[E, V]) Remove 

func (trie *BinTrie[E, V]) Remove(key E) bool

func (*BinTrie[E, V]) RemoveElementsContainedBy 

func (trie *BinTrie[E, V]) RemoveElementsContainedBy(key E) *BinTrieNode[E, V]

func (*BinTrie[E, V]) ShortestPrefixMatch added in v1.2.3 

func (trie *BinTrie[E, V]) ShortestPrefixMatch(key E) (E, bool)

ShortestPrefixMatch finds the added key with the shortest matching prefix.

func (*BinTrie[E, V]) ShortestPrefixMatchNode added in v1.2.3 

func (trie *BinTrie[E, V]) ShortestPrefixMatchNode(key E) *BinTrieNode[E, V]

ShortestPrefixMatchNode finds the added node whose key has the shortest matching prefix.

func (*BinTrie[E, V]) Size 

func (trie *BinTrie[E, V]) Size() int

Size returns the number of elements in the tree. Only nodes for which IsAdded() returns true are counted. When zero is returned, IsEmpty() returns true.

func (*BinTrie[E, V]) String 

func (trie *BinTrie[E, V]) String() string

String returns a visual representation of the tree with one node per line.

func (*BinTrie[E, V]) TreeString 

func (trie *BinTrie[E, V]) TreeString(withNonAddedKeys bool) string

TreeString returns a visual representation of the tree with one node per line, with or without the non-added keys.

type BinTrieNode 

type BinTrieNode[E TrieKey[E], V any] struct {
	// contains filtered or unexported fields
}

func AddTrieKeys added in v1.2.0 

func AddTrieKeys[E TrieKey[E], V1 any, V2 any](trie *BinTrie[E, V1], addedTreeNode *BinTrieNode[E, V2]) *BinTrieNode[E, V1]

AddTrieKeys copies the trie node structure of addedTrie into trie, but does not copy node mapped values

func (*BinTrieNode[E, V]) AllNodeIterator 

func (node *BinTrieNode[E, V]) AllNodeIterator(forward bool) TrieNodeIteratorRem[E, V]

AllNodeIterator returns an iterator that iterates through all the nodes of the sub-tree with this node as the root, in forward or reverse tree order.

func (*BinTrieNode[E, V]) AsNewTrie 

func (node *BinTrieNode[E, V]) AsNewTrie() *BinTrie[E, V]

AsNewTrie creates a new sub-trie, copying the nodes starting with this node as root. The nodes are copies of the nodes in this sub-trie, but their keys and values are not copies.

func (*BinTrieNode[E, V]) BlockSizeAllNodeIterator 

func (node *BinTrieNode[E, V]) BlockSizeAllNodeIterator(lowerSubNodeFirst bool) TrieNodeIteratorRem[E, V]

BlockSizeAllNodeIterator returns an iterator that iterates all the nodes, ordered by keys from largest prefix blocks to smallest and then to individual addresses, in the sub-trie with this node as the root.

If lowerSubNodeFirst is true, for blocks of equal size the lower is first, otherwise the reverse order

func (*BinTrieNode[E, V]) BlockSizeCachingAllNodeIterator 

func (node *BinTrieNode[E, V]) BlockSizeCachingAllNodeIterator() CachingTrieNodeIterator[E, V]

BlockSizeCachingAllNodeIterator returns an iterator of all nodes, ordered by keys from largest prefix blocks to smallest and then to individual addresses, in the sub-trie with this node as the root.

This iterator allows you to cache an object with subnodes so that when those nodes are visited the cached object can be retrieved.

func (*BinTrieNode[E, V]) BlockSizeNodeIterator 

func (node *BinTrieNode[E, V]) BlockSizeNodeIterator(lowerSubNodeFirst bool) TrieNodeIteratorRem[E, V]

BlockSizeNodeIterator returns an iterator that iterates the added nodes, ordered by keys from largest prefix blocks (smallest prefix length) to smallest (largest prefix length) and then to individual addresses, in the sub-trie with this node as the root.

If lowerSubNodeFirst is true, for blocks of equal size the lower is first, otherwise the reverse order is taken.

func (*BinTrieNode[E, V]) CeilingAddedNode 

func (node *BinTrieNode[E, V]) CeilingAddedNode(key E) *BinTrieNode[E, V]

func (*BinTrieNode[E, V]) Clear 

func (node *BinTrieNode[E, V]) Clear()

Clear removes this node and all sub-nodes from the tree, after which isEmpty() will return true.

func (*BinTrieNode[E, V]) ClearValue 

func (node *BinTrieNode[E, V]) ClearValue()

func (*BinTrieNode[E, V]) Clone 

func (node *BinTrieNode[E, V]) Clone() *BinTrieNode[E, V]

Clone clones the node. Keys remain the same, but the parent node and the lower and upper sub-nodes are all set to nil.

func (*BinTrieNode[E, V]) CloneTree 

func (node *BinTrieNode[E, V]) CloneTree() *BinTrieNode[E, V]

CloneTree clones the sub-tree starting with this node as root. The nodes are cloned, but their keys and values are not cloned.

func (*BinTrieNode[E, V]) Compare 

func (node *BinTrieNode[E, V]) Compare(other *BinTrieNode[E, V]) int

Compare returns -1, 0 or 1 if this node is less than, equal, or greater than the other, according to the key and the trie order.

func (*BinTrieNode[E, V]) ContainedFirstAllNodeIterator 

func (node *BinTrieNode[E, V]) ContainedFirstAllNodeIterator(forwardSubNodeOrder bool) TrieNodeIterator[E, V]

func (*BinTrieNode[E, V]) ContainedFirstIterator 

func (node *BinTrieNode[E, V]) ContainedFirstIterator(forwardSubNodeOrder bool) TrieNodeIteratorRem[E, V]

func (*BinTrieNode[E, V]) ContainingFirstAllNodeIterator 

func (node *BinTrieNode[E, V]) ContainingFirstAllNodeIterator(forwardSubNodeOrder bool) CachingTrieNodeIterator[E, V]

func (*BinTrieNode[E, V]) ContainingFirstIterator 

func (node *BinTrieNode[E, V]) ContainingFirstIterator(forwardSubNodeOrder bool) CachingTrieNodeIterator[E, V]

func (*BinTrieNode[E, V]) Contains 

func (node *BinTrieNode[E, V]) Contains(addr E) bool

func (*BinTrieNode[E, V]) DeepEqual 

func (node *BinTrieNode[E, V]) DeepEqual(other *BinTrieNode[E, V]) bool

DeepEqual returns whether the key matches the key of the given node using Compare, and whether the value matches the other value using reflect.DeepEqual

func (*BinTrieNode[E, V]) DescendingIterator 

func (node *BinTrieNode[E, V]) DescendingIterator() TrieKeyIterator[E]

DescendingIterator returns an iterator that iterates through the elements of the subtrie with this node as the root. The iteration is in reverse sorted element order.

func (*BinTrieNode[E, V]) ElementContains 

func (node *BinTrieNode[E, V]) ElementContains(key E) bool

func (*BinTrieNode[E, V]) ElementsContainedBy 

func (node *BinTrieNode[E, V]) ElementsContainedBy(key E) *BinTrieNode[E, V]

func (*BinTrieNode[E, V]) ElementsContaining 

func (node *BinTrieNode[E, V]) ElementsContaining(key E) *Path[E, V]

ElementsContaining finds the trie nodes containing the given key and returns them as a linked list only added nodes are added to the linked list

func (*BinTrieNode[E, V]) Equal 

func (node *BinTrieNode[E, V]) Equal(other *BinTrieNode[E, V]) bool

Equal returns whether the key matches the key of the given node

func (*BinTrieNode[E, V]) FirstAddedNode 

func (node *BinTrieNode[E, V]) FirstAddedNode() *BinTrieNode[E, V]

func (*BinTrieNode[E, V]) FirstNode 

func (node *BinTrieNode[E, V]) FirstNode() *BinTrieNode[E, V]

func (*BinTrieNode[E, V]) FloorAddedNode 

func (node *BinTrieNode[E, V]) FloorAddedNode(key E) *BinTrieNode[E, V]

func (BinTrieNode[E, V]) Format 

func (node BinTrieNode[E, V]) Format(state fmt.State, verb rune)

Format implements the fmt.Formatter interface

func (*BinTrieNode[E, V]) Get 

func (node *BinTrieNode[E, V]) Get(key E) (V, bool)

func (*BinTrieNode[E, V]) GetAddedNode 

func (node *BinTrieNode[E, V]) GetAddedNode(key E) *BinTrieNode[E, V]

GetAddedNode gets trie nodes representing added elements.

Use Contains to check for the existence of a given address in the trie, as well as GetNode to search for all nodes including those not-added but also auto-generated nodes for subnet blocks.

func (*BinTrieNode[E, V]) GetKey 

func (node *BinTrieNode[E, V]) GetKey() E

GetKey gets the key used for placing the node in the tree.

func (*BinTrieNode[E, V]) GetLowerSubNode 

func (node *BinTrieNode[E, V]) GetLowerSubNode() *BinTrieNode[E, V]

GetLowerSubNode gets the direct child node whose key is smallest in value

func (*BinTrieNode[E, V]) GetNode 

func (node *BinTrieNode[E, V]) GetNode(key E) *BinTrieNode[E, V]

GetNode gets the node in the trie corresponding to the given address, or returns nil if not such element exists.

It returns any node, whether added or not, including any prefix block node that was not added.

func (*BinTrieNode[E, V]) GetParent 

func (node *BinTrieNode[E, V]) GetParent() *BinTrieNode[E, V]

GetParent gets the node from which this node is a direct child node, or nil if this is the root.

func (*BinTrieNode[E, V]) GetUpperSubNode 

func (node *BinTrieNode[E, V]) GetUpperSubNode() *BinTrieNode[E, V]

GetUpperSubNode gets the direct child node whose key is largest in value

func (*BinTrieNode[E, V]) GetValue 

func (node *BinTrieNode[E, V]) GetValue() (val V)

func (*BinTrieNode[E, V]) HigherAddedNode 

func (node *BinTrieNode[E, V]) HigherAddedNode(key E) *BinTrieNode[E, V]

func (*BinTrieNode[E, V]) IsAdded 

func (node *BinTrieNode[E, V]) IsAdded() bool

IsAdded returns whether the node was "added". Some binary tree nodes are considered "added" and others are not. Those nodes created for key elements added to the tree are "added" nodes. Those that are not added are those nodes created to serve as junctions for the added nodes. Only added elements contribute to the size of a tree. When removing nodes, non-added nodes are removed automatically whenever they are no longer needed, which is when an added node has less than two added sub-nodes.

func (*BinTrieNode[E, V]) IsEmpty 

func (node *BinTrieNode[E, V]) IsEmpty() bool

IsEmpty returns where there are not any elements in the sub-tree with this node as the root.

func (*BinTrieNode[E, V]) IsLeaf 

func (node *BinTrieNode[E, V]) IsLeaf() bool

IsLeaf returns whether this node is in the tree (a node for which IsAdded() is true) and there are no elements in the sub-tree with this node as the root.

func (*BinTrieNode[E, V]) IsRoot 

func (node *BinTrieNode[E, V]) IsRoot() bool

IsRoot returns whether this is the root of the backing tree.

func (*BinTrieNode[E, V]) Iterator 

func (node *BinTrieNode[E, V]) Iterator() TrieKeyIterator[E]

Iterator returns an iterator that iterates through the elements of the sub-tree with this node as the root. The iteration is in sorted element order.

func (*BinTrieNode[E, V]) LastAddedNode 

func (node *BinTrieNode[E, V]) LastAddedNode() *BinTrieNode[E, V]

func (*BinTrieNode[E, V]) LastNode 

func (node *BinTrieNode[E, V]) LastNode() *BinTrieNode[E, V]

func (*BinTrieNode[E, V]) LongestPrefixMatch 

func (node *BinTrieNode[E, V]) LongestPrefixMatch(key E) (E, bool)

LongestPrefixMatch finds the longest matching prefix amongst keys added to the trie

func (*BinTrieNode[E, V]) LongestPrefixMatchNode 

func (node *BinTrieNode[E, V]) LongestPrefixMatchNode(key E) *BinTrieNode[E, V]

LongestPrefixMatchNode finds the node with the longest matching prefix. Only added nodes are considered.

func (*BinTrieNode[E, V]) LowerAddedNode 

func (node *BinTrieNode[E, V]) LowerAddedNode(key E) *BinTrieNode[E, V]

func (*BinTrieNode[E, V]) NextAddedNode 

func (node *BinTrieNode[E, V]) NextAddedNode() *BinTrieNode[E, V]

NextAddedNode returns the next node in the tree that is an added node, following the tree order, or nil if there is no such node.

func (*BinTrieNode[E, V]) NextNode 

func (node *BinTrieNode[E, V]) NextNode() *BinTrieNode[E, V]

NextNode returns the node that follows this node following the tree order

func (*BinTrieNode[E, V]) NodeIterator 

func (node *BinTrieNode[E, V]) NodeIterator(forward bool) TrieNodeIteratorRem[E, V]

NodeIterator returns an iterator that iterates through the added nodes of the sub-tree with this node as the root, in forward or reverse tree order.

func (*BinTrieNode[E, V]) NodeSize 

func (node *BinTrieNode[E, V]) NodeSize() int

NodeSize returns the count of all nodes in the tree starting from this node and extending to all sub-nodes. Unlike for the Size method, this is not a constant-time operation and must visit all sub-nodes of this node.

func (*BinTrieNode[E, V]) PreviousAddedNode 

func (node *BinTrieNode[E, V]) PreviousAddedNode() *BinTrieNode[E, V]

PreviousAddedNode returns the previous node in the tree that is an added node, following the tree order in reverse, or nil if there is no such node.

func (*BinTrieNode[E, V]) PreviousNode 

func (node *BinTrieNode[E, V]) PreviousNode() *BinTrieNode[E, V]

PreviousNode returns the node that precedes this node following the tree order.

func (*BinTrieNode[E, V]) Remove 

func (node *BinTrieNode[E, V]) Remove()

Remove removes this node from the collection of added nodes, and also removes from the tree if possible. If it has two sub-nodes, it cannot be removed from the tree, in which case it is marked as not "added", nor is it counted in the tree size. Only added nodes can be removed from the tree. If this node is not added, this method does nothing.

func (*BinTrieNode[E, V]) RemoveElementsContainedBy 

func (node *BinTrieNode[E, V]) RemoveElementsContainedBy(key E) *BinTrieNode[E, V]

func (*BinTrieNode[E, V]) RemoveNode 

func (node *BinTrieNode[E, V]) RemoveNode(key E) bool

func (*BinTrieNode) SetAdded 

func (node *BinTrieNode) SetAdded()

SetAdded makes this node an added node, which is equivalent to adding the corresponding key to the tree. If the node is already an added node, this method has no effect. You cannot set an added node to non-added, for that you should Remove the node from the tree by calling Remove. A non-added node will only remain in the tree if it needs to in the tree.

func (*BinTrieNode) SetValue 

func (node *BinTrieNode) SetValue(val V)

SetValue assigns a value to the node, overwriting any previous value

func (*BinTrieNode[E, V]) ShortestPrefixMatch added in v1.2.3 

func (node *BinTrieNode[E, V]) ShortestPrefixMatch(key E) (E, bool)

ShortestPrefixMatch finds the shortest matching prefix amongst keys added to the trie. Only added nodes are considered. It is quicker than LongestPrefixMatch in that once it finds the first containing node, the look-up is done.

func (*BinTrieNode[E, V]) ShortestPrefixMatchNode added in v1.2.3 

func (node *BinTrieNode[E, V]) ShortestPrefixMatchNode(key E) *BinTrieNode[E, V]

func (*BinTrieNode[E, V]) Size 

func (node *BinTrieNode[E, V]) Size() int

Size returns the count of nodes added to the sub-tree starting from this node as root and moving downwards to sub-nodes. This is a constant-time operation since the size is maintained in each node and adjusted with each add and Remove operation in the sub-tree.

func (*BinTrieNode[E, V]) String 

func (node *BinTrieNode[E, V]) String() string

Returns a visual representation of this node including the key, with an open circle indicating this node is not an added node, a closed circle indicating this node is an added node.

func (*BinTrieNode[E, V]) TreeDeepEqual 

func (node *BinTrieNode[E, V]) TreeDeepEqual(other *BinTrieNode[E, V]) bool

TreeDeepEqual returns whether the sub-tree represented by this node as the root node matches the given sub-tree, matching the nodes using DeepEqual

func (*BinTrieNode[E, V]) TreeEqual 

func (node *BinTrieNode[E, V]) TreeEqual(other *BinTrieNode[E, V]) bool

TreeEqual returns whether the sub-tree represented by this node as the root node matches the given sub-tree, matching the trie keys using the Compare method

func (*BinTrieNode[E, V]) TreeString 

func (node *BinTrieNode[E, V]) TreeString(withNonAddedKeys, withSizes bool) string

TreeString returns a visual representation of the sub-tree with this node as root, with one node per line.

withNonAddedKeys: whether to show nodes that are not added nodes withSizes: whether to include the counts of added nodes in each sub-tree

type BitCount 

type BitCount = int // using signed integers allows for easier arithmetic

A BitCount represents a count of bits in an address, section, grouping, segment, or division. Using signed integers allows for easier arithmetic, avoiding bugs. However, all methods adjust bit counts to match address size, so negative bit counts or bit counts larger than address size are meaningless.

type C 

type C any

C represents cached values in iterators

type CachingIterator 

type CachingIterator interface {
	// GetCached returns an object previously cached with the current iterated node.
	// After Next has returned a node,
	// if an object was cached by a call to CacheWithLowerSubNode or CacheWithUpperSubNode
	// was called when that node's parent was previously returned by Next,
	// then this returns that cached object.
	GetCached() C

	// CacheWithLowerSubNode caches an object with the lower sub-node of the current iterated node.
	// After Next has returned a node,
	// calling this method caches the provided object with the lower sub-node so that it can
	// be retrieved with GetCached when the lower sub-node is visited later.
	//
	// Returns false if it could not be cached, either because the node has since been removed with a call to Remove,
	// because Next has not been called yet, or because there is no lower sub node for the node previously returned by  Next.
	//
	// The caching and retrieval is done in constant time.
	CacheWithLowerSubNode(C) bool

	// CacheWithUpperSubNode caches an object with the upper sub-node of the current iterated node.
	// After Next has returned a node,
	// calling this method caches the provided object with the upper sub-node so that it can
	// be retrieved with GetCached when the upper sub-node is visited later.
	//
	// Returns false if it could not be cached, either because the node has since been removed with a call to Remove,
	// because Next has not been called yet, or because there is no upper sub node for the node previously returned by Next.
	//
	// The caching and retrieval is done in constant time.
	CacheWithUpperSubNode(C) bool
}

type CachingTrieNodeIterator 

type CachingTrieNodeIterator[E TrieKey[E], V any] interface {
	TrieNodeIteratorRem[E, V]
	CachingIterator
}

type EmptyValueType added in v1.2.0 

type EmptyValueType struct{}

type HasNext 

type HasNext interface {
	HasNext() bool
}

type Key added in v1.2.0 

type Key interface {
	comparable // needed by populateCacheItem
}

type KeyCompareResult 

type KeyCompareResult interface {
	// BitsMatch should be called when the existing key is the same size or large as the new key and the new key bits match the existing key bits.
	BitsMatch()

	// BitsMatchPartially should be called when the existing key is shorter than the new key and the existing key bits match the new key bits.
	// It returns true if further matching is required, which might eventually result in calls to BitsMatch or BitsDoNotMatch.
	BitsMatchPartially() bool

	// BitsDoNotMatch should be called when at least one bit in the new key does not match the same bit in the existing key.
	// You can skip calling it if a prior call to MismatchCallbackRequired returns true.
	BitsDoNotMatch(matchedBits BitCount)

	// MismatchCallbackRequired indicates if you need to call BitsDoNotMatch for a mismatch
	MismatchCallbackRequired() bool
}

KeyCompareResult has callbacks for a key comparison of a new key with a key pre-existing in the trie. At most one of the two methods should be called when comparing keys. If existing key is shorter, and the new key matches all bits in the existing key, then neither method should be called.

type Path added in v1.1.0 

type Path[E Key, V any] struct {
	// contains filtered or unexported fields
}

Path is a list of nodes derived from following a path in a tree. Each node in the list corresponds to a node in the tree. Each node in the list corresponds to a tree node that is a direct or indirect sub-node of the tree node corresponding to the previous node in the list. Not all nodes in the pathway through the tree need to be included in the linked list.

In other words, a path follows a pathway through a tree from root to leaf, but not necessarily including all nodes encountered along the way.

func (*Path[E, V]) GetLeaf added in v1.1.0 

func (path *Path[E, V]) GetLeaf() *PathNode[E, V]

GetLeaf returns the end of the Path, which may or may not match a leaf in the originating tree.

func (*Path[E, V]) GetRoot added in v1.1.0 

func (path *Path[E, V]) GetRoot() *PathNode[E, V]

GetRoot returns the beginning of the Path, which may or may not match the tree root of the originating tree.

func (*Path[E, V]) ListString added in v1.1.0 

func (path *Path[E, V]) ListString(withNonAddedKeys bool) string

ListString returns a visual representation of the tree with one node per line, with or without the non-added keys.

func (*Path[E, V]) Size added in v1.1.0 

func (path *Path[E, V]) Size() (storedSize int)

Size returns the count of nodes in the list This is a constant-time operation since the size is maintained in each node.

func (*Path[E, V]) String added in v1.1.0 

func (path *Path[E, V]) String() string

String returns a visual representation of the Path with one node per line.

type PathNode added in v1.1.0 

type PathNode[E Key, V any] struct {
	// contains filtered or unexported fields
}

PathNode is an element in the list of a Path

func (*PathNode[E, V]) GetKey added in v1.1.0 

func (node *PathNode[E, V]) GetKey() (key E)

GetKey gets the key used for placing the node in the tree.

func (*PathNode[E, V]) GetValue added in v1.1.0 

func (node *PathNode[E, V]) GetValue() (val V)

GetValue returns the value assigned to the node

func (*PathNode[E, V]) IsAdded added in v1.1.0 

func (node *PathNode[E, V]) IsAdded() bool

IsAdded returns whether the node was "added". Some binary tree nodes are considered "added" and others are not. Those nodes created for key elements added to the tree are "added" nodes. Those that are not added are those nodes created to serve as junctions for the added nodes. Only added elements contribute to the size of a tree. When removing nodes, non-added nodes are removed automatically whenever they are no longer needed, which is when an added node has less than two added sub-nodes.

func (*PathNode[E, V]) ListString added in v1.1.0 

func (node *PathNode[E, V]) ListString(withNonAddedKeys, withSizes bool) string

ListString returns a visual representation of the sub-list with this node as root, with one node per line.

withNonAddedKeys: whether to show nodes that are not added nodes withSizes: whether to include the counts of added nodes in each sub-list

func (*PathNode[E, V]) Next added in v1.1.0 

func (node *PathNode[E, V]) Next() *PathNode[E, V]

Next returns the next node in the path

func (*PathNode[E, V]) Previous added in v1.1.0 

func (node *PathNode[E, V]) Previous() *PathNode[E, V]

Previous returns the previous node in the path

func (*PathNode[E, V]) Size added in v1.1.0 

func (node *PathNode[E, V]) Size() (storedSize int)

Size returns the count of nodes added to the sub-tree starting from this node as root and moving downwards to sub-nodes. This is a constant-time operation since the size is maintained in each node.

func (*PathNode[E, V]) String added in v1.1.0 

func (node *PathNode[E, V]) String() string

Returns a visual representation of this node including the key, with an open circle indicating this node is not an added node, a closed circle indicating this node is an added node.

type PrefixBitCount 

type PrefixBitCount uint8

A PrefixBitCount is the count of bits in a non-nil PrefixLen.

func (*PrefixBitCount) Len 

func (p *PrefixBitCount) Len() BitCount

Len returns the length of the prefix. If the receiver is nil, representing the absence of a prefix length, returns 0. It will also return 0 if the receiver is a prefix with length of 0. To distinguish the two, compare the receiver with nil.

type PrefixLen 

type PrefixLen = *PrefixBitCount

A PrefixLen indicates the length of the prefix for an address, section, division grouping, segment, or division. The zero value, which is nil, indicates that there is no prefix length.

type SubNodesMapping added in v1.2.0 

type SubNodesMapping[E TrieKey[E], V any] struct {
	Value V

	// subNodes is the list of direct and indirect added subnodes in the original trie
	SubNodes []*BinTrieNode[E, AddedSubnodeMapping]
}

type TrieKey 

type TrieKey[E any] interface {
	comparable

	// MatchBits matches the bits in this key to the bits in the given key, starting from the given bit index.
	// Only the remaining bits in the prefix can be compared for either key.
	// If the prefix length of a key is nil, all the remaining bits can be compared.
	//
	// MatchBits returns false on a successful match or mismatch, and true if only a partial match, in which case further trie traversal is required.
	// In the case where continueToNext is true, followingBitsFlag is 0 if the single bit in the given key that follows the prefix length of this key is zero, and non-zero otherwise.
	//
	// MatchBits calls BitsMatch in handleMatch when the given key matches all the bits in this key (even if this key has a shorter prefix),
	// or calls BitsDoNotMatch in handleMatch when there is a mismatch of bits, returning true in both cases.
	//
	// If the given key has a shorter prefix length, so not all bits in this key can be compared to the given key,
	// but the bits that can be compared are a match, then that is a partial match.
	// MatchBits calls neither method in handleMatch and returns false in that case.
	MatchBits(key E, bitIndex BitCount, simpleMatch bool, handleMatch KeyCompareResult, trieKeyData *TrieKeyData) (continueToNext bool, followingBitsFlag uint64)

	// Compare returns a negative integer, zero, or a positive integer if this instance is less than, equal, or greater than the give item.
	// When comparing, the first mismatched bit determines the result.
	// If either key is prefixed, you compare only the bits up until the minumum prefix length.
	// If those bits are equal, and both have the same prefix length, they are equal.
	// Otherwise, the next bit in the key with the longer prefix (or no prefix at all) determines the result.
	// If that bit is 1, that key is larger, if it is 0, then smaller.
	Compare(E) int

	// GetBitCount returns the bit count for the key, which is a fixed value for any and all keys in the trie.
	GetBitCount() BitCount

	// GetPrefixLen returns the prefix length if this key has a prefix length (ie it is a prefix block).
	// It returns nil if not a prefix block.
	GetPrefixLen() PrefixLen

	// IsOneBit returns whether a given bit in the prefix is 1.
	// If the key is a prefix block, the operation is undefined if the bit index falls outside the prefix.
	// This method will never be called with a bit index that exceeds the prefix.
	IsOneBit(bitIndex BitCount) bool

	// ToPrefixBlockLen creates a new key with a prefix of the given length
	ToPrefixBlockLen(prefixLen BitCount) E

	// GetTrailingBitCount returns the number of trailing ones or zeros in the key.
	// If the key has a prefix length, GetTrailingBitCount is undefined.
	// This method will never be called on a key with a prefix length.
	GetTrailingBitCount(ones bool) BitCount

	// ToMaxLower returns a new key. If this key has a prefix length, it is converted to a key with a 0 as the first bit following the prefix, followed by all ones to the end, and with the prefix length then removed.
	// It returns this same key if it has no prefix length.
	// For instance, if this key is 1010**** with a prefix length of 4, the returned key is 10100111 with no prefix length.
	ToMaxLower() E

	// ToMinUpper returns a new key. If this key has a prefix length, it is converted to a key with a 1 as the first bit following the prefix, followed by all zeros to the end, and with the prefix length then removed.
	// It returns this same key if it has no prefix length.
	// For instance, if this key is 1010**** with a prefix length of 4, the returned key is 10101000 with no prefix length.
	ToMinUpper() E

	// GetTrieKeyData provides a condensed set of mask, prefix length, and values
	// from 32-bit and 128-bit keys for optimized search.
	// Implementing this method is optional, even for 32-bit and 128-bit keys, it can return nil.
	GetTrieKeyData() *TrieKeyData
}

TrieKey represents a key for a trie.

All trie keys represent a sequence of bits. The bit count, which is the same for all keys, is the total number of bits in the key.

Some trie keys represent a fixed sequence of bits. The bits have a single value.

The remaining trie keys have an initial sequence of bits, the prefix, within which the bits are fixed, and the remaining bits beyond the prefix are not fixed and represent all potential bit values. Such keys represent all values with the same prefix.

When all bits in a given key are fixed, the key has no prefix or prefix length.

When not all bits are fixed, the prefix length is the number of bits in the initial fixed sequence. A key with a prefix length is also known as a prefix block.

A key should never change. For keys with a prefix length, the prefix length must remain constance, and the prefix bits must remain constant. For keys with no prefix length, all the key bits must remain constant.

type TrieKeyData added in v1.2.3 

type TrieKeyData struct {
	Is32Bits, Is128Bits bool

	PrefLen PrefixLen

	// 32-bit fields
	Uint32Val, Mask32Val, NextBitMask32Val uint32

	// 128-bit fields
	Uint64HighVal,
	Uint64LowVal,
	Mask64HighVal,
	Mask64LowVal,
	NextBitMask64Val uint64
}

type TrieKeyIterator 

type TrieKeyIterator[E TrieKey[E]] interface {
	HasNext

	Next() E

	// Remove removes the last iterated element from the underlying trie, and returns that element.
	// If there is no such element, it returns the zero value.
	Remove() E
}

type TrieNodeIterator 

type TrieNodeIterator[E TrieKey[E], V any] interface {
	HasNext

	Next() *BinTrieNode[E, V]
}

type TrieNodeIteratorRem 

type TrieNodeIteratorRem[E TrieKey[E], V any] interface {
	TrieNodeIterator[E, V]

	// Remove removes the last iterated element from the underlying trie, and returns that element.
	// If there is no such element, it returns the zero value.
	Remove() *BinTrieNode[E, V]
}

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.