This article is about a difference algorithm. It extracts changes from one version of an object to another. It helps storing a smaller amount of information.

Template

In a project, I have a template object with all the default settings for a widget.

var template = {
    achievement: {
        page: 0,
        column: "name",
        ascending: true,
        search: "",
        filter: [1, 2, 3]
    }
};

Alter it

Default settings are changed during the use of the application. It can happen when you load a configuration from an object:

var override = {
    achievement: {
        page: 1,
        ascending: false
    }
};
var settings = _.extend({}, template, override);

Or when the user clicks on the buttons, you have script that edits a copy of the template:

var settings = _.extend({}, template);
settings.achievement.page = 1;
settings.achievement.ascending = false;

Find the differences

Now, we'd like to store the current user configuration. We could simply dump the current settings variable but we can do better. Instead we want to dump only what has changed from the defaults. This has the benefit of being smaller to store and more resilient to changes.

In order to extract changes between the template and settings, I made a small function called difference (If you have a better name, feel free to suggest :)).

var override = difference(template, settings);
console.log(override);
 
// Result:
{
    achievement: {
        page: 1,
        ascending: false
    }
}

Instead of saving the full object, we only have to save 2 fields. This is therefore smaller :) In order to get the full configuration back, we simply extend the template object with the difference:

var settings = _.extend({}, template, override);

In a way, difference is the opposite of extend.

  • settings = extend(template, override)
  • override = difference(template, settings)

How it works

Once we know what we want it to do, it is fairly straightforward to write. We traverse the template and build a new object that contains only attributes that mismatch between template and override. The following implementation makes great use of underscore (isObject, isArray and isEqual).

function difference(template, override) {
    var ret = {};
    for (var name in template) {
        if (name in override) {
            if (_.isObject(override[name]) && !_.isArray(override[name])) {
                var diff = difference(template[name], override[name]);
                if (!_.isEmpty(diff)) {
                    ret[name] = diff;
                }
            } else if (!_.isEqual(template[name], override[name])) {
                ret[name] = override[name];
            }
        }
    }
    return ret;
}

Note: Any attribute that is present only in the override object will be ignored.

Conclusion

I'm still looking forward storing as much information as possible in the hash part of the URL. Two years ago, I did SmallHash to encode integer ranges. This week, with URLON and this difference algorithm, I explored another way to look at the problem, dealing with structured objects.

It is possible to combine both approaches in order to encode structured objects that also contain integer ranges. Maybe in a next blog post!

If you liked this article, you might be interested in my Twitter feed as well.
 
  • Tibor Vass

    How about "delta" instead of "difference" ? It's only 5 characters long.

  • Michaelr

    Very useful function. I'm surprised it isn't in underscore itself.

  • Chris Kimpton

    Thanks - just looking for something like this.
    It doesnt seem to diff arrays - either they are the same or not. For my needs, I think I need to provide the difference. I dont suppose you've seen something that does that on your travels :)

    Cheers,
    Chris

  • http://blog.vjeux.com/ Vjeux

    This function works on object keys. In case of arrays, keys are just 0, 1, 2, 3... So this is probably not going to do what you want. Try using underscore js difference function ( http://underscorejs.org/#difference ) which works on values ;)

  • Chris Kimpton

    Ok, thanks for that, I also found jsonDiffPatch that looks quite interesting too - https://github.com/benjamine/JsonDiffPatch

 

Related Posts

  • December 7, 2011 -- C++: Fuzzy Search with Trie (0)
    For a school project, I had to make a part of a spell-check program. Given a dictionnary of words, you have to determine all the words that are within K mistakes of the original word. Trie As input, we've got a list of words along with their frequency. For example, with the following list, we...
  • October 12, 2011 -- Intercept and alter <script> include (0)
    For a project, I want to transparently be able to intercept all the included javascript files, edit the AST and eval it. This way I can manipulate all the code of an application just by inserting a custom script. Hook the <script> tag insertion. Download the Javascript file using XHR....
  • September 24, 2011 -- Javascript: Cyclic Object Detection (3)
    URLON.stringify() suffer from a problem, when passed an object that contains a cycle, it will never stop. This article shows 3 techniques in order to detect if an object is cyclical. Edit the object: Mark In order to detect a cycle in an object, the method we learn at school is to mark each v...
  • July 8, 2012 -- Image Layout Algorithm – Lightbox (1)
    Layout Algorithms: Facebook | Google Plus | Lightbox | Lightbox Android | 500px Lightbox.com has a really interesting image layout algorithm. We're going to see how it works and its best use case. How does it work? Column based The algorithm is column based. You pick a number of...
  • August 19, 2011 -- Javascript – Stupid Idea: Hoisting at the end (0)
    JSLint imposes us to do manual hoisting of variables. What if we did it but at the end of the function? :P How you write function print_array (array) { var length = array.length; for (var i = 0; i < length; ++i) { var elem = array[i]; console.log(elem); } } How ...