Skip navigation.

The Roost

Programming, palaver, puffins!

How to copy arrays and objects in Javascript

, , , ...

There are a few things that trip people up with regards to Javascript. One is the fact that assigning a boolean or string to a variable makes a copy of that value, while assigning an array or an object to a variable makes a reference to the value. The trouble this causes can range from befuddlement - when two variables you assume are separate are in fact references to the same value - to frustration when you realize there is no native way to tell the Javascript engine to pass a value rather than a reference.

In PHP, for example, all assignments make copies unless you explicitly tell the engine to pass a reference using the =& operator. If only it were so simple in Javascript.

I'm pretty much reinventing the wheel with this post since this issue has been solved before, but the reason I'm writing it is because up until recently I had always been designing custom functions to copy objects of types I designed myself. Very efficient on a per-case basis, but not very reusable. There had to be a way to make such a thing work for any and all arrays and objects. So I searched the interwebs and was enlightened.

Firstly, arrays. Surprisingly, arrays are easy to copy because a couple of native Array object methods actually return a copy of the array. The easiest to use is the slice() method:

var foo = [1, 2, 3];
var bar = foo;
bar[1] = 5;
alert(foo[1]);
// alerts 5

var foo = [1, 2, 3];
var bar = foo.slice(0);
bar[1] = 5;
alert(foo[1]);
// alerts 2

The slice(0) method means, return a slice of the array from element 0 to the end. In other words, the entire array. Voila, a copy of the array. The only caveat to remember here is that this method works if the array contains only simple data types, like numbers, strings and booleans. If the array contains objects or other arrays (a multi-dimensional array), then those contained "objects" will be copied by reference, retaining a connection with the source array. In such a case you will need to copy the array as a full-fledged object.

Objects are trickier because there is no native method which returns a copy of the object. So instead we add one ourselves using a prototype method:

Object.prototype.clone = function() {
  var newObj = (this instanceof Array) ? [] : {};
  for (i in this) {
    if (i == 'clone') continue;
    if (this[i] && typeof this[i] == "object") {
      newObj[i] = this[i].clone();
    } else newObj[i] = this[i]
  } return newObj;
};

Notice the recursion going on; isn't it divine? :smile: The clone() method steps through the properties of any object one by one. If the property is itself an object or array, it calls the clone() method on that object too. If the property is anything else, it just takes the value of the property. Then the result received is assigned to a property of the same name in a new object.

Finally, after we're done stepping through all properties, return the new object which is a copy of - not a reference to - the old object. A call to the clone method is as simple as this:

var foo = {a: 1, b: 2, c: 3};
var bar = foo;
bar.b = 5;
alert(foo.b);
// alerts 5

var foo = {a: 1, b: 2, c: 3};
var bar = foo.clone();
bar.b = 5;
alert(foo.b);
// alerts 2

Alphanum: Javascript Natural Sorting Algorithm

, , , ...

Today I had a need for a natural sorting function in javascript. I've seen these functions before in other languages, so I thought to myself, no problem, I'll find one in a couple of minutes!. How wrong I was!

First off, a little explanation. Natural sorting, or Lexicographical order, is sorting a list of strings which contain letters and numbers, in such a way that makes sense to humans rather than computers. Given a list of filenames, a computer would sort them this way:

z1.doc, z10.doc, z17.doc, z2.doc, z23.doc, z3.doc
While a human would sort it like so:

z1.doc, z2.doc, z3.doc, z10.doc, z17.doc, z23.doc
Obviously, the second list makes more sense, no? Anyway, I needed an algorithm that would sort any list of strings in that fashion.

Right off the bat, I found two promising candidates, but both failed quite spectacularly on my test array (which included bunches of numbers up to 1000). More searching only seemed to find blog posts which merely linked to these faulty examples.

So, giving up that angle, I decided the best way to get a natural sorting algorithm in javascript was to examine one from another language (preferably one which worked) and port it to javascript.

I ended up coming across David Koelle's Alphanum algorithm which worked like a charm. I took the Perl implementation and ported it to Javascript resulting in the function below:

function alphanum(a, b) {
  function chunkify(t) {
    var tz = [], x = 0, y = -1, n = 0, i, j;

    while (i = (j = t.charAt(x++)).charCodeAt(0)) {
      var m = (i == 46 || (i >=48 && i <= 57));
      if (m !== n) {
        tz[++y] = "";
        n = m;
      }
      tz[y] += j;
    }
    return tz;
  }

  var aa = chunkify(a);
  var bb = chunkify(b);

  for (x = 0; aa[x] && bb[x]; x++) {
    if (aa[x] !== bb[x]) {
      var c = Number(aa[x]), d = Number(bb[x]);
      if (c == aa[x] && d == bb[x]) {
        return c - d;
      } else return (aa[x] > bb[x]) ? 1 : -1;
    }
  }
  return aa.length - bb.length;
}
Note that this code is case sensitive, so "A" will sort before "a". You can turn it into a case insensitive sort by lowercasing the incoming a and b test strings. Just change the chunkify lines to:

  var aa = chunkify(a.toLowerCase());
  var bb = chunkify(b.toLowerCase());

Thanks to David K. for the algorithm! This saved me tons of time. I owe you one. :smile:

An IE Issue Appears
After first posting this script, I came across an issue in IE which caused the script to fail. Don't worry! The lines of code above are the modified - and working - alphanum function. The problem occurred in the script as originally posted; specifically with the two lines:

  a = chunkify(a);
  b = chunkify(b);
Note the variable names, where the assignment tries to place the result back into the original variable. Actually, all that's required for the bug to manifest is to assign any array to the incoming a and b variables. For some strange reason this would fail in IE6 and IE7 while sorting arrays with larger than 23 or 24 elements. In these cases, at seemingly random times during the sort, "undefined" would be passed back to a, causing the next reference to it to trigger an exception.

The following is example code (from a testcase prepared by TarquinWJ) which triggers the bug in IE. This sort will fail in IE6 and IE7.

function customsort(a, b) {
  a = ['a']; // assign an array to a
  b = ['b']; // assign an array to b

  // IE will bail out when either a or b is undefined
  return a.length - b.length;
}
var arr = [
  'a','b','c','d','e','f','g','h','i','j','k','l','m',
  'n','o','p','q','r','s','t','u','v','w','x'
];
arr.sort(customsort);
To solve this, all it took was to assign the result to new variables (aa and bb) and change all further references to a and b to the new set. Definitely a JS bug in IE, and as it involves the creation and destruction of many arrays within a short time, it is likely some kind of memory issue.

Thanks very much for TarquinWJ for helping isolate this bug.

A Faster Prototype Version
For those who value speed over flexibility, I also made this function into an Array method. Because it breaks up all the array strings first, then does the actual sorting, then joins all the sub-arrays back into strings, it is a great deal faster than the version above. That version breaks up two strings for each sort iteration rather than only once for each array element.

It's harder to modify this method to sort multi-dimensional arrays, or arrays of objects with string properties, but the speed gain is hard to ignore. As an added bonus, you can specify case sensitivity on a per-call basis with the caseInsensitive argument (true|false). If you're just going to sort plain arrays of strings, use this version.

Array.prototype.alphanumSort = function(caseInsensitive) {
  for (var z = 0, t; t = this[z]; z++) {
    this[z] = [];
    var x = 0, y = -1, n = 0, i, j;

    while (i = (j = t.charAt(x++)).charCodeAt(0)) {
      var m = (i == 46 || (i >=48 && i <= 57));
      if (m !== n) {
        this[z][++y] = "";
        n = m;
      }
      this[z][y] += j;
    }
  }

  this.sort(function(a, b) {
    for (var x = 0, aa, bb; (aa = a[x]) && (bb = b[x]); x++) {
      if (caseInsensitive) {
        aa = aa.toLowerCase();
        bb = bb.toLowerCase();
      }
      if (aa !== bb) {
        var c = Number(aa), d = Number(bb);
        if (c == aa && d == bb) {
          return c - d;
        } else return (aa > bb) ? 1 : -1;
      }
    }
    return a.length - b.length;
  });

  for (var z = 0; z < this.length; z++)
    this[z] = this[z].join("");
}

PlanetWerks 2 - Now Available!

, , , ...

Four months in the re-making, PlanetWerks 2 is now available for download from widgets.opera.com.

PlanetWerks 2 is a major overhaul of the previous version which only supported very basic controls and orbit motions. This new version now supports orientation-accurate eccentricity and inclines, which means that objects in PlanetWerks 2 orbit the sun the same way they do in the full-size solar system!

New objects have been added, such as Eris, Sedna, Orcus, Quaoar, Ixion and Varuna. Also, the major planetary satellites have been added: Ganymede, Titan, Callisto, Luna, Io, Europa, Triton, Rhea, Titania, Oberon, Iapetus, Dione, Tethys, Umbriel, Ariel and Charon.

In PlanetWerks 2, you can now switch the view to a linear scale model, so you can see just how vast the solar system really is. And if things are just too hard to see in this mode, just activate the planetoid finder [F] to help you find things quickly! Then, once you've found your favourite celetial object, four levels of zoom and rotation precision help you zero in on those great views.

