UNB/ CS/ David Bremner/ teaching/ cs2613/ labs/ CS2613 Lab 11

Background

Array methods

Time
10 minutes
Activity
Demo

In Lab 10 we used a few Array methods like length. It turns out that JavaScript arrays have some useful higher order methods, i.e. methods that take functions as arguments.

    function average (array) {
        return array.reduce(function (a,b) {__________}, 0)/array.length;
    }
    console.log(average([1,2,3]));
    function average2 (array) {
        var sum=0;
        array.forEach(function (a) { __________ });
        return sum/array.length;
    }

Flatten

Time
25 minutes
Activity
Small groups

Solve the Flatten Exercise using reduce and concat methods. Your solution should pass the following test suite. Notice that one of the specs is disabled ("pending"); that's because this solution only works for one level of nesting. This motivates the task of implimenting flatten recursively in A3

flatten=require("./flatten.js").flatten;
describe("flatten",
     function () {
         it("base case",
        function () {
            expect(flatten([])).toEqual([]);
        });
         it("single element",
        function () {
            expect(flatten([1])).toEqual([1]);
            expect(flatten(["foo"])).toEqual(["foo"]);
            expect(flatten([{foo: 1}])).toEqual([{foo: 1}]);
        });
         it("longer list, no mutation",
        function () {
            var data = [[1],2,[3],4,[5,6]];
            var orig_data = data;
            expect(flatten(data)).toEqual([1,2,3,4,5,6]);
            expect(data).toEqual(orig_data);
        });
        xit("deeper nesting",
        function () {
            var data = [[[1],2,[3]],4,[5,6]];
            var orig_data = data;
            expect(flatten(data)).toEqual([1,2,3,4,5,6]);
            expect(data).toEqual(orig_data);
        });

     });

JSON

Time
15 minutes
Activity
Demo/Group discussion

Like Assignment 2, Assignment 3 includes a question about parsing JSON. The syntax should look more familiar now that we have studied JavaScript a bit. The book embeds ancestry.json in a JavaScript string, which feels a bit fake, because we start out with a perfectly good data structure and then squash it into a string. Since we're using node.js, we can reasonably simply read the JSON from a file.

var fs = require('fs');

function read_json_file(filename) {
    var contents = fs.readFileSync(filename);

    return JSON.parse(contents);
}
exports.read_json_file=read_json_file;

Here we consider another way simulate "object-like" behaviour, by using a closure. The way that by_name is defined is a bit complicated, but it allows us to keep the variable data between calls. Which of for or forEach makes the most sense here?

var read_json_file=require("./read_json_file.js").read_json_file;

var by_name = (function () {
    var data = null;
    var real_by_name= function(name){
        if (data===null)
            data=read_json_file("big.json");
        // simple linear scan

        return null;
    };
    return real_by_name;
})();

exports.by_name=by_name;

Here are some tests that our function should pass.

by_name=require("./ancestry.js").by_name;
describe("by_name", function() {
    it("not-present", function() {
        expect(by_name("ronald mcdonald")).toBe(null);
        expect(by_name("Captain Ahab")).toBe(null);
    });
    it("first", function () {
        expect(by_name("Carolus Haverbeke")).toEqual({"name": "Carolus Haverbeke", "sex": "m", "born": 1832, "died": 1905, "father": "Carel Haverbeke", "mother": "Maria van Brussel"});
    });
    it("last", function () {
        expect(by_name("Jacobus Bernardus van Brussel")).toEqual({"name": "Jacobus Bernardus van Brussel", "sex": "m", "born": 1736, "died": 1809, "father": "Jan van Brussel", "mother": "Elisabeth Haverbeke"});
    });
    it("middle", function () {
        expect(by_name("Joanna de Pape")).toEqual(  {"name": "Joanna de Pape", "sex": "f", "born": 1654, "died": 1723, "father": "Vincent de Pape", "mother": "Petronella Wauters"});
    });

});

Methods

Time
25 minutes
Activity
Group discussion / Demo

