Aleph::LineSweepFramework< Event, CmpEvent > Class Template Reference

Reusable event-driven sweep line framework. More...

#include <geom_algorithms.H>

Collaboration diagram for Aleph::LineSweepFramework< Event, CmpEvent >:

Classes
struct	CmpSeqEvent
	Comparator for SeqEvent, ensuring a strict weak ordering. More...
struct	SeqEvent
	Internal event wrapper that adds a sequence number for tie-breaking. More...

Public Member Functions
void	enqueue (const Event &e)
	Enqueue an event.
void	enqueue (Event &&e)
	Enqueue an event (move version).
bool	has_events () const noexcept
	True if the event queue is non-empty.
size_t	pending () const noexcept
	Number of pending events.
Event	dequeue ()
	Remove and return the next (minimum) event.
const Event &	peek () const
	Peek at the next event without removing it.
void	clear () noexcept
	Discard all pending events.
template<typename Handler >
void	run (Handler &&handler)
	Run the sweep: process every event through handler.
template<typename Handler >
void	run (Handler &&handler, Array< Event > &out)
	Run the sweep, collecting every event into out.

Private Attributes
DynSetTree< SeqEvent, Avl_Tree, CmpSeqEvent >	queue_
size_t	seq_ = 0

Detailed Description

template<typename Event, typename CmpEvent>
class Aleph::LineSweepFramework< Event, CmpEvent >

Reusable event-driven sweep line framework.

This template manages an event queue backed by a balanced BST (DynSetTree<Avl_Tree>). The user supplies:

• Event: the event payload (e.g. a point + an enum tag).
• CmpEvent: strict weak order on events that defines the sweep direction. Ties are broken internally by insertion sequence, so duplicate-position events are supported.

The framework does not own the sweep-line status structure — the handler is free to use whatever data structure is appropriate (array, BST, linked list, etc.).

Usage

struct MyEvent { Point pos; int type; size_t seg_id; };
struct CmpMyEvent {
  bool operator()(const MyEvent & a, const MyEvent & b) const
  { return a.pos.get_x() < b.pos.get_x(); }
};
 
LineSweepFramework<MyEvent, CmpMyEvent> fw;
fw.enqueue({p1, START, 0});
fw.enqueue({p2, END,   0});
 
fw.run([&](auto & sweep, const MyEvent & e) {
  // process event, may call sweep.enqueue(...)
});

Complexity

• Enqueue / dequeue: O(log n) per operation.
• run(): processes all events; total cost depends on the handler.

Template Parameters

Event	Event payload type.
CmpEvent	Strict-weak-order comparator on Event.

Definition at line 5741 of file geom_algorithms.H.

Member Function Documentation

clear()

template<typename Event , typename CmpEvent >

void Aleph::LineSweepFramework< Event, CmpEvent >::clear ( )

inlinenoexcept

Discard all pending events.

Definition at line 5810 of file geom_algorithms.H.

References Aleph::LineSweepFramework< Event, CmpEvent >::queue_, and Aleph::LineSweepFramework< Event, CmpEvent >::seq_.

dequeue()

template<typename Event , typename CmpEvent >

Event Aleph::LineSweepFramework< Event, CmpEvent >::dequeue ( )

inline

Remove and return the next (minimum) event.

Definition at line 5796 of file geom_algorithms.H.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::LineSweepFramework< Event, CmpEvent >::queue_.

Referenced by Aleph::LineSweepFramework< Event, CmpEvent >::run(), and Aleph::LineSweepFramework< Event, CmpEvent >::run().

enqueue() [1/2]

template<typename Event , typename CmpEvent >

void Aleph::LineSweepFramework< Event, CmpEvent >::enqueue ( const Event &  e )

inline

Enqueue an event.

Definition at line 5772 of file geom_algorithms.H.

References Aleph::LineSweepFramework< Event, CmpEvent >::queue_, and Aleph::LineSweepFramework< Event, CmpEvent >::seq_.

Referenced by Aleph::SweepLineSegmentIntersection::operator()(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), and TEST_F().

enqueue() [2/2]

