Compare a segment of an array (with wildcards)
Posted: Sun Oct 01, 2006 7:10 am
I'm trying to check if a slice of an array exists in a (possibly) larger array. The slice we look for can contain wilcard values represented by "*". A wildcard constitutes NONE or MORE values so if it's midway in the sequence, or at the start we can keep skipping non-matching values until we find a match. If the wildcard is at the end it can simply be disregarded since it's not worth checking.
I've been playing around with this all night and still can't quite get it right so I'm throwing it out here in case on of you can. Try to avoid using PHP-specific functions since this is needed in JavaScript and PHP. I can translate it if needs be though
Here's a test case the clarify what I mean:
Kudos to anyone who can manage this
It seemed simple upon first thought but it's the wildacards that cause headaches
EDIT | Test case fixed
I've been playing around with this all night and still can't quite get it right so I'm throwing it out here in case on of you can. Try to avoid using PHP-specific functions since this is needed in JavaScript and PHP. I can translate it if needs be though
Here's a test case the clarify what I mean:
Code: Select all
function array_sequence_compare($wanted_sequence=array(), $master_sequence=array())
{
//
}
class TestOfSequenceMatching extends UnitTestCase
{
//A sequence to check against
protected $masterArray = array('x', 'y', 'x', 'x', 'x', 'z', 'a', 'a', 'b', 'a', 'c', 'd', 'e', 'f', 'f', 'f', 'g');
public function testCanFindStraightForwardSequences()
{
$this->assertTrue(array_sequence_compare(array('x', 'y', 'x', 'x', 'x', 'z', 'a', 'a', 'b', 'a', 'c', 'd', 'e', 'f', 'f', 'f', 'g'), $this->masterArray));
$this->assertTrue(array_sequence_compare(array('a', 'a', 'b'), $this->masterArray));
$this->assertTrue(array_sequence_compare(array('x'), $this->masterArray));
$this->assertTrue(array_sequence_compare(array('g'), $this->masterArray));
$this->assertTrue(array_sequence_compare(array('d', 'e', 'f', 'f', 'f', 'g'), $this->masterArray));
$this->assertTrue(array_sequence_compare(array('b', 'a'), $this->masterArray));
$this->assertTrue(array_sequence_compare(array('z', 'a', 'a', 'b', 'a'), $this->masterArray));
}
public function testReturnsFalseWhenStraightForwardSequenceNotFound()
{
$this->assertFalse(array_sequence_compare(array('a', 'g'), $this->masterArray));
$this->assertFalse(array_sequence_compare(array('h'), $this->masterArray));
$this->assertFalse(array_sequence_compare(array('c', 'd', 'e', 'f', 'g'), $this->masterArray));
$this->assertFalse(array_sequence_compare(array('x', 'x', 'a'), $this->masterArray));
$this->assertFalse(array_sequence_compare(array('b', 'a', 'c', 'd', 'z'), $this->masterArray));
$this->assertFalse(array_sequence_compare(array('x', 'f'), $this->masterArray));
}
public function testReturnsTrueForEmptyArray()
{
$this->assertTrue(array_sequence_compare(array(), $this->masterArray));
}
public function testReturnsTrueForWilcardsAtStart()
{
$this->assertTrue(array_sequence_compare(array('*'), $this->masterArray));
$this->assertTrue(array_sequence_compare(array('*', 'd', 'e', 'f'), $this->masterArray));
$this->assertTrue(array_sequence_compare(array('*', 'x', 'y', 'x'), $this->masterArray));
$this->assertTrue(array_sequence_compare(array('*', 'a', 'b', 'a', 'c', 'd'), $this->masterArray));
$this->assertTrue(array_sequence_compare(array('*', 'x', 'y', 'x', 'x', 'x', 'z', 'a', 'a', 'b', 'a', 'c', 'd', 'e', 'f', 'f', 'f', 'g'), $this->masterArray));
}
public function testCanSkipZeroOrMoreTimesForWilcards()
{
$this->assertTrue(array_sequence_compare(array('x', '*', 'a'), $this->masterArray));
$this->assertTrue(array_sequence_compare(array('d', 'e', 'f', '*', 'g'), $this->masterArray));
$this->assertTrue(array_sequence_compare(array('x', '*', 'g'), $this->masterArray));
$this->assertTrue(array_sequence_compare(array('c', 'd', '*', 'e'), $this->masterArray));
$this->assertTrue(array_sequence_compare(array('x', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', 'x'), $this->masterArray));
}
public function testReturnsFalseWhenWildcardNotInSuitablePosition()
{
$this->assertFalse(array_sequence_compare(array('e', '*', 'x'), $this->masterArray));
$this->assertFalse(array_sequence_compare(array('f', 'f', '*', 'a'), $this->masterArray));
$this->assertFalse(array_sequence_compare(array('b', 'a', 'c', 'd', '*', 'z'), $this->masterArray));
$this->assertFalse(array_sequence_compare(array('a', '*', 'c', '*', 'z'), $this->masterArray));
}
public function testReturnsTrueWhenWilcardAtEndOfAnyValidSequence()
{
$this->assertTrue(array_sequence_compare(array('x', 'y', 'x', 'x', 'x', 'z', 'a', 'a', 'b', 'a', 'c', 'd', 'e', 'f', 'f', 'f', 'g', '*'), $this->masterArray));
$this->assertTrue(array_sequence_compare(array('a', 'a', 'b', '*'), $this->masterArray));
$this->assertTrue(array_sequence_compare(array('x', '*'), $this->masterArray));
$this->assertTrue(array_sequence_compare(array('g', '*'), $this->masterArray));
$this->assertTrue(array_sequence_compare(array('d', 'e', 'f', 'f', 'f', 'g', '*'), $this->masterArray));
$this->assertTrue(array_sequence_compare(array('b', 'a', '*'), $this->masterArray));
$this->assertTrue(array_sequence_compare(array('z', 'a', 'a', 'b', 'a', '*'), $this->masterArray));
}
}EDIT | Test case fixed