We know about objects in JavaScript, and we can use them in a simple way by e.g. naming conventions for functions.

function timePlus(time1, time2) {
    var mins = (time1.mins + time2.mins) % 60;
    var hours = time1.hours + time2.hours + Math.floor((time1.mins+time2.mins)/60);
    return {'hours': hours, 'mins': mins};
}

console.log(timePlus({hours: 10, mins:30}, {hours: 17, mins:47}));

If we want to have "time" objects with a "plus" method, one way is to add that method manually. In order for that to work, we need to make use of the JavaScript variable this. When the function method is called as object.method(), the special variable this is defined to mean the current object.

function maketime(hours, mins){
    var plus=function (other) {
        var raw=timePlus(this,other);
        return ______________________________
    };

    return { 'hours': hours, 'mins': mins, 'plus': plus};
}

var A=maketime(10, 30);
var B=maketime(17, 47);
var C=A.plus(B);
console.log(C);

Adding methods manually to newly created objects is a bit painful, so JavaScript has the notion of a 'prototype'

var protoTime = {
    plus: function(other) {
        var raw=timePlus(this,other);
        return timeNew(raw.hours, raw.mins);
    }
};

function timeNew(hours, mins) {
    var obj=Object.create(protoTime);
    _______________;
    _____________;
    return obj;
}

D=timeNew(21,42);
E=timeNew(17,37);

F=D.plus(E);
console.log(F);

The benefit is not huge here, but you can see how it would help if there were many methods, all creating new objects.

In practice it's not usual to call object.create directly with the prototype object, but rather to use new keyword, along with the prototype property of a constructor.

function Time(hours, mins){
    this.hours=hours;
    this.mins=mins;
}

Time.prototype.plus=function (other) {
    var raw=timePlus(this,other);
    return ______________________________;
}

G = new Time(20,59);
H = new Time(11,11);

I=G.plus(H);
console.log(I);

Finally, ES2015 provides the class keyword to concisely generate constructors and prototypes.

class Time2 {
    constructor(hours, mins){
        this.hours=hours;
        this.mins=mins;
    };
    plus(other) {
        var raw=timePlus(this,other);
        ______________________________________;
    }
}

Time2;

J= new Time2(5,30);
K= new Time2(11,55);

L=J.plus(K); 

It's important to keep in mind that this is just convenience syntax for the same prototype based system.

Memoization

Time
25 minutes
Activity
Small Groups

For small data sets, a for loop is fast enough, but for larger data sets, it pays to be a bit smarter. In order to be able to see the difference, here is a larger data file. It contains all the data from before, padded with many copies with slightly changed names.

    var read_json_file=require("./read_json_file.js").read_json_file;

    var data=read_json_file("ancestry.json");

    var names = [];

    for (var i=0; i<data.length; i++){
        names.push(data[i].name);
    }

    exports.names=names;
    function shuffle (array) {
        var dest=array.length;

        for (var dest=array.length-1; dest>0; dest--) {

            var source = Math.floor(Math.random() * dest);
            var tmp = array[dest];
            array[dest] = array[source];
            array[source]=tmp;
        }
    }

    exports.shuffle=shuffle;
    var by_name=require("./ancestry.js").by_name;
    var names=require("./names.js").names;
    var shuffle=require("./shuffle.js").shuffle;

    var reps = 3;

    for (var i=0; i< reps; i++){
        shuffle (names);
        for (var j=0; j<names.length; j++) {
            var test_name=i+","+j;
            console.time(test_name);
            var dummy=by_name(names[i]);
            console.timeEnd(test_name);
        }
    }
    var read_json_file=require("./read_json_file.js").read_json_file;

    var by_name = (function () {
        var cache = {};
        var data = null;
        var real_by_name= function(name){
            if (data===null)
                data=read_json_file("big.json");
            if (cache[name] != undefined)
                return cache[name];
            for (var i=0; i<data.length; i++){






            }
            return null;
        };
        return real_by_name;
    })();

    exports.by_name=by_name;