Public class Q implements CQueue,Comparable<Q>
{
private static final int INITIAL_DIM = 1;
private Comparable[] v;
private int front;
private int back;
/**
Inizializza una coda vuota
*/
public Q()
{ v = new Comparable[INITIAL_DIM];
front = back = 0;
}
/**
@return numero di elementi nel contenitore
*/
public int size()
{ return (back - front + v.length) % v.length;
}
/**
@return true se il contenitore e' vuoto, false altrimenti
*/
public boolean isEmpty()
{ return front == back;
}
/**
accoda un elemento
Complessita' temporale: O(1) con analisi ammortizzata
@param x elemento da accodare
*/
public void enqueue(Comparable x)
{ if (increment(back) == front)
{ Comparable[] a = new Comparable[2 * v.length];
System.arraycopy(v, front, a, 0, v.length - front);
System.arraycopy(v, 0, a, v.length - front, back);
front = 0;
back = size();
v = a;
}
v[back] = x;
back = increment(back);
}
/**
ispezione, estraendolo, l'elemento in fronte alla coda
Complessita' temporale: O(1)
@return elemento in fronte alla coda
@throw EmptyQueueException se la coda e' vuota
*/
public Object dequeue() throws EmptyQueueException
{
Object x = v[front];
v[front] = null;
front = increment(front);
return x;
}
/**
restituisce la descrizione testuale della coda, un elemento per riga, in
sequenza FIFO, in modo che il primo elemento sia l'elemento in testa alla
coda
Complessita' temporale: O(n)
@return descrizione testuale
*/
public String toString()
{ Comparable[] a = toArray();
String str = "";
for (int i = 0; i < a.length; i++)
str = str + a + "\n";
return str;
}
/**
restituisce gli elementi comparabili della coda in un array ordinato in
senso crescente, secondo il loro ordine naturale
Complessita' temporale: O(n logn)
@return array ordinato contenente gli elementi comoparabili della coda
*/
public Comparable[] toSortedArray()
{ Comparable[] a = toArray();
mergesort(a);
return a;
}
/*
incremento di indice circolare
*/
private int increment(int k)
{ return (k + 1) % v.length;
}
/*
restituisce in un array gli elementi comparabili della coda in sequenza
FIFO, in modo che all'indice zero ci sia il fronte della coda
*/
private Comparable[] toArray()
{ Comparable[] a = new Comparable[size()];
int i = 0;
int j = front;
while (i < a.length)
{ a = v[j];
i++;
j = increment(j);
}
return a;
}
public int compareTo(Q obj)
{if(size()<obj.size()) return -1;
if(size()>obj.size()) return 1;
return 0;}
/*
ordinamento per fusione
*/
private static void mergesort(Comparable[] a)
{ if (a.length < 2)
return;
int mid = a.length / 2;
Comparable[] left = new Comparable[mid];
Comparable[] right = new Comparable[a.length - mid];
System.arraycopy(a, 0, left, 0, mid);
System.arraycopy(a, mid, right, 0, a.length - mid);
mergesort(left);
mergesort(right);
merge(a, left, right);
}
/*
fusione
*/
private static void merge(Comparable[] a, Comparable[] b, Comparable[] c)
{ int ia = 0, ib = 0, ic = 0;
while (ib < b.length && ic < c.length)
if (b[ib].compareTo(c[ic]) < 0)
a[ia++] = b[ib++];
else
a[ia++] = c[ic++];
while (ib < b.length)
a[ia++] = b[ib++];
while (ic < c.length)
a[ia++] = c[ic++];
}
}
interface CQueue
{
/**
@return true se il contenitore e' vuoto, false altrimenti
*/
boolean isEmpty();
/**
@return numero di elementi nel contenitore
*/
int size();
/**
accoda un elemento
@param x elemento da accodare
*/
void enqueue(Comparable x);
/**
ispezione, estraendolo, l'elemento in fronte alla coda
estae un elemento
@return elemento in fronte alla coda
@throw EmptyQueueException se la coda e' vuota
*/
Object dequeue() throws EmptyQueueException;
}