interval

package
v0.0.0-...-25502c3 Latest Latest
Warning

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

 Go to latest Published: Oct 9, 2012 License: GPL-3.0 Imports: 5 Imported by: 0

Documentation

Overview

Package to find intersections between intervals or to sort intervals.

Index

Examples

Constants

This section is empty.

Variables

View Source 
var StringFunc = defaultStringFunc

Default function for String method.

Functions

This section is empty.

Types

type Interval 

type Interval struct {
	Meta interface{}
	// contains filtered or unexported fields
}

Interval type stores start and end of interval and meta data in line and Meta (meta may be used to link to a feat.Feature).

func New 

func New(seg string, start, end, line int, meta interface{}) (*Interval, error)

Create a new Interval.

func (*Interval) Contain 

func (self *Interval) Contain(i *Interval, slop int, r chan<- *Interval)

Find Intervals completely containing the query (search is recursive inorder), and pass results on provided channel.

func (*Interval) End 

func (self *Interval) End() int

Return the end position of an Interval node.

func (*Interval) Intersect 

func (self *Interval) Intersect(i *Interval, overlap int, r chan<- *Interval)

Find Intervals that intersect with the query (search is recursive inorder), and pass results on provided channel.

func (*Interval) Left 

func (self *Interval) Left() *Interval

Return a pointer to the left child of an Interval node.

func (*Interval) LeftMost 

func (self *Interval) LeftMost() (n *Interval)

Return the left-most interval of the subtree of which the interval is the root.

func (*Interval) Line 

func (self *Interval) Line() int

Return the line number of an Interval node - not used except for reference to file.

func (*Interval) Parent 

func (self *Interval) Parent() *Interval

Return a pointer to the parent of an Interval node.

func (*Interval) Range 

func (self *Interval) Range() (int, int)

Return the range of the node's subtree span.

func (*Interval) Right 

func (self *Interval) Right() *Interval

Return a pointer to the right child of an Interval node.

func (*Interval) RightMost 

func (self *Interval) RightMost() (n *Interval)

Return the right-most interval of the subtree of which the interval is the root.

func (*Interval) ScanLeft 

func (self *Interval) ScanLeft() (n *Interval)

Return the previous interval in tree traverse order.

func (*Interval) ScanRight 

func (self *Interval) ScanRight() (n *Interval)

Return the next interval in tree traverse order.

func (*Interval) Segment 

func (self *Interval) Segment() string

Return the segment identifier for an Interval node.

func (*Interval) Start 

func (self *Interval) Start() int

Return the start position of an Interval node.

func (*Interval) String 

func (self *Interval) String() string

String method.

func (*Interval) Traverse 

func (self *Interval) Traverse(r chan<- *Interval)

Traverse all intervals accessible from the current Interval in tree order and pass results on provided channel.

func (*Interval) Within 

func (self *Interval) Within(i *Interval, slop int, r chan<- *Interval)

Find Intervals completely within with the query (search is recursive inorder), and pass results on provided channel.

type Tree 

type Tree map[string]*Interval

Tree type will store a collection of intervals. While this is not necessary for interval tree searching, a Tree stores intervals in a hash based on the segment name, reducing search time and easing coding.

func NewTree 

func NewTree() Tree

Create a new interval Tree.

func (Tree) AdjustRange 

func (self Tree) AdjustRange(seg string)

func (Tree) Contain 

func (self Tree) Contain(i *Interval, slop int) (result chan *Interval)

Find all intervals in Tree that entirely contain query. Return a channel that will convey results.

The slop parameter determines how much slop is allowed: 

slop < 0 query must be within interval by slop
slop = 0 intervals may completely coincide
slop > 0 query may extend beyond interval by slop
Example 
tree := CreateExampleTree("example", [][]int{{0, 4}, {8, 12}, {2, 3}, {5, 10}, {3, 7}, {-22, 6}, {34, 61}})
if i, err := New("example", 4, 6, 0, nil); err == nil {
	for s := range tree.Contain(i, 0) {
		fmt.Printf("%s\n", s)
	}
}

Output:

"example":[-22, 6)
"example":[3, 7)

func (Tree) FastRemove 

