UNB/ CS/ David Bremner/ teaching/ cs2613/ labs/ 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) {
        let 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

let 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 () {
            let data = [[1],2,[3],4,[5,6]];
            let orig_data = data;
            expect(flatten(data)).toEqual([1,2,3,4,5,6]);
            expect(data).toEqual(orig_data);
        });
        xit("deeper nesting",
        function () {
            let data = [[[1],2,[3]],4,[5,6]];
            let 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.

let fs = require('fs');

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

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

The use of a module local variable here to cache data is roughly equivalent to a class variable in Java. It's not particularly flexible, and real code would likely use an object to cache data for a given file.

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

let data = null;

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

    return null;

}
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) {
    let mins = (time1.mins + time2.mins) % 60;
    let 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){
    let plus=function (other) {
        let raw=timePlus(this,other);
        return ______________________________
    };

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

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

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

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

function timeNew(hours, mins) {
    let 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) {
    let 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) {
        let 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.

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

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

    let names = [];

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

    exports.names=names;

    function shuffle (array) {
        let dest=array.length;

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

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

    exports.shuffle=shuffle;

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

    let reps = 3;

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

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

let cache = {};
let data = null;

function by_name(name){
    if (data===null)
        data=read_json_file("big.json");
    if (cache[name] != undefined)
        return cache[name];
    // loop goes here
    

    return null;
};

exports.by_name=by_name;