Création de liste chainée à la volée

Partagez votre expérience de PureBasic avec les autres utilisateurs.
nico
Messages : 3702
Inscription : ven. 13/févr./2004 0:57

Création de liste chainée à la volée

Message par nico »

J'ai pondu une lib afin de pouvoir créer des listes chainées comme on veut!

Cette lib permet de faire des listes chainées simple; c'est pour cela qu'il n'y a pas de PreviousElement() par exemple.

Code source de la Lib:

Code : Tout sélectionner

 ;/ Les fonctions:
;----------------------------
;/ CreateList(size.l)   crée une nouvelle liste chainée et renvoie un index 
;/                      et retourne la référence de la liste 
;/ Count_Element()      compte le nombre d'élément
;/ First_Element()      renvoie le premier élément
;/ Current_element()    renvoie l'élément courant 
;/ Next_Element()       élément suivant 
;/ Delete_element()     éfface l'élément courant 
;/ DestructList()       détruit la liste chainée courante
;/ UseList(index.l)     la liste de cette index devient la liste courante 
;----------------------------
;----------------------------

ProcedureDLL CreateList_Init() 
  Structure _liste
    *Pointeur_debut
    *Pointeur_fin 
    *pointeur_courant
    size_struct.l
    flag.b
    count.l
    index.l 
  EndStructure 
  
  NewList liste._liste()
  Global index_courant.l 
EndProcedure 
 
Procedure FindList(ref.l)
  ForEach liste()
    If liste()\index=ref
      ProcedureReturn 1
    EndIf 
  Next
  ProcedureReturn 0
EndProcedure 
  
ProcedureDLL CreateList(size.l)
  Static index.l
  index=index+1
  AddElement(liste())
  liste()\index=index
  liste()\size_struct = size + 4
  liste()\Pointeur_debut=0
  liste()\Pointeur_fin=0
  liste()\flag=0
  liste()\count=0
  index_courant=index
  ProcedureReturn index
EndProcedure 

ProcedureDLL Add_Element()
  If FindList(index_courant)
    *nouveau=AllocateMemory(liste()\size_struct) 
    If liste()\Pointeur_debut=0
      liste()\count=0
      liste()\Pointeur_debut=*nouveau + liste()\size_struct - 4
    Else
      PokeL(liste()\Pointeur_fin,*nouveau)
    EndIf
    liste()\count=liste()\count+1
    liste()\Pointeur_fin=*nouveau + liste()\size_struct - 4
    PokeL(liste()\Pointeur_fin, 0)
    liste()\pointeur_courant=liste()\Pointeur_fin
    ProcedureReturn *nouveau 
  EndIf 
  ProcedureReturn 0
EndProcedure   
 
ProcedureDLL First_Element()
  If FindList(index_courant)
    If liste()\Pointeur_debut<>0
      liste()\flag=0
      liste()\pointeur_courant=liste()\Pointeur_debut
      ProcedureReturn liste()\Pointeur_debut - liste()\size_struct + 4
    EndIf
  EndIf 
  ProcedureReturn 0
EndProcedure

ProcedureDLL Current_Element()
  If FindList(index_courant)
    If liste()\pointeur_courant<>0
      ProcedureReturn liste()\pointeur_courant - liste()\size_struct + 4
    EndIf 
  EndIf 
  ProcedureReturn 0
EndProcedure
   
ProcedureDLL End_Element()
  If FindList(index_courant)
    If liste()\Pointeur_fin
      liste()\pointeur_courant=liste()\Pointeur_fin
      ProcedureReturn liste()\Pointeur_fin - liste()\size_struct + 4
    EndIf 
  EndIf 
  ProcedureReturn 0
EndProcedure

ProcedureDLL Next_Element()
  If FindList(index_courant)
    If liste()\flag=0
      suivant=PeekL(liste()\pointeur_courant)
      If suivant <> 0
        liste()\pointeur_courant = suivant + liste()\size_struct - 4
        ProcedureReturn suivant
      EndIf 
    Else
      liste()\flag=0
      If liste()\Pointeur_debut <> 0
        ProcedureReturn liste()\Pointeur_debut - liste()\size_struct + 4
      EndIf 
    EndIf
  EndIf 
  ProcedureReturn 0