func (self Tree) FastRemove(i *Interval) (removed *Interval)

Remove an interval, returning the removed interval. Does not adjust ranges within tree; call AdjustRange(i.Segment()) on the tree to restore internal consistency.

func (Tree) Flatten 

func (self Tree) Flatten(i *Interval, overlap, tolerance int) (flat []*Interval, rich [][]*Interval)

Flatten a range of intervals intersecting i so that only one interval covers any given location. Intervals less than tolerance positions apart are merged into a single new flattened interval. Return flattened intervals and all intervals originally in intersected region.

The overlap parameter determines how much overlap is required: 

overlap < 0 intervals can be up to overlap away
overlap = 0 intervals abut
overlap > 0 intervals must overlap by overlap

No metadata is transfered to flattened intervals.

Example 
tree := CreateExampleTree("example", [][]int{{0, 4}, {8, 12}, {2, 3}, {5, 10}, {3, 7}, {27, 61}})
start, end := tree.Range("example")
if i, err := New("example", start, end, 0, nil); err == nil {
	flat, original := tree.Flatten(i, 0, 0)
	fmt.Printf("flattened: %v\noriginal: %v\n", flat, original)
}

Output:

flattened: ["example":[0, 12) "example":[27, 61)]
original: [["example":[0, 4) "example":[2, 3) "example":[3, 7) "example":[5, 10) "example":[8, 12)] ["example":[27, 61)]]

func (Tree) FlattenContaining 

func (self Tree) FlattenContaining(i *Interval, slop, tolerance int) (flat []*Interval, rich [][]*Interval)

Flatten a range of intervals containing i so that only one interval covers any given location. Return flattened intervals and all intervals originally in containing region.

The slop parameter determines how much slop is allowed: 

slop < 0 query must be within interval by slop
slop = 0 intervals may completely coincide
slop > 0 query may extend beyond interval by slop

No metadata is transfered to flattened intervals.

func (Tree) FlattenWithin 

func (self Tree) FlattenWithin(i *Interval, slop, tolerance int) (flat []*Interval, rich [][]*Interval)

Flatten a range of intervals within i so that only one interval covers any given location. Return flattened intervals and all intervals originally in contained region.

The slop parameter determines how much slop is allowed: 

slop < 0 intervals must be within query by slop
slop = 0 intervals may completely coincide
slop > 0 intervals may extend beyond query by slop

No metadata is transfered to flattened intervals.

Example 
tree := CreateExampleTree("example", [][]int{{0, 4}, {8, 12}, {2, 3}, {5, 10}, {3, 7}, {-22, 6}, {34, 61}})

if i, err := New("example", 2, 7, 0, nil); err == nil {
	flat, original := tree.FlattenWithin(i, 0, 0)
	fmt.Printf("flattened: %v\noriginal: %v\n", flat, original)
}

Output:

flattened: ["example":[2, 7)]
original: [["example":[2, 3) "example":[3, 7)]]

func (Tree) Insert 

func (self Tree) Insert(i *Interval)

Insert an Interval into the Tree.

Example 
tree := NewTree()
chromosome := "example"
segments := [][]int{{0, 4}, {8, 12}, {2, 3}, {5, 10}, {3, 7}, {-22, 6}, {34, 61}}

for _, s := range segments {
	if i, err := New(chromosome, s[0], s[1], 0, nil); err == nil {
		tree.Insert(i)
	} else {
		fmt.Println(err)
	}
}

PrintAll(tree)

Output:

"example":[-22, 6), "example":[0, 4), "example":[2, 3), "example":[3, 7), "example":[5, 10), "example":[8, 12), "example":[34, 61)

func (Tree) Intersect 

func (self Tree) Intersect(i *Interval, overlap int) (result chan *Interval)

Find all intervals in Tree that overlap query. Return a channel that will convey results.

The overlap parameter determines how much overlap is required: 

overlap < 0 intervals can be up to overlap away
overlap = 0 intervals abut
overlap > 0 intervals must overlap by overlap
Example 
tree := CreateExampleTree("example", [][]int{{0, 4}, {8, 12}, {2, 3}, {5, 10}, {3, 7}, {-22, 6}, {34, 61}})
if i, err := New("example", -15, -2, 0, nil); err == nil {
	for s := range tree.Intersect(i, 0) {
		fmt.Printf("%s\n", s)
	}
}

