interval

package
v0.0.0-...-1e0262a Latest Latest
Warning

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

 Go to latest Published: May 3, 2025 License: MIT Imports: 8 Imported by: 0

Documentation

Overview

Package interval provides a generic interval tree implementation.

An interval tree is a data structure useful for storing values associated with intervals, and efficiently search those values based on intervals that overlap with any given interval. This generic implementation uses a self-balancing binary search tree algorithm, so searching for any intersection has a worst-case time-complexity guarantee of <= 2 log N, where N is the number of items in the tree.

For more on interval trees, see https://en.wikipedia.org/wiki/Interval_tree

To create a tree with time.Time as interval key type and string as value type: 

cmpFn := func(t1, t2 time.Time) int {
  switch{
  case t1.After(t2): return 1
  case t1.Before(t2): return -1
  default: return 0
  }
}
st := interval.NewSearchTree[string](cmpFn)
Example 
package main

import (
	"fmt"

	"github.com/hilariousai/intervalst/interval"
)

func main() {
	cmpFn := func(x, y int) int { return x - y }

	// We must define the value type as the compiler can't infer in this case.
	st := interval.NewSearchTree[string](cmpFn)

	st.Insert(17, 19, "value1")
	st.Insert(5, 8, "value2")
	st.Insert(21, 24, "value3")
	st.Insert(4, 8, "value4")
	st.Insert(15, 18, "value5")
	st.Insert(7, 10, "value6")
	st.Insert(16, 22, "value7")

	val, ok := st.AnyIntersection(23, 25)
	fmt.Println(val, ok)

	val, ok = st.AnyIntersection(21, 23)
	fmt.Println(val, ok)

	_, ok = st.AnyIntersection(12, 14)
	fmt.Println(ok)

}

Output:

value3 true
value7 true
false

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

func HCOjAG 

func HCOjAG() error

Types

type CmpFunc 

type CmpFunc[T any] func(x, y T) int

CmpFunc must return a nagative integer, zero or a positive interger as x is less than, equal to, or greater than y, respectively.

CmpFunc imposes a total ordering on the given x and y values.

It must also ensure that the relation is transitive: cmp(x, y) > 0 && cmp(y, z) > 0 implies cmp(x, z) > 0.

type EmptyValueListError 

type EmptyValueListError string

EmptyValueListError is a description of an invalid list of values.

func (EmptyValueListError) Error 

func (e EmptyValueListError) Error() string

Error returns a string representation of the EmptyValueListError error.

type InvalidIntervalError 

type InvalidIntervalError string

InvalidIntervalError is a description of an invalid interval.

func (InvalidIntervalError) Error 

func (s InvalidIntervalError) Error() string

Error returns a string representation of the InvalidIntervalError error.

type MultiValueSearchTree 

type MultiValueSearchTree[V, T any] SearchTree[V, T]

MultiValueSearchTree is a generic type representing the Interval Search Tree where V is a generic value type, and T is a generic interval key type. MultiValueSearchTree can store multiple values for a given interval key.

func NewMultiValueSearchTree 

func NewMultiValueSearchTree[V, T any](cmp CmpFunc[T]) *MultiValueSearchTree[V, T]

NewMultiValueSearchTree returns an initialized multi value interval search tree. The cmp parameter is used for comparing total order of the interval key type T when inserting or looking up an interval in the tree. For more details on cmp, see the CmpFunc type.

NewMultiValueSearchTree will panic if cmp is nil.

func NewMultiValueSearchTreeWithOptions 

func NewMultiValueSearchTreeWithOptions[V, T any](cmp CmpFunc[T], opts ...TreeOption) *MultiValueSearchTree[V, T]

NewSearchTreeWithOptions returns an initialized multi-value interval search tree with custom configuration options. The cmp parameter is used for comparing total order of the interval key type T when inserting or looking up an interval in the tree. The opts parameter is an optional list of TreeOptions that customize the behavior of the tree, such as allowing point intervals using TreeWithIntervalPoint.

