interval

package
v1.2.1 Latest Latest
Warning

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

Go to latest
Published: Jan 12, 2023 License: MIT Imports: 3 Imported by: 0

README

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).

Example

{
	tree := New[int, string]()
	tree.Put(0, 10, "foo")
	tree.Put(5, 9, "bar")
	tree.Put(10, 11, "baz")
	tree.Put(-10, 4, "quux")

	vals := tree.Overlaps(4, 10)
	for _, v := range vals {
		fmt.Println(v.Val)
	}

}
Output
foo
bar

Index

type KV

type KV[I constraints.Ordered, V any] struct {
    Low, High I
    Val       V
}

type Tree

Tree implements an interval tree. All intervals must have unique starting positions. Every low bound if an interval is inclusive, while high is exclusive.

type Tree[I constraints.Ordered, V any] struct {
    // contains filtered or unexported fields
}
func New
func New[I constraints.Ordered, V any]() *Tree[I, V]

New returns an empty interval tree.

func (*Tree[I, V]) Add
func (t *Tree[I, V]) Add(low, high I, value V) (KV[I, V], bool)

Add associates the interval [low, high) with value.

If an interval starting at low already exists in t, this method doesn't perform any change of the tree, but returns the conflicting interval.

func (*Tree[I, V]) Each
func (t *Tree[I, V]) Each(fn func(low, high I, val V))

Each calls 'fn' on every element in the tree, and its corresponding interval, in order sorted by starting position.

func (*Tree[I, V]) Get
func (t *Tree[I, V]) Get(low I) (KV[I, V], bool)

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

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

Height returns the height of the tree.

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

Overlaps returns all values that overlap with the given range. List returned is sorted by low positions of intervals.

func (*Tree[I, V]) Put
func (t *Tree[I, V]) Put(low, high I, value V) (KV[I, V], bool)

Put associates the interval [low, high) with value.

If an interval starting at low already exists, this method will replace it. In such a case the conflicting (replaced) interval is returned.

func (*Tree[I, V]) Remove
func (t *Tree[I, V]) Remove(low I) (KV[I, V], bool)

Remove deletes the interval starting at low. The removed interval is returned. If no such interval existed in a tree, the returned value is false.

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

Size returns the number of elements in the tree.

Generated by gomarkdoc

Documentation

Overview

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).

Example
tree := New[int, string]()
tree.Put(0, 10, "foo")
tree.Put(5, 9, "bar")
tree.Put(10, 11, "baz")
tree.Put(-10, 4, "quux")

vals := tree.Overlaps(4, 10)
for _, v := range vals {
	fmt.Println(v.Val)
}
Output:

foo
bar

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type KV

type KV[I constraints.Ordered, V any] struct {
	Low, High I
	Val       V
}

type Tree

type Tree[I constraints.Ordered, V any] struct {
	// contains filtered or unexported fields
}

Tree implements an interval tree. All intervals must have unique starting positions. Every low bound if an interval is inclusive, while high is exclusive.

func New

func New[I constraints.Ordered, V any]() *Tree[I, V]

New returns an empty interval tree.

func (*Tree[I, V]) Add added in v1.0.0

func (t *Tree[I, V]) Add(low, high I, value V) (KV[I, V], bool)

Add associates the interval [low, high) with value.

If an interval starting at low already exists in t, this method doesn't perform any change of the tree, but returns the conflicting interval.

func (*Tree[I, V]) Each

func (t *Tree[I, V]) Each(fn func(low, high I, val V))

Each calls 'fn' on every element in the tree, and its corresponding interval, in order sorted by starting position.

func (*Tree[I, V]) Get

func (t *Tree[I, V]) Get(low I) (KV[I, V], bool)

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

func (*Tree[I, V]) Height

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

Height returns the height of the tree.

func (*Tree[I, V]) Overlaps

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

Overlaps returns all values that overlap with the given range. List returned is sorted by low positions of intervals.

func (*Tree[I, V]) Put

func (t *Tree[I, V]) Put(low, high I, value V) (KV[I, V], bool)

Put associates the interval [low, high) with value.

If an interval starting at low already exists, this method will replace it. In such a case the conflicting (replaced) interval is returned.

func (*Tree[I, V]) Remove

func (t *Tree[I, V]) Remove(low I) (KV[I, V], bool)

Remove deletes the interval starting at low. The removed interval is returned. If no such interval existed in a tree, the returned value is false.

func (*Tree[I, V]) Size

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

Size returns the number of elements in the tree.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL