base: github.com/grailbio/base/intervalmap Index | Examples | Files

package intervalmap

import "github.com/grailbio/base/intervalmap"

Package intervalmap stores a set of (potentially overlapping) intervals. It supports searching for intervals that overlap user-provided interval.

The implementation uses an 1-D version of Kd tree with randomized surface-area heuristic (http://www.sci.utah.edu/~wald/Publications/2007/ParallelBVHBuild/fastbuild.pdf).

Code generated by generate_randomized_freepool.py. DO NOT EDIT.

Code:

newEntry := func(start, limit Key) Entry {
    return Entry{
        Interval: Interval{start, limit},
        Data:     fmt.Sprintf("[%d,%d)", start, limit),
    }
}

doGet := func(tree *T, start, limit Key) string {
    matches := []*Entry{}
    tree.Get(Interval{start, limit}, &matches)
    s := []string{}
    for _, m := range matches {
        s = append(s, m.Data.(string))
    }
    sort.Strings(s)
    return strings.Join(s, ",")
}

tree := New([]Entry{newEntry(1, 4), newEntry(3, 5), newEntry(6, 7)})
fmt.Println(doGet(tree, 0, 2))
fmt.Println(doGet(tree, 0, 4))
fmt.Println(doGet(tree, 4, 6))
fmt.Println(doGet(tree, 4, 7))

Output:

[1,4)
[1,4),[3,5)
[3,5)
[3,5),[6,7)

Index

Examples

Package Files

intervalmap.go randomized_freepool_internal.go search_freepool.go

func NewsearcherFreePool Uses

func NewsearcherFreePool(new func() *searcher, maxSize int) *searcherFreePool

NewsearcherFreePool creates a new free object pool. new should create a new object. It is called when the pool is empty on Get(). maxSize bounds the approx max number of objects that can be stored in the pool. Beyond this limit, Put() call will drop the objects.

type Entry Uses

type Entry struct {
    // Interval defines a half-open interval, [Start,Limit)
    Interval Interval
    // Data is an arbitrary user-defined payload
    Data interface{}
}

Entry represents one interval.

type Interval Uses

type Interval struct {
    // Start is included
    Start Key
    // Limit is excluded.
    Limit Key
}

Interval defines an half-open interval, [Start, Limit).

func (Interval) Empty Uses

func (i Interval) Empty() bool

Empty checks if the interval is empty.

func (Interval) Intersect Uses

func (i Interval) Intersect(j Interval) Interval

Intersect computes i ∩ j.

func (Interval) Intersects Uses

func (i Interval) Intersects(j Interval) bool

Intersects checks if (i∩j) != ∅

func (Interval) Span Uses

func (i Interval) Span(j Interval) Interval

Span computes a minimal interval that spans over both i and j. If either i or j is an empty set, this function returns the other set.

type Key Uses

type Key = int64

Key is the type for interval boundaries.

type T Uses

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

T represents the intervalmap. It must be created using New().

func New Uses

func New(ents []Entry) *T

New creates a new tree with the given set of entries. The intervals may overlap, and they need not be sorted.

func (*T) Any Uses

func (t *T) Any(interval Interval) bool

Any checks if any of the entries intersect the given interval.

func (*T) Get Uses

func (t *T) Get(interval Interval, ents *[]*Entry)

Get finds all the entries that intersect the given interval and return them in *ents.

func (*T) MarshalBinary Uses

func (t *T) MarshalBinary() (data []byte, err error)

MarshalBinary implements encoding.BinaryMarshaler interface. It allows T to be encoded and decoded using Gob.

func (*T) Stats Uses

func (t *T) Stats() TreeStats

Stats returns tree-wide stats.

func (*T) UnmarshalBinary Uses

func (t *T) UnmarshalBinary(data []byte) error

UnmarshalBinary implements encoding.BinaryUnmarshaler interface. It allows T to be encoded and decoded using Gob.

type TreeStats Uses

type TreeStats struct {
    // Nodes is the total number of tree nodes.
    Nodes int
    // Nodes is the total number of leaf nodes.
    //
    // Invariant: LeafNodes < Nodes
    LeafNodes int
    // MaxDepth is the max depth of the tree.
    MaxDepth int
    // MaxLeafNodeSize is the maximum len(node.ents) of all nodes in the tree.
    MaxLeafNodeSize int
    // TotalLeafDepth is the sum of depth of all leaf nodes.
    TotalLeafDepth int
    // TotalLeafDepth is the sum of len(node.ents) of all leaf nodes.
    TotalLeafNodeSize int
}

TreeStats shows tree-wide stats.

Package intervalmap imports 11 packages (graph). Updated 2019-10-14. Refresh now. Tools for package owners.