Map/Set implementations for js?

Collections.ts

interface NumberConstructor {
  isNaN(x: any): boolean
}

namespace Collections {
  

  type Dictionary<T> = {
    [k: string]: T
  }

  type NilEntry<K, V> = {
    nextEntry: NilEntry<K, V>;
    prevEntry: NilEntry<K, V>;
  }
  type Entry<K, V> = NilEntry<K, V> & {
    key: K;
    value: V;
  }

  type Maybe<T> = { value: T } | undefined;

  function defined<T>(x: T | undefined): x is T {
    return typeof x !== 'undefined';
  }

  type StringHashFunction<T> = (t: T) => string;

  const uniqueIdKey = Symbol('Unique Identifier');
  
  const getIdOfObject = (() => {
    var id = 0;
    return function(o: any): string {
      try {
        if (defined(o[uniqueIdKey])) return o[uniqueIdKey];
        const value = "Object#" + id;
        id++;
        Object.defineProperty(o, uniqueIdKey, {
          value: value,
          enumerable: false,
          writable: false
        });
        if (defined(o[uniqueIdKey])) return value;
      } catch (ex) {

      }
      return Object.keys(o).join();
    }
  })();

  function defaultStringHash<T>(t: T): string {
    if (typeof t !== 'object') {
      return t + "";
    }
    return getIdOfObject(t);
  }

  type EqualityFunction<T> = (t1: T, t2: T) => boolean;
  function defaultEqualityFunction<T>(t1: T, t2: T): boolean {
    return Number.isNaN(t1) ? Number.isNaN(t2) : t1 === t2;
  }

  class GenericLinkedHashMap<K, V, I> {

    private _innerMap: Dictionary<Entry<K, V>[]>;
    private _nil: NilEntry<K, V>;

    public size: number;
    constructor(
      private entryIteratorFunction: (e: Entry<K, V>) => I,
      private keyHashFunction: StringHashFunction<K> = defaultStringHash,
      private keyEqualityFunction: EqualityFunction<K> = defaultEqualityFunction
    ) {
      this.clear();
    }

    private _doMap(k: K, modify?: boolean, v?: Maybe<V>): Maybe<V> {
      const hashKey = this.keyHashFunction(k);
      if (!this._innerMap.hasOwnProperty(hashKey)) {
        if (!modify || !defined(v)) return;
        this._innerMap[hashKey] = [];
      }
      const hashEntries = this._innerMap[hashKey];
      var foundIndex = hashEntries.findIndex(entry => this.keyEqualityFunction(entry.key, k));
      if (foundIndex < 0) {
        if (modify && defined(v)) {
          // add new entry to the end of the list
          const lastEntry = this._nil.prevEntry;
          const newEntry = { key: k, value: v.value, nextEntry: this._nil, prevEntry: lastEntry };
          this._nil.prevEntry = newEntry;
          lastEntry.nextEntry = newEntry;
          hashEntries.push(newEntry);
          this.size++;
        }
        return;
      }
      var foundEntry = hashEntries[foundIndex];
      if (modify) {
        if (defined(v)) {
          foundEntry.value = v.value;
        } else {
          // remove an entry from the list
          const removedEntry = hashEntries.splice(foundIndex, 1)[0];
          removedEntry.prevEntry.nextEntry = removedEntry.nextEntry;
          removedEntry.nextEntry.prevEntry = removedEntry.prevEntry;
          this.size--;
        }
      }
      return { value: foundEntry.value };
    }

    private _iterEntryMap<T>(f: (e: Entry<K, V>) => T): IterableIterator<T> {
      const nil = this._nil;
      const isEntry = function isEntry<K, V>(e: NilEntry<K, V>): e is Entry<K, V> {
        return e !== nil;
      }
      const _innerMap = this._innerMap;
      var curEntry = nil.nextEntry;
      var iter = {
        [Symbol.iterator](): IterableIterator<T> {
          return iter;
        },
        next(): IteratorResult<T> {
          if (isEntry(curEntry)) {
            const entry = curEntry;
            curEntry = curEntry.nextEntry;
            return { done: false, value: f(entry) };
          }
          return { done: true } as IteratorResult<any>;
        }
      }
      return iter;
    }

