dsa - npm Package Compare versions

Comparing version 0.0.1 to 0.1.0

bit-array.js

@@ -7,3 +7,3 @@ 'use strict'
  */
-const MAX_ENTRY_INDEX = Math.log2(Number.MAX_SAFE_INTEGER)
+const MAX_BITS_PER_ENTRY = Math.log2(Number.MAX_SAFE_INTEGER)
 
@@ -19,46 +19,187 @@ /**
    * Creates a new BitArray object representing an array containing all zeros.
+   * @param {array} [data] Array of integers representing the initial state of
+   *   the bit array. Defaults to `[]`.
    */
-  constructor() {
-    this._table = [0]
+  constructor (data) {
+    this._table = []
+    if (Array.isArray(data)) {
+      this._table = data
+      this._trim()
+    }
   }
 
   /**
-   * Gets the individual bit value at the given index.
-   * @param {integer} index Index to fetch.
-   * @return {boolean} The bit value at the given index.
+   * @return The maximum number of bits that can be held by entries in the data
+   *   table.
    */
-  get(index) {
-    let tableIndex = parseInt(index / MAX_ENTRY_INDEX)
+  static getMaxBitsPerEntry () {
+    return MAX_BITS_PER_ENTRY
+  }
 
+  /**
+   * Gets the data table entry for the given bit index. This method will return
+   * `0` if the given bit index maps to an entry that is out-of-bounds.
+   * @param {integer} bitIndex The bit index (bit number) for which to fetch
+   *   the data table entry.
+   * @return {integer} The data table entry that contains the given bit index.
+   */
+  _getEntry (bitIndex) {
+    let tableIndex = parseInt(bitIndex / MAX_BITS_PER_ENTRY)
     if (tableIndex >= this._table.length) {
-      return false
+      return 0
     }
-
-    let entry = this._table[tableIndex]
-    let entryOffset = index % MAX_ENTRY_INDEX
-    return (entry & (1 << entryOffset)) > 0
+    return this._table[tableIndex]
   }
 
   /**
-   * Sets the individual bit value at the given index.
-   * @param {integer} index Index to set.
-   * @param {boolean} value Value to set.
+   * Sets the data table entry for which contains the given bit index to the
+   * given value. This method will resize the data table so that it can be
+   * addressed by the given bit index.
+   * @param {integer} bitIndex The bit index (bit number) for which to set the
+   *   data table entry.
+   * @param {integer} entry Entry to set.
    */
-  set(index, value) {
-    let tableIndex = parseInt(index / MAX_ENTRY_INDEX)
-
+  _setEntry (bitIndex, entry) {
+    let tableIndex = parseInt(bitIndex / MAX_BITS_PER_ENTRY)
     for (let k = tableIndex - this._table.length; k >= 0; k--) {
       this._table.push(0)
     }
+    this._table[tableIndex] = entry
+    this._trim()
+  }
 
-    let entry = this._table[tableIndex]
-    let entryOffset = index % MAX_ENTRY_INDEX
+  /**
+   * Determines the offset on the data table entry that contains the given
+   * bit index.
+   * @param {integer} bitIndex Bit index for which to find the entry offset.
+   * @return {integer} The offset relative to the data table entry.
+   */
+  _getOffset (bitIndex) {
+    return bitIndex % MAX_BITS_PER_ENTRY
+  }
 
+  /**
+   * Removes all high-order entry zeros from the BitArray data table
+   * effectively reclaiming unused entries.
+   */
+  _trim () {
+    while (this.size() > 0 && this._table[this.size() - 1] === 0) {
+      this._table.pop()
+    }
+  }
+
+  /**
+   * @return The number of integers needed to represent this bit array.
+   */
+  size () {
+    return this._table.length
+  }
+
+  /**
+   * Gets the individual bit value at the given index.
+   * @param {integer} bitIndex Index of the bit to fetch.
+   * @return {boolean} The bit value at the given index.
+   */
+  get (bitIndex) {
+    return (this._getEntry(bitIndex) & (1 << this._getOffset(bitIndex))) > 0
+  }
+
+  /**
+   * Sets the individual bit value at the given index.
+   * @param {integer} bitIndex Index of the bit to fetch.
+   * @param {boolean} value Value to set.
+   */
+  set (bitIndex, value) {
+    let entry = this._getEntry(bitIndex)
+    let entryOffset = this._getOffset(bitIndex)
     if (value) {
-      this._table[tableIndex] = entry | (1 << entryOffset)
+      this._setEntry(bitIndex, entry | (1 << entryOffset))
+    } else {
+      this._setEntry(bitIndex, entry & (~(1 << entryOffset)))
     }
-    else {
-      this._table[tableIndex] = entry & (~(1 << entryOffset))
+  }
+
+  /**
+   * Toggles the bit at the given index.
+   * @param {integer} index Index of the bit to toggle.
+   * @return {boolean} The resulting value of the bit.
+   */
+  toggle (index) {
+    let entry = this._getEntry(index)
+    let offset = this._getOffset(index)
+    this._setEntry(index, entry ^ (1 << offset))
+  }
+
+  /**
+   * Maps this BitArray to a new BitArray under the given unary operation.
+   * @param {function} op Operation to perform during the map.
+   * @return {BitArray} A new bit array transformed under the given operation.
+   */
+  map (op) {
+    return new BitArray(this._table.map(op))
+  }
+
+  /**
+   * Merges this BitArrays into a new BitArray by applying the given binary
+   * operation.
+   * @param {BitArray} b Bit array to "merge" into.
+   * @param {function} op Binary operation used to perform the merge.
+   * @return {BitArray} A new bit array that represents the merge of the given
+   *   arrays under the given operation.
+   */
+  merge (b, op) {
+    let a = this
+    let aTable = a._table.slice()
+    let bTable = b._table.slice()
+
+    if (a.size() < b.size()) {
+      for (let k = 0; k < b.size() - a.size(); k++) {
+        aTable.push(0)
+      }
+    } else if (b.size() < a.size()) {
+      for (let k = 0; k < a.size() - b.size(); k++) {
+        bTable.push(0)
+      }
     }
+
+    return new BitArray(aTable.map(function (entry, i) {
+      return op(entry, bTable[i])
+    }))
   }
+
+  /**
+   * Performs a bitwise "not" on this bit array.
+   * @return {BitArray} A new bit array representing the bitwise not of this
+   *   bit array.
+   */
+  not () {
+    return this.map((entry) => { return ~entry })
+  }
+
+  /**
+   * Peforms a bitwise "and" with this bit array and the given bit array.
+   * @param {BitArray} b Right operand for the bitwise "and".
+   * @return {BitArray} A new bit array that representing the result.
+   */
+  and (b) {
+    return this.merge(b, (k, j) => { return k & j })
+  }
+
+  /**
+   * Peforms a bitwise "or" with this bit array and the given bit array.
+   * @param {BitArray} b Right operand for the bitwise "or".
+   * @return {BitArray} A new bit array that representing the result.
+   */
+  or (b) {
+    return this.merge(b, (k, j) => { return k | j })
+  }
+
+  /**
+   * Peforms a bitwise "xor" with this bit array and the given bit array.
+   * @param {BitArray} b Right operand for the bitwise "xor".
+   * @return {BitArray} A new bit array that representing the result.
+   */
+  xor (b) {
+    return this.merge(b, (k, j) => { return k ^ j })
+  }
 }

package.json

 {
   "name": "dsa",
-  "version": "0.0.1",
+  "version": "0.1.0",
   "description": "A data-structures and algorithms library for node",
   "main": "index.js",
   "scripts": {
-    "test": "lab -v -a code -M 100 -c -t 100"
+    "test": "lab -v -a code -M 100 -c -t 100",
+    "standard": "standard *.js test/*.js"
   },
@@ -25,4 +26,7 @@ "repository": {
     "code": "^2.1.0",
-    "lab": "^8.2.0"
+    "jsdoc-to-markdown": "^1.3.3",
+    "lab": "^8.2.0",
+    "sinon": "^1.17.3",
+    "standard": "^6.0.4"
   }
 }

README.md

 # dsa
 A data-structures and algorithms library for node
 
+
 ## Overview
-The primary motivation behind `dsa` is to keep myself sharp. I could think of
-no better way to do so than to implement a nice library of common and exotic
-data-structures and algorithms.
+> "A data-structure a day keeps the mind atrophy away..." -- Some wise dude.
 
+The primary motivation behind `dsa` is to keep myself sharp. Specifically, its
+goal is to provide a "low stress" way to keep myself engaged with algorithmic
+problem-solving. I, due to my limited imagination, could think of no better way
+to do so than to implement  a nice library of common and exotic data-structures
+and algorithms.
+
 The secondary motivation is to provide a useful and large library of structures
 and algorithms to supplement existing libraries.
 
+## Completed
+
+- [BitArray](https://en.wikipedia.org/wiki/Bit_array)
+
 ## Proposed Data-Structures
@@ -16,3 +25,2 @@
 
-- [BitArray](https://en.wikipedia.org/wiki/Bit_array)
 - [CircularBuffer](https://en.wikipedia.org/wiki/Circular_buffer)
@@ -19,0 +27,0 @@ - [GapBuffer](https://en.wikipedia.org/wiki/Gap_buffer)

test/bit-array.js

@@ -7,4 +7,6 @@ 'use strict'
 const beforeEach = lab.beforeEach
+const afterEach = lab.afterEach
 const it = lab.it
 const expect = require('code').expect
+const sinon = require('sinon')
 
@@ -14,17 +16,130 @@ const BitArray = require('../bit-array')
 describe('BitArray', () => {
+  var maxBitsPerEntry = BitArray.getMaxBitsPerEntry()
+
   describe('constructor', () => {
-    it('should create an empty BitArray', (done) => {
-      let a = new BitArray()
-      expect(a._table.length).to.equal(1)
-      expect(a._table[0]).to.equal(0)
-      done()
+    describe('without data', () => {
+      it('should create an empty BitArray', (done) => {
+        let a = new BitArray()
+        expect(a._table.length).to.equal(0)
+        done()
+      })
     })
+
+    describe('with data', () => {
+      beforeEach((done) => {
+        sinon.spy(BitArray.prototype, '_trim')
+        done()
+      })
+
+      afterEach((done) => {
+        BitArray.prototype._trim.restore()
+        done()
+      })
+
+      it('should create a bit array with the given data', (done) => {
+        let data = [1, 2, 4, 8]
+        let a = new BitArray(data)
+        expect(a._table).to.deep.equal(data)
+        done()
+      })
+
+      it('should trim the resulting data', (done) => {
+        let array = new BitArray([1, 2, 3, 0])
+        sinon.assert.calledOnce(BitArray.prototype._trim)
+        expect(array._table).to.deep.equal([1, 2, 3])
+        done()
+      })
+    })
   }) // end 'constructor'
 
+  describe('getMaxBitsPerEntry', () => {
+    it('should return the correct value', (done) => {
+      let expected = Math.log2(Number.MAX_SAFE_INTEGER)
+      expect(BitArray.getMaxBitsPerEntry()).to.equal(expected)
+      done()
+    })
+  }) // end 'getMaxBitsPerEntry'
+
+  describe('_getEntry', () => {
+    var array
+
+    beforeEach((done) => {
+      array = new BitArray([1, 2, 3])
+      done()
+    })
+
+    it('should return the correct entry for the given bit index', (done) => {
+      expect(array._getEntry(0), 'bitIndex=0').to.equal(1)
+      expect(
+        array._getEntry(maxBitsPerEntry + 1),
+        `bitIndex=${maxBitsPerEntry + 1}`
+      ).to.equal(2)
+      expect(
+        array._getEntry(2 * maxBitsPerEntry + 1),
+        `bitIndex=${2 * maxBitsPerEntry + 1}`
+      ).to.equal(3)
+      done()
+    })
+
+    it('should return `0` if the bit index is out-of-bounds', (done) => {
+      expect(array._getEntry(1000000)).to.equal(0)
+      done()
+    })
+  }) // end '_getEntry'
+
+  describe('_setEntry', () => {
+    var array
+
+    beforeEach((done) => {
+      array = new BitArray([1, 2, 3])
+      done()
+    })
+
+    it('should set the correct bit entry', (done) => {
+      array._setEntry(0, 456)
+      array._setEntry(maxBitsPerEntry + 1, 123)
+      array._setEntry(2 * maxBitsPerEntry + 1, 890)
+      expect(array._table).to.deep.equal([456, 123, 890])
+      done()
+    })
+
+    it('should resize the data table if the index is out-of-bounds', (done) => {
+      let bitIndex = 5 * maxBitsPerEntry + 1
+      array._setEntry(bitIndex, 123456)
+      expect(array._table).to.deep.equal([1, 2, 3, 0, 0, 123456])
+      done()
+    })
+  }) // end '_setEntry'
+
+  describe('_getOffset', () => {
+    it('should return the correct offset', (done) => {
+      let bitIndex = 12304
+      expect(new BitArray()._getOffset(bitIndex))
+        .to.equal(bitIndex % maxBitsPerEntry)
+      done()
+    })
+  }) // end '_getOffset'
+
+  describe('_trim', () => {
+    it('should trim empty trailing data entries', (done) => {
+      let array = new BitArray([1, 0, 0, 0, 2, 0, 0, 0, 0, 0])
+      array._trim()
+      expect(array._table).to.deep.equal([1, 0, 0, 0, 2])
+      done()
+    })
+  }) // end 'trim'
+
+  describe('size', () => {
+    it('should return the size of the data table', (done) => {
+      expect(new BitArray([1, 2, 3, 4]).size()).to.equal(4)
+      done()
+    })
+  }) // end 'size'
+
   describe('get', () => {
-    var bitArray
+    var array
 
     beforeEach((done) => {
-      bitArray = new BitArray()
-      bitArray._table = [ 0b10101010, 0b11001100 ]
+      array = new BitArray()
+      array._table = [ 0b10101010, 0b11001100 ]
       done()
@@ -34,4 +149,4 @@ })
     it('should get the value at the given bit index', (done) => {
-      expect(bitArray.get(0), 'bitArray[0]').to.be.false()
-      expect(bitArray.get(1), 'bitArray[1]').to.be.true()
+      expect(array.get(0), 'array[0]').to.be.false()
+      expect(array.get(1), 'array[1]').to.be.true()
       done()
@@ -41,18 +156,13 @@ })
     it('should return values at any place in the data table', (done) => {
-      expect(bitArray.get(54), 'bitArray[54]').to.be.false()
-      expect(bitArray.get(55), 'bitArray[55]').to.be.true()
+      expect(array.get(54), 'array[54]').to.be.false()
+      expect(array.get(55), 'array[55]').to.be.true()
       done()
     })
-
-    it('should return `false` for out-of-bounds indices', (done) => {
-      expect(bitArray.get(2003), 'bitArray[2003]').to.be.false()
-      done()
-    })
   }) // end 'get'
 
   describe('set', () => {
-    var bitArray
+    var array
 
     beforeEach((done) => {
-      bitArray = new BitArray()
+      array = new BitArray()
       done()
@@ -62,4 +172,4 @@ })
     it('should set a `true` value for the bit at the given index', (done) => {
-      bitArray.set(22, true)
-      expect(bitArray.get(22)).to.be.true()
+      array.set(22, true)
+      expect(array.get(22)).to.be.true()
       done()
@@ -69,14 +179,106 @@ })
     it('should set a `false` value for the bit at the given index', (done) => {
-      bitArray.set(5, true)
-      bitArray.set(5, false)
-      expect(bitArray.get(5)).to.be.false()
+      array.set(5, true)
+      array.set(5, false)
+      expect(array.get(5)).to.be.false()
       done()
     })
+  }) // end 'set'
 
-    it('should resize the table if the index is out of bounds', (done) => {
-      bitArray.set(110, true)
-      expect(bitArray._table.length).to.equal(3)
+  describe('toggle', () => {
+    var array
+
+    beforeEach((done) => {
+      array = new BitArray([ 0b10 ])
       done()
     })
-  }) // end 'set'
-}) // end 'Bit Array'
+
+    it('should toggle a bit "on"', (done) => {
+      array.toggle(0)
+      expect(array.get(0)).to.be.true()
+      done()
+    })
+
+    it('should toggle a bit "off"', (done) => {
+      array.toggle(1)
+      expect(array.get(1)).to.be.false()
+      done()
+    })
+  }) // end 'toggle'
+
+  describe('map', () => {
+    it('should return a bit array mapped under the given operation', (done) => {
+      let array = new BitArray([1, 2, 3])
+      expect(array.map((e) => { return e + 1 })._table).to.deep.equal([2, 3, 4])
+      done()
+    })
+  }) // end 'map'
+
+  describe('merge', () => {
+    it('should merge the bit arrays under the given operation', (done) => {
+      let a = new BitArray([1, 2, 3])
+      let b = new BitArray([3, 2, 1])
+      expect(a.merge(b, (k, j) => { return k + j })._table)
+        .to.deep.equal([4, 4, 4])
+      done()
+    })
+
+    it('should merge into larger bit arrays', (done) => {
+      let a = new BitArray([1])
+      let b = new BitArray([0, 2, 3])
+      expect(a.merge(b, (k, j) => { return Math.max(k, j) })._table)
+        .to.deep.equal([1, 2, 3])
+      done()
+    })
+
+    it('should merge into smaller bit arrays', (done) => {
+      let a = new BitArray([1, 2, 2])
+      let b = new BitArray([1])
+      expect(a.merge(b, (k, j) => { return k + j })._table)
+        .to.deep.equal([2, 2, 2])
+      done()
+    })
+  }) // end 'merge'
+
+  describe('not', () => {
+    it('should return the bitwise `not` of the bit array', (done) => {
+      let given = [
+        0b11111111111111111111111111111111111111111111111111111,
+        0b11110000111100001111010100000111111101111111011111111,
+        455,
+        18,
+        19,
+        22
+      ]
+      expect(new BitArray(given).not()._table)
+        .to.deep.equal(given.map((entry) => { return ~entry }))
+      done()
+    })
+  }) // end 'not'
+
+  describe('and', () => {
+    it('should return the bitwise `and` of the two bit arrays', (done) => {
+      let a = new BitArray([ 0b101, 0b111 ])
+      let b = new BitArray([ 0b100, 0b000 ])
+      expect(a.and(b)._table).to.deep.equal([0b100])
+      done()
+    })
+  }) // end 'and'
+
+  describe('or', () => {
+    it('should return the bitwise `or` of the two bit arrays', (done) => {
+      let a = new BitArray([ 0b101, 0b111 ])
+      let b = new BitArray([ 0b010, 0b000 ])
+      expect(a.or(b)._table).to.deep.equal([0b111, 0b111])
+      done()
+    })
+  }) // end 'or'
+
+  describe('xor', () => {
+    it('should return the bitwise `xor` of the two bit arrays', (done) => {
+      let a = new BitArray([ 0b101, 0b111 ])
+      let b = new BitArray([ 0b110, 0b101 ])
+      expect(a.xor(b)._table).to.deep.equal([0b11, 0b10])
+      done()
+    })
+  }) // end 'xor'
+}) // end 'BitArray'

New alerts

Major refactor

Supply chain risk

Package has recently undergone a major refactor. It may be unstable or indicate significant internal changes. Use caution when updating to versions that include significant changes.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

15675

increased by196.82%

Lines of code

422

increased by263.79%

Number of lines in readme file

40

increased by25%

Worsened metrics

Dev dependency count

5

increased by150%

Number of medium supply chain risk alerts

1

increased byInfinity%

No dependency changes