Mimicking Sets in JavaScript

Mimicking sets in JavaScript?

If you are programming in an ES6-capable environment (such as node.js, a specific browser with the ES6 capabilities you need or transpiling ES6 code for your environment), then you can use the Set object built into ES6. It has very nice capabilities and can be used as is right in your environment.

For many simple things in an ES5 environment, using an Object works very well. If obj is your object and A is a variable that has the value you want to operate on in the set, then you can do these:

Initialization code:

// create empty object
var obj = {};

// or create an object with some items already in it
var obj = {"1":true, "2":true, "3":true, "9":true};

Question 1: Is A in the list:

if (A in obj) {
    // put code here
}

Question 2: Delete 'A' from the list if it's there:

delete obj[A];

Question 3: Add 'A' to the list if it wasn't already there

obj[A] = true;

For completeness, the test for whether A is in the list is a little safer with this:

if (Object.prototype.hasOwnProperty.call(obj, A))
    // put code here
}

because of potential conflict between built-in methods and/or properties on the base Object like the constructor property.

Sidebar on ES6: The current working version of ECMAScript 6 or somethings called ES 2015 has a built-in Set object. It is implemented now in some browsers. Since browser availability changes over time, you can look at the line for Set in this ES6 compatibility table to see the current status for browser availability.

One advantage of the built-in Set object is that it doesn't coerce all keys to a string like the Object does so you can have both 5 and "5" as separate keys. And, you can even use Objects directly in the set without a string conversion. Here's an article that describes some of the capabilities and MDN's documentation on the Set object.

I have now written a polyfill for the ES6 set object so you could start using that now and it will automatically defer to the built-in set object if the browser supports it. This has the advantage that you're writing ES6 compatible code that will work all the way back to IE7. But, there are some downsides. The ES6 set interface takes advantage of the ES6 iterators so you can do things like for (item of mySet) and it will automatically iterate through the set for you. But, this type of language feature cannot be implemented via polyfill. You can still iterate an ES6 set without using the new ES6 languages features, but frankly without the new language features, it isn't as convenient as the other set interface I include below.

You can decide which one works best for you after looking at both. The ES6 set polyfill is here: https://github.com/jfriend00/ES6-Set.

FYI, in my own testing, I've noticed that the Firefox v29 Set implementation is not fully up-to-date on the current draft of the spec. For example, you can't chain .add() method calls like the spec describes and my polyfill supports. This is probably a matter of a specification in motion as it is not yet finalized.

Pre-Built Set objects: If you want an already built object that has methods for operating on a set that you can use in any browser, you can use a series of different pre-built objects that implement different types of sets. There is a miniSet which is small code that implements the basics of a set object. It also has a more feature rich set object and several derivations including a Dictionary (let's you store/retrieve a value for each key) and an ObjectSet (let's you keep a set of objects - either JS objects or DOM objects where you either supply the function that generates a unique key for each one or the ObjectSet will generate the key for you).

Here's a copy of the code for the miniSet (most up-to-date code is here on github).

"use strict";
//-------------------------------------------
// Simple implementation of a Set in javascript
//
// Supports any element type that can uniquely be identified
//    with its string conversion (e.g. toString() operator).
// This includes strings, numbers, dates, etc...
// It does not include objects or arrays though
//    one could implement a toString() operator
//    on an object that would uniquely identify
//    the object.
// 
// Uses a javascript object to hold the Set
//
// This is a subset of the Set object designed to be smaller and faster, but
// not as extensible.  This implementation should not be mixed with the Set object
// as in don't pass a miniSet to a Set constructor or vice versa.  Both can exist and be
// used separately in the same project, though if you want the features of the other
// sets, then you should probably just include them and not include miniSet as it's
// really designed for someone who just wants the smallest amount of code to get
// a Set interface.
//
// s.add(key)                      // adds a key to the Set (if it doesn't already exist)
// s.add(key1, key2, key3)         // adds multiple keys
// s.add([key1, key2, key3])       // adds multiple keys
// s.add(otherSet)                 // adds another Set to this Set
// s.add(arrayLikeObject)          // adds anything that a subclass returns true on _isPseudoArray()
// s.remove(key)                   // removes a key from the Set
// s.remove(["a", "b"]);           // removes all keys in the passed in array
// s.remove("a", "b", ["first", "second"]);   // removes all keys specified
// s.has(key)                      // returns true/false if key exists in the Set
// s.isEmpty()                     // returns true/false for whether Set is empty
// s.keys()                        // returns an array of keys in the Set
// s.clear()                       // clears all data from the Set
// s.each(fn)                      // iterate over all items in the Set (return this for method chaining)
//
// All methods return the object for use in chaining except when the point
// of the method is to return a specific value (such as .keys() or .isEmpty())
//-------------------------------------------