    clear(): void {
      this._innerMap = {};
      this.size = 0;
      var nil = {} as NilEntry<K,V>;
      nil.nextEntry = nil;
      nil.prevEntry = nil;
      this._nil = nil;
    }
    delete(key: K): boolean {
      return defined(this._doMap(key, true));
    }
    forEach(callbackfn: (value: V, key: K, map: this) => void, thisArg?: any): void {
      for (var entry of Array.from(this._iterEntryMap(e => e))) {
        callbackfn.call(thisArg, entry.value, entry.key, this);
      }
    }
    get(key: K): V | undefined {
      var ret = this._doMap(key);
      return defined(ret) ? ret.value : ret;
    }
    has(key: K): boolean {
      return defined(this._doMap(key));
    }
    set(key: K, value: V): this {
      this._doMap(key, true, { value: value });
      return this;
    }
    [Symbol.iterator](): IterableIterator<I> {
      return this._iterEntryMap<I>(this.entryIteratorFunction);
    }
    entries(): IterableIterator<[K, V]> {
      return this._iterEntryMap<[K, V]>(e => [e.key, e.value]);
    }
    keys(): IterableIterator<K> {
      return this._iterEntryMap(e => e.key);
    }
    values(): IterableIterator<V> {
      return this._iterEntryMap(e => e.value);
    }

  }

  export class HashMap<K, V> extends GenericLinkedHashMap<K, V, [K, V]> implements Map<K, V> {
    constructor(
      keyHashFunction?: StringHashFunction<K>, keyEqualityFunction?: EqualityFunction<K>) {
      super(e => [e.key, e.value], keyHashFunction, keyEqualityFunction);
    }
    [Symbol.toStringTag]: "Map" = "Map";
    static get [Symbol.species]() { return HashMap; }
  }

  export class HashSet<T> extends GenericLinkedHashMap<T, T, T> implements Set<T> {
    constructor(
      hashFunction?: StringHashFunction<T>, equalityFunction?: EqualityFunction<T>) {
      super(e => e.key, hashFunction, equalityFunction);
    }
    add(value: T): this {
      return this.set(value, value);
    }
    [Symbol.toStringTag]: "Set" = "Set";
    static get [Symbol.species]() { return HashSet; }
  }

  // Collection tests?

  export function randomString(len?: number): string {
    if (!len) len = 10;
    var r = [];
    var chars = 'abcdefghijklmnopqrstuvwxyz'.split('');
    var numchars = chars.length;
    for (var i = 0; i < len; i++) { r.push(chars[Math.floor(Math.random() * numchars)]); }
    return r.join('')
  }

  export function randomObject(len?: number): Dictionary<any> {
    if (!len) len = 10;
    var ret: Dictionary<any> = {};
    for (var i = 0; i < len; i++) {
      ret[randomString()] = randomString();
    }
    return ret;
  }

  export function mapTest<K, V>(map: Map<K, V>, keyGenerator: () => K, valueGenerator: () => V, iterations: number = 100) {
    map.clear();
    if (map.size !== 0) throw new Error("Supposedly empty map has size " + map.size);
    for (var i = 0; i < iterations; i++) {
      var k = keyGenerator();
      if (map.has(k)) throw new Error("Supposedly empty map has key " + k);
    }
    var distinctKeys: K[] = [];
    var expectedSize = 0;
    for (var i = 0; i < iterations; i++) {
      var k = keyGenerator();
      var v = valueGenerator();
      var already = distinctKeys.findIndex(kk => kk === k);
      map.set(k, v);
      if ((already < 0) && defined(v)) {
        distinctKeys.push(k);
        expectedSize++;
      } else if ((already >= 0) && !defined(v)) {
        distinctKeys.splice(already, 1);
        expectedSize--;
      }
      const vGet = map.get(k);
      const sizeGet = map.size;
      if (map.has(k) !== defined(v)) throw new Error("Map has " + (defined(v) ? "a" : "no") + " value for key " + k + " when it should have " + (defined(v) ? "no" : "a") + " value");
      if (vGet !== v) throw new Error("Set value for key " + k + " to " + v + ", but got " + vGet + " back instead");
      if (sizeGet !== expectedSize) throw new Error("Expected map size to be " + expectedSize + " but got got " + sizeGet + " insetead");
    }
    distinctKeys.forEach(k => {
      map.delete(k);
      expectedSize--;
      if (map.has(k)) throw new Error("Map has a value for key " + k + " after it was deleted");
      const sizeGet = map.size;
      if (sizeGet !== expectedSize) throw new Error("Expected map size to be " + expectedSize + " but got got " + sizeGet + " insetead");
    })


  }

}

Collections.js