NewMultiValueSearchTreeWithOptions will panic if cmp is nil.

func (*MultiValueSearchTree[V, T]) AllIntersections 

func (st *MultiValueSearchTree[V, T]) AllIntersections(start, end T) ([]V, bool)

AllIntersections returns a slice of values which interval key intersects with the given start and end interval. It returns true as the second return value if any intersection is found in the tree; otherwise, false.

func (*MultiValueSearchTree[V, T]) AnyIntersection 

func (st *MultiValueSearchTree[V, T]) AnyIntersection(start, end T) ([]V, bool)

AnyIntersection returns values which interval key intersects with the given start and end interval. It returns true as the second return value if any intersection is found in the tree; otherwise, false.

func (*MultiValueSearchTree[V, T]) Ceil 

func (st *MultiValueSearchTree[V, T]) Ceil(start, end T) ([]V, bool)

Ceil returns the values which interval key is the smallest interval key greater than the given start and end interval. It returns true as the second return value if there's a ceiling interval key for the given start and end interval in the tree; otherwise, false.

func (*MultiValueSearchTree[V, T]) Delete 

func (st *MultiValueSearchTree[V, T]) Delete(start, end T) error

Delete removes the given start and end interval key and its associated values from the tree. It does nothing if the given start and end interval key doesn't exist in the tree.

Delete returns an InvalidIntervalError if the given end is less than or equal to the given start value.

func (*MultiValueSearchTree[V, T]) DeleteMax 

func (st *MultiValueSearchTree[V, T]) DeleteMax()

DeleteMax removes the largest interval key and its associated values from the tree.

func (*MultiValueSearchTree[V, T]) DeleteMin 

func (st *MultiValueSearchTree[V, T]) DeleteMin()

DeleteMin removes the smallest interval key and its associated values from the tree.

func (*MultiValueSearchTree[V, T]) Find 

func (st *MultiValueSearchTree[V, T]) Find(start, end T) ([]V, bool)

Find returns the values which interval key exactly matches with the given start and end interval. It returns true as the second return value if an exaclty matching interval key is found in the tree; otherwise, false.

func (*MultiValueSearchTree[V, T]) Floor 

func (st *MultiValueSearchTree[V, T]) Floor(start, end T) ([]V, bool)

Floor returns the values which interval key is the greatest interval key lesser than the given start and end interval. It returns true as the second return value if there's a floor interval key for the given start and end interval in the tree; otherwise, false.

func (*MultiValueSearchTree[V, T]) GobDecode 

func (st *MultiValueSearchTree[V, T]) GobDecode(data []byte) error

GobDecode decodes the tree (compatible with encoding/gob).

func (*MultiValueSearchTree[V, T]) GobEncode 

func (st *MultiValueSearchTree[V, T]) GobEncode() ([]byte, error)

GobEncode encodes the tree (compatible with encoding/gob).

func (*MultiValueSearchTree[V, T]) Height 

func (st *MultiValueSearchTree[V, T]) Height() int

Height returns the max depth of the tree.

func (*MultiValueSearchTree[V, T]) Insert 

func (st *MultiValueSearchTree[V, T]) Insert(start, end T, vals ...V) error

Insert inserts the given vals with the given start and end as the interval key. If there's already an interval key entry with the given start and end interval, Insert will append the given vals to the exiting interval key.

Insert returns an InvalidIntervalError if the given end is less than or equal to the given start value, or an EmptyValueListError if vals is an empty list.

Example 
package main

import (
	"fmt"
	"time"

	"github.com/hilariousai/intervalst/interval"
)

func main() {
	cmpFn := func(start, end time.Time) int {
		switch {
		case start.After(end):
			return 1
		case start.Before(end):
			return -1
		default:
			return 0
		}
	}

	st := interval.NewMultiValueSearchTree[string](cmpFn)

	start, end := time.Now(), time.Now().Add(time.Hour)
	st.Insert(start, end, "event1", "event2", "event3")

	st.Insert(start, end, "event4")

	vals, ok := st.Find(start, end)
	fmt.Println(vals, ok)
}

