interval

package
v0.0.0-...-aad293a Latest Latest
Warning

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

Go to latest
Published: Nov 20, 2020 License: BSD-3-Clause Imports: 2 Imported by: 148

Documentation

Overview

Package interval implements an interval tree based on an augmented Left-Leaning Red Black tree.

Index

Examples

Constants

View Source
const (
	TD234 = iota
	BU23
)

Operation mode of the underlying LLRB tree.

View Source
const Mode = BU23

Variables

View Source
var ErrInvertedRange = errors.New("interval: inverted range")

ErrInvertedRange is returned if an interval is used where the start value is greater than the end value.

Functions

This section is empty.

Types

type Comparable

type Comparable interface {
	// Compare returns a value indicating the sort order relationship between the
	// receiver and the parameter.
	//
	// Given c = a.Compare(b):
	//  c < 0 if a < b;
	//  c == 0 if a == b; and
	//  c > 0 if a > b.
	//
	Compare(Comparable) int
}

A Comparable is a type that describes the ends of an Overlapper.

type IntInterface

type IntInterface interface {
	IntOverlapper
	Range() IntRange
	ID() uintptr // Returns a unique ID for the element.
}

An IntInterface is a type that can be inserted into a IntTree.

type IntNode

type IntNode struct {
	Elem        IntInterface
	Interval    IntRange
	Range       IntRange
	Left, Right *IntNode
	Color       llrb.Color
}

A IntNode represents a node in an IntTree.

type IntOperation

type IntOperation func(IntInterface) (done bool)

An IntOperation is a function that operates on an IntInterface. If done is returned true, the IntOperation is indicating that no further work needs to be done and so the Do function should traverse no further.

type IntOverlapper

type IntOverlapper interface {
	// Overlap returns a boolean indicating whether the receiver overlaps a range.
	Overlap(IntRange) bool
}

An IntOverlapper can determine whether it overlaps an integer range.

type IntRange

type IntRange struct {
	Start, End int
}

An IntRange is a type that describes the basic characteristics of an interval over the integer number line.

type IntTree

type IntTree struct {
	Root  *IntNode // Root node of the tree.
	Count int      // Number of elements stored.
}

A IntTree manages the root node of an integer line interval tree. Public methods are exposed through this type.

func (*IntTree) AdjustRanges

func (t *IntTree) AdjustRanges()

AdjustRanges fixes range fields for all IntNodes in the IntTree. This must be called before Get or DoMatching* is used if fast insertion or deletion has been performed.

func (*IntTree) Ceil

func (t *IntTree) Ceil(q IntInterface) (o IntInterface, err error)

Ceil returns the smallest value equal to or greater than the query q according to q.Start().Compare(), with ties broken by comparison of ID() values.

func (*IntTree) Delete

func (t *IntTree) Delete(e IntInterface, fast bool) (err error)

Delete deletes the element e if it exists in the IntTree.

func (*IntTree) DeleteMax

func (t *IntTree) DeleteMax(fast bool)

DeleteMax deletes the right-most interval.

func (*IntTree) DeleteMin

func (t *IntTree) DeleteMin(fast bool)

DeleteMin deletes the left-most interval.

func (*IntTree) Do

func (t *IntTree) Do(fn IntOperation) bool

Do performs fn on all intervals stored in the tree. A boolean is returned indicating whether the Do traversal was interrupted by an IntOperation returning true. If fn alters stored intervals' end points, future tree operation behaviors are undefined.

func (*IntTree) DoMatching

func (t *IntTree) DoMatching(fn IntOperation, q IntOverlapper) bool

DoMatch performs fn on all intervals stored in the tree that match q according to Overlap, with q.Overlap() used to guide tree traversal, so DoMatching() will out perform Do() with a called conditional function if the condition is based on sort order, but can not be reliably used if the condition is independent of sort order. A boolean is returned indicating whether the Do traversal was interrupted by an IntOperation returning true. If fn alters stored intervals' end points, future tree operation behaviors are undefined.

func (*IntTree) DoMatchingReverse

func (t *IntTree) DoMatchingReverse(fn IntOperation, q IntOverlapper) bool

DoMatchReverse performs fn on all intervals stored in the tree that match q according to Overlap, with q.Overlap() used to guide tree traversal, so DoMatching() will out perform Do() with a called conditional function if the condition is based on sort order, but can not be reliably used if the condition is independent of sort order. A boolean is returned indicating whether the Do traversal was interrupted by an IntOperation returning true. If fn alters stored intervals' end points, future tree operation behaviors are undefined.

func (*IntTree) DoReverse

func (t *IntTree) DoReverse(fn IntOperation) bool

DoReverse performs fn on all intervals stored in the tree, but in reverse of sort order. A boolean is returned indicating whether the Do traversal was interrupted by an IntOperation returning true. If fn alters stored intervals' end points, future tree operation behaviors are undefined.

