Iterator: CombinationsIterator

Small, short code snippets that other people may find useful. Do you have a good regex that you would like to share? Share it! Even better, the code can be commented on, and improved.

Moderator: General Moderators

Post Reply
McGruff
DevNet Master
Posts: 2893
Joined: Thu Jan 30, 2003 8:26 pm
Location: Glasgow, Scotland

Iterator: CombinationsIterator

Post by McGruff »

Updated 3rd September 2004.

Code: Select all

<?php
/*
    Class: CombinationsIterator

    Provide an iterator interface for all combinations of values in a collection of iterators, ie:
    iterator A: 1, 2, 3
    iterator B: a, b, c
    combinations returned: array(a, 1), array(a, 2), array(a, 3), array(b, 1), array(b, 2), etc..
*/
class CombinationsIterator
{
    var $_iterators;
    var $_num_iterators;

    // public
    var $is_valid = false;  // initialise false to force a reset before first use
    var $k = 0;             // pseudo-key (simple counter)
    
    /*
        param (array) 0 indexed, sequential, numerical array of (Eclipse) iterators
    */ 
    function CombinationsIterator(&$iterators) 
    {        
        $this->_iterators        =& $iterators;
        $this->_num_iterators    =  count($iterators);
    }

    /*
    */
    function reset() 
    {
        if($this->_num_iterators == 0)
        {
            $this->is_valid = false;
        
        } else {
        
            $this->is_valid = true;
            $this->k = 0;
            $this->_resetIterators();
        }
    }

    /*
        return (bool)
    */     
    function isValid() 
    {
        return $this->is_valid;
    }
    
    /*
        Advance the appropriate iterator cursor.        
        Set $is_valid = false after final combination.
    */
    function next()
    {
        $this->k++;

        for($j=$this->_num_iterators-1; $j>=0; $j--)
        {
            $this->_iterators[$j]->next();

            if($j == 0 and !$this->_iterators[$j]->isValid()) // finished
            {
                $this->is_valid = false;
                return;
            }
            if($this->_iterators[$j]->isValid())
            {
                return;
            
            } else {
            
                $this->_iterators[$j]->reset();
            }
        }
    }

    /*
        return (array)
    */
    function &getCurrent() 
    {
        $row = array();

        for($i=0; $i<$this->_num_iterators; $i++)
        {
            $row[] =& $this->_iterators[$i]->getCurrent();
        }
        return $row;
    }

    function getKey()
    {
        return $this->k;
    }

    //////////////////////////////////////////
    //              PRIVATE                 //
    //////////////////////////////////////////    
    
    function _resetIterators()
    {
        foreach(array_keys($this->_iterators) as $key)
        {
            $this->_iterators[$key]->reset();
        }
    }

}
The unit test (using SimpleTest):

Code: Select all

class TestOfCombinationsIterator extends UnitTestCase 
{
    function TestOfCombinationsIterator() 
    {
        $this->UnitTestCase();
    }

    /*
        Document behaviour with an empty array.
    */
    function testEmptyArrayParameter() 
    {
        $iterators = array();
        $cit =& new CombinationsIterator($iterators);
        
        $cit->reset();
        $this->assertFalse($cit->isValid());
        $this->assertIdentical($cit->getCurrent(), array());

        $i = 0;
        for($cit->reset(); $cit->isValid(); $cit->next())
        {
            $i++;
        }
        $this->assertIdentical($i, 0); // ie no output
    }

    /*  
        Iterators collections in $iterators param may have no members.
        Check this doesn't break things.
    */
    function testEmptyCollectionMixedWithValidCollections() 
    {
        $a = array('a', 'b', 'c');
        $b = array(1, 2, 3);
        $c = array();
        $iterators = array();
        $iterators[] =& new EclipseArrayIterator($a);
        $iterators[] =& new EclipseArrayIterator($b);
        $iterators[] =& new EclipseArrayIterator($c);
        $cit =& new CombinationsIterator($iterators);
        
        $cit->reset();
        $this->assertTrue($cit->isValid());

        $i = 0;
        for($cit->reset(); $cit->isValid(); $cit->next())
        {
            $i++;
        }
        $this->assertIdentical($i, 9);    
    }

    /*
        Document behaviour if all are empty.
    */
    function testAllEmptyCollections() 
    {
        $a = array();
        $b = array();
        $c = array();
        $iterators = array();
        $iterators[] =& new EclipseArrayIterator($a);
        $iterators[] =& new EclipseArrayIterator($b);
        $iterators[] =& new EclipseArrayIterator($c);
        $cit =& new CombinationsIterator($iterators);
        
        $cit->reset();
        $this->assertTrue($cit->isValid());

        $i = 0;
        for($cit->reset(); $cit->isValid(); $cit->next())
        {
            $i++;
        }
        $this->assertIdentical($i, 1);    

        // for reference:
        // "empty" collections always behave as if they have one value: null
        // thus a single combination is obtained from n empty collections
        // this is a numerical array with null values at each key (and n keys)
        // if null values in combinations are going to upset things, either
        // check iterator collections before passing in, or check
        // output array for null values 
        $cit->reset();
        $output = $cit->getCurrent();
        $this->assertNull($output[0]);
        $this->assertNull($output[1]);
        $this->assertNull($output[2]);    
    }