Output:

[event1 event2 event3 event4] true

func (*MultiValueSearchTree[V, T]) IsEmpty 

func (st *MultiValueSearchTree[V, T]) IsEmpty() bool

IsEmpty returns true if the tree is empty; otherwise, false.

func (*MultiValueSearchTree[V, T]) Max 

func (st *MultiValueSearchTree[V, T]) Max() ([]V, bool)

Max returns the values which interval key is the maximum interval in the tree. It returns false as the second return value if the tree is empty; otherwise, true.

func (*MultiValueSearchTree[V, T]) MaxEnd 

func (st *MultiValueSearchTree[V, T]) MaxEnd() ([]V, bool)

MaxEnd returns the values in the tree that have the largest ending interval. It returns false as the second return value if the tree is empty; otherwise, true.

func (*MultiValueSearchTree[V, T]) Min 

func (st *MultiValueSearchTree[V, T]) Min() ([]V, bool)

Min returns the values which interval key is the minimum interval key in the tree. It returns false as the second return value if the tree is empty; otherwise, true.

func (*MultiValueSearchTree[V, T]) Rank 

func (st *MultiValueSearchTree[V, T]) Rank(start, end T) int

Rank returns the number of intervals strictly less than the given start and end interval.

func (*MultiValueSearchTree[V, T]) Select 

func (st *MultiValueSearchTree[V, T]) Select(k int) ([]V, bool)

Select returns the values which interval key is the kth smallest interval key in the tree. It returns false if k is not between 0 and N-1, where N is the number of interval keys in the tree; otherwise, true.

func (*MultiValueSearchTree[V, T]) Size 

func (st *MultiValueSearchTree[V, T]) Size() int

Size returns the number of intervals in the tree.

func (*MultiValueSearchTree[V, T]) Upsert 

func (st *MultiValueSearchTree[V, T]) Upsert(start, end T, vals ...V) error

Upsert inserts the given vals with the given start and end as the interval key. If there's already an interval key entry with the given start and end interval, it will be updated with the given vals.

Insert returns an InvalidIntervalError if the given end is less than or equal to the given start value, or an EmptyValueListError if vals is an empty list.

Example 
package main

import (
	"fmt"
	"time"

	"github.com/hilariousai/intervalst/interval"
)

func main() {
	cmpFn := func(start, end time.Time) int {
		switch {
		case start.After(end):
			return 1
		case start.Before(end):
			return -1
		default:
			return 0
		}
	}

	st := interval.NewMultiValueSearchTree[string](cmpFn)

	start, end := time.Now(), time.Now().Add(time.Hour)
	st.Insert(start, end, "event1", "event2", "event3")

	// Upsert will replace the previous values associated
	// with the start and end interval key, if any.
	st.Upsert(start, end, "event4", "event5")

	vals, ok := st.Find(start, end)
	fmt.Println(vals, ok)
}

Output:

[event4 event5] true

type SearchTree 

type SearchTree[V, T any] struct {
	// contains filtered or unexported fields
}

SearchTree is a generic type representing the Interval Search Tree where V is a generic value type, and T is a generic interval key type. For more details on how to use these configuration options, see the TreeOption function and their usage in the NewSearchTreeWithOptions and NewMultiValueSearchTreeWithOptions functions.

func NewSearchTree 

func NewSearchTree[V, T any](cmp CmpFunc[T]) *SearchTree[V, T]

NewSearchTree returns an initialized interval search tree. The cmp parameter is used for comparing total order of the interval key type T when inserting or looking up an interval in the tree. For more details on cmp, see the CmpFunc type.

NewSearchTree will panic if cmp is nil.

func NewSearchTreeWithOptions 

