How to recursively build a list of Item Substitutions when multiple substitutes exist

Question

In Microsoft Dynamics Nav 2013, there is a feature for specifying Item Substitutions for an item (product); However, you can specify more than one substitution for a single product and technically a substitution can itself have one or more substitutions.

I am trying to build a recursive solution in PHP that allows me to take a known product code, and recursively search for item substitutions to generate a one dimensional array of items. If this were a one to one relationship (parent,child) this would be a trivial task for me, but the fact that there can be multiple childs on any given iteration is kind of blowing my mind.

My question is if anyone knows how to write a recursive method for the situation I've described above? Below I will layout the way the data is structured to give a better understanding of the problem:

$lineItems = array(
    'XXX-0',
    'XXX-1',
    'XXX-3'
);

$substitutionsLookup = array(
    0 => array('No_' => 'XXX-1', 'Substitute No_' => 'XXX-2'),
    1 => array('No_' => 'XXX-3', 'Substitute No_' => 'XXX-4'),
    2 => array('No_' => 'XXX-3', 'Substitute No_' => 'XXX-5'),
    3 => array('No_' => 'XXX-5', 'Substitute No_' => 'XXX-6')
);

// Resulting product code substitutions for XXX-0
$result1 = array();

// Resulting product code substitutions for XXX-1
$result2 = array('XXX-2');

// Resulting product code substitutions for XXX-3
$result3 = array('XXX-4', 'XXX-6');

Edit (added my attempt to solve using recursive method):

protected function getSubstitutions($haystack, $needle, &$results = array())
{
    if (count($haystack) == 0)
    {
        return false;
    }

    $matches = array();   
    foreach ($haystack as $index => $check)
    {
        if ($check['No_'] === $needle)
        {
            $newHaystack = $haystack;
            unset($newHaystack[$index]);

            $moreMatches = $this->getSubstitutions($newHaystack, $check['Substitute No_'], $results);

            if ($moreMatches === false)
            {
                $matches[] = $check['Substitute No_'];
            }
        }
    }

    if (count($matches))
    {
        foreach($matches as $match)
        {
            $results[] = $match;
        }
    }

    return $results;
}

Edit (Final code used, derived from accepted answer):

class ItemSubstitutionService implements ServiceLocatorAwareInterface
{    
    public function getSubstitutions($itemNo, $noInventoryFilter = true, $recursive = true)
    {
        $substitutions = array();
        $directSubs = $this->itemSubstitutionTable->getSubstitutionsByNo($itemNo);

        if ($recursive)
        {
            foreach($directSubs as $sub)
            {
                $this->getSubstitutionsRecursive($sub, $substitutions);
            }
        } else {
            $substitutions = $directSubs;
        }

        foreach($substitutions as $index => $sub)
        {
            $inventory = $this->itemLedgerEntryTable->getQuantityOnHand($sub->getSubstituteNo());
            $sub->setInventory($inventory);

            if ($noInventoryFilter)
            {
                if ($inventory == 0)
                {
                    unset($substitutions[$index]);
                }
            }
        }

        return $substitutions;
    }

    private function getSubstitutionsRecursive(ItemSubstitution $sub, &$subs)
    {
        $directSubs = $this->itemSubstitutionTable->getSubstitutionsByNo($sub->getSubstituteNo());
        if (empty($directSubs))
        {
            $subs[$sub->getSubstituteNo()] = $sub;
        }

        foreach($directSubs as $curSub)
        {
            $this->getSubstitutionsRecursive($curSub, $subs);
        }
    }
}

I'm not sure I understand your question perfectly, but why would you like to do it recursively? The way I'm looking at it you don't seem to need any recursion. Could you explain it further, or perhaps show some of your actual code? — Bono, Dec 17 '14 at 19:51
It might not even need solved recursively. It just seemed to me like it did, and I'm a little lost on how to solve it at all. I will update with code I have written so far. — sdaugherty, Dec 17 '14 at 20:04
So you're trying to build a list of all possible substitutes for a particular item? Perhaps a Codeunit exposed via Web Services would let you leverage NAV logic & code instead of trying to sort it yourself, separating it from the PHP layer. — Jake Edwards, Dec 17 '14 at 21:25
I completely agree with you Shadow but unfortunately at my company we don't have a developers license, it's very costly to get our Nav partner to do any work, and I am sure that I wouldn't get approval for something like that anyway. All I have to work with is my Zend Framework 2 environment that I've cooked up to solve this problem. Ugh... — sdaugherty, Dec 17 '14 at 21:46
I have updated the the question to reflect the code I wrote so far that doesn't seem to work. — sdaugherty, Dec 17 '14 at 22:19
We are using Item Substitutions as a way to indicate Item replacements. The reason I wanted to do this recursively is because when I looked at the data I noticed item substitutions that also had substitutions. I wanted to follow the path of substitutions down to the final items that have no more substitutions. I suspect that this is not the intended purpose of Item Substitutions, but it's all I have to work with for the time being. — sdaugherty, Jan 02 '15 at 20:45
ShadowXVII, There is an Item Subst. Codeunit that I published as a web service but it seemed to be erroring out (Internal 500 error) when trying to use it. Ultimately what you suggested is where I would like to go. Thanks for your input. — sdaugherty, Jan 02 '15 at 20:48

score 1 · Accepted Answer · answered Dec 18 '14 at 21:46

This code could serve as a solution for your example. I just presume that you fetch the list of 'direct' items substitutes from your database, so you could replace GetDirectSubstitutes with the code that fetches the substitutes list for the given item (I used you example array as a data source).

Just be careful - this simple implementation doesn't check for cyclical references. If your initial data contains loops, this code will stuck.

function GetDirectSubstitutes($itemNo)
{
    global $substitutionsLookup;
    $items = array();
    foreach ($substitutionsLookup as $itemPair) {
        if ($itemPair['No'] == $itemNo) {
            array_push($items, $itemPair['SubstNo']);
        }
    }

    return $items;
}

function GetSubstitutesTree($itemNo, &$substitutes)
{
    $directSubst = GetDirectSubstitutes($itemNo);
    if (!empty($directSubst)) {
        $substitutes = array_merge($substitutes, $directSubst);
        foreach ($directSubst as $item) {
            GetSubstitutesTree($item, $substitutes);
        }
    }
}

I realized that I only want to add substitutions at the end of the tree lookup that had no more substitutes. But this demonstrated how to solve the problem successfully the way I asked the question. Thank you! — sdaugherty, Jan 02 '15 at 17:38

How to recursively build a list of Item Substitutions when multiple substitutes exist

1 Answers1