[JAVA] Dizionario ordinato su skipList a 2 riferimenti

Condivisione e sviluppo di conoscenze sulle alternative a Microsoft

Moderatore: Moderatori

Avatar utente
EvolutionCrazy
Amministratore
Amministratore
Messaggi: 4462
behance Kuchnie Warszawa
Iscritto il: 23 apr 2003 02:00
Contatta:

[JAVA] Dizionario ordinato su skipList a 2 riferimenti

Messaggio da EvolutionCrazy »

Visto che qualche mese fa quando ho dovuto farlo per l'università (universitò di Padova, corso di Dati e Algoritmi) sul web non ho trovato nulla di già pronto ora lo pubblico fatto :wink:

Il codice l'ho scritto io, io ne sono il proprietario e lo diffondo come voglio :P

Qui il link per il download del pacchetto completo di sorgenti e relazione:
http://evcz.hwtweakers.net/varie/proget ... oritmi.zip

Codice: Seleziona tutto

Progetto N° 9 (Dizionario Ordinato su skipList a 2 riferimenti)

***********************************************
Linee generali di utilizzo:
Il dizionario è strutturato in modo da accettare oggetti Comparable come chiavi e qualsiasi oggetto Object come "valore"

Gli oggetti restituiti dalle varie funzioni possono essere di tipo Iteratore ed Entry
Le funzionalità di questi oggetti saranno descritte in seguito.

!!! NOTE sul JDK usato/consigliato !!!
Se si compila usando il JDK 1.5.x (java5) si ottiene un warning (dovuto al fatto che java5 usa compareTo con i generics e non come oggetti Comparable che venivano usati fino all’1.4), la compilazione va comunque a buon fine e i class ottenuti sono comunque funzionanti. Per evitare tale warning basta compilare usando il parametro –nowarn)
L’uso del jdk1.4 o precedente produce comunque un applicazione funzionante, ma a livello prestazione risulta di gran lunga più lenta rispetto alla versione compilata ed eseguita su java5.
E’ quindi altamente consigliato (se si è interessati alle prestazioni e ai tempi di esecuzione) l’uso di un jdk della seria 1.5.x !!!

***********************************************
Classe principale: DizionarioOrdinato
***********************************************
	DizionarioOrdinato(Comparable key_min, Comparable key_max)
Questo è il costruttore del dizionario…
min_key e max_key sono le due chiavi sentinella che l’utilizzatore deve inserire in fase di creazione del dizionario; rispettivamente rappresentano –infinito e +infinito
Le chiavi sentinella devono essere oggetti dello stesso tipo delle chiavi che verranno utilizzate nel dizionario.
Nella classe di Prova come chiavi sentinella ho usato il carattere unicode più piccolo e una sequenza del carattere unicode più grande come estremi (tale scelta è dovuta al fatto che tale prova è stata fatta usando oggetti String che java tratta come unicode)

	boolean isEmpty()
restituisce true se il dizionario è vuoto

	int size()
restituisce un intero che rappresenta il numero di definizioni presenti nel dizionario

	Entry find(Comparable key)
Restituisce una Entry del tipo (Comparable key, Object value) contenente chiave e una definizione della chiave ricercata
Restituisce null se la chiave cercata non è presente del dizionario

	Iteratore findAll(Comparable key)
restituisce un Iteratore per scorrere tutte le definizioni associate alla chiave
oppure se la chiave non esiste restituisce null

	Entry insert(Comparable key, Object content)
Inserisce chiave e oggetto associato nel dizionario restituendi l’entry
restituisce null se l’inserimento fallisce (si è tentato di inserire una chiave che esce dal range key_min – key_max)

	Iteratore entries()
restituisce un oggetto Iteratore che punta alla chiave più piccola e con il quale si può scorrere l’intero dizionario

	Iteratore predecessors(Comparable key)
restituisce un oggetto Iteratore che punta alla chiave minore o uguale a quella passata e con il quale si può scorrere il dizionario in ordine decrescente

	Iteratore successors(Comparable key)
restituisce un oggetto Iteratore che punta alla maggiore minore o uguale a quella passata e con il quale si può scorrere il dizionario in ordine crescente

	Entry first()
Restituisce una Entry contenente la chiave più piccola presente nel dizionario e una definizione associata a tale chiave.
Restituisce null se il dizionario è vuoto.

	Entry last()
Restituisce una Entry contenente la chiave più grande presente nel dizionario e una definizione associata a tale chiave.
Restituisce null se il dizionario è vuoto.

	Entry remove (Entry entry)
Rimuove dal dizionario l’Entry passata restituendo l’Entry.
Se la rimozione fallisce(Entry non esistente nel dizionario) restituisce null

***********************************************
Classe Entry
***********************************************

E' un oggetto con due campi (ad accesso amichevole per massimizzare le prestazioni)

	Comparable key
Contiene la chiave

	Object value
Contiene il riferimento all'oggetto associato alla chiave

L’accesso amichevole permette all’utente la modifica dell’oggetto… per me come è concepito il dizionario tale azione non è assolutamente un problema in quanto l’oggetto Entry viene creato ogni volta da 0 e non viene mai riusato… anche se l’utente lo distrugge/altera al dizionario non succede nulla ;)


***********************************************
Classe Iteratore
***********************************************

