Packing strategy that assigns tiles to palettes using overload-and-remove with multi-start. More...

#include <overload_and_remove_strategy.hpp>

Inheritance diagram for porytiles::OverloadAndRemoveStrategy:

Collaboration diagram for porytiles::OverloadAndRemoveStrategy:

Public Member Functions
	OverloadAndRemoveStrategy ()=default

	OverloadAndRemoveStrategy (gsl::not_null< const UserDiagnostics * > diag)
	Constructs in preset matrix mode with diagnostics support.

	OverloadAndRemoveStrategy (std::size_t max_attempts, std::uint64_t seed, ShuffleStrategy shuffle_strategy, const UserDiagnostics *diag=nullptr)
	Constructs with explicit parameters for single-configuration mode.

ChainableResult< PackingOutput >	pack (const PackingInput &input) const override
	Packs tiles into palettes using the Overload-And-Remove algorithm with multi-start.

std::string	name () const override
	Returns the name of this strategy.

Public Member Functions inherited from porytiles::PackingStrategy
virtual	~PackingStrategy ()=default

Detailed Description

Packing strategy that assigns tiles to palettes using overload-and-remove with multi-start.

Tiles are greedily assigned to the palette with the best color overlap. When a palette becomes overloaded (exceeds its color capacity), the worst-fitting tile is removed and re-queued with that palette marked as forbidden, guaranteeing termination. A multi-start loop retries with different tile orderings controlled by ShuffleStrategy to escape local optima that defeat a single FFD pass.

The strategy supports two modes:

Preset matrix mode (default): Iterates through 17 known-good configurations (varying shuffle strategies, attempt counts, and seeds) until a solution is found. Configurations escalate from cheapest (single FFD) to most expensive (75 random attempts). Use this when the input characteristics are unknown.
Single-config mode: Runs a single multi-start search with caller-specified parameters. Use this when you know which settings work for your input, or for targeted testing and tuning.

This algorithm is based on insights and samples from:

Grange, A., Kacem, I., & Martin, S. (2018). Algorithms for the bin packing problem with overlapping items. Computers & Industrial Engineering, 115, 331–341. https://doi.org/10.1016/j.cie.2017.10.015 https://arxiv.org/pdf/1605.00558

Definition at line 40 of file overload_and_remove_strategy.hpp.

Constructor & Destructor Documentation

◆ OverloadAndRemoveStrategy() [1/3]

porytiles::OverloadAndRemoveStrategy::OverloadAndRemoveStrategy ( )

default

◆ OverloadAndRemoveStrategy() [2/3]

porytiles::OverloadAndRemoveStrategy::OverloadAndRemoveStrategy ( gsl::not_null< const UserDiagnostics * > diag )

inlineexplicit

Constructs in preset matrix mode with diagnostics support.

Uses the full 17-configuration preset matrix (default behavior) and emits a remark via the provided diagnostics when a successful configuration is found.

Parameters

diag	Diagnostics interface for emitting remarks about successful search parameters.

Definition at line 53 of file overload_and_remove_strategy.hpp.

◆ OverloadAndRemoveStrategy() [3/3]

porytiles::OverloadAndRemoveStrategy::OverloadAndRemoveStrategy	(	std::size_t	max_attempts,
		std::uint64_t	seed,
		ShuffleStrategy	shuffle_strategy,
		const UserDiagnostics *	diag = `nullptr`
	)

inlineexplicit

Constructs with explicit parameters for single-configuration mode.

When constructed with this constructor, the strategy runs a single multi-start search with the provided parameters instead of iterating through the preset configuration matrix.

Parameters

max_attempts	Maximum number of packing attempts (first uses FFD, subsequent use shuffled orderings).
seed	Base seed for the PRNG used to generate shuffle seeds.
shuffle_strategy	Strategy for generating tile orderings in retry attempts.
diag	Optional diagnostics interface for emitting remarks about successful search parameters.

Definition at line 67 of file overload_and_remove_strategy.hpp.

Member Function Documentation

◆ name()

std::string porytiles::OverloadAndRemoveStrategy::name ( ) const

inlineoverridevirtual

Returns the name of this strategy.

Returns: "Overload-And-Remove"

Implements porytiles::PackingStrategy.

Definition at line 95 of file overload_and_remove_strategy.hpp.

◆ pack()

ChainableResult< PackingOutput > porytiles::OverloadAndRemoveStrategy::pack ( const PackingInput & input ) const

overridevirtual

Packs tiles into palettes using the Overload-And-Remove algorithm with multi-start.

In preset matrix mode, tries 17 search configurations (varying shuffle strategies, attempt counts, and seeds) until a valid assignment is found. In single-config mode, runs one multi-start search with the configured parameters. Returns the first successful result, or an error if all configurations fail.

Parameters

input The packing input containing tiles, hints, fixed slots, and constraints.

Returns: A PackingOutput on success, or an error if packing fails.

Implements porytiles::PackingStrategy.

Definition at line 172 of file overload_and_remove_strategy.cpp.

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

porytiles/include/porytiles/domain/packing/services/overload_and_remove_strategy.hpp
porytiles/lib/domain/packing/services/overload_and_remove_strategy.cpp

Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ OverloadAndRemoveStrategy() [1/3]

◆ OverloadAndRemoveStrategy() [2/3]

◆ OverloadAndRemoveStrategy() [3/3]

Member Function Documentation

◆ name()

◆ pack()