The highest tagged major version is
Documentation
¶
Index ¶
- Variables
- func Dump(tree *Node, path string)
- func Expect(tree *Node, pathStr, startStr, endStr string, priority float64) error
- func Insert(tree *Node, startStr, endStr string, priority float64) interval.Interval
- func InsertExpect(tree *Node, pathStr, startStr, endStr string, priority float64) error
- func Match(iv interval.Interval, startStr, endStr string, priority float64) error
- func NewInterval(startStr, endStr string, priority float64) interval.Interval
- func SaveDot(tree *Node)
- func ShowDot(tree *Node, bg bool)
- func Verify(t *testing.T, tree *Node, ckBalance bool, show bool)
- type Iterator
- type Node
- func (t *Node) AllIntervals() []interval.Interval
- func (t *Node) AsDot(path Path) string
- func (t *Node) Busy() bool
- func (t *Node) BusyIntervals() (intervals []interval.Interval)
- func (t *Node) CalcHeight() int
- func (t *Node) Conflicts(iv interval.Interval, includeFree bool) []interval.Interval
- func (t *Node) Delete(interval interval.Interval) (out *Node, err error)
- func (t *Node) End() time.Time
- func (t *Node) FindExact(interval interval.Interval) (path Path)
- func (t *Node) FindFree(first bool, minStart, maxEnd time.Time, duration time.Duration) (free interval.Interval)
- func (t *Node) FindLowerPriority(first bool, searchStart, searchEnd time.Time, duration time.Duration, ...) (window []*Node, out Path)
- func (t *Node) FirstNode() *Node
- func (t *Node) FreeIntervals() (intervals []interval.Interval)
- func (t *Node) Height() int
- func (t *Node) Insert(newInterval interval.Interval) (out *Node, err error)
- func (t *Node) Interval() interval.Interval
- func (t *Node) LastNode() *Node
- func (t *Node) Left() *Node
- func (t *Node) MaxEnd() time.Time
- func (t *Node) MaxPriority() float64
- func (t *Node) MinPriority() float64
- func (t *Node) MinStart() time.Time
- func (t *Node) Parent() *Node
- func (t *Node) RemoveRange(start, end time.Time) (out *Node, removed []interval.Interval)
- func (t *Node) Right() *Node
- func (t *Node) RotateLeft() (R *Node)
- func (t *Node) RotateRight() (L *Node)
- func (t *Node) SetInterval(iv interval.Interval)
- func (t *Node) SetLeft(left *Node)
- func (t *Node) SetParent(parent *Node) (out *Node)
- func (t *Node) SetRight(right *Node)
- func (t *Node) Shuffle(first bool, minStart, maxEnd time.Time, iv interval.Interval) (newIv interval.Interval, removed []interval.Interval, err error)
- func (t *Node) Size() int
- func (t *Node) Start() time.Time
- func (t *Node) String() string
- func (t *Node) Verify(ckBalance bool) error
- func (t *Node) XXXFindLowerPriority(first bool, searchStart, searchEnd time.Time, duration time.Duration, ...) []*Node
- type Path
Constants ¶
This section is empty.
Variables ¶
var TreeEnd = time.Date(9999, 12, 31, 23, 59, 59, 999999999, time.UTC)
TreeEnd is the maximum time value that can be represented by a Tree node.
var TreeEndStr = TreeEnd.Format(time.RFC3339)
TreeEndStr is the string representation of TreeEnd.
var TreeStart = time.Date(0, 1, 1, 0, 0, 0, 0, time.UTC)
TreeStart is the minimum time value that can be represented by a Tree node.
var TreeStartStr = TreeStart.Format(time.RFC3339)
TreeStartStr is the string representation of TreeStart.
Functions ¶
func Expect ¶
Expect is a test helper function that checks if the given tree node's interval has the expected start and end times and priority. pathStr is the path to the node in the tree, where 'l' means to go left and 'r' means to go right. An empty pathStr means to check the root node.
func Insert ¶
Insert is a test helper function that inserts an interval into the tree and returns the interval that was inserted.
func InsertExpect ¶
InsertExpect is a test helper function that inserts an interval into the tree and checks if the tree has the expected structure.
func Match ¶
Match is a test helper function that checks if the given interval has the expected start and end times and priority.
func NewInterval ¶
NewInterval is a test helper function that creates a new interval with the given start and end times and priority.
func SaveDot ¶
func SaveDot(tree *Node)
SaveDot is a test helper function that saves the tree as a dot file
Types ¶
type Iterator ¶
Iterator allows iterating over the nodes in the tree in either forward or reverse order. If fwd is true, then the iterator will iterate in forward order, otherwise it will iterate in reverse order.
func NewIterator ¶
NewIterator returns a new iterator for the given tree and direction.
type Node ¶
type Node struct {
// contains filtered or unexported fields
}
Node represents a node in an interval tree.
func Get ¶
Get is a test helper function that returns the tree node at the given path in the tree. pathStr is the path to the node in the tree, where 'l' means to go left and 'r' means to go right. An empty pathStr means to return the root node.
func NewTree ¶
func NewTree() *Node
NewTree creates and returns a new Tree node containing a free interval spanning all time.
func (*Node) AllIntervals ¶
AllIntervals returns a slice of all intervals in all leaf nodes of the tree.
func (*Node) BusyIntervals ¶
BusyIntervals returns a slice of all busy intervals in all leaf nodes of the tree.
func (*Node) CalcHeight ¶
CalcHeight returns the height of the tree.
func (*Node) Conflicts ¶
Conflicts returns a slice of intervals in leaf nodes that overlap with the given interval. If includeFree is true, then this function returns all intervals that conflict with the given interval, otherwise it returns only busy intervals.
func (*Node) FindExact ¶
FindExact returns the path to the node containing the exact interval that matches the given interval. If the exact interval is not found, then the path is nil.
func (*Node) FindFree ¶
func (t *Node) FindFree(first bool, minStart, maxEnd time.Time, duration time.Duration) (free interval.Interval)
FindFree returns a free interval that has the given duration. The interval starts as early as possible if first is true, and as late as possible if first is false. The minStart and maxEnd times are inclusive. The duration is exclusive.
This function works by walking the tree in a depth-first manner, following the left child first if first is set, otherwise following the right child first.
func (*Node) FindLowerPriority ¶
func (t *Node) FindLowerPriority(first bool, searchStart, searchEnd time.Time, duration time.Duration, priority float64) (window []*Node, out Path)
FindLowerPriority returns a contiguous set of nodes that have a lower priority than the given priority. The start time of the first node is on or before minStart, and the end time of the last node is on or after maxEnd. The nodes must total at least the given duration, and may be longer. If first is true, then the search starts at minStart and proceeds in order, otherwise the search starts at maxEnd and proceeds in reverse order. XXX this should be refactored to find and return a path to a subtree instead of a slice; the common parent of the set will always be a member of the set.
func (*Node) FreeIntervals ¶
FreeIntervals returns a slice of all free intervals in all leaf nodes of the tree.
func (*Node) Insert ¶
Insert clones the tree, adds the interval, and returns the new tree. Insertion fails if the new interval conflicts with any existing interval in the tree with a priority greater than 0. Insertion fails if the new interval is not busy. XXX return tree
func (*Node) MaxPriority ¶
func (*Node) MinPriority ¶
func (*Node) RemoveRange ¶
RemoveRange removes all intervals that start or end within the given time range. It returns the removed intervals. It does not return intervals that are marked as free (priority 0) -- it instead adjusts free intervals to fill gaps in the tree.
func (*Node) RotateLeft ¶
RotateLeft performs a left rotation on this node. XXX move to Tree
func (*Node) RotateRight ¶
RotateRight performs a right rotation on this node. XXX move to Tree
func (*Node) SetInterval ¶
SetInterval sets the node's interval.
func (*Node) SetLeft ¶
SetLeft sets the left child of this node. It returns the old left child or nil if there was no old left child. If the given child node is already a child of another node, the right child of this node, or the parent of this node, then this function clears the old relationship before setting the new one. XXX move to Tree XXX return new Tree
func (*Node) SetRight ¶
SetRight sets the right child of this node. It returns the old right child or nil if there was no old right child. If the given child node is already a child of another node, the left child of this node, or the parent of this node, then this function clears the old relationship before setting the new one. XXX move to Tree XXX return new Tree
func (*Node) Shuffle ¶
func (t *Node) Shuffle(first bool, minStart, maxEnd time.Time, iv interval.Interval) (newIv interval.Interval, removed []interval.Interval, err error)
Shuffle inserts a new interval into the tree. It finds one or more lower-priority intervals using FindFreePriority, removes and returns them, adjusts the start and end times of the new interval to fit within the found free time, and inserts the new interval into the tree. Shuffle returns the newly created interval and the removed intervals if successful, otherwise it returns nil. The 'first' parameter determines whether to start searching for free time at the beginning or end of the given time range. Shuffle does not return intervals that are marked as free (priority 0) -- it instead adjusts free intervals to fill gaps in the tree.
type Path ¶
type Path []*Node
Path is a slice of Nodes originating from the root of a Tree.
func (Path) Equal ¶
Equal returns true if the paths are the same length and the nav strings are the same.
Source Files