Recent

Author Topic: Class with object tree functionality  (Read 2439 times)

Milsa

  • Sr. Member
  • ****
  • Posts: 309
Class with object tree functionality
« on: September 01, 2019, 11:14:00 am »
I found TObjectList but I need something as TObjectTreeList. Does exists any class in FPC with this functionality? I need to create subtrees and assign to main tree etc.
I work with Lazarus 2.2.2, FPC 3.2.2, date 2022-05-15
This information is actual to: 28st Dec 2022

Thaddy

  • Hero Member
  • *****
  • Posts: 14203
  • Probably until I exterminate Putin.
Re: Class with object tree functionality
« Reply #1 on: September 01, 2019, 12:32:07 pm »
In  rtl-generics: TAvlTree<Tobject>? from 3.2 otherwise download from Maciej's website or install from fpcdeluxe.
Specialize a type, not a var.

julkas

  • Guest
Re: Class with object tree functionality
« Reply #2 on: September 01, 2019, 06:01:21 pm »
I found TObjectList but I need something as TObjectTreeList. Does exists any class in FPC with this functionality? I need to create subtrees and assign to main tree etc.
What is your requirements?
Balanced binary tree, ...?
As @Thaddy says check first Delphi compatible generics.collections.

jamie

  • Hero Member
  • *****
  • Posts: 6090
Re: Class with object tree functionality
« Reply #3 on: September 01, 2019, 06:51:56 pm »
You could always use a TstringList…

 It has Addobject that allows you to also name it

 So you start with the base Stringlist, add some other string list within each of the base.

 you could use the string part to name the object, etc...
The only true wisdom is knowing you know nothing

ASerge

  • Hero Member
  • *****
  • Posts: 2222
Re: Class with object tree functionality
« Reply #4 on: September 01, 2019, 09:08:45 pm »
This works in the current release:
Code: Pascal  [Select][+][-]
  1. {$APPTYPE CONSOLE}
  2. {$MODE OBJFPC}
  3. {$LONGSTRINGS ON}
  4.  
  5. uses gtree;
  6.  
  7. type
  8.   TSomeTree = specialize TTree<string>;
  9.  
  10. procedure AddItemToTree(Tree: TSomeTree; const S: string);
  11. var
  12.   Node: TSomeTree.TTreeNodeType;
  13. begin
  14.   Node := TSomeTree.TTreeNodeType.Create(S);
  15.   if Assigned(Tree.Root) then
  16.     Tree.Root.Children.PushBack(Node)
  17.   else
  18.     Tree.Root := Node;
  19. end;
  20.  
  21. function CreateTree(const Items: array of string): TSomeTree;
  22. var
  23.   i: SizeInt;
  24. begin
  25.   Result := TSomeTree.Create;
  26.   for i := Low(Items) to High(Items) do
  27.     AddItemToTree(Result, Items[i]);
  28. end;
  29.  
  30. procedure PrintItem(const Item: string);
  31. begin
  32.   Writeln(Item);
  33. end;
  34.  
  35. procedure PrintTree(const TreeName: string; Tree: TSomeTree);
  36. begin
  37.   Writeln(TreeName);
  38.   Tree.DepthFirstTraverse(@PrintItem);
  39.   Writeln;
  40. end;
  41.  
  42. procedure CombineTrees(ToTree, Appened: TSomeTree);
  43. begin
  44.   if Assigned(Appened.Root) then
  45.   begin
  46.     if Assigned(ToTree.Root) then
  47.       ToTree.Root.Children.PushBack(Appened.Root)
  48.     else
  49.       ToTree.Root := Appened.Root;
  50.     Appened.Root := nil;
  51.   end;
  52. end;
  53.  
  54. procedure TestTree;
  55. var
  56.   Tree1, Tree2: TSomeTree;
  57. begin
  58.   Tree1 := CreateTree(['1', '2', '3', '4']);
  59.   try
  60.     PrintTree('Tree1', Tree1);
  61.     Tree2 := CreateTree(['101', '102', '103']);
  62.     try
  63.       PrintTree('Tree2', Tree2);
  64.       CombineTrees(Tree1, Tree2);
  65.       PrintTree('Tree1', Tree1);
  66.       PrintTree('Tree2', Tree2);
  67.     finally
  68.       Tree2.Free;
  69.     end;
  70.   finally
  71.     Tree1.Free;
  72.   end;
  73. end;
  74.  
  75. begin
  76.   TestTree;
  77.   Readln;
  78. end.

egsuh

  • Hero Member
  • *****
  • Posts: 1273
