IntervalSearchTree

public struct IntervalSearchTree<Metric, Value> where Metric : Comparable

An IntervalSearchTree is an augmentatin of an AVLTree, wherein the the value of Node is an IntervalSearchTree.Node. An IntervalSearchTree.Node contains the interval indexing the payload, the max upper bound of subtrees, and the payload value itself.

Todo

Push down to dn-m/Structure/DataStructures when fully vetted.

  • Underlying AVLTree augmented for interval searching purposes.

    Declaration

    Swift

    public typealias Base = AVLTree<Metric, Node>

  • Undocumented

    See more

    Declaration

    Swift

    public struct Node

Initializers

  • Creates an empty IntervalSearchTree.

    Declaration

    Swift

    public init()

  • Creates an IntervalSearchTree with the given sequence of Payload values.

    Declaration

    Swift

    @inlinable
public init<S>(_ sequence: S) where S : Sequence, S.Element == IntervalSearchTree<Metric, Value>.Node

  • Undocumented

    Declaration

    Swift

    public static var empty: IntervalSearchTree { get }

  • Declaration

    Swift

    public subscript(interval: Range<Metric>) -> IntervalSearchTree { get }

    Return Value

    An IntervalSearchTree composed of the nodes overlapping the given interval.

Instance Methods

  • Declaration

    Swift

    @inlinable
public func containing(_ target: Metric) -> [Node]

    Return Value

    An array of payloads containing the fractional interval and associated values containing the given target offset.

  • Undocumented

    Declaration

    Swift

    @inlinable
public func overlapping(_ target: Range<Metric>) -> [Node]

  • Inserts the given payload, storing the payload by the lower bound of its interval.

    Declaration

    Swift

    @inlinable
public mutating func insert(_ payload: Node)

  • Undocumented

    Declaration

    Swift

    @inlinable
public func overlapping(_ target: Range<Metric>) -> [Node]