ranger

Documentation

Overview

Package ranger provides a way to take a function expressed as cartesian points, downsample the points to a bounded number of bins by computing a range of the points that represent the downsampled bins (called the Envelope), then querying the Envelope with a range to find the smallest domain of X values that cover the range queried. A useful application of this is to index a very large file comprised of chunks of data tagged say by time, then arrange the seek offsets of the file as the X values and the time stamps as the Y values to determine the min and max seek offsets into a file that will cover a given time range. This is robust to out-of-order data chunks and performs best if the data is mostly in order, but performs correctly for any data order.

Index

• type Bin
• type Domain
• type Envelope
  • func NewEnvelope(offsets []Point, nbin int) Envelope
  • func (e Envelope) FindSmallestDomain(r Range) Domain
  • func (e Envelope) Merge(u Envelope) Envelope
• type Point
• type Range
  • func (a Range) Overlaps(b Range) bool

Types

type Bin

type Bin struct {
	X uint64
	Range
}

Bin defines a subsampled range of Y values comprising the Range, which starts at coordinate X and ends at coordinate X of the next bin.

type Domain

type Domain struct {
	X0 uint64
	X1 uint64
}

type Envelope

type Envelope []Bin

func NewEnvelope

func NewEnvelope(offsets []Point, nbin int) Envelope

NewEnvelope creates a range envelope structure used by FindSmallestDomain. The X field of the Points must be in non-decreasing order.

func (Envelope) FindSmallestDomain

func (e Envelope) FindSmallestDomain(r Range) Domain

FindSmallestDomain finds the smallest domain that covers the indicated range from the data points comprising the binned envelope.

func (Envelope) Merge

func (e Envelope) Merge(u Envelope) Envelope

Merge squashes the two envelopes together returning a new Envelope the size of the longest Envelope provided.

type Point

type Point struct {
	X uint64
	Y uint64
}

type Range

type Range struct {
	Y0 uint64
	Y1 uint64
}

func (Range) Overlaps

func (a Range) Overlaps(b Range) bool