JavaScript non-recursive Depth First Search to compare, match and return matching values from an unknown number of arrays with unknown length

Question

As the title says, I am in search for a non-recursive solution that accepts an array of objects each containing an array stored in a property named "dataMap" and can be any size and length. The objects stored in the array have two properties: dataMap (type Array) and i (type Number).

I found and read through this other post here on Stack Overflow but am not drawing a parallel to how it pertains to my problem. Non-recursive depth first search algorithm

Example data structure:

Array[
       {
          dataMap:[...N],
          i:0
       },
       {
          dataMap:[...N],
          i:0
       },
       ...N
]

Assume (from the above):

• "Array" is of any length, unknown at runtime
• "dataMap" is of any length, unknown at runtime
• "dataMap" data type in each index is arbitrary and can be any data type (In my example I just used numbers to keep it simple)

Edit addendum 1.0: Target environment for solution deployment is Internet Explorer 10 and ECMASript 5. The solution needs to match all pairs even if they are repeated. In my original recursive solution, if you run the code you will see each matched pair printed regardless if it was a duplicate. This is due to the fact that each of these arrays are representing data sets containing data from other databases that, when matched, I need to grab some pieces of other information about the row and return it. This is just backstory but is not particularly relevant to the question or solution as I tried to simplify it for brevity. End Edit addendum 1.0:

I have a recursive solution, but after finishing and testing it will only work with the amount (or close to) of objects that are uncommented. If you uncomment the last object in the array and run the program, you will get a stack overflow. I hope it is suitable to read.

var a = 
[
    {
    dataMap:[1,75,7,8,4,2,4,5,6,5,4,34,5,67,7,74,6,3,6,78,8,2,4],
    i:0
  },
  {
    dataMap:[2,5,8,6,5,4,6,4,5,76,8,8],
    i:0
  },
  {
    dataMap:[1,75,7,8,4,2,4,5,6],
    i:0
  },
  /*{
    dataMap:[3,5,7,5,4,3,5,7,56,7,9,6,5,2,2,5],
    i:0
  }*/


];


(function foo(array,level,compare){

  compare[level] = array[level].dataMap[array[level].i];


  if(typeof array[level-1] === "undefined"){
    // First array
    if(array[level].i == array[level].dataMap.length-1){
      // were at the end of the first array;
      return;
    }else{
      level++;
      array[level].i = 0;
    }
  }else if(typeof array[level+1] === "undefined"){
    // last array
    if(array[level].i == array[level].dataMap.length-1){
      level--;
      //array[level].i++;
    }
    array[level].i++;
  }else{
    // somewhere in the middle
    if(array[level].i == array[level].dataMap.length-1){
      // if at the end
      if(array[level+1].i == array[level+1].dataMap.length-1){
        //if the array below me is at their end
        // go up
        level--;
        array[level].i++;
      }
    }else{
      level++;
      array[level].i = 0;
    }
  }

  var t = true;
  for(var z=0;z<compare.length;z++){
    if(typeof compare[z+1] !== "undefined" && t != false && compare[z] != compare[z+1]){
        t = false;
    }
  }
  if(t){
    console.log("FOUND ONE:" + JSON.stringify(compare));
  }
  foo(array,level,compare);

})(a,0,[]);

The reason for selecting a recursive function is that the matching results from the comparison will eventually be returned to be stored in a variable who is executing this code via a self executing inline function. Recursion is what I thought I needed but clearly see there are memory issues.

jQuery may be used. I chose to use pure JS.

So, is there a way to accomplish what I am asking? My mind goes to breaking it out into functions but wont that cause the same memory issues?

Answer 1

This solution maybe is not the best, but I tried and it works.

var array = 
[
    {
    dataMap:[1,1,75,34,8,4,2,4,5,6,5,4,34,5,67,7,74,6,3,6,78,8,2,4,67],
    i:0
  },
  {
    dataMap:[1,2,5,8,6,5,4,6,4,5,76,8,7,67],
    i:0
  },
  {
    dataMap:[1,75,8,4,2,4,5,67,6],
    i:0
  },
  {
    dataMap:[11,3,5,7,5,54,3,5,7,67,56,7,9,6,5,2,2,5],
    i:0
  }


];

