spans

Documentation

Index

• func Debug(full *ValueSortedFull)
• func Overlaps(a, b Span) bool
• func ValuedSetEquals(xs, ys []Valued) bool
• type Span
  • func Collapse(length int, getRange func(int) Span) []Span
  • func Full() []Span
• type Value
• type ValueSortedFull
  • func Sorted(f *ValuedFull) *ValueSortedFull
  • func (v *ValueSortedFull) Merge(newItem Valued)
  • func (v *ValueSortedFull) MergeAll(newItems []Valued)
  • func (v *ValueSortedFull) MinValue() Value
  • func (v *ValueSortedFull) TraverseValuesLessThan(n Value, action func(Valued) bool)
• type Valued
  • func (x Valued) Equals(y Valued) bool
  • func (r Valued) Less(other btree.Item) bool
  • func (r Valued) String() string
• type ValuedFull
  • func NewFullWith(initSpans []Span, init Value) *ValuedFull
  • func (f *ValuedFull) Merge(val Valued)
  • func (f *ValuedFull) Traverse(m func(Valued) bool)

Functions

func Debug

func Debug(full *ValueSortedFull)

func Overlaps

func Overlaps(a, b Span) bool

Overlaps checks whether two spans have overlapped part.

func ValuedSetEquals

func ValuedSetEquals(xs, ys []Valued) bool

Types

type Span

type Span = kv.KeyRange

Span is the type of an adjacent sub key space.

func Collapse

func Collapse(length int, getRange func(int) Span) []Span

Collapse collapse ranges overlapping or adjacent. Example: Collapse({[1, 4], [2, 8], [3, 9]}) == {[1, 9]} Collapse({[1, 3], [4, 7], [2, 3]}) == {[1, 3], [4, 7]}

func Full

func Full() []Span

Full returns a full span crossing the key space.

type Value

type Value = uint64

Value is the value type of stored in the span tree.

type ValueSortedFull

type ValueSortedFull struct {
	*ValuedFull
	// contains filtered or unexported fields
}

ValueSortedFull is almost the same as `Valued`, however it added an extra index hence enabled query range by theirs value.

func Sorted

func Sorted(f *ValuedFull) *ValueSortedFull

Sorted takes the ownership of a raw `ValuedFull` and then wrap it with `ValueSorted`.

func (*ValueSortedFull) Merge

func (v *ValueSortedFull) Merge(newItem Valued)

func (*ValueSortedFull) MergeAll

func (v *ValueSortedFull) MergeAll(newItems []Valued)

func (*ValueSortedFull) MinValue

func (v *ValueSortedFull) MinValue() Value

func (*ValueSortedFull) TraverseValuesLessThan

func (v *ValueSortedFull) TraverseValuesLessThan(n Value, action func(Valued) bool)

type Valued

type Valued struct {
	Key   Span
	Value Value
}

Valued is span binding to a value, which is the entry type of span tree.

func (Valued) Equals

func (x Valued) Equals(y Valued) bool

func (Valued) Less

func (r Valued) Less(other btree.Item) bool

func (Valued) String

func (r Valued) String() string

type ValuedFull

type ValuedFull struct {
	// contains filtered or unexported fields
}

ValuedFull represents a set of valued ranges, which doesn't overlap and union of them all is the full key space.

func NewFullWith

func NewFullWith(initSpans []Span, init Value) *ValuedFull

NewFullWith creates a set of a subset of spans.

func (*ValuedFull) Merge

func (f *ValuedFull) Merge(val Valued)

Merge merges a new interval into the span set. The value of overlapped part with other spans would be "merged" by the `join` function. An example:

|___________________________________________________________________________| ^-----------------^-----------------^-----------------^---------------------^ | c = 42 | c = 43 | c = 45 | c = 41 |

      ^--------------------------^
merge(|          c = 44          |)

Would Give: |___________________________________________________________________________| ^-----------------^----^------------^-------------^---^---------------------^ | c = 42 | 43 | c = 44 | c = 45 | c = 41 |

|-------------|
Unchanged, because 44 < 45.

func (*ValuedFull) Traverse

func (f *ValuedFull) Traverse(m func(Valued) bool)

Traverse traverses all ranges by order.