operations_research::sat::SweepLineIntervalTree Struct Reference

Public Member Functions
	SweepLineIntervalTree (int max_y, int num_boxes)
void	RecomputeConnectedComponents (TreeNodeIndex idx)
void	RemoveNodeIfXMaxLowerOrEqual (TreeNodeIndex idx, int x_threshold)
void	UpdateChildrenIntersecting (TreeNodeIndex idx, int sweep_line_x_pos, int component_index, std::vector< int > *new_connections)
bool	UpdateParents (TreeNodeIndex node, int sweep_line_x_pos, int component_index, std::vector< int > *new_connections)
void	AddInterval (TreeNodeIndex idx, int sweep_line_x_pos, int box_index, int x_max, std::vector< int > *new_connections)

Public Attributes
FixedShapeBinaryTree	tree
util_intops::StrongVector< TreeNodeIndex, BinaryTreeNode >	tree_nodes
DenseConnectedComponentsFinder	union_find

Detailed Description

A data structure to store which boxes are overlapping the current sweep line. This uses a binary tree in a slight non-standard way: in a typical use of a binary tree the actual values are stored in the leaves and the intermediate nodes are there just to make finding the right leaf efficient. Here we do the opposite: the values are stored as high up in the tree as possible. For example, for a tree of size 8 a box that occupies the y interval [0, 7] will be stored as a single node at the root. In the same tree, a box that occupies [3, 7] will be stored with the nodes representing the [3, 4), [4, 6) and [6, 8) intervals. There is no difference on what is stored in the intermediate nodes or on the leaves. When the sweep line moves, we don't update the existing nodes on the tree. Thus, some nodes will become stale and will represent boxes that no longer overlap the sweep line. Those stale nodes get removed lazily.

Definition at line 1658 of file diffn_util.cc.

Constructor & Destructor Documentation

SweepLineIntervalTree()

operations_research::sat::SweepLineIntervalTree::SweepLineIntervalTree ( int max_y, int num_boxes )

inlineexplicit

Definition at line 1659 of file diffn_util.cc.

Member Function Documentation

AddInterval()

void operations_research::sat::SweepLineIntervalTree::AddInterval ( TreeNodeIndex idx, int sweep_line_x_pos, int box_index, int x_max, std::vector< int > * new_connections )

inline

Add a new box to the sweep line. This will store it in the tree (split in log N intervals) check if it connects to one or more existing connected components, and for each case it does, add the box that it is overlapping to new_connections.

We can only be connecting children if it is not already connect via something above on the tree.

We have already something fully occupying this interval.

Replace the existing box by the new one.

Definition at line 1767 of file diffn_util.cc.

RecomputeConnectedComponents()

void operations_research::sat::SweepLineIntervalTree::RecomputeConnectedComponents ( TreeNodeIndex idx )

inline

Recompute the connected components of a given node, by simply setting it to {self} + left.connected_components + right.connected_components.

The order is non-deterministic, but since this is doing the union of hash sets the result is deterministic.

Definition at line 1666 of file diffn_util.cc.

RemoveNodeIfXMaxLowerOrEqual()

void operations_research::sat::SweepLineIntervalTree::RemoveNodeIfXMaxLowerOrEqual ( TreeNodeIndex idx, int x_threshold )

inline

We don't have global deletion method in this class, but this method checks if a single interval is fully to the left of the sweep line and removes it if so, also updating its connected components.

Node is already empty.

Node is still overlapping the sweep line.

Definition at line 1689 of file diffn_util.cc.

UpdateChildrenIntersecting()

void operations_research::sat::SweepLineIntervalTree::UpdateChildrenIntersecting ( TreeNodeIndex idx, int sweep_line_x_pos, int component_index, std::vector< int > * new_connections )

inline

No need to recurse here: we already connected everything on this branch to the new box.

Since everything is intersecting the current box, all descendants must be in one single component.

Only go down on the tree if we have below either:

• a different component to connect.
• a box to remove that is in a different component. In any case, we will visit O(c + d) terminals, where c is the number of components we are connecting and d is the number of boxes that we will delete. Since a box can only be deleted log N times (one per interval it was cut into) and we can only connect O(N) components in total, the amortized cost of a call to UpdateChildrenIntersecting is O((log N)^2).

Definition at line 1703 of file diffn_util.cc.

UpdateParents()

bool operations_research::sat::SweepLineIntervalTree::UpdateParents ( TreeNodeIndex node, int sweep_line_x_pos, int component_index, std::vector< int > * new_connections )

inline

Definition at line 1744 of file diffn_util.cc.

Member Data Documentation

tree

FixedShapeBinaryTree operations_research::sat::SweepLineIntervalTree::tree

Definition at line 1799 of file diffn_util.cc.

tree_nodes

util_intops::StrongVector<TreeNodeIndex, BinaryTreeNode> operations_research::sat::SweepLineIntervalTree::tree_nodes

Definition at line 1800 of file diffn_util.cc.

union_find

DenseConnectedComponentsFinder operations_research::sat::SweepLineIntervalTree::union_find

Definition at line 1801 of file diffn_util.cc.

---

The documentation for this struct was generated from the following file:

• ortools/sat/diffn_util.cc