Vixen
02b45cc4

IndexedPriorityQueue

class Core/Vixen.Core.Collections/IndexedPriorityQueue.cs:27
csharp
public sealed class IndexedPriorityQueue<TPriority> where TPriority : IComparable<TPriority>

A min-heap keyed by a caller-supplied integer id, which can therefore find an entry it has already queued and change its priority.

No guide page documents this yet — the page shows what the code says about itself.

Remarks

The BCL's PriorityQueue cannot do this. Once an element is in it there is no way to reach it again, so the usual workaround is to enqueue a second copy at the new priority and skip the stale one on the way out — which unbounds the queue and makes Count a lie. That matters for the three places this exists for: a job graph whose successors become ready as dependencies complete, animation events being rescheduled, and a timeline being scrubbed.

An id maps to a heap position through a flat array, so ids should be dense and small — they are indices into whatever the caller already has, not arbitrary keys.

Fields and properties (3)

  • public int Count

    How many entries are queued.

  • public bool IsEmpty

    Whether the queue is empty.

  • public int IdCapacity

    The largest id the queue currently has room for, plus one.

Methods (9)

  • public IndexedPriorityQueue(int idCapacity = 64, int capacity = 16)

    Creates a queue sized for a given id range and entry count.

  • public bool Contains(int id)

    Whether an id is queued.

  • public void Enqueue(int id, TPriority priority)

    Queues an id at a priority.

  • public void SetPriority(int id, TPriority priority)

    Queues an id, or moves it if it is already queued.

  • public bool TryDecreasePriority(int id, TPriority priority)

    Lowers an id's priority, ignoring the call if the new value is not an improvement.

  • public bool TryPeek(out int id, out TPriority priority)

    Reads the lowest-priority entry without removing it.

  • public bool TryDequeue(out int id, out TPriority priority)

    Removes and returns the lowest-priority entry.

  • public bool Remove(int id)

    Removes an id wherever it sits in the queue.

  • public void Clear()

    Empties the queue, keeping the buffers.

Used by (2)

  • CollectionTestsVixen.Core.Collections.Tests
  • NavMeshQueryVixen.Navigation