var __extends = (this && this.__extends) || (function () {
    var extendStatics = Object.setPrototypeOf ||
        ({ __proto__: [] } instanceof Array && function (d, b) { d.__proto__ = b; }) ||
        function (d, b) { for (var p in b) if (b.hasOwnProperty(p)) d[p] = b[p]; };
    return function (d, b) {
        extendStatics(d, b);
        function __() { this.constructor = d; }
        d.prototype = b === null ? Object.create(b) : (__.prototype = b.prototype, new __());
    };
})();
var Collections;
(function (Collections) {
    function defined(x) {
        return typeof x !== 'undefined';
    }
    var uniqueIdKey = Symbol('Unique Identifier');
    var getIdOfObject = (function () {
        var id = 0;
        return function (o) {
            try {
                if (defined(o[uniqueIdKey]))
                    return o[uniqueIdKey];
                var value = "Object#" + id;
                id++;
                Object.defineProperty(o, uniqueIdKey, {
                    value: value,
                    enumerable: false,
                    writable: false
                });
                if (defined(o[uniqueIdKey]))
                    return value;
            }
            catch (ex) {
            }
            return Object.keys(o).join();
        };
    })();
    function defaultStringHash(t) {
        if (typeof t !== 'object') {
            return t + "";
        }
        return getIdOfObject(t);
    }
    function defaultEqualityFunction(t1, t2) {
        return Number.isNaN(t1) ? Number.isNaN(t2) : t1 === t2;
    }
    var GenericLinkedHashMap = (function () {
        function GenericLinkedHashMap(entryIteratorFunction, keyHashFunction, keyEqualityFunction) {
            if (keyHashFunction === void 0) { keyHashFunction = defaultStringHash; }
            if (keyEqualityFunction === void 0) { keyEqualityFunction = defaultEqualityFunction; }
            this.entryIteratorFunction = entryIteratorFunction;
            this.keyHashFunction = keyHashFunction;
            this.keyEqualityFunction = keyEqualityFunction;
            this.clear();
        }
        GenericLinkedHashMap.prototype._doMap = function (k, modify, v) {
            var _this = this;
            var hashKey = this.keyHashFunction(k);
            if (!this._innerMap.hasOwnProperty(hashKey)) {
                if (!modify || !defined(v))
                    return;
                this._innerMap[hashKey] = [];
            }
            var hashEntries = this._innerMap[hashKey];
            var foundIndex = hashEntries.findIndex(function (entry) { return _this.keyEqualityFunction(entry.key, k); });
            if (foundIndex < 0) {
                if (modify && defined(v)) {
                    // add new entry to the end of the list
                    var lastEntry = this._nil.prevEntry;
                    var newEntry = { key: k, value: v.value, nextEntry: this._nil, prevEntry: lastEntry };
                    this._nil.prevEntry = newEntry;
                    lastEntry.nextEntry = newEntry;
                    hashEntries.push(newEntry);
                    this.size++;
                }
                return;
            }
            var foundEntry = hashEntries[foundIndex];
            if (modify) {
                if (defined(v)) {
                    foundEntry.value = v.value;
                }
                else {
                    // remove an entry from the list
                    var removedEntry = hashEntries.splice(foundIndex, 1)[0];
                    removedEntry.prevEntry.nextEntry = removedEntry.nextEntry;
                    removedEntry.nextEntry.prevEntry = removedEntry.prevEntry;
                    this.size--;
                }
            }
            return { value: foundEntry.value };
        };
        GenericLinkedHashMap.prototype._iterEntryMap = function (f) {
            var nil = this._nil;
            var isEntry = function isEntry(e) {
                return e !== nil;
            };
            var _innerMap = this._innerMap;
            var curEntry = nil.nextEntry;
            var iter = (_a = {},
                _a[Symbol.iterator] = function () {
                    return iter;
                },
                _a.next = function () {
                    if (isEntry(curEntry)) {
                        var entry = curEntry;
                        curEntry = curEntry.nextEntry;
                        return { done: false, value: f(entry) };
                    }
                    return { done: true };
                },
                _a);
            return iter;
            var _a;
        };
        GenericLinkedHashMap.prototype.clear = function () {
            this._innerMap = {};
            this.size = 0;
            var nil = {};
            nil.nextEntry = nil;
            nil.prevEntry = nil;
            this._nil = nil;
        };
        GenericLinkedHashMap.prototype.delete = function (key) {
            return defined(this._doMap(key, true));
        };
        GenericLinkedHashMap.prototype.forEach = function (callbackfn, thisArg) {
            for (var _i = 0, _a = Array.from(this._iterEntryMap(function (e) { return e; })); _i < _a.length; _i++) {
                var entry = _a[_i];
                callbackfn.call(thisArg, entry.value, entry.key, this);
            }
        };
        GenericLinkedHashMap.prototype.get = function (key) {
            var ret = this._doMap(key);
            return defined(ret) ? ret.value : ret;
        };
        GenericLinkedHashMap.prototype.has = function (key) {
            return defined(this._doMap(key));
        };
        GenericLinkedHashMap.prototype.set = function (key, value) {
            this._doMap(key, true, { value: value });
            return this;
        };
        GenericLinkedHashMap.prototype[Symbol.iterator] = function () {
            return this._iterEntryMap(this.entryIteratorFunction);
        };
        GenericLinkedHashMap.prototype.entries = function () {
            return this._iterEntryMap(function (e) { return [e.key, e.value]; });
        };
        GenericLinkedHashMap.prototype.keys = function () {
            return this._iterEntryMap(function (e) { return e.key; });
        };
        GenericLinkedHashMap.prototype.values = function () {
            return this._iterEntryMap(function (e) { return e.value; });
        };
        return GenericLinkedHashMap;
    }());
    var HashMap = (function (_super) {
        __extends(HashMap, _super);
        function HashMap(keyHashFunction, keyEqualityFunction) {
            var _this = _super.call(this, function (e) { return [e.key, e.value]; }, keyHashFunction, keyEqualityFunction) || this;
            _this[Symbol.toStringTag] = "Map";
            return _this;
        }
        Object.defineProperty(HashMap, Symbol.species, {
            get: function () { return HashMap; },
            enumerable: true,
            configurable: true
        });
        return HashMap;
    }(GenericLinkedHashMap));
    Collections.HashMap = HashMap;
    var HashSet = (function (_super) {
        __extends(HashSet, _super);
        function HashSet(hashFunction, equalityFunction) {
            var _this = _super.call(this, function (e) { return e.key; }, hashFunction, equalityFunction) || this;
            _this[Symbol.toStringTag] = "Set";
            return _this;
        }
        HashSet.prototype.add = function (value) {
            return this.set(value, value);
        };
        Object.defineProperty(HashSet, Symbol.species, {
            get: function () { return HashSet; },
            enumerable: true,
            configurable: true
        });
        return HashSet;
    }(GenericLinkedHashMap));
    Collections.HashSet = HashSet;
    // Collection tests?
    function randomString(len) {
        if (!len)
            len = 10;
        var r = [];
        var chars = 'abcdefghijklmnopqrstuvwxyz'.split('');
        var numchars = chars.length;
        for (var i = 0; i < len; i++) {
            r.push(chars[Math.floor(Math.random() * numchars)]);
        }
        return r.join('');
    }
    Collections.randomString = randomString;
    function randomObject(len) {
        if (!len)
            len = 10;
        var ret = {};
        for (var i = 0; i < len; i++) {
            ret[randomString()] = randomString();
        }
        return ret;
    }
    Collections.randomObject = randomObject;
    function mapTest(map, keyGenerator, valueGenerator, iterations) {
        if (iterations === void 0) { iterations = 100; }
        map.clear();
        if (map.size !== 0)
            throw new Error("Supposedly empty map has size " + map.size);
        for (var i = 0; i < iterations; i++) {
            var k = keyGenerator();
            if (map.has(k))
                throw new Error("Supposedly empty map has key " + k);
        }
        var distinctKeys = [];
        var expectedSize = 0;
        for (var i = 0; i < iterations; i++) {
            var k = keyGenerator();
            var v = valueGenerator();
            var already = distinctKeys.findIndex(function (kk) { return kk === k; });
            map.set(k, v);
            if ((already < 0) && defined(v)) {
                distinctKeys.push(k);
                expectedSize++;
            }
            else if ((already >= 0) && !defined(v)) {
                distinctKeys.splice(already, 1);
                expectedSize--;
            }
            var vGet = map.get(k);
            var sizeGet = map.size;
            if (map.has(k) !== defined(v))
                throw new Error("Map has " + (defined(v) ? "a" : "no") + " value for key " + k + " when it should have " + (defined(v) ? "no" : "a") + " value");
            if (vGet !== v)
                throw new Error("Set value for key " + k + " to " + v + ", but got " + vGet + " back instead");
            if (sizeGet !== expectedSize)
                throw new Error("Expected map size to be " + expectedSize + " but got got " + sizeGet + " insetead");
        }
        distinctKeys.forEach(function (k) {
            map.delete(k);
            expectedSize--;
            if (map.has(k))
                throw new Error("Map has a value for key " + k + " after it was deleted");
            var sizeGet = map.size;
            if (sizeGet !== expectedSize)
                throw new Error("Expected map size to be " + expectedSize + " but got got " + sizeGet + " insetead");
        });
    }
    Collections.mapTest = mapTest;
})(Collections || (Collections = {}));