Options
All
  • Public
  • Public/Protected
  • All
Menu

Class DBstNode<T>

Type parameters

Hierarchy

Index

Constructors

Properties

Accessors

Methods

Constructors

constructor

  • new DBstNode(value?: number): DBstNode

Properties

Readonly equal_nodes

equal_nodes: T[] = []

Optional left_node

left_node: T

Optional parent_node

parent_node: T

Optional right_node

right_node: T

value

value: number

Accessors

absolute_value

  • get absolute_value(): number

  • The actual value of this node. The value member only stores the value relative to the parent node.

    Returns number

equal_parent

  • get equal_parent(): T

  • The highest parent of this node that has the same value or this node if there is no such node.

    Returns T

inorder_predecessor

  • get inorder_predecessor(): T

inorder_successor

  • get inorder_successor(): T

largest_child

  • get largest_child(): T

  • Finds the largest child of this node not including equal nodes.

    Returns T

largest_larger_child

  • get largest_larger_child(): T

  • Finds the largest child that is larger than this node not including equal nodes.

    Returns T

root

  • get root(): T

smallest_child

  • get smallest_child(): T

  • Finds the smallest child of this node not including equal nodes.

    Returns T

smallest_smaller_child

  • get smallest_smaller_child(): T

  • Finds the smallest child that is smaller than this node not including equal nodes.

    Returns T

Methods

addChild

  • addChild(node: T, rootUpdate?: (np: T) => void): void

  • Called by the BST only. DO NOT use. This is only public because JS has no concept of C++ friend classes and I need to use this function in unit tests. Call the add function on the BST object instead.

    Parameters

    • node: T

      The node to add

    • Default value rootUpdate: (np: T) => void = noRootUpdateFunction

      A function that will be called if the BST root needs to be updated. A TypeError will be thrown if one is not provided.

        • (np: T): void

        • Parameters

          • np: T

          Returns void

    Returns void

addSpaceBefore

  • addSpaceBefore(s: number, rootUpdate?: (np: T) => void): void

  • Applies an offset to the node's starting position. This will offset all nodes after this one efficiently. There's just one catch: This may not change the order of the BST. No errors will be thrown (or can, efficiently at least), so just make sure your code doesn't change the order. This will not mutate the BST unless the position of a node becomes equal to that of another node. In that case, the BST will be re-arranged so that the equal nodes form a linked list under the left side of the root equal node as required.

    Parameters

    • s: number

      The offset to apply to this node's start. This may be positive to add space before or negative to remove space before.

    • Default value rootUpdate: (np: T) => void = noRootUpdateFunction

      A function that will be called if the BST root needs to be updated. A TypeError will be thrown if one is not provided.

        • (np: T): void

        • Parameters

          • np: T

          Returns void

    Returns void

operateOnAll

  • operateOnAll(cb: (data: T) => void): void

  • Parameters

    • cb: (data: T) => void
        • (data: T): void

        • Parameters

          • data: T

          Returns void

    Returns void

predecessorIterator

  • predecessorIterator(): IterableIterator<T>

prefSearch

  • Searches the DBST based on the values of preferential_cmp only. Useful for searching for a node when its value is not known.

    todo

    More efficient searches of equal nodes

    Parameters

    Returns void

Abstract preferential_cmp

  • Order nodes that have the same value may be ordered differently using this function. This function must follow these rules:

    1. It must return values other than 0 if multiple nodes may have the same value in your implementation. Basically, if you ever have zero length nodes or nodes with the same position, you have to use this for things to not break.
    2. It must define the same order as if the nodes were ordered by value (with the exception of unorderable equal nodes).

    Parameters

    • other: T

    Returns CompareResult

remove

  • remove(rootUpdate?: (np: T) => void): void

  • Removes this node from the BST. The node's absolute_value will be preserved, so it can be directly re-added to the BST.

    Parameters

    • Optional rootUpdate: (np: T) => void

      This function is called if the bst_root of the BST must be updated. Normally, it should be given the value of (node) => (bst.bst_root = node). If no value is provided, an error will be thrown if an update is attempted. For this reason, if you expect that no root update will be required for whatever reason, do not provide a value. This will ensure that an error is thrown and a potential bug is caught.

        • (np: T): void

        • Parameters

          • np: T

          Returns void

    Returns void

removeChild

  • removeChild(value: number, filter?: (data: T) => boolean, vals?: T[], rootUpdate?: (np: T) => void): T[]

  • Parameters

    • value: number
    • Default value filter: (data: T) => boolean = (): boolean => true
        • (data: T): boolean

        • Parameters

          • data: T

          Returns boolean

    • Default value vals: T[] = []
    • Optional rootUpdate: (np: T) => void
        • (np: T): void

        • Parameters

          • np: T

          Returns void

    Returns T[]

replaceWith

  • replaceWith(data: T, rootUpdate?: (np: T) => void, value?: number): T

  • THIS IS NOT INTENDED FOR OUTSIDE USE! It is not protected for the unit tests that rely on it.

    Replaces this node with another node. This is used internally by the remove function. If the node provided has a parent, it will be removed from the parent. WARNING: If the provided node's current children conflict with the children of the destination node, the destination node's children have priority.

    Parameters

    • data: T

      New node

    • Default value rootUpdate: (np: T) => void = noRootUpdateFunction

      A function that will be called if the BST root needs to be updated. A TypeError will be thrown if one is not provided.

        • (np: T): void

        • Parameters

          • np: T

          Returns void

    • Default value value: number = data?.absolute_value

      The value to use for the new node. It defaults to the node's absolute_value.

    Returns T

search

  • Searches the DBST based on node value.

    Parameters

    Returns void

selfTest

  • selfTest(parent?: T, is_left?: boolean, mnv?: number, mxv?: number, known?: DBstNode<T>[]): void

  • Parameters

    • Optional parent: T
    • Optional is_left: boolean
    • Default value mnv: number = 0
    • Default value mxv: number = 0
    • Default value known: DBstNode<T>[] = []

    Returns void

selfTestEqual

  • selfTestEqual(parent?: T, known?: DBstNode<T>[]): void

  • Parameters

    • Optional parent: T
    • Default value known: DBstNode<T>[] = []

    Returns void

successorIterator

  • successorIterator(): IterableIterator<T>

toDeepString

  • toDeepString(): string

  • Creates a virtual tree showing right, left, and equal nodes. Very useful when debugging BST issues.

    Returns string

Generated using TypeDoc