Uses the “The Tortoise and the Hare” algorithm to detect loops.

Description

For every step of the algorithm, the hare takes two steps and the tortoise one.
If the hare ever laps the tortoise, there must be a loop.

Parameters

$callbackcallablerequired

Function that accepts ( ID, callback_arg, … ) and outputs parent_ID.

$startintrequired

The ID to start the loop check at.

$overridearrayoptional

An array of ( ID => parent_ID, … ) to use instead of $callback.

Default:array()

$callback_argsarrayoptional

Additional arguments to send to $callback.

Default:array()

$_return_loopbooloptional

Return loop members or just detect presence of loop? Only set to true if you already know the given $start is part of a loop (otherwise the returned array might include branches).

Default:false

Return

Source

function wp_find_hierarchy_loop_tortoise_hare( $callback, $start, $override = array(), $callback_args = array(), $_return_loop = false ) {
	$tortoise        = $start;
	$hare            = $start;
	$evanescent_hare = $start;
	$return          = array();

	// Set evanescent_hare to one past hare. Increment hare two steps.
	while (
		$tortoise
	&&
		( $evanescent_hare = isset( $override[ $hare ] ) ? $override[ $hare ] : call_user_func_array( $callback, array_merge( array( $hare ), $callback_args ) ) )
	&&
		( $hare = isset( $override[ $evanescent_hare ] ) ? $override[ $evanescent_hare ] : call_user_func_array( $callback, array_merge( array( $evanescent_hare ), $callback_args ) ) )
	) {
		if ( $_return_loop ) {
			$return[ $tortoise ]        = true;
			$return[ $evanescent_hare ] = true;
			$return[ $hare ]            = true;
		}

		// Tortoise got lapped - must be a loop.
		if ( $tortoise === $evanescent_hare || $tortoise === $hare ) {
			return $_return_loop ? $return : $tortoise;
		}

		// Increment tortoise by one step.
		$tortoise = isset( $override[ $tortoise ] ) ? $override[ $tortoise ] : call_user_func_array( $callback, array_merge( array( $tortoise ), $callback_args ) );
	}

	return false;
}

View all references View on Trac View on GitHub

Changelog