Skip to content

Latest commit

 

History

History
145 lines (102 loc) · 3.06 KB

README.md

File metadata and controls

145 lines (102 loc) · 3.06 KB

Diqueue

A performant updatable priority queue which can pop AND shift.


Install

$ npm install --save diqueue

Usage

var DiQueue = require('diqueue');

// An empty priority queue
var q = new DiQueue();

q.push(88);
q.push(12);
q.push(23);

q.pop(); // returns 12
q.shift(); // returns 88

// Initialized with data
var qData = new DiQueue([88, 12, 23, 45, 56]);

qData.length; // returns 5
qData.pop(); // returns 12
qData.length; // returns 4
qData.shift(); // returns 88
qData.length; // returns 3
qData.peekPop(); // returns 23
qData.length; // returns 3 (unchanged)
qData.peekShift(); // returns 56
qData.length; // returns 3 (unchanged)

// Initialized with custom comparator
var qComp = new DiQueue([88, 12, 23, 45, 56], (a, b) => {
  return a < b ? a : b;
});

qComp.pop(); // returns 88
qComp.shift(); // returns 12

// Initialized with custom objects
var qObj = new DiQueue([{ name: 'A', lag: 54 }, { name: 'B', lag: 22 }, { name: 'C', lag: 37 }], (a, b) => {
  return a.lag > b.lag ? a : b;
});

qObj.pop() // returns object { name: 'B', lag: 22 }
qObj.shift() // returns object { name: 'A', lag: 54 }

// Initialized an updatable priority queue with a custom key
var qObj2 = new DiQueue([{ name: 'A', lag: 54 }, { name: 'B', lag: 22 }, { name: 'C', lag: 37 },{ name: 'D', lag: 15 }], (a, b) => {
  return a.lag > b.lag ? a : b;
}, 'name');

qObj2.update('A', { name: 'A', lag: 12 });
qObj2.remove('D');

qObj2.pop(); // returns object { name: 'A', lag: 12 }
qObj2.pop(); // returns object { name: 'B', lag: 22 }
qObj2.pop(); // returns object { name: 'C', lag: 37 }

API

constructor(data, compareFn, identityKey)


data

  • Optional
  • Type: Array
  • Default: []

The array of items to insert into the priority queue.

compareFn

  • Optional
  • Type: Function
  • Default: (a, b) => { return a > b ? a : b; }

A comparator function to order the elements in the queue.

identityKey

  • Optional
  • Type: String
  • Default: id

For an updatable queue, the key which is used to identify the object to update.

push(data)


data

  • Required
  • Type: Object

The item to insert into the priority queue.

remove(idValue)


idValue

  • Required
  • Type: Any

The value used to match the object, which will be removed.

update(idValue, updatedItem)


idValue

  • Required
  • Type: Any

The value used to match the object, which will be updated.

updatedItem

  • Required
  • Type: Object

The new item which will replace the previous item that matched the given idValue.

License

MIT © 2017, Muaz Siddiqui

Inspired by:

js-priority-queue by Adam Hooper

tinyqueue by Vladimir Agafonkin

updatable-priority-queue by Benjamin Becquet