Detects fixed points and short cycles via frame hashing. More...

#include <ca-observer.H>

Collaboration diagram for Aleph::CA::Stationary_Detector:

Public Member Functions
	Stationary_Detector ()=default
	Construct a detector with the default 16-frame window.

	Stationary_Detector (std::size_t max_cycle_length)
	Construct a detector with an explicit window size.

bool	cycle_detected () const noexcept
	Return whether a cycle has been detected.

std::optional< std::size_t >	cycle_length () const noexcept
	Return the detected cycle length.

std::optional< std::size_t >	cycle_start () const noexcept
	Return the cycle start step.

std::size_t	buffered_hashes () const noexcept
	Return the number of buffered hashes.

void	reset () noexcept
	Clear buffered hashes and detected-cycle state.

template<typename Lattice >
void	on_step_begin (const std::size_t step, const Lattice &frame)
	Seed the detector with the initial frame hash.

template<typename Lattice >
void	on_step_end (std::size_t step, const Lattice &frame)
	Check the completed frame against the recent hash window.

Private Member Functions
void	push (const std::uint64_t h, const std::size_t step) noexcept

Private Attributes
std::size_t	max_cycle_length_ = 0

Array< std::uint64_t >	hashes_

Array< std::size_t >	steps_

std::optional< std::size_t >	cycle_length_

std::optional< std::size_t >	cycle_start_

Detailed Description

Detects fixed points and short cycles via frame hashing.

Keeps a ring buffer of the last max_cycle_length frame hashes paired with the step at which they were seen. After every step the new hash is compared against the buffer; on a hit the observer records the cycle length (current step minus the step at which the matching frame was seen) and exposes it through cycle_length().

Multiple periodic patterns active at once (e.g. a blinker plus a glider in different regions) result in the longest reachable cycle within the buffer being detected.

Complexity: Each callback computes one frame hash in O(N) and scans at most max_cycle_length + 1 hashes.

Thread-safety: Thread-safe for concurrent readers after simulation stops; not thread-safe for concurrent callbacks.

Exception-safety: Strong guarantee unless array allocation throws.

Definition at line 647 of file ca-observer.H.

Constructor & Destructor Documentation

◆ Stationary_Detector() [1/2]

Aleph::CA::Stationary_Detector::Stationary_Detector ( )

default

Construct a detector with the default 16-frame window.

Exceptions

This	function does not throw.

◆ Stationary_Detector() [2/2]

Aleph::CA::Stationary_Detector::Stationary_Detector ( std::size_t max_cycle_length )

inlineexplicit

Construct a detector with an explicit window size.

Parameters

[in] max_cycle_length maximum cycle length to retain.

Exceptions

This	function does not throw.

Definition at line 678 of file ca-observer.H.

Member Function Documentation

◆ buffered_hashes()

std::size_t Aleph::CA::Stationary_Detector::buffered_hashes ( ) const

inlinenoexcept

Return the number of buffered hashes.

Returns: current ring-buffer occupancy.

Exceptions

This	function does not throw.

Definition at line 712 of file ca-observer.H.

References hashes_, and Aleph::Array< T >::size().

◆ cycle_detected()

bool Aleph::CA::Stationary_Detector::cycle_detected ( ) const

inlinenoexcept

Return whether a cycle has been detected.

Returns: true after the first matching frame hash.

Exceptions

This	function does not throw.

Definition at line 685 of file ca-observer.H.

References cycle_length_.

◆ cycle_length()

std::optional< std::size_t > Aleph::CA::Stationary_Detector::cycle_length ( ) const

inlinenoexcept

Return the detected cycle length.

Returns: cycle length, or std::nullopt if none has been found.

Exceptions

This	function does not throw.

Definition at line 694 of file ca-observer.H.

References cycle_length_.

◆ cycle_start()

std::optional< std::size_t > Aleph::CA::Stationary_Detector::cycle_start ( ) const

inlinenoexcept

Return the cycle start step.