func (*IntTree) Floor

func (t *IntTree) Floor(q IntInterface) (o IntInterface, err error)

Floor returns the largest value equal to or less than the query q according to q.Start().Compare(), with ties broken by comparison of ID() values.

func (*IntTree) Get

func (t *IntTree) Get(q IntOverlapper) (o []IntInterface)

Get returns a slice of IntInterfaces that overlap q in the IntTree according to q.Overlap().

func (*IntTree) Insert

func (t *IntTree) Insert(e IntInterface, fast bool) (err error)

Insert inserts the IntInterface e into the IntTree. Insertions may replace existing stored intervals.

func (*IntTree) Len

func (t *IntTree) Len() int

Len returns the number of intervals stored in the IntTree.

func (*IntTree) Max

func (t *IntTree) Max() IntInterface

Return the right-most interval stored in the tree.

func (*IntTree) Min

func (t *IntTree) Min() IntInterface

Return the left-most interval stored in the tree.

type Interface

type Interface interface {
	Overlapper
	Range
	ID() uintptr         // Returns a unique ID for the element.
	NewMutable() Mutable // Returns an mutable copy of the Interface's range.
}

An Interface is a type that can be inserted into a Tree.

type Mutable

type Mutable interface {
	Range
	SetStart(Comparable) // Set the start value.
	SetEnd(Comparable)   // Set the end value.
}

A Mutable is a Range that can have its range altered.

type Node

type Node struct {
	Elem        Interface
	Range       Mutable
	Left, Right *Node
	Color       llrb.Color
}

A Node represents a node in a Tree.

type Operation

type Operation func(Interface) (done bool)

An Operation is a function that operates on an Interface. If done is returned true, the Operation is indicating that no further work needs to be done and so the Do function should traverse no further.

type Overlapper

type Overlapper interface {
	// Overlap returns a boolean indicating whether the receiver overlaps the parameter.
	Overlap(Range) bool
}

An Overlapper can determine whether it overlaps a range.

type Range

type Range interface {
	// Return a Comparable equal to the start value of the Overlapper.
	Start() Comparable
	// Return a Comparable equal to the end value of the Overlapper.
	End() Comparable
}

A Range is a type that describes the basic characteristics of an interval.

type Tree

type Tree struct {
	Root  *Node // Root node of the tree.
	Count int   // Number of elements stored.
}

A Tree manages the root node of an interval tree. Public methods are exposed through this type.

func (*Tree) AdjustRanges

func (t *Tree) AdjustRanges()

AdjustRanges fixes range fields for all Nodes in the Tree. This must be called before Get or DoMatching* is used if fast insertion or deletion has been performed.

func (*Tree) Ceil

func (t *Tree) Ceil(q Interface) (o Interface, err error)

Ceil returns the smallest value equal to or greater than the query q according to q.Start().Compare(), with ties broken by comparison of ID() values.

func (*Tree) Delete

func (t *Tree) Delete(e Interface, fast bool) (err error)

Delete deletes the element e if it exists in the Tree.

func (*Tree) DeleteMax

func (t *Tree) DeleteMax(fast bool)

DeleteMax deletes the right-most interval.

func (*Tree) DeleteMin

func (t *Tree) DeleteMin(fast bool)

DeleteMin deletes the left-most interval.

func (*Tree) Do

func (t *Tree) Do(fn Operation) bool

Do performs fn on all intervals stored in the tree. A boolean is returned indicating whether the Do traversal was interrupted by an Operation returning true. If fn alters stored intervals' sort relationships, future tree operation behaviors are undefined.

Example
package main

import (
	"fmt"

	"github.com/biogo/store/interval"
)

func min(a, b Int) Int {
	if a < b {
		return a
	}
	return b
}

func max(a, b Int) Int {
	if a > b {
		return a
	}
	return b
}

// Flatten all overlapping intervals, storing originals as sub-intervals.
func Flatten(t *interval.Tree) {
	var (
		fi  = true
		ti  []Interval
		mid uintptr
	)

	t.Do(
		func(e interval.Interface) (done bool) {
			iv := e.(Interval)
			if fi || iv.start >= ti[len(ti)-1].end {
				ti = append(ti, Interval{
					start: iv.start,
					end:   iv.end,
				})
				fi = false
			} else {
				ti[len(ti)-1].end = max(ti[len(ti)-1].end, iv.end)
			}
			ti[len(ti)-1].Sub = append(ti[len(ti)-1].Sub, iv)
			if iv.id > mid {
				mid = iv.id
			}

			return
		},
	)

	mid++
	t.Root, t.Count = nil, 0
	for i, iv := range ti {
		iv.id = uintptr(i) + mid
		t.Insert(iv, true)
	}
	t.AdjustRanges()
}

