New Research: Supply Chain Attack on Axios Pulls Malicious Dependency from npm.Details →
Socket
Book a DemoSign in
Socket
Book a DemoSign in

priority-queue

Package Overview
Dependencies
Maintainers
1
Versions
4
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

priority-queue - npm Package Compare versions

Comparing version
0.1.0
 to
0.2.0
+32
.github/workflows/main.yml
# This is a basic workflow to help you get started with Actions
name: CI
# Controls when the workflow will run
on:
# Triggers the workflow on push or pull request events but only for the main branch
push:
branches: [ main ]
# Allows you to run this workflow manually from the Actions tab
workflow_dispatch:
# A workflow run is made up of one or more jobs that can run sequentially or in parallel
jobs:
# This workflow contains a single job called "build"
build:
# The type of runner that the job will run on
runs-on: ubuntu-latest
# Steps represent a sequence of tasks that will be executed as part of the job
steps:
# Checks-out your repository under $GITHUB_WORKSPACE, so your job can access it
- uses: actions/checkout@v2
# Runs a single command using the runners shell
- name: setup
run: npm install
# Runs a single command using the runners shell
- name: tests
run: npm test
+36
test-fuzz.js
import PQ from './priority-queue.js'
function randomInt (min, max) {
return min + Math.round((max - min) * Math.random())
}
const TEST_COUNT = 20000
console.log(`Fuzzing ${TEST_COUNT} iterations`)
for (let i=0; i < TEST_COUNT; i++) {
const itemCount = randomInt(1, 1000)
const queue = PQ.create(itemCount)
// add itemCount items with random values
for (let i = 0; i < itemCount; i++) {
const val = Math.random()
const priority = val
PQ.queue(queue, val, priority)
}
// remove the items in order
let output = [ ]
for (let i = 0; i < itemCount; i++)
output.push(PQ.dequeue(queue))
for (let i = 0; i < itemCount; i++)
if (i > 0 && output[i] > output[i-1])
throw new Error(`priority not respected in this run; ${output[i]} > ${output[i-1]}`)
}
console.log('Fuzzing completed without errors')
+9
-0
CHANGELOG.md

@@ -0,1 +1,10 @@

## 0.2.0
* BREAKING: queue(...) requires priority as the 3rd argument, no longer optional
* BREAKING: comparator functions are removed. They are confusing and error-prone. Just pass a simple priority value instead
* BREAKING: priority-queue is now always a max-heap,(i.e.,dequeue(...) always returns highest priority item.) If you want a min-heap, use negative priority values.
* fix issue #2
* add fuzz testing
* update mocha dep
## 0.1.0

@@ -2,0 +11,0 @@ * package maintenance taken over by mreinstein

+1
-1
LICENSE
MIT License
Copyright (c) 2021 Mike Reinstein
Copyright (c) 2022 Mike Reinstein

@@ -5,0 +5,0 @@ Permission is hereby granted, free of charge, to any person obtaining a copy

