Recent

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

Milsa

  • Full Member
  • ***
  • Posts: 192
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.

Thaddy

  • Hero Member
  • *****
  • Posts: 8973
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.
Most people that want to use threading should learn to patch their jeans first: use a needle.

julkas

  • Sr. Member
  • ****
  • Posts: 385
  • KISS principle / Lazarus 2.0.0 / FPC 3.0.4
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.
procedure mulu64(a, b: QWORD; out clo, chi: QWORD); assembler;
asm
  mov rax, a
  mov rdx, b
  mul rdx
  mov [clo], rax
  mov [chi], rdx
end;

jamie

  • Hero Member
  • *****
  • Posts: 1997
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...

ASerge

  • Hero Member
  • *****
  • Posts: 1409
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

  • Full Member
  • ***
  • Posts: 241
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: 8973
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.
Most people that want to use threading should learn to patch their jeans first: use a needle.

Leledumbo

  • Hero Member
  • *****
  • Posts: 8109
  • 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

  • Full Member
  • ***
  • Posts: 133
    • my self-education project
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: 8109
  • 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

  • Full Member
  • ***
  • Posts: 133
    • my self-education project
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: 1997
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.

Thaddy

  • Hero Member
  • *****
  • Posts: 8973
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 »
Most people that want to use threading should learn to patch their jeans first: use a needle.

avk

  • Full Member
  • ***
  • Posts: 133
    • my self-education project
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.