Structure récursive & Hiérarchie

[falsam]

Une structure qui fait référence à elle même pour former une liste de nodes. C'est cette astuce qu'on utilisera pour arriver à établir un exemple de hiérarchie.

■ Principe de fonctionnement.
Un node peut contenir une ou plusieurs variables ainsi qu'une liste de nodes.
Chacun de ces nodes de la liste contiendra une liste de nodes.
Chacun de ces nodes de la liste contiendra une liste de nodes.
etc ...

Code : Tout sélectionner

Structure NewNode
  Texte.s
  List Nodes.NewNode()
EndStructure
Global NewList Nodes.NewNode()

■ Exemple.
Nous allons créer des types de véhicules (terrestres & marins). Pour chacun des types on va inséré des véhicules et sur un des véhicules nous allons insérer une motorisation.

Code : Tout sélectionner

Structure NewNode
  Texte.s
  List Nodes.NewNode()
EndStructure
Global NewList Nodes.NewNode()

Procedure AddNode(Texte.s,*Node.NewNode=0)
  Protected Result
  
  If *Node
    Result = AddElement(*Node\Nodes())
    *Node\Nodes()\Texte = Texte
  Else
    Result = AddElement(Nodes())
    Nodes()\Texte = Texte
  EndIf   
  ProcedureReturn Result 
EndProcedure

Procedure ListNodes(List Nodes.NewNode())
  Static pre.s = "="
  ForEach Nodes()
    Debug pre + "> " + Nodes()\Texte  
    ForEach Nodes()\Nodes()
      pre + "="
      ListNodes(Nodes()\Nodes())
    Next
  Next
  pre = "="
EndProcedure

;// Test Zone

; Création de la hiérachie 
Terrestre = AddNode("Véhicules terrestres")

AddNode("Trotinettes", Terrestre)
AddNode("Vélos", Terrestre)

Voitures = AddNode("Voitures", Terrestre)

AddNode("Electriques", Voitures)
AddNode("Thermiques ", Voitures)

Marins = AddNode("Véhicules marins")
AddNode("Barques", Marins)
AddNode("Voiliers", Marins)
AddNode("Paquebots", Marins)

; Visualisation du résultat
ListNodes(Nodes())

le résultat devrait être le suivant.

=> Véhicules terrestres
==> Trotinettes
==> Vélos
==> Voitures
===> Electriques
===> Thermiques
=> Véhicules marins
==> Barques
==> Voiliers
==> Paquebots

[falsam]

Représentation visuelle de la hiérarchie. (Dessin classique dans un canvas)

Code : Tout sélectionner

EnableExplicit

Structure NewNode
  Texte.s
  x.i
  y.f
  List Node.NewNode()
EndStructure
Global NewList Nodes.NewNode()

Global rx, ry, nx0, ny0, nx1, ny1 

;Plan de l'application
Declare Start()
Declare AddNode(Texte.s, x.i, y.i, *Node.NewNode=0)
Declare Draw(List Nodes.NewNode())
Declare Exit()

Start()

