burndown

Documentation

Index

• Constants
• type File
  • func NewFile(time int, length int, allocator *rbtree.Allocator, updaters ...Updater) *File
  • func NewFileFromTree(keys []int, vals []int, allocator *rbtree.Allocator, updaters ...Updater) *File
  • func (file *File) CloneDeep(allocator *rbtree.Allocator) *File
  • func (file *File) CloneShallow(allocator *rbtree.Allocator) *File
  • func (file *File) Delete()
  • func (file *File) Dump() string
  • func (file *File) Len() int
  • func (file *File) Merge(day int, others ...*File)
  • func (file *File) Nodes() int
  • func (file *File) Update(time int, pos int, insLength int, delLength int)
  • func (file *File) Validate()
• type Updater

Constants

const TreeEnd = math.MaxUint32

TreeEnd denotes the value of the last leaf in the tree.

const TreeMaxBinPower = 14

TreeMaxBinPower is the binary power value which corresponds to the maximum day which can be stored in the tree.

const TreeMergeMark = (1 << TreeMaxBinPower) - 1

TreeMergeMark is the special day which disables the status updates and is used in File.Merge().

Types

type File

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

File encapsulates a balanced binary tree to store line intervals and a cumulative mapping of values to the corresponding length counters. Users are not supposed to create File-s directly; instead, they should call NewFile(). NewFileFromTree() is the special constructor which is useful in the tests.

Len() returns the number of lines in File.

Update() mutates File by introducing tree structural changes and updating the length mapping.

Dump() writes the tree to a string and Validate() checks the tree integrity.

func NewFile

func NewFile(time int, length int, allocator *rbtree.Allocator, updaters ...Updater) *File

NewFile initializes a new instance of File struct.

time is the starting value of the first node;

length is the starting length of the tree (the key of the second and the last node);

updaters are the attached interval length mappings.

func NewFileFromTree

func NewFileFromTree(keys []int, vals []int, allocator *rbtree.Allocator, updaters ...Updater) *File

NewFileFromTree is an alternative constructor for File which is used in tests. The resulting tree is validated with Validate() to ensure the initial integrity.

keys is a slice with the starting tree keys.

vals is a slice with the starting tree values. Must match the size of keys.

updaters are the attached interval length mappings.

func (*File) CloneDeep

func (file *File) CloneDeep(allocator *rbtree.Allocator) *File

CloneDeep copies the file. It performs a deep copy of the tree.

func (*File) CloneShallow

func (file *File) CloneShallow(allocator *rbtree.Allocator) *File

CloneShallow copies the file. It performs a shallow copy of the tree: the allocator must be Clone()-d beforehand.

func (*File) Delete

func (file *File) Delete()

Delete deallocates the file.

func (*File) Dump

func (file *File) Dump() string

Dump formats the underlying line interval tree into a string. Useful for error messages, panic()-s and debugging.

func (*File) Len

func (file *File) Len() int

Len returns the File's size - that is, the maximum key in the tree of line intervals.

func (*File) Merge

func (file *File) Merge(day int, others ...*File)

Merge combines several prepared File-s together.

func (*File) Nodes

func (file *File) Nodes() int

Nodes returns the number of RBTree nodes in the file.

func (*File) Update

func (file *File) Update(time int, pos int, insLength int, delLength int)

Update modifies the underlying tree to adapt to the specified line changes.

time is the time when the requested changes are made. Sets the values of the inserted nodes.

pos is the index of the line at which the changes are introduced.

ins_length is the number of inserted lines after pos.

del_length is the number of removed lines after pos. Deletions come before the insertions.

The code inside this function is probably the most important one throughout the project. It is extensively covered with tests. If you find a bug, please add the corresponding case in file_test.go.

func (*File) Validate

func (file *File) Validate()

Validate checks the underlying line interval tree integrity. The checks are as follows:

1. The minimum key must be 0 because the first line index is always 0.

2. The last node must carry TreeEnd value. This is the maintained invariant which marks the ending of the last line interval.

3. Node keys must monotonically increase and never duplicate.

type Updater

type Updater = func(currentTime, previousTime, delta int)

Updater is the function which is called back on File.Update().