Sentinels in JavaScript

Can you find the substring?

Can you find the substring?

In older procedural languages, the return values that came back from a function were restricted. If you said you were going to return a number, you returned a number. If you wanted to sometimes return a number, but other times return an indication of failure, you resorted to what is known as a “sentinel value” to return the failure.

A sentinel value is a number that doesn’t represent the answer to the problem that the function was asked to solve, but instead flags the caller to the fact that something rather out-of-the-ordinary has happened. For example, a value of -1 can indicate the end of a file being read in.

The problem with a sentinel is that it means nothing special to the language. The programmer has to keep in mind that the sentinel exists and that it has to be handled on every call that could possibly generate the sentinel value. Programmers are notorious for paying attention to and handling sentinels only when they crash a program.

Also, the programmer has to be careful in choosing the value. Is it 0? -1? 99? 255? 999? -999? MAXINT? The choice can bite you if you’ve misunderstood the possible values that can be generated in your function. I regret to inform you that I once wrote a BASIC program that had three different sentinel values returned from three different subroutines!

Sentinel values sound old and busted, don’t they? Their usage fell a bit once we could pass around pointers to data structures. With a little more elbow room, we could put a “success” boolean right up front in the data structure and do away with a lot of sentinels.

They Live!

But sentinels are still around. In JavaScript, the string method “indexOf” returns a -1 if the needle (substring) can’t be found in the haystack (the string to be searched).

Let’s look at a few different ways we can deal with that awkward -1.

function wrappedIndexOf(needle,haystack) {
    var res=haystack.indexOf(needle);
    if (res===-1) {
        res=false;
    }
    return res;
}

And you call it like this:

res=wrappedIndexOf(needle,haystack);
if (res!==false) {
    location=res;
}

We haven’t done much here but replace the need to check explicitly for -1 with a need to check explicitly for false. Too weird to sometimes return a number and sometimes return a boolean? Yeah, probably. I like it a bit better than the numeric sentinel because the calling code makes the exception check a bit more obvious. Because JavaScript functions can return just about anything (including wild things like anonymous functions), you always need to think about what can come out of a function, so what’s important is a consistent convention.

Similarly, you could return null or undefined.

But let’s move on to another solution–returning an object.

function wrappedIndexOf(needle,haystack) {
    var res=haystack.indexOf(needle);
    if (res===-1) {
        res={"success":false,"value":-1};
    } else {
        res={"success":true,"value":res};
    }
    return res;
}

And you call it like this:

obj=wrappedIndexOf(needle,haystack);
if (obj.success) {
    location=obj.value;
}

Note that I’ve left the -1 in obj.value, so you can still use that as a sentinel if you like.

What makes JavaScript really good for this task? Its object literals. You don’t need to have a structure or class around to hold the extra info. You just build the object on the fly and return it.

Bitwise, Byte Foolish?

 

To avoid Carnival, Logan is trying to get some plastic surgery from Farrah Fawcett.

To avoid Carnival, Logan is trying to get some plastic surgery from Farrah Fawcett.

In the post-apocalyptic world of Logan’s Run, humans live out cramped lives in a bunker. Because of the crowded conditions, all citizens must submit to Carnival on their 30th birthdays. What do you do on your Carnival day? You and all the other 30 year olds spiral up into the air and get zapped to death.

Sound like a bad deal? It gets worse. The radiation outside has long since subsided, and the rules being enforced are no longer necessary.

I’ve been immersed in JavaScript for the last few years. Every time I’ve read about JavaScript’s bit operations (and it has a very nice set of ops), I’ve been warned that they are “a hack,” and “slow.” This has always bummed me out. I love bits.

But I got to thinking the other day, all these warnings sound like a sort of a Logan’s Run passed-down message from days gone by. With all the cool things that have been going on with JavaScript lately (thanks to Google’s V8 and the various JIT subsystems going into browsers), maybe, just maybe, bitwise operations have sped up enough to be worthwhile. Since some of the JIT compilers are doing type inference, a series of bit operations could, in theory, be done at full speed, without costly implicit type conversions.