// polyfill for Array.isArray
if(!Array.isArray) {
    Array.isArray = function (vArg) {
        return Object.prototype.toString.call(vArg) === "[object Array]";
    };
}

function MiniSet(initialData) {
    // Usage:
    // new MiniSet()
    // new MiniSet(1,2,3,4,5)
    // new MiniSet(["1", "2", "3", "4", "5"])
    // new MiniSet(otherSet)
    // new MiniSet(otherSet1, otherSet2, ...)
    this.data = {};
    this.add.apply(this, arguments);
}

MiniSet.prototype = {
    // usage:
    // add(key)
    // add([key1, key2, key3])
    // add(otherSet)
    // add(key1, [key2, key3, key4], otherSet)
    // add supports the EXACT same arguments as the constructor
    add: function() {
        var key;
        for (var i = 0; i < arguments.length; i++) {
            key = arguments[i];
            if (Array.isArray(key)) {
                for (var j = 0; j < key.length; j++) {
                    this.data[key[j]] = key[j];
                }
            } else if (key instanceof MiniSet) {
                var self = this;
                key.each(function(val, key) {
                    self.data[key] = val;
                });
            } else {
                // just a key, so add it
                this.data[key] = key;
            }
        }
        return this;
    },
    // private: to remove a single item
    // does not have all the argument flexibility that remove does
    _removeItem: function(key) {
        delete this.data[key];
    },
    // usage:
    // remove(key)
    // remove(key1, key2, key3)
    // remove([key1, key2, key3])
    remove: function(key) {
        // can be one or more args
        // each arg can be a string key or an array of string keys
        var item;
        for (var j = 0; j < arguments.length; j++) {
            item = arguments[j];
            if (Array.isArray(item)) {
                // must be an array of keys
                for (var i = 0; i < item.length; i++) {
                    this._removeItem(item[i]);
                }
            } else {
                this._removeItem(item);
            }
        }
        return this;
    },
    // returns true/false on whether the key exists
    has: function(key) {
        return Object.prototype.hasOwnProperty.call(this.data, key);
    },
    // tells you if the Set is empty or not
    isEmpty: function() {
        for (var key in this.data) {
            if (this.has(key)) {
                return false;
            }
        }
        return true;
    },
    // returns an array of all keys in the Set
    // returns the original key (not the string converted form)
    keys: function() {
        var results = [];
        this.each(function(data) {
            results.push(data);
        });
        return results;
    },
    // clears the Set
    clear: function() {
        this.data = {}; 
        return this;
    },
    // iterate over all elements in the Set until callback returns false
    // myCallback(key) is the callback form
    // If the callback returns false, then the iteration is stopped
    // returns the Set to allow method chaining
    each: function(fn) {
        this.eachReturn(fn);
        return this;
    },
    // iterate all elements until callback returns false
    // myCallback(key) is the callback form
    // returns false if iteration was stopped
    // returns true if iteration completed
    eachReturn: function(fn) {
        for (var key in this.data) {
            if (this.has(key)) {
                if (fn.call(this, this.data[key], key) === false) {
                    return false;
                }
            }
        }
        return true;
    }
};

MiniSet.prototype.constructor = MiniSet;

Shallow-clone a Map or Set

Use the constructor to clone Maps and Sets:

var clonedMap = new Map(originalMap);

var clonedSet = new Set(originalSet);

An efficient Javascript set structure

For fixed large array of string I suggest to use some form of radix search
Also, take a look at different data structures and algorithms (AVL trees, queues/heaps etc) in this package

I'm pretty sure that using JS object as storage for strings will result in 'hash mode' for that object. Depending on implementation this could be O(log n) to O(1) time. Look at some jsperf benchmarks to compare property lookup vs binary search on sorted array.

In practice, especially if I'm not going to use the code in browser I would offload this functionality to something like redis or memcached.

Does JavaScript have an implementation of a set data structure?

You could build a simple wrapper around the keys of a hash table provided by my jshashtable. I have one knocking around somewhere that I will dig out later.

UPDATE

I have completed and tested an implementation of HashSet and uploaded it to the jshashtable project on GitHub. You can download it or view the source.

var s = new HashSet();
var o1 = {name: "One"}, o2 = {name: "Two"};
s.add(o1);
s.add(o2);
s.values(); // Array containing o1 and o2

Mimic the structure of a javascript array object

Found it.
Thanks @Paul S
It seems Jscript will allow the call of the splice function on an object. I tried that before like this:

var obj = new Object();
obj[0] = "item1";
obj[1] = "item2";
obj[2] = "item3";
obj.trunc = [].splice;
obj.trunc(1,1);
console.log(obj);
//outputs
//Object {0: "item1", 1: "item2", 2: "item3", trunc: function}

