Last active
February 17, 2025 14:43
-
-
Save adammyhre/d896df0cf20e4e10672483b7f3200d87 to your computer and use it in GitHub Desktop.
Double Key Priority Queue for Unity C#
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections.Generic; | |
using UnityUtils; | |
public class PriorityQueue<T> { | |
class KeyNodeComparer : IComparer<(Key, T)> { | |
public int Compare((Key, T) x, (Key, T) y) { | |
return x.Item1 < y.Item1 ? -1 : x.Item1 > y.Item1 ? 1 : 0; | |
} | |
} | |
readonly SortedSet<(Key, T)> set = new(new KeyNodeComparer()); | |
readonly Dictionary<T, Key> lookups = new(); | |
public int Count => set.Count; | |
public (Key, T) Min => set.Min; | |
public void Add((Key, T) item) { | |
set.Add(item); | |
lookups[item.Item2] = item.Item1; | |
} | |
public void Remove(T item) { | |
set.Remove((lookups[item], item)); | |
lookups.Remove(item); | |
} | |
public bool ContainsKey(T item) => lookups.ContainsKey(item); | |
public bool Contains((Key, T) item) => set.Contains(item); | |
public void Clear() => set.Clear(); | |
} | |
public readonly struct Key { | |
public readonly float k1; | |
readonly float k2; | |
public Key(float k1, float k2) { | |
this.k1 = k1; | |
this.k2 = k2; | |
} | |
public static bool operator <(Key a, Key b) => a.k1 < b.k1 || a.k1.Approx(b.k1) && a.k2 < b.k2; | |
public static bool operator >(Key a, Key b) => a.k1 > b.k1 || a.k1.Approx(b.k1) && a.k2 > b.k2; | |
public static bool operator ==(Key a, Key b) => a.k1.Approx(b.k1) && a.k2.Approx(b.k2); | |
public static bool operator !=(Key a, Key b) => !(a == b); | |
public override bool Equals(object obj) => obj is Key key && this == key; | |
public override int GetHashCode() => HashCode.Combine(k1, k2); | |
public override string ToString() => $"({k1}, {k2})"; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment