The highest tagged major version is
Documentation
¶
Index ¶
- Constants
- type 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) ForEach(callback func(line, value int))
- 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().
Variables ¶
This section is empty.
Functions ¶
This section is empty.
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 ¶
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) CloneShallow ¶
CloneShallow copies the file. It performs a shallow copy of the tree: the allocator must be Clone()-d beforehand.
func (File) Dump ¶
Dump formats the underlying line interval tree into a string. Useful for error messages, panic()-s and debugging.
func (File) Len ¶
Len returns the File's size - that is, the maximum key in the tree of line intervals.
func (*File) Update ¶
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.
Source Files