Output:

"example":[-22, 6)

func (Tree) LeftMost 

func (self Tree) LeftMost(seg string) *Interval

Return the left most interval in the segment's tree.

func (Tree) Merge 

func (self Tree) Merge(i *Interval, overlap int) (replaced []*Interval)

Merge an Interval into the Tree.

Example 
tree := CreateExampleTree("example", [][]int{{0, 4}, {8, 12}, {2, 3}, {5, 10}, {3, 7}, {34, 61}})
chromosome := "example"
segments := [][]int{{0, 1}, {27, 42}}
inserted := []*Interval{}
replaced := []*Interval{}

for _, s := range segments {
	if i, err := New(chromosome, s[0], s[1], 0, nil); err == nil {
		o := tree.Merge(i, 0)
		inserted = append(inserted, i)
		replaced = append(replaced, o...)
	} else {
		fmt.Println(err)
	}
}

fmt.Println("Inserted")
for _, s := range inserted {
	fmt.Printf("%s\n", s)
}

fmt.Println("Replaced")
for _, s := range replaced {
	fmt.Printf("%s\n", s)
}

PrintAll(tree)

Output:

Inserted
"example":[0, 4)
"example":[27, 61)
Replaced
"example":[0, 4)
"example":[34, 61)
"example":[0, 4), "example":[2, 3), "example":[3, 7), "example":[5, 10), "example":[8, 12), "example":[27, 61)

func (Tree) Range 

func (self Tree) Range(seg string) (min, max int)

Return the range of the tree's span

func (Tree) Remove 

func (self Tree) Remove(i *Interval) (removed *Interval)

Remove an interval, returning the removed interval with all pointers set to nil.

Example 
tree := CreateExampleTree("example", [][]int{{0, 4}, {8, 12}, {2, 3}, {5, 10}, {3, 7}, {-22, 6}, {34, 61}})
if i, err := New("example", -15, -2, 0, nil); err == nil {
	for s := range tree.Intersect(i, 0) {
		r := tree.Remove(s)
		fmt.Println(r, r.Left(), r.Right(), r.Parent())
	}
}

PrintAll(tree)

Output:

"example":[-22, 6) <nil> <nil> <nil>
"example":[0, 4), "example":[2, 3), "example":[3, 7), "example":[5, 10), "example":[8, 12), "example":[34, 61)

func (Tree) RightMost 

func (self Tree) RightMost(seg string) *Interval

Return the right-most interval in the segment's tree.

func (Tree) Traverse 

func (self Tree) Traverse(seg string) (result chan *Interval)

Traverse all intervals for a segment in Tree in order. Return a channel that will convey results.

func (Tree) TraverseAll 

func (self Tree) TraverseAll() (result chan *Interval)

Traverse all intervals in Tree in order (chromosomes in hash order). Return a channel that will convey results.

Example 
tree := CreateExampleTree("example", [][]int{{0, 4}, {8, 12}, {2, 3}, {5, 10}, {3, 7}, {27, 61}})
segs := []string{}
for i := range tree.TraverseAll() {
	segs = append(segs, i.String())
}
fmt.Println(strings.Join(segs, ", "))

Output:

"example":[0, 4), "example":[2, 3), "example":[3, 7), "example":[5, 10), "example":[8, 12), "example":[27, 61)

func (Tree) Within 

func (self Tree) Within(i *Interval, slop int) (result chan *Interval)

Find all intervals in Tree that are entirely contained by query. Return a channel that will convey results.

The slop parameter determines how much slop is allowed: 

slop < 0 intervals must be within query by slop
slop = 0 intervals may completely coincide
slop > 0 intervals may extend beyond query by slop
Example 
tree := CreateExampleTree("example", [][]int{{0, 4}, {8, 12}, {2, 3}, {5, 10}, {3, 7}, {-22, 6}, {34, 61}})
if i, err := New("example", 1, 5, 0, nil); err == nil {
	for s := range tree.Within(i, 0) {
		fmt.Printf("%s\n", s)
	}
}

Output:

"example":[2, 3)

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.