Ho seguito le istruzioni fornite in this question (la risposta di Jason) per scrivere il mio PriorityQueue<T> utilizzando un SortedList. Comprendo che il campo count all'interno di questa classe viene utilizzato per garantire priorità univoche e per mantenere l'ordine dell'accodamento tra la stessa priorità.Modificare la priorità in una coda di priorità personalizzata
Tuttavia, quando count raggiunge il valore massimo e I somma 1 ad esso, quest'ultimo ricomincia da 0, quindi la priorità delle voci successive sarà superiore alla priorità delle voci precedenti. Usando questo approccio avevo bisogno di un modo per "sicuro" azzerare il contatore count ... Infatti, supponiamo di avere il seguente stato della coda (nella priorità formato | contare | voce):
0 | 123 | A
0 | 345 | B
1 | 234 | C
2 | 200 | D
Ora supponiamo che il limite del contatore sia stato raggiunto, quindi devo resettarlo a 0: di conseguenza, il prossimo elemento inserito avrà il contatore 0: ad esempio, se inserisco un elemento con priorità uguale a 1, esso sarà inserito erroneamente prima 1 | 234 | D
0 | 123 | A
0 | 345 | B
1 | 000 | nuovo elemento
1 | 234 | C
2 | 200 | D
Il problema della priorità può essere risolto implementando un mucchio: ho creato una classe Heap, poi ho usato Heap<KeyValuePair<TPriority, TElement> e personalizzato PriorityComparer al fine di risolvere gli elementi da TPriority. Dato TPriority come int e TElement come string, il PriorityComparer è la seguente:
public class MyComparer : IComparer<KeyValuePair<int, string>>
{
public int Compare(KeyValuePair<int, string> x, KeyValuePair<int, string> y)
{
return x.Key.CompareTo(y.Key);
}
}
...
int capacity = 10;
Heap<KeyValuePair<int, string>> queue;
queue = new Heap<KeyValuePair<int, string>>(capacity, new PriorityComparer());
...
UPDATE In questo modo (usando il PriorityComparer), sono riuscito ad implementare una coda di priorità. Ora vorrei aggiungere supporto per modificare il suo comportamento in fase di esecuzione, ovvero passare da FIFO a ordinamento prioritario e viceversa. Dal momento che la mia implementazione di coda con priorità ha un campo IComparer, penso che è sufficiente aggiungere una proprietà Comparer per modificare questo campo, come la seguente:
public IComparer
{
set
{
this._comparer = value;
}
}
Nel frattempo ho pensato di adottare un approccio diverso: invece di usare un heap binario per gestire le priorità, potrei avvolgere code diverse (ogni coda si riferisce a una determinata priorità) come segue.
public class PriorityQueue<T, int>
{
private Queue<T> _defaultQueue;
private bool _priority;
private SortedList<int, Queue<T>> _priorityQueues;
public PriorityQueue(int capacity)
{
this._defaultQueue = new Queue<T>(capacity);
this._priority = false;
this._priorityQueues = new SortedList<int, Queue<T>>(0);
}
public void PriorityEnable()
{
this._priority = true;
}
public void PriorityDisable()
{
this._priority = false;
}
public void Enqueue(T item)
{
if (this._priority)
{
// enqueue to one of the queues
// with associated priority
// ...
}
else this._defaultQueue.Enqueue(item);
}
public T Dequeue()
{
if (this._priority)
{
// dequeue from one of the queues
// with associated priority and
// return
// ...
}
return this._defaultQueue.Dequeue();
}
}
- Come gestire la transizione da FIFO modalità-modalità priorità quando ci sono ancora elementi nella coda di default? Potrei copiarli nelle code di priorità in base alla priorità dell'oggetto ... Altre soluzioni migliori?
- Come gestire la transizione dalla modalità priorità a Modalità FIFO? In questo caso, avrei diverse code di priorità, che possono contenere elementi, ma non devono più gestirle in base alla priorità e nemmeno conoscere l'ordine di arrivo originale ...
- Come posso gestire la capacità dei diversi code?
- E le prestazioni delle suddette due soluzioni? Quale usa più memoria?
La mia risposta è di qualche aiuto per il tuo problema? – JeremyK