func main() {
	t := &interval.Tree{}
	for i, iv := range ivs {
		iv.id = uintptr(i)
		err := t.Insert(iv, false)
		if err != nil {
			fmt.Println(err)
		}
	}

	Flatten(t)
	t.Do(func(e interval.Interface) (done bool) { fmt.Printf("%s: %v\n", e, e.(Interval).Sub); return })

}
Output:

[0,8)#10: [[0,2)#0 [1,6)#2 [1,3)#4 [2,4)#1 [3,4)#3 [4,6)#5 [5,8)#6 [5,7)#8 [6,8)#7]
[8,9)#11: [[8,9)#9]

func (*Tree) DoMatching

func (t *Tree) DoMatching(fn Operation, q Overlapper) bool

DoMatch performs fn on all intervals stored in the tree that match q according to Overlap, with q.Overlap() used to guide tree traversal, so DoMatching() will out perform Do() with a called conditional function if the condition is based on sort order, but can not be reliably used if the condition is independent of sort order. A boolean is returned indicating whether the Do traversal was interrupted by an Operation returning true. If fn alters stored intervals' sort relationships, future tree operation behaviors are undefined.

Example
package main

import (
	"fmt"

	"github.com/biogo/store/interval"
)

// Merge an interval into the tree, replacing overlapping intervals, but retaining them as sub intervals.
func Merge(t *interval.Tree, ni Interval) {
	var (
		fi = true
		qi = &Interval{start: ni.start, end: ni.end}
		r  []interval.Interface
	)

	t.DoMatching(
		func(e interval.Interface) (done bool) {
			iv := e.(Interval)
			r = append(r, e)
			ni.Sub = append(ni.Sub, iv)

			// Flatten merge history.
			ni.Sub = append(ni.Sub, iv.Sub...)
			iv.Sub = nil

			if fi {
				ni.start = min(iv.start, ni.start)
				fi = false
			}
			ni.end = max(iv.end, ni.end)

			return
		},
		qi,
	)
	for _, d := range r {
		t.Delete(d, false)
	}
	t.Insert(ni, false)
}

func main() {
	t := &interval.Tree{}

	var (
		i  int
		iv Interval
	)

	for i, iv = range ivs {
		iv.id = uintptr(i)
		err := t.Insert(iv, false)
		if err != nil {
			fmt.Println(err)
		}
	}
	i++

	Merge(t, Interval{start: -1, end: 4, id: uintptr(i)})
	t.Do(func(e interval.Interface) (done bool) {
		fmt.Printf("%s: %v\n", e, e.(Interval).Sub)
		return
	})

}
Output:

[-1,6)#10: [[0,2)#0 [1,6)#2 [1,3)#4 [2,4)#1 [3,4)#3]
[4,6)#5: []
[5,8)#6: []
[5,7)#8: []
[6,8)#7: []
[8,9)#9: []

func (*Tree) DoMatchingReverse

func (t *Tree) DoMatchingReverse(fn Operation, q Overlapper) bool

DoMatchReverse performs fn on all intervals stored in the tree that match q according to Overlap, with q.Overlap() used to guide tree traversal, so DoMatching() will out perform Do() with a called conditional function if the condition is based on sort order, but can not be reliably used if the condition is independent of sort order. A boolean is returned indicating whether the Do traversal was interrupted by an Operation returning true. If fn alters stored intervals' sort relationships, future tree operation behaviors are undefined.

func (*Tree) DoReverse

func (t *Tree) DoReverse(fn Operation) bool

DoReverse performs fn on all intervals stored in the tree, but in reverse of sort order. A boolean is returned indicating whether the Do traversal was interrupted by an Operation returning true. If fn alters stored intervals' sort relationships, future tree operation behaviors are undefined.

func (*Tree) Floor

func (t *Tree) Floor(q Interface) (o Interface, err error)

Floor returns the largest value equal to or less than the query q according to q.Start().Compare(), with ties broken by comparison of ID() values.

func (*Tree) Get

func (t *Tree) Get(q Overlapper) (o []Interface)

Get returns a slice of Interfaces that overlap q in the Tree according to q.Overlap().

func (*Tree) Insert

func (t *Tree) Insert(e Interface, fast bool) (err error)

Insert inserts the Interface e into the Tree. Insertions may replace existing stored intervals.

func (*Tree) Len

func (t *Tree) Len() int

Len returns the number of intervals stored in the Tree.

func (*Tree) Max

func (t *Tree) Max() Interface

Return the right-most interval stored in the tree.

func (*Tree) Min

func (t *Tree) Min() Interface

Return the left-most interval stored in the tree.

Directories

Path Synopsis
Package landscape implements persistence landscape calculation for a set of intervals.
Package landscape implements persistence landscape calculation for a set of intervals.

Jump to

Keyboard shortcuts

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