EndProcedure

ProcedureDLL Delete_element()
  If FindList(index_courant)
    If liste()\Pointeur_debut<>0
      *pointeur=liste()\Pointeur_debut
      Select liste()\pointeur_courant
        Case liste()\Pointeur_debut
          If PeekL(*pointeur)<>0
            liste()\Pointeur_debut=PeekL(*pointeur)+ liste()\size_struct-4
            *memory=liste()\pointeur_courant - liste()\size_struct + 4
            liste()\pointeur_courant=liste()\Pointeur_debut
            liste()\count=liste()\count-1
          Else
            *memory=liste()\pointeur_courant - liste()\size_struct + 4
            liste()\Pointeur_debut=0:liste()\Pointeur_fin=0:liste()\pointeur_courant=0
            liste()\count=0
          EndIf 
          liste()\flag=1
          
        Default
          While *pointeur
            If liste()\pointeur_courant=PeekL(*pointeur)+ liste()\size_struct - 4
              *Pointeur_precedent=*pointeur
              If liste()\Pointeur_fin=liste()\pointeur_courant
                liste()\Pointeur_fin=*Pointeur_precedent
              EndIf 
              *memory=liste()\pointeur_courant - liste()\size_struct + 4
              Break 
            EndIf
            *pointeur=PeekL(*pointeur)+ liste()\size_struct - 4 
          Wend
          PokeL(*Pointeur_precedent,PeekL(liste()\pointeur_courant))
          *memory=liste()\pointeur_courant - liste()\size_struct + 4
          liste()\pointeur_courant=*Pointeur_precedent
          liste()\count=liste()\count-1
      EndSelect 
      
      If *memory
        If FreeMemory(*memory)
          ProcedureReturn 1
        EndIf
      EndIf
      
    EndIf 
  EndIf 
  ProcedureReturn 0 
EndProcedure

ProcedureDLL UseList(ref.l)
  If FindList(ref)
    index_courant=ref
    ProcedureReturn 1
  EndIf 
  ProcedureReturn 0
EndProcedure 
  
ProcedureDLL DestructList()
    *liste=First_Element()
    While *liste
      Delete_element()
      *liste=Next_Element()
    Wend
  ProcedureReturn 1
EndProcedure 

ProcedureDLL Count_Element() 
  If FindList(index_courant)
    ProcedureReturn liste()\count
  EndIf 
  ProcedureReturn 0
EndProcedure 
  
ProcedureDLL CreateList_End() 
    ForEach liste()
      If UseList(liste()\index)
        DestructList()
      EndIf 
    Next 
EndProcedure 

Exemple d'utilisation:

Code : Tout sélectionner

 Structure liste 
  valeur.l 
EndStructure 

index1=CreateList(SizeOf(liste)) 

*liste.liste=Add_Element() 
*liste\valeur=11 

*liste=Add_Element() 
*liste\valeur=11 

*liste=Add_Element() 
*liste\valeur=22 

*liste=Add_Element() 
*liste\valeur=33 

*liste=Add_Element() 
*liste\valeur=44 

Debug Count_Element() 

Delete_element() 
Delete_element() 


*liste=First_Element() 
While *liste 
  If *liste\valeur=11 
    Delete_element() 
  EndIf 
  *liste=Next_Element() 
Wend 
; 
Debug "---------------" 



*liste=Add_Element() 
*liste\valeur=55 

Debug "---------------" 

*liste=First_Element() 
While *liste 
  Debug *liste\valeur 
  *liste=Next_Element() 
Wend 

Debug "---------------" 
DestructList() 

Telecharger la Lib:
http://home.tele2.fr/purebasic/Liste_chainee_lib.zip

:)
Dernière modification par nico le mer. 20/juil./2005 10:20, modifié 9 fois.
nico
Messages : 3702
Inscription : ven. 13/févr./2004 0:57

Message par nico »

Comme on ne peut pas utiliser de variable de type chaine dans une structure pour cette Lib, il faut opérer come ceci:

Code : Tout sélectionner

 Structure liste 
  Nom.b[12] 
  age.l 
EndStructure 

index1=CreateList(SizeOf(liste)) 

