Options
All
  • Public
  • Public/Protected
  • All
Menu

Class RadixTree<T>

The RadixTree class

Type parameters

  • T

Hierarchy

  • RadixTree

Index

Constructors

Properties

Methods

Constructors

constructor

  • new RadixTree(kvpairs?: Array<[string, T]>): RadixTree

  • Create a new RadixTree.

    Parameters

    • Optional kvpairs: Array<[string, T]>

      the [key, value] pairs with which to initialize the radix tree

    Returns RadixTree

Properties

root

root: RadixNode<T>

Methods

delete

  • delete(k: string): boolean

  • Delete the k,v pair for the given key k from the radix tree.

    Parameters

    • k: string

      the key to delete from the radix tree

    Returns boolean

    true if success, false if k not found

get

  • get(k: string, allNodes?: boolean): KeyMatch<T> | undefined

  • Return the value associated to a key in the RadixTree.

    Parameters

    • k: string

      the key to look for. must have length > 0

    • Optional allNodes: boolean

    Returns KeyMatch<T> | undefined

    the keyMatch for the given key k. if k not found, return undefined

getAll

  • getAll(prefix: string, config?: { allNodes?: boolean; pruner?: Pruner<T>; searchType?: SearchType }): IterableIterator<KeyMatch<T>>

  • Get the KeyMatch object for every [k,v] pair where k.startsWith(prefix).

    generator
    yields

    the KeyMatch object for each key in the RadixTree that starts with prefix

    desc

    Note: the depth property of the KeyMatch is relative to the searchRoot of the given prefix.

    Parameters

    • prefix: string

      only return KeyMatch for keys k where k.startsWith(prefix)

    • Default value config: { allNodes?: boolean; pruner?: Pruner<T>; searchType?: SearchType } = {}

      configuration for behavior of this function

      • Optional allNodes?: boolean

        include keyMatch objects for all nodes, not just those having values

      • Optional pruner?: Pruner<T>

        prune nodes from traversal

      • Optional searchType?: SearchType

        the type of tree traversal to do, must be in constants.SEARCH_TYPES

    Returns IterableIterator<KeyMatch<T>>

getSearchRoot

  • For a given prefix, find the shallowest node in the radix tree whose key either matches the prefix exactly or is the shortest matching key that is longer than the prefix.

    For example, if "ab" and "abcd" are inserted into the radix tree, the search root of the prefix "abc" would be the node matching "abcd". The "abcd" node would be the root of the subtree containing all nodes whose keys start with "abc", since there were no other keys that start with "abc" other than "abcd" and its children.

    Parameters

    • prefix: string

      the prefix for which to find the searchRoot

    Returns SearchRootMatch<T> | undefined

    the SearchRootMatch if one is found

set

  • set(k: string, v: T): void

  • Add a [key, value] pair to the RadixTree.

    Parameters

    • k: string

      the key to insert into the radix tree. must have length > 0

    • v: T

      the value to associate to the key in the radix tree

    Returns void

Generated using TypeDoc