Aleph-w: Aleph::SweepLineSegmentIntersection::StatusTree Class Reference

Aleph-w 3.0

A C++ Library for Data Structures and Algorithms

Loading...

Searching...

No Matches

Sweep-line status as a balanced tree with O(log n) updates. More...

Collaboration diagram for Aleph::SweepLineSegmentIntersection::StatusTree:

Classes
struct	Node

Public Member Functions
	StatusTree (const Array< Segment > &segs)

	~StatusTree ()

bool	contains (const size_t seg) const

void	insert (const size_t seg, const Geom_Number &sx)

void	erase (const size_t seg)

size_t	predecessor (const size_t seg) const

size_t	successor (const size_t seg) const

Private Member Functions
size_t	predecessor_for_insert (const size_t seg, const Geom_Number &sx) const

size_t	successor_for_insert (const size_t seg, const Geom_Number &sx) const

Geom_Number	fresh_label_between (const size_t pred, const size_t succ) const

Static Private Member Functions
static Node *	merge (Node a, Node b)

static Node *	insert_by_label (Node root, Node node)

static void	split_by_label (Node root, const Geom_Number &label, Node &left, Node *&right)

static Node *	erase_by_label (Node root, const Geom_Number &label, Node &removed)

static void	destroy (const Node *n)

Private Attributes
Node *	root_ = nullptr

const Array< Segment > &	segs_

std::mt19937	rng_ {0x5f3759dfu}

Array< Node * >	nodes_

Detailed Description

Sweep-line status as a balanced tree with O(log n) updates.

Maintains an order label per active segment. Labels are updated only when segments are inserted/removed or reinserted at intersection events. This avoids global re-sorting while supporting predecessor/successor queries in logarithmic time.

Definition at line 6017 of file geom_algorithms.H.

Constructor & Destructor Documentation

◆ StatusTree()

Aleph::SweepLineSegmentIntersection::StatusTree::StatusTree ( const Array< Segment > & segs )

inlineexplicit

Definition at line 6163 of file geom_algorithms.H.

References Aleph::Array< T >::append(), Aleph::blossom_maximum_cardinality_matching(), nodes_, and Aleph::Array< T >::reserve().

◆ ~StatusTree()

Aleph::SweepLineSegmentIntersection::StatusTree::~StatusTree ( )

inline

Definition at line 6170 of file geom_algorithms.H.

References destroy(), and root_.

Member Function Documentation

◆ contains()

bool Aleph::SweepLineSegmentIntersection::StatusTree::contains ( const size_t seg ) const

inline

Definition at line 6175 of file geom_algorithms.H.

References nodes_.

Referenced by erase(), insert(), Aleph::SweepLineSegmentIntersection::operator()(), predecessor(), and successor().

◆ destroy()

static void Aleph::SweepLineSegmentIntersection::StatusTree::destroy ( const Node * n )

inlinestaticprivate

Definition at line 6112 of file geom_algorithms.H.

References destroy(), Aleph::SweepLineSegmentIntersection::StatusTree::Node::left, and Aleph::SweepLineSegmentIntersection::StatusTree::Node::right.

Referenced by ~StatusTree(), and destroy().

◆ erase()

void Aleph::SweepLineSegmentIntersection::StatusTree::erase ( const size_t seg )

inline

Definition at line 6193 of file geom_algorithms.H.

References Aleph::blossom_maximum_cardinality_matching(), contains(), erase_by_label(), nodes_, and root_.

Referenced by Aleph::SweepLineSegmentIntersection::operator()().

◆ erase_by_label()

static Node * Aleph::SweepLineSegmentIntersection::StatusTree::erase_by_label	(	Node *	root,
		const Geom_Number &	label,
		Node *&	removed
	)

inlinestaticprivate

Definition at line 6091 of file geom_algorithms.H.

References Aleph::blossom_maximum_cardinality_matching(), erase_by_label(), Aleph::SweepLineSegmentIntersection::StatusTree::Node::left, merge(), and root().

Referenced by erase(), and erase_by_label().

◆ fresh_label_between()

Geom_Number Aleph::SweepLineSegmentIntersection::StatusTree::fresh_label_between	(	const size_t	pred,
		const size_t	succ
	)		const

inlineprivate

Definition at line 6151 of file geom_algorithms.H.

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), nodes_, and pred.

Referenced by insert().

◆ insert()

void Aleph::SweepLineSegmentIntersection::StatusTree::insert	(	const size_t	seg,
		const Geom_Number &	sx
	)

inline

Definition at line 6180 of file geom_algorithms.H.

References contains(), fresh_label_between(), insert_by_label(), nodes_, pred, predecessor_for_insert(), rng_, root_, and successor_for_insert().

