Forum Informatica Unict

LAUREA TRIENNALE (D.M. 270/04) => Programmazione 2, 9 CFU => Topic started by: Daréios89 on 19-05-2010, 19:36:37



Title: Esercizio sugli array espandibili.
Post by: Daréios89 on 19-05-2010, 19:36:37
Nell'esercizio:

Code:
Si realizzi una classe Java, denominata ListOfArray<E> che implementi
l'interfaccia OrderedSet<E> (mostrata nella pagina seguente). La nuova classe
ListOfArray<E> mantiene gli elementi dell'insieme all'interno di array di
dimensione fissa pari a 100. Quando lo spazio allocato nella struttura non è più
sufficiente per contenere tutti gli elementi inseriti viene creato un nuovo array di
dimensione 100 che permette di estendere lo spazio disponibile.
Tutti gli array allocati nella struttura sono organizzati in una lista linkata semplice.
Gli elementi sono memorizzati in ordine non decrescente.
Si realizzi in seguito una classe che implementi l'interfaccia Person (mostrata nella
pagine seguente) e si fornisca un programma Java che prenda in input un file
contenente una lista di persone (specificate da nome, cognome ed età) e restituisca
in output la medesima lista ordinata in senso non decrescente secondo i campi
cognome, nome ed età.
L'insieme deve essere gestito attraverso una classe ListOfArray<Person>.

Mi chiedevo:
Code:
Tutti gli array allocati nella struttura sono organizzati in una lista linkata semplice.
Significa che dovrei inserire gli array all'interno dei nodi della lista o che debba implementare gli array tramite lista?


Poi nell'interfaccia Person:
 
Code:
public int compareTo(Person person);
// ritorna un valore maggiore di 0 se la persona ha un valore
più grande di person; 0 se hanno due valori uguali; un intero
minore di 0 altrimenti

Ma che cosa si intende per valore maggiore che una persona ha rispetto ad un altro?


Title: Re:Esercizio sugli array espandibili.
Post by: LtWorf on 19-05-2010, 21:08:14
Significa che gli array sono accessibili tramite i nodi della lista, come fai a implementare gli array con una lista scusa? :D

Boh magari hanno un campo value le Person?


Title: Re:Esercizio sugli array espandibili.
Post by: Daréios89 on 19-05-2010, 21:14:22
Si deve prendere in input una lista di persone:

Antonio, Barbagallo, 12
Michele, Zafarana, 23
Roberta, Mapo, 56

Che sono persone con nome cognome ed età e bisogna riordinare la lista in base ai tre parametri e stamparla in ordine non decrescente.

Non capisco perchè è richiesto di usare la lista, dovrei creare un'altra classe a parte ovviamente.....


Title: Re:Esercizio sugli array espandibili.
Post by: LtWorf on 20-05-2010, 09:03:08
Eh si l'idea degli esercizi è proprio quella di fare esercitare


Title: Re:Esercizio sugli array espandibili.
Post by: Daréios89 on 20-05-2010, 09:54:01
Eh si l'idea degli esercizi è proprio quella di fare esercitare

 :yoh

Allora credi che per memorizzare nellal ista debba crearmi una mia classe Nodo e lista linkata giusto?
Poichè anche se non è richiesto devo trovare io gli strumenti utili alla risoluzione del problema...


Title: Re:Esercizio sugli array espandibili.
Post by: LtWorf on 20-05-2010, 11:05:00
Si, a programmazione è vietatissimo usare le liste già pronte di java!


Title: Re:Esercizio sugli array espandibili.
Post by: aryanna on 24-05-2010, 22:28:23
Ma sei riuscito a risolevrlo l'esercizio? io ci ho messo mano ma mi sn fermata al compareTo... io ho stratturato il mio array espandibile come un array le cui locazioni sono occupate da nodi a loro volta contenenti oggetti di tipo E che in altre parole sarebbero le persone... e i metodi che utilizzo x lavorare sull'array sono quelli della linked list semplice... come l'hai sviluppato il programma tu?


Title: Re:Esercizio sugli array espandibili.
Post by: Daréios89 on 24-05-2010, 22:39:53
Emh.....a dire il vero...non l'ho sviluppato, avevo iniziato un altro esercizio sulle liste che mi ha dato pure problemi, quindi non me ne sono occupato, ma ci torno, e ti faccio sapere.
Penso che la tua idea sia corretta, il problema, che già avevo intuito è fare il confronto.... .penso


Title: Re:Esercizio sugli array espandibili.
Post by: XDnl on 25-05-2010, 14:02:47
Ragazzi io avrei dei dubbi sull'interfaccia OrderedSet<E>
Code:
interface OrderedSet<E>
{
// ritorna true se l'insieme è vuoto
public boolean isEmpty();

// ritorna il numero di elementi contenuti nell'insieme
public int size();

// inserisce un nuovo elemento nell'insieme
public void add(E element);

// elimina il primo elemento di valore element
public void remove(E element);

// ritorna true se l'emento element è presente nell'insieme
public boolean isPresent(E element);

// ritorna l'elemento più piccolo dell'insieme
public E getFirst();

// ritorna l'elemento più grande dell'insieme
public E getLast();

// stampa la lista ordinata degli elementi dell'insieme
public String toString();
}
I metodi getFirst(), getLast() e add() (che immagino sia un inserimento ordinato) devono per forza fare dei confronti sui vari elementi di tipo E.
Così com'è specificata l'interfaccia, non abbiamo alcuna informazione sulla natura di E, come facciamo a confrontarli?
Non bisognerebbe imporre che il tipo generico E implementi l'interfaccia Comparable? Una cosa del genere
Code:
interface OrderedSet<E extends Comparable>
{
// ... metodi ...
}

Ovviamente anche l'interfaccia Person (che d'altrode ha già il metodo compareTo!) deve estendere Comparable in modo da poterla utilizzare come tipo in OrderedSet<E>.

Non vedo altra soluzione, anche se non mi sembra buono modificare le specifiche date dal pdf.
Qualcun'altro ha delle idee su come aggirare il problema?