L'iteratore è un oggetto che si posiziona esattamente sopra le Entry e permette di scorrerle e di ottenerne il contenuto, a seconda che l’Iteratore sia stato creato con predecessors() o successors() il verso di percorrenza delle chiavi sarà rispettivamente decrescente o crescente (se l’Iteratore viene creato con entries() il verso di percorrenza sarà crescente, se l’Iteratore viene creato con un findAll() non c’è alcun verso: le definizioni vengono lette così come sono memorizzate nella ValuesList di supporto)

	boolean hasNext()
restituisce true se c'è una posizione successiva a quella attuale

	boolean next()
sposta l'iteratore sulla posizione successiva
restituisce null se lo spostamento fallisce (per esempio quando non ci sono più posizioni successive)

	Entry getdata ()
restituisce un Entry contenente chiave e valore corrispondenti alla posizione attuale in cui si trova l’iteratore


Esempio di utilizzo di un Iteratore:

String key = "0chiave";
System.out.println("\r\n > Cerco e stampo tutte le definizioni associate a " + key);
Iteratore entries = dizionario.findAll(key);
if (entries != null)
{
 	do

 	{
		System.out.println("" + entries.getdata().value);
	}while(entries.next());
}
else
	System.out.println(key + " non trovata!!!");


***********************************************
Classe ValuesList
***********************************************

Allo scopo di diminuire ulteriormente lo spreco di memoria anziché usare una struttura dati già pronta per contenere tutti le definizioni associate ad una chiave mi sono scritto questa classe dedicata ottimizzandola al massimo in modo da usare meno memoria possibile e dotandola solo dei metodi strettamente necessari a compiere le mie operazioni.

La lista che ho creato è una LinkedList che al suo interno ha tutti i nodi pieni (non esistono nodi vuoti, così da non sprecare spazio e ovviamente la lista non può esistere se vuota!) e non ha alcun campo dedicato alla memorizzazione del numero di elementi contenuti (questa scelta incide leggermente sulle prestazioni in quanto per “misurare” la lista ogni volta viene fatta una scansione lineare… ma le specifiche di progetto si preoccupavano della memoria… quindi il mio scopo era risparmiare memoria dove possibile…)

Questa classe è a solo uso interno e l’utente non dovrà mai interagirvi.
Ulteriori informazioni nei commenti del codice.

***********************************************
Classe SkipList
***********************************************

Questa classe costituisce la struttura dati su cui si appoggia il dizionario.
L'utente finale non dovrà MAI ed in NESSUN CASO interagire con questa classe...
Questa classe è solo di supporto... una descrizione dettagliata delle scelte progettuali e della varie funzionalità che incorpora è disponibile direttamente nel sorgente della classe sotto forma di commenti.

Nelle richieste di progetto c’è il vincolo che la memoria usata sia minore possibile, in tale ottica ho provveduto ad “stringere” al massimo i nodi.

Generalmente le skipList sono costituite da nodi con 5 campi (4puntatori + 1 dato) ed il campo dati contiene a sua volta altri 2 campi: chiave e valore…
Un evidente spreco di memoria… per migliorare il tutto ho provveduto a concepire il singolo nodo con soli 3 campi:

	un campo di tipo Nodo che punta al nodo di destra (.r) e che vale “null” quando ci si trova alla chiave sentinella +infinito.

	un campo di tipo Object (.d) che può essere usato in due modi: puntatore al nodo sotto se il nodo è a livello > 0 oppure puntatore ad un ValuesList (che contiene tutti i valori associati alla chiave in questione) se il nodo si trova al livello 0.

	un campo di tipo Comparable che contiene la chiave (.key)

Visto che il puntatore al nodo inferiore è usato anche per contenere la lista serve un “flag” che mi permetta di sapere quando sono arrivato alla lista base (livello S0) a tale scopo tra le variabili esemplare della lista è previsto un campo “h” che memorizza l’altezza attuale della lista, così da avere un riferimento per sapere se sono arrivato in fondo.

Le scelte possibili per la gestione delle chiavi doppie erano 2:
* inserire le chiavi doppie come se fossero diverse
* inserire le chiavi una sola volta e aggiungere soltanto gli elementi

