How to implement a map or sorted-set in javascript

Question

Javascript has arrays which use numeric indexes ["john", "Bob", "Joe"] and objects which can be used like associative arrays or "maps" that allow string keys for the object values {"john" : 28, "bob": 34, "joe" : 4}.

In PHP it is easy to both A) sort by values (while maintaining the key) and B) test for the existence of a value in an associative array.

$array = ["john" => 28, "bob" => 34, "joe" => 4];

asort($array); // ["joe" => 4, "john" => 28, "bob" => 34];

if(isset($array["will"])) { }

How would you acheive this functionality in Javascript?

This is a common need for things like weighted lists or sorted sets where you need to keep a single copy of a value in data structure (like a tag name) and also keep a weighted value.

This is the best I've come up with so far:

function getSortedKeys(obj) {
    var keys = Object.keys(obj);
    keys = keys.sort(function(a,b){return obj[a]-obj[b]});

    var map = {};
    for (var i = keys.length - 1; i >= 0; i--) {
      map[keys[i]] = obj[keys[i]];
    };

    return map;
}

var list = {"john" : 28, "bob": 34, "joe" : 4};
list = getSortedKeys(list);
if(list["will"]) { }

Answer 1

Looking at this answer by Luke Schafer I think I might have found a better way to handle this by extending the Object.prototype:

// Sort by value while keeping index
Object.prototype.iterateSorted = function(worker, limit)
{
    var keys = Object.keys(this), self = this;
    keys.sort(function(a,b){return self[b] - self[a]});

    if(limit) {
        limit = Math.min(keys.length, limit);
    }

    limit = limit || keys.length;
    for (var i = 0; i < limit; i++) {
        worker(keys[i], this[keys[i]]);
    }
};

var myObj = { e:5, c:3, a:1, b:2, d:4, z:1};

myObj.iterateSorted(function(key, value) {
    console.log("key", key, "value", value)
}, 3);

http://jsfiddle.net/Xeoncross/kq3gbwgh/

Answer 2

I'm not sure why none of these answers mentions the existence of a built-in JS class, Set. Seems to be an ES6 addition, perhaps that's why.

Ideally override either add or keys below... NB overriding keys doesn't even need access to the Set object's prototype. Of course you could override these methods for the entire Set class. Or make a subclass, SortedSet.

  const mySet = new Set();

  const mySetProto = Object.getPrototypeOf(mySet);
  const addOverride = function(newObj){
    const arr = Array.from(this);
    arr.add(newObj);
    arr.sort(); // or arr.sort(function(a, b)...)
    this.clear();
    for(let item of arr){
      mySetProto.add.call(this, item);
    }
  }
  mySet.add = addOverride;
    
  const keysOverride = function(){
    const arr = Array.from(this);
    arr.sort(); // or arr.sort(function(a, b)...)
    return arr[Symbol.iterator]();
  }
  mySet.keys = keysOverride;

Usage:

mySet.add(3); mySet.add(2); mySet.add(1); mySet.add(2);
for(let item of mySet.keys()){console.log(item)};

Prints out:

1 ... 2 ... 3

NB Set.keys() returns not the items in the Set, but an iterator. You could choose to return the sorted array instead, but you'd obviously be breaking the class's "contract".

Which one to override? Depends on your usage and the size of your Set. If you override both you will be duplicating the sort activity, but in most cases it probably won't matter.

NB The add function I suggest is of course naive, a "first draft": rebuilding the entire set each time you add could be pretty costly. There are clearly much cleverer ways of doing this based on examining the existing elements in the Set and using a compare function, a binary tree structure*, or some other method to determine where in it to add the candidate for adding (I say "candidate" because it would be rejected if an "identical" element, namely itself, were already found to be present).

The question also asks about similar arrangements for a sorted map... in fact it turns out that ES6 has a new Map class which lends itself to similar treatment ... and also that Set is just a specialised Map, as you might expect.

* e.g. https://github.com/Crizstian/data-structure-and-algorithms-with-ES6/tree/master/10-chapter-Binary-Tree