[JAVA] File d'attente...

Recherche :

Dernière réponse
Sujet : [JAVA] File d'attente...
benou	bon, la première vresion que j'ai donnée était pas terrible : déjà, elle marchait pas bien pour certaines méthodes et puis j'avais utilisée une variable full inutile. Comme quoi, faut pas faire de la programmation pendant qu'on regarde un épisode d'Urgence ;) voilà la v2, qui marche, qui est extensible, et qui a été faite apres urgence : public class File { protected Object[] tab; protected int begin, end; protected File ext; public File () { this(10); } public File (int initialCapacity) { tab = new Object[initialCapacity]; begin = 0; end = 0; } public void put(Object o) { if (tab[end]!=null) { if (ext == null) ext = new File((tab.length==0)?10:tab.length*2); ext.put(o); } else { tab[end] = o; end = (end+1)%tab.length; } } public boolean empty() { return tab[begin]==null; } public boolean full() { return tab[end]!=null; } public Object get() { if (empty()) throw new Error("File empty " ); Object o = tab[begin]; if ((ext != null) && (! ext.empty())) { tab[begin]=ext.get(); begin = (begin+1)%tab.length; end = (end+1)%tab.length; } else { tab[begin]=null; begin = (begin+1)%tab.length; } return o; } public int size() { int res = (ext==null)?0:ext.size(); if ((begin<=end) && (!full())) res+= end - begin; else res+= (tab.length - begin) + end; return res; } }

Dernière réponse

Sujet : [JAVA] File d'attente...

benou

bon, la première vresion que j'ai donnée était pas terrible : déjà, elle marchait pas bien pour certaines méthodes et puis j'avais utilisée une variable full inutile.

Comme quoi, faut pas faire de la programmation pendant qu'on regarde un épisode d'Urgence ;)

voilà la v2, qui marche, qui est extensible, et qui a été faite apres urgence :

public class File {

protected Object[] tab;
protected int begin, end;
protected File ext;

public File () {
this(10);
}

public File (int initialCapacity) {
tab = new Object[initialCapacity];
begin = 0;
end = 0;
}

public void put(Object o) {
if (tab[end]!=null) {
if (ext == null)
ext = new File((tab.length==0)?10:tab.length*2);
ext.put(o);
} else {
tab[end] = o;
end = (end+1)%tab.length;
}
}

public boolean empty() {
return tab[begin]==null;
}

public boolean full() {
return tab[end]!=null;
}

public Object get() {
if (empty())
throw new Error("File empty " );
Object o = tab[begin];
if ((ext != null) && (! ext.empty())) {
tab[begin]=ext.get();
begin = (begin+1)%tab.length;
end = (end+1)%tab.length;
} else {
tab[begin]=null;
begin = (begin+1)%tab.length;
}
return o;
}

public int size() {
int res = (ext==null)?0:ext.size();
if ((begin<=end) && (!full()))
res+= end - begin;
else
res+= (tab.length - begin) + end;
return res;
}

}

Votre réponse

Nom d'utilisateur

Pour poster, vous devez être inscrit sur ce forum .... si ce n'est pas le cas, cliquez ici !

Le ton de votre message

Votre réponse

Smilies

Liste des smilies perso
Wiki smilies
Chercher un smiley

Options

Activer votre signature
Désactiver les smilies
Activer la notification par email du sujet

Aperçu

Vous avez perdu votre mot de passe ?

Vue Rapide de la discussion

benou

désolé pour le tps pour la réponse ...

ca c'est pour la version à taille fixe :