Grazie


Title: Re:Esercizio sugli array espandibili.
Post by: aryanna on 26-05-2010, 07:33:41
Io per comparare gli oggetti di tipo E che in altre parole x noi sarebbero le Persone ho basato tutto sul metodo compareTo, in base allo stesso compareTo delle stringhe, xk l'ordinamento va fatto prendendo in considerazione prima il cognome e solo se il cognome uguale anche il nome... ancora a me nn funziona perfettamente ma il ragionamento dovrebbe esseere giusto


Title: Re:Esercizio sugli array espandibili.
Post by: XDnl on 26-05-2010, 12:30:14
Io per comparare gli oggetti di tipo E che in altre parole x noi sarebbero le Persone
Ok, però nell'implementazione di ArrayList<E> abbiamo tipi generici.

ho basato tutto sul metodo compareTo, in base allo stesso compareTo delle stringhe, xk l'ordinamento va fatto prendendo in considerazione prima il cognome e solo se il cognome uguale anche il nome...
Esattamente, per confrontare nome e cognome anch'io ho utilizzato il compareTo delle stringhe.

ancora a me nn funziona perfettamente ma il ragionamento dovrebbe esseere giusto
Come hai implementato, ad esempio, il metodo add dell'interfaccia OrderedSet<E>?
Suppongo che questo metodo debba inserire l'elemento E al posto giusto (mantenendo cioè gli elementi in ordine non decrescente), d'altronde OrderedSet non significa insieme ordinato?  :-)|

Nell'implementare questo metodo, non ti serve effettuare il confronto tra due oggetti di tipo E?
Solo che non abbiamo alcuna informazione su quale oggetto sia E (indipendentemente poi dal fatto che il testo ci dica di implementare un ArrayList<Person>).
Una soluzione che ho pensato è imporre che l'oggetto generico E implementi l'interfaccia Comparable:

Code:
// Imponendo che E implementi Comparable, posso richiamare su di esso il compareTo
interface OrderedSet<E extends Comparable>
{
// ritorna true se l'insieme è vuoto
public boolean isEmpty();

// altri metodi...
}
Poi ho modificato anche Person, cambiando leggermente la firma di compareTo, in modo da rispettare le
specifiche dell'interfaccia Comparable

Code:
interface Person extends Comparable
{
// metodi..

// ritorna un valore maggiore di 0 se la persona ha un valore
// più grande di person; 0 se hanno due valori uguali; un intero
// minore di 0 altrimenti
public int compareTo(Object o) throws ClassCastException;

boolean equals(Object obj) throws ClassCastException;

}

Infine, ovviamente, ho imposto anche nella classe ArrayList che il tipo generico E debba estendere Comparable:
Code:
class ListOfArray<E extends Comparable> implements OrderedSet<E>
{
public static final int ARRAY_CAPACITY = 100;
private SLinkedList<BucketArray<E>> arrayList;

public ListOfArray()
{
arrayList = new SLinkedList<BucketArray<E>>();
}

// metodi...

// inserisce un nuovo elemento nell'insieme
public void add(E element)
{
// Vedo la prima lista libera
SNode<BucketArray<E>> arrayNode = arrayList.getHead();
while (arrayNode != null && arrayNode.getData().isFull())
arrayNode = arrayNode.getNext();

// Se tutte le liste sono piene
// Devo generarne una nuova
if (arrayNode == null)
arrayNode = arrayList.addTail(new BucketArray<E>(ARRAY_CAPACITY));

final BucketArray<E> myArray = arrayNode.getData();

// Devo inserire l'elemento in ordine all'interno di myArray.getData()
// Qui mi serve per forza il compareTo!
int pos = 0;
while (pos < myArray.getSize() && element.compareTo(myArray.at(pos)) < 0)
pos++;

myArray.addAt(pos, element);
}
}
Così sembra funzionare, ma come vedi ho dovuto modificare le interfacce specificate dal testo, per questo non sono sicuro che sia il modo giusto di svolgere l'esercizio.  :-)|


Title: Re:Esercizio sugli array espandibili.
Post by: XDnl on 27-05-2010, 16:50:01
Nessuna idea in proposito?  :-)|


Title: Re:Esercizio sugli array espandibili.
Post by: aryanna on 27-05-2010, 19:03:14
Allora ci sn riuscita mettendo insieme le idee di altri ragazzi.. in pratica l'add l'abbiamo implementato in qst modo..
Code:
public void add(E element){
if(tail==null){
ListPerson [] vett = new ListPerson[100];
cont=0;
vett[cont]= (ListPerson) element;
Node n= new Node(vett);
tail=n;
head=tail;
size++;
}
else if(cont==99){
cont=0;
ListPerson [] vett = new ListPerson[100];
vett[cont]=(ListPerson) element;
Node n= new Node(vett);
tail.setNext(n);
tail=n;
size++;
}
else{
ListPerson [] vettsupp= (ListPerson[]) tail.getElement();
cont++;
vettsupp[cont]= (ListPerson) element;
tail.setElement((E) vettsupp);
}
}
Che in altre parole crea un nuovo nodo (che contiene un array di 100 locazioni in cui in ogni cella viene inserita la persona). Tutti i vari if sono x controllare se l'array è pieno cioè con tutti e 100 gli elementi o meno in modo da allocare un nuovo nodo o semplicemente riempire un'altra cella.
La classe compare nn la utilizzo


Title: Re:Esercizio sugli array espandibili.
Post by: Daréios89 on 29-05-2010, 15:19:24
Scusate, sto provando ora a fare l'esercizio, siccome dice che bisogna memorizzare gli elementi in una linkedlist io avevo creato la classe Node e poila classica LinkedList, ma allora ho sbagliato, devo solo creare Node, e poi invece la lista la gestisco in questa class ArrayList giusto?
Creando head,tail......
P.S. non ho ben capito come fare i metodi getFirst() e getLast() della classe che implementa OrderedSet.
Ritornano l'elemento più grande e più piccolo dell'insieme.
Ma se abbiamo una lista di persone, più piccolo e più grande rispetto a cosa, all'età?


