interval/list.go

// Copyright (C) 2015 The Android Open Source Project
//
// 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.

package interval

// List is the interface to an object that can be used as an interval list by
// the algorithms in this package.
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
	// SetSpan sets the span for the element at index in the list
	SetSpan(index int, span U64Span)
	// Copy count list entries
	Copy(to, from, count int)
	// Resize adjusts the length of the array
	Resize(length int)
}

// Predicate is used as the condition for a Search
type Predicate func(test U64Span) bool

// Contains returns true if the value is found inside on of the intervals.
func Contains(l List, value uint64) bool {
	return findSpanFor(l, value) >= 0
}

// IndexOf returns the index of the span the value is a part of, or -1 if not found
func IndexOf(l List, value uint64) int {
	return findSpanFor(l, value)
}

// 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 Merge(l List, span U64Span, joinAdj bool) int {
	return merge(l, span, joinAdj)
}

// Replace cuts the span out of any existing intervals, and then adds a new interval,
// and returns it's index.
func Replace(l List, span U64Span) int {
	index, newSpan := cut(l, span, true)
	l.SetSpan(index, newSpan)
	return index
}

// Remove strips the specified span from the list, cutting it out of any
// overlapping intervals
func Remove(l List, span U64Span) {
	cut(l, span, false)
}

// Intersect finds the intervals from the list that overlap with the specified span.
func Intersect(l List, span U64Span) (first, count int) {
	s := intersection{}
	s.intersect(l, span, false)
	return s.lowIndex, s.overlap
}

// 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 Search(l List, t Predicate) int {
	return search(l, t)
}