intervals

README

intervals

A Go library for manipulating sets of intervals.

Documentation

Overview

Package intervals is a library for manipulating sets of intervals.

Index

• type Elem
• type Enum
• type Interval
  • func Range[E Elem[E]](lo, hi E) Interval[E]
  • func Unit[E Enum[E]](v E) Interval[E]
  • func (r Interval[E]) Equal(r2 Interval[E]) bool
  • func (r Interval[E]) IsValid() bool
  • func (r Interval[E]) Set() Set[E]
• type Set
  • func Add[E Elem[E]](x Set[E], s ...Interval[E]) Set[E]
  • func Collect[E Elem[E]](s ...Interval[E]) Set[E]
  • func CollectInto[E Elem[E]](x Set[E], s ...Interval[E]) Set[E]
  • func Delete[E Elem[E]](x Set[E], s ...Interval[E]) Set[E]
  • func Difference[E Elem[E]](z, x, y Set[E]) Set[E]
  • func Intersection[E Elem[E]](z, x, y Set[E]) Set[E]
  • func Reduce[E Elem[E]](op func(z, x, y Set[E]) Set[E], sets ...Set[E]) Set[E]
  • func SymmetricDifference[E Elem[E]](z, x, y Set[E]) Set[E]
  • func Union[E Elem[E]](z, x, y Set[E]) Set[E]
  • func (x Set[E]) Contains(r Interval[E]) bool
  • func (x Set[E]) ContainsUnit(v E) bool
  • func (x Set[E]) Difference(y Set[E]) Set[E]
  • func (x Set[E]) Equal(y Set[E]) bool
  • func (x Set[E]) Extent() Interval[E]
  • func (x Set[E]) Intersection(y Set[E]) Set[E]
  • func (x Set[E]) IsSubsetOf(y Set[E]) bool
  • func (x Set[E]) Overlaps(y Set[E]) bool
  • func (x Set[E]) SymmetricDifference(y Set[E]) Set[E]
  • func (x Set[E]) Union(y Set[E]) Set[E]

Types

type Elem

type Elem[E any] interface {
	Compare(E) int
}

Elem is the type set containing all supported element types.

type Enum

type Enum[E any] interface {
	Elem[E]
	Next() E
}

An Enum is a computably enumerable Elem. There exists a computable enumeration that lists elements, in a valid Interval of Enum, in an increasing ordering determined by the Compare method.

type Interval

type Interval[E Elem[E]] struct {
	Low  E // inclusive
	High E // exclusive
}

An Interval is a half-open continuous range of elements.

func Range

func Range[E Elem[E]](lo, hi E) Interval[E]

Range returns an Interval of range [lo, hi). If lo.Compare(hi) >= 0, Range returns an invalid Interval. Note that calling Set method on an invalid Interval panics.

func Unit

func Unit[E Enum[E]](v E) Interval[E]

Unit returns an Interval that only contains a single element v. If there is no element next to v, Unit returns an invalid Interval. Note that calling Set method on an invalid Interval panics.

func (Interval[E]) Equal

func (r Interval[E]) Equal(r2 Interval[E]) bool

Equal reports whether r is identical to r2.

func (Interval[E]) IsValid

func (r Interval[E]) IsValid() bool

IsValid reports whether r is a valid Interval. A valid Interval r either satisfies r.Low.Compare(r.High) < 0 or equals to the zero value.

func (Interval[E]) Set

func (r Interval[E]) Set() Set[E]

Set returns the set of elements that are in r. If r is the zero value, Set returns an empty set. If r is an invalid Interval, Set panics.

type Set

type Set[E Elem[E]] []Interval[E]

A Set is a slice of separate intervals sorted in ascending order. The zero value for a Set, i.e. a nil Set, is an empty set.

Since Intervals are half-open, the maximum value of E cannot be added into a Set.

func Add

func Add[E Elem[E]](x Set[E], s ...Interval[E]) Set[E]

Add adds zero or more Intervals into x, returning the modified Set.

func Collect

func Collect[E Elem[E]](s ...Interval[E]) Set[E]

Collect returns the set of elements that are in any of s.

Collect performs better if s are sorted in ascending order by the Low field.

func CollectInto

func CollectInto[E Elem[E]](x Set[E], s ...Interval[E]) Set[E]

CollectInto returns the set of elements that are in any of s, overwriting x. x and s can be the same slice. x must not be used after.

CollectInto performs better if s are sorted in ascending order by the Low field.

func Delete

func Delete[E Elem[E]](x Set[E], s ...Interval[E]) Set[E]

Delete removes zero or more Intervals from x, returning the modified Set.

func Difference

func Difference[E Elem[E]](z, x, y Set[E]) Set[E]

Difference returns the set of elements that are in x, but not in y, overwriting z. z must not be x or y and z must not be used after.

func Intersection

func Intersection[E Elem[E]](z, x, y Set[E]) Set[E]

Intersection returns the set of elements that are in both x and y, overwriting z. z must not be x or y and z must not be used after.

func Reduce

func Reduce[E Elem[E]](op func(z, x, y Set[E]) Set[E], sets ...Set[E]) Set[E]

Reduce applies set operation op over sets, returning the end result. op can be any of Difference, Intersection, SymmetricDifference and Union.

func SymmetricDifference

func SymmetricDifference[E Elem[E]](z, x, y Set[E]) Set[E]

SymmetricDifference returns the set of elements that are in one of x and y, but not in both, overwriting z. z must not be x or y and z must not be used after.

func Union

func Union[E Elem[E]](z, x, y Set[E]) Set[E]

Union returns the set of elements that are in either x, or y, or both, overwriting z. z must not be x or y and z must not be used after.

func (Set[E]) Contains

func (x Set[E]) Contains(r Interval[E]) bool

Contains reports whether x contains every element in range [r.Low, r.High).

func (Set[E]) ContainsUnit

func (x Set[E]) ContainsUnit(v E) bool

ContainsUnit reports whether x contains a single element v. Faster than x.Contains(Unit(v)).

func (Set[E]) Difference

func (x Set[E]) Difference(y Set[E]) Set[E]

Difference returns the set of elements that are in x, but not in y.

func (Set[E]) Equal

func (x Set[E]) Equal(y Set[E]) bool

Equal reports whether x is identical to y.

func (Set[E]) Extent

func (x Set[E]) Extent() Interval[E]

Extent returns the smallest Interval that contains every element in x.

If x is empty, Extent returns the zero value.

func (Set[E]) Intersection

func (x Set[E]) Intersection(y Set[E]) Set[E]

Intersection returns the set of elements that are in both x and y.

func (Set[E]) IsSubsetOf

func (x Set[E]) IsSubsetOf(y Set[E]) bool

IsSubsetOf reports whether elements in x are all in y.

func (Set[E]) Overlaps

func (x Set[E]) Overlaps(y Set[E]) bool

Overlaps reports whether the intersection of x and y is not empty.

func (Set[E]) SymmetricDifference

func (x Set[E]) SymmetricDifference(y Set[E]) Set[E]

SymmetricDifference returns the set of elements that are in one of x and y, but not in both.

func (Set[E]) Union

func (x Set[E]) Union(y Set[E]) Set[E]

Union returns the set of elements that are in either x, or y, or both.