Deep Copy of Arrays

With jPaq and many other JavaScript libraries, it is very easy to do a shallow copy of an array. On the other hand, it isn’t as easy to do a deep copy of arrays. For this reason, I plan on replacing the Array.prototype.clone() function with the following:

Array.prototype.clone = function(doDeepCopy) {
    if(doDeepCopy) {
        var encountered = [{
            a : this,
            b : []
        }];

        var item,
            levels = [{a:this, b:encountered[0].b, i:0}],
            level = 0,
            i = 0,
            len = this.length;

        while(i < len) {
            item = levels[level].a[i];
            if(Object.prototype.toString.call(item) === "[object Array]") {
                for(var j = encountered.length - 1; j >= 0; j--) {
                    if(encountered[j].a === item) {
                        levels[level].b.push(encountered[j].b);
                        break;
                    }
                }
                if(j < 0) {
                    encountered.push(j = {
                        a : item,
                        b : []
                    });
                    levels[level].b.push(j.b);
                    levels[level].i = i + 1;
                    levels[++level] = {a:item, b:j.b, i:0};
                    i = -1;
                    len = item.length;
                }
            }
            else {
                levels[level].b.push(item);
            }

            if(++i == len && level > 0) {
                levels.pop();
                i = levels[--level].i;
                len = levels[level].a.length;
            }
        }

        return encountered[0].b;
    }
    else {
        return this.slice(0);
    }
};

The above code can be used to make deep copies of arrays. It is important to note, though, that only sub-arrays are deeply copied, not objects. The reason so much code is used is to even make it possible to make a deep copy of a recursive array structure. The following code exemplifies how to use this function:

// Create a recursive array to prove that the cloning function can handle it.
var arrOriginal = [1,2,3];
arrOriginal.push(arrOriginal);

// Make a shallow copy of the recursive array.
var arrShallowCopy = arrOriginal.clone();

// Prove that the shallow copy isn't the same as a deep copy by showing that
// arrShallowCopy contains arrOriginal.
alert("It is " + (arrShallowCopy[3] === arrOriginal)
    + " that arrShallowCopy contains arrOriginal.");

// Make a deep copy of the recursive array.
var arrDeepCopy = arrOriginal.clone(true);

// Prove that the deep copy really works by showing that the original array is
// not the fourth item in arrDeepCopy but that this new array is.
alert("It is "
    + (arrDeepCopy[3] !== arrOriginal && arrDeepCopy === arrDeepCopy[3])
    + " that arrDeepCopy contains itself and not arrOriginal.");

If you want to use this code right now, there is nothing stopping you. The code doesn’t require any library references and is fully cross-browser compatible. A JSBin example can be found here. It even works in JScript. The only thing that I ask is that you give credit where it is due. šŸ˜€

Power Set

As I was beefing up my past implementation of cartesianProductOf(), I decided to look into set theory a little bit more. After looking through some Wikipedia pages, I found another process that may be of interest to JavaScript programmers that have to deal with sets: a JavaScript implementation of finding a power set. Here is my code to do this:

function powerSetOf(arrFull) {
  var ret = [], fullLen = arrFull.length, last = fullLen - 1;
  function get(arrPrefix, start, lenToFind) {
    for(lenToFind--; start < fullLen; start++)
      if(!lenToFind)
        ret.push(arrPrefix.concat([arrFull[start]]));
      else if(start < last)
        get(arrPrefix.concat([arrFull[start]]), start + 1, lenToFind);
  }
  for(var lenToFind = fullLen; lenToFind > 0; lenToFind--)
    get([], 0, lenToFind);
  return ret.concat([[]]);
}

Although the above code works, I couldn’t help think that there was a simpler way of achieving the same goal. After fumbling around the idea in my head, I came up with the following, shorter solution:

function powerSetOf(arr) {
  var item, ret = [[]], max = arr.length - 1;
  function fn(arrPrefix, start) {
    for(; ret.push(item = arrPrefix.concat([arr[start]])) && start < max;)
      fn(item, ++start);
  }
  if(max + 1)
    fn([], 0);
  return ret;
}

Unlike the first solution, the above one does not return the results ordered by size. On the other hand, this solution is shorter, an works faster.

You may have noticed that neither solution removes duplicates if they exist within the array. If you want to remove all duplicates from an array, you can make a build of jPaq that has the Array.prototype.uniquify() function and then use it as follows:

// Your array of numbers or whatever.
var arr = [1,2,1,3,4,3,2];

// Get the power set for your array.
var arrPowerSet = powerSetOf(arr.uniquify());

Cartesian Product of Multiple Arrays

A few weeks ago, I came across a question about finding the cartesian product of two or more arrays in JavaScript. For anybody who is looking to do so, I posted the following code on stackoverflow:

function cartesianProductOf() {
  return Array.prototype.reduce.call(arguments, function(a, b) {
    var ret = [];
    a.forEach(function(a) {
      b.forEach(function(b) {
        ret.push(a.concat([b]));
      });
    });
    return ret;
  }, [[]]);
}

It is important to note that the above code will only work on newer browsers that implement Array.prototype.forEach() and Array.prototype.reduce(). If you must allow this function to be used on any browser or even in a stand-alone Windows Host Script, I would suggest using this version of jPaq which implements the functions if they aren’t already present. As of yet, I have not received any requests to see this in a JavaScript library. If you do want it in a library, let me know of your suggestions for a better name than cartesianProductOf. My issue with the name is that it is too long.