Referenced by Aleph::SweepLineSegmentIntersection::operator()().

◆ insert_by_label()

static Node * Aleph::SweepLineSegmentIntersection::StatusTree::insert_by_label	(	Node *	root,
		Node *	node
	)

inlinestaticprivate

Definition at line 6048 of file geom_algorithms.H.

References insert_by_label(), Aleph::SweepLineSegmentIntersection::StatusTree::Node::label, Aleph::SweepLineSegmentIntersection::StatusTree::Node::left, Aleph::SweepLineSegmentIntersection::StatusTree::Node::priority, Aleph::SweepLineSegmentIntersection::StatusTree::Node::right, root(), and split_by_label().

Referenced by insert(), and insert_by_label().

◆ merge()

static Node * Aleph::SweepLineSegmentIntersection::StatusTree::merge	(	Node *	a,
		Node *	b
	)

inlinestaticprivate

Definition at line 6033 of file geom_algorithms.H.

References Aleph::SweepLineSegmentIntersection::StatusTree::Node::left, merge(), Aleph::SweepLineSegmentIntersection::StatusTree::Node::priority, and Aleph::SweepLineSegmentIntersection::StatusTree::Node::right.

Referenced by erase_by_label(), and merge().

◆ predecessor()

size_t Aleph::SweepLineSegmentIntersection::StatusTree::predecessor ( const size_t seg ) const

inline

Definition at line 6204 of file geom_algorithms.H.

References Aleph::blossom_maximum_cardinality_matching(), contains(), nodes_, pred, and root_.

Referenced by Aleph::SweepLineSegmentIntersection::operator()().

◆ predecessor_for_insert()

size_t Aleph::SweepLineSegmentIntersection::StatusTree::predecessor_for_insert	(	const size_t	seg,
		const Geom_Number &	sx
	)		const

inlineprivate

Definition at line 6121 of file geom_algorithms.H.

References Aleph::blossom_maximum_cardinality_matching(), pred, root_, segs_, and Aleph::SweepLineSegmentIntersection::status_less().

Referenced by insert().

◆ split_by_label()

static void Aleph::SweepLineSegmentIntersection::StatusTree::split_by_label	(	Node *	root,
		const Geom_Number &	label,
		Node *&	left,
		Node *&	right
	)

inlinestaticprivate

Definition at line 6070 of file geom_algorithms.H.

References Aleph::SweepLineSegmentIntersection::StatusTree::Node::left, root(), and split_by_label().

Referenced by insert_by_label(), and split_by_label().

◆ successor()

size_t Aleph::SweepLineSegmentIntersection::StatusTree::successor ( const size_t seg ) const

inline

Definition at line 6224 of file geom_algorithms.H.

References Aleph::blossom_maximum_cardinality_matching(), contains(), Aleph::SweepLineSegmentIntersection::StatusTree::Node::left, nodes_, Aleph::SweepLineSegmentIntersection::StatusTree::Node::right, root_, and Aleph::SweepLineSegmentIntersection::StatusTree::Node::seg.

Referenced by Aleph::SweepLineSegmentIntersection::operator()().

◆ successor_for_insert()

size_t Aleph::SweepLineSegmentIntersection::StatusTree::successor_for_insert	(	const size_t	seg,
		const Geom_Number &	sx
	)		const

inlineprivate

Definition at line 6136 of file geom_algorithms.H.

References Aleph::blossom_maximum_cardinality_matching(), root_, Aleph::SweepLineSegmentIntersection::StatusTree::Node::seg, segs_, and Aleph::SweepLineSegmentIntersection::status_less().

Referenced by insert().

Member Data Documentation

◆ nodes_

Array<Node *> Aleph::SweepLineSegmentIntersection::StatusTree::nodes_

private

Definition at line 6031 of file geom_algorithms.H.

Referenced by StatusTree(), contains(), erase(), fresh_label_between(), insert(), predecessor(), and successor().

◆ rng_

std::mt19937 Aleph::SweepLineSegmentIntersection::StatusTree::rng_ {0x5f3759dfu}

private

Definition at line 6030 of file geom_algorithms.H.

Referenced by insert().

◆ root_

Node* Aleph::SweepLineSegmentIntersection::StatusTree::root_ = nullptr

private

Definition at line 6028 of file geom_algorithms.H.

Referenced by ~StatusTree(), erase(), insert(), predecessor(), predecessor_for_insert(), successor(), and successor_for_insert().

◆ segs_

const Array<Segment>& Aleph::SweepLineSegmentIntersection::StatusTree::segs_

private

Definition at line 6029 of file geom_algorithms.H.

Referenced by predecessor_for_insert(), and successor_for_insert().

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

geom_algorithms.H