but I did not add the length property, so adding to the code above:

var countNum = 0;
for (var item in obj)
    !isNaN(parseFloat(item)? countNum++ : "";
obj.length = countNum;//number of num-indexed properties 
obj.trunc(1,1);
console.log(obj);
//outputs
//Object {0: "item1", 1: "item3", trunc: function}

so as long as the structure is number-index and has a length property the splice function will work on it.

Therefore the data structure of an array in javascript is reliant on the properties :

number index
length

How to mimic extends and super in prototypes?

You can make sure, that EmployeeF inherits it's prototype from PersonF by using Object.create with PersonFs Prototype:

EmployeeF.prototype = Object.create(PersonF.prototype)

let PersonF = function(name, id){
    this.name = name;
    this.id = id;
}

PersonF.prototype.getDetails = function(){ 
    console.log(`Printing details in parent in function way :${this.name} : ${this.id}`, this); // added log of `this`
}

let pers = new PersonF('Person', 111);

let EmployeeF = function(name, id, salary){
    PersonF.call(this, name, id); 
    this.salary = salary;
}

EmployeeF.prototype = Object.create(PersonF.prototype) // create Employees Prototype from Persons

EmployeeF.prototype.printDetails = function(){
    console.log(`${this.name} : ${this.id} : ${this.salary}`);
}

const emp = new EmployeeF('John', 1 , 10000000)

emp.getDetails();

What are the differences between javascript's Set and a regular plain object?

First off, here's a post with code that shows how to start to use a plain Javascript object for set-like behavior (with some limitations).

And, here's a set of objects (that work in ES5) for getting lots more set-like behavior.

And, here a partial ES6 polyfill for the Set object implemented in ES5.

If you study any of this code, you will see that a plain Javascript object falls far short of an ES6 Set in many ways that require significant additional coding to work around.

Here are a couple of those issues:

Assigning an object as a key will not work properly because all objects convert to a string key of "[object Object]" so all objects would have the same key in your set-like Javascript object.
Assigning a number as a key will convert to the string representation so keys like 4 and "4" will conflict.

The ES6 Set object does not have these limitations. Here's more discussion of these two issues:

If you look at this answer to a prior post and the code in that answer, you can see how an underlying Javascript object can be used as the lookup mechanism for set-like behavior. Without lots of other coding though, it has some limitations because a Javascript object requires a string as the lookup key. An ES6 Set does not. So, out of the box the ES6 Set supports objects as elements. Using a Javascript object as a poor man's set does not support objects as elements in the set.

This becomes the most material when you want to add an object to the plain Javascript object-based set.

// create a set-like object
var mySet = {};

// create an object and put it in the set
var myObj = {greeting: "hello"};
mySet[myObj] = true;

Because a Javascript object requires a string key, it will call myObj.toString() to get such a key. Without a custom override for the toString() method, that will come out as "[object Object]" which is not at all what you want. See here for a demo. It will appear to work for one object, but as soon as you have more than one object in the set or set the set for a different object, it won't work at all because all objects would get indexed with the same key.

With an actual ES6 set, on the other hand, it natively accepts and works with objects just fine - you don't have to do anything special.

If you want to see how you can mimic an ES6 set as closely as possible using a plain Javascript object as the lookup mechanism, please read this answer. Further info is located on github where you can see what as to be done to make a regular Javascript object-based set implementation support Javascript objects with this ObjectSet implementation. There's even an ES6 Set polyfill here that uses an underlying Javacript object as it's storage mechanism.

A second issue arises with Javascript object based set implementations which is also because of the string key requirement. If you do this:

var mySet = {};
mySet[4] = true;
mySet["4"] = true;

You will end up with only one item in the set. This is because mySet[4] = true; converts the 4 to a string "4" to use as the key. If you are only using strings in your set or only using numbers in the set, then this can be easily worked around, but if you have both strings and numbers in the set, then a javascript object-base set implementation does not distinguish between 4 and "4" so does not treat them as separate items in the set. An ES6 does make this distinction.

Again, it would be possible to work around this with more code. If you manually do the toString() conversion yourself to create the key, one can preprend to the key value some type information such that in the above example, the key for the number 4 becomes "num_4" instead of just "4". To prevent collisions with a string '"num_4"`, you have to also do the same for string types. And numbers aren't the only type with this issue. In fact, in this ES6 Set polyfill, you can see a unique key being generated here. That unique key then has to be regenerated and used to do any lookup in the set.

Set of objects in javascript

ES6 provides a native Set:

let s = new Set();let a = {};let b = {};
s.add(a);
console.log(s.has(a));  // trueconsole.log(s.has(b));  // false

Mimicking Sets in JavaScript