SHARE
TWEET

Untitled

a guest Sep 13th, 2017 56 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. function HashMapNode(key, value) {
  2.     this.key   = key;
  3.     this.value = value;
  4.     this.prev  = null;
  5.     this.next  = null;
  6. }
  7.  
  8. function HashMap(keyEquals, keyHashCode) {
  9.     this.storageArray = new Array(8);
  10.     this.size         = 0;
  11.     this.keyEquals    = keyEquals;
  12.     this.keyHashCode  = keyHashCode;
  13. }
  14.  
  15. HashMap.prototype.insert = function(node, storageArray) {
  16.     var storageArrayIndex = this.keyHashCode(node.key) & (storageArray.length - 1);
  17.     node.prev = null;
  18.     node.next = storageArray[storageArrayIndex];
  19.  
  20.     if (storageArray[storageArrayIndex]) {
  21.         storageArray[storageArrayIndex].prev = node;
  22.     }
  23.  
  24.     storageArray[storageArrayIndex] = node;
  25. };
  26.  
  27. HashMap.prototype.expand = function() {
  28.     var newStorageArray = new Array(2 * this.storageArray.length);
  29.  
  30.     for (var i = 0; i < this.storageArray.length; ++i) {
  31.         while (this.storageArray[i]) {
  32.             var node = this.storageArray[i];
  33.             this.storageArray[i] = this.storageArray[i].next;
  34.             this.insert(node, newStorageArray);
  35.         }
  36.     }
  37.  
  38.     this.storageArray = newStorageArray;
  39. };
  40.  
  41. HashMap.prototype.put = function(key, value) {
  42.     if (this.size === this.storageArray.length) {
  43.         this.expand();
  44.     }
  45.  
  46.     var storageArrayIndex = this.keyHashCode(key) & (this.storageArray.length - 1);
  47.     var currentNode = this.storageArray[storageArrayIndex];
  48.  
  49.     while (currentNode) {
  50.         if (this.keyEquals(currentNode.key, key)) {
  51.             var oldValue = currentNode.value;
  52.             currentNode.value = value;
  53.             return oldValue;
  54.         }
  55.  
  56.         currentNode = currentNode.next;
  57.     }
  58.  
  59.     // Once here, the 'key' has no mapping in this hash map.
  60.     var newNode = new HashMapNode(key, value);
  61.     this.insert(newNode, this.storageArray);
  62.     this.size++;
  63.     return null;
  64. };
  65.  
  66. HashMap.prototype.getNodeByKey = function(key) {
  67.     var storageArrayIndex = this.keyHashCode(key) & (this.storageArray.length - 1);
  68.     var currentNode = this.storageArray[storageArrayIndex];
  69.  
  70.     while (currentNode) {
  71.         if (this.keyEquals(currentNode.key, key)) {
  72.             return currentNode;
  73.         }
  74.  
  75.         currentNode = currentNode.next;
  76.     }
  77.  
  78.     return null;
  79. };
  80.  
  81. HashMap.prototype.get = function(key) {
  82.     var node = this.getNodeByKey(key);
  83.     return node ? node.value : null;
  84. };
  85.  
  86. HashMap.prototype.containsKey = function(key) {
  87.     return this.getNodeByKey(key) !== null;
  88. };
  89.  
  90. HashMap.prototype.unlink = function(node, storageArrayIndex) {
  91.     if (node.prev) {
  92.         node.prev.next = node.next;
  93.     } else {
  94.         this.storageArray[storageArrayIndex] = node.next;
  95.  
  96.         if (this.storageArray[storageArrayIndex]) {
  97.             this.storageArray[storageArrayIndex].prev = null;
  98.         }
  99.     }
  100.  
  101.     if (node.next) {
  102.         node.next.prev = node.prev;
  103.     }
  104. };
  105.  
  106. HashMap.prototype.remove = function(key) {
  107.     var storageArrayIndex = this.keyHashCode(key) & (this.storageArray.length - 1);
  108.     var currentNode = this.storageArray[storageArrayIndex];
  109.  
  110.     while (currentNode) {
  111.         if (this.keyEquals(currentNode.key, key)) {
  112.             this.unlink(currentNode, storageArrayIndex);
  113.             this.size--;
  114.             return currentNode.value;
  115.         }
  116.  
  117.         currentNode = currentNode.next;
  118.     }
  119.  
  120.     return null;
  121. };
  122.  
  123. HashMap.prototype.getSize = function() {
  124.     return this.size;
  125. };
  126.  
  127. function Point(x, y) {
  128.     this.x = x;
  129.     this.y = y;
  130. }
  131.  
  132. function pointEquals(p1, p2) {
  133.     return p1.x === p2.x && p1.y === p2.y;
  134. }
  135.  
  136. function pointHashCode(p) {
  137.     return p.x ^ p.y;
  138. }
  139.  
  140. function assert(test) {
  141.     if (!test) {
  142.         console.log("Test failure!");
  143.     }
  144. }
  145.  
  146. function test() {
  147.     var map = new HashMap(pointEquals, pointHashCode);
  148.     var p1 = new Point(0, 0);
  149.     var p2 = new Point(0, 0);
  150.     map.put(p1, "value");
  151.     assert(map.get(p1) === "value");
  152.     assert(map.get(p2) === "value");
  153.     p2.x = 1;
  154.     assert(!map.containsKey(p2));
  155.     map.put(p1, "second value");
  156.     assert(map.get(p1) === "second value");
  157.     map.remove(p1);
  158.     assert(map.get(p1) === null);
  159.     assert(map.containsKey(p1) === false);
  160.  
  161.     for (var i = 0; i < 100; ++i) {
  162.         assert(map.getSize() === i);
  163.         var p = new Point(0, i);
  164.         map.put(p, "" + i);
  165.         assert(map.getSize() === i + 1);
  166.     }
  167.  
  168.     for (var i = 99; i >= 0; --i) {
  169.         var p = new Point(0, i);
  170.         assert(map.get(p) === "" + i);
  171.     }
  172.  
  173.     for (var i = 0; i < 100; ++i) {
  174.         assert(map.getSize() === 100 - i);
  175.         var p = new Point(0, i);
  176.         assert(map.remove(p) === "" + i);
  177.         assert(map.getSize() === 99 - i);
  178.     }
  179. }
  180.  
  181. test();
RAW Paste Data
Top