ovviamente la seconda scelta è quella che più si addice al progetto in quanto diminuisce notevolmente la richiesta di spazio in memoria per contenere chiavi doppie!
Se si fossero inserite tutte le chiavi come diverse ogni nuova "definizione" associata ad una chiave già esistente avrebbe creato una nuova chiave con una nuova torre inserendo svariati nodi per nulla (in un dizionario è frequentissimo l'inserimento di chiavi doppie...)

Nei nodi appartenenti alla lista S0 (la base della SkipList) il puntatore sotto (.d) anziché puntare ad un altro Nodo punta ad una ValuesList che contiene tutti gli oggetti associati alla chiave rappresentata dal nodo in questione.

I metodi di ricerca/inserimento/rimozione sono stati realizzati seguendo gli algoritmi standard per le SkipList e adattati/ottimizzati per ottenere le massime prestazioni usando nodi con due soli riferimenti (destra, sotto)

Questo un esempio di un percorso di ricerca (ricerca della chiave 71)
 

Per quanto riguarda l’inserimento, anziché procedere dal basso come avviene solitamente per le liste con 4 riferimenti, in questo caso ho fatto prima il conteggio casuale per determinare l’altezza della torre, quindi creo la torre partendo dall’alto e abbassandomi di volta in volta finché non si arriva al nodo sulla lista di base.

***********************************************
Classe Nodo
***********************************************
Classe che costituisce l'elemento base della skipList
Realizzata secondo quanto descritto sopra.
Per massimizzare le prestazioni le variabili interne anche in questo caso godono tutte di accesso "amico"
Questa scelta non mette a repentaglio la robustezza della lista in quanto l'utente del dizionario non avrà MAI accesso ai nodi ;)


Esempio di output classe di Prova eseguito su di una macchina AMD Athlon Barton @ 2400mhz con jdk 1.5 su Win XP


C:\Programmi\Java\jdk1.5.0_01\bin\java.exe   Prova
Working Directory - C:\Documents and Settings\EvolutionCrazy\Desktop\507375\
Class Path - c:\programmi\java\jdk1.5.0_01\lib\tools.jar;c:\programmi\java\jdk1.5.0_01\jre\lib\rt.jar

 > Popolo il dizionario con 200000 definizioni completamente casuali (anche chiavi duplicate)
Inserimento di 200000 definizioni completato in 5110.0 millisecondi

 > Aggiungo 3 definizioni associate a 0chiave
Aggiunte tre definizioni a 0chiave, ora il dizionario contiene 200003 definizioni

 > Cerco e stampo tutte le definizioni associate a 0chiave
definizione00
definizione0000
definizione000

 > test remove(find(0chiave)) + findAll(0chiave) di verifica
definizione0000
definizione000

 > Faccio un find() di 100000 chiavi completamente casuali
chiave "-1638517137chiave" trovata, una definizione e' "definizione-1638517137"
chiave "788118962chiave" trovata, una definizione e' "definizione788118962"
chiave "407568933chiave" trovata, una definizione e' "definizione407568933"
Ricerca di 100000 chiavi casuali completata in 1093.0 millisecondi, 3 chiavi trovate

 > Richiedo iteratore su intera lista ordinata (entries()) e faccio uno scan completo
Iteratore ottenuto, 200002 entry rilevate

 > Richiedo iteratore di tutte le entry con chiave >= di 99985 e ne faccio una scansione
999859331chiave
999907432chiave
99991084chiave
999948130chiave
999979393chiave
999982300chiave
999997998chiave
Iteratore ottenuto, rilevate 7 entry con chiave >= di 99985

 > Richiedo iteratore di tutte le entry con chiave <= di -1000146778chiave e ne faccio una scansione
-1000137538chiave
-1000120615chiave
-1000113578chiave
-1000077758chiave
-1000064297chiave
-1000046856chiave
-1000020068chiave
-1000017025chiave
Iteratore ottenuto, rilevate 8 entry con chiave <= di -1000146778chiave

 > La chiave piu' piccola presente nel dizionario e' -1000017025chiave

 > La chiave piu' grande presente nel dizionario e' 999997998chiave

Process Exit...
DizionarioOrdinato.java

Codice: Seleziona tutto

import java.util.*;

class DizionarioOrdinato
{
	//lista che conterrà i dati
	private SkipList skipList;
	
	//costruttore
	DizionarioOrdinato(Comparable min, Comparable max)
	{
		skipList = new SkipList(min, max);
	}
	
	//funzione che dice se il dizionario è vuoto oppure no
	boolean isEmpty()
	{
		return skipList.size() == 0;
	}
	
	//funzione che dice quante definizioni contiene il dizionario
	int size()
	{
		return skipList.size();
	}

	//funzione di inserimento
	Entry insert(Comparable key, Object value)
	{
		return skipList.skipInsert(key, value);
	}

	//funzione di ricerca (restituisce un singolo elemento)
	Entry find(Comparable key)
	{
		return skipList.find(key);
	}

	//funzione di ricerca di tutte le definizioni (le restituisce in una ValuesList)
	Iteratore findAll(Comparable key)
	{
		Nodo nodo = skipList.findAll(key);
		if(nodo != null)
			return new Iteratore(nodo, this.skipList, 0);
		else
			return null;	
	}

	//restituisce un iteratore che punta alla chiave più piccola
	Iteratore entries()
	{
		return this.skipList.entries();
	}
	
	//funzione successors(key)
	Iteratore successors(Comparable key)
	{
		return skipList.successors(key);
	}
	
	//funzione predecessors(key)
	Iteratore predecessors(Comparable key)
	{
		return skipList.predecessors(key);
	}

	//funzione per ottenere la chiave più piccola
	Entry first()
	{
		return skipList.first();
	}

	//funzione per ottenere la chiave più grande
	Entry last()
	{
		return skipList.last();
	}

	Entry remove(Entry entry)
	{
		if(entry == null)
			return null;
		
		Nodo nodo = skipList.findAll(entry.key);

		if (nodo == null)
			return null;

		ValuesList lista = (ValuesList)(nodo.d);
		if (lista != null)
		{
			int posizione = lista.posizione(entry.value);
			if (posizione != -1)
			{
				if(skipList.skipRemove(entry.key, posizione) != null)
					return entry;
				else
					return null;
			}
		}
		return null;
	}

}

//classe per ritornare un entry coppia(chiave-value)
class Entry
{
	Comparable key;
	Object value;
	public Entry(Comparable key, Object value)
	{
		this.value = value;
		this.key = key;
	}
}


//classe iteratore
class Iteratore
{
	//variabile che contiene il riferimento al nodo puntato dall'Iteratore
	private Nodo nodo;
	//variabile che contiene il riferimento alla skipList su cui deve
	//muoversi l'iteratore
	private SkipList skiplist;
	//variabile che contiene il verso di percorrenza:
	//1 verso destra, -1 verso sinistra, 0 solo dentro la chiave
	private int direzione;
	//variabile che tiene conto del livello a cui sono nelle ValuesList
	private int definizione;
	
	//costruttore
	Iteratore(Nodo nodo, SkipList skiplist, int direzione)
	{
		this.nodo = nodo;
		this.skiplist = skiplist;
		this.direzione = direzione;
		if(direzione != -1)
			this.definizione = 0;
		else
			this.definizione = ((ValuesList)(nodo.d)).size()-1;
	}
	
	//true se ci sono altre entries
	boolean hasNext()
	{
		if (direzione != 0)
		{
			//verso destra
			if (direzione == 1)
			{
				//ho ancora elementi nella lista
				if(definizione < ((ValuesList)(nodo.d)).size()-1)
					return true;
				//finiti gli elementi nella lista, cambio nodo
				else
				{	
					if((nodo.r).r != null)
						return true;
					else
						return false;
				}	
			}
			//verso sinistra
			else
			{
				if(definizione > 0)
					return true;
				else
				{	
					if(skiplist.prev(nodo.key) != null)
						return true;
					else
						return false;
				}	
			}
		}
		else
		{
			//devo muovermi solo dentro la lista
			if(definizione < ((ValuesList)(nodo.d)).size()-1)
				return true;
			else
				return false;	
		}
	}
	
	//sposta l'iteratore
	public boolean next()
	{
		if (direzione != 0)
		{
			//verso destra
			if (direzione == 1)
			{
				if (this.hasNext())
				{
					//mi sposto alla definizione successiva
					if(definizione < ((ValuesList)(nodo.d)).size()-1)
						definizione++;
					else
					{
						//sposto in avanti il nodo e riparto col conteggio
						definizione = 0;
						nodo = nodo.r;
					}
					return true;
				}
				else
					return false;
			}
			//verso sinistra
			else
			{
				if (this.hasNext())
				{
					//mi sposto alla definizione precendente
					if(definizione > 0)
						definizione--;
					else
					{
						//sposto indietro il nodo e riparto col conteggio
						nodo = skiplist.prev(nodo.key);
						definizione = ((ValuesList)(nodo.d)).size()-1;
					}
					return true;
				}
				else
					return false;
			}
		}
		else
		{
			//mi posso spostare solo dentro la lista
			if (this.hasNext())
			{
				definizione++;
				return true;
			}
			else
				return false;
		}
	}
	
	//restituisce l'Entry a cui sta puntando
	public Entry getdata()
	{
		return new Entry(nodo.key, ((ValuesList)nodo.d).get(definizione));
	}
}

//classe nodo... quella che verrà usata nella linked list e nell'iteratore
//tutte le variabili usate qui hanno accesso "friendly" in modo da ottenere
//maggiori prestazioni durante gli accessi
//questa scelta non intacca assolutamente la sicurezza della classe dizionario
//in quanto l'utente non avrà mai un oggetto Nodo da manipolare.
//una scelta diversa invece va fatta se si vuole usare la classe SkipList
//per conto suo... infatti il metodo skipSearch restituisce un nodo...
//in quel caso quindi converrebbe dichiare la classe Nodo come privata e costruirla
//internamente alla SkipList
class Nodo
{
	//link al nodo di destra
	Nodo r;
	//link al nodo sotto / ValuesList
	Object d;
	//chiave associata (un oggetto Comparable)
	Comparable key;

	//costruttore del nodo
	Nodo(Nodo r, Object d, Comparable key){this.r = r;this.d = d;this.key = key;}
}

//lista semplificata usata al posto di LinkedList per risparmiare memoria
class ValuesList
{
	private class ValueListNode
	{
		private ValueListNode next;
		private Object value;
		private ValueListNode(Object value, ValueListNode next)
		{
			this.next = next;
			this.value = value;
		}
	}

	private ValueListNode head;
	
	//costruttore (nasce direttamente con un elemento, no nodi vuoti)
	//così da risparmiare memoria
	ValuesList(Object value)
	{
		this.head = new ValueListNode(value,null);
	}
	
	//size
	//per risparmiare memoria non viene salvato alcun contatore
	//per tenere traccia della dimensione di ogni lista
	//quindi è necessaria una scansione ogni volta... minori prestazioni
	//ma maggiore risparmio di memoria... le specifiche di progetto parlano
	//solo di memoria, quindi si presume che questa scelta sia la più
	//adatta
	int size()
	{
		ValueListNode temp = head;
		int i = 1;
		while (temp.next != null)
		{
			i++;
			temp = temp.next;
		}
		return i;
	}
	
	//funzione di ricerca (lineare) usata per identificare la posizione
	//che contiene l'oggetto passato come parametro
	int posizione(Object element)
	{
		ValueListNode temp = head;
		int i = 1;
		
		if(temp.value == element)
			return 0;
		
		while (temp.next != null)
		{
			if(temp.value == element)
				return (i-1);
			
			temp = temp.next;
		}

		if(temp.value == element)
			return (i-1);
		else
			return -1;
	}

	//restituisce un elemento a caso... la testa
	//complessità O(1)
	Object element()
	{
		return this.head.value;
	}
	
	//aggiunta elemento
	//lo inserisce tra la testa e quello dopo
	//(la lista non deve essere ordinata)
	//complessità O(1)
	void add(Object value)
	{
		this.head.next = new ValueListNode(value, this.head.next);
	}
	
	//remove index O(n) [n=numero di elementi nella lista]
	boolean remove(int index)
	{
		//index non valido, esco con false
		if(index < 0)
			return false;
		
		//creo nodo temporeaneo
		ValueListNode temp = this.head;
		
		int i = 0;
		
		if (index == 0)
		{
			this.head = head.next;
			return true;
		}
		else
		{		
			//mi sposto fino al nodo prima di quello che mi interessa
			while ((temp.next != null) && (i < index))
			{
				temp = temp.next;
				i++;
			}
			
			//scollego il nodo che voglio togliere ed esco con true
			if (i == index)
			{
				temp.next=(temp.next).next;
				return true;
			}
			else
				return false;
		}	
	}
	
	//get index O(n) [n=numero di elementi nella lista]
	//restituisce l'oggetto associato all'elemento con indice "index"
	//null se l'indice non è corretto....
	Object get(int index)
	{
		//creo nodo temporeaneo
		ValueListNode temp = head;

		for(int j = 0; j<index; j++)
			temp = temp.next;
	
		//restituisco l'oggetto
		return temp.value;
	}
}

//il cuore di tutto
class SkipList
{
	
	//altezza (quanti piani ha la lista)
	private int h;
	
	//nodo in alto a sinistra
	private Nodo head;
	
	//moneta
	private Random moneta;
	
	//numero elementi
	private int numeroElementi;
	
	//-infinito : uso il più piccolo carattere unicode
	private final Comparable min;
	//+infinito : uso il più grande carattere unicode
	private final Comparable max;
	
	//costruttore
	SkipList(Comparable min, Comparable max)
	{
		
		// mi creo una lista del tipo (* rappresenta una chiave, x rappresenta "null")
		//
		// * - * - x	S1
		// |   |
		// * - * - x	S0
		// |   |
		// x   x
		
		this.h = 1;
		this.head = new Nodo(null,null,min);
		Nodo aDx = new Nodo(null,null,max);
		Nodo bSx = new Nodo(null,null,min);
		Nodo tail = new Nodo(null,null,max);
		
		this.min = min;
		this.max = max;

		head.r = aDx;
		head.d = bSx;
		aDx.d = tail;
		bSx.r = tail;
		
		numeroElementi = 0;
		
		//inizializzo moneta
		moneta = new Random();
	}
	
	//ricerca di una chiave
	//restituisce il riferimento al nodo la cui la chiave è <= di quella che cerco io
	Nodo skipSearch(Comparable key)
	{
		//parto dalla testa (alto a sinistra)
		Nodo temp = head;
	
		int i = h;

		//scorro fino al piano terra
		while(i>0)
		{
			temp = (Nodo)temp.d;
			i--;
			//System.out.println(" <> Sono al livello " + i);
			
			//mi sposto a destra al massimo che posso (finchè è rispettata
			//la condizione chiave <= chiave cercata)
			while (key.compareTo((temp.r).key) >= 0)
			{
				//riassegno il nodo facendolo puntare a quello a destra
				temp = temp.r;
				//System.out.println(" <> mi sono spostato a destra, la prossima chiave sarà " + ((Nodo)(temp.r)).key);
			}
		}
		//System.out.println(" <> finita la ricerca di " + key + " quella prima è " + temp.key + " al piano " + i);
		return temp;
	}
	
	Entry skipInsert(Comparable key, Object value)
	{
	
		//System.out.println("\r\n******** INSERIMENTO DI " + key + " ********");

		//skipInsert blindato... chiavi out of range... non inserisco!!!
		if(key.compareTo(min)<=0 || key.compareTo(max)>=0)
			return null;
				
		//cerco il nodo
		Nodo temp = skipSearch(key);
		Nodo nodoNuovo;
		
		int i = 0;

		//chiave già esistente, aggiungo la definizione alla lista
		if ((temp.key).compareTo(key) == 0)
		{
			((ValuesList)(temp.d)).add(value);
			numeroElementi++;
			nodoNuovo = temp;		
		}
		//chiave non esistente: creo una lista nuova
		else
		{
			ValuesList lista = new ValuesList(value);
			
			//piazzo il nodo al suo posto nella lista 0
			nodoNuovo = new Nodo(temp.r, lista, key);
			numeroElementi++;
			temp.r = nodoNuovo;
			//System.out.println("Nodo nuovo correttamente collegato al livello 0");
			
			//generatore casuale (testa o croce)
			i = 0;
			while (moneta.nextBoolean())
			{
				i++;
				if (i==h)
				{
					Nodo tailSopra = new Nodo(null, head.r, max);
					head.d = new Nodo(head.r, head.d, min);
					head.r = tailSopra;
					h++;
				}
			}

			//riparto da capo
			temp = head;
			int j = h;

			for(j = h-1; j > i; j--)
			{	
				
				temp = (Nodo)temp.d;
				//System.out.println("=> mi sono spostato al piano " + (j-1));
				
				//System.out.println("=> ora sono al piano " + j);
				
				while ( ((temp.r).key).compareTo(key) < 0 )
				{
					temp = temp.r;
					//System.out.println("=> mi sono spostato a destra la prossima chiave ha valore " + (((Nodo)temp.r).key));
				}
				
				
			}

			Nodo nodoNuovo2 = new Nodo(temp.r, nodoNuovo, key);
			temp.r = nodoNuovo2;
			
			while (j > 0)
			{
				//mi abbasso
				temp = (Nodo)temp.d;
				j--;
			
				//mi sposto tutto a destra
				while ( ((temp.r).key).compareTo(key) < 0 )
				{
					//System.out.println("*> mi sono spostato a destra la prossima chiave ha valore " + (((Nodo)temp.r).key));
					temp = temp.r;
				}
				
				//creo il nodo nuovo e lo collego orizzontalmente
				//verticalmente lo collego a s0
				
				Nodo nodoNuovoTemp = new Nodo(temp.r, nodoNuovo2.d, key);
				nodoNuovo2.d = nodoNuovoTemp;
				
				nodoNuovo2 = nodoNuovoTemp;
				
				//collego orizzontalmente
				temp.r = nodoNuovo2;
							
			}
		}
		//System.out.println(key + " aggiunta con altezza " + i);
		//return nodoNuovo;
		return new Entry(key, value);
	}
	
	//funzione che restituisce il numero di elementi (numero di definizioni)
	int size(){return this.numeroElementi;}

	//funzione di rimozione
	Object skipRemove(Comparable key, int definizione)
	{
		if(key.compareTo(min)<=0 || key.compareTo(max)>=0)
			return null;
		
		//cerco il nodo di base associato
		Nodo nodo = (Nodo)skipSearch(key);
		
		//se non ho trovato la chiave corretta esco con false
		if (nodo.key.compareTo(key) != 0)
		{
			return null;
		}
		
		//devo rimuovere tutta la colonna senza preoccuparmi di nulla
		if (definizione < 0 || ((ValuesList)(nodo.d)).size() < 2)
		{
			this.numeroElementi = this.numeroElementi-(((ValuesList)(nodo.d)).size());
			
			//parto dalla testa (alto a sinistra)
			Nodo temp = head;
			Nodo tempPrev = head;	
		
			int i = h;

			//scorro fino a trovare l'elemento in cima alla mia torre con la chiave che cerco
			while(i>0)
			{
				temp = (Nodo)temp.d;
				tempPrev = (Nodo)tempPrev.d;
				i--;
				
				//mi sposto a destra al massimo che posso (finchè è rispettata
				//la condizione chiave <= chiave cercata)
				while (key.compareTo((temp.r).key) >= 0)
				{
					//riassegno il nodo facendolo puntare a quello a destra
					temp = temp.r;
				}
				
				while (key.compareTo((tempPrev.r).key) > 0)
				{
					//riassegno il nodo facendolo puntare a quello a destra
					tempPrev = tempPrev.r;
				}
				
				if(temp.key.compareTo(key) == 0)
					break;

			}
			
			//System.out.println(" >> Chiave " + key + " trovata al livello " + i );
			
			//qua ho i che contiene l'altezza del nodo ed il riferimento al nodo "temp"
			//che sta in alto sulla torre
			//poi ho il riferimento al nodo "tempPrev" che è quello precedente
			
			while (i>0)
			{
				//ora aggiorno i riferimenti saltando via quella che devo eliminare
				//System.out.println(" >> Sono dentro, sposto i riferimenti per far saltare " + key + " dal livello " + i );
				tempPrev.r = temp.r;

				//mi abbasso con entrambi
				temp = (Nodo)temp.d;
				tempPrev = (Nodo)tempPrev.d;
				i--;

				//sposto a destra al massimo "tempPrev"
				while (key.compareTo(((Nodo)(tempPrev.r)).key) > 0)
				{
					//riassegno il nodo facendolo puntare a quello a destra
					tempPrev = tempPrev.r;
				}
				
				
			}
			
			//System.out.println(" >> Sono fuori, sposto i riferimenti per far saltare " + key + " dal livello " + i );
			tempPrev.r = temp.r;
			
			//elimino le righe vuote (taglio la testa della skiplist)
			temp = head;
			while ( (((Nodo)(temp.d)).r).r == null )
			{
				temp.d = ((Nodo)(temp.d)).d;
				(temp.r).d = (((Nodo)((temp.r).d)).d);
				h--;
			}
			
			return new Entry(nodo.key, ((ValuesList)(nodo.d)).get(definizione));	
		}
		//rimuovo solo un elemento	
		else
		{
			Object valore = ((ValuesList)(nodo.d)).get(definizione);
			if (((ValuesList)(nodo.d)).remove(definizione))
			{
				this.numeroElementi--;
				return new Entry(key, valore);
			}
			else
				return null;
		}
	}
	
	//funzione entries() completa
	Iteratore entries()
	{
		//non ci sono chiavi che rispettano la condizione
		if(this.size() == 0)
			return null;
		
		Nodo temp = this.head;

		//scorro fino alla base
		for(int i=this.h;i>0;i--)
			temp = (Nodo)temp.d;

		//mi sposto a destra di un nodo così da non leggere -infinito
		temp = temp.r;
		
		return new Iteratore(temp, this, 1);
	}

	//funzione successors(key)
	Iteratore successors(Comparable key)
	{
		//non ci sono chiavi che rispettano la condizione
		if(this.size() == 0)
			return null;
			
		Nodo temp = (Nodo)(this.skipSearch(key));
		if(key.compareTo(temp.key) != 0)
			temp = temp.r;
	
		//non ci sono chiavi che rispettano la condizione
		if(temp.r == null)
			return null;
		else	
			return new Iteratore(temp, this, 1);
	}

	//funzione predecessors(key)
	Iteratore predecessors(Comparable key)
	{
		//non ci sono chiavi che rispettano la condizione
		if(this.size() == 0)
			return null;
		
		Nodo temp = (Nodo)(this.skipSearch(key));
		
		//non ci sono chiavi che rispettano la condizione
		if(temp.d == null)
			return null;
		else
			return new Iteratore(temp, this, -1);
	}
	

	Entry first()
	{
		if(this.size() == 0)
			return null;
			
		Nodo nodo = (this.skipSearch(this.min)).r;
		Comparable key = nodo.key;
		ValuesList values = (ValuesList)(nodo.d);
		return new Entry(key, values.element());
	}
	
	Entry last()
	{
		if(this.size() == 0)
			return null;
		
		//parto dalla testa (alto a sinistra)
		Nodo temp = head;
	
		int i = h;

		//scorro fino al piano terra
		while(i>0)
		{
			temp = (Nodo)temp.d;
			i--;
			
			//mi sposto a destra al massimo che posso (finchè è rispettata
			//la condizione chiave <= chiave cercata)
			while (max.compareTo((temp.r).key) > 0)
			{
				//riassegno il nodo facendolo puntare a quello a destra
				temp = temp.r;
			}
		}
		
		Comparable  key = temp.key;
		ValuesList values = (ValuesList)(temp.d);
		return new Entry(key, values.element());
	}
	
	Nodo prev(Comparable key)
	{
		//parto dalla testa (alto a sinistra)
		Nodo temp = head;
		//Nodo nodo = this.skipSearch(key);
	
		int i = h;

		//scorro fino al piano terra
		while(i>0)
		{
			temp = (Nodo)temp.d;
			i--;
			
			//mi sposto a destra al massimo che posso (finchè è rispettata
			//la condizione chiave < chiave cercata)
			while (key.compareTo((temp.r).key) > 0)
			{
				if(key.compareTo((temp.r).key) <= 0)
					break;
				//riassegno il nodo facendolo puntare a quello a destra
				temp = temp.r;
			}
		}
		
		if(temp.d == null)
			return null;
		else		
			return temp;
	}

	//funzione di ricerca
	Entry find(Comparable key)
	{
		//cerco il nodo di base associato
		Nodo nodo = (Nodo)skipSearch(key);
		
		//se ho trovato la chiave corretta mando in output una definizione a caso
		
		if (nodo.key.compareTo(key) == 0)
		{
			Entry entry = new Entry(nodo.key, ((ValuesList)(nodo.d)).element());
			return entry;
		}
		//altrimenti mando in output null
		else
			return null;
	}
	
	Nodo findAll(Comparable key)
	{
		//cerco il nodo di base associato
		Nodo nodo = (Nodo)this.skipSearch(key);
		
		//se ho trovato la chiave corretta mando in output il nodo
		if (nodo.key.compareTo(key) == 0)
			return nodo;
		//altrimenti mando in output null	
		else
			return null;
	}
}
Prova.java

Codice: Seleziona tutto

import java.util.*;
class Prova
{
	public static void main (String[] args)
	{

		//creo il dizionario
		//bisogna passargli i due estremi +infinito e meno infinito...
		//gli estremi devono essere dati dello stesso tipo di quelli che saranno usati per le chiavi
		//e devono implementare l'interfaccia Comparable
		//in questo caso faccio i test con le stringhe e quindi uso il più piccolo ed il più grande
		//caratteri Unicode disponibile ;)
		DizionarioOrdinato dizionario = new DizionarioOrdinato("" + (char)0x0000, "" + (char)0x10FFFD + (char)0x10FFFD + (char)0x10FFFD + (char)0x10FFFD);

		//preparo una variabile per contenere le liste restituite da findAll()
		ValuesList lista;
	
		Entry entry;
		Comparable key;
		Iteratore entries;
		
		//creo variabile che conterra un numero intero casuale
		int rand;
		
		//creo variabili per il timer
		long start, stop;
		float durata;

		//inizializzo generatore casuale
		Random random = new Random();

		//test insert()
			start = System.currentTimeMillis();
			
			int elementiDaInserire = 200000;
			
			System.out.println("\r\n > Popolo il dizionario con " + elementiDaInserire + " definizioni completamente casuali (anche chiavi duplicate)");
			
			for(int i = 0; i < elementiDaInserire; i++)
			{
				rand = random.nextInt();
				dizionario.insert(rand+"chiave", "definizione"+rand);
			}
			
			stop = System.currentTimeMillis();
			durata = stop - start;
		
		//test size() <= restituisce il numero di definizioni presenti nel dizionario
		if(!dizionario.isEmpty())
			System.out.println("Inserimento di " + dizionario.size() + " definizioni completato in " + durata + " millisecondi");
		else
			System.out.println("Qualcosa è andato storto... il dizionario risulta vuoto... le definizioni memorizzate sono " + dizionario.size() + " (il processo di inserimento è durato " + durata + " millisecondi)");
						
		//test inserimento chiavi doppie: inseriesco altre due definizioni per la chiave 0	
			System.out.println("\r\n > Aggiungo 3 definizioni associate a 0chiave");
			dizionario.insert("0chiave", "definizione00");
			dizionario.insert("0chiave", "definizione000");
			dizionario.insert("0chiave", "definizione0000");
			System.out.println("Aggiunte tre definizioni a 0chiave, ora il dizionario contiene " + dizionario.size() + " definizioni");

		//test findAll()
			key = "0chiave";
			System.out.println("\r\n > Cerco e stampo tutte le definizioni associate a " + key);
			entries = dizionario.findAll(key);
			if (entries != null)
			{
				do
				{
					System.out.println("" + entries.getdata().value);
				}while(entries.next());
			}
			else
				System.out.println(key + " non trovata!!!");
		
		//test remove
			key = "0chiave";
			System.out.println("\r\n > test remove(find(" + key + ")) + findAll(" + key + ") di verifica");	
			if (dizionario.remove(dizionario.find(key)) != null)
			{
				entries = dizionario.findAll(key);
				if (entries != null)
				{
					do
					{
						System.out.println("" + entries.getdata().value);
					}while(entries.next());
				}
				else
					System.out.println(key + " non trovata!!!");
			}	
			else
				System.out.println("Errore nella rimozione!");
	
		//test find() di tante chiavi
			random = new Random();
			start = System.currentTimeMillis();
			
			int quante = 0;
			
			int elementiDaCercare = 100000;
			System.out.println("\r\n > Faccio un find() di " + elementiDaCercare + " chiavi completamente casuali");
			for(int i = 0; i < elementiDaCercare; i++)
			{
				rand = random.nextInt();
				entry = dizionario.find(rand + "chiave");
				if (entry != null)
				{
					quante++;
					System.out.println("chiave \"" + rand + "chiave\" trovata, una definizione e' \"" + entry.value + "\"");
				}
			}
			
			stop = System.currentTimeMillis();
			durata = stop - start;
			System.out.println("Ricerca di " + elementiDaCercare + " chiavi casuali completata in " + durata + " millisecondi, " + quante + " chiavi trovate");

		//test entries() ed iteratore
			System.out.println("\r\n > Richiedo iteratore su intera lista ordinata (entries()) e faccio uno scan completo");
			entries = dizionario.entries();
			int quanteEntry = 0;
			if (entries != null)
			{
				do
				{
					//System.out.println(entries.key());
					quanteEntry++;
				}while(entries.next());

			}
			System.out.println("Iteratore ottenuto, " + quanteEntry + " entry rilevate");

		//test successors(start) + iteratore
			key = "99985";
			System.out.println("\r\n > Richiedo iteratore di tutte le entry con chiave >= di " + key + " e ne faccio una scansione");	
			entries = dizionario.successors(key);
			quanteEntry = 0;
			if (entries != null)
			{
				do
				{
					System.out.println(entries.getdata().key);
					quanteEntry++;
				}while(entries.next());

				System.out.println("Iteratore ottenuto, rilevate " + quanteEntry + " entry con chiave >= di " + key);
			}
			else
				System.out.println("Iteratore ottenuto, nessuna chiave >= di " + key);

		//test predecessors(start) + iteratore
			key = "-1000146778chiave";
			System.out.println("\r\n > Richiedo iteratore di tutte le entry con chiave <= di " + key + " e ne faccio una scansione");	
			entries = dizionario.predecessors(key);
			quanteEntry = 0;
			if (entries != null)
			{
				do
				{
					System.out.println(entries.getdata().key);
					quanteEntry++;
				}while(entries.next());

				System.out.println("Iteratore ottenuto, rilevate " + quanteEntry + " entry con chiave <= di " + key);
			}
			else
				System.out.println("Iteratore ottenuto, nessuna chiave <= di " + key);
				
					
		//test first()
			entry = dizionario.first();
			if(entry != null)	
				System.out.println("\r\n > La chiave piu' piccola presente nel dizionario e' " + entry.key);
			else	
				System.out.println("\r\n > Non e' stato possibile trovare la chiave più piccola, il dizionario e' vuoto!");

		//test last()
			entry = dizionario.last();
			if(entry != null)		
				System.out.println("\r\n > La chiave piu' grande presente nel dizionario e' " + entry.key);
			else
				System.out.println("\r\n > Non e' stato possibile trovare la chiave più piccola, il dizionario e' vuoto!");	
	}
}
Avatar utente
Google
Supporter
Supporter
Messaggi: Tanti
Iscritto il: 17/11/2008, 1:00