Who Needs Bits?

When I started programming (on 8-bit processors), I mostly worked with integers. When floating point numbers became available, I avoided them for years because they were slow. We did as much math as we could with integers and bit operations. Shift left once, and that’s a multiplication by 2. If you wanted to multiply by 10, you’d do a shift left by one (times two) and a shift left by 3 (times eight) and add those results together.

You wouldn’t do math like that any more, but bits are still good as flags. A single JavaScript number (when treated bitwise) can hold 32 boolean flags!

Here’s what I found out. Just about everything I tried was faster with bitwise operations than with other solutions (even in Internet Explorer). No, you can’t usefully replace one multiplication with a series of adds and shifts, but by no means are bitwise operators too slow to be useful.

        k=~~i; //this is much faster
        k=Math.floor(i); //than this

You can lop off the decimal part of a number not just with ~~, but with ^0 and <<0, too. And they are ALL significantly faster, in all modern major browsers, than calling Math.floor().

//break a number in the range 0-65535 into
// low and high bytes

// this is significantly faster
    lo = i & 255;
    hi = i >> 8;

//than this
    lo = i % 256;
    hi = (i-lo)/256;

Don’t discriminate against JavaScript’s bitwise operators. But keep these things in mind…

  1. You have 32 bits to work with when you treat a JavaScript variable as bits. And that top bit is a sign bit (meaning any number with that top bit set is a negative number).
  2. Don’t mistake bitwise for logical operators.
  3. Learn the difference between “-” and “~”.
  4. Remember that >> shifts the sign bit down while >>> shifts a zero into the top bit.

My favorite place to learn about JavaScript bitwise facilities is here: Bitwise Operators.

When should you be using bitwise operators? Obviously, when you want to pack a bunch of flags into one variable. That should be much faster than having an array of flags.

Dealing with the red, blue, and green parts of a color call out for bitwise operators.

And think about using a shift when you want to multiply or divide by a power of 2, while at the same time converting a floating point number into an integer. Two operations for the price of one!

Review: Balsamiq Mockups

How do you design the layout of a website? My favorite way is with Balsamiq Mockups, which I first heard about at Ajaxian. Why Balsamiq?

  • Very short learning curve. Anyone on the team can make changes to the layout or leave notes on it.
  • The mockup looks like a mockup, so no client or team member carries around the assumption that the work is already done.
  • Designs take just a couple of minutes, so no one moans when a change is made.
I’m going to time myself making a mockup of the coverflow iTunes page in Mockups to show you how fast it really is. OK. Launching the program…now! (1:18PM.)
Balsamiq Mockups

Balsamiq Mockups

OK. I’m back. 1:31PM. It took me 13 minutes. My take on iTunes isn’t perfect, but it’s a good start, and the team can talk about whether this is really the way we want this.

I used the desktop version. It’s $80 for one user.

http://www.balsamiq.com/products/mockups/desktop

Nice!

Balsamiq is well thought out. As you drag content around it snaps to likely places to help you line items up with other items. The snaps are not hard, though — you can drop anything anywhere. You can even overlap items.

Also nice is the ability to group and ungroup items. You can drop a window in, fill it with smaller items, then group the window and its objects together and move them around as a group.

You can also duplicate items or groups.

Snags?

Balsamiq works pretty much the way I want it to. There are a couple quirks I noticed as I started working, though.

When I’m working in the extreme right top corner, opening the options menu blocks my view of the object I’m modifying. I got in the habit of dragging things out of the corner before opening the options menu.

I looked for a way to import a jpg or png file so I could get a logo into the mockup. No luck.

I couldn’t figure out how to print a mockup directly. I had to export it as an image and print that image.

On the export to image, I wanted an option to keep the notebook background. I think the fake paper look enhances the idea that this is a mockup, and not the real thing. If you want to keep that look, you have to take a screenshot.

Future

