diet

Documentation

Overview

Package diet provides an implementation of a Discrete Interval Encoding Tree. A Diet is a binary search tree where each node represents a range of integers. Ranges do not overlap, and each interval has maximal extent (i.e., is not adjacent to another range).

See https://web.engr.oregonstate.edu/~erwig/papers/Diet_JFP98.pdf

This implementation is a modified version of the original that allows the insertion of an entire range at a time.

Note: Deletion has NOT been implemented, due to lack of current need.

Index

• type Diet
  • func NewDiet() *Diet
  • func (d *Diet) Balance()
  • func (d *Diet) Contains(x, y uint64) bool
  • func (d *Diet) Insert(x, y uint64)
  • func (d *Diet) Intersection(x, y uint64) uint64
  • func (d *Diet) IntersectionAll(other *Diet) uint64
  • func (d *Diet) Total() uint64

Types

type Diet

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

Diet is a Discrete Interval Encoding Tree, allowing insertion of ranges of integers and fast intersection and membership calculation.

func NewDiet

func NewDiet() *Diet

NewDiet returns a new Diet.

func (*Diet) Balance

func (d *Diet) Balance()

Balance balances the tree using the DSW algorithm. It is most efficient to do this after the tree is complete.

func (*Diet) Contains

func (d *Diet) Contains(x, y uint64) bool

Contains returns whether all of the range specified is contained within this diet.

func (*Diet) Insert

func (d *Diet) Insert(x, y uint64)

Insert adds a new range of integers to the tree.

func (*Diet) Intersection

func (d *Diet) Intersection(x, y uint64) uint64

Intersection finds the intersection of the range of integers specified with any of the members of the tree. It returns the number of members in common.

func (*Diet) IntersectionAll

func (d *Diet) IntersectionAll(other *Diet) uint64

IntersectionAll finds the number of members in common between two Diets.

func (*Diet) Total

func (d *Diet) Total() uint64

Total finds the number of integers represented by this tree.