basarat / basarat/typescript-collections

A priority queue should guarantee order

Open
#129 1 comment 0 reactions 0 assignees View on GitHub
Dominant language
TypeScript
Stars
1.2k
Forks
153
PR merge metrics
No merged PRs in 30d

Description

`PriorityQueue` doesn't seem to guarantee order:

```ts
import { PriorityQueue } from 'typescript-collections';

interface Obj {
prio: number;
id: string;
}

const q = new PriorityQueue((a: Obj, b: Obj) => a.prio - b.prio);

q.enqueue({ prio: 0, id: 'first' });
q.enqueue({ prio: 10, id: 'prio' });
q.enqueue({ prio: 0, id: 'another 1' });
q.enqueue({ prio: 0, id: 'another 2' });
q.enqueue({ prio: 0, id: 'last' });

let o: Obj | undefined;
while (o = q.dequeue()) {
console.log(o.id);
}
```

outputs:

```
prio
last
another 2
another 1
first
```

(in this example the order is perfectly reversed but this won't be the case if `enqueue`/`dequeue` are interleaved)

Contributor guide

No contributing guide indexed for this repository

Research direction

Start at the PriorityQueue implementation and reproduce the TypeScript example from the issue. Inspect how equal-priority entries are stored and removed, then check whether the existing tests cover their ordering. Done means the queue's ordering for equal-priority items matches the project's intended guarantee and the reported reproduction is covered by a test.

Written by the indexing model from the issue text.

Assessment

Tech stack
typescript
Domain
data
Issue type
Bug
Difficulty
3/5
Estimated time
1-2 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.