public class File {

protected Object[] tab;
protected int begin, end;
protected boolean full;

public File (int size) {
tab = new Object[size];
begin = 0;
end = 0;
full = (size==0);
}

public void put(Object o) {
if (full)
throw new Error("File full " + tab.length);
tab[end] = o;
end = (end+1)%tab.length;
if (begin==end)
full = true;
}

public boolean empty() {
return (begin==end) && (!full);
}

public boolean full() {
return full;
}

public Object get() {
if (empty())
throw new Error("File empty " );
full = false;
Object o = tab[begin];
begin = (begin+1)%tab.length;
return o;
}

public String toString () {
if (empty())
return "File vide";
String s="";
for (int i=begin; i != end; i=(i+1)%tab.length)
s+="\n" + i + " : " + tab[i];
return s;
}

public int size() {
if (begin < end)
return end - begin;
else
return (begin - tab.length) + end;
}

public static void main(String[] args) {
File f = new File(3);
f.put("coucou" );
f.put("beuh" );
System.out.println(f.get());
f.put("tralala" );
f.put("pouetpouet" );
System.out.println(f.get());
System.out.println(f.get());
f.put("tchoutchou" );
}
}

belzme

BOn j'ai réussi à faire ceci , par contre ça ne marche pas, vs pouvez me dire pourquoi ?

public class File {
private final int DIMENSION_DEFAUT = 3;
private int augmenter = 0;
private int tableau[];
private int sommet;
private int debut = 0;
private int fin = 0;
private int longueur = 0;

public void initialise(int dimension) {
if (dimension < 0)
throw new RuntimeException("dimension de pile invalide" );
tableau = new int[dimension];
sommet = tableau.length - 1;
}

public File() {
initialise(DIMENSION_DEFAUT);
}

public File(int dimension) {
initialise(dimension);
augmenter = 1;
}

public File(int dimension, int augmentation){
initialise(dimension);
augmenter = augmentation;
}

public void enfiler(int valeur) {
if (estPleine())
if (augmenter == 0)
throw new RuntimeException("la file est pleine!" );
else
augmenter();
fin = (fin +1) % capacite();
tableau[fin] = valeur;
longueur++;
}

public void augmenter() {
int temp[] = new int[capacite() + augmenter];
for (int i = 0; i < capacite(); i++) {
temp[i] = tableau[debut];
debut = (debut +1) % capacite();
}
debut = 0;
fin = capacite() - 1;
tableau = temp;

}

public int defiler() {
if (estVide())
throw new RuntimeException("on défile une file vide" );
return tableau[debut];
debut = (debut +1) % capacite();
longueur--;

}

public boolean estPleine() {
return longueur == capacite();
}

public boolean estVide() {
return longueur == 0;
}

public int capacite() {
return tableau.length;
}

}

belzme

J'ai réusis à faire cela, est-ce bon ?

