Wednesday 8 April 2020

JavaScript Sets for Objects

While I was working on the chapter in my recent book that described a "First Person Shooter" type game project using ray casting I experimented with a JavaScript collection object very similar to a standard JavaScript Set but for objects.

The excellent Mozilla documentation page describes a JavaScript set thus: "The Set object lets you store unique values of any type, whether primitive values or object references."

The snag is that all JavaScript objects are unique even if the contain identical members with identical values. This can be illustrated with the following code:

var mSet = new Set(); var objA = {x: 1, y: 2}; var objB = objA; mSet.add(objA); mSet.add(objB); console.log("Set size: " + mSet.size); //=> 1 objB = {x: 1, y: 2}; mSet.add(objB); console.log("Set size: " + mSet.size); //=> 2









After creating a set instance, the code creates an object which is referenced by the two variables objA and objB. When the variable values are added to the set the result is only a single entry as  objB points to the same object as objA. When we assign the variable objB to a new object which to all intents and purposes is the same as the one referenced by objA we can add it to the set as it is deemed unique.

My first stab at creating a new collection object included using a comparison function to identify objects that should be deemed equal for the purposes of the current collection. I decided to use a similarly constructed comparison function to one that might otherwise be used to sort an array. It can be simplified as a return value of 0 (zero) indicates a match and a non-zero value indicates that the two objects do not match. This saved having to write a dedicated comparison function if one already existed for a given type of object. Based on that idea, the collection object is defined.

var UniqueList = function(compare){ this.list = []; this.compare = compare; }; UniqueList.prototype.add = function(obj){ if(!this.has(obj)){ this.list.push(obj); } return this; }; UniqueList.prototype.delete = function(obj){ for(let i = 0; i < this.list.length; i++){ if(!this.compare(this.list[i], obj)){ this.list.splice(i, 1); // removes the element return true; } } return false; }; UniqueList.prototype.has = function(obj) { for(let i = 0; i < this.list.length; i++){ if(!this.compare(this.list[i], obj)){ return true; } } return false; }; UniqueList.prototype.forEach = function(callBack){ for(let i = 0; i < this.list.length; i++){ callBack(this.list[i]); } }; UniqueList.prototype.size = function() { return this.list.length; }; UniqueList.prototype.clear = function(){ this.list = []; };































Which was tested with code like the following:

function compareCells(a,b){ return (a.x === b.x && a.y === b.y) ? 0 : 1; } var uList = new UniqueList(compareCells); uList.add({x: 0, y: 0}); uList.add({x:72, y: 99}); uList.add({x:77, y: 90}); uList.add({x:78, y: 99}); uList.add({x:0, y: 0}); // not added to set console.log("Size: " + uList.size()); // => 4 uList.delete({x:78, y: 99}); console.log("Size: " + uList.size()); // => 3












The forEach() function was handy but I later thought it might be nice to be able to iterate over the stored values. The standard JavaScript Set object can supply a number of iterable objects (entries(), keys() and values()). A simple "kludge" involved adding a line to the constructor

var UniqueList = function(compare){ this.list = []; this.compare = compare; this.entries = this.list; };




So that I could then write something like:

for(let cell of uList.entries){ console.log(cell.x); }





That worked because the array referenced by uList.entries is itself iterable. I then though it would be much nicer to make the object iterable in its own right. One solution is to rework the collection object as a class and override the default iterator.

class ObjectSet { constructor(compare){ this.compare = compare; this._list = []; this.size = 0; } has(obj) { for(let i = 0; i < this._list.length; i++){ if(!this.compare(this._list[i], obj)){ return true; } } return false; } add(obj) { if(!this.has(obj)){ this._list.push(obj); this.size++; } return this; } clear() { this._list = []; this.size = 0; } delete(obj) { for(let i = 0; i < this._list.length; i++){ if(!this.compare(this._list[i], obj)){ this._list.splice(i, 1); this.size--; return true; } } return false; } forEach(callBack) { for(let i = 0; i < this._list.length; i++){ callBack(this._list[i]); } } [Symbol.iterator]() { let _idx = 0; return { next: () => { if(_idx < this._list.length){ return{value: this._list[_idx++], done: false}; } else { return {done: true}; } } }; } }










































That class object was tested with some code similar to the following;

var oSet = new ObjectSet(compareCells); oSet.add({x: 0, y: 0}); oSet.add({x:77, y: 99}); oSet.add({x:72, y: 90}); oSet.add({x:78, y: 99}); oSet.add({x:0, y: 0}); console.log("Size: " + oSet.size); oSet.delete({x:78, y: 99}); console.log("Size: " + oSet.size); for(let cell of oSet){ console.log(cell.x); } oSet.forEach(function(obj) {console.log(obj.y);});












This demonstrated nicely that my ObjectSet class could be iterated and that it implemented the same functionality as the original concept object.


No comments:

Post a Comment