I don’t know what Balsamiq has in mind for the product’s future. What I’d like to see is Mockups rolled into Google Apps. This would be a perfect tool for collaborative app interface design.

I spent a lot of time exporting images and pulling them into a Google Presentation. Google, buy this company!

Combinations and Permutations in JavaScript

Range

In JavaScript Numbers Can Bite, I talked about a problem that can crop up in JavaScript when you’re doing calculations with integers.

At the end of the post I hinted at a better way to write the combination function. Let’s go ahead and implement it. I’ll throw a permutation function in as well.

Let’s look at combinations. The formula is:

n!/(k!*(n-k)!)

That’s for n items, taken k at a time. In my mom’s family, there were seven children. How many combinations of them are there if you take 4 at a time?

7!/(4!*3!)

Now, if we write out the factorials, we immediately see a simplification (not in notation, but in floating point operations).

(7*6*5*4*3*2*1)/(4*3*2*1*3*2*1) = (7*6*5)/(3*2*1)

What we need here is a function that multiplies a range of numbers. Then we have:

productRange(5,7)/productRange(1,3)

or more generally,

productRange(k+1,n)/productRange(1,n-k)
function productRange(a,b) {
  var product=a,i=a;

  while (i++<b) {
    product*=i;
  }
  return product;
}

function combinations(n,k) {
  if (n==k) {
    return 1;
  } else {
    k=Math.max(k,n-k);
    return productRange(k+1,n)/productRange(1,n-k);
  }
}

So that’s combinations, where the order of the items doesn’t matter. What about permutations, where the order does matter? The formula is:

n!/(n-k)!

That one is simple…

function permutations(n,k) {
  return productRange(k+1,n);
}

Eliminating Duplicates

Multiplicity

Yesterday I ran into a programming problem and I didn’t like any of the solutions I came up with. I went to bed kind of grouchy about it.

Here’s the problem: Given a huge number of strings, return an array that has each string appear just once. Eliminate all duplicates.

This is a common enough problem in programming that there exists a large body of literature about it.

The solutions I found, though, were pretty ugly. They either involved nested loops and a lot of comparisons, or brain-busting regular expressions.

Now, I’m always willing to look at the regular expression solution to a problem, but for me a RegEx solution is a lot of work. It’s like trying to dredge up my high school Latin. You know the joke–there are 10 kinds of programmers, those who understand Regular Expressions, and those who don’t.

I wanted small, simple code. I couldn’t find anything that really felt right.

Going with the Flow

What kept bugging me? In the back of my head, I kept thinking that all these solutions are coming from other languages. They’re not taking advantage of JavaScript.

Isn’t there something in JavaScript that naturally removes duplicates? And finally, it hit me: object keys.

Objects in JavaScript are hashes–they are made of two parts: the left part and the right part.

{"left":right}

The key is unique, but of course the value can be duplicated.

Then I had it: The “key” is the key. All I have to do is loop through the strings and assign them to the keys of an object. Hashes are an automatic duplicate removal machine.

And it works. JavaScript does the work of eliminating the duplicates naturally. I’m not doing the heavy lifting in JavaScript. Instead, JavaScript is doing the heavy lifting internally in some kick-ass compiled C loop.

My code stays clean and minty fresh because I’m relying on heavily tested and optimized code inside the JavaScript interpreter of the browser.

function eliminateDuplicates(arr) {
  var i,
      len=arr.length,
      out=[],
      obj={};

  for (i=0;i<len;i++) {
    obj[arr[i]]=0;
  }
  for (i in obj) {
    out.push(i);
  }
  return out;
}

var a=[];
var b=[];

a[0]="fish";
a[1]="fishes";
a[2]="fish";
a[3]="1";
a[4]="fishes";

b=eliminateDuplicates(a);
console.log(a);
console.log(b);

---

["fish", "fishes", "fish", "1", "fishes"]
["fish", "fishes", "1"]

Further

Armed with this concept, I was able to simplify my code even more. My data didn't start out as an array. Instead, it was coming from a file, so I just grabbed the strings as they came in and stuffed them right into the object as keys.

Every language has its own strengths and weaknesses. You get a nice feeling when you finally see the problem you're trying to solve in the context of the tool you're using to do the job.

Default Parameters, Episode V

I keep a pretty close eye on the searches that bring people to this blog. A lot of you are searching for how to sort in JavaScript (I’ll have to go into more detail on sorting soon). And a whole mess of you want to know about missing and default parameters.

I’m going to take another shot at the default parameter problem. I gave a solution that adds just one line of code per function, but it requires you to pass all parameters in a single object. I’ll adapt that solution to better handle the normal way of passing JavaScript parameters.

Really quickly, let’s talk about JavaScript parameters.

  1. When you pass in fewer than the expected number of parameters, the missing ones come in as undefined.
  2. When you pass in more than the expected number of parameters, the excess ones can be slurped out of the arguments pseudo-array. This array-like variable has the length method, but is missing other array methods.
  3. A common way to implement default parameters is with a series of statements like this: a=a || 1; The problem with such a statement is that so many different values evaluate to false that it’s easy to make a mistake and prevent a valid number like 0 from coming through.
  4. A better way to implement default parameters is like this: if (a===undefined) a=1;
  5. Another common way is if (a==null) a=1; This works pretty well because null and undefined are loosely equal to each other, but other falsy values aren’t equal to either of them.

Let’s modify my defaultHandler from my previous post on the subject so that it works with arrays instead of objects.

    defaultHandler=function(defaults,params) {
        var i;
        for (i=0;i<defaults.length;i++) {
            if (params[i]!==undefined) {
                defaults[i]=params[i];
            }
        }
        return defaults;
    }

Choose Your Poison

You now have a couple choices on how to use it. After the default handler is called, the array params will hold all your parameters in order.

    function test(a,b,c) {
        var params=defaultHandler([1,"banana",3],arguments);

        console.log(params);
    }

If you really want to, you can stuff the values back into the original named parameters…

    function test(a,b,c) {
        var params=defaultHandler([1,"banana",3],arguments);
        a=params[0];
        b=params[1];
        c=params[2];

        console.log(a,b,c);
    }

It’s a shame there’s no way to automate that stuffing of the parameters back into the original variables, isn’t it?

Ah, but there is. In fact, the whole process can be cleaned up with a bit of metaprogramming and some introspection. But that’s for Episode VI.

Note: This is the second post on default parameters. I took a cue from George Lucas on its numbering to try to get some search hits from the Star Wars zealots.

JavaScript Functions are Weird, Too

Remember when I said that JavaScript arrays are weird because they are also objects? Aside from their numbered elements, they can have, in addition, hash elements (a key and a value).

Believe it or not, functions in JavaScript are just as weird. They also are objects. If you have a function named bar, it can have a property named foo.

Doesn’t seem very useful, does it? After all, functions can already have variables declared inside them.

The difference? These special function elements persist from one call of the function to the next. You can use them to replace global variables that might otherwise cause unsightly clutter.

For instance, if you want a function to keep track of how many times it’s been called, this does the trick:

function add(a,b) {
  if (add.called===undefined) {
    add.called=0;
  }
  add.called++;
  return a+b;
}

or, more tersely but confusingly,

function add(a,b) {
  add.called=add.called+1 || 1;
  return a+b;
}

You don’t have to call the function by its name when you’re in the function, you can use arguments.callee instead.

How about a real world example. [Warning: You probably won’t get your money’s worth unless you compare the before-and-after code. I suggest copying and pasting them into a diff program so you can see the changes highlighted. Or you could just print out this whole blog post and take it to the bathroom.]

Alert! Unresponsive Script!

Sometimes, you might have some code that takes so long to execute that the browser alerts the user that a script has become unresponsive. That tends to take a long time for new browsers (they assume you might be running a Rich Internet Application and that such messages may be worse than the trouble they’re trying to solve), but for old browsers (like my nemesis IE6), the time is short. Something like 3 seconds.

Yummy Morsels

To solve this problem we have to break up work into bite-sized pieces.

Here’s our before case, the brute force (slow) solution to finding prime numbers. Adapted from a C version here.

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN">
<html lang="en">
<head>
    <title><!-- Insert your title here --></title>
    <script type="text/javascript">
        function findPrimes(topCandidate) {
            var primes=[];

            candidate = 2;
            while (candidate <= topCandidate) {
                trialDivisor = 2;
                       prime = true;
                while (trialDivisor * trialDivisor <= candidate) {
                    if (candidate % trialDivisor === 0) {
                        prime = false;
                        break;
                    }
                    trialDivisor++;
                }
                if (prime) {
                    primes.push(candidate);
                }
                candidate++;
            }
            return primes.length;
        }
    </script>
</head>
<body>
    <!-- Insert your content here -->
    <form action="">
        <input type="button"
               onclick='alert(findPrimes(100000))'
               value="Find Primes" />
    </form>
</body>
</html>

Now here’s the version where we only let 1000 numbers be checked at once. After 1000 have been done, we fall out of the code, but before we go we trigger a setTimeout with a delay time of 0. That’s all we need to do to let the browser catch its breath.

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN">
<html lang="en">
<head>
<title><!-- Insert your title here --></title>
<script type="text/javascript">
    function findPrimes2(topCandidate) {
        var persist=arguments.callee;
        var tries=0;
        if (persist.candidate===undefined) {
            persist.candidate=2;
            persist.primes=[];
            persist.topCandidate=topCandidate;
        }
        keepTrying = true;
        while (persist.candidate <= persist.topCandidate && keepTrying) {
            trialDivisor = 2;
            prime = true;
            while (trialDivisor * trialDivisor <= persist.candidate) {
                if (persist.candidate % trialDivisor === 0) {
                    prime = false;
                    break;
                }
                trialDivisor++;
            }
            if (prime) {
                persist.primes.push(persist.candidate);
            }
            persist.candidate++;
            tries++;
            if (tries>1000) {
                keepTrying=false;
            }
        }
        if (keepTrying) {
            persist.candidate=undefined;
            alert(persist.primes.length);
        } else {
            setTimeout(persist,0);
        }
    }
    </script>
</head>
<body>
    <!-- Insert your content here -->
    <form action="">
        <input type="button"
               onclick='findPrimes2(100000)'
               value="Find Primes" />
    </form>
</body>
</html>

Compare the two versions. In the second, I’ve short-circuited the loop so that it only checks 1000 numbers to see if they are prime. To keep comparisons easy, I’ve tried to make the least number of changes I could. In real-world cases, you start with the idea that you’re going to work in chunks, and your code ends up cleaner.

Some Are Sticky, Some Aren’t

We’ve made some of the variables persistent. These are the ones that have to be kept across invocations of the function. All other variables dry up and blow away.

Since arguments.callee is such a long name, I’ve set the variable persist to hold the current function name.

This is not a recursive function. We let the function finish. It’s set up to be called again with setTimeout. You don’t want to wait around in busy loops, making the browser all gummy and unresponsive.

If you do have responsiveness problems, put a longer delay and check fewer candidates at a time. This will make the process take longer, of course. It’s a trade-off.

Any wait longer than a couple seconds is going to make the user wonder what’s going on. A progress bar is the best solution for long waits. For short waits, a throbberis OK.

Program flow is not obvious when using setTimeout to control flow. In larger programs when you’re using this technique, you may want some kind of handler that’s in charge of passing control from one section of the code to another, instead of hardcoded setTimeout chaining.

Falsies

We call values that loosely evaluate to false “falsy.” What does “loosely” mean in this context? There are two comparison operators to test equivalence in JavaScript (== and ===). The first is loose, and the second is strict.

The results of the loose form are sometimes surprising, as you’ll soon find out.

What sorts of things are falsy? Douglas Crockford lists these: 0, NaN, the empty string(” or “”), false, null, undefined. In essence, they are the zero or false or empty versions of JavaScript’s various types.

Tripped Up

The worst trouble I have with falsy values are when I’m comparing to a number and I forget that 0 might be one of the numbers I’m going to get. I did this recently in my sorting post in the final bit of code. I used == when I should have used ===. (Note: I’ve since fixed the code in that post.)

I’ve had this blog post in my mind for about a month. I’ve been waiting for a stroke of brilliance to come so I could make all this falsy stuff completely clear once and for all. The stroke of brilliance never came, so I’ve decided to make a table for you that tell what falsy values loosely and strictly equal other falsy values.

== / === false 0 NaN null undefined “” (empty string) ” ” (white space) [] {}
false yes/yes yes/no no/no no/no no/no yes/no yes/no yes/no no/no
0 yes/no yes/yes no/no no/no no/no yes/no yes/no yes/no no/no
NaN no/no no/no no/no no/no no/no no/no no/no no/no no/no
null no/no no/no no/no yes/yes yes/no no/no no/no no/no no/no
undefined no/no no/no no/no yes/no yes/yes no/no no/no no/no no/no
“” (empty string) yes/no yes/no no/no no/no no/no yes/yes no/no yes/no no/no
” ” (white space) yes/no yes/no no/no no/no no/no no/no yes/yes no/no no/no
[] yes/no yes/no no/no no/no no/no yes/no no/no no/no no/no
{} no/no no/no no/no no/no no/no no/no no/no no/no no/no

In the table above, you see the result of each value when compared loosely (with ==), then when compared strictly (with ===). The next table tries to convert each value logically by negating the negation of it.

value !!value
false false
0 false
NaN false
null false
undefined false
“” (empty string) false
” ” (white space) true
[] true
{} true

Eye-Popping Results

Most interesting observations from the tables? How about NaN, which doesn’t even loosely equal itself? The empty object {} is the same way. They are the ultimate Dr. No’s. Interestingly, the empty array loosely equals false, 0, and the empty string.

A string of white space loosely equals more than I thought it would.

0 and false are pretty damned close to each other.

According to the first chart, NaN, null, undefined, and {} are not falsy, because they don’t equal false in a loose comparison. In the second chart, ” ” (white space), [], and {} and not falsy.

So, now you know why it’s safer to use ===. If you find a good use for ==, make sure you’ve thought hard about things that might go wrong. I might even go so far as to say you should comment every usage of ==, because it’s bound to be misunderstood in many cases.

Can you tell falsies when you see them? I used to think I could, but now I’m not so sure.

Do While Once in a While

The other day, a programmer I follow on Twitter was pleased because he had found a good use for a do/while loop.

When a programmer gets excited by a loop construct, you know something is wrong. The truth is that do/while is underutilized, not just in JavaScript but in all C-based languages.

The rule of thumb is that you should use always use a do/while loop when the body of the loop must execute at least once. Use a while loop when the body of the loop may never execute.

Maybe it’s true that a while loop is indicated more often than a do/while loop, but I’ve often seen programmers do a little jury-rigging to patch up the while loop to do their bidding when a do/while would have meant less typing and have made more sense.

Why? Well, programmers get into habits. If you get to know while very well, you may be shy about using do/while.

But I think there’s some clumsiness inherent in do/while that also plays a part in its unpopularity. It’s a result of JavaScript getting its syntax genes from C rather than the Wirth family of languages. Pascal and the others (Modula-2 and Oberon) used repeat/until

    JavaScript
do {
  a = a + 1;
} while (a!==10);

    Pascal
repeat
  a := a + 1
until a = 10;

I think repeat/until is superior to do/while for these reasons:

  • In JavaScript, the reuse of the identifier “while” is awkward. When you see it, you tend to expect the loop body to come after it. See how it just sits there AFTER the close brace? Like a teenage boy avoiding a girl at a middle school dance.
  • do/while‘s ending condition is the same as while‘s starting condition. Pascal’s until condition is logically negated, which I think is more natural at the end of a loop. Do something over and over UNTIL something is true, rather than do something over and over WHILE something is true. REPEAT UNTIL i hits 5, rather than DO WHILE i is less than 5. A possible solution would be to allow do/until as well as do/while. This would allow for backward compatibility. Someone remind me I said that the next time I invent my own computer language.

In short, the do/while construct just doesn’t sit quite right in C, encouraging the overuse of the while loop, which sits just fine. In any case, repeat/until seems to get more use in Pascal than do/while gets in C.

Don’t forget do/while is there, waiting for you to be excited to use it. It’s the right choice when you must execute the body at least once.

Sort of Confusing

Some of the worst JavaScript code I have seen has to do with sorting data.

JavaScript has a flexible array sort method, but it takes a while to get the hang of using it. Programmers seem to do fine sorting a simple array, but if the data format is something just a bit less trivial, many JavaScript programmers throw their hands up in the air. You can almost see the frustration in the code (sometimes in the comments).

One common situation that many people seem stumped by is sorting an array of objects based on a given key.

Suppose we have this array of objects:

    arr[0]={r:100,g:100,b:250};
    arr[1]={r:50,g:127,b:255};
    arr[2]={r:255,g:255,b:100};

Now suppose you want to sort the array by any of r, g, or b, and that you want to support both ascending and descending sorts. How would you approach the problem?

Back To Basics

Remember that to sort an array, you just invoke the “sort” method that belongs to JavaScript’s array type.

    arr.sort();

That works for sorting an array of strings, but it doesn’t work for sorting an array of numbers. That’s why even the novice JavaScript programmer recognizes the code for sorting numeric values.

    function sortNumber(a,b) {
        return a - b;
    }

    arr.sort(sortNumber);

JavaScript lets us pass in a function that is used to judge whether a value is less than, equal, or greater than another value.

Having that hook into the guts of the sort method lets us solve just about any sorting problem. But how?

Here’s a solution for the {r,g,b} problem above, where I want to be able to sort on r, g, or b in either ascending or descending mode.

    function sortByKey(arr,key,direction) {
        function sortNumeric(a,b) {
            if (direction=="ASC") {
                return a[key]-b[key];
            } else {
                return b[key]-a[key];   
            }
        }       
        return arr.sort(sortNumeric);
    }

The outer function is a handy way to keep the key (what we’re sorting on) and direction (which way we’re sorting) around, since there is no simple way to pass that information into the sort method. Remember that the inner function has access to the outer function’s variables, and that includes the parameters that come in.

Oh, by the way, the code is easier to understand if you recall that obj.r is the same as obj[“r”]. We can pass in a string to a function and use that string as a key to get a value. That way we get around the need to write a separate evaluation function for each key.

Call the function like this:

    sortByKey(arr,"r","DESC");

to sort the objects in descending r order, or

    sortByKey(arr,"g","ASC");

to sort the objects in ascending g order.

Real Life Intrudes

Sometimes the data is not nice. You may have blank (empty or missing) spots in your data. In Excel, whether you sort ascending or descending, cells that are empty always show up at the end of the list. I recently needed to match that functionality in an Adobe AIR utility program I was writing. Here’s the code (blank cells from Excel ended up as empty strings in my data).

    function sortByKey(arr,key,direction) {
        function sortNumeric(a,b) {
            var c=a[key],d=b[key];
            if (direction=="ASC") {
                return (c==="")-(d==="") || c-d;
            } else {
                return (c==="")-(d==="") || d-c;   
            }
        }       
        return arr.sort(sortNumeric);
     }

A bit longer, codewise. But exactly what I needed for my data.

Once you get the hang of using inner functions, JavaScript’s sort method makes much more sense. It’s easy to extend this idea to accomodate other kinds of data (like strings), or to support secondary sorts, where a second key can be used to break ties.

« Older entries

Follow

Get every new post delivered to your Inbox.