Salve a tutti sto cercando di analizzare questo codice sulla gestione degli array circolari.
Nel caso in cui isFull() e' true cioe' l'array e' pieno si raddoppia la dimensione dell'array e viceversa se
gli elementi dell'array si riducono oltre la meta' della dimensione originale si deve dimezzare.
Non mi e' chiara l'implementazione di quest'ultimo metodo.
In particolare:
if (( elem<size/4) && (elem>=s_size/4))
Purtroppo non ho modo (lavorando) di avere chiarimenti dal prof e mercoledi' ho l'esame qualcuno, cortesemente, puo' darmi una dritta?
allego gli stralci di codice dalle dispense:
Grazie.
public void enqueue(Object el) {
if (isFull())
doubleQueue();
protected void doubleQueue(){
Object[] newdata = new Object[2*size];
for(int i=first, j=0; j<size; j++, i++,i=i%size){
newdata[j] = data[i];
}
first=0;
last=size-1;
size=2*size;
data=newdata;
}
public Object dequeue() {
int elem;
if (first<=last)
elem=last-first+1;
else
elem=size-first+last+1;
if (( elem<size/4) && (elem>=s_size/4))
halfQueue(elem);
…
protected void halfQueue(int elem){
Object[] newdata = new Object[size/2];
for(int i=first, j=0; j<elem; j++,
i++,i=i%size ){
newdata[j] = data[i];
}
first=0;
last=elem-1;
size=size/2;
data=newdata;
}
Nella dispensa il prof dice che il nuovo campo s_size memorizza la dimensione iniziale della coda, quindi e' inizializzato nel costruttore. :confused:
Non ho certo l'autorevolezza e probabilmente neppure la competenza per criticare quel codice ma non mi stupisce che si possano avere delle difficoltà a comprendere perchè funzioni. Se il Lombroso fosse stato programmatore avrebbe certamente detto che questo:
for(int i=first, j=0; j<size; j++, i++,i=i%size)
è il segnale di una recondita pericolosità sociale. Non riesco francamente a capire il perchè di quel /4. Ci vuole anche parecchia fantasia a capire cosa sia elem.
Posso darti una versione che a me appare più comprensibile della faccenda coda, realizzata con un array, trattato come un anello per garantire una complessità costante all'inserimento e all'estrazione. E' possibile che questo ti aiuti a comprendere il significato del codice che hai.
public class ArrayQueue {
/* Array degli elementi */
private Object[] array;
/* Dimensione originale dell'array */
private int dimensioneOriginale;
/* Numero totale di elementi nella coda, può essere minore
del numero totale di spazi disponibili nell'array */
private int numeroTotaleElementi;
/* Se il numero totale di elementi nella coda è maggiore di
zero allora il componente array[indiceDiEstrazione] è quello
che deve essere restituito come risposta ad una richiesta
dequeue() */
private int indiceDiEstrazione;
/* L'elemento accodato con l'invocazione di enqueue(e) finisce
nell'array in posizione indiceDiInserimento (array[indiceDiInserimento]) */
private int indiceDiInserimento;
/** Crea un ArrayQueue con un numero iniziale di celle
disponibili pari a dimensioneIniziale. */
public ArrayQueue(int dimensioneIniziale) {
array = new Object[dimensioneIniziale];
dimensioneOriginale = dimensioneIniziale;
}
/** Accoda l'oggetto o */
public void enqueue(Object o) {
/* poichè indiceDiInserimento tiene traccia della
posizione in cui deve essere inserito un nuovo
elemento, l'assegnamento seguente coincide con
l'accodamento */
array[indiceDiInserimento] = o;
/* dopo aver accodato l'elemento, ArrayQueue
aumenta di uno il numero dei componenti che
contiene (è stato aggiunto un elemento) e
"sposta avanti di uno" l'indice della cella in
cui dovrà essere inserito un nuovo elemento... */
incrementaDimensioneECalcolaIndiceDiInserimento();
}
/* Estrae un valore dalla coda o null se la coda sia vuota */
public Object dequeue() {
Object valore = null;
/* Se la coda ha almento un elemento... altrimenti non
c'è un bel null da restituire */
if(numeroTotaleElementi > 0) {
/* Be', avendo stabilito che se la coda non è vuota
indiceDiEstrazione punta sempre alla cella che contiene
l'elemento da estrarre, valore è chiaramente... */
valore = array[indiceDiEstrazione];
/* Questo è superfluo e si può togliere ma aiuta
a visualizzare il contenuto della coda che si modifica
quando si usi il metodo dump() */
array[indiceDiEstrazione] = null;
/* Ha tolto un elemento dalla coda: a questo punto
deve stabilire quale sia il prossimo elemento da
restituire, nel caso di un nuovo dequeue(). Certamente
la coda ha un elmento in meno (decrementaDimensioneE...) */
decrementaDimensioneECalcolaIndiceDiEstrazione();
}
return valore;
}
/** true se la coda è zeppa */
private boolean èPiena() {
/* la coda è piena se il numero totale di elementi, che è
aumentato o diminuito ad ogni inserimento o estrazione, è
pari al numero di componenti dell'array */
return numeroTotaleElementi == array.length;
}
/** Stampa su System.out il contenuto delle celle dell'array
su cui si basa questa coda, l'indice di inserimento (la cella
che sarà occupata in caso di nuovo enqueue), l'indice di
estrazione (la cella che sarà svuotata in caso di nuovo dequeue)
e il numero totale di elementi contenuti nella coda */
public void dump() {
System.out.println("Indice di estrazione: " + indiceDiEstrazione);
System.out.println("IndiceDiInserimento: " + indiceDiInserimento);
System.out.println("Numero totale di elementi: " + numeroTotaleElementi);
for(int i = 0; i < array.length; i++) {
System.out.println(i+": "+array[i]);
}
}
/** E' stato tolto un elemento dalla coda. Questo metodo diminuisce di uno
il numero di elementi contenuti nella coda e calcola il prossimo indice
di estrazione per un futuro dequeue */
private void decrementaDimensioneECalcolaIndiceDiEstrazione() {
/* Nella coda c'è un elemento in meno */
numeroTotaleElementi--;
/* Gli elementi vengono estratti a partire dalla testa. L'indice
del prossimo elemento da rimuovere è quello della cella che succede
al vecchio indice di estrazione (si va dalla testa alla coda) */
indiceDiEstrazione++;
/* Se l'indice di estrazione così calcolato risulta essere pari
al numero di componente dell'array allora questo indice è un po'
troppo in là. Poichè trattiamo l'array come un anello, il prossimo
indice di estrazione diventa zero (abbia fatto un giro) */
if(indiceDiEstrazione == array.length) {
indiceDiEstrazione = 0;
}
/* Abbiamo tolto un elementi. Il numero di elementi rimasti è abbastanza
basso da giustificare un dimezzamento delle dimensioni dell'array? Si se:
il numero totale di elementi è meno della metà delle dimensioni dell'array.
Commentata c'è una condizione ulteriore il cui scopo ideale sarebbe quello
non dimezzare la coda a meno della dimensione originariamente imposta. Senza
quella condizione, nel caso di estrazione, l'array è ridotto fino ad assumere
una dimensione pari a uno nel caso in cui non ci siano elementi nella coda */
if(numeroTotaleElementi < array.length / 2 /*&& array.length > dimensioneOriginale*/) {
dimezzaArray();
}
}
/* Riduce le dimensione dell'array a metà di quelle attuali */
private void dimezzaArray() {
/* Crea un array di dimensioni pari alla metà di quello
corrente */
Object[] arrayDimezzato = new Object[array.length / 2];
/* copia il contenuto della coda in arrayDimezzato */
copiaContenutoCoda(arrayDimezzato);
/* arrayDimezzato sostituisce il vecchio array */
array = arrayDimezzato;
/* poichè il contenuto della coda è stato infilato in
arrayDimezzato a partire dall'indice zero, il nuovo
indice del primo elemento della coda è zero. */
indiceDiEstrazione = 0;
/* L'indice della prima cella libera è pari a
numeroTotaleElementi perchè il numero di elementi copiati
in arrayDimezzato è numeroTotaleElementi - 1 */
indiceDiInserimento = numeroTotaleElementi;
}
/** Aumenta di uno il numero totale di elementi contenuti nella
coda e sposta avanti di una cella il punto in cui dovrà essere
accodato un nuovo elemento */
private void incrementaDimensioneECalcolaIndiceDiInserimento() {
/* nella coda c'è un elemento in più...*/
numeroTotaleElementi++;
/* prima dell'invocazione di questo metodo è stato
inserito un nuovo elemento. Il vecchio indice di inserimento
non è più valido (c'è stato buttato dentro un elemento):
incrementa l'indice di inserimento in modo tale che un
nuovo accodamento avvenga nella cella successiva a quella
appena riempita */
indiceDiInserimento++;
/* se l'array è pieno allora lo raddoppia */
if(èPiena()) {
raddoppiaArray();
}
/* se l'indice di inserimento è uguale al numero di componenti
che possono essere infilati nell'array, allora, trattando
l'array come un anello, l'indice della prossima cella
libera è zero */
if(indiceDiInserimento == array.length) {
indiceDiInserimento = 0;
}
}
/* Raddoppia le dimensioni di array */
private void raddoppiaArray() {
/* Crea un array che possa ricevere il doppio di componenti
di quello attualmente usato */
Object[] arrayRaddoppiato = new Object[array.length * 2];
/* copia il contenuto della coda in arrayRaddoppiato */
copiaContenutoCoda(arrayRaddoppiato);
/* il "vecchio array" diventa il "nuovo e più grosso" arrayRaddoppiato */
array = arrayRaddoppiato;
/* Avendo copiato in arrayRaddoppiato tutti gli elementi della coda,
destinandoli in successione dalla cella zero alla cella numeroTotaleElementi - 1,
l'indice di estrazione, cioè il primo elemento della coda, è zero...*/
indiceDiEstrazione = 0;
/* e la prima posizione libera è pari al numeroTotaleElementi che, per
il vecchio array, era anche il primo indice che sforava la dimensione
massima ma, per il nuovo, è un indice perfettamente valido */
indiceDiInserimento = numeroTotaleElementi;
}
/* Copia in destinazione il contenuto della coda. L'array
destinazione è riempito a partire dalla cella zero fino
a quante celle è necessario siano riempite (numeroTotaleElementi - 1)
con gli elementi della coda, dal primo (indiceDiEstrazione)
all'ultimo (indiceDiInserimento - 1) */
private void copiaContenutoCoda(Object[] destinazione) {
/* La copia riempie le celle di destinazione da zero a
numeroTotaleElementi - 1. I valori da copiare partono da
indiceDiEstrazione (primo elemento della coda) e
arrivano... fin dove arrivano. Tanto sappiamo quanti
sono. */
int indiceDiCopia = indiceDiEstrazione;
/* Copia da array ad destinazione un numero di elementi
pari al numero di elementi contenuti nella coda */
for(int i = 0; i < numeroTotaleElementi; i++) {
destinazione[i] = array[indiceDiCopia];
indiceDiCopia++; //il prossimo elemento nella coda
if(indiceDiCopia == array.length) {
/* Se risulta che il prossimo elemento va oltre
la capacità di array allora, trattando array come
un anello, il prossimo elemento è quello in posizione
zero */
indiceDiCopia = 0;
}
}
}
}
Un "Main espresso" per "vedere le cose in funzione":
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) {
ArrayQueue q;
try {
q = new ArrayQueue(Integer.parseInt(args[0]));
} catch(Throwable t) {
System.out.println("Uso: java Main numeroIntero");
System.out.println("Il numero intero indica la dimensione iniziale della coda");
System.out.println("Esempio: java Main 10");
return;
}
System.out.println("e = enqueue(new Date())");
System.out.println("d = dequeue()");
System.out.println("p = dump()");
System.out.println("quit = exit");
System.out.println("Esempio: eep, due enqueue seguiti da un dump");
System.out.println("Esempio: dpep, un dequeue, un dump, un enqueue, un dump");
System.out.println("Buon divertimento (quit e invio per uscire)");
Scanner in = new Scanner(System.in);
String line;
while(!(line = in.nextLine()).equals("quit")) {
for(int i = 0; i < line.length(); i++) {
char c = line.charAt(i);
if(c == 'e') {
q.enqueue(new Date());
} else if(c == 'd') {
q.dequeue();
} else if(c == 'p') {
System.out.println();
q.dump();
System.out.println();
}
}
}
}
}
In bocca al lupo.
leox@mitoalfaromeo
06-11-2006, 21:59
boh: controlla che siano meno di size/4 perchè in tal modo saranno meno della metà del nuovo vettore creato.
contemporaneamente devono essere più di un quarto del vettore originale...
forse è un modo per evitare di dividere a metà più di una volta la dimensione del vett originale...
@pgi elem è il numero di elementi attuali. in un vettore circolare o sono compresi tra il primo e l'ultimo o sono da 0 a last e da first a .length(), da cui quelle formulette..
Grazie e.... crepi il lupo.
vBulletin® v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.