Remove by value/reference instead of by comparator?

[fchu]

Hello there,

How should one use this library, if they want to update the priority value of an existing entry? (eg for A* search)? Right now, it looks like one need to remove then add back an entry with the updated priority, the remove() itself uses a comparator to retrieve an entry, which might not work as intended if you have different objects that have shared priorities, for example:

  class Node {
    score: number;
    name: string;
    constructor(score: number, name: string) {
      this.score = score;
      this.name = name;
    }
  }
  const x = new FastPriorityQueue((a: Node, b: Node) => a.score < b.score);
  const a = new Node(10, 'a');
  const b = new Node(10, 'b');
  x.add(a);
  x.add(b);
  console.log(x.array);
  console.log(x.remove(b)); // returns true, even if it actually removed a. also x still has 2 elements representing b
  console.log(x.array);

The removeOne function might be suitable, however it performs as O(n) as it iterates over the underlying array, which is not ideal.

One approach would be to maintain an internal HashMap from entry values/references to their index in this.array, and use that instead to perform the removal. Another one would be to support an update(entry) or a reevaluate() method, so that removal itself becomes unnecessary.

Either way, thank you for this library, it's been very useful!

[lemire]

Thanks.

I am certainly inviting contributions and feature requests but we cannot burden the main implementation with an additional data structure that most users will benefit from.

We could add an additional, distinct, data structure but I am not convinced by the hash table idea.

Could you offer a realistic benchmark?