Procedure Start()
  Protected Value, ww = 800, wh = 700
  
  OpenWindow(0, 0, 0, ww, wh, "Structure recursive et hierachie", #PB_Window_SystemMenu|#PB_Window_ScreenCentered)
  CanvasGadget(0, 0, 0, ww, wh)
  
  ; Création de la hiérachie
  Value = AddNode("Véhicules terrestres", 100, 50)
  AddNode("Trotinettes", 300, 150, Value)
  
  Value = AddNode("Voitures", 250, 250, Value)
  AddNode("Electriques", 500, 350, Value)
  AddNode("Thermiques", 400, 400, Value)
  
  Value = AddNode("Marins", 100, 450)
  AddNode("Barques", 400, 520, Value)
  AddNode("Voiliers", 330, 580, Value)
  AddNode("Paquebots", 230, 630, Value)
  
  ; Dessin des nodes 
  If StartDrawing(CanvasOutput(0))  
    Box(0, 0, ww, wh, RGB(211, 211, 211))
    Draw(Nodes())
    StopDrawing()
  EndIf
  
  ;Triggers
  BindEvent(#PB_Event_CloseWindow, @Exit())
  
  Repeat : WaitWindowEvent() : ForEver
EndProcedure

Procedure AddNode(Texte.s, x.i, y.i, *Node.NewNode=0)
  Protected Result
  
  If *Node
    Result = AddElement(*Node\Node())
    *Node\Node()\Texte = Texte
    *Node\Node()\x = x
    *Node\Node()\y = y
  Else
    Result = AddElement(Nodes())
    Nodes()\Texte = Texte
    Nodes()\x = x
    Nodes()\y = y   
  EndIf   
  ProcedureReturn Result 
EndProcedure

Procedure Draw(List Nodes.NewNode())   
  Static First 
  
  ForEach Nodes()        
    nx1 = Nodes()\x
    ny1 = Nodes()\y
    
    DrawingMode(#PB_2DDrawing_Default)
    Box(nx1, ny1, 200, 30, RGB(255, 215, 0))
    
    DrawingMode(#PB_2DDrawing_Outlined)
    Box(nx1, ny1, 200, 30, RGB(0, 0, 0))
    
    DrawingMode(#PB_2DDrawing_Transparent)
    DrawText(nx1 + 5 , ny1 + 5, Nodes()\Texte, RGB(0, 0, 0))
    
    If First = 0
      rx = Nodes()\x
      ry = Nodes()\y
      First = #True
    Else
      LineXY(nx0 + 100, ny0 + 30, nx1 + 100 , ny1, RGB(105, 105, 105)) 
      Circle(nx0 + 100, ny0 + 30 , 4, RGB(0, 0, 0))
      Circle(nx1 + 100, ny1, 4, RGB(0, 0, 0))      
    EndIf
    
    ForEach Nodes()\Node()
      nx0 = Nodes()\x
      ny0 = Nodes()\y
      Draw(Nodes()\Node())
    Next  
  Next
  
  ; Retour racine de l'arbre 
  nx0 = rx
  ny0 = ry
EndProcedure

Procedure Exit()  
  End
EndProcedure

[falsam]

Représentation visuelle de la hiérarchie. (Dessin vectoriel dans un canvas)

Code : Tout sélectionner

EnableExplicit

Structure NewNode
  Texte.s
  x.i
  y.f
  List Node.NewNode()
EndStructure
Global NewList Nodes.NewNode()

Global rx, ry, nx0, ny0, nx1, ny1 

;Plan de l'application
Declare Start()
Declare AddNode(Texte.s, x.i, y.i, *Node.NewNode=0)
Declare Draw(List Nodes.NewNode())
Declare Exit()

Start()

Procedure Start()
  Protected Value, ww = 800, wh = 700
  
  OpenWindow(0, 0, 0, ww, wh, "Structure recursive et hierachie", #PB_Window_SystemMenu|#PB_Window_ScreenCentered)
  CanvasGadget(0, 0, 0, ww, wh)
  
  ; Création de la hiérachie  
  Value = AddNode("Véhicules terrestres", 100, 50)
  AddNode("Trotinettes", 300, 150, Value)
  
  Value = AddNode("Voitures", 250, 250, Value)
  AddNode("Electriques", 500, 350, Value)
  AddNode("Thermiques", 400, 400, Value)
  
  Value = AddNode("Marins", 100, 450)
  AddNode("Barques", 400, 520, Value)
  AddNode("Voiliers", 330, 580, Value)
  AddNode("Paquebots", 230, 630, Value)
  
  ; Dessin des nodes 
  If StartVectorDrawing(CanvasVectorOutput(0))  
    LoadFont(0, "Arial", 10, #PB_Font_Bold)
    VectorFont(FontID(0), 15)
    AddPathBox(0, 0, ww, wh)
    VectorSourceColor(RGBA(211, 211, 211, 255))
    FillPath()      
    Draw(Nodes())
    StopVectorDrawing()
  EndIf
  
  ;Triggers
  BindEvent(#PB_Event_CloseWindow, @Exit())
  
  Repeat : WaitWindowEvent() : ForEver
EndProcedure

Procedure AddNode(Texte.s, x.i, y.i, *Node.NewNode=0)
  Protected Result
  
  If *Node
    Result = AddElement(*Node\Node())
    *Node\Node()\Texte = Texte
    *Node\Node()\x = x
    *Node\Node()\y = y
  Else
    Result = AddElement(Nodes())
    Nodes()\Texte = Texte
    Nodes()\x = x
    Nodes()\y = y   
  EndIf   
  ProcedureReturn Result 
EndProcedure

Procedure Draw(List Nodes.NewNode())   
  Static First 
  Protected Delta = 30
  
  ForEach Nodes()        
    nx1 = Nodes()\x
    ny1 = Nodes()\y
    
    ; Dessin de la boite et du texte
    AddPathBox(nx1, ny1, 200, 30)
    VectorSourceColor(RGBA(255, 215, 0, 255))
    FillPath()
    
    AddPathBox(nx1, ny1, 200, 30)
    VectorSourceColor(RGBA(0, 0, 0, 255))
    StrokePath(3)
        
    MovePathCursor(nx1 + 5, ny1 + 5)   
    AddPathText(Nodes()\Texte)
    VectorSourceColor(RGBA(0, 0, 0, 255))
    FillPath()
    
    ; Dessin de la ligne (Courbe de Bezier)
    If First = 0
      rx = Nodes()\x
      ry = Nodes()\y
      First = #True
    Else
      MovePathCursor(nx0 + 100, ny0 + 30)
      AddPathCurve(nx0 - Delta + 100 , ny0 + Delta + 30, nx1 + Delta + 100, ny1 - Delta + 30, nx1 + 100, ny1) 
      
      VectorSourceColor(RGBA(255, 0, 0, 255))
      StrokePath(3)
      
      ; Dessin des plots de jonction
      AddPathCircle(nx0 + 100, ny0 + 30 , 4)
      VectorSourceColor(RGBA(0, 0, 0, 255))
      FillPath()
      
      AddPathCircle(nx1 + 100, ny1, 4)
      VectorSourceColor(RGBA(0, 0, 0, 255))
      FillPath()     
    EndIf
    
    ForEach Nodes()\Node()
      nx0 = Nodes()\x
      ny0 = Nodes()\y
      Draw(Nodes()\Node())
    Next  
  Next
  
  ; Retour racine de l'arbre 
  nx0 = rx
  ny0 = ry
EndProcedure

Procedure Exit()  
  End
EndProcedure

[venom]

Merci falsam pour les exemples. Il y a pas a dire, j'ai du mal a saisir les structures (pourtant j'en croise souvent) mais qu'est ce que c'est pratique.

Je vais étudié tout ça.






@++

[Micoute]

Du très bon travail comme j'aime, merci pour ce partage falsam.

[Zorro]

ou comme ça

Code : Tout sélectionner

Declare ajout(type.s,level)

Enumeration
		#Win 
		#tree 
EndEnumeration

If OpenWindow(#win, 0, 0, 250, 400, "liste de vehicules", #PB_Window_SystemMenu | #PB_Window_ScreenCentered) 
		TreeGadget(#tree, 10, 10, 200, 350)
		ajout("terrestre",0)
		;
		ajout("Voiture",1)
		ajout("Electrique",2)
		ajout("Thermique",2)
		;
		ajout("Trotinette",1)
		;
		ajout("Velo",1)
		ajout("Panier pick_nick",2)
		;
		ajout("Marin",0)
		;
		ajout("Barque",1)
		ajout("Canoée hooo héééé",1)
		ajout("voilier",1)
		ajout("Paquebot",1)
		Repeat : Until WaitWindowEvent() = #PB_Event_CloseWindow
EndIf
procedure ajout(type.s,level)
		AddGadgetItem(#tree, -1, type.s, 0, level) ; si vous souhaitez ajouter une image, utilisez 
EndProcedure

[falsam]

Oui bien sur Zorro ! Tu le sens bien le HS ?

L'objectif n'est pas de créer un treeview mais de manipuler une structure récursive hierachique. La liste obtenue pouvant être sauvegardée au format JSON en moins de 5 lignes de code et loader par la suite là aussi en quelques lignes.

[Zorro]

tain ... j'avais pourtant pas lésiné sur le nombre de smiley ..

[djes]

Très chouette ! Merci !

[Kwai chang caine]

C'est drôlement chouette, merci Falsam
J'ai pas trop compris à quoi ça sert, je suppose pour la représentation graphique d'une hiérarchie, ou bien tu bosses sur ça car ça fait partie d'un projet
C'est drôlement chouette ce que vous faites tous en ce moment sur ce style de sujet....y'a une épidémie

tain ... j'avais pourtant pas lésiné sur le nombre de smiley ..

Effectivement ....m'en parlez pas mon bon m'sieur...à notre époque même l’efficacité des smyley par en couille.....

[Shadow]

Je pense que ça pourrais me servir à moi un jours car dans mon logiciel j'utilise justement ce genre de chose.

Un Gadget peut avoir des enfants, les enfants peuvent avoir aussi des enfants, qui eux même peuvent avoir des enfants, etc etc etc...
Ex:

Fenêtre
> PanelGadget
>> Panel 1
>>> TreeView
>>>> Lien n°1
>>>>> Enfants n°1
>>>>>> Petit Enfants n°1
>>>>> Enfants n°2
>>>>>> Petit Enfants n°1
>>>>>> Petit Enfants n°2
>>>>> Enfants n°3
>>>> Lien n°2
>>>> Lien n°3
>> Panel 2
> Bouton

Sachez que ça peut aller très loin comme ça dans la Hiérarchie, dans mon logiciel, je gère n'importe quel niveau de Hiérarchie comme ça !
Une fois qu'on à compris, c'est pas si compliquer.

Pour parcourir les élément et leurs enfants, ont utilise une procédure récursive !
Merci Falsam pour ton exemple très utile

[G-Rom]

Je vais critiquer en argumentant ton code.
- Véhicules terrestre -> Marin -> voiliers , bon celle la elle est facile.

Sans déconner , ta structure "est trop rigide", il est parfois utile de connaitre pour X ou Y raison le parent d'un noeud.
tu pourrais utilisé ceci :

Structure NewNode
Texte.s
x.i
y.f
List Node.NewNode()
*Parent.NewNode
EndStructure

Il faut bien entendu que cela soit un pointeur sur le parent, je sais que si tu veut sauvegardé dans un json, le pointeur ne sert à rien, dans ce cas, tu l'ignore. si tu n'utilise pas de pointeur , tu auras un "nouveau" node à part entière.
Idem , pour les enfants, j'utiliserais des pointeurs à la place , là , tu donnes la responsabilité à NewNode la gestion des enfants, si tu détruit un parent , tout les enfants sont morts aussi, pas très flexible.
Je pense aussi que ce n'est pas très "cache friendly" , c'est à dire qu'au niveau optimisation , ce n'est pas contiguë , avec 3 nodes pas de problèmes , mais si tu en as des milliers , ca peu se faire ressentir dans les accès mémoire.
je ne dit pas que c'est mal, mais , ça manque de flexibilité pour être utilisé.
J'avais fait un "topo" à shadow la dessus justement y a quelque temps : https://www.purebasic.fr/french/viewtop ... 38#p204138 , si cela peut être utile.
Je sais que tu vas me parler que pour sauvegardé , du coup avec les pointeurs on perd la hiérarchie , ce qui est logique , mais sois tu sauvegardes sans te soucier des pointeurs , ou soit tu utilises , comme d'autres le font , un système de "path"

Par exemple, par rapport à ton graph , "Electrique" aura le path suivant : Véhicules terrestres/Voitures/Electrique , évidement cela implique que des noeuds du même niveau n'ai pas le même nom...
Voilà, j'éspère avoir été constructif & compréhensible. si ce n'est pas le cas , n'hésite pas à me posé des questions.

@++

[Ollivier]

C'est un leurre, c'est pas possible. Remarque : un débat hiérarchique sans fin, c'est récursif.

Pour rester constructif : exemple de récursivité

Un autre exemple : ta retraite, inlassablement travaillée et retravaillée de manière récursive sur les marchés financiers (comme x retraites, salaires d'Etat ou indemnités).

Par contre, la présentation est nickel.

Code : Tout sélectionner

véhicule
   aérien
      delta
      cape
      montgolfière
      dirigeable
   terrestre
      simple
         calèche
         traineau
      composé
         patins
   maritime
      simple
         péniche
            propulsion Diesel
            traction à cheval
         zodiaque
            rames
            moteur thermique
            turboréacteur
      composé
         catamaran

[G-Rom]

C'est un leurre, c'est pas possible. Remarque : un débat hiérarchique sans fin, c'est récursif.

Pour rester constructif : exemple de récursivité

Un autre exemple : ta retraite, inlassablement travaillée et retravaillée de manière récursive sur les marchés financiers (comme x retraites, salaires d'Etat ou indemnités).

Par contre, la présentation est nickel.

Code : Tout sélectionner

véhicule
   aérien
      delta
      cape
      montgolfière
      dirigeable
   terrestre
      simple
         calèche
         traineau
      composé
         patins
   maritime
      simple
         péniche
            propulsion Diesel
            traction à cheval
         zodiaque
            rames
            moteur thermique
            turboréacteur
      composé
         catamaran

C'est moi, ou je ne comprends rien ? y a un topic intéressant , puis après des références sur le jardinage en timelapse , des phrases énigmatiques , de la politique de comptoir , etc...
c'est un leurre ? tu réponds à qui ? à quoi ? qu'est ce qui n'est pas possible ?

[Ollivier]

C'est pas grave. Falsam a corrigé.