Many other small aesthetic improvments combine to create a truly unique astronomical experience! Works best in the new Opera 9.5 betas. Give PlanetWerks 2 a spin :lol: today!

The Great Planet Debate

, , , ...

So it's been over a year since the International Astronomical Union demoted Pluto to what they term a "dwarf planet". I must say that this decision was a long time coming. Astronomers knew for decades that Pluto wasn't by any means massive enough to have a significant affect on other bodies within its vast and highly inclined orbit. Essentially, all theories and estimates concluded that it was only a matter of time before other bodies were found within the same area of space.

And starting in the 1990s, these bodies began being found. One after the other, with great anticipation, the lists of astronomical discoveries were lengthened. And every eager face with an eye pressed to a telescope hoped to be the one to find the Grail: a solar system body larger than Pluto.

Then, on October 21, 2003, it was found by a team headed by the unfortunately blandly named Mike Brown (in contrast, how could you forget names like Clyde Tombaugh or Percival Lowell!). This body was Eris, larger than Pluto and orbiting the Sun at an average distance 70% further than Pluto. It was Eris' discovery which finally brought to the attention of the mainstream, a question which had been plaguing astronomers for years: What is a planet?

Where We Stand
On the surface, it seemed obvious to most people. The Planets are Mercury, Venus, Earth, Mars, Jupiter, Saturn, Uranus, Neptune and Pluto; what's the big deal? Well, that list was The Planets, but the big question was rather: what set of criteria makes body A a planet and body B a non-planet? Also, should any bodies currently referred to as "planets" and "non-planets" be reclassified because of this change?

In the end, the IAU came up with three guidelines and a new set of naming conventions.

Originally posted by IAU:

The IAU therefore resolves that planets and other bodies in our Solar System, except satellites, be defined into three distinct categories in the following way:

(1) A "planet"[1] is a celestial body that: (a) is in orbit around the Sun, (b) has sufficient mass for its self-gravity to overcome rigid body forces so that it assumes a hydrostatic equilibrium (nearly round) shape, and (c) has cleared the neighbourhood around its orbit.

(2) A "dwarf planet" is a celestial body that: (a) is in orbit around the Sun, (b) has sufficient mass for its self-gravity to overcome rigid body forces so that it assumes a hydrostatic equilibrium (nearly round) shape[2], (c) has not cleared the neighbourhood around its orbit, and (d) is not a satellite.

(3) All other objects[3] except satellites orbiting the Sun shall be referred to collectively as "Small Solar System Bodies".

Footnotes:

1 The eight planets are: Mercury, Venus, Earth, Mars, Jupiter, Saturn, Uranus, and Neptune.
2 An IAU process will be established to assign borderline objects into either "dwarf planet" and other categories.
3 These currently include most of the Solar System asteroids, most Trans-Neptunian Objects (TNOs), comets, and other small bodies.

The IAU further resolves:

Pluto is a "dwarf planet" by the above definition and is recognised as the prototype of a new category of trans-Neptunian objects.



While it divided the objects in the solar system into neat categories, it also divided the astronomical community against itself. There were, and still are, significant camps of people who disagree with the new definition. And these people raise a few very legitimate concerns.

First of all, the definition cripples itself by limiting its scope to bodies orbiting the Sun. The objects we are now finding orbiting other stars are being called "extra-solar planets"; so is this wrong or right? The current definition can't say.

Second, the eight objects in the solar system which fulfil all the criteria in item (1) of the IAU proposal, are called "planets" while those fulfilling all the criteria in item (2) are called "dwarf planets". Confusingly, this means that "dwarf planets" can't be called "planets" because there is a category which already has this single name officially. At the same time, "dwarf stars" are still "stars" and "dwarf galaxies" are still "galaxies". However, "dwarf planets" are not "planets".

Finally, there is an instance of an object which technically fulfills criteria (a) and (b) of both items (1) and (2) yet is a satellite. This object is Luna, Earth's moon. A study of Luna's path around the Sun reveals that it is never concave as one might conceive in a mental image. Rather, it follows a wobbly orbit around the Sun influenced by Earth's gravity. To prevent the Moon from becoming its own dwarf planet, the extra criteria (d) was tacked on to the second definition.

An Alternate Proposal
Obviously, the definition reached by the IAU is not perfect, but it was the product of much wrangling between groups determined to implement their own view of the cosmos on the public. That the conflicting items above were introduced and retained, is only to be expected when trying to find a compromise between two groups determined to have their own way.

