lazylog

Documentation

Overview

Package lazylog provides an interval tree backed by an AVL tree. In addition, the interval tree supports shifting intervals in amortized constant time using lazy shifts.

Index

• Constants
• type Tree
  • func (t *Tree) Add(id, low, high int, value intval.Value) intval.Pos
  • func (t *Tree) AllValues() []intval.Value
  • func (t *Tree) FindLargest(id, pos int) intval.Value
  • func (t *Tree) RemoveAndShift(low, high, amt int)
  • func (t *Tree) Size() int

Constants

const ShiftThreshold = -1

ShiftThreshold is the number of shifts to accumulate before applying all shifts.

Types

type Tree

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

func (*Tree) Add

func (t *Tree) Add(id, low, high int, value intval.Value) intval.Pos

Adds the given interval to the tree. An id should also be given to the interval to uniquely identify it if any other intervals begin at the same location.

func (*Tree) AllValues

func (t *Tree) AllValues() []intval.Value

func (*Tree) FindLargest

func (t *Tree) FindLargest(id, pos int) intval.Value

Search for the interval starting at pos with the given id. Returns nil if no such interval exists.

func (*Tree) RemoveAndShift

func (t *Tree) RemoveAndShift(low, high, amt int)

func (*Tree) Size

func (t *Tree) Size() int

Size returns the total number of intervals stored in the tree.