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

Answer 3

With ES6 you could choose to extend the Map constructor/class with a sort method that takes an optional compare function (just like arrays have). That sort method would take two arguments, each of which are key/value pairs so that the sorting can happen on either the keys or the values (or both).

The sort method will rely on the documented behaviour of Maps that entries are iterated in insertion order. So this new method will visit the entries according to the sorted order, and then delete and immediately re-insert them.

Here is how that could look:

class SortableMap extends Map {
    sort(cmp = (a, b) => a[0].localeCompare(b[0])) {
        for (const [key, value] of [...this.entries()].sort(cmp)) {
            this.delete(key);
            this.set(key, value); // New keys are added at the end of the order
        }
    }
}
// Demo
const mp = new SortableMap([[3, "three"],[1, "one"],[2, "two"]]);
console.log("Before: ", JSON.stringify([...mp])); // Before
mp.sort( (a, b) => a[0] - b[0] ); // Custom compare function: sort numerical keys
console.log(" After: ", JSON.stringify([...mp])); // After

Answer 4

You usually don't sort an object. But if you do: Sorting JavaScript Object by property value

If you want to sort an array, let's say the following

var arraylist = [{"john" : 28},{ "bob": 34},{ "joe" : 4}];

You can always use Array.prototype.sort function. Source: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort

Answer 5

Maybe this code look like what you want:

Object.prototype.asort = function(){
    var retVal = {};
    var self = this;
    var keys = Object.keys(this);
    keys = keys.sort(function(a,b){return self[a] - self[b]});
    for (var i = 0; i < keys.length; i++) {
        retVal[keys[i]] = this[keys[i]];
    }
    return retVal;
}
var map = {"john" : 28, "bob": 34, "joe" : 4}
var sortedMap = map.asort();//sortedMap["will"]: undefined

Answer 6

If you use the open source project jinqJs its easy.

See Fiddler

var result = jinqJs()
                .from([{"john" : 28},{ "bob": 34},{ "joe" : 4}])
                .orderBy([{field: 0}])
                .select();

Answer 7

Here's an implementation of OrderedMap. Use the functions get() and set() to extract or push key value pairs to the OrderedMap. It is internally using an array to maintain the order.

class OrderedMap {
  constructor() {
    this.arr = [];
    return this;
  }
  get(key) {
    for(let i=0;i<this.arr.length;i++) {
      if(this.arr[i].key === key) {
        return this.arr[i].value;
      }
    }
    return undefined;
  }

  set(key, value) {
    for(let i=0;i<this.arr.length;i++) {
      if(this.arr[i].key === key) {
        this.arr[i].value = value;
        return;
      }
    }
    this.arr.push({key, value})
  }

  values() {
    return this.arr;
  }
}

let m = new OrderedMap();
m.set('b', 60)
m.set('a', 10)
m.set('c', 20)
m.set('d', 89)

console.log(m.get('a'));

console.log(m.values());

Answer 8

https://github.com/js-sdsl/js-sdsl

The OrderedMap in Js-sdsl maybe helpful.

This is a sorted-map which implement refer to C++ STL Map.

/*
 * key value
 * 1   1
 * 2   2
 * 3   3
 * Sorted by key.
 */
const mp = new OrderedMap(
    [1, 2, 3].map((element, index) => [index, element])
);
mp.setElement(1, 2);        // O(logn)
mp.eraseElementByKey(1)     // O(logn)

// custom comparison function
mp = new OrderedMap(
    [1, 2, 3].map((element, index) => [index, element]),
    (x, y) => x - y
);

// enable tree iterator index (enableIndex = true)
console.log(new OrderedMap([[0, 1], [1, 1]], undefined, true).begin(),next().index);   // 1