hashes - npm Package Compare versions

Comparing version 0.0.1 to 0.0.2

hashtable.js

@@ -8,7 +8,2 @@ var Hashtable = (function () {
 
-    function Bucket() {
-        this._freeSlots = []; //TODO: This should be a min-heap
-        this._items = [];
-    }
-
     function Hashtable(options) {
@@ -81,9 +76,9 @@ this._buckets = {
 
-    //Searches the given key within the given bucket. If the key is found then returns the index in the _items array,
+    //Searches the given key within the given bucket. If the key is found then returns the index in the bucket,
     //otherwise returns -1
     Hashtable.getKeyIndex = function (bucket, key, options) {
-        var i, bucketLength = bucket._items.length, equality, currentItem;
+        var i, bucketLength = bucket.length, equality, currentItem;
         equality = Hashtable.getEqual(key, options);
         for (i = 0; i < bucketLength; i++) {
-            currentItem = bucket._items[i];
+            currentItem = bucket[i];
             if (currentItem !== undefined && equality(currentItem._key, key)) {
@@ -99,13 +94,3 @@ return i;
     Hashtable.addToBucket = function (bucket, key, value, options) {
-        var i, bucketLength, freeIndex, item = new DataItem(key, value);
-
-        //The bucket has no free slots from previous deletions, add at the end of the items;
-        if (bucket._freeSlots.length === 0) {
-            bucket._items.push(item);
-
-        } else {
-            //The bucket has some free slots!
-            freeIndex = bucket._freeSlots.pop();
-            bucket._items[freeIndex] = item;
-        }
+        bucket.push(new DataItem(key, value));
     };
@@ -124,4 +109,3 @@
     Hashtable.removeKey = function (bucket, key, options) {
-
-        var index = Hashtable.getKeyIndex(bucket, key, options);
+        var index = Hashtable.getKeyIndex(bucket, key, options), bucketLength = bucket.length;
         if (index < 0) {
@@ -131,5 +115,7 @@ return false;
 
-        bucket._items[index] = undefined;
-        bucket._freeSlots.push(index);
+        if (bucketLength > 1 && index !== (bucketLength - 1)) {
+            bucket[index] = bucket[bucketLength - 1];
+        }
 
+        bucket.length = bucketLength - 1;
         return true;
@@ -155,3 +141,3 @@ }
         if (!this._buckets.hasOwnProperty(hash)) {
-            this._buckets[hash] = new Bucket();
+            this._buckets[hash] = [];
         }
@@ -162,3 +148,3 @@ bucket = this._buckets[hash];
             if (overwriteIfExists) {
-                bucket._items[itemIndex] = new DataItem(key, value);
+                bucket[itemIndex] = new DataItem(key, value);
                 return true;
@@ -194,3 +180,6 @@ }
 
-        return bucket._items[itemIndex]._value;
+        return {
+            value: bucket[itemIndex]._value,
+            key: bucket[itemIndex]._value
+        };
     }
@@ -241,2 +230,32 @@
 
+    ///Returns all the hashes that are currently in the hashtable
+    Hashtable.prototype.getHashes = function () {
+        var result = [], hash;
+        for (hash in this._buckets) {
+            if (this._buckets.hasOwnProperty(hash) && this._buckets[hash].length > 0) {
+                result.push(hash);
+            }
+        }
+
+        return result;
+    }
+
+    ///Returns an array of all the key-value pairs in the hashtable
+    Hashtable.prototype.getKeyValuePairs = function () {
+        var result = [], hash, bucket, i, bucketLength;
+        for (hash in this._buckets) {
+            if (this._buckets.hasOwnProperty(hash)) {
+                bucket = this._buckets[hash];
+                for (i = 0, bucketLength = bucket.length; i < bucketLength; i++) {
+                    result.push({
+                        key: bucket[i]._key,
+                        value: bucket[i]._value
+                    });
+                }
+            }
+        }
+
+        return result;
+    }
+
     ///Returns the total number of items in the hashtable
@@ -258,13 +277,15 @@ Hashtable.prototype.count = function () {
         for (hash in this._buckets) {
+            if (!this._buckets.hasOwnProperty(hash)) {
+                continue;
+            }
             console.log("*");
             console.log("Bucket:", hash);
             bucket = this._buckets[hash];
-            console.log("Free Slots:", bucket._freeSlots);
-            length = bucket._items.length
+            length = bucket.length;
             console.log("There are", length, "item slots");
             for (i = 0; i < length; i++) {
-                if (bucket._items[i] === undefined) {
-                    console.log("  ",i, ":", undefined);
+                if (bucket[i] === undefined) {
+                    console.log("  ", i, ":", undefined);
                 } else {
-                    console.log("  ", i, ":", "Key:", bucket._items[i]._key, "Value:", bucket._items[i]._value);
+                    console.log("  ", i, ":", "Key:", bucket[i]._key, "Value:", bucket[i]._value);
                 }
@@ -271,0 +292,0 @@ }

package.json

 {
     "name": "hashes",
-	"version" : "0.0.1",
-    "description": "A package implementing a 'real' Hashtable and Hashset",
+	"version" : "0.0.2",
+    "description": "A package implementing a 'real' Hashtable and (soon) Hashset",
     "author": "Boris Kozorovitzky",
@@ -6,0 +6,0 @@ "main":"hashtable.js",

README.md

 jsHash
 ======
 
-A node package that implements the Hashtable and HashSet datastructures
+A node package that implements the Hashtable and HashSet (in the near future) datastructures.
+
+Install:
+
+```
+$ npm install hashes
+```
+
+##API
+Currently only a hashtable is implemented.
+
+To use the module in your code simply type
+
+```javascript
+var hashes = require('hashes');
+```
+
+###Hashtable
+To create a new hash table use the _new_ keyword:
+
+```
+var myHashTable = new hashes.HashTable();
+``` 
+
+You may provide an optional argument to the constructor called _options_. The options object can have any of the following methods and properties:
+
+* **getHashCode(key)** - Returns the hash code of the given _key_ object.
+
+* **equal(first, second)** - Returns true if the given arguments are equal, and false otherwise.
+
+The options object is used throughout the diffrent API calls. The API of the hashtable is therefore:
+
+* **add(key, value, [overwriteIfExists])** - Adds the given key-value pair to the hashtable. _overwriteIfExists_ is an optional argument that is used when the given key already exists in the hashtable.
+If _overwriteIfExists_ is truthy then the given key-value pair will overwrite the existing key-value pair, otherwise the given key-value pair will not be added to the hashtable.
+
+* **get(key)** - Returns the key-value pair associated with the given key. If there is no key-value pair associated with the given key, null is returned. The returned object is ```{key:key, value:value}```.
+(Note that a pair is returned because the key in the hashtable may differ from the provided key.)
+
+* **remove(key)** - Removes the key-value pair associated with the given key from the hashtable. Returns true if a key-value pair was removed and false otherwise (e.g. when there is no value associated with the given key).
+
+* **contains(key)** - Returns true if there is a value associated with the given key and false otherwise.
+
+* **getHashes()** - Returns a string array of all the hashes that are currently in the hashtable.
+
+* **getKeyValuePairs()** - Returns an array of all the key-value pairs in the hashtable **in no particular order**. Each object in the returned array is ```{key:key, value:value}```.
+
+* **count()** - Returns the number of key-value pairs in the hashtable.
+
+* **clear()** - Removes all the key-value pairs from the hashtable.
+
+## Contributions
+Please feel free to contribute code to this module. Make sure that the contributed code is in the spirit of the existing code.
+Thanks!
+
+
+## Test
+The module uses [Mocha](http://visionmedia.github.com/mocha/) testing framework for all the tests. To run the tests simply type
+```mocha``` in a command line while in the module main directory.
+
+## License
+
+(The MIT License)
+
+Copyright (c) 2012 Boris Kozorovitzky
+
+Permission is hereby granted, free of charge, to any person obtaining
+a copy of this software and associated documentation files (the
+'Software'), to deal in the Software without restriction, including
+without limitation the rights to use, copy, modify, merge, publish,
+distribute, sublicense, and/or sell copies of the Software, and to
+permit persons to whom the Software is furnished to do so, subject to
+the following conditions:
+
+The above copyright notice and this permission notice shall be
+included in all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED 'AS IS', WITHOUT WARRANTY OF ANY KIND,
+EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
+IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
+CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
+TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
+SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

test/hashtable.js

@@ -44,3 +44,3 @@ describe('Hashtable tests', function () {
     it('should get the value of key1 from the hashtable', function () {
-        var value = hashtable.get(key1);
+        var value = hashtable.get(key1).value;
         should.exist(value);
@@ -58,3 +58,3 @@ value.should.equal(value1);
         hashtable.count().should.equal(1);
-        var value = hashtable.get(key1);
+        var value = hashtable.get(key1).value;
         should.exist(value);
@@ -77,3 +77,3 @@ value.should.equal(value2);
         hashtable.count().should.equal(3);
-        var value = hashtable.get(key3);
+        var value = hashtable.get(key3).value;
         should.exist(value);
@@ -100,3 +100,25 @@ value.should.equal("3");
 
+    it('should add multiple hash codes', function () {
+        hashtable.add(key2, "2", false);
+        hashtable.count().should.equal(2);
+        var value = hashtable.get(key2).value;
+        should.exist(value);
+        value.should.equal("2");
+    });
 
+    it('should get all the hashes in the hashtable', function () {
+        var hashes = hashtable.getHashes();
+        should.exist(hashes);
+        hashes.length.should.equal(2);
+    });
+
+    it('should get all the key-value pairs in the hashtable', function () {
+        var keyValuePairs = hashtable.getKeyValuePairs();
+        should.exist(keyValuePairs);
+        keyValuePairs.length.should.equal(2);
+        keyValuePairs[0].key.should.equal(key3); //Not so robust :(
+        keyValuePairs[0].value.should.equal("3");
+    });
+
+
 });

No alert changes

Improved metrics

Total package byte prevSize

80393

increased by12.48%

Lines of code

523

increased by8.28%

Number of lines in readme file

86

increased by2050%

No dependency changes