interval

Documentation

Overview

Package interval implements algorithms that operate on lists of intervals.

Index

• func Contains(l List, value uint64) bool
• func IndexOf(l List, value uint64) int
• func Intersect(l List, span U64Span) (first, count int)
• func Merge(l MutableList, span U64Span, joinAdj bool) int
• func Remove(l MutableList, span U64Span)
• func Replace(l MutableList, span U64Span) int
• func Search(l List, t Predicate) int
• func Update(l ValueList, span U64Span, f func(interface{}) interface{})
• type List
• type MutableList
• type Predicate
• type U64Range
  • func (r U64Range) Span() U64Span
• type U64RangeList
  • func (l U64RangeList) Clone() U64RangeList
  • func (l U64RangeList) Copy(to, from, count int)
  • func (l U64RangeList) GetSpan(index int) U64Span
  • func (l U64RangeList) Length() int
  • func (l U64RangeList) New(index int, span U64Span)
  • func (l *U64RangeList) Resize(length int)
  • func (l U64RangeList) SetSpan(index int, span U64Span)
• type U64Span
  • func (s U64Span) Range() U64Range
• type U64SpanList
  • func (l U64SpanList) Copy(to, from, count int)
  • func (l U64SpanList) GetSpan(index int) U64Span
  • func (l U64SpanList) Length() int
  • func (l U64SpanList) New(index int, span U64Span)
  • func (l *U64SpanList) Resize(length int)
  • func (l U64SpanList) SetSpan(index int, span U64Span)
• type ValueList
• type ValueSpan
• type ValueSpanList
  • func (l *ValueSpanList) Copy(to, from, count int)
  • func (l *ValueSpanList) Delete(index int, count int)
  • func (l *ValueSpanList) GetSpan(index int) U64Span
  • func (l ValueSpanList) GetValue(index int) interface{}
  • func (l *ValueSpanList) Insert(index int, count int)
  • func (l *ValueSpanList) Length() int
  • func (l *ValueSpanList) New(index int, span U64Span)
  • func (l *ValueSpanList) Resize(length int)
  • func (l *ValueSpanList) SetSpan(index int, span U64Span)
  • func (l *ValueSpanList) SetValue(index int, value interface{})

Functions

func Contains

func Contains(l List, value uint64) bool

Contains returns true if the value is found inside on of the intervals.

func IndexOf

func IndexOf(l List, value uint64) int

IndexOf returns the index of the span the value is a part of, or -1 if not found

func Intersect

func Intersect(l List, span U64Span) (first, count int)

Intersect finds the intervals from the list that overlap with the specified span.

func Merge

func Merge(l MutableList, span U64Span, joinAdj bool) int

Merge adds a span to the list, merging it with existing spans if it overlaps them, and returns the index of that span. If the joinAdj parameter is true, then any intervals that are immediately adjacent to span will be merged with span. For example, consider the merging of intervals [0, 2] and [3, 5]:

When joinAdj == false:

╭       ╮       ╭       ╮   ╭       ╮╭       ╮
│0  1  2│ merge │3  4  5│ = │0  1  2││3  4  5│
╰       ╯       ╰       ╯   ╰       ╯╰       ╯

When join == true:

╭       ╮       ╭       ╮   ╭                ╮
│0  1  2│ merge │3  4  5│ = │0  1  2  3  4  5│
╰       ╯       ╰       ╯   ╰                ╯

func Remove

func Remove(l MutableList, span U64Span)

Remove strips the specified span from the list, cutting it out of any overlapping intervals

func Replace

func Replace(l MutableList, span U64Span) int

Replace cuts the span out of any existing intervals, and then adds a new interval, and returns its index.

func Search

func Search(l List, t Predicate) int

Search finds the first interval in the list that the supplied predicate returns true for. If no interval matches the predicate, it returns the length of the list.

func Update

func Update(l ValueList, span U64Span, f func(interface{}) interface{})

Update modifies the values in `span` by applying the function `f`.

• Parts of `span` that are outside the intervals in `l` are inserted with value `f(nil)`.
• If `f` returns `nil`, the corresponding span is removed.
• Adjacent intervals with the same value are merged.

Types

type List

type List interface {
	// Length returns the number of elements in the list
	Length() int
	// GetSpan returns the span for the element at index in the list
	GetSpan(index int) U64Span
}

