intstab

README

intstab

A Golang Interval stabbing implementation for small integer ranges

As described in "Interval Stabbing Problems in Small Integer Ranges" Jens M. Schmidt, 2010

Assuming a set of intervals, I, it will find the answer to which intervals cover query q in o(1+k) time where k is the result set size. The output will be ordered.

Example usage:

intervals := IntervalSlice{
	{4, 15, "First"},
	{50, 72, "Second"},
	{34, 90, "Third"},
	{34, 45, "Fourth"},
	{34, 40, "Fifth"},
	{34, 34, "Sixth"},
	{34, 45, "Seventh"},
}

// Initialise
ts, _ := NewIntervalStabber(intervals)

// Query for intervals intersecting 42
results, _ := ts.Intersect(42)
  
// Results should be:
// [0].Tag = "Fourth"
// [1].Tag = "Seventh"
// [2].Tag = "Third"

Documentation

Overview

integer stabbing.

Index

• type Interval
  • func (a *Interval) Less(b *Interval) bool
  • func (i Interval) Stab(q uint16) bool
• type IntervalSlice
  • func (i IntervalSlice) Len() int
  • func (i IntervalSlice) Less(a, b int) bool
  • func (i IntervalSlice) Swap(a, b int)
• type IntervalStabber
  • func NewIntervalStabber(intervals IntervalSlice) (ts IntervalStabber, err error)
• type PooledSliceStack
  • func (s *PooledSliceStack) Len() int
  • func (s *PooledSliceStack) Pop() (v interface{})
  • func (s *PooledSliceStack) Push(v interface{})
• type Stack
  • func NewStack() Stack

Types

type Interval

type Interval struct {
	Start uint16
	End   uint16
	Tag   interface{}
}

* Public

func (*Interval) Less

func (a *Interval) Less(b *Interval) bool

for two intervals a and b, it holds a < b if la < lb or (la = lb ∧ ra ≤ rb). li = left (Start), ri = right (End)

func (Interval) Stab

func (i Interval) Stab(q uint16) bool

type IntervalSlice

type IntervalSlice []*Interval

func (IntervalSlice) Len

func (i IntervalSlice) Len() int

sort.Interface methods for []Interval

func (IntervalSlice) Less

func (i IntervalSlice) Less(a, b int) bool

func (IntervalSlice) Swap

func (i IntervalSlice) Swap(a, b int)

type IntervalStabber

type IntervalStabber interface {
	Intersect(uint16) ([]*Interval, error)
}

* Public

func NewIntervalStabber

func NewIntervalStabber(intervals IntervalSlice) (ts IntervalStabber, err error)

type PooledSliceStack

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

func (*PooledSliceStack) Len

func (s *PooledSliceStack) Len() int

func (*PooledSliceStack) Pop

func (s *PooledSliceStack) Pop() (v interface{})

func (*PooledSliceStack) Push

func (s *PooledSliceStack) Push(v interface{})

type Stack

type Stack interface {
	Push(interface{})
	Pop() interface{}
	Len() int
}

func NewStack

func NewStack() Stack