Merge branch 'master' of github.com:mgechev/javascript-algorithms

mgechev · mgechev · commit fcd2b07a4ebb · 2015-05-18T11:12:21.000+03:00
* 'master' of github.com:mgechev/javascript-algorithms:
  use https instead of ssh
  fibonacci spec and throw on too large of input.
  Fibonacci algorithm
  LZW Encoding/Decoding
diff --git a/readme.md b/readme.md
@@ -23,7 +23,7 @@ npm install
 - Go to the parent directory of the `javascript-algorithms` folder and call:
 
 ```bash
-git clone git@github.com:mgechev/javascript-algorithms.git javascript-algorithms-docs
+git clone https://github.com/mgechev/javascript-algorithms.git javascript-algorithms-docs
 ```
 
 - Go to the `javascript-algorithms-docs` folder and change current branch to `gh-pages`:
@@ -81,4 +81,4 @@ If the build is not successful fix your code in order the tests and jshint valid
 
 ## License
 
-The code in this repository is distributed under the terms of the MIT license.
+The code in this repository is distributed under the terms of the MIT license.
diff --git a/src/compression/LZW/LZW.js b/src/compression/LZW/LZW.js
@@ -0,0 +1,95 @@
+/**
+ * LZW Encoding/Decoding
+ *
+ * Lempel–Ziv–Welch (LZW) is a universal lossless data
+ * compression algorithm. It is an improved implementation
+ * of the LZ78 algorithm.
+ *
+ * @example
+ * var lzwModule = require('path-to-algorithms/src/compression'+
+ * '/LZW/LZW');
+ * var lzw = new lzwModule.LZW();
+ *
+ * var compressed = lzw.compress("ABCABCABCABCABCABC");
+ * console.log(compressed);
+ *
+ * var decompressed = lzw.decompress(compressed);
+ * console.log(decompressed);
+ *
+ * @module compression/LZW/LZW
+ */
+(function (exports) {
+  'use strict';
+
+  exports.LZW = function () {
+    this.dictionarySize = 256;
+  };
+
+  exports.LZW.compress = function (data) {
+    var i;
+    var dictionary = {};
+    var character;
+    var wc;
+    var w = '';
+    var result = [];
+
+    for (i = 0; i < this.dictionarySize; i = i + 1) {
+      dictionary[String.fromCharCode(i)] = i;
+    }
+
+    for (i = 0; i < data.length; i = i + 1) {
+      character = data.charAt(i);
+      wc = w + character;
+      if (dictionary.hasOwnProperty(wc)) {
+        w = wc;
+      } else {
+        result.push(dictionary[w]);
+        dictionary[wc] = this.dictionarySize;
+        this.dictionarySize = this.dictionarySize + 1;
+        w = String(character);
+      }
+    }
+
+    if (w !== '') {
+      result.push(dictionary[w]);
+    }
+
+    return result;
+  };
+
+  exports.LZW.decompress = function (compressedData) {
+    var i;
+    var dictionary = [];
+    var w;
+    var result;
+    var key;
+    var entry = '';
+
+    for (i = 0; i < this.dictionarySize; i = i + 1) {
+      dictionary[i] = String.fromCharCode(i);
+    }
+
+    w = String.fromCharCode(compressedData[0]);
+    result = w;
+
+    for (i = 1; i < compressedData.length; i = i + 1) {
+      key = compressedData[i];
+      if (dictionary[key]) {
+        entry = dictionary[key];
+      } else {
+        if (key === this.dictionarySize) {
+          entry = w + w.charAt(0);
+        } else {
+          return null;
+        }
+      }
+
+      result += entry;
+      dictionary[this.dictionarySize] = w + entry.charAt(0);
+      this.dictionarySize = this.dictionarySize + 1;
+      w = entry;
+    }
+
+    return result;
+  };
+})(typeof window === 'undefined' ? module.exports : window);
diff --git a/src/others/fibonacci.js b/src/others/fibonacci.js
@@ -0,0 +1,40 @@
+/**
+ * Nth number of fibonacci's sequence
+ *
+ * Returns the nth number of fibonacci's sequence.
+ *
+ * @public
+ *
+ * @example
+ * var fibonacci = require('path-to-algorithms/src/others/fibonacci').fibonacci;
+ * var nth = fibonacci(20);
+ *
+ * console.log(nth); // 6765
+ *
+ * @param {Number} n The nth position in fibonacci's sequence
+ *
+ * @module others/fibonacci
+*/
+(function (exports) {
+  'use strict';
+
+  function fibonacci (n) {
+    if (n > 97) {
+      throw 'Input too large, results in inaccurate fibonacci value.';
+    }
+    var n1 = 0;
+    var n2 = 1;
+    var aux;
+
+    while (n > 0) {
+      aux = n1;
+      n1 = n2;
+      n2 += aux;
+      n = n - 1;
+    }
+
+    return n1;
+  }
+
+  exports.fibonacci = fibonacci;
+})(typeof window === 'undefined' ? module.exports : window);
diff --git a/test/others/fibonacci.spec.js b/test/others/fibonacci.spec.js
@@ -0,0 +1,28 @@
+'use strict';
+
+var mod = require('../../src/others/fibonacci.js');
+var fibonacci = mod.fibonacci;
+
+describe('fibonacci algorithm', function () {
+  it('should return value 1 with input 1.', function () {
+    expect(fibonacci(1)).toBe(1);
+  });
+  it('should return value 1 with input 2.', function () {
+    expect(fibonacci(2)).toBe(1);
+  });
+  it('should return value 2 with input 3.', function () {
+    expect(fibonacci(3)).toBe(2);
+  });
+  it('should return value 3 with input 4.', function () {
+    expect(fibonacci(4)).toBe(3);
+  });
+  it('should return value 5 with input 5.', function () {
+    expect(fibonacci(5)).toBe(5);
+  });
+  it('should be 83621143489848422977 with input 97.', function () {
+    expect(fibonacci(97)).toBe(83621143489848422977);
+  });
+  it('should throw when input is too large.', function () {
+    expect(function () {fibonacci(98)}).toThrow('Input too large, results in inaccurate fibonacci value.');
+  });
+});