Title: Re:Esercizio sugli array espandibili.
Post by: aryanna on 30-05-2010, 08:45:33
No, l'ordinamento deve essere fatto sempre prendendo in considerazione innanzitutto il cognome, se poi trovi due persone con lo stesso cognome allora vai a controllare il nome e se anche questo è uguale allora controlli l'età. La linked list deve essere in pratica questa tua classe particolare, non una classica linked list a parte


Title: Re:Esercizio sugli array espandibili.
Post by: Daréios89 on 30-05-2010, 10:50:33
Eh ma per l'ordinamento devo creare un metodo apposta io?
Per getFirst e getLast, non sto capendo...su tutto l'insieme come faccio a stabilire il più piccolo, cioè sarebbe quello che ha cognome che inizia con A, nome per A, e il minor numero di anni?
Viceversa per il più grande?
Mentre per ordinare gli elementi avete creato un vostro metodo in questa classe oppure tramite getFirst e getLast si può ordinare?


Title: Re:Esercizio sugli array espandibili.
Post by: XDnl on 30-05-2010, 12:48:26
Allora ci sn riuscita mettendo insieme le idee di altri ragazzi.. in pratica l'add l'abbiamo implementato in qst modo..
Code:
public void add(E element){
if(tail==null){
ListPerson [] vett = new ListPerson[100];
cont=0;
vett[cont]= (ListPerson) element;
Node n= new Node(vett);
tail=n;
head=tail;
size++;
}
else if(cont==99){
cont=0;
ListPerson [] vett = new ListPerson[100];
vett[cont]=(ListPerson) element;
Node n= new Node(vett);
tail.setNext(n);
tail=n;
size++;
}
else{
ListPerson [] vettsupp= (ListPerson[]) tail.getElement();
cont++;
vettsupp[cont]= (ListPerson) element;
tail.setElement((E) vettsupp);
}
}

 .penso Ho riflettuto un po' sul tuo codice.  .leggo
La classe ListPerson è una lista di persone ( .penso) o contiene le informazioni su una singola persona?
Nel secondo caso (che penso sia il più logico), praticamente mantieni una lista dove ogni nodo è un array di 100 persone.
La variabile cont serve a tener traccia dell'indice dell'ultimo elemento inserito giusto?
C'è una cosa però che non mi convince: il metodo add fa parte della classe ListOfArray<E> dove E è un elemento generico, mentre all'interno del metodo crei un'array di tipo ListPerson.
Se per esempio vorresti creare una ListOfArray<Integer> quando fai
Code:
vettsupp[cont]= (ListPerson) element;
dovresti avere una ClassCastException (o qualcosa del genere  :-)|)

L'inserimento inoltre avviene in coda e quindi all'interno dei vari array le persone non sono ordinate in senso non decrescente. (e qui approfitto per rispondere a Darèios  :[Emoticon] Asd:)

Eh ma per l'ordinamento devo creare un metodo apposta io?
In teoria dovrebbe essere il metodo compareTo dell'interfaccia Person  .sisi

Per getFirst e getLast, non sto capendo...su tutto l'insieme come faccio a stabilire il più piccolo, cioè sarebbe quello che ha cognome che inizia con A, nome per A, e il minor numero di anni?
Viceversa per il più grande?
Esattamente.

Mentre per ordinare gli elementi avete creato un vostro metodo in questa classe oppure tramite getFirst e getLast si può ordinare?
A quanto ho capito io, quando fai add devi inserire l'elemento al posto giusto. In questo modo ti ritrovi i vari array ordinati.

Secondo me il problema permane: come si fa (assumendo che E sia un tipo generico) a confrontare due elementi?
Il professore ha dato delle indicazioni a riguardo?  .penso


Title: Re:Esercizio sugli array espandibili.
Post by: Daréios89 on 30-05-2010, 12:55:30
Tu dici che l'ordinamento va fatto con il metodo add inserendo gli elementi nell'array al posto giusto.
Quindi non può essere che invece con add si inseriscono semplicemente gli elementi che si leggono in input, si riempie tutta la lista, e poi con un metodo appostito si confrontano gli elementi una volta inseriti nelle liste accedendo agli array?

Quote
Secondo me il problema permane: come si fa (assumendo che E sia un tipo generico) a confrontare due elementi?

Non ho provato, ma secondo te dà errori?
Cioè con il fatto che si dichiara tutto con i generics non dovrebbe permettere al compareTo di funzionare lo stesso?


Title: Re:Esercizio sugli array espandibili.
Post by: XDnl on 30-05-2010, 13:01:47
Tu dici che l'ordinamento va fatto con il metodo add inserendo gli elementi nell'array al posto giusto.
Quindi non può essere che invece con add si inseriscono semplicemente gli elementi che si leggono in input, si riempie tutta la lista, e poi con un metodo appostito si confrontano gli elementi una volta inseriti nelle liste accedendo agli array?
Beh anche volendo fare così (che secondo me non è molto logico, essendo la classe una OrderedSet, ossia un insieme ordinato), nell'implementare i metodi getFirst e getLast hai comunque bisogno di usare la compareTo della classe Person.

Non ho provato, ma secondo te dà errori?
Cioè con il fatto che si dichiara tutto con i generics non dovrebbe permettere al compareTo di funzionare lo stesso?
Il problema è che i generics, come specificati nel testo, sono un po' troppo... generics...  :boh
Il metodo compareTo non fa parte della classe Object, bensì dell''interfaccia comparable (Object ha al massimo il metodo equals, che non è sufficiente).
Quindi un generico oggetto di tipo E non ha il metodo compareTo.
L'unica soluzione che ho trovato è stata di imporre che il tipo generico E estenda l'interfaccia comparable.
Come già detto però, non sono sicuro che modificare il testo sia il modo corretto per affrontare l'esercizio.

Come si fa ad aggirare il problema senza cambiare le interfacce?  :-)| :-)| :-)|

