Iterate through complex multidimensional array (Trie data structure on PHP , code Improvement) -

recently faced coding challenge had build simple trie in php, managed using php , foreach loops i'm not happy code (seems not solid should be) i'm trying implement using php's iterators.

so, have complex array ( trie ), example:

array(   'a' => array(),   'b' => array(       'a' => array(            'c' => array(                 'o' => array(                      'n' => array()                  )             )        )   ),   'x' => array(          'x' => array(                 'x' => array()           )    ) ); 

and want check if 'bacon' it's word stored on trie, process find should iterating through array , check if each node it's nested , exists, instance: need in root element key 'b', inside array array['b'] , need check if there array['b']['a'] , ['b']['a']['c'] , on.

with foreach loop able passing new array reference , check keys. using iterator seems i'm hammering code bit ( , fact when doing foreachs php copies array, makes me think solution might use lot more memory using iterators).

so code until it's while loop has condition finished stops on fail (the current array doesn't have key i'm searching) or success ( word it's complete ):

// outside loop $finished = false; $string = 'bacon'; $string = str_split($string); $queue = new splqueue(); // enqueue letters queue -> skipping because it's boring  // first while loop $iterator = new arrayiterator($array); $iterator->key(); // no match queue -> check next key  // second whileloop $iterator->next(); $iterator->key(); // matches key want dequeue (b),   $next =  new arrayiterator($array[$iterator->key()]); $queue->dequeue();  // third while loop $next->key();  // match [a] -> create new iterator $next = new arrayiterator($next[$next->key()]); $queue->dequeue();  // 4th while loop $next->key();  // match [c] -> create new iterator $next = new arrayiterator($next[$next->key()]); $queue->dequeue();  // 5th while loop $next->key();  // match [o] -> create new iterator $next = new arrayiterator($next[$next->key()]); $queue->dequeue();  // 5th while loop  $next->key();  // match [n]  $next = new arrayiterator($next[$next->key()]); $queue->dequeue(); // queue empty, throw success 

so, until it's have, fact i'm creating new arrayiterator on each loop it's bothering me, hoping hear if has better solution problem.

thanks in advance.

this challenge solve problem using iterators. although think iterators great, force think in terms of iterative approach. while problems it's ok, tasks described makes more sense use recursion.

so, think should accept answer of @cjohansson. readable , understandable.

but prove of concept here's solution using recursiveiteratoriterator. have extend class , alter bit suit our needs , reduce number of unnecessary iterations:

class trierecursiveiteratoriterator extends recursiveiteratoriterator {     protected $word;      public function __construct(         $word,         traversable $iterator,         $mode = recursiveiteratoriterator::leaves_only,         $flags = 0     ) {         $this->word = str_split($word);          parent::__construct($iterator, $mode, $flags);     }      public function next()     {         if ($this->currentlettermatched()) {             $this->updateprefix();             $this->setprefixed();            }            parent::next();     }      protected $prefix = [];     protected function updateprefix()     {         $this->prefix[$this->getdepth()] = $this->key();     }      protected $prefixed = [];     protected function setprefixed()     {         $this->prefixed = $this->current();     }      public function valid()     {         if (             $this->getdepth() < count($this->prefix)             || count($this->word) === count($this->prefix)         ) {             return false;         }          return parent::valid();     }      public function callhaschildren()     {         if ($this->currentlettermatched()) {             return parent::callhaschildren();         }          return false;     }      protected function currentlettermatched()     {         return isset($this->word[$this->getdepth()])             && $this->key() === $this->word[$this->getdepth()];     }      public function testformatches()     {         foreach ($this $_) {         }          return $this;     }      public function getprefix()     {         return implode('', $this->prefix);     }      public function getprefixed()     {         return $this->prefixed;     }      public function matchfound()     {         return ($this->word === $this->prefix);     }      public function exactmatchfound()     {         return ($this->word === $this->prefix) && empty($this->prefixed);     }      public function prefixmatchfound()     {         return ($this->word === $this->prefix) && !empty($this->prefixed);     } } 

then can following:

$iterator = new trierecursiveiteratoriterator(     $word,     new recursivearrayiterator($trie),     recursiveiteratoriterator::self_first );  $iterator->testformatches(); 

after that, can ask our $iterator different things, such as:

1. if match found: $iterator->matchfound();
2. if exact match found: $iterator->exactmatchfound();
3. if there words prefixed given word: $iterator->prefixmatchfound();
4. get prefix (when either of matches found prefix equal given word): $iterator->getprefix();
5. get endings prefixed given word: $iterator->getprefixed().

here working demo.

so can see realization not straight forward recursion one. , while big fan of iterators , spl usage, not silver bullet , should chose tools fits current needs better.

also, outside domain, class violates single responsibility principle. intentional sake of simplicity. in real life there other class wich use our iterator dependency.