public void enfiler(int valeur) {
if (estPleine())
if (augmenter == 0)
throw new RuntimeException("la file est pleine!" );
else
augmenter();
fin = (fin +1) % capacite();
tableau[fin] = valeur;

et :

public int defiler() {
if (estVide())
throw new RuntimeException("on défile une file vide" );
return tableau[debut];
debut = (debut +1) % capacite();

EstVide() étant :
return debut == fin;

Parcontre je ne sais pas quoi faire pour estPleine()... :(

belzme

ok je comprend ... mais je comprend pas comment l'appliquer...

tu peux justem edonner l'exemple de la méthode enfiler() ou encore defiler() ?. Juste 1 pour que je comprenne le principe car j'arrive pas a visualiser comment utiliser le modulo ...

Merci bcp :)

edit : Je comprend comment vérifier si la pile est vide (debut ==fin) mais comment je vérifie si elle est pleine?

[edtdd]--Message édité par BelzME--[/edtdd]

benou

ouais je comprend et c'est pour ca que je disais que tu devais incrémenter modulo la taille du tableau.

il ne faut pas faire simplement un ++i, mais un (++i)%tableau.length

en fesant ca, c'est circulaire. d'ailleur c'est la façon de faire une file sans allouer et désalouer de la mémore sans arret !

belzme

OK merci bcp , parcontre le problème c'est que cette file doit être circulaire ...

Explication :

Une file de taille 3 :

position dans le tableau 0 1 2

Il faudrait que si 0 1 2 soit tous occupé, si la la position #0 du tableau ce libère, que le prochain client (dans mon cas) soit stocké à la position 0 et que se soit le client à la position 1 qui soit défiler le prochain coup...

donc l'orde de ma file (en ordre du premier à sortir) 1 2 0...

Tu comprend ce que je veux dire ?

benou

ben déjà tu dois pas utiliser une pile ...

la 1ere question à teposer c'est est ce que tu peux définir une taille maximale pour ta File. Si oui, c'est plus simple.

Dans ce cas, tu peux utiliser un tableau de cette taille maximale. Tu utilise en suite 2 entiers. le premier (begin) pour dire où commence ta file dans le tableau, le deuxième (end) où il se termine.

au départ (la file est vide)
les 2 entiers valent 0.

pour empiler, tu incrémentes end, et tu stockes le nouvel objet a cet endroit : tableau[++end] = objet

pour dépiler, tu mets l'objet dans le tableau à l'index begin à null puis tu incrémentes begin : return tableau[begin++];

Bien sur, tes incrémentations doivent être modulo la taille du tableau, il faut que tu ne retourne pas de valeur nulle (cas de la file vide) et il faut que tu n'écrive pas dans ton tableau sur une valeur non nulle (cas du tableau plein).

ensuite, s'il faut que ta file soient "extensible", une solution simple est d'utiliser une File à l'intérieur de ta file : quand ta file est pleine et que tu dois ajouter des trucs dedans, tu les mets dans la "sous-file". quand la "sous-file" est non vide et que tu dois retirer un truc de ta file, tu fais comme d'habitude, mais en plus tu retire un objet de la "sous-file" et tu le met à l'endroit d'où tu viens de retirer l'objet de ta file.
L'avantage de cette technique, c'est que c'est pas trop compliqué à coder (3 ou 4 lignes de plus) et que c'est récursif => ta file est extensible à l'infinie ;)

belzme

Voila je doit faire une classe nommé File, je me base sur une classe Pile que j'ai déja faite et qui ce trouve plus bas. Je doit la transformer en file circulaire en utilisant modulo, parcontre j'ai aucune idée de la façon dont je doit m'y prendre ... ^surtout pour la méthode enfiler et la méthode défiler...

Voici ma méthode Pile :

Citation :

public class Pile {
private final int DIMENSION_DEFAUT = 3;
private int augmenter = 0;
private int tableau[];
private int sommet;

public void initialise(int dimension) {
if (dimension < 0)
throw new RuntimeException("dimension de pile invalide" );
tableau = new int[dimension];
sommet = tableau.length - 1;
}

public Pile() {
initialise(DIMENSION_DEFAUT);
}

public Pile(int dimension) {
initialise(dimension);
augmenter = 1;
}

public Pile(int dimension, int augmentation){
initialise(dimension);
augmenter = augmentation;
}

public void empiler(int valeur) {
if (estPleine())
if (augmenter == 0)
throw new RuntimeException("on dépile une pile vide" );
else
augmenter();
tableau[sommet] = valeur;
sommet--;
}

public void augmenter() {
int temp[] = new int[capacite() + augmenter];
for (int i = capacite()-1; i > sommet; i--)
temp[i+augmenter] = tableau[i];
tableau = temp;
sommet = sommet +augmenter;
}

public int depiler() {
if (estVide())
throw new RuntimeException("on dépile une pile vide" );
return tableau[++sommet];
}

public boolean estPleine() {
return sommet == -1;
}

public boolean estVide() {
return sommet == tableau.length;
}

public int capacite() {
return tableau.length;
}

public int nbElements() {
return capacite() - (sommet+1);
}

public String toString() {
String retour = "Capacité : " + capacite() + " Nombre d'éléments : "
+ nbElements() + " Éléments : ";
for (int i = sommet+1; i < capacite(); i++) {
retour += ' ';
retour += tableau[i];
}
return retour;
}
}