Documentation
¶
Overview ¶
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.
Example ¶
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)
Example (Gob) ¶
Example_gob is an example of serializing an intervalmap using Gob.
newEntry := func(start, limit Key) Entry {
return Entry{
Interval: Interval{start, limit},
Data: fmt.Sprintf("[%d,%d)", start, limit),
}
}
tree := New([]Entry{newEntry(1, 4), newEntry(3, 5), newEntry(6, 7)})
buf := bytes.Buffer{}
enc := gob.NewEncoder(&buf)
if err := enc.Encode(tree); err != nil {
panic(err)
}
dec := gob.NewDecoder(&buf)
var tree2 *T
if err := dec.Decode(&tree2); err != nil {
panic(err)
}
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, ",")
}
fmt.Println(doGet(tree2, 0, 2))
fmt.Println(doGet(tree2, 0, 4))
fmt.Println(doGet(tree2, 4, 6))
fmt.Println(doGet(tree2, 4, 7))
Output: [1,4) [1,4),[3,5) [3,5) [3,5),[6,7)
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func NewsearcherFreePool ¶
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.
Types ¶
type Entry ¶
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 ¶
Interval defines an half-open interval, [Start, Limit).
func (Interval) Intersects ¶
Intersects checks if (i∩j) != ∅
type T ¶
type T struct {
// contains filtered or unexported fields
}
T represents the intervalmap. It must be created using New().
func New ¶
New creates a new tree with the given set of entries. The intervals may overlap, and they need not be sorted.
func (*T) Get ¶
Get finds all the entries that intersect the given interval and return them in *ents.
func (*T) MarshalBinary ¶
MarshalBinary implements encoding.BinaryMarshaler interface. It allows T to be encoded and decoded using Gob.
func (*T) UnmarshalBinary ¶
UnmarshalBinary implements encoding.BinaryUnmarshaler interface. It allows T to be encoded and decoded using Gob.
type TreeStats ¶
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.
Source Files