Strutture Dati - Priority Queue

Dato che il tempo scorre in fretta inizio subito a postare l'inizio degli esercizi che faremo domani in laboratorio sulle Code a Priorità, precisamente sono due implementazioni di PriorityQueue rispettivamente con lista ordinata, e non ordinata. Preciso che l'elemento c di entrambe le classi è di tipo java.util.Comparator e che l'implementazione di DefaultComparator la trovate sulle slides del prof (lez07). In bocca al lupo per la probabile prova su alberi e tour euleriani di domani a tutti i miei compagni di corso.

public class SortedListPriorityQueue<K,V> implements PriorityQueue<K,V> 

{

protected PositionList<Entry<K,V>> entries;

protected Comparator<K> c;

protected static class MyEntry<K,V> implements Entry<K,V> 

{

protected K k;

protected V v;

public MyEntry(K key, V value) 

{

k = key;

v = value;

}

public K getKey() {return k;}

public V getValue() {return v;}

public String toString() { return "(k:"+k+" v:"+v+")"; }

}

public SortedListPriorityQueue()

{

entries = new NodePositionList<Entry<K,V>>();

c = new DefaultComparator<K>();

}

public SortedListPriorityQueue(Comparator<K> comp)

{

entries = new NodePositionList<Entry<K,V>>();

c = comp;

}

public int size() 

{

return entries.size();

}

public boolean isEmpty() 

{

return (entries.size() == 0);

}

public Entry<K, V> min() throws EmptyPriorityQueueException 

{

Position<Entry<K,V>> min;

if (entries.isEmpty())

throw new EmptyPriorityQueueException();

else

{ 

min = entries.first();

Position<Entry<K,V>> prossimo = min;

for (int i=1; i<entries.size(); i++)

{

prossimo = entries.next(prossimo);

if (c.compare(min.element().getKey(), prossimo.element().getKey()) > 0)

min=prossimo;

}

}

return min.element();

}

public Entry<K, V> insert(K key, V value) throws InvalidKeyException 

{

checkKey(key);

Entry<K,V> entry = new MyEntry<K,V>(key, value);

insertEntry(entry);

return entry;

}

public Entry<K, V> removeMin() throws EmptyPriorityQueueException 

{

if (entries.isEmpty())

throw new EmptyPriorityQueueException();

else

return entries.remove(entries.first());

}

protected boolean checkKey(K key)

{

boolean result;

try 

{

result = (c.compare(key,key)==0);

} 

catch (ClassCastException e)

{ 

throw new InvalidKeyException("Not Comparable Key"); 

}

return result;

}

protected void insertEntry(Entry<K,V> e)

{

if (entries.isEmpty())

entries.addFirst(e);

else if (c.compare(e.getKey(), entries.last().element().getKey())> 0)

entries.addLast(e);

else

{

Position<Entry<K,V>> curr = entries.first();

while (c.compare(e.getKey(), curr.element().getKey())>0)

curr = entries.next(curr);

entries.addBefore(curr, e);

}

}

public String toString()

{

if (isEmpty())

return("Empty PQ");

String s="[ ";

Iterator<Entry<K,V>> it = entries.iterator();

while(it.hasNext())

s += it.next()+" ";

return s+"] size:"+size()+" min:"+min();

}

}

public class UnsortedListPriorityQueue<K,V> implements PriorityQueue<K,V> 

{

protected PositionList<Entry<K,V>> entries;

protected Comparator<K> c;

protected static class MyEntry<K,V> implements Entry<K,V> 

{

protected K k;

protected V v;

public MyEntry(K key, V value) 

{

k = key;

v = value;

}

public K getKey() {return k;}

public V getValue() {return v;}

public String toString() { return "(k:"+k+" v:"+v+")"; }

}

public UnsortedListPriorityQueue()

{

entries = new NodePositionList<Entry<K,V>>();

c = new DefaultComparator<K>();

}

public UnsortedListPriorityQueue(Comparator<K> comp)

{

entries = new NodePositionList<Entry<K,V>>();

c = comp;

}

public int size() 

{

return entries.size();

}

public boolean isEmpty() 

{

return (entries.size() == 0);

}

public Entry<K, V> min() throws EmptyPriorityQueueException 

{

Position<Entry<K,V>> min;

if (entries.isEmpty())

throw new EmptyPriorityQueueException();

else

{ 

min = entries.first();

Position<Entry<K,V>> prossimo = min;

for (int i=1; i<entries.size(); i++)

{

prossimo = entries.next(prossimo);

if (c.compare(min.element().getKey(), prossimo.element().getKey()) > 0)

min=prossimo;

}

}

return min.element();

}

public Entry<K, V> insert(K key, V value) throws InvalidKeyException 

{

checkKey(key);

Entry<K,V> entry = new MyEntry<K,V>(key, value);

entries.addLast(entry);

return entry;

}

public Entry<K, V> removeMin() throws EmptyPriorityQueueException 

{

Position<Entry<K,V>> min;

if (entries.isEmpty())

throw new EmptyPriorityQueueException();

else

{ 

min = entries.first();

Position<Entry<K,V>> prossimo = min;

for (int i=1; i<entries.size(); i++)

{

prossimo = entries.next(prossimo);

if (c.compare(min.element().getKey(), prossimo.element().getKey()) > 0)

min=prossimo;

}

}

return entries.remove(min);

}

protected boolean checkKey(K key)

{

boolean result;

try 

{

result = (c.compare(key,key)==0);

} 

catch (ClassCastException e)

{ 

throw new InvalidKeyException("UnComparable Key"); 

}

return result;

}

public String toString()

{

if (isEmpty())

return("Empty PQ");

String s="[ ";

Iterator<Entry<K,V>> it = entries.iterator();

while(it.hasNext())

s += it.next()+" ";

return s+"] size:"+size()+" min:"+min();

}

}