Well, the definition has stood for over a year now and the world hasn't fallen apart. Personally, I think it's time the definition was refined, and this time a more universal approach should be taken.

First off, it should be noted that I am a universalist when it comes to measurements. If we ever meet life out there, their systems of measurement are going to be based on their own culture and because we base our own systems on the eccentric properties of Earth and Earth's orbit, any such systems will clash in a hopeless mess. We need to devise systems of measurement which do not change, which hold true from one end of the universe to the other. Our measurements of distance are in a particularily incompatible and sorry state of affairs in this regard.

The meter? Based on the circumference of the Earth, so it's out.

Well, how about the light-year? That depends on the definition of year which depends on Earth's orbit.

Okay, then the parsec has to be it! Wrong. The parsec is how far away from the solar system you need to be for the orbit of Earth to appear 1 arcsecond in diameter, so it is also based on Earth's orbit.

To be fair, things get a little better with SI volumes and masses, which are based on water, a substance which should be ubiquitous wherever life is found.

In any case, I believe the definition of planet should be made such that it holds true no matter which cultural viewpoint is used. Thus we need to prepare a definition based solely upon observations, eschewing any cultural bias. Whereby I offer the following, new definition of "planet" and also "moon".

The New Definition

(1) A planet is a celestial body that: (a) is in orbit around a star, (b) is not itself a star, and (c) has sufficient mass for its self-gravity to overcome rigid body forces so that it assumes a hydrostatic equilibrium (nearly round) shape. This set is further subdivided into major and minor planets.

(2) A major planet is a celestial body that: (a) fulfills all the criteria of item (1) and (b) has cleared the neighbourhood around its orbit.

(3) A minor planet is a celestial body that: (a) fulfills all the criteria of item (1) and (b) has not cleared the neighbourhood around its orbit.

(4) An asteroid/comet is a celestial body that: (a) is in orbit around a star, (b) is not itself a star and (c) has insufficient mass for its self-gravity to achieve hydrostatic equilibrium.

Furthermore:
(1) A moon is a celestial body that: (a) orbits a planet (the primary), (b) forms a barycenter with the primary which is contained within the volume of the primary, (c) absent any third-party gravitational influence would continue to orbit the primary, and (d) has sufficient mass for its self-gravity to overcome rigid body forces so that it assumes a hydrostatic equilibrium (nearly round) shape.

(2) A binary (star|planet|asteroid/comet) is a pair of celestial bodies that: (a) are of the same basic type (star|planet|asteroid/comet), (b) which orbit each other forming a barycenter not contained within the volume of either body, and (c) absent any third-party gravitational influence would continue to orbit each other. The exact term depends on the largest of the system's components. For example, Pluto and Charon shall be known as a binary planet, or as a minor binary planet since at least one of the system components fulfils the minor planet criteria (in this case, both components do).

(3) All other celestial bodies which do not fulfil the criteria of item(2), but fulfil criteria (a) and (b) but not (c) of item (1) shall be collectively known as satellites. "Moon" is defined as a type of satellite.



Consequences
As a result of this new definition, Ceres, Pluto/Charon, Eris, Sedna, and a host of other solar system bodies become "planets", but the "major planets" remain the traditional eight: Mercury, Venus, Earth, Mars, Jupiter, Saturn, Uranus and Neptune. In effect, the term planet becomes synonymous with hydrostatic equilibrium, something which is easily observed and is a property of mass and gravity which holds true throughout the universe.

A second consequence is that the number of "moons" orbiting the planets will change. Earth will keep its one moon, but Mars will lose its count of two since both Phobos and Deimos haven't enough mass to acheive hydrostatic equilibrium. Instead, Mars will have two satellites, but no moons. In effect, the term moon also becomes synonymous with hydrostatic equilibrium as "planet" does.

Next, the terms "major" and "minor" describe whether or not the body co-orbits with many other bodies, or has cleared a swath due to a considerable gravitational influence.

I feel the use of these terms will assist people in visualizing what astronomers are talking about while they begin finding many more objects within other star systems. For example: "a major planet with one moon and two satellites", would be immediately interpreted to mean: a round body large enough to have cleared its orbit, with three satellites, one of which is large enough to be round.

However, the best property of this new definition is that it is based on laws of gravitation and physics which (as far as we know) hold true throughout this universe. So if we ever do meet another civilisation out there, our definitions of celestial bodies should be quite easily translatable since they have not been defined within any cultural context.

It's just too bad that we'll also have to deal with 1 meter being approximately equal to 8.28672065901862533 oogolbleks.

Digg this
December 2009
S M T W T F S
November 2009January 2010
1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31