mourner / flatqueue

A very fast and simple JavaScript priority queue

Hi! I'm Volodymyr Agafonkin.

I'm a software engineer. I created Leaflet, the number one library for interactive web maps, and maintain 40+ other open source projects with a focus on algorithms, computational geometry and data visualization. I'm building the future of maps at Mapbox. Here are a few of my best tech articles: https://agafonkin.com

I'm a musician. I write songs, play guitar and sing in Obiymy Doschu. If you like beautiful, evocative rock music with lush string arrangements, check out our last album.

I'm a father to beautiful 9-year-old twin girls, I'm happily married and live in Kyiv, Ukraine. I love baking, photography, strength training, martial arts, reading sci-fi and fantasy, and exploring quiet parks. You can find tidbits of my life on X (Twitter), Instagram and Facebook.

flatqueue's Issues

Improve documentation and naming of arguments

I tried using FlatQueue but accidentally mixed up id and value parameters.

I was under the impression that id would be some order-index, whereas value would be the actual data associated with that element. However, in reality it's the other way around.
The naming of the id parameter is what led to this confusion.

Before I understood the issue, I even wrote a wrapper because I wanted to pop the data associated with the element (instead of the order-index), because I thought FlatQueue only allowed popping the order-index.
The naming of the peek() / peekValue() functions made my confusion worse.

Even when I understood this, it also wasn't clear to me wether the order-index (value parameter) had to be an integer, or wether it could also be a rational number. It was also unclear wether the order-index could be negative.
And lastly, it also wasn't clear what happens if the same order-index is used multiple times.

It's also not clear how people should check for items in the queue: while(flatqueue.length > 0) or while(flatqueue.peekValue() !== undefined); for API stability, this should probably be documented.

Publish version with typescript types to npm

It's great that there are TypeScript types, but they currently don't exist in the npm version. Could a new version including them be pushed?

Shrink internal arrays

Currently, once a FlatQueue was filled, it will use a considerable amount of memory, even when the queue is less full (even after a clear).

That happens because the FlatQueue itself will only use this.length to track the size of the queue, but the ids and values arrays will never be shrunk again (to match the current this.length).

There should be a way to trigger a cleanup of the queue, or it should clean up after itself using some heuristic.

Add support for updating priority of entry

Since I'm trying to implement Dijkstra's algorithm, I want to be able to update the priority of an already existing entry in the queue.

Typescript not happy with the advice from README

Trying to take this advice in the README: https://github.com/mourner/flatqueue#using-typed-arrays

But Typescript is not happy:

I am using flatqueue v2.0.3.

What am I doing wrong here?

Add support for Node.js require

Add support for being able to use require instead of import.

This is useful when working with Node.js and you for some reason can't use ES modules

Popped items can't be garbage collected

Hi!
I noticed that you only reduce this.length in pop() and clear(), but don't actually update ids. That means if I store large objects (e.g. DOM nodes) in the queue, they might not get garbage collected even if my code has no other references to them.
I don't know what the performance impact would be to always shrink ids. In any case, it should be safe to assign undefined to the unused indexes.