PureBasic Forums - English

Posted: **Sat Feb 10, 2007 1:06 pm**

The very thing i love in PB is the native linked lists because one can use any type and also get items directly with the "=" operator (except for structured types)

I wrote tree functions, it works very well BUT it only work for ONE type which sounds too bad for me so i think it may be a good idea to have new "NewThing"s in PB...

NewTree
A tree would be like a linked list, with a current node, changing position to the superior (if it's not the root) or the siblings or the children. A tree could have "several roots" (several siblings whit no superior) like in the tree gadget.
NewBinaryTree
A binary tree would have a current node but also a position for each node. The position would be a string of zeros and ones ("001101001text11111" would be the "001101001" position) and an empty string would change the current node to the root.
NewBST (Binary Search Tree)
A BST would only work with ordonned types (integers, floats and maybe strings because of the "<" and ">" operators) and positions would be choosen automatically to ensure the tree to always be sorted (and it wouldn't be possible to have two nodes with the same value)

It would also be great to have loops like "foreach" for infix, prefix and postfix traversals. And also the same function names for all trees (and compiler errors if one try to use a string position not for a binary tree for example).

I can make my functions work for any type, i did it when i tried to make my own pb-like linked lists but it wouldn't be the same as doing somthing like :

myvariable = mytree() ;get the current node's value
SuperiorNode( mytree() ) ;go to the superior node
debug mytree() ;display the node's value

I know it's a "not really small" request but i also know it would be a great feature.

Dri

Posted: **Sat Feb 10, 2007 1:36 pm**

I made some macros to automatically generate dynamic linkelist code for any type: http://www.purebasic.fr/english/viewtopic.php?t=24399

Posted: **Sat Feb 10, 2007 5:26 pm**

I know and I like your code, but it's not what I am looking for...

Dri

Posted: **Fri Feb 16, 2007 10:11 am**

After a few days i don't have any answer (i have one but not what i expected) so i think my english is not good enough... I hope I'll get a "No we won't add that" or a "Yes it's a good idea" but my post may not be clear enough ???

Je me suis peut-être mal exprimé, si c'est le cas je m'en excuse... Ce que je propose ce sont de nouveaux types dynamiques natifs. Et ces types (pou utilisateurs +/- avancés) ce sont trois types d'arbres. Pour les arbres BST j'ai aussi oublié de suggérer de les faire auto-balancés. Enfin quoi qu'il en soit je pense sincèrement que ce serait un gros plus mais comme je n'ai pas de réponse de la PB team et que je n'ai l'avis d'aucun utilisateur de PB je fini par croire que j'ai écris un truc incompréhensible. Enfin bon j'espère que ma suggestion sera remarquée.

Dri

Posted: **Fri Feb 16, 2007 11:55 am**

I don't understand french, but I think I understood what you meant, at least the first point.

if you say, the tree could have multiple roots, this would mean,
each node can have multiple parents and multiple children.
so, a Node would be an element with a list of pointers to the parents and a list of pointers to the children.
in opposite to LL, where each Element only has one "parent" and one "child".

the problem with such a tree would be, how much memory should you allocate for a single node.

so, if we allocate only mem for the parent-pointer at the moment we create the node,
we have to re-allocate the mem for the node everytime something changes,
when some parent or child is added/removed.

I don't get the second and third point, maybe you thought about a totally different concept...

Posted: **Fri Feb 16, 2007 12:06 pm**

Self balancing trees...... Now that would be a great addition!

Posted: **Fri Feb 16, 2007 3:34 pm**

Kaeru Gaman wrote:I don't understand french, but I think I understood what you meant, at least the first point.

if you say, the tree could have multiple roots, this would mean,
each node can have multiple parents and multiple children.

[...]

I don't get the second and third point, maybe you thought about a totally different concept...

My english sucks

For the first point :

Code: Select all

If OpenWindow(0, 0, 0, 355, 180, "TreeGadget", #PB_Window_SystemMenu | #PB_Window_ScreenCentered) And CreateGadgetList(WindowID(0))
  TreeGadget(0, 10, 10, 160, 160)                                         ; TreeGadget standard
  TreeGadget(1, 180, 10, 160, 160, #PB_Tree_CheckBoxes|#PB_Tree_NoLines)  ; TreeGadget with Checkboxes + NoLines
  For ID = 0 To 1
    For a = 0 To 10
      AddGadgetItem (ID, -1, "Normal Item "+Str(a), 0, 0) ; if you want to add an image, use 
      AddGadgetItem (ID, -1, "Node "+Str(a), 0, 0)        ; ImageID(x) as 4th parameter
      AddGadgetItem(ID, -1, "Sub-Item 1", 0, 1)    ; These are on the 1st sublevel  
      AddGadgetItem(ID, -1, "Sub-Item 2", 0, 1)
      AddGadgetItem(ID, -1, "Sub-Item 3", 0, 1)
      AddGadgetItem(ID, -1, "Sub-Item 4", 0, 1)
      AddGadgetItem (ID, -1, "File "+Str(a), 0, 0) ; sublevel 0 again
    Next
  Next
  Repeat : Until WaitWindowEvent() = #PB_Event_CloseWindow
EndIf

In this example, "Normal Item X" "Node X" "File X" have no parent, so they are roots, their are several roots but a node cannot have several parents.

Second point :
I'm talking about binary trees which are particular trees

Third point :
I'm talking about self balanced binary search trees which are sorted binary trees

Dri

Posted: **Fri Feb 16, 2007 3:52 pm**

Dr. Dri wrote:In this example, "Normal Item X" "Node X" "File X" have no parent, so they are roots, their are several roots but a node cannot have several parents.

Second point :
I'm talking about binary trees which are particular trees

Third point :
I'm talking about self balanced binary search trees which are sorted binary trees

1. so if a Node cannot have several parents, a tree can only have ONE root.
Different Roots mean different Trees.

2. Binary Trees... that means, each Node has 1 parent and 2 childs?

3. ok... I have to look this up in the german wiki to get the specials...

1.+2. => should be not too hard to write an Include/Lib for it....?

Posted: **Sat Feb 17, 2007 12:15 pm**

Kaeru Gaman wrote:1. so if a Node cannot have several parents, a tree can only have ONE root.
Different Roots mean different Trees.

2. Binary Trees... that means, each Node has 1 parent and 2 childs?

3. ok... I have to look this up in the german wiki to get the specials...

1.+2. => should be not too hard to write an Include/Lib for it....?

1. a root is a node which have a sublevel (see #PB_Tree_SubLevel) equal to zero

2. a node can have 0, 1 or 2 children

1.+2. like i said i've already coded tree routines but my request aims to have them native for any type in PB...

Dri

Posted: **Sat Feb 17, 2007 4:27 pm**

ok, so a "Tree" like in a TreeGadget is a bit different from a Tree in other mathematical concerns...
I never used a TreeGadget....

> i've already coded tree routines but my request aims to have them native for any type in PB...
hum.. ok..

krgds
KG

Posted: **Sun Feb 18, 2007 8:09 am**

i've already coded tree routines but my request aims to have them native for any type in PB...

Good idea

!

PureBasic Forums - English

[Implemented] More types like array and linked lists

[Implemented] More types like array and linked lists