P.S: Avete notato che il testo dell'esercizio "Liste implementate tramite vettori" (sempre nella stessa sezione) è identico a quello precedente? (mentre nella pagina html del sistema la descrizione, purtroppo incompleta, è quella corretta).


Title: Re:Esercizio sugli array espandibili.
Post by: Daréios89 on 30-05-2010, 13:32:11
Si ci avevo fatto caso, al fatto che sono uguali, però non che quella incompleta fosse diversa, ad ogni modo l'input e l'output di quella non so se siano corretti a questo punto, sono identici pure quelli.....
Ma se il tuo metodo funziona perchè no, forse lui non ha voluto specificare tutto per fare in modo che gli studenti da soli dovessero capire come aggirare il problema, però a me non compila in quel modo:

Code:
public class ListOfArray <E extends Comparable> implements OrderedSet<E>

si scrive così? Nonostante abbia modificato come hai detto tu le altre classi per farsì che il tipo generico estenda Comparable non mi compila così.

[RISOLTO]

Certo che se non apro con la parentesi graffa.....  :pray


Title: Re:Esercizio sugli array espandibili.
Post by: aryanna on 30-05-2010, 14:18:09
Quote
La classe ListPerson è una lista di persone o contiene le informazioni su una singola persona?
Nel secondo caso (che penso sia il più logico), praticamente mantieni una lista dove ogni nodo è un array di 100 persone.
La variabile cont serve a tener traccia dell'indice dell'ultimo elemento inserito giusto?
C'è una cosa però che non mi convince: il metodo add fa parte della classe ListOfArray<E> dove E è un elemento generico, mentre all'interno del metodo crei un'array di tipo ListPerson.
Se per esempio vorresti creare una ListOfArray<Integer> quando fai

vettsupp[cont]= (ListPerson) element;
dovresti avere una ClassCastException (o qualcosa del genere  )