*liste.liste=Add_Element() 
PokeS(@*liste\Nom[0],"jerome",Len("jerome")) 
*liste\age=22 

*liste.liste=Add_Element() 
PokeS(@*liste\Nom[0],"jean",Len("jean")) 
*liste\age=25 

*liste.liste=Add_Element() 
PokeS(@*liste\Nom[0],"stephane",Len("stephane")) 
*liste\age=25 

Debug Count_Element() 
Debug "" 

*liste=First_Element() 
While *liste 
  Debug PeekS(@*liste\Nom[0]) 
  Debug *liste\age 
  *liste= Next_Element() 
Wend 

Debug "---------------" 

DestructList() 
Dernière modification par nico le mer. 20/juil./2005 1:34, modifié 1 fois.
nico
Messages : 3702
Inscription : ven. 13/févr./2004 0:57

Message par nico »

J'ai mis à jour la lib avec une correction d'un bug et l'ajout de la fonction :
Current_Element(index).

Le lien pour télécharger la lib prend en compte ces modifications.
Le Soldat Inconnu
Messages : 4312
Inscription : mer. 28/janv./2004 20:58
Localisation : Clermont ferrand OU Olsztyn
Contact :

Message par Le Soldat Inconnu »

Ca peux être utile, ça ;)

Merci
Je ne suis pas à moitié Polonais mais ma moitié est polonaise ... Vous avez suivi ?

[Intel quad core Q9400 2.66mhz, ATI 4870, 4Go Ram, XP (x86) / 7 (x64)]
nico
Messages : 3702
Inscription : ven. 13/févr./2004 0:57

Message par nico »

Oui, je l'ai créé car j'en avais besoin pour ma prochaine Lib MenuBar.

Je me demande si je devrais pas supprimer le paramètre index des fonctions et créer une fonction Use_Index(index); ainsi on n'aurait pas forcément besoin de passer en paramètre la référence de la liste.

Ce qui donnerait:
;/ CreateList(size.l)------crée une nouvelle liste chainée
;/----------------------------et retourne la référence de la liste
;/ Next_Element()--------élément suivant
;/ Delete_element()-----éfface l'élément courant
;/ DestructList()----------détruit la liste chainée
;/ Count_Element()------compte le nombre d'élément
;/ Current_element()----renvoie le pointeur courant
;/ UseList(index.l)--------la liste de cette index devient la liste courante

Qu'est - ce que t'en penses?
Dr. Dri
Messages : 2527
Inscription : ven. 23/janv./2004 18:10

Message par Dr. Dri »

C'est de là que venait la question sur les chaines libérées ou non ?
Je vois le truc ^^
Si ca t'intéresse je met mon code à jour, il est plus optimal que celui que j'avais posté
http://purebasic.hmt-forum.com/viewtopic.php?t=2154

Dri
nico
Messages : 3702
Inscription : ven. 13/févr./2004 0:57

Message par nico »

Il y a un problème avec le code mais je n'arrive pas à déterminer où il se situe. :twisted:
nico
Messages : 3702
Inscription : ven. 13/févr./2004 0:57

Message par nico »

J'ai remis en ligne et mis à jour le nouveau code qui prend en compte mon interrogation.
:D soulagement.

Dr Dri,
Je ne veux pas me tromper une seconde fois, mais ton code n'est pas fini si on souhaite créer des listes à la volée comme ceci:

Première liste
index1=CreateList(SizeOf(liste))

Deuxième liste
index2=CreateList(SizeOf(liste))
Dr. Dri
Messages : 2527
Inscription : ven. 23/janv./2004 18:10

Message par Dr. Dri »

bah si justement ^^

Code : Tout sélectionner

liste_de_longs  = CreerListe( SizeOf(Long) )
liste_de_coords = CreerListe( SizeOf(Coord) )
C'est justement dans le même but que j'ai codé ces fonctions...

Dri
nico
Messages : 3702
Inscription : ven. 13/févr./2004 0:57

Message par nico »

Si tu pouvais faire un exemple d'utilisation, ça me permettrait d'y voir plus clair, y a des choses que je ne comprend pas. :roll:
Dr. Dri
Messages : 2527
Inscription : ven. 23/janv./2004 18:10

