diff options
Diffstat (limited to 'vendor/github.com/google')
3 files changed, 832 insertions, 0 deletions
diff --git a/vendor/github.com/google/go-intervals/LICENSE b/vendor/github.com/google/go-intervals/LICENSE new file mode 100644 index 000000000..d64569567 --- /dev/null +++ b/vendor/github.com/google/go-intervals/LICENSE @@ -0,0 +1,202 @@ + + Apache License + Version 2.0, January 2004 + http://www.apache.org/licenses/ + + TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION + + 1. Definitions. + + "License" shall mean the terms and conditions for use, reproduction, + and distribution as defined by Sections 1 through 9 of this document. + + "Licensor" shall mean the copyright owner or entity authorized by + the copyright owner that is granting the License. + + "Legal Entity" shall mean the union of the acting entity and all + other entities that control, are controlled by, or are under common + control with that entity. For the purposes of this definition, + "control" means (i) the power, direct or indirect, to cause the + direction or management of such entity, whether by contract or + otherwise, or (ii) ownership of fifty percent (50%) or more of the + outstanding shares, or (iii) beneficial ownership of such entity. + + "You" (or "Your") shall mean an individual or Legal Entity + exercising permissions granted by this License. + + "Source" form shall mean the preferred form for making modifications, + including but not limited to software source code, documentation + source, and configuration files. + + "Object" form shall mean any form resulting from mechanical + transformation or translation of a Source form, including but + not limited to compiled object code, generated documentation, + and conversions to other media types. + + "Work" shall mean the work of authorship, whether in Source or + Object form, made available under the License, as indicated by a + copyright notice that is included in or attached to the work + (an example is provided in the Appendix below). + + "Derivative Works" shall mean any work, whether in Source or Object + form, that is based on (or derived from) the Work and for which the + editorial revisions, annotations, elaborations, or other modifications + represent, as a whole, an original work of authorship. For the purposes + of this License, Derivative Works shall not include works that remain + separable from, or merely link (or bind by name) to the interfaces of, + the Work and Derivative Works thereof. + + "Contribution" shall mean any work of authorship, including + the original version of the Work and any modifications or additions + to that Work or Derivative Works thereof, that is intentionally + submitted to Licensor for inclusion in the Work by the copyright owner + or by an individual or Legal Entity authorized to submit on behalf of + the copyright owner. For the purposes of this definition, "submitted" + means any form of electronic, verbal, or written communication sent + to the Licensor or its representatives, including but not limited to + communication on electronic mailing lists, source code control systems, + and issue tracking systems that are managed by, or on behalf of, the + Licensor for the purpose of discussing and improving the Work, but + excluding communication that is conspicuously marked or otherwise + designated in writing by the copyright owner as "Not a Contribution." + + "Contributor" shall mean Licensor and any individual or Legal Entity + on behalf of whom a Contribution has been received by Licensor and + subsequently incorporated within the Work. + + 2. Grant of Copyright License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + copyright license to reproduce, prepare Derivative Works of, + publicly display, publicly perform, sublicense, and distribute the + Work and such Derivative Works in Source or Object form. + + 3. Grant of Patent License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + (except as stated in this section) patent license to make, have made, + use, offer to sell, sell, import, and otherwise transfer the Work, + where such license applies only to those patent claims licensable + by such Contributor that are necessarily infringed by their + Contribution(s) alone or by combination of their Contribution(s) + with the Work to which such Contribution(s) was submitted. If You + institute patent litigation against any entity (including a + cross-claim or counterclaim in a lawsuit) alleging that the Work + or a Contribution incorporated within the Work constitutes direct + or contributory patent infringement, then any patent licenses + granted to You under this License for that Work shall terminate + as of the date such litigation is filed. + + 4. Redistribution. You may reproduce and distribute copies of the + Work or Derivative Works thereof in any medium, with or without + modifications, and in Source or Object form, provided that You + meet the following conditions: + + (a) You must give any other recipients of the Work or + Derivative Works a copy of this License; and + + (b) You must cause any modified files to carry prominent notices + stating that You changed the files; and + + (c) You must retain, in the Source form of any Derivative Works + that You distribute, all copyright, patent, trademark, and + attribution notices from the Source form of the Work, + excluding those notices that do not pertain to any part of + the Derivative Works; and + + (d) If the Work includes a "NOTICE" text file as part of its + distribution, then any Derivative Works that You distribute must + include a readable copy of the attribution notices contained + within such NOTICE file, excluding those notices that do not + pertain to any part of the Derivative Works, in at least one + of the following places: within a NOTICE text file distributed + as part of the Derivative Works; within the Source form or + documentation, if provided along with the Derivative Works; or, + within a display generated by the Derivative Works, if and + wherever such third-party notices normally appear. The contents + of the NOTICE file are for informational purposes only and + do not modify the License. You may add Your own attribution + notices within Derivative Works that You distribute, alongside + or as an addendum to the NOTICE text from the Work, provided + that such additional attribution notices cannot be construed + as modifying the License. + + You may add Your own copyright statement to Your modifications and + may provide additional or different license terms and conditions + for use, reproduction, or distribution of Your modifications, or + for any such Derivative Works as a whole, provided Your use, + reproduction, and distribution of the Work otherwise complies with + the conditions stated in this License. + + 5. Submission of Contributions. Unless You explicitly state otherwise, + any Contribution intentionally submitted for inclusion in the Work + by You to the Licensor shall be under the terms and conditions of + this License, without any additional terms or conditions. + Notwithstanding the above, nothing herein shall supersede or modify + the terms of any separate license agreement you may have executed + with Licensor regarding such Contributions. + + 6. Trademarks. This License does not grant permission to use the trade + names, trademarks, service marks, or product names of the Licensor, + except as required for reasonable and customary use in describing the + origin of the Work and reproducing the content of the NOTICE file. + + 7. Disclaimer of Warranty. Unless required by applicable law or + agreed to in writing, Licensor provides the Work (and each + Contributor provides its Contributions) on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or + implied, including, without limitation, any warranties or conditions + of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A + PARTICULAR PURPOSE. You are solely responsible for determining the + appropriateness of using or redistributing the Work and assume any + risks associated with Your exercise of permissions under this License. + + 8. Limitation of Liability. In no event and under no legal theory, + whether in tort (including negligence), contract, or otherwise, + unless required by applicable law (such as deliberate and grossly + negligent acts) or agreed to in writing, shall any Contributor be + liable to You for damages, including any direct, indirect, special, + incidental, or consequential damages of any character arising as a + result of this License or out of the use or inability to use the + Work (including but not limited to damages for loss of goodwill, + work stoppage, computer failure or malfunction, or any and all + other commercial damages or losses), even if such Contributor + has been advised of the possibility of such damages. + + 9. Accepting Warranty or Additional Liability. While redistributing + the Work or Derivative Works thereof, You may choose to offer, + and charge a fee for, acceptance of support, warranty, indemnity, + or other liability obligations and/or rights consistent with this + License. However, in accepting such obligations, You may act only + on Your own behalf and on Your sole responsibility, not on behalf + of any other Contributor, and only if You agree to indemnify, + defend, and hold each Contributor harmless for any liability + incurred by, or claims asserted against, such Contributor by reason + of your accepting any such warranty or additional liability. + + END OF TERMS AND CONDITIONS + + APPENDIX: How to apply the Apache License to your work. + + To apply the Apache License to your work, attach the following + boilerplate notice, with the fields enclosed by brackets "[]" + replaced with your own identifying information. (Don't include + the brackets!) The text should be enclosed in the appropriate + comment syntax for the file format. We also recommend that a + file or class name and description of purpose be included on the + same "printed page" as the copyright notice for easier + identification within third-party archives. + + Copyright [yyyy] [name of copyright owner] + + 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 + + http://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. 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} +} diff --git a/vendor/github.com/google/go-intervals/intervalset/intervalset_immutable.go b/vendor/github.com/google/go-intervals/intervalset/intervalset_immutable.go new file mode 100644 index 000000000..f6d5cbb52 --- /dev/null +++ b/vendor/github.com/google/go-intervals/intervalset/intervalset_immutable.go @@ -0,0 +1,85 @@ +// 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 + +// ImmutableSet is a set of interval objects. It provides various set theory +// operations. +type ImmutableSet struct { + set *Set +} + +// NewImmutableSet returns a new set given a sorted slice of intervals. This +// function panics if the intervals are not sorted. +func NewImmutableSet(intervals []Interval) *ImmutableSet { + return NewImmutableSetV1(intervals, oldBehaviorFactory.makeZero) +} + +// NewImmutableSetV1 returns a new set given a sorted slice of intervals. This +// function panics if the intervals are not sorted. +func NewImmutableSetV1(intervals []Interval, makeZero func() Interval) *ImmutableSet { + return &ImmutableSet{NewSetV1(intervals, makeZero)} +} + +// String returns a human-friendly representation of the set. +func (s *ImmutableSet) String() string { + return s.set.String() +} + +// Extent returns the Interval defined by the minimum and maximum values of the +// set. +func (s *ImmutableSet) Extent() Interval { + return s.set.Extent() +} + +// Contains reports whether an interval is entirely contained by the set. +func (s *ImmutableSet) Contains(ival Interval) bool { + return s.set.Contains(ival) +} + +// Union returns a set with the contents of this set and another set. +func (s *ImmutableSet) Union(b SetInput) *ImmutableSet { + union := s.set.Copy() + union.Add(b) + return &ImmutableSet{union} +} + +// Sub returns a set without the intervals of another set. +func (s *ImmutableSet) Sub(b SetInput) *ImmutableSet { + x := s.set.Copy() + x.Sub(b) + return &ImmutableSet{x} +} + +// Intersect returns the intersection of two sets. +func (s *ImmutableSet) Intersect(b SetInput) *ImmutableSet { + x := s.set.Copy() + x.Intersect(b) + return &ImmutableSet{x} +} + +// 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 *ImmutableSet) IntervalsBetween(extents Interval, f IntervalReceiver) { + s.set.IntervalsBetween(extents, f) +} + +// Intervals iterates over all the intervals within the set and calls f with +// each one. If f returns false, iteration ceases. +func (s *ImmutableSet) Intervals(f IntervalReceiver) { + s.set.Intervals(f) +} |