func NewSearchTreeWithOptions[V, T any](cmp CmpFunc[T], opts ...TreeOption) *SearchTree[V, T]

NewSearchTreeWithOptions returns an initialized interval search tree with custom configuration options. The cmp parameter is used for comparing total order of the interval key type T when inserting or looking up an interval in the tree. The opts parameter is an optional list of TreeOptions that customize the behavior of the tree, such as allowing point intervals using TreeWithIntervalPoint.

NewSearchTreeWithOptions will panic if cmp is nil.

func (*SearchTree[V, T]) AllIntersections 

func (st *SearchTree[V, T]) AllIntersections(start, end T) ([]V, bool)

AllIntersections returns a slice of values which interval key intersects with the given start and end interval. It returns true as the second return value if any intersection is found in the tree; otherwise, false.

func (*SearchTree[V, T]) AnyIntersection 

func (st *SearchTree[V, T]) AnyIntersection(start, end T) (V, bool)

AnyIntersection returns a value which interval key intersects with the given start and end interval. It returns true as the second return value if any intersection is found in the tree; otherwise, false.

func (*SearchTree[V, T]) Ceil 

func (st *SearchTree[V, T]) Ceil(start, end T) (V, bool)

Ceil returns a value which interval key is the smallest interval key greater than the given start and end interval. It returns true as the second return value if there's a ceiling interval key for the given start and end interval in the tree; otherwise, false.

Example 
package main

import (
	"fmt"

	"github.com/hilariousai/intervalst/interval"
)

func main() {
	cmpFn := func(x, y int) int { return x - y }

	st := interval.NewSearchTree[string](cmpFn)

	st.Insert(17, 19, "value1")
	st.Insert(5, 8, "value2")
	st.Insert(21, 24, "value3")
	st.Insert(4, 8, "value4")
	st.Insert(15, 18, "value5")
	st.Insert(7, 10, "value6")

	val, ok := st.Ceil(9, 16)
	fmt.Println(val, ok)
}

Output:

value5 true

func (*SearchTree[V, T]) Delete 

func (st *SearchTree[V, T]) Delete(start, end T) error

Delete removes the given start and end interval key and its associated value from the tree. It does nothing if the given start and end interval key doesn't exist in the tree.

Delete returns an InvalidIntervalError if the given end is less than or equal to the given start value.

func (*SearchTree[V, T]) DeleteMax 

func (st *SearchTree[V, T]) DeleteMax()

DeleteMax removes the largest interval key and its associated value from the tree.

func (*SearchTree[V, T]) DeleteMin 

func (st *SearchTree[V, T]) DeleteMin()

DeleteMin removes the smallest interval key and its associated value from the tree.

func (*SearchTree[V, T]) Find 

func (st *SearchTree[V, T]) Find(start, end T) (V, bool)

Find returns the value which interval key exactly matches with the given start and end interval. It returns true as the second return value if an exaclty matching interval key is found in the tree; otherwise, false.

func (*SearchTree[V, T]) Floor 

func (st *SearchTree[V, T]) Floor(start, end T) (V, bool)

Floor returns a value which interval key is the greatest interval key lesser than the given start and end interval. It returns true as the second return value if there's a floor interval key for the given start and end interval in the tree; otherwise, false.

Example 
package main

import (
	"fmt"

	"github.com/hilariousai/intervalst/interval"
)

func main() {
	cmpFn := func(x, y int) int { return x - y }

	st := interval.NewSearchTree[string](cmpFn)

	st.Insert(17, 19, "value1")
	st.Insert(5, 8, "value2")
	st.Insert(21, 24, "value3")
	st.Insert(4, 8, "value4")
	st.Insert(15, 18, "value5")
	st.Insert(7, 10, "value6")

	val, ok := st.Floor(9, 16)
	fmt.Println(val, ok)
}

Output:

value6 true

func (*SearchTree[V, T]) GobDecode 

