Back to godoc.org

Package adt

v3.3.22+incompatible
Latest Go to latest

The latest major version is .

Published: May 20, 2020 | License: Apache-2.0 | Module: go.etcd.io/etcd

Overview

Package adt implements useful abstract data types.

Example

Code:

package main

import (
	"fmt"
	"github.com/coreos/etcd/pkg/adt"
)

func main() {
	ivt := adt.NewIntervalTree()
	ivt.Insert(adt.NewInt64Interval(1, 3), 123)
	ivt.Insert(adt.NewInt64Interval(9, 13), 456)
	ivt.Insert(adt.NewInt64Interval(7, 20), 789)

	rs := ivt.Stab(adt.NewInt64Point(10))
	for _, v := range rs {
		fmt.Printf("Overlapping range: %+v\n", v)
	}
}
Overlapping range: &{Ivl:{Begin:7 End:20} Val:789}
Overlapping range: &{Ivl:{Begin:9 End:13} Val:456}

Index

Examples

type BytesAffineComparable

type BytesAffineComparable []byte

BytesAffineComparable treats empty byte arrays as > all other byte arrays

func (BytesAffineComparable) Compare

func (b BytesAffineComparable) Compare(c Comparable) int

type Comparable

type Comparable interface {
	// Compare gives the result of a 3-way comparison
	// a.Compare(b) = 1 => a > b
	// a.Compare(b) = 0 => a == b
	// a.Compare(b) = -1 => a < b
	Compare(c Comparable) int
}

Comparable is an interface for trichotomic comparisons.

type Int64Comparable

type Int64Comparable int64

func (Int64Comparable) Compare

func (v Int64Comparable) Compare(c Comparable) int

type Interval

type Interval struct {
	Begin Comparable
	End   Comparable
}

Interval implements a Comparable interval [begin, end) TODO: support different sorts of intervals: (a,b), [a,b], (a, b]

func NewBytesAffineInterval

func NewBytesAffineInterval(begin, end []byte) Interval

func NewBytesAffinePoint

func NewBytesAffinePoint(b []byte) Interval

func NewInt64Interval

func NewInt64Interval(a int64, b int64) Interval

func NewInt64Point

func NewInt64Point(a int64) Interval

func NewStringAffineInterval

func NewStringAffineInterval(begin, end string) Interval

func NewStringAffinePoint

func NewStringAffinePoint(s string) Interval

func NewStringInterval

func NewStringInterval(begin, end string) Interval

func NewStringPoint

func NewStringPoint(s string) Interval

func (*Interval) Compare

func (ivl *Interval) Compare(c Comparable) int

Compare on an interval gives == if the interval overlaps.

type IntervalTree

type IntervalTree interface {
	// Insert adds a node with the given interval into the tree.
	Insert(ivl Interval, val interface{})
	// Delete removes the node with the given interval from the tree, returning
	// true if a node is in fact removed.
	Delete(ivl Interval) bool
	// Len gives the number of elements in the tree.
	Len() int
	// Height is the number of levels in the tree; one node has height 1.
	Height() int
	// MaxHeight is the expected maximum tree height given the number of nodes.
	MaxHeight() int
	// Visit calls a visitor function on every tree node intersecting the given interval.
	// It will visit each interval [x, y) in ascending order sorted on x.
	Visit(ivl Interval, ivv IntervalVisitor)
	// Find gets the IntervalValue for the node matching the given interval
	Find(ivl Interval) *IntervalValue
	// Intersects returns true if there is some tree node intersecting the given interval.
	Intersects(iv Interval) bool
	// Contains returns true if the interval tree's keys cover the entire given interval.
	Contains(ivl Interval) bool
	// Stab returns a slice with all elements in the tree intersecting the interval.
	Stab(iv Interval) []*IntervalValue
	// Union merges a given interval tree into the receiver.
	Union(inIvt IntervalTree, ivl Interval)
}

IntervalTree represents a (mostly) textbook implementation of the "Introduction to Algorithms" (Cormen et al, 3rd ed.) chapter 13 red-black tree and chapter 14.3 interval tree with search supporting "stabbing queries".

func NewIntervalTree

func NewIntervalTree() IntervalTree

NewIntervalTree returns a new interval tree.

type IntervalValue

type IntervalValue struct {
	Ivl Interval
	Val interface{}
}

IntervalValue represents a range tree node that contains a range and a value.

type IntervalVisitor

type IntervalVisitor func(n *IntervalValue) bool

IntervalVisitor is used on tree searches; return false to stop searching.

type StringAffineComparable

type StringAffineComparable string

StringAffineComparable treats "" as > all other strings

func (StringAffineComparable) Compare

func (s StringAffineComparable) Compare(c Comparable) int

type StringComparable

type StringComparable string

func (StringComparable) Compare

func (s StringComparable) Compare(c Comparable) int

Package Files

Documentation was rendered with GOOS=linux and GOARCH=amd64.

Jump to identifier

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to identifier