Message par Dr. Dri »

pas de problème, j'en fais un et je poste ;)

Dri
Dr. Dri
Messages : 2527
Inscription : ven. 23/janv./2004 18:10

Message par Dr. Dri »

Voila un petit exemple, qui bien sûr ne fait pas le tour des fonctions...

Code : Tout sélectionner

;création des listes
liste_de_longs  = CreerListe( SizeOf(Long) )
liste_de_coords = CreerListe( SizeOf(Coord) )

;on va remplir avec des valeurs aléatoires
RandomSeed( ElapsedMilliseconds() )

;On a besoin de variables temporaires pour ajouter les valeurs...
tmp_long.l
tmp_coord.coord

For i = 1 To 10
  tmp_long = Random(1000)
  AjouterElement(liste_de_longs, @tmp_long)
  
  tmp_coord\x = tmp_long
  
  tmp_long = Random(1000)
  AjouterElement(liste_de_longs, @tmp_long)
  
  tmp_coord\y = tmp_long
  AjouterElement(liste_de_coords, @tmp_coord)
Next i

;Une de mes fonctions simule un ForEach
;Elle nécessite une procédure callback
Procedure DebugLong(*ptr.Long)
  Debug *ptr\l
EndProcedure

Procedure DebugCoord(*ptr.Coord)
  Debug "x : " + Str(*ptr\x)
  Debug "y : " + Str(*ptr\y)
EndProcedure

;On debug les valeurs maintenant
Debug "liste_de_longs : " + Str( CardinalListe(liste_de_longs) ) + " élément(s)"
PourChaqueElement( liste_de_longs, @DebugLong() )

Debug "liste_de_coords : " + Str( CardinalListe(liste_de_coords) ) + " élément(s)"
PourChaqueElement( liste_de_coords, @DebugCoord() )
Dri ;)
nico
Messages : 3702
Inscription : ven. 13/févr./2004 0:57

Message par nico »

Je comprend mieux maintenant. :)

Ton code est très complet, il peut être intéressant d'utiliser l'une ou l'autre suivant ses besoins. Par exemple, ma lib n'utilise qu'une fonction qui utilise un paramètre unique, c'est pratique à l'usage.

Code : Tout sélectionner

 Structure liste 
  valeur.l 
EndStructure 

index1=CreateList(SizeOf(liste)) 
index2=CreateList(SizeOf(liste)) 

UseList(index1)
*liste.liste=Add_Element() 
*liste\valeur=11 

*liste=Add_Element() 
*liste\valeur=22 

*liste=Add_Element() 
*liste\valeur=33

UseList(index2)
*liste.liste=Add_Element() 
*liste\valeur=1111

*liste=Add_Element() 
*liste\valeur=2222

*liste=Add_Element() 
*liste\valeur=3333 

UseList(index1)
*liste=First_Element()
While *liste
  Debug *liste\valeur  
  *liste= Next_Element()
Wend
Debug "---------------"

UseList(index2)
*liste=First_Element()
While *liste
  Debug *liste\valeur  
  *liste= Next_Element()
Wend
Debug "---------------"
:)
Dr. Dri
Messages : 2527
Inscription : ven. 23/janv./2004 18:10

Message par Dr. Dri »

La facon dont j'ai codé mes fonctions permettent d'en faire une interface, mais je ne l'ai pas encore codé... C'était censé être l'étape suivante ^^
L'idée du UseList() est bien (dans la lignée des UseBidule() de PB) mais je n'ai jamais accroché à cette facon de procéder... Pas pratique pour les images et fichiers par exemple...

Dri
nico
Messages : 3702
Inscription : ven. 13/févr./2004 0:57

Message par nico »

Ben mon problème était de pouvoir créer une liste chaînée utilisable dans une lib fonctionnant avec les interfaces.

Je voulais pour chaque instanciation, pouvoir disposer d'une liste chaînée unique.


Ce qui donnerait par exemple:

Code : Tout sélectionner

procédure test(*this, a.l, b.l)

UseList(*this\index)
;ensuite on peut utiliser les fonctions sans se compliquer.
;/
;/
EndProceure 
Répondre