(JAVA) Raddoppio e dimezzamento array

[aduri]

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;
}

[leox@mitoalfaromeo]

dove è definito s_size?

[aduri]

Nella dispensa il prof dice che il nuovo campo s_size memorizza la dimensione iniziale della coda, quindi e' inizializzato nel costruttore.

[PGI-Bis]

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]

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..

[aduri]

Grazie e.... crepi il lupo.