Re: Class with object tree functionality
« Reply #5 on: September 02, 2019, 01:01:13 pm »
I have been using TTreeView quite widely. What's problem with TTreeView?
You can add TObject to each node, just like adding TObject to TStringList.

Thaddy

  • Hero Member
  • *****
  • Posts: 14203
  • Probably until I exterminate Putin.
Re: Class with object tree functionality
« Reply #6 on: September 02, 2019, 05:37:50 pm »
I have been using TTreeView quite widely. What's problem with TTreeView?
You can add TObject to each node, just like adding TObject to TStringList.
TTreeview is as the name says a visual component... You should not use it for tasks like this: much too much overhead.
You CAN use it, but it is severely wrong for non-visual tasks.
Specialize a type, not a var.

Leledumbo

  • Hero Member
  • *****
  • Posts: 8746
  • Programming + Glam Metal + Tae Kwon Do = Me
Re: Class with object tree functionality
« Reply #7 on: September 05, 2019, 04:27:49 pm »
I've put a generic tree structure to fcl-stl waaay back then before rtl-generics is available. It's much much more inferior to rtl-generics' TAVLTree but it does the job if you really really just need a tree data structure with DFS/BFS traversal.

avk

  • Hero Member
  • *****
  • Posts: 752
Re: Class with object tree functionality
« Reply #8 on: September 13, 2019, 04:43:15 pm »
@Leledumbo, DFS is usually expected to be traversed by the entire subtree of a node by the time it traverses a node. It seems your DFS does not have this property?

Leledumbo

  • Hero Member
  • *****
  • Posts: 8746
  • Programming + Glam Metal + Tae Kwon Do = Me
Re: Class with object tree functionality
« Reply #9 on: September 14, 2019, 02:27:36 pm »
@Leledumbo, DFS is usually expected to be traversed by the entire subtree of a node by the time it traverses a node. It seems your DFS does not have this property?
Sorry, I don't get what you mean. The implementation is taken from a basic algorithms & data structures book which I forget what the book title was, but all I remember is that the implementation for both DFS and BFS are completely equal, with the exception of DFS uses stack instead of queue for the to-be-visited nodes.

avk

  • Hero Member
  • *****
  • Posts: 752
Re: Class with object tree functionality
« Reply #10 on: September 14, 2019, 04:41:01 pm »
Let's say we need to calculate the size of subtrees for all nodes of the tree,
using DFS and timestamps, this can be done in one pass. But your algorithm, unfortunately, is not suitable for this.

jamie

  • Hero Member
  • *****
  • Posts: 6090
Re: Class with object tree functionality
« Reply #11 on: September 14, 2019, 08:27:32 pm »
Maybe a Class specific to the use should be written ?

 I mean really, I know how to do it and I am just a backyard coder with skills just barely passing the ok meter.
The only true wisdom is knowing you know nothing

Thaddy

  • Hero Member
  • *****
  • Posts: 14203
  • Probably until I exterminate Putin.
Re: Class with object tree functionality
« Reply #12 on: September 14, 2019, 08:42:27 pm »
@jamie,

avk has already done that (and a very good implementation in his L series generics) , but I can't agree with the full critic he has on leledumbo, because the old fashioned stack and the queue are indeed the classic way to solve it.
It also has better read/write characteristics - in theory.
« Last Edit: September 14, 2019, 08:48:07 pm by Thaddy »
Specialize a type, not a var.

avk

  • Hero Member
  • *****
  • Posts: 752
Re: Class with object tree functionality
« Reply #13 on: September 15, 2019, 03:50:08 am »
@Thaddy, this is not criticism at all, but regret. When I needed a general tree implementation, it turned out that the existing implementation was not suitable for me. However, as jamie pointed out, the problem is solved by creating my own class.

egsuh

  • Hero Member
  • *****
  • Posts: 1273
Re: Class with object tree functionality
« Reply #14 on: August 19, 2020, 10:34:45 am »
This is rather old subject, but I've tested TTreeView in non-visual state, and tested.  That is,

Code: Pascal  [Select][+][-]
  1. var
  2.     tv1 : TTreeView;
  3.     ti : integer;
  4.  begin
  5.    tv1 := TTreeView.Create(nil);
  6.    for ti := 1 to 100000 do tv1.items.add(nil, 'Node ' + IntToStr(Random(100000)));
  7.    // .. other operations
  8.    tv1.Free;
  9. end;  

This code does not display visual form.

I've used the same operation with visual component on a form.  The time took 8 times longer in the case of having visual form.

But when I set 'visible' property of the component on the form, both took very similar result. 

So if not a situation when speed is really needed, just setting visibility to false will lessen the operation load in the tree structure.

 

TinyPortal © 2005-2018