interval

import "github.com/zyedidia/generic/interval"

Package interval provides an implementation of an interval tree built using an augmented AVL tree. An interval tree stores values associated with intervals, and can efficiently determine which intervals overlap with others. All intervals must have a unique starting position. It supports the following operations, where 'n' is the number of intervals in the tree: * Put: add an interval to the tree. Complexity: O(lg n). * Get: find an interval with a given starting position. Complexity O(lg n). * Overlaps: find all intervals that overlap with a given interval. Complexity: O(lg n + m), where 'm' is the size of the result (number of overlapping intervals found). * Remove: remove the interval at a given position. Complexity: O(lg n).

Index

• type KV
• type Tree
  • func NewV any *Tree[V]
  • func (t *Tree[V]) Get(pos int) (V, bool)
  • func (t *Tree[V]) GetZ(pos int) V
  • func (t *Tree[V]) Height() int
  • func (t *Tree[V]) Iter() iter.Iter[KV[V]]
  • func (t *Tree[V]) Overlaps(low, high int) []V
  • func (t *Tree[V]) Put(low, high int, value V)
  • func (t *Tree[V]) Remove(pos int)
  • func (t *Tree[V]) Size() int

type KV

type KV[V any] struct {
    Low, High int
    Val       V
}

type Tree

Tree implements an interval tree. All intervals must have unique starting positions.

type Tree[V any] struct {
    // contains filtered or unexported fields
}

func New

func New[V any]() *Tree[V]

New returns an empty interval tree.

func (*BADRECV) Get

func (t *Tree[V]) Get(pos int) (V, bool)

Get returns the value associated with the interval starting at 'pos', or 'false' if no such value exists.

func (*BADRECV) GetZ

func (t *Tree[V]) GetZ(pos int) V

GetZ is the same as Get but returns the zero value if nothing is found.

func (*BADRECV) Height

func (t *Tree[V]) Height() int

Height returns the height of the tree.

func (*BADRECV) Iter

func (t *Tree[V]) Iter() iter.Iter[KV[V]]

Iter returns the tree iterator.

func (*BADRECV) Overlaps

func (t *Tree[V]) Overlaps(low, high int) []V

Overlaps returns all values that overlap with the given range.

func (*BADRECV) Put

func (t *Tree[V]) Put(low, high int, value V)

Put associates the interval 'key' with 'value'.

func (*BADRECV) Remove

func (t *Tree[V]) Remove(pos int)

Remove deletes the interval starting at 'pos'.

func (*BADRECV) Size

func (t *Tree[V]) Size() int

Size returns the number of elements in the tree.

Generated by gomarkdoc