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.

Source Files

View all Source files

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
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.