func (st *SearchTree[V, T]) GobDecode(data []byte) error

GobDecode decodes the tree (compatible with encoding/gob).

func (*SearchTree[V, T]) GobEncode 

func (st *SearchTree[V, T]) GobEncode() ([]byte, error)

GobEncode encodes the tree (compatible with encoding/gob).

func (*SearchTree[V, T]) Height 

func (st *SearchTree[V, T]) Height() int

Height returns the max depth of the tree.

func (*SearchTree[V, T]) Insert 

func (st *SearchTree[V, T]) Insert(start, end T, val V) error

Insert inserts the given val with the given start and end as the interval key. If there's already an interval key entry with the given start and end interval, it will be updated with the given val.

Insert returns an InvalidIntervalError if the given end is less than or equal to the given start value.

func (*SearchTree[V, T]) IsEmpty 

func (st *SearchTree[V, T]) IsEmpty() bool

IsEmpty returns true if the tree is empty; otherwise, false.

func (*SearchTree[V, T]) Max 

func (st *SearchTree[V, T]) Max() (V, bool)

Max returns the value which interval key is the maximum interval in the tree. It returns false as the second return value if the tree is empty; otherwise, true.

func (*SearchTree[V, T]) MaxEnd 

func (st *SearchTree[V, T]) MaxEnd() ([]V, bool)

MaxEnd returns the values in the tree that have the largest ending interval. It returns false as the second return value if the tree is empty; otherwise, true.

func (*SearchTree[V, T]) Min 

func (st *SearchTree[V, T]) Min() (V, bool)

Min returns the value which interval key is the minimum interval key in the tree. It returns false as the second return value if the tree is empty; otherwise, true.

func (*SearchTree[V, T]) Rank 

func (st *SearchTree[V, T]) Rank(start, end T) int

Rank returns the number of intervals strictly less than the given start and end interval.

func (*SearchTree[V, T]) Select 

func (st *SearchTree[V, T]) Select(k int) (V, bool)

Select returns the value which interval key is the kth smallest interval key in the tree. It returns false if k is not between 0 and N-1, where N is the number of interval keys in the tree; otherwise, true.

func (*SearchTree[V, T]) Size 

func (st *SearchTree[V, T]) Size() int

Size returns the number of intervals in the tree.

type TreeConfig 

type TreeConfig struct {
	// contains filtered or unexported fields
}

TreeConfig contains configuration fields that are used to customize the behavior of interval trees, specifically SearchTree and MultiValueSearchTree types.

type TreeOption 

type TreeOption func(*TreeConfig)

TreeOption is a functional option type used to customize the behavior of interval trees, such as the SearchTree and MultiValueSearchTree types.

func TreeWithIntervalPoint 

func TreeWithIntervalPoint() TreeOption

TreeWithIntervalPoint returns a TreeOption function that configures an interval tree to accept intervals in which the start and end key values are the same, effectively representing a point rather than a range in the tree.

Example 
package main

import (
	"fmt"
	"time"

	"github.com/hilariousai/intervalst/interval"
)

func main() {
	cmpFn := func(start, end time.Time) int {
		switch {
		case start.After(end):
			return 1
		case start.Before(end):
			return -1
		default:
			return 0
		}
	}

	st := interval.NewSearchTreeWithOptions[string](cmpFn, interval.TreeWithIntervalPoint())

	pointInerval := time.Now()
	st.Insert(pointInerval, pointInerval, "event")

	vals, ok := st.Find(pointInerval, pointInerval)
	fmt.Println(vals, ok)
}

Output:

event true

type TypeMismatchError 

type TypeMismatchError struct {
	// contains filtered or unexported fields
}

TypeMismatchError represents an error that occurs when a type mismatch is encountered during the decoding of a tree from its gob representation. It indicates that the encoded value does not match the expected type.

func (TypeMismatchError) Error 

func (e TypeMismatchError) Error() string

Error returns a string representation of the TypeMismatchError error.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.