interval

package
v1.6.1 Latest Latest
Warning

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

Go to latest
Published: Jul 26, 2019 License: Apache-2.0 Imports: 2 Imported by: 82

Documentation

Overview

Package interval implements algorithms that operate on lists of intervals.

Index

Constants

This section is empty.

Variables

This section is empty.

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(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 added in v1.3.1

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 added in v1.3.1

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 added in v1.3.1

type ValueSpan struct {
	Span  U64Span
	Value interface{}
}

type ValueSpanList added in v1.3.1

type ValueSpanList []ValueSpan

func (*ValueSpanList) Copy added in v1.3.1

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

Copy count list entries Implements `MutableList.Copy`

func (*ValueSpanList) Delete added in v1.3.1

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

func (*ValueSpanList) GetSpan added in v1.3.1

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 added in v1.3.1

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

func (*ValueSpanList) Insert added in v1.3.1

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

func (*ValueSpanList) Length added in v1.3.1

func (l *ValueSpanList) Length() int

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

func (*ValueSpanList) New added in v1.3.1

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 added in v1.3.1

func (l *ValueSpanList) Resize(length int)

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

func (*ValueSpanList) SetSpan added in v1.3.1

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 added in v1.3.1

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

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL