Tag Archives: inheritance

Javascript Design Patterns: Strategy

For a quick assignment I was asked to write the following program:

In the language of your choosing build an application that, given an English language document as input, builds a data structure capturing the count of each word in the document.

Bonus:
Create an inverted index as well: a mapping of the words to absolute positions in the document.

As context, this is a foundational algorithm for search systems and information retrieval. Be sure to consider accuracy, complexity, and intent in the design of your program.

The last phrase was the one that got me thinking.
This sounded a little vague, so I started thinking what kind of design I can implement that would be flexible enough so I can apply the algorithms later.
This kind of program usually runs on the back end using Java/Python/etc, but obviously, the language of my choice was javascript.

I started by defining a master processor:

var Processor = function(doc) {
    this.doc = doc;
};
Processor.prototype.parse = function(parser, sorter) {
    data = parser.parse(this.doc);
    if (sorter && typeof sorter.sort === 'function') {
        return sorter.sort(data);
    }
    else {
        return data;
    }
};

This processor gets a document (in our simple example, a long string) and has parse method, which accepts a “parser” object that has a parse() method and an optional “sorter” object that has a sort() method.
As the names suggest, the former will parse the document, and the latter will sort the results.
This use of the Strategy Design Pattern will allow the application to be flexible for algorithm changes, in the future.

First, I defined an abstract Parser object.
This object is responsible to convert the input to a standard format, and apply an algorithm

var Parser = function(){};
/**
 * The implementation will return an object literal 
 * with the format {word: num, word: num ...}
 * 
 * @param str {String}
 * @returns {Object}
 */
Parser.prototype.parse = function(str){
    throw 'please extned abstract object';
};

/**
 * Convert an object literal into a sortable array
 * with the format [[word, num], [word, num], ...]
 * 
 * @param data {Object}
 * @returns {Array}
 */
Parser.prototype.convert = function(data) {
    var arr = [],
        data = data || {};
    for(var key in data) {
        if(data.hasOwnProperty(key)) {
            arr.push([key, data[key]]);
        }
    }
    return arr;
};

My next step was defining the parsers I was requested to write:
One for capturing the count of each word in the document:


var CountParser = function(arr) {
this.arr = arr;
};
CountParser.prototype = new Parser; // extend the base parser
CountParser.prototype.parse = function(str) {
var value, i, l, data = {},
arr = str.split(/[\s]+/);
for(i=0, l=arr.length; i