È possibile aggiungere controlli di sicurezza e cosa no, ma qui è una semplice implementazione utilizzando SortedList
:
class PriorityQueue<T> {
SortedList<Pair<int>, T> _list;
int count;
public PriorityQueue() {
_list = new SortedList<Pair<int>, T>(new PairComparer<int>());
}
public void Enqueue(T item, int priority) {
_list.Add(new Pair<int>(priority, count), item);
count++;
}
public T Dequeue() {
T item = _list[_list.Keys[0]];
_list.RemoveAt(0);
return item;
}
}
sto supponendo che i valori minori di priority
corrispondono agli elementi di priorità superiore (questo è facile da modificare).
Se più thread accedono alla coda, è necessario aggiungere anche un meccanismo di blocco. È facile, ma fammi sapere se hai bisogno di una guida qui.
SortedList
è implementato internamente come un albero binario.
L'implementazione di cui sopra richiede le seguenti classi di supporto. Questo indirizzo di Lasse V. Karlsen commenta che gli oggetti con la stessa priorità non possono essere aggiunti usando l'implementazione naive usando uno SortedList
.
class Pair<T> {
public T First { get; private set; }
public T Second { get; private set; }
public Pair(T first, T second) {
First = first;
Second = second;
}
public override int GetHashCode() {
return First.GetHashCode()^Second.GetHashCode();
}
public override bool Equals(object other) {
Pair<T> pair = other as Pair<T>;
if (pair == null) {
return false;
}
return (this.First.Equals(pair.First) && this.Second.Equals(pair.Second));
}
}
class PairComparer<T> : IComparer<Pair<T>> where T : IComparable {
public int Compare(Pair<T> x, Pair<T> y) {
if (x.First.CompareTo(y.First) < 0) {
return -1;
}
else if (x.First.CompareTo(y.First) > 0) {
return 1;
}
else {
return x.Second.CompareTo(y.Second);
}
}
}
Hai intenzione di chiamarlo da più thread? – sohum
@sohum: No ... il mio programma * è * threaded, ma solo un thread avrà bisogno di accedervi. – mpen
La ragione che viene immediatamente in mente per T che supporta IComparable è che se si inseriscono due elementi nella coda con priorità 2, è comunque necessario confrontare gli articoli e decidere quale ordine elaborare gli elementi prioritari due. . . Quindi alla fine hai bisogno che T sia comparabile. Quindi, come farlo con la tua interfaccia ... Bene, hai alcuni buoni suggerimenti qui sotto. –