+6
-4
package.json
{
"name": "priority-queue",
"version": "0.1.0",
"version": "0.2.0",
"description": "functional, data oriented priority queue that doesn't suck",

@@ -8,3 +8,5 @@ "main": "priority-queue.js",

"scripts": {
"test": "mocha test.js",
"test": "npm-run-all -s test:*",
"test:unit": "mocha test.js",
"test:fuzz": "node test-fuzz.js",
"prepublishOnly": "npm test"

@@ -28,5 +30,5 @@ },

"devDependencies": {
"mocha": "^8.3.2"
"mocha": "^10.0.0",
"npm-run-all": "^4.1.5"
},
"dependencies": {},
"engines": {

@@ -33,0 +35,0 @@ "node": ">=12.17"

+117
-28
priority-queue.js

@@ -1,33 +0,107 @@

import Heap from './heap.js'
import removeItem from './remove-array-item.js'
function create (maxLength=1000) {
return {
arr: new Array(maxLength),
length: 0,
maxLength,
}
}
// creates a new priority queue data structure
function create (comparator, maxLength=1000) {
return Heap.create(comparator, maxLength)
function queue (heap, item, priority) {
if (priority === undefined)
throw new Error('must include priority when queueing')
if (_findIndex(heap, item) >= 0) {
del(heap, item)
}
if (heap.length === heap.maxLength) {
return
}
heap.arr[heap.length] = { item, priority }
heap.length++
_upHeap(heap, heap.length-1)
}
function _findIndex (arr, length, needle) {
for (let i=0; i < length; i++)
if (arr[i].val === needle)
return i
return -1
// traverse up the heap from a starting index
//
// heap
// index to start at
function _upHeap (heap, index) {
while (index > 0) {
let parentIdx
if (index % 2 === 0)
parentIdx = (index - 2) / 2
else
parentIdx = (index - 1) / 2
// if the parent is greater than the current node, stop because we've corrected the heap
if (heap.arr[parentIdx].priority >= heap.arr[index].priority)
return
_swap(heap.arr, index, parentIdx)
index = parentIdx
}
}
function queue (heap, val, priority) {
// TODO: consider checking existing priority. If it's the same, no point in deleting and re-inserting
if (_findIndex(heap.arr, heap.length, val) >= 0)
del(heap, val)
// get and remove highest priority item from the heap
function dequeue (heap) {
if (heap.length === 0)
return
Heap.insert(heap, { val, priority })
const max = heap.arr[0].item
heap.length--
heap.arr[0] = heap.arr[heap.length]
_downHeap(heap, 0)
return max
}
function dequeue (heap, dequeueHighest=true) {
return Heap.poll(heap, dequeueHighest)
// traverse down the heap from a starting index
//
// heap
// index to start at
function _downHeap (heap, index) {
while (index < heap.length) {
const left = index * 2 + 1
const right = index * 2 + 2
let largest = index
if (left <= heap.length && heap.arr[left].priority > heap.arr[largest].priority)
largest = left
if (right <= heap.length && heap.arr[right].priority > heap.arr[largest].priority)
largest = right
if (largest === index)
return
_swap(heap.arr, index, largest)
index = largest
}
}
function _swap (arr, i, j) {
const tmp = arr[i]
arr[i] = arr[j]
arr[j] = tmp
}
function clear (heap) {

@@ -43,18 +117,36 @@ heap.length = 0

function peek (heap, dequeueHighest=true) {
return Heap.peek(heap, dequeueHighest)
function peek (heap) {
if (!heap.length)
return
return heap.arr[0].item
}
function del (heap, k) {
const ind = _findIndex(heap.arr, heap.length, k)
function del (heap, item) {
const ind = _findIndex(heap, item)
if (ind < 0)
throw new Error('key does not exist!')
throw new Error('key does not exist in priority queue!')
removeItem(heap.arr, heap.length, ind)
const tmp = heap.arr[ind]
heap.arr[ind] = heap.arr[heap.length-1]
heap.arr[heap.length-1] = tmp
if (heap.arr[ind].priority > heap.arr[heap.length-1].priority)
_upHeap(heap, ind)
else if (heap.arr[ind].priority < heap.arr[heap.length-1].priority)
_downHeap(heap, ind)
heap.length--
Heap.callHeapify(heap)
}
function _findIndex (heap, item) {
for (let i=0; i < heap.length; i++)
if (heap.arr[i].item === item)
return i
return -1
}
function list (heap) {

@@ -64,8 +156,5 @@ if (!heap.length)

if (heap.arr[0].priority)
return heap.arr.slice(0, heap.length)
const result = [ ]
for (let i=0; i < heap.length; i++)
result[i] = heap.arr[i].val
result[i] = heap.arr[i].item

@@ -72,0 +161,0 @@ return result

+12
-53
README.md

@@ -5,3 +5,3 @@ # priority-queue

[![Build Status](https://travis-ci.org/mreinstein/priority-queue.svg?branch=main)](https://travis-ci.org/mreinstein/priority-queue)
![tests](https://github.com/mreinstein/priority-queue/actions/workflows/main.yml/badge.svg)

@@ -27,11 +27,6 @@

// declarea a custom function for comparing the priority values of 2 items in the queue
function comparator (a, b) {
return a < b ? true : false
}
// create a new priority queue that can hold a maximum of 20,000 items.
// by default max length is 1000
const MAX_LENGTH = 20000
const obj = PQ.create(comparator, MAX_LENGTH)
const obj = PQ.create(MAX_LENGTH)

@@ -51,17 +46,5 @@

console.log(PQ.dequeue(obj)) // undefined
```
By default dequeue will return the highest prioritied item in the queue first.
If you want to get the lowest priority item instead, pass a 3rd boolean argument:
```javascript
const highest = PQ.dequeue(obj)
GET_HIGHEST = false
const lowest = PQ.dequeue(obj, GET_HIGHEST)
```
## API

@@ -76,28 +59,6 @@

The Item stored in the queue should be class and a comparator should be provided.
### Using classes/objects
### If values in a queue are strings, comparator will receive priorities as a and b in the example below
We need max priority element to be removed first.
```javascript
const comparator = function (a, b) {
return a >= b ? false : true
}
```
An example would be:
```javascript
const obj = PriorityQueue.create(comparator)
PQ.queue(obj, 'c', 1)
PQ.queue(obj, 'b', 3)
PQ.queue(obj, 'a', 5)
console.log(PQ.dequeue(obj)) //'a'
```
### If values in the queue is an object, comparator will receive the object and you need to compare priorities
```javascript
class Box {

@@ -107,21 +68,19 @@ constructor(w, l) {

this.l = l
this.area = w * l //this is priority
this.area = w * l // this is priority
}
comparator(a, b) {
return a.area >= b.area ? false : true
}
}
const obj = PQ.create(Box.prototype.comparator)
const obj = PQ.create()
const a = new Box(5, 5)
const b = new Box(9, 9)
PQ.queue(obj, a)
PQ.queue(obj, new Box(2, 3))
PQ.queue(obj, new Box(3, 3))
PQ.queue(obj, b)
const c = new Box(2, 3)
const d = new Box(3, 3)
PQ.queue(obj, a, a.area)
PQ.queue(obj, c, c.area)
PQ.queue(obj, d, d.area)
PQ.queue(obj, b, b.area)
assert.deepEqual(PQ.dequeue(obj), b)
assert.deepEqual(PQ.dequeue(obj), a)
```
+101
-63
test.js

@@ -5,9 +5,2 @@ import PQ from './priority-queue.js'

// a is parent b is child
// sort in descending order
function comparator (a, b) {
return a < b ? true : false // swap true
}
// used for custom object testing

@@ -20,13 +13,9 @@ class Box {

}
comparator(a, b) {
return a.area >= b.area ? false : true
}
}
describe('test', () => {
describe('test', () => {
it('basic test', () => {
const obj = PQ.create(comparator)
const obj = PQ.create()
PQ.queue(obj, 'd', 1)

@@ -37,6 +26,7 @@ PQ.queue(obj, 'a', 4)

assert.equal(PQ.dequeue(obj).val, 'a')
assert.equal(PQ.dequeue(obj).val, 'b')
assert.equal(PQ.dequeue(obj).val, 'c')
assert.equal(PQ.dequeue(obj).val, 'd')
assert.equal(PQ.dequeue(obj), 'a')
assert.equal(PQ.dequeue(obj), 'b')
assert.equal(PQ.dequeue(obj), 'c')
assert.equal(PQ.dequeue(obj), 'd')
assert.equal(PQ.dequeue(obj), undefined)

@@ -46,9 +36,8 @@ })

it('if queue is empty then dequeue undefined', () => {
const obj = PQ.create(comparator)
const obj = PQ.create()
assert.equal(PQ.dequeue(obj), undefined)
})
it('accepts 0 and negative numbers as valid values', () => {
const obj = PQ.create(comparator)
const obj = PQ.create()

@@ -59,10 +48,9 @@ PQ.queue(obj, -1, 1)

assert.equal(PQ.dequeue(obj).val, 0)
assert.equal(PQ.dequeue(obj).val, -5)
assert.equal(PQ.dequeue(obj).val, -1)
assert.equal(PQ.dequeue(obj), 0)
assert.equal(PQ.dequeue(obj), -5)
assert.equal(PQ.dequeue(obj), -1)
})
it('re-prioritizes an existing element if it is in the queue', () => {
const obj = PQ.create(comparator)
const obj = PQ.create()

@@ -75,16 +63,20 @@ PQ.queue(obj, 'd', 1)

assert.equal(PQ.dequeue(obj).val, 'b')
assert.equal(PQ.dequeue(obj).val, 'a')
assert.equal(PQ.dequeue(obj).val, 'd')
assert.equal(PQ.dequeue(obj), 'b')
assert.equal(PQ.dequeue(obj), 'a')
assert.equal(PQ.dequeue(obj), 'd')
})
it('throw an error if we try to queue with no priority', () => {
const obj = PQ.create()
assert.throws(() => { PQ.queue(obj, '3') }, /^Error/)
})
it('throw an error if we try to delete a key that doesnt exist', () => {
const obj = PQ.create(comparator)
assert.throws(() => { PQ.delete(obj, '3') }, /^Error/) //delete key that doesnt exist
const obj = PQ.create()
assert.throws(() => { PQ.delete(obj, '3') }, /^Error/) // delete key that doesnt exist
})
it('should delete before updating priority', () => {
const obj = PQ.create(comparator)
const obj = PQ.create()
PQ.queue(obj, 'e', 3)

@@ -96,9 +88,10 @@ PQ.queue(obj, 'b', 1)

PQ.queue(obj, 'a', 5)
assert.equal(PQ.dequeue(obj).val, 'a')
assert.equal(PQ.dequeue(obj).val, 'e')
assert.equal(PQ.dequeue(obj).val, 'b')
assert.equal(PQ.dequeue(obj), 'a')
assert.equal(PQ.dequeue(obj), 'e')
assert.equal(PQ.dequeue(obj), 'b')
})
it('check if queue is empty', () => {
const obj = PQ.create(comparator)
const obj = PQ.create()
assert.equal(PQ.isEmpty(obj), true)

@@ -108,3 +101,3 @@ })

it('clear the queue', () => {
const obj = PQ.create(comparator)
const obj = PQ.create()
PQ.queue(obj, 'a', 5)

@@ -117,3 +110,3 @@ assert.equal(PQ.isEmpty(obj), false)

it('list the contents of the queue', () => {
const obj = PQ.create(comparator)
const obj = PQ.create()
PQ.queue(obj, 'c', 1)

@@ -123,19 +116,16 @@ PQ.queue(obj, 'b', 3)

assert.equal(obj.length, 3)
assert.deepEqual(PQ.list(obj).slice(0, 3), [ { val: 'a', priority: 5 },
{ val: 'c', priority: 1 },
{ val: 'b', priority: 3 }])
assert.deepEqual(PQ.list(obj).slice(0, 3), [ 'a', 'c', 'b' ])
})
it('should peek content of queue', () => {
const obj = PQ.create(comparator)
const obj = PQ.create()
PQ.queue(obj, 'c', 1)
PQ.queue(obj, 'b', 3)
assert.deepEqual(PQ.peek(obj), { val:'b', priority: 3 })
assert.deepEqual(PQ.peek(obj), 'b')
})
describe('test with an object', () => {
it('basic test', () => {
const obj = PQ.create(Box.prototype.comparator)
const obj = PQ.create()
const a = new Box(5, 5)

@@ -145,6 +135,6 @@ const b = new Box(2, 3)

const d = new Box(9, 9)
PQ.queue(obj, a)
PQ.queue(obj, b)
PQ.queue(obj, c)
PQ.queue(obj, d)
PQ.queue(obj, a, a.area)
PQ.queue(obj, b, b.area)
PQ.queue(obj, c, c.area)
PQ.queue(obj, d, d.area)

@@ -159,29 +149,33 @@ assert.deepEqual(PQ.peek(obj), d)

it('test peek', () => {
const obj = PQ.create(Box.prototype.comparator)
PQ.queue(obj, new Box(5, 5))
PQ.queue(obj, new Box(9, 9))
const obj = PQ.create()
const a = new Box(5, 5)
const b = new Box(9, 9)
PQ.queue(obj, a, a.area)
PQ.queue(obj, b, b.area)
assert.deepEqual(PQ.peek(obj), new Box(9, 9))
assert.deepEqual(PQ.peek(obj), b)
})
it('throw an error if we try to add a duplicate element in queue', () => {
const obj = PQ.create(comparator)
const obj = PQ.create()
const a = new Box(5, 5)
PQ.queue(obj, a)
PQ.queue(obj, a, a.area)
})
it('throw an error if we try to delete a key that doesnt exist', () => {
const obj = PQ.create(comparator)
const obj = PQ.create()
const a = new Box(15, 5)
PQ.queue(obj, a)
assert.throws(() => { PQ.delete(obj, new Box(15, 51)) }, /^Error/) //delete key that doesnt exist
PQ.queue(obj, a, a.area)
assert.throws(() => { PQ.delete(obj, new Box(15, 51)) }, /^Error/) // delete key that doesnt exist
})
it('should delete before updating priority', () => {
const obj = PQ.create(comparator)
const obj = PQ.create()
const a = new Box(2, 3)
const b = new Box(5, 5)
const c = new Box(3, 3)
PQ.queue(obj, new Box(5, 5))
PQ.queue(obj, a)
PQ.queue(obj, new Box(3, 3))
PQ.queue(obj, b, b.area)
PQ.queue(obj, a, a.area)
PQ.queue(obj, c, c.area)
PQ.delete(obj, a) // so we delete

@@ -191,7 +185,51 @@

PQ.queue(obj, a)
PQ.queue(obj, a, a.area)
assert.deepEqual(PQ.list(obj)[2], a)
})
it('should allow min-heap behavior with negative priority values', () => {
const obj = PQ.create()
// if we want to a min-heap (dequeue min value) we can do this by using negative signed priorities
const negate = (a) => -a
PQ.queue(obj, 'E', negate(0))
PQ.queue(obj, 'A', negate(4))
PQ.queue(obj, 'C', negate(1))
PQ.queue(obj, 'B', negate(2))
PQ.queue(obj, 'D', negate(0.34599))
const output = [ ]
for (let i=0; i < 5; i++)
output.push(PQ.dequeue(obj))
assert.deepEqual(output, [ 'E', 'D', 'C', 'B', 'A' ])
})
// https://github.com/mreinstein/priority-queue/issues/2
it('should respect priority (gh issue #2)', () => {
const obj = PQ.create()
PQ.queue(obj, 'A', 0.9725668889004737)
PQ.queue(obj, 'C', 0.8222610668744892)
PQ.queue(obj, 'J', 0.12049612472765148)
PQ.queue(obj, 'B', 0.8349967401009053)
PQ.queue(obj, 'G', 0.3161299272906035)
PQ.queue(obj, 'F', 0.394229659345001)
PQ.queue(obj, 'D', 0.7465265986975282)
PQ.queue(obj, 'E', 0.6853948319330812)
PQ.queue(obj, 'I', 0.13059667288325727)
PQ.queue(obj, 'H', 0.14856508816592395)
const output = [ ]
for (let i=0; i < 10; i++)
output.push(PQ.dequeue(obj))
assert.deepEqual(output, [ 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J' ])
})
})
})
-5
.travis.yml
sudo: false
language: node_js
node_js:
- '14'
- '12'
-92
heap.js
import removeItem from './remove-array-item.js'
// creates a new heap data structure
function create (comparator, maxLength=1000) {
if (!Number.isInteger(maxLength))
throw new Error('maxLength must be an integer')
const arr = new Array(maxLength)
return { arr, length: 0, maxLength, comparator }
}
function insert (heap, item) {
if (heap.length === heap.maxLength)
return
heap.arr[heap.length] = item
heap.length++
callHeapify(heap)
}
function callHeapify (heap) {
let ind = heap.length - 1
while (ind > 0) {
if (ind % 2 === 0)
ind = (ind - 2) / 2
else
ind = (ind - 1) / 2
heapify(heap, ind)
}
}
function heapify (heap, parentInd) {
let largestInd = parentInd
const leftChildInd = 2 * parentInd + 1
const rightChildInd = 2 * parentInd + 2
// if child exists and is greater than parent
if (heap.length > leftChildInd && heap.comparator(getValue(heap.arr[parentInd]), getValue(heap.arr[leftChildInd])))
largestInd = leftChildInd
if (heap.length > rightChildInd && heap.comparator(getValue(heap.arr[largestInd]), getValue(heap.arr[rightChildInd])))
largestInd = rightChildInd
if (largestInd != parentInd) {
swap(heap, largestInd, parentInd)
heapify(heap, largestInd)
}
}
function poll (heap, dequeueHighest=true) {
if (heap.length === 0)
return
const max = dequeueHighest ? heap.arr[0] : heap.arr[heap.length-1]
if (dequeueHighest)
removeItem(heap.arr, heap.length, 0)
heap.length--
callHeapify(heap)
return max.priority ? max : max.val
}
function peek (heap, dequeueHighest=true) {
if (heap.length === 0)
return
const firstIndex = dequeueHighest ? 0 : heap.length-1
return heap.arr[firstIndex].priority ? heap.arr[firstIndex] : heap.arr[firstIndex].val
}
function getValue (obj) {
return obj.priority ? obj.priority : obj.val // if priority is undefined then return val
}
function swap (heap, i, j) {
const tmp = heap.arr[i]
heap.arr[i] = heap.arr[j]
heap.arr[j] = tmp
}
export default { create, callHeapify, insert, poll, peek }
-13
remove-array-item.js
/**
* Remove 1 item from an array
*
* @function removeItems
* @param {Array<*>} arr The target array
* @param {number} arrLength actual length of the array
* @param {number} removeIdx The index to remove from (inclusive)
*/
export default function removeItem (arr, arrLength, removeIdx) {
const len = arrLength - 1
for (let i = removeIdx; i < len; ++i)
arr[i] = arr[i + 1]
}