little-ds-toolkit - npm Package Compare versions

Comparing version 0.1.0 to 0.2.0

lib/heap.js

		@@ -155,2 +155,3 @@
		Heap.prototype.removeIndex = function (i) {
		var last;
		if (i === -1) return;
		@@ -174,2 +175,18 @@

		Heap.prototype.replaceIndex = function (i, value) {
		var last;
		if (i === -1) return;
		this.data.push(value);

		this._swap(i, this.data.length - 1);

		last = this.data.pop();

		if (this.data.length > 1) {
		this._bubbleUp(i);
		this._bubbleDown(i);
		}
		return last;
		};

		Heap.prototype.toArray = function () {
		@@ -176,0 +193,0 @@ return this.data.slice(0);

package.json

		{
		"name": "little-ds-toolkit",
		"version": "0.1.0",
		"version": "0.2.0",
		"description": "A small collection of useful data structures",
		@@ -5,0 +5,0 @@ "main": "index.js",

README.md

		@@ -83,2 +83,21 @@ little-ds-toolkit

		Advanced features: updating item order and removing items
		---------------------------------------------------------
		An algorithm may require to remove items or update the sorting order. These operations can be expensive as they require to search the item to remove or replace (O(n)). You can solve this problem with some additional book keeping, using the "onMove" callback.
		This function can be passed to the contructor (as second argument) and is called every time an item moves in the heap.
		```js
		var itemPos = {};
		var heap = new Heap(undefined, function (item, previousPos, nextPos) {
		itemPos[item.id] = nextPos;
		});
		```
		Using this you can easily remove or replace an item in O(log n):
		```js
		// removing item "A"
		heap.removeIndex(itemPos.A);

		// replace item "A"
		heap.removeIndex(itemPos.A, newItem);
		```

		min-max-heap
		@@ -137,2 +156,3 @@ ============
		The find returns the element "leader". The important part is that 2 elements with the same leader belongs to the same group.
		You can retrieve the original value with "item.data".

		@@ -139,0 +159,0 @@ lru-cache

tests/heap.spec.js

		@@ -185,2 +185,35 @@ var assert = require('chai').assert;

		describe('replaceIndex', function () {
		var h;

		beforeEach(function () {
		h = new Heap();
		h.data = [2, 5, 3, 8, 7, 4];
		});

		it('must be able to replace the tail', function () {
		var res = h.replaceIndex(5, 1);
		assert.equal(res, 4);
		assert.deepEqual(h.data, [1, 5, 2, 8, 7, 3]);
		});

		it('must be able to replace the root', function () {
		var res = h.replaceIndex(0, 10);
		assert.equal(res, 2);
		assert.deepEqual(h.data, [3, 5, 4, 8, 7, 10]);
		});

		it('must be able to replace in the middle', function () {
		var res = h.replaceIndex(2, 10);
		assert.equal(res, 3);
		assert.deepEqual(h.data, [2, 5, 4, 8, 7, 10]);
		});

		it('must be able to replace in the middle (2)', function () {
		var res = h.replaceIndex(2, 0);
		assert.equal(res, 3);
		assert.deepEqual(h.data, [0, 5, 2, 8, 7, 4]);
		});
		});

		describe('pushall', function () {
		@@ -187,0 +220,0 @@ it('must push an array', function () {

New alerts