template<typename Event , typename CmpEvent >

void Aleph::LineSweepFramework< Event, CmpEvent >::enqueue ( Event &&  e )

inline

Enqueue an event (move version).

Definition at line 5778 of file geom_algorithms.H.

References Aleph::LineSweepFramework< Event, CmpEvent >::queue_, and Aleph::LineSweepFramework< Event, CmpEvent >::seq_.

has_events()

template<typename Event , typename CmpEvent >

bool Aleph::LineSweepFramework< Event, CmpEvent >::has_events ( ) const

inlinenoexcept

True if the event queue is non-empty.

Definition at line 5784 of file geom_algorithms.H.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::LineSweepFramework< Event, CmpEvent >::queue_.

Referenced by Aleph::LineSweepFramework< Event, CmpEvent >::run(), and Aleph::LineSweepFramework< Event, CmpEvent >::run().

peek()

template<typename Event , typename CmpEvent >

const Event & Aleph::LineSweepFramework< Event, CmpEvent >::peek ( ) const

inline

Peek at the next event without removing it.

Definition at line 5804 of file geom_algorithms.H.

References Aleph::LineSweepFramework< Event, CmpEvent >::queue_.

pending()

template<typename Event , typename CmpEvent >

size_t Aleph::LineSweepFramework< Event, CmpEvent >::pending ( ) const

inlinenoexcept

Number of pending events.

Definition at line 5790 of file geom_algorithms.H.

References Aleph::LineSweepFramework< Event, CmpEvent >::queue_.

run() [1/2]

template<typename Event , typename CmpEvent >

template<typename Handler >

void Aleph::LineSweepFramework< Event, CmpEvent >::run ( Handler &&  handler )

inline

Run the sweep: process every event through handler.

The handler signature must be compatible with:

void handler(LineSweepFramework<Event,CmpEvent> & fw,
             const Event & e);

The handler may call fw.enqueue() to schedule new events discovered during processing (e.g. intersection events).

Definition at line 5829 of file geom_algorithms.H.

References Aleph::LineSweepFramework< Event, CmpEvent >::dequeue(), and Aleph::LineSweepFramework< Event, CmpEvent >::has_events().

run() [2/2]

template<typename Event , typename CmpEvent >

template<typename Handler >

void Aleph::LineSweepFramework< Event, CmpEvent >::run ( Handler &&  handler, Array< Event > &  out  )

inline

Run the sweep, collecting every event into out.

Each dequeued event is appended to out before the handler is invoked, providing a full processing log.

Definition at line 5842 of file geom_algorithms.H.

References Aleph::LineSweepFramework< Event, CmpEvent >::dequeue(), Aleph::divide_and_conquer_partition_dp(), and Aleph::LineSweepFramework< Event, CmpEvent >::has_events().

Member Data Documentation

queue_

template<typename Event , typename CmpEvent >

DynSetTree<SeqEvent, Avl_Tree, CmpSeqEvent> Aleph::LineSweepFramework< Event, CmpEvent >::queue_

private

Definition at line 5767 of file geom_algorithms.H.

Referenced by Aleph::LineSweepFramework< Event, CmpEvent >::clear(), Aleph::LineSweepFramework< Event, CmpEvent >::dequeue(), Aleph::LineSweepFramework< Event, CmpEvent >::enqueue(), Aleph::LineSweepFramework< Event, CmpEvent >::enqueue(), Aleph::LineSweepFramework< Event, CmpEvent >::has_events(), Aleph::LineSweepFramework< Event, CmpEvent >::peek(), and Aleph::LineSweepFramework< Event, CmpEvent >::pending().

seq_

template<typename Event , typename CmpEvent >

size_t Aleph::LineSweepFramework< Event, CmpEvent >::seq_ = 0

private

Definition at line 5768 of file geom_algorithms.H.

Referenced by Aleph::LineSweepFramework< Event, CmpEvent >::clear(), Aleph::LineSweepFramework< Event, CmpEvent >::enqueue(), and Aleph::LineSweepFramework< Event, CmpEvent >::enqueue().

---

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

• geom_algorithms.H