List is the interface to an object that can be used as an interval list by the algorithms in this package.

type MutableList

type MutableList interface {
	List
	// SetSpan sets the span for the element at index in the list
	SetSpan(index int, span U64Span)
	// New creates a new element at the specifed index with the specified span
	New(index int, span U64Span)
	// Copy count list entries
	Copy(to, from, count int)
	// Resize adjusts the length of the array
	Resize(length int)
}

MutableList is a mutable form of a List.

type Predicate

type Predicate func(test U64Span) bool

Predicate is used as the condition for a Search

type U64Range

type U64Range struct {
	First uint64 // the first value in the interval
	Count uint64 // the count of values in the interval
}

U64Range is an interval specified by a beginning and size.

func (U64Range) Span

func (r U64Range) Span() U64Span

Span converts a U64Range to a U64Span

type U64RangeList

type U64RangeList []U64Range

U64RangeList implements List for an array of U64Range intervals

func (U64RangeList) Clone

func (l U64RangeList) Clone() U64RangeList

func (U64RangeList) Copy

func (l U64RangeList) Copy(to, from, count int)

func (U64RangeList) GetSpan

func (l U64RangeList) GetSpan(index int) U64Span

func (U64RangeList) Length

func (l U64RangeList) Length() int

func (U64RangeList) New

func (l U64RangeList) New(index int, span U64Span)

func (*U64RangeList) Resize

func (l *U64RangeList) Resize(length int)

func (U64RangeList) SetSpan

func (l U64RangeList) SetSpan(index int, span U64Span)

type U64Span

type U64Span struct {
	Start uint64 // the value at which the interval begins
	End   uint64 // the next value not included in the interval.
}

U64Span is the base interval type understood by the algorithms in this package. It is a half open interval that includes the lower bound, but not the upper.

func (U64Span) Range

func (s U64Span) Range() U64Range

Range converts a U64Span to a U64Range

type U64SpanList

type U64SpanList []U64Span

U64SpanList implements List for an array of U64Span intervals

func (U64SpanList) Copy

func (l U64SpanList) Copy(to, from, count int)

func (U64SpanList) GetSpan

func (l U64SpanList) GetSpan(index int) U64Span

func (U64SpanList) Length

func (l U64SpanList) Length() int

func (U64SpanList) New

func (l U64SpanList) New(index int, span U64Span)

func (*U64SpanList) Resize

func (l *U64SpanList) Resize(length int)

func (U64SpanList) SetSpan

func (l U64SpanList) SetSpan(index int, span U64Span)

type ValueList

type ValueList interface {
	MutableList
	GetValue(index int) interface{}
	SetValue(index int, value interface{})
	Insert(index int, count int)
	Delete(index int, count int)
}

type ValueSpan

type ValueSpan struct {
	Span  U64Span
	Value interface{}
}

type ValueSpanList

type ValueSpanList []ValueSpan

func (*ValueSpanList) Copy

func (l *ValueSpanList) Copy(to, from, count int)

Copy count list entries Implements `MutableList.Copy`

func (*ValueSpanList) Delete

func (l *ValueSpanList) Delete(index int, count int)

func (*ValueSpanList) GetSpan

func (l *ValueSpanList) GetSpan(index int) U64Span

GetSpan returns the span for the element at index in the list Implements `List.GetSpan`

func (ValueSpanList) GetValue

func (l ValueSpanList) GetValue(index int) interface{}

func (*ValueSpanList) Insert

func (l *ValueSpanList) Insert(index int, count int)

func (*ValueSpanList) Length

func (l *ValueSpanList) Length() int

Length returns the number of elements in the list Implements `List.Length`

func (*ValueSpanList) New

func (l *ValueSpanList) New(index int, span U64Span)

New creates a new element at the specifed index with the specified span Implements `MutableList.New`

func (*ValueSpanList) Resize

func (l *ValueSpanList) Resize(length int)

Resize adjusts the length of the array Implements `MutableList.Resize`

func (*ValueSpanList) SetSpan

func (l *ValueSpanList) SetSpan(index int, span U64Span)

SetSpan sets the span for the element at index in the list Implements `MutableList.SetSpan`

func (*ValueSpanList) SetValue

func (l *ValueSpanList) SetValue(index int, value interface{})