interval

package
v0.0.0-...-7b6cf24 Latest Latest
Warning

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

 Go to latest Published: Mar 27, 2012 License: GPL-3.0 Imports: 7 Imported by: 0

Documentation

Overview

Package to find intersections between intervals or sort intervals.

Index

Examples

Constants

View Source 
const Version int = 1

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(chrom string, start, end, line int, meta interface{}) (*Interval, error)

Create a new Interval.

func (*Interval) Chromosome 

func (self *Interval) Chromosome() string

Return the chromosome identifier for an Interval node.

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. 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

func (*Interval) End 

func (self *Interval) End() int

Return the end position of an Interval node.

func (*Interval) Flatten 

func (self *Interval) Flatten(r chan *Interval, tolerance int) (flat []*Interval, rich [][]*Interval)

Merge a range of intervals provided by r. Returns merged intervals in a slice and intervals contributing to merged intervals groups in a slice of slices.

func (*Interval) GobDecode 

func (self *Interval) GobDecode(b []byte) (err error)

func (*Interval) GobEncode 

func (self *Interval) GobEncode() (b []byte, err error)

func (*Interval) Insert 

func (self *Interval) Insert(i *Interval) (root *Interval)

Insert an Interval into a tree returning the new root. Receiver should be the root of the tree.

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. 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

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)

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) Remove 

func (self *Interval) Remove() (root, removed *Interval)

Remove an interval. Returns the new root of the subtree and the removed interval.

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)

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) 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. 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

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 chromosome name, reducing search time and easing coding.

func NewTree 

func NewTree() Tree

Create a new interval Tree.

func (Tree) AdjustRange 

func (self Tree) AdjustRange(chromosome 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.

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.

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. 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. 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. 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.

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) Merge 

func (self Tree) Merge(i *Interval, overlap int) (inserted, 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 {
		n, o := tree.Merge(i, 0)
		inserted = append(inserted, n...)
		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(chromosome 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) Traverse 

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

Traverse all intervals for a chromosome 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.

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.