de.ipcon.tools

Class SingleMovedElementLocator

java.lang.Object

de.ipcon.tools.SingleMovedElementLocator

public class SingleMovedElementLocator
extends java.lang.Object

A utility class for finding a single moved element between two integer arrays. This class is designed to work under specific, strict prerequisites regarding the nature of the change between the arrays.

Prerequisites for correct operation:

• The arrays are always the same length.
• They contain the exact same set of elements.
• Only ONE element has changed its position. (This includes adjacent swaps.)
• The relative order of ALL *other* elements remains identical.
• The value of the moved element is known and provided.
• The original index of the moved value in the old array is known and provided.

Constructor Summary

Constructors

Constructor and Description
SingleMovedElementLocator()

Method Summary

Modifier and Type	Method and Description
static int	findMovedElement(int[] oldArray, int[] newArray, int movedValueKnown, int originalIndexKnown) Finds the single moved element between two arrays.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

SingleMovedElementLocator

public SingleMovedElementLocator()

Method Detail

findMovedElement

public static int findMovedElement(int[] oldArray,
                                   int[] newArray,
                                   int movedValueKnown,
                                   int originalIndexKnown)

Finds the single moved element between two arrays.

Prerequisites:

• The arrays are always the same length.
• They contain the exact same set of elements.
• Only ONE element has changed its position. (This now includes adjacent swaps)
• The relative order of ALL OTHER elements remains identical.
• The value of the moved element is known and provided.
• The original index of the moved value in the old array is known and provided.

This algorithm leverages binary search to find the boundaries of the changed section from both ends, achieving an O(log N) time complexity for finding these boundaries, and then O(1) to deduce the moved element's details. The provided "originalIndexKnown" is used for immediate validation and to enable the O(log N) binary searches for the mismatch boundaries.

Parameters:

oldArray - The original array of integers.

newArray - The modified array of integers.

movedValueKnown - The known value of the element that moved.

originalIndexKnown - The known original index of the moved value in the old array.

Returns:

An int representing the new index, or -1 indicating "No change found" if the arrays are identical.

Throws:

java.lang.IllegalArgumentException - If the input prerequisites are violated.