diff options
Diffstat (limited to 'vendor/github.com/google/go-intervals/intervalset/intervalset.go')
| -rw-r--r-- | vendor/github.com/google/go-intervals/intervalset/intervalset.go | 545 |
1 files changed, 545 insertions, 0 deletions
diff --git a/vendor/github.com/google/go-intervals/intervalset/intervalset.go b/vendor/github.com/google/go-intervals/intervalset/intervalset.go new file mode 100644 index 000000000..6a33db63c --- /dev/null +++ b/vendor/github.com/google/go-intervals/intervalset/intervalset.go @@ -0,0 +1,545 @@ +// Copyright 2017 Google Inc. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +// Package intervalset provides an abtraction for dealing with sets of +// 1-dimensional spans, such as sets of time ranges. The Set type provides set +// arithmetic and enumeration methods based on an Interval interface. +// +// DISCLAIMER: This library is not yet stable, so expect breaking changes. +package intervalset + +import ( + "fmt" + "sort" + "strings" +) + +// Interval is the interface for a continuous or discrete span. The interval is +// assumed to be inclusive of the starting point and exclusive of the ending +// point. +// +// All methods in the interface are non-destructive: Calls to the methods should +// not modify the interval. Furthermore, the implementation assumes an interval +// will not be mutated by user code, either. +type Interval interface { + // Intersect returns the intersection of an interval with another + // interval. The function may panic if the other interval is incompatible. + Intersect(Interval) Interval + + // Before returns true if the interval is completely before another interval. + Before(Interval) bool + + // IsZero returns true for the zero value of an interval. + IsZero() bool + + // Bisect returns two intervals, one on the lower side of x and one on the + // upper side of x, corresponding to the subtraction of x from the original + // interval. The returned intervals are always within the range of the + // original interval. + Bisect(x Interval) (Interval, Interval) + + // Adjoin returns the union of two intervals, if the intervals are exactly + // adjacent, or the zero interval if they are not. + Adjoin(Interval) Interval + + // Encompass returns an interval that covers the exact extents of two + // intervals. + Encompass(Interval) Interval +} + +// Set is a set of interval objects used for +type Set struct { + //non-overlapping intervals + intervals []Interval + // factory is needed when the extents of the empty set are needed. + factory intervalFactory +} + +// SetInput is an interface implemented by Set and ImmutableSet. It is used when +// one of these types type must take a set as an argument. +type SetInput interface { + // Extent returns the Interval defined by the minimum and maximum values of + // the set. + Extent() Interval + + // IntervalsBetween iterates over the intervals within extents set and calls f + // with each. If f returns false, iteration ceases. + // + // Any interval within the set that overlaps partially with extents is truncated + // before being passed to f. + IntervalsBetween(extents Interval, f IntervalReceiver) +} + +// NewSet returns a new set given a sorted slice of intervals. This function +// panics if the intervals are not sorted. +func NewSet(intervals []Interval) *Set { + return NewSetV1(intervals, oldBehaviorFactory.makeZero) +} + +// NewSetV1 returns a new set given a sorted slice of intervals. This function +// panics if the intervals are not sorted. +// +// NewSetV1 will be renamed and will replace NewSet in the v1 release. +func NewSetV1(intervals []Interval, makeZero func() Interval) *Set { + if err := CheckSorted(intervals); err != nil { + panic(err) + } + return &Set{intervals, makeIntervalFactor(makeZero)} +} + +// CheckSorted checks that interval[i+1] is not before interval[i] for all +// relevant elements of the input slice. Nil is returned when len(intervals) is +// 0 or 1. +func CheckSorted(intervals []Interval) error { + for i := 0; i < len(intervals)-1; i++ { + if !intervals[i].Before(intervals[i+1]) { + return fmt.Errorf("!intervals[%d].Before(intervals[%d]) for %s, %s", i, i+1, intervals[i], intervals[i+1]) + } + } + return nil +} + +// Empty returns a new, empty set of intervals. +func Empty() *Set { + return EmptyV1(oldBehaviorFactory.makeZero) +} + +// EmptyV1 returns a new, empty set of intervals using the semantics of the V1 +// API, which will require a factory method for construction of an empty interval. +func EmptyV1(makeZero func() Interval) *Set { + return &Set{nil, makeIntervalFactor(makeZero)} +} + +// Copy returns a copy of a set that may be mutated without affecting the original. +func (s *Set) Copy() *Set { + return &Set{append([]Interval(nil), s.intervals...), s.factory} +} + +// String returns a human-friendly representation of the set. +func (s *Set) String() string { + var strs []string + for _, x := range s.intervals { + strs = append(strs, fmt.Sprintf("%s", x)) + } + return fmt.Sprintf("{%s}", strings.Join(strs, ", ")) +} + +// Extent returns the Interval defined by the minimum and maximum values of the +// set. +func (s *Set) Extent() Interval { + if len(s.intervals) == 0 { + return s.factory.makeZero() + } + return s.intervals[0].Encompass(s.intervals[len(s.intervals)-1]) +} + +// Add adds all the elements of another set to this set. +func (s *Set) Add(b SetInput) { + // Deal with nil extent. See https://github.com/google/go-intervals/issues/6. + bExtent := b.Extent() + if bExtent == nil { + return // no changes needed + } + + // Loop through the intervals of x + b.IntervalsBetween(bExtent, func(x Interval) bool { + s.insert(x) + return true + }) +} + +// Contains reports whether an interval is entirely contained by the set. +func (s *Set) Contains(ival Interval) bool { + // Loop through the intervals of x + next := s.iterator(ival, true) + for setInterval := next(); setInterval != nil; setInterval = next() { + left, right := ival.Bisect(setInterval) + if !left.IsZero() { + return false + } + ival = right + } + return ival.IsZero() +} + +// adjoinOrAppend adds an interval to the end of intervals unless that value +// directly adjoins the last element of intervals, in which case the last +// element will be replaced by the adjoined interval. +func adjoinOrAppend(intervals []Interval, x Interval) []Interval { + lastIndex := len(intervals) - 1 + if lastIndex == -1 { + return append(intervals, x) + } + adjoined := intervals[lastIndex].Adjoin(x) + if adjoined.IsZero() { + return append(intervals, x) + } + intervals[lastIndex] = adjoined + return intervals +} + +func (s *Set) insert(insertion Interval) { + if s.Contains(insertion) { + return + } + // TODO(reddaly): Something like Java's ArrayList would allow both O(log(n)) + // insertion and O(log(n)) lookup. For now, we have O(log(n)) lookup and O(n) + // insertion. + var newIntervals []Interval + push := func(x Interval) { + newIntervals = adjoinOrAppend(newIntervals, x) + } + inserted := false + for _, x := range s.intervals { + if inserted { + push(x) + continue + } + if insertion.Before(x) { + push(insertion) + push(x) + inserted = true + continue + } + // [===left===)[==x===)[===right===) + left, right := insertion.Bisect(x) + if !left.IsZero() { + push(left) + } + push(x) + // Replace the interval being inserted with the remaining portion of the + // interval to be inserted. + if right.IsZero() { + inserted = true + } else { + insertion = right + } + } + if !inserted { + push(insertion) + } + s.intervals = newIntervals +} + +// Sub destructively modifies the set by subtracting b. +func (s *Set) Sub(b SetInput) { + extent := s.Extent() + // Deal with nil extent. See https://github.com/google/go-intervals/issues/6. + if extent == nil { + // Set is already empty, no changes necessary. + return + } + var newIntervals []Interval + push := func(x Interval) { + newIntervals = adjoinOrAppend(newIntervals, x) + } + nextX := s.iterator(extent, true) + nextY, cancel := setIntervalIterator(b, extent) + defer cancel() + + x := nextX() + y := nextY() + for x != nil { + // If y == nil, all of the remaining intervals in A are to the right of B, + // so just yield them. + if y == nil { + push(x) + x = nextX() + continue + } + // Split x into parts left and right of y. + // The diagrams below show the bisection results for various situations. + // if left.IsZero() && !right.IsZero() + // xxx + // y1y1 y2y2 y3 y4y4 + // xxx + // or + // xxxxxxxxxxxx + // y1y1 y2y2 y3 y4y4 + // + // if !left.IsZero() && !right.IsZero() + // x1x1x1x1x1 + // y1 y2 + // + // if left.IsZero() && right.IsZero() + // x1x1x1x1 x2x2x2 + // y1y1y1y1y1y1y1 + // + // if !left.IsZero() && right.IsZero() + // x1x1 x2 + // y1y1y1y1 + left, right := x.Bisect(y) + + // If the left side of x is non-zero, it can definitely be pushed to the + // resulting interval set since no subsequent y value will intersect it. + // The sequences look something like + // x1x1x1x1x1 OR x1x1x1 x2 + // y1 y2 y1y1y1 + // left = x1x1 x1x1x1 + // right = x1x1 {zero} + if !left.IsZero() { + push(left) + } + + if !right.IsZero() { + // If the right side of x is non-zero: + // 1) Right is the remaining portion of x that needs to be pushed. + x = right + // 2) It's not possible for current y to intersect it, so advance y. It's + // possible nextY() will intersect it, so don't push yet. + y = nextY() + } else { + // There's nothing left of x to push, so advance x. + x = nextX() + } + } + + // Setting s.intervals is the only side effect in this function. + s.intervals = newIntervals +} + +// intersectionIterator returns a function that yields intervals that are +// members of the intersection of s and b, in increasing order. +func (s *Set) intersectionIterator(b SetInput) (iter func() Interval, cancel func()) { + return intervalMapperToIterator(func(f IntervalReceiver) { + sExtent, bExtent := s.Extent(), b.Extent() + // Deal with nil extent. See https://github.com/google/go-intervals/issues/6. + if sExtent == nil || bExtent == nil { + // IF either set is already empty, the intersection is empty. This + // voids a panic below where a valid Interval is needed for each + // extent. + return + } + nextX := s.iterator(bExtent, true) + nextY, cancel := setIntervalIterator(b, sExtent) + defer cancel() + + x := nextX() + y := nextY() + // Loop through corresponding intervals of S and B. + // If y == nil, all of the remaining intervals in S are to the right of B. + // If x == nil, all of the remaining intervals in B are to the right of S. + for x != nil && y != nil { + if x.Before(y) { + x = nextX() + continue + } + if y.Before(x) { + y = nextY() + continue + } + xyIntersect := x.Intersect(y) + if !xyIntersect.IsZero() { + if !f(xyIntersect) { + return + } + _, right := x.Bisect(y) + if !right.IsZero() { + x = right + } else { + x = nextX() + } + } + } + }) +} + +// Intersect destructively modifies the set by intersectin it with b. +func (s *Set) Intersect(b SetInput) { + iter, cancel := s.intersectionIterator(b) + defer cancel() + var newIntervals []Interval + for x := iter(); x != nil; x = iter() { + newIntervals = append(newIntervals, x) + } + s.intervals = newIntervals +} + +// searchLow returns the first index in s.intervals that is not before x. +func (s *Set) searchLow(x Interval) int { + return sort.Search(len(s.intervals), func(i int) bool { + return !s.intervals[i].Before(x) + }) +} + +// searchLow returns the index of the first interval in s.intervals that is +// entirely after x. +func (s *Set) searchHigh(x Interval) int { + return sort.Search(len(s.intervals), func(i int) bool { + return x.Before(s.intervals[i]) + }) +} + +// iterator returns a function that yields elements of the set in order. +// +// The function returned will return nil when finished iterating. +func (s *Set) iterator(extents Interval, forward bool) func() Interval { + low, high := s.searchLow(extents), s.searchHigh(extents) + + i, stride := low, 1 + if !forward { + i, stride = high-1, -1 + } + + return func() Interval { + if i < 0 || i >= len(s.intervals) { + return nil + } + x := s.intervals[i] + i += stride + return x + } +} + +// IntervalReceiver is a function used for iterating over a set of intervals. It +// takes the start and end times and returns true if the iteration should +// continue. +type IntervalReceiver func(Interval) bool + +// IntervalsBetween iterates over the intervals within extents set and calls f +// with each. If f returns false, iteration ceases. +// +// Any interval within the set that overlaps partially with extents is truncated +// before being passed to f. +func (s *Set) IntervalsBetween(extents Interval, f IntervalReceiver) { + // Begin = first index in s.intervals that is not before extents. + begin := sort.Search(len(s.intervals), func(i int) bool { + return !s.intervals[i].Before(extents) + }) + + // TODO(reddaly): Optimize this by performing a binary search for the ending + // point. + for _, interval := range s.intervals[begin:] { + // If the interval is after the extents, there will be no more overlap, so + // break out of the loop. + if extents.Before(interval) { + break + } + portionOfInterval := extents.Intersect(interval) + if portionOfInterval.IsZero() { + continue + } + + if !f(portionOfInterval) { + return + } + } +} + +// Intervals iterates over all the intervals within the set and calls f with +// each one. If f returns false, iteration ceases. +func (s *Set) Intervals(f IntervalReceiver) { + for _, interval := range s.intervals { + if !f(interval) { + return + } + } +} + +// AllIntervals returns an ordered slice of all the intervals in the set. +func (s *Set) AllIntervals() []Interval { + return append(make([]Interval, 0, len(s.intervals)), s.intervals...) +} + +// ImmutableSet returns an immutable copy of this set. +func (s *Set) ImmutableSet() *ImmutableSet { + return NewImmutableSet(s.AllIntervals()) +} + +// mapFn reports true if an iteration should continue. It is called on values of +// a collection. +type mapFn func(interface{}) bool + +// mapFn calls mapFn for each member of a collection. +type mapperFn func(mapFn) + +// iteratorFn returns the next item in an iteration or the zero value. The +// second return value indicates whether the first return value is a member of +// the collection. +type iteratorFn func() (interface{}, bool) + +// generatorFn returns an iterator. +type generatorFn func() iteratorFn + +// cancelFn should be called to clean up the goroutine that would otherwise leak. +type cancelFn func() + +// mapperToIterator returns an iteratorFn version of a mappingFn. The second +// return value must be called at the end of iteration, or the underlying +// goroutine will leak. +func mapperToIterator(m mapperFn) (iteratorFn, cancelFn) { + generatedValues := make(chan interface{}, 1) + stopCh := make(chan interface{}, 1) + go func() { + m(func(obj interface{}) bool { + select { + case <-stopCh: + return false + case generatedValues <- obj: + return true + } + }) + close(generatedValues) + }() + iter := func() (interface{}, bool) { + value, ok := <-generatedValues + return value, ok + } + return iter, func() { + stopCh <- nil + } +} + +func intervalMapperToIterator(mapper func(IntervalReceiver)) (iter func() Interval, cancel func()) { + genericMapper := func(m mapFn) { + mapper(func(ival Interval) bool { + return m(ival) + }) + } + + genericIter, cancel := mapperToIterator(genericMapper) + return func() Interval { + genericVal, iterationEnded := genericIter() + if !iterationEnded { + return nil + } + ival, ok := genericVal.(Interval) + if !ok { + panic("unexpected value type, internal error") + } + return ival + }, cancel +} + +func setIntervalIterator(s SetInput, extent Interval) (iter func() Interval, cancel func()) { + return intervalMapperToIterator(func(f IntervalReceiver) { + s.IntervalsBetween(extent, f) + }) +} + +// oldBehaviorFactory returns a nil interval. This was used before +// construction of a Set/ImmutableSet required passing in a factory method for +// creating a zero interval object. +var oldBehaviorFactory = makeIntervalFactor(func() Interval { return nil }) + +// intervalFactory is used to construct a zero-value interval. The zero value +// interval may be different for different types of intervals, so a factory is +// sometimes needed to write generic algorithms about intervals. +type intervalFactory struct { + makeZero func() Interval +} + +func makeIntervalFactor(makeZero func() Interval) intervalFactory { + return intervalFactory{makeZero} +} |