Returns: start step, or std::nullopt if no cycle has been found.

Exceptions

This	function does not throw.

Definition at line 703 of file ca-observer.H.

References cycle_start_.

◆ on_step_begin()

template<typename Lattice >

void Aleph::CA::Stationary_Detector::on_step_begin	(	const std::size_t	step,
		const Lattice &	frame
	)

inline

Seed the detector with the initial frame hash.

Template Parameters

Lattice lattice type.

Parameters

[in]	step	step index about to run.
[in]	frame	frame before the step.

Exceptions

std::bad_alloc if buffering the hash allocates.

Definition at line 738 of file ca-observer.H.

References Aleph::and, Aleph::CA::frame_hash(), hashes_, Aleph::Array< T >::is_empty(), max_cycle_length_, and push().

◆ on_step_end()

template<typename Lattice >

void Aleph::CA::Stationary_Detector::on_step_end	(	std::size_t	step,
		const Lattice &	frame
	)

inline

Check the completed frame against the recent hash window.

Template Parameters

Lattice lattice type.

Parameters

[in]	step	completed step index.
[in]	frame	frame after the step.

Exceptions

std::bad_alloc if buffering the hash allocates.

Definition at line 753 of file ca-observer.H.

References Aleph::blossom_maximum_cardinality_matching(), cycle_length_, cycle_start_, Aleph::CA::frame_hash(), h, hashes_, max_cycle_length_, push(), Aleph::Array< T >::size(), and steps_.

◆ push()

void Aleph::CA::Stationary_Detector::push	(	const std::uint64_t	h,
		const std::size_t	step
	)

inlineprivatenoexcept

Definition at line 655 of file ca-observer.H.

References Aleph::Array< T >::append(), Aleph::blossom_maximum_cardinality_matching(), h, hashes_, max_cycle_length_, Aleph::Array< T >::remove_first(), Aleph::Array< T >::size(), and steps_.

Referenced by on_step_begin(), and on_step_end().

◆ reset()

void Aleph::CA::Stationary_Detector::reset ( )

inlinenoexcept

Clear buffered hashes and detected-cycle state.

Exceptions

This	function does not throw.

Complexity: O(buffered_hashes()).

Definition at line 723 of file ca-observer.H.

References Aleph::Array< T >::clear(), cycle_length_, cycle_start_, hashes_, and steps_.

Member Data Documentation

◆ cycle_length_

std::optional<std::size_t> Aleph::CA::Stationary_Detector::cycle_length_

private

Definition at line 652 of file ca-observer.H.

Referenced by cycle_detected(), cycle_length(), on_step_end(), and reset().

◆ cycle_start_

std::optional<std::size_t> Aleph::CA::Stationary_Detector::cycle_start_

private

Definition at line 653 of file ca-observer.H.

Referenced by cycle_start(), on_step_end(), and reset().

◆ hashes_

Array<std::uint64_t> Aleph::CA::Stationary_Detector::hashes_

private

Definition at line 650 of file ca-observer.H.

Referenced by buffered_hashes(), on_step_begin(), on_step_end(), push(), and reset().

◆ max_cycle_length_

std::size_t Aleph::CA::Stationary_Detector::max_cycle_length_ = 0

private

Definition at line 649 of file ca-observer.H.

Referenced by on_step_begin(), on_step_end(), and push().

◆ steps_

Array<std::size_t> Aleph::CA::Stationary_Detector::steps_

private

Definition at line 651 of file ca-observer.H.

Referenced by on_step_end(), push(), and reset().

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

ca-observer.H

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ Stationary_Detector() [1/2]

◆ Stationary_Detector() [2/2]

Member Function Documentation

◆ buffered_hashes()

◆ cycle_detected()

◆ cycle_length()

◆ cycle_start()

◆ on_step_begin()

◆ on_step_end()

◆ push()

◆ reset()

Member Data Documentation

◆ cycle_length_

◆ cycle_start_

◆ hashes_

◆ max_cycle_length_

◆ steps_