La mia ListPerson in effetti sarebbe stato più opportuno chiamarla Persona perchè in poche parole contiene le informazioni relative ad una singola persona. Cont è l'indice dell'array. Mentre nn capisco cosa intendi per la classe ClassCastException perchè lavorando con oggetti generici non dovrebbero esserci problemi facendo un ListOfArray<Integer> o ListOfArray<ListPerson> (come d'altronde ho fatto)... o a qst punto c'è qualcosa che mi sfugge sul concetto di oggetti generici..però penso abbia senso logico è un array di persone proprio come richiede il testo


Title: Re:Esercizio sugli array espandibili.
Post by: Daréios89 on 30-05-2010, 14:24:36
Ma quindi con l'add inserisci solamente in lista gli elementi che leggi in input, ma poi per ordinarli e metterli nelle giuste posizioni dell'array(e dei nodi) hai scritto un metodo a parte semrpe in questa classe?


Title: Re:Esercizio sugli array espandibili.
Post by: XDnl on 30-05-2010, 14:25:04
Mentre nn capisco cosa intendi per la classe ClassCastException perchè lavorando con oggetti generici non dovrebbero esserci problemi facendo un ListOfArray<Integer> o ListOfArray<ListPerson> (come d'altronde ho fatto)...
Prova ad eseguire questo programmino:

Code:
// La classe usa il tipo generico E
class Generico<E>
{
// Qui invece diamo per sicuro che E sia un intero
public int dato;

public Generico(E element)
{
// Se element non è effettivamente un intero, viene
// lanciata l'eccezione java.lang.ClassCastException
dato = (Integer)element;
}

}

public class main
{

public static void main(String[] args)
{
// Ok
Generico<Integer> prova = new Generico<Integer>(3);

// Errore!
Generico<String> prova2 = new Generico<String>("CIAO");
}
}

o a qst punto c'è qualcosa che mi sfugge sul concetto di oggetti generici..però penso abbia senso logico è un array di persone proprio come richiede il testo
Si, però la classe ListOfArray è dichiarata così
Code:
class ListOfArray<E> // E potrebbe essere la qualunque cosa
{
 ....
}
Mentre all'interno di add crei direttamente degli array di ListPerson, ma nessuno ti garantisce che il tipo generico E sia effettivamente quello.
Se provi a creare una ListOfArray<Integer>, quando fai il cast di tipo, dovresti avere un'eccezione.

Ma quindi con l'add inserisci solamente in lista gli elementi che leggi in input, ma poi per ordinarli e metterli nelle giuste posizioni dell'array(e dei nodi) hai scritto un metodo a parte semrpe in questa classe?
No, con la modifica delle interfacce, ho fatto che add inserisce gli elementi al posto giusto, quindi alla fine ho tutti gli elementi ordinati. L'elemento piu' piccolo è il primo elemento del primo array, mentre quello piu' grande sarà l'ultimo elemento dell'ultimo array.  :[Emoticon] PC Asd:

 :boh A questo punto penso sia meglio fare come si crede, basta che funzioni  :-OK


Title: Re:Esercizio sugli array espandibili.
Post by: Daréios89 on 30-05-2010, 14:37:31
Scusate, potrei sapere come avete implementato il compareTo dell'interfaccia Person?


Title: Re:Esercizio sugli array espandibili.
Post by: XDnl on 31-05-2010, 17:08:24
Scusate, potrei sapere come avete implementato il compareTo dell'interfaccia Person?
Ecco (un po' in ritardo XD) la mia versione:
Code:
// ritorna un valore maggiore di 0 se la persona ha un valore
// più grande di person; 0 se hanno due valori uguali; un intero
// minore di 0 altrimenti
public int compareTo(Object o) throws ClassCastException
{
Person person = (Person)o;
int ret = cognome.compareTo(person.getCognome());
if (ret != 0) return ret;

ret = nome.compareTo(person.getNome());
if (ret != 0) return ret;

return anni - person.getAnni();
}

public boolean equals(Object obj) throws ClassCastException
{
return compareTo(obj) == 0;
}
Ovviamente l'interfaccia Person è stata modificata (nel senso che estende Comparable).
 .ciaociao


Title: Re:Esercizio sugli array espandibili.
Post by: Daréios89 on 31-05-2010, 21:09:46
Quando ad esempio fai:

Code:
int ret = cognome.compareTo(person.getCognome());
Confronto il cognome della persona che sta invocando il metodo con quella tra parentesi?
P.S. Io avrei pensato che ci voleva il this.

Code:
int ret=this.cognome.compareTo......

Invece per l'inserimento ordinato, io sto avendo molta confusione(per non dire che non so farlo  .whistling)
Perchè in sostanza, dovrei leggere in input un elemento e praticamente il metodo add all'interno della lista vede in testa, nell'array gli elementi, li confronta, e in caso li shifta tutti, quindi se per esempio la dimensione 100 viene raggiunta io dovrei spostare gli elementi nell'altro nodo accanto?  .huh


Title: Re:Esercizio sugli array espandibili.
Post by: XDnl on 01-06-2010, 09:46:56
Quando ad esempio fai:

Code:
int ret = cognome.compareTo(person.getCognome());
Confronto il cognome della persona che sta invocando il metodo con quella tra parentesi?
Si.  .sisi

P.S. Io avrei pensato che ci voleva il this.
No.  .nono

Code:
int ret=this.cognome.compareTo......
Funziona anche in questo modo, comunque non è necessario usare la parola chiave this.

Invece per l'inserimento ordinato, io sto avendo molta confusione(per non dire che non so farlo  .whistling)
Perchè in sostanza, dovrei leggere in input un elemento e praticamente il metodo add all'interno della lista vede in testa, nell'array gli elementi, li confronta, e in caso li shifta tutti, quindi se per esempio la dimensione 100 viene raggiunta io dovrei spostare gli elementi nell'altro nodo accanto?  .huh
Si.  .sisi All'inizio avevo sbagliato anch'io, ordinando in modo separato gli array.
Supponiamo che la dimensione max. di ciascun array sia 2 ( :[Emoticon] Asd:) con 4 elementi da inserire:
A, C, D, B

Applicando il seguente algoritmo:
- Trova la prima lista che non è piena, altrimenti creane una nuova
- Inserisci l'elemento al posto giusto

Otteniamo i seguenti passi:
- [A, vuoto] (primo elemento inserito, lista creata)
- [A, C]
- [A, C] - [D, vuoto]
- [A, C] - [B, D]
Come vedi l'ordine degli elementi non è "globale" ma relativo ad ogni singolo array.
Per questo è necessario agire come hai detto tu (cioè cercare il posto giusto in TUTTI gli array, sia pieni che non, e agire di conseguenza).
Con il nuovo algoritmo avremmo i seguenti passi:
- [A, vuoto]
- [A, C]
- [A, C] - [D, vuoto]
- [A, B] - [C, D]
Come vedi adesso la configurazione è corretta. Ovviamente questa versione è più complessa, sono riuscito ad implementarla con un algoritmo ricorsivo.  :-)|


Title: Re:Esercizio sugli array espandibili.
Post by: Daréios89 on 01-06-2010, 11:37:43
Quote
Applicando il seguente algoritmo:
- Trova la prima lista che non è piena, altrimenti creane una nuova
- Inserisci l'elemento al posto giusto

 .penso

Una cosa, tu dici trova la prima lista libera sennò creane una nuova, ma non dovrei creare solo un nodo?
Cioè per esempio, il metodo add crea una lista se head è null, un nodo che prende come parametro un array (ListPerson) e inserisce l'elemento, se head non è null, faccio i confronti, e se lo spazio non basta inserisco dopo tail un altro nodo con un altro array, perchè creare un' altra lista?
Avrò capito male io...


Title: Re:Esercizio sugli array espandibili.
Post by: XDnl on 01-06-2010, 11:46:35
Quote
Applicando il seguente algoritmo:
- Trova la prima lista che non è piena, altrimenti creane una nuova
- Inserisci l'elemento al posto giusto

 .penso

Una cosa, tu dici trova la prima lista libera sennò creane una nuova, ma non dovrei creare solo un nodo?
Cioè per esempio, il metodo add crea una lista se head è null, un nodo che prende come parametro un array (ListPerson) e inserisce l'elemento, se head non è null, faccio i confronti, e se lo spazio non basta inserisco dopo tail un altro nodo con un altro array, perchè creare un' altra lista?
Avrò capito male io...
No scusami mi sono espresso male.  :pray
Intendevo dire crea un nuovo nodo contenente l'array di cento elementi.  :-OK


Title: Re:Esercizio sugli array espandibili.
Post by: Daréios89 on 01-06-2010, 14:30:31
Ahhh!!!!!
Per fortuna perchè già stavo entrando nel panico...poi già io non capisco le cose che sono giuste  .whistling
Lo sapresti se mi conoscessi di persona........( .penso  .huh  .huh  .huh).
Va bene ora vediamo che riesco a fare, ma.....ci provo in questo pomeriggio, anche se la vedo dura..  .rido


Title: Re:Esercizio sugli array espandibili.
Post by: Daréios89 on 02-06-2010, 18:13:09
Scusa ma ci sono altri problemi prima ancora del metodo add, non mi compilano le classi.

Code:
public interface OrderedSet <E extends Comparable> {
// ritorna true se l'insieme è vuoto
public boolean isEmpty();
// ritorna il numero di elementi contenuti nell'insieme
public int size();
// inserisce un nuovo elemento nell'insieme
public void add(E element);
// elimina il primo elemento di valore element
public void remove(E element);
// ritorna true se l'emento element è presente nell'insieme
public boolean isPresent(E element);
// ritorna l'elemento più piccolo dell'insieme
public E getFirst();
// ritorna l'elemento più grande dell'insieme
public E getLast();
// stampa la lista ordinata degli elementi dell'insieme
public String toString();
}

Code:
public interface Person extends Comparable{

public void setNome(String nome);
// setta il nome della persona
public void setCognome(String cognome);
// setta il cognome della persona
public void setAnni(int anni);
// setta l'età della persona
public String getNome();
// ritorna il nome della perona
public String getCognome();
// ritorna il cognome della persona
public int getAnni();
// ritorna l'età della persona
public int compareTo(Person person);
/* ritorna un valore maggiore di 0 se la persona ha un valore
più grande di person; 0 se hanno due valori uguali; un intero
minore di 0 altrimenti*/
}

Code:
public class ListOfArray <E extends Comparable> implements OrderedSet<E>


già qui: solo scrivendo l'intestazione e senza nulla nella classe.
Se non erro dava problemi anche se c'era tutto il corpo.

Code:
ListOfArray.java:1: ListOfArray is not abstract and does not override abstract method getLast() in OrderedSet
public class ListOfArray <E extends Comparable> implements OrderedSet<E>
       ^

E poi in

Code:
public class ListPerson implements Person
{
private String nome;
private String cognome;
private int anni;

public ListPerson(String nome, String cognome, int anni)
{
this.nome=nome;
this.cognome=cognome;
this.anni=anni;
}

public void setNome(String nome) {this.nome=nome;}

public void setCognome(String cognome) {this.cognome=cognome;}

public void setAnni(int anni){this.anni=anni;}

public String getNome(){ return nome;}

public String getCognome(){ return cognome;}

public int getAnni(){return anni;}

public int compareTo(Person person) throws ClassCastException
{
int ret = cognome.compareTo(person.getCognome());
if (ret != 0) return ret;

ret = nome.compareTo(person.getNome());
if (ret != 0) return ret;

return anni - person.getAnni();
}

}
Ho:

Code:
istPerson.java:1: ListPerson is not abstract and does not override abstract method compareTo(java.lang.Object) in java.lang.Comparable
public class ListPerson implements Person
       ^
1 error

Nom capisco che cosa manca...


Title: Re:Esercizio sugli array espandibili.
Post by: XDnl on 03-06-2010, 09:45:55
E' una pena questo esercizio eh?  :[Emoticon] PC Asd: :-)|  .rido
Quando estendi un'interfaccia, la classe in questione deve implementare tutti i suoi metodi.
Gli errori di compilazione sono dovuti a due motivi:

  • Metodi presenti nell'interfaccia, ma non implementati nella classe
Code:
ListOfArray.java:1: ListOfArray is not abstract and does not override abstract method getLast() in OrderedSet
public class ListOfArray <E extends Comparable> implements OrderedSet<E>
In questo caso OrderedSet<E> prevede un metodo getLast(), che evidentemente non hai implementato in ListOfArray<E extends Comparable>.

  • Firma del metodo non corrispondente alle specifiche dell'interfaccia

Devi fare molta attenzione quando implementi la classe, infatti basta anche una minima differenza con l'interfaccia per far "confondere" ( :-K) il compilatore.
Con questo metodo:
Code:
public class ListPerson implements Person
{
// ... omissis.... (commento perchè sennò dà errore   :-K)
public int compareTo(Person person) throws ClassCastException
{
int ret = cognome.compareTo(person.getCognome());
if (ret != 0) return ret;

ret = nome.compareTo(person.getNome());
if (ret != 0) return ret;

return anni - person.getAnni();
}
}
ottieni il seguente errore
Code:
ListPerson.java:1: ListPerson is not abstract and does not override abstract method compareTo(java.lang.Object) in java.lang.Comparable
public class ListPerson implements Person
1 error
perchè in realtà la firma del metodo compareTo prevede un parametro di tipo java.lang.Object, NON Person.
In particolare il compilatore considera differenti i due metodi e quindi è come se non stessi implementando il metodo compareTo dell'interfaccia, da cui l'errore.   .sisi

Quando estendi interfacce non tue, conviene sempre fare riferimento alla documentazione:
http://java.sun.com/j2se/1.4.2/docs/api/java/lang/Comparable.html#method_summary

 .ciaociao

Edit: Il nome "ListPerson" è un po' fuorviante perchè fa pensare ad una lista di persone, mentre in realtà è solo una.  Il compilatore non si confonderà per questo, ma una persona magari sì. .wink


Title: Re:Esercizio sugli array espandibili.
Post by: Daréios89 on 03-06-2010, 22:37:39
 .huh

Azz......adesso funziona, una parte...domani faccio il resto sperando funzioni tutto e ti faccio sapere.... ma non credere che te la caverai così facilmente  .rido

P.S, onde evitare di aprire un nuovo topic, mi chiedevo un altra cosa,noi gli alberi e gli alberi binari di ricerca li
abbiamo implementati in che modo?

Array o liste?


Title: Re:Esercizio sugli array espandibili.
Post by: aryanna on 05-06-2010, 09:12:35
Ho visto che già siete andati avanti... cmq io x si e x no vi posto il mio codice di compareTo anche se nn utilizzo la classe compare

Code:
public int compareTo(Person person){
if(this.getCognome().compareTo(person.getCognome())>0){
return 1;
}

if(this.getCognome().compareTo(person.getCognome())== 0){
if(this.getNome().compareTo(person.getNome())>0) return 1;

if (this.getNome().compareTo(person.getNome())== 0){
if(this.getAnni() > (person.getAnni())) return 1;
else return 0;
}
}
return -1;
}

in poche parole controlla prima il cognome e se sono uguali i due cognomi, va a vedere il nome e così via sino ad arrivare all'ultimo controllo relativo all'età


Title: Re:Esercizio sugli array espandibili.
Post by: Daréios89 on 05-06-2010, 13:38:33
Dovrebbe essere simile al nostro, o meglio quello che XDnl ha pensato  .rido

Io invece non sono riuscito a fare l'inserimento....mi confondo troppo....ci sono un sacco di problemi da gestire..
aryanna, l'hai fatto come hai postato qualche intervento fa? Senza avere problemi con i "tipi"?
Uff.....


Title: Re:Esercizio sugli array espandibili.
Post by: aryanna on 05-06-2010, 15:10:29
Sisi l'ho fatto come quello che ho postato, è un esercizio piuttosto tosto in effetti. devi prima avere in mente la struttura proprio di come devono essere qst nodi con gli array ecc ecc... così ti verrà già più semplice pia piano scrivere il codice


Title: Re:Esercizio sugli array espandibili.
Post by: XDnl on 05-06-2010, 15:48:48
Dovrebbe essere simile al nostro, o meglio quello che XDnl ha pensato  .rido

Io invece non sono riuscito a fare l'inserimento....mi confondo troppo....ci sono un sacco di problemi da gestire..
aryanna, l'hai fatto come hai postato qualche intervento fa? Senza avere problemi con i "tipi"?
Uff.....
Forza Daréios non ti arrendere!  :-OK
Dopo tutti questi post DEVI farlo funzionare  .rido

@aryanna: ma alla fine a te funziona il programma?


Title: Re:Esercizio sugli array espandibili.
Post by: Daréios89 on 05-06-2010, 20:10:43
Ho provato a scrivere qualcosa, che ancora non ho provato perchè devo correggere altri errori dovuti ai tipi.
Maledettissimi tipi.. :"-(
Però volevo sapere...insomma quanto di sbagliato c'è in quello che ho scritto nell'algoritmo add, poichè ho un modo di pensare molto contorto.... .rido

Intanto due metodi che ho creato....sperando che mi possano servire.

Code:
public boolean ArrayFull(int [] a)         //verifica se l'array è pieno
{
return (a[a.length-1]!=null);

}

public int getArrayIndex(int []a)      //restituisce l'indice dell'ultimo elemento
{
int index=0;
for(int i=0; i<a.length; i++)
{
if(a[i]!=null)
index++;
}
return index;
}



E poi la parte contorta...

Code:
public void add(E element)
{
if(size==0)
{
Persona[] vett=new Persona[CAPACITY];
vett[0]=(Persona)element;                                //Se la lista è vuota creo un nodo e inserisco nella prima posizione dell'array element
Node<E> node=new Node(vett);
head=node;

}

else if(size>0)
{
boolean inserito=false;

Node<E> node=head;

Persona []vett=(Persona[])node.getElement();


for(Node <E> node2=node; node!=null; node=node.getNext())
{
       int index=vett.getArrayIndex(this);

if(index!=vett.length-1)                       //Se l'array ha posti disponibili
{
for(int i=0; i<=index; i++)
{
if(vett[i].compareTo(element)<0)
{
for(int j=index+1; j>=i; j--)        //shifto gli elementi a destra
{
vett[j]=vett[j-1];               //inserisco nella posizione libera element
}

vett[i]=element;
inserito=true;
}

}

if(inserito==false)                          //Se nei confronti di prima element non è minore di nessuno lo inserisco alla fine di tutti perchè è più grande
{
vett[index+1]=element;
}
}

else                              //Se l'array è pieno
{
inserito=false;
Persona[] vett2=new Persona[CAPACITY];

for(int i=0; i<=index; i++)
{
if(vett[i].compareTo(element)<0)
{
vett2[0]=vett[index];                     //allora copio l'ultimo elemento in un nuovo array e shifto come prima gli altri valori
for(int j=index; j>=i; j--)         
{
vett[j]=vett[j-1];
}

vett[i]=element;
inserito=true;
}
}

if(inserito==false)
{
vett2[0]=element;                  //se element è maggiore di tutti allora dato che l'array è pieno lo metto in un nuovo array in posizione 0
inserito=false;
}
}

node2=node.getNext();          //continuo a scorre sulla lista per fare confronti...

}
}

size++;
}


Title: Re:Esercizio sugli array espandibili.
Post by: aryanna on 06-06-2010, 09:42:12
Si si, alla fine a me funziona. Ho visto il tuo add...in poche parole inserisci e nel frattempo ordini, x quello che capisco mi sembra giusto o meglio non mi è chiara una cosa... quando vedi che l'array è pieno ne crei un altro e ..? nn lo passi ad un nodo come fai nel caso iniziale qnd crei il primo array e fai
Code:
Node<E> node=new Node(vett);
comunque, aspettiamo lo stesso il parere di XDnl k è meglio!  :boh


Title: Re:Esercizio sugli array espandibili.
Post by: Daréios89 on 06-06-2010, 11:00:15
Azz.....si si certo, su tutto quel codice me ne ero dimenticato...dunque.....dovrei assegnare a un nuovo nodo e impostarlo come tail, sperando sia giusto:

Code:
else                              //Se l'array è pieno
{
inserito=false;
Persona[] vett2=new Persona[CAPACITY];

for(int i=0; i<=index; i++)
{
if(vett[i].compareTo(element)<0)
{
vett2[0]=vett[index];                     //allora copio l'ultimo elemento in un nuovo array e shifto come prima gli altri valori
for(int j=index; j>=i; j--)          
{
vett[j]=vett[j-1];
}

vett[i]=element;
inserito=true;
}
}

if(inserito==false)
{
vett2[0]=element;                  //se element è maggiore di tutti allora dato che l'array è pieno lo metto in un nuovo array in posizione 0
inserito=false;
}
}

Node<E> nuovo=new Node(vett2);
tail.setNext(nuovo);
tail=nuovo;
node2=node.getNext();          //continuo a scorre sulla lista per fare confronti...

}
}



 :boh