    function testWithSingleElementCollections() 
    {        
        $a = array(1);
        $b = array(2);
        $c = array(3);
        $iterators = array();
        $iterators[] =& new EclipseArrayIterator($a);
        $iterators[] =& new EclipseArrayIterator($b);
        $iterators[] =& new EclipseArrayIterator($c);
        $cit =& new CombinationsIterator($iterators);

        #!! are also testing element order here - not required
        $cit->reset();
        $output = $cit->getCurrent();
        $this->assertEqual($output[0], 1);
        $this->assertEqual($output[1], 2);
        $this->assertEqual($output[2], 3);

        // a single combination
        $cit->next();
        $this->assertFalse($cit->isValid());
    }
    
    function testReset() 
    {
        $a = array(1, 2);
        $b = array('a', 'b', 'c');
        $iterators = array();
        $iterators[] =& new EclipseArrayIterator($a);
        $iterators[] =& new EclipseArrayIterator($b);
        $cit =& new CombinationsIterator($iterators);

        $i = 0;
        for($cit->reset(); $cit->isValid(); $cit->next())
        {
            $i++;
        }
        $this->assertIdentical($i, 6);  

        $i = 0;
        for($cit->reset(); $cit->isValid(); $cit->next())
        {
            $i++;
        }
        $this->assertIdentical($i, 6);
    }
    
    function testOutput() 
    {
        $a = array(1, 2);
        $b = array('a', 'b', 'c');
        $iterators = array();
        $iterators[] =& new EclipseArrayIterator($a);
        $iterators[] =& new EclipseArrayIterator($b);
        $cit =& new CombinationsIterator($iterators);

        #!! are also testing element order here - not required
        $cit->reset();
        $output = $cit->getCurrent();
        $this->assertEqual($output[0], 1);
        $this->assertEqual($output[1], 'a');
        $cit->next();
        $output = $cit->getCurrent();
        $this->assertEqual($output[0], 1);
        $this->assertEqual($output[1], 'b');
        $cit->next();
        $output = $cit->getCurrent();
        $this->assertEqual($output[0], 1);
        $this->assertEqual($output[1], 'c');
        $cit->next();
        $output = $cit->getCurrent();
        $this->assertEqual($output[0], 2);
        $this->assertEqual($output[1], 'a');
        $cit->next();
        $output = $cit->getCurrent();
        $this->assertEqual($output[0], 2);
        $this->assertEqual($output[1], 'b');
        $cit->next();
        $output = $cit->getCurrent();
        $this->assertEqual($output[0], 2);
        $this->assertEqual($output[1], 'c');
    }

}

?>
Last edited by McGruff on Tue Aug 09, 2005 7:01 am, edited 11 times in total.
Awox
Forum Newbie
Posts: 1
Joined: Fri Apr 09, 2004 8:46 pm
Location: Coffs Harbour, Australia.
Contact:

Post by Awox »

Hi! I have been trying for hours to do something like this, I decided to google for it.. I have come across your result, but it doesn't seem to work in PHP5..
Fatal error: Call to private ArrayIterator::__construct() from context '' in /wwwsites/pepsi/web/iptables_gen/array.php on line 105
McGruff
DevNet Master
Posts: 2893
Joined: Thu Jan 30, 2003 8:26 pm
Location: Glasgow, Scotland

Post by McGruff »

Sorry I should have stated what version of php I tested it with (4.3.3 - have edited the original post).

I hardly know anything about php5 so I can't tell you why the error occurs. I'd rather not have to maintain two libraries of the "same" code (one for v4 and one for v5) so I've been waiting for v5 to become more widespread before taking time out to bone up on it. However, maybe this will prompt me to think again.
Last edited by McGruff on Mon Apr 12, 2004 8:57 am, edited 1 time in total.
McGruff
DevNet Master
Posts: 2893
Joined: Thu Jan 30, 2003 8:26 pm
Location: Glasgow, Scotland

Post by McGruff »

ArrayIterator & Iterator are now part of the standard php library http://www.zend.com/manual/ref.spl.php.

CombinationsIterator will either need a rewrite using php5 native iterators. Or you can simply change the names of Eclipse iterators so they don't conflict.
McGruff
DevNet Master
Posts: 2893
Joined: Thu Jan 30, 2003 8:26 pm
Location: Glasgow, Scotland

Post by McGruff »

Here's an example of CombinationsIterator in use: http://cgi.mcgruff.plus.com/php/search_ ... index.html

The class can sound kind of obscure when you try to describe it on its own but it was a nice solution to a problem I had generating dynamic sql in a search from processor.
Post Reply