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

Question

Recently I was faced with a coding challenge where I had to build a simple trie in php, I managed to do it using php and foreach loops but I'm not happy with the code itself (seems not solid as it should be) so I'm trying to implement it using php's iterators.

So, I have a complex array ( a trie ), for example:

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

And I want to check if 'bacon' it's a word stored on this trie, the process to find it should be by iterating through the array and check if each node it's nested and exists, for instance: I need in the root the element with key 'b', then inside the array array['b'] , I need to check if I there is array['b']['a'] , then ['b']['a']['c'] and so on.

With a foreach loop I was able to do so by passing the new array by reference and check the keys. Now using a iterator it seems I'm hammering the code a bit ( and the fact that when doing foreachs php copies the array, makes me think that this solution might use a lot more memory than using iterators).

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

// OUTSIDE THE LOOP
$finished = false;
$string = 'bacon';
$string = str_split($string);
$queue = new SplQueue();
// Enqueue all the letters to the queue -> skipping this because it's boring

// FIRST WHILE LOOP
$iterator = new ArrayIterator($array);
$iterator->key(); // No match with queue -> check next key

// SECOND WHILELOOP
$iterator->next();
$iterator->key(); // Matches with the key I want do 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, up until now it's this I have, but the fact I'm creating a new ArrayIterator on each loop it's bothering me, so I was hoping to hear if someone has a better solution to this problem.

Thanks in advance.

If the code is already working you'll probably have better luck at codereview.stackexchange.com — Chris
– Chris, Commented Nov 8, 2016 at 12:14

score 2 · Accepted Answer · 2016-11-24 09:59:30Z

Here is code for a recursive algorithm which will iterate any number of levels:

<?php
$trie = array(
    'a' => array(),
    'b' => array(
        'a' => array(
            'c' => array(
                'o' => array(
                    'n' => array()
                )
            )
        )
    ),
    'x' => array(
        'x' => array(
            'x' => array()
        )
    )
);

/**
 * @param string $word
 * @param array $array
 * @param int [$i = 0]
 */
function findWord($word, $array, $i = 0)
{
    $letter = substr($word, $i, 1);
    if (isset($array[$letter])) {
        if ($i == strlen($word) - 1) {
            return true;
        } else if ($i < strlen($word)) {
            return findWord($word, $array[$letter], $i + 1);
        }
    }
    return false;
}

if (findWord('bacon', $trie)) {
    die("Did find word.");
} else {
    die("Didn't find word.");
}

Here is code for a iterative algorithm which will iterate any number of levels and should be memory and cpu efficient:

<?php

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

/**
 * @param string $word
 * @param array $array
 */
function findWord($word, $array)
{
    $tmpArray = $array;
    for ($i = 0; $i < strlen($word); $i++)
    {
        $letter = substr($word, $i, 1);
        if (isset($tmpArray[$letter])) {
            if ($i == strlen($word) - 1) {
                return true;
            } else {
                $tmpArray = $tmpArray[$letter];
            }
        } else {
            break;
        }
    }
    return false;
}

if (findWord('bacon', $trie)) {
    die("Did find word.");
} else {
    die("Didn't find word.");
}

Hi @cjohansson , I allready had a recursive algorithm built on top of an array, the problem lied in the memory that's why I was hoping iterators would help me on this one. Nonthe less, great answer

sevavietl · Accepted Answer · 2016-11-10 18:30:52Z

This is a good challenge to solve this problem using iterators. Although I think that iterators are great, but they force you to think in terms of iterative approach. While for some problems it's ok, but for tasks like you described it makes more sense to use recursion.

So, I think that you should accept the answer of @cjohansson. As it is readable and understandable.

But just as a prove of concept here's my solution using RecursiveIteratorIterator. We have to extend this class and alter it a bit to suit our needs and also to reduce the 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 as $_) {
        }

        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 we can do following:

$iterator = new TrieRecursiveIteratorIterator(
    $word,
    new RecursiveArrayIterator($trie),
    RecursiveIteratorIterator::SELF_FIRST
);

$iterator->testForMatches();

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

If match was found: $iterator->matchFound();
If exact match was found: $iterator->exactMatchFound();
If there are words that prefixed with given word: $iterator->prefixMatchFound();
Get prefix itself (when either of matches were found the prefix will be equal to given word): $iterator->getPrefix();
Get endings prefixed with given word: $iterator->getPrefixed().

Here is working demo.

So as you can see this realization is not as straight forward as recursion one. And while I am a big fan of iterators and SPL usage, but this is not a silver bullet and you should chose tools that fits your current needs better.

Also, this is outside the domain, but my class violates Single responsibility principle. This was intentional for the sake of simplicity. In real life there would be the other class wich will use our iterator as dependency.

Perfect answer mate, I'd upvote this 100 times if I could. The problem on this exercise was memory leaks, I was hoping that using recursion would help me because as far as I know, for loops store the array temporarily in the memory so, iterators should be the perfect solution ( at least it's what my intuition says ) . Thanks a lot for this

Collectives™ on Stack Overflow

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

2 Answers 2

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related