Nel frattempo cerco di risolvere gli altri problemi con i tipi.... .smile

Il problema è che ho fatto la classica classe Node:

Code:
public class Node<E>
{
private E element;
private Node<E> next;

public Node(E element)
{
this.element=element;
this.next=null;
}

public void setElement(E element){this.element=element;}

public E getElement(){ return element;}

public void setNext(Node<E> node){this.next=node;}

public Node<E> getNext(){return next;}

}




E mi dà errore nel metodo add stesso, un problema con i tipi:

Code:
public void add(E element)
{
if(size==0)
{
Persona[] vett=new Persona[CAPACITY];
vett[0]=(Persona)element;                                //Se la lista è vuota creo un nodo e inserisco nella prima posizione dell'array element
Node<E> node=new Node(vett);
head=node;

}

else if(size>0)
{
boolean inserito=false;

Node<E> node=head;

Persona []vett=(Persona[])node.getElement();      //errore   



 inconvertible types
found   : E
required: Persona[]
Persona []vett=(Persona[])node.getElement();



Però il cast lo faccio....


Title: Re:Esercizio sugli array espandibili.
Post by: XDnl on 06-06-2010, 17:53:19
Leggi i commenti:
Code:
public void add(E element)
{
// Suppongo tu abbia una cosa del genere nella classe ListOfArray<Person>:
// public Node<E> head;
// public int size;
// Pero' se tu crei una ListOfArray<Person> avrai E = Person e quindi
// public Node<Person> head; che è una lista di Person, non una lista di array di person :P
// Vabbè a parte questo...

// Se non ci sono liste allocate....
if (size==0)
{
// Creo un array
Persona[] vett=new Persona[CAPACITY];

// Imposto il primo elemento
// Solito discorso, element potrebbe essere qualunque cosa:
// public class CosaCheNonCentraNiente { ... }
// ListOfArray<CosaCheNonCentraNiente> lista;
// Se element non è di tipo Persona allora verrà lanciata l'eccezione java.lang.ClassCastException
// Vabbè a parte questo...
vett[0]=(Persona)element;

// Creo il nodo (discorso di prima, E sarebbe Person, non Person[])
// Dovresti fare una cosa del tipo Node<E[]> node = new Node(vett);
Node<E> node=new Node(vett);

// Imposto la testa
head = node;
}
else
// Se ci sono liste...
if (size > 0)
{
// Oddio che malo pezzo di codice O_O
// Ok vediamo... XD
boolean inserito=false;

// Memorizzo in vett il primo array di persone
Node<E> node=head;
Persona []vett=(Persona[])node.getElement();

// Per ogni array di person (Person[]) presente nella lista
// Hmmm
// Node <E> node2=node (inizializzi node2)
// node != null (il test lo fai su node)
// node = node.getNext() (modifichi node)
// hmmm... non dovrebbe essere
// for (Node <E> node2=node; node2!=null; node2=node2.getNext()) ?
for (Node <E> node2=node; node!=null; node=node.getNext())
{
// Calcolo l'indice del primo posto vuoto
int index=vett.getArrayIndex(this);

// Se questo indice non è fuori dall'array (ossia se ci sono posti disponibili)
// (hmmm dovrebbe essere if (index != vett.length), infatti vett.length - 1 è un indice valido!)
if (index != vett.length-1)
{
// Per ogni elemento (fino ad index)
for (int i = 0; i <= index; i++)
{
// Se l'elemento i-esimo viene prima di element (cioè la persona da inserire)
if(vett[i].compareTo(element)<0)
{
//shifto gli elementi a destra
// Se i = 0 e j = 0 quando fai vett[j] = vett[j - 1] ti dà IndexOutOfBoundsException
for(int j=index+1; j>=i; j--)       
{
vett[j]=vett[j-1];               
}

// inserisco nella posizione libera element
vett[i]=element;
inserito=true;
}
// Hmmm... continua a ciclare..
}

// Boh mi sono un po' perso in questa parte
if(inserito==false)                         
{
vett[index+1]=element;
}
}
else  // Se l'array è pieno
{
// Creo un nuovo vettore (ma questo lo fai per ogni vettore pieno che incontri??)
inserito=false;
Persona[] vett2=new Persona[CAPACITY];

for(int i=0; i<=index; i++)
{
if(vett[i].compareTo(element)<0)
{
vett2[0]=vett[index];                     //allora copio l'ultimo elemento in un nuovo array e shifto come prima gli altri valori
for(int j=index; j>=i; j--)         
{
vett[j]=vett[j-1];
}
// Copi i valori in vett2
// Ma poi inserisci element in vett[i]?
vett[i]=element;
inserito=true;
}
}

if(inserito==false)
{
// Qua invece inserisci in vett2
vett2[0]=element;                  //se element è maggiore di tutti allora dato che l'array è pieno lo metto in un nuovo array in posizione 0
inserito=false;
}
}

// Crei un nodo con l'array vett2 inserendolo in coda
Node<E> nuovo=new Node(vett2);
tail.setNext(nuovo);
tail=nuovo;

// Sposti node2 (boh, con il ciclo for che hai scritto serve, con quello suggerito da me no)
node2=node.getNext();          //continuo a scorre sulla lista per fare confronti...
}
}

// Incremento size
// Ora: size indica il numero di elementi inseriti oppure il numero di elementi presenti nella lista linkata?
size++;

// Conclusione: BOH. Non ho capito bene la logica del programma, in ogni caso non credo funzioni.
// Il discorso è semplice: hai una lista di array.
// Cioè una lista dove ogni nodo contiene un array(di dimensione fissa, pari a CAPACITY) di elementi di E
// Node<E> non è quello che ti serve, in quanto è una lista di elementi di E
// Ti serve una lista di array di E ossia Node<E[]>
// Devi dividere l'algoritmo di inserimento in due passi:
// 1) Trovare tra TUTTE le liste allocate il posto giusto in cui inserire l'elemento (senza fare allocazioni, nè modifiche)
// 2) Puoi avere due casi:
// L'array in questione non ha abbastanza spazio per il nuovo elemento: questo è il caso piu' difficile, perchè devi shiftare tutti gli eleementi della liste successive
// L'array in questione ha spazio per il nuovo elemento: devi shiftare a destra tutti gli elementi successivi al posto giusto ed inserire l'elemento nel punto.
}


Title: Re:Esercizio sugli array espandibili.
Post by: Daréios89 on 07-06-2010, 13:30:18
Mh........bè ma classe ListOfArray io l'avevo messa E, in effetti nel testo mi pare è specificato sia da mettere come ListOfArray<Person>.

Per il resto più tardi provo, ora penso farò analisi.....del sangue :-K

Per il resto, dici che secondo te non funziona, pensavo di esserci andato vicino però, di shiftare gli elementi nei nuovi array di un nuovo nodo, oppure seplicemente di aggiungerli nello stesso array....................vabbè.