/**
* Save no duplicated data to compare after
* Set, allow us to add no duplicated data
* https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set 
*/
addNoDuplicated = ( ( array, noDuplicated ) => {
  
  array.map( ( item ) => {
    
    item.dataMap.map( (data) => {
      
      noDuplicated.add( data );
      
    });
    
  } )
  
} )

deepSearchAndPrint = ( array, noDuplicated, duplicatedItSelf, accumDuplicated ) => {
  
  addNoDuplicated( array, noDuplicated );
  
  for ( let elem of noDuplicated ) { 
    
    accumDuplicated[elem] = [ ];
        
    array.map( ( item , index) => {
      
      duplicatedItSelf[index] = [];
      
      item.dataMap.map( ( data ) => { 
        
        // avoid add duplicated
        if ( data === elem && duplicatedItSelf[index].indexOf(data) === -1 ) {
          
          duplicatedItSelf[index].push(data);
                    
          accumDuplicated[elem].push(data)
          
        }
        
      } )
      
    })
    
    /**
    * check if sizes are equal, if they are equal, is a valid case
    */
    if ( accumDuplicated[elem].length === array.length ) {
      
      console.log( accumDuplicated[elem] );
      
    }
    
  }
    
}

deepSearchAndPrint( array, new Set(), { }, { } );

UPDATE

This other solution is using normal loop function and function declarations.

var array = 
[
    {
    dataMap:[1,1],
    i:0
  },
  {
    dataMap:[1,3],
    i:0
  }/*,
  {
    dataMap:[1,7],
    i:0
  },
  {
    dataMap:[3,1],
    i:0
  }*/


];

/**
* Save all no duplicated data contained into each dataMap array
* noDuplicated: [1, 3]
* This is going to help us to compare
*/
function addNoDuplicated( array, noDuplicated ) {
  
  for ( let item of array ) {
  
    
    for ( let data of item.dataMap ) {
      
      // if they are primitive data type we use indexOf to check exist
      if ( noDuplicated.indexOf( data ) === -1 ) {
        
        noDuplicated.push( data );
        
      }
      
    };
  }
  
}

function deepSearchAndPrint( array, noDuplicated, duplicatedItSelf, accumDuplicated ) {
  
  addNoDuplicated( array, noDuplicated );
  
  /**
  * start looping through noDuplicated data array
  */
  
  // you can use normal loop here if you want
  for ( let elem of noDuplicated ) { 
    
    /**
    * create an array to each no repeated element 
    * noDuplicated: [1, 3]
    * accumDuplicated[elem] => 1: [],3: [], .... 
    */
    accumDuplicated[elem] = [ ];
    
    const arraySize = array.length;
    
    /**
    * iterate through our original array data structure
    */
    for ( let index = 0; index < arraySize; index++ ) {
     
      duplicatedItSelf[index] = [];
      
      const dataSize = array[index].dataMap.length;
      
      /**
      * iterate through each dataMap array
      */
      for ( let indexData = 0; indexData < dataSize; indexData++ ) { 
      
        let data = array[index].dataMap[indexData];
        
        /** 
        * avoid add duplicated values into a same array(dataMap)
        * e.g 
        * dataMap:[1,1]
        * dataMap:[1,3]
        * duplicatedItSelf[0] = [1]
        * duplicatedItSelf[1] = [1,3]
        */
        if ( data === elem && duplicatedItSelf[index].indexOf(data) === -1 ) {
          
          duplicatedItSelf[index].push(data);
          /**
          * save into accumDuplicated array according to key of noDuplicated data array
          * accumDuplicated[1] = [1]
          * accumDuplicated[1] = [1, 1]
          */
          accumDuplicated[elem].push(data)
          // console.log(accumDuplicated); // uncomment to verify
        }
        
      }
      
    }
    /**
    * if accumDuplicated in its own key has the same length as the general array => << match >>
    * accumDuplicated[0] = [1, 1] =>  = 2
    * array              = [ {}, {} ] = 2 
    */
    if ( accumDuplicated[elem].length === array.length ) {
      
       console.log( accumDuplicated[elem] );
      
    }
    
  }
  
}

deepSearchAndPrint( array, [ ], { }, { } );

I hope that helps you :)