Aleph::CA::Margolus_Update Struct Reference

Margolus 2×2 partition update for reversible CAs. More...

#include <tpl_ca_update_scheme.H>

Public Member Functions
template<typename Engine , typename Block_Rule >
void	apply_with_origin (Engine &e, Block_Rule &r, const ca_index_t origin) const
	Apply the block rule to every 2×2 block of the active partition.
template<typename Engine , typename Block_Rule >
void	apply (Engine &e, Block_Rule &r) const
	Apply the block rule using the parity of the engine step.

Static Public Member Functions
static constexpr ca_index_t	origin_for_step (const std::size_t k) noexcept
	Origin offset used at step k: even → (0,0), odd → (1,1).

Static Public Attributes
static constexpr bool	requires_double_buffer = false
	Margolus uses a single buffer; reads and writes the same lattice block by block.
static constexpr bool	requires_block_rule = true
	Operates on Block_Rule, not on cell rules.

Detailed Description

Margolus 2×2 partition update for reversible CAs.

The 2D lattice is partitioned into non-overlapping 2×2 blocks. Even steps anchor the partition at origin (0, 0) and odd steps shift it to (1, 1). A Block_Rule (tpl_ca_block_rule.H) is then applied to every block of the active partition.

Combined with an involution Block_Rule (Critters, BBM, TM Gas), the resulting CA is bit-exact reversible: undoing step k is obtained by applying the same rule to the partition with the same parity (since the rule is its own inverse).

Constraints:

• The lattice must be 2D.
• Even-sided lattices are recommended; for odd extents the partial blocks at the right/bottom edge are skipped on odd steps to preserve reversibility.
• Toroidal boundaries are recommended for fully wrapping the partition.

Margolus does not need a neighborhood: the engine should be instantiated with Null_Neighborhood<2>.

Definition at line 608 of file tpl_ca_update_scheme.H.

Member Function Documentation

apply()

template<typename Engine , typename Block_Rule >

void Aleph::CA::Margolus_Update::apply ( Engine &  e, Block_Rule &  r  ) const

inline

Apply the block rule using the parity of the engine step.

Template Parameters

Engine	engine type.
Block_Rule	block rule type.

Parameters

[in,out]	e	engine reference.
[in]	r	block rule reference.

Definition at line 671 of file tpl_ca_update_scheme.H.

References apply_with_origin(), origin_for_step(), and r.

apply_with_origin()

template<typename Engine , typename Block_Rule >

void Aleph::CA::Margolus_Update::apply_with_origin ( Engine &  e, Block_Rule &  r, const ca_index_t  origin  ) const

inline

Apply the block rule to every 2×2 block of the active partition.

Template Parameters

Engine	engine type providing current_buffer().
Block_Rule	type satisfying Block_Rule_2x2<Block_Rule, State>.

Parameters

[in,out]	e	engine reference.
[in]	r	block rule reference.
[in]	origin	offset for the partition origin (usually 0 or 1).

Exceptions

Any	exception propagated by the rule or the lattice.

Definition at line 632 of file tpl_ca_update_scheme.H.

References Aleph::blossom_maximum_cardinality_matching(), out, r, and Aleph::CA::Lattice< Storage, Boundary >::rank.

Referenced by apply().

origin_for_step()

static constexpr ca_index_t Aleph::CA::Margolus_Update::origin_for_step ( const std::size_t  k )

inlinestaticconstexprnoexcept

Origin offset used at step k: even → (0,0), odd → (1,1).

Definition at line 617 of file tpl_ca_update_scheme.H.

References k.

Referenced by apply().

Member Data Documentation

requires_block_rule

constexpr bool Aleph::CA::Margolus_Update::requires_block_rule = true

staticconstexpr

Operates on Block_Rule, not on cell rules.

Definition at line 614 of file tpl_ca_update_scheme.H.

requires_double_buffer

constexpr bool Aleph::CA::Margolus_Update::requires_double_buffer = false

staticconstexpr

Margolus uses a single buffer; reads and writes the same lattice block by block.

Definition at line 612 of file tpl_ca_update_scheme.H.

---

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

• tpl_ca_update_scheme.H