goaugmented

README

goaugmented

Golang augmented tree realisation for interfaces types.

import (
    "github.com/Kerah/goaugmented"
    "github.com/Kerah/goaugmented/augmented"
    "fmt"
)

func main(){
  tree := goaugmented.New(1)
  iv := goaugmented.SingleDimensionInterval(
		NewFloat64(10.0),
		NewFloat64(100.0),
		1,
	)

	iv2 := goaugmented.SingleDimensionInterval(
		NewFloat64(50.0),
		NewFloat64(100.0),
		2,
	)
	
	tree.Add(iv, iv2)
	q := NewFloat64VI(64)
	ivs := tree.Query(q)


	data := map[uint64]struct{}{}

	for _, i := range ivs {
		fmt.Printf("Founded: %d\n", i.ID())
	}
}

Documentation

Overview

Copyright 2014 Workiva, LLC

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.

Index

• func MultiDimensionInterval(id uint64, dimensions ...*dimension) *interval
• func SingleDimensionInterval(low, high Value, id uint64) *interval
• func ValueInterval(val Value) *interval
• type Interval
• type Intervals
  • func (ivs *Intervals) Dispose()
• type Tree
  • func New(dimensions uint64) Tree
• type Value

Functions

func MultiDimensionInterval

func MultiDimensionInterval(id uint64, dimensions ...*dimension) *interval

func SingleDimensionInterval

func SingleDimensionInterval(low, high Value, id uint64) *interval

func ValueInterval

func ValueInterval(val Value) *interval

Types

type Interval

type Interval interface {
	// LowAtDimension returns an integer representing the lower bound
	// at the requested dimension.
	LowAtDimension(uint64) Value
	// HighAtDimension returns an integer representing the higher bound
	// at the requested dimension.
	HighAtDimension(uint64) Value
	// OverlapsAtDimension should return a bool indicating if the provided
	// interval overlaps this interval at the dimension requested.
	OverlapsAtDimension(Interval, uint64) bool
	// ID should be a unique ID representing this interval.  This
	// is used to identify which interval to delete from the tree if
	// there are duplicates.
	ID() uint64
}

Interval is the interface that must be implemented by any item added to the interval tree.

type Intervals

type Intervals []Interval

Intervals represents a list of Intervals.

func (*Intervals) Dispose

func (ivs *Intervals) Dispose()

Dispose will free any consumed resources and allow this list to be re-allocated.

type Tree

type Tree interface {
	// Add will add the provided intervals to the tree.
	Add(intervals ...Interval)
	// Len returns the number of intervals in the tree.
	Len() uint64
	// Delete will remove the provided intervals from the tree.
	Delete(intervals ...Interval)
	// Query will return a list of intervals that intersect the provided
	// interval.  The provided interval's ID method is ignored so the
	// provided ID is irrelevant.
	Query(interval Interval) Intervals
	// Insert will shift intervals in the tree based on the specified
	// index and the specified count.  Dimension specifies where to
	// apply the shift.  Returned is a list of intervals impacted and
	// list of intervals deleted.  Intervals are deleted if the shift
	// makes the interval size zero or less, ie, min >= max.  These
	// intervals are automatically removed from the tree.  The tree
	// does not alter the ranges on the intervals themselves, the consumer
	// is expected to do that.
	Insert(dimension uint64, index Value, count int64) (Intervals, Intervals)
}

Tree defines the object that is returned from the tree constructor. We use a Tree interface here because the returned tree could be a single dimension or many dimensions.

func New

func New(dimensions uint64) Tree

New constructs and returns a new interval tree with the max dimensions provided.

type Value

type Value interface {
	Greater(Value) bool
	GreaterOrEq(Value) bool
	Lesser(Value) bool
	LesserOrEq(Value) bool
	Substract(Value) int64

	Add(int64) Value

	MinimalValue() Value
	MaximalValue() Value
}