Recent

Author Topic: Yet another generics collection  (Read 14993 times)

sash

  • Sr. Member
  • ****
  • Posts: 366
Re: Yet another generics collection
« Reply #60 on: August 27, 2020, 05:17:45 pm »
Provided that you do not remove the vertices and edges of the graph while manipulating with it, this can be done in the destructor.
Well ... I do remove elements... so I wrote
Code: Pascal  [Select][+][-]
  1. function TMyGraph.DoRemoveEdge(aSrc, aDst : SizeInt) : Boolean;
  2. var
  3.   edg : TMyGraphEdge;
  4. begin
  5.   Result := false;
  6.   if GetEdgeDataI(aSrc, aDst, edg) then begin
  7.     Result := inherited DoRemoveEdge(aSrc, aDst);
  8.     if Result then
  9.       edg.Free;
  10.   end;
  11. end;
  12.  
Is it ok? Will it work on MyGraph.Clear() ?
« Last Edit: August 27, 2020, 05:27:56 pm by sash »
Lazarus 2.0.10 FPC 3.2.0 x86_64-linux-gtk2 @ Ubuntu 20.04 XFCE

avk

  • Sr. Member
  • ****
  • Posts: 325
    • my self-education project
Re: Yet another generics collection
« Reply #61 on: August 27, 2020, 06:02:44 pm »
OMG, I completely forgot about Clear.
It also needs to be overridden.

Provided that you do not remove the vertices and edges of the graph while manipulating with it, this can be done in the destructor.
Well ... I do remove elements... so I wrote
Code: Pascal  [Select][+][-]
  1. function TMyGraph.DoRemoveEdge(aSrc, aDst : SizeInt) : Boolean;
  2. var
  3.   edg : TMyGraphEdge;
  4. begin
  5.   Result := false;
  6.   if GetEdgeDataI(aSrc, aDst, edg) then begin
  7.     Result := inherited DoRemoveEdge(aSrc, aDst);
  8.     if Result then
  9.       edg.Free;
  10.   end;
  11. end;
  12.  

I would prefer like this:
Code: Pascal  [Select][+][-]
  1. function TMyGraph.DoRemoveEdge(aSrc, aDst : SizeInt) : Boolean;
  2. var
  3.   edg : TMyGraphEdge;
  4. begin
  5.   if GetEdgeDataI(aSrc, aDst, edg) and (inherited DoRemoveEdge(aSrc, aDst)) then begin
  6.     edg.Free;
  7.     exit(True);
  8.   end;
  9.   Result := False;  
  10. end;
  11.  

avk

  • Sr. Member
  • ****
  • Posts: 325
    • my self-education project
Re: Yet another generics collection
« Reply #62 on: August 27, 2020, 07:08:46 pm »
Perhaps something like this:
Code: Pascal  [Select][+][-]
  1. ...
  2. type
  3.  
  4.   TMyVertex = class
  5.   end;
  6.  
  7.   TMyEdge = class
  8.   end;
  9.  
  10.   TMyGraph = class(specialize TGSimpleGraph<TMyVertex, TMyEdge, TMyVertex>)
  11.   protected
  12.     procedure DoRemoveVertex(aIndex: SizeInt); override;
  13.     function  DoRemoveEdge(aSrc, aDst: SizeInt): Boolean; override;
  14.   public
  15.     destructor Destroy; override;
  16.     procedure Clear; override;
  17.   end;
  18.  
  19. implementation
  20. {$B-}{$COPERATORS ON}{$POINTERMATH ON}
  21. ...
  22. { TMyGraph }
  23.  
  24. procedure TMyGraph.DoRemoveVertex(aIndex: SizeInt);
  25. var
  26.   p: PAdjItem;
  27. begin
  28.   for p in AdjLists[aIndex]^ do
  29.     p^.Data.Free;
  30.   Items[aIndex].Free;
  31.   inherited DoRemoveVertex(aIndex);
  32. end;
  33.  
  34. function TMyGraph.DoRemoveEdge(aSrc, aDst: SizeInt): Boolean;
  35. var
  36.   e: TMyEdge;
  37. begin
  38.   if GetEdgeDataI(aSrc, aDst, e) and (inherited DoRemoveEdge(aSrc, aDst)) then
  39.     begin
  40.       e.Free;
  41.       exit(True);
  42.     end;
  43.     Result := False;
  44. end;
  45.  
  46. destructor TMyGraph.Destroy;
  47. begin
  48.   Clear;
  49.   inherited;
  50. end;
  51.  
  52. procedure TMyGraph.Clear;
  53. var
  54.   e: TEdge;
  55.   I: SizeInt;
  56. begin
  57.   for e in DistinctEdges do
  58.     e.Data.Free;
  59.   for I := 0 to Pred(VertexCount) do
  60.     Items[I].Free;
  61.   inherited;
  62. end;
  63.  

avk

  • Sr. Member
  • ****
  • Posts: 325
    • my self-education project
Re: Yet another generics collection
« Reply #63 on: August 28, 2020, 04:41:32 pm »
@sash, eventually I added TGSimpleObjGraph. It would be interesting to know your opinion.

sash

  • Sr. Member
  • ****
  • Posts: 366
Re: Yet another generics collection
« Reply #64 on: August 29, 2020, 01:33:38 pm »
@sash, eventually I added TGSimpleObjGraph. It would be interesting to know your opinion.

Thank you very much.
Updated to TGSimpleObjGraph.

Much more convenient. Seems like It works as it should. I didn't test allocations yet, but certainly will.
I'm glad you implemented OwnsXXX properties, don't know about edges, but my use-case assumes some vertices belongs to multiple graphs, so it's very handy.

Again (some more questions :))
- what happens with orphaned edges (when both connected vertices deleted)?
- can I replace an existing instance of vertex like
Code: Pascal  [Select][+][-]
  1. graph.Items[i].Free;
  2. graph.Items[i] := TAnotherVertex.Create;
?

Lazarus 2.0.10 FPC 3.2.0 x86_64-linux-gtk2 @ Ubuntu 20.04 XFCE

avk

  • Sr. Member
  • ****
  • Posts: 325
    • my self-education project
Re: Yet another generics collection
« Reply #65 on: August 30, 2020, 01:07:00 pm »
- what happens with orphaned edges (when both connected vertices deleted)?
- can I replace an existing instance of vertex like

1. Removal of any vertex of the graph implies the removal of all incident edges.
2. It would be safer like this:
Code: Pascal  [Select][+][-]
  1.   OldValue := graph.Items[i];
  2.   graph.Items[i] := TAnotherVertex.Create;
  3.   OldValue.Free;
  4.  
But the latest revision of the library will do this automatically(provided that the graph owns the vertices).

sash

  • Sr. Member
  • ****
  • Posts: 366
Re: Yet another generics collection
« Reply #66 on: August 30, 2020, 05:19:19 pm »
But the latest revision of the library will do this automatically(provided that the graph owns the vertices).
Do what? Free old contained object on assignment of new one?
Lazarus 2.0.10 FPC 3.2.0 x86_64-linux-gtk2 @ Ubuntu 20.04 XFCE

avk

  • Sr. Member
  • ****
  • Posts: 325
    • my self-education project
Re: Yet another generics collection
« Reply #67 on: August 30, 2020, 05:53:38 pm »
Yeah, exactly.

avk

  • Sr. Member
  • ****
  • Posts: 325
    • my self-education project
Re: Yet another generics collection
« Reply #68 on: October 19, 2020, 10:45:33 am »
Added a radix sort algorithm, so I ran the sorting benchmark again.
  • Rtl/SortBase denotes SortBase.QuickSort_ItemList_Context
  • Rtl-Generics - Generics.Collections.TArrayHelper.Sort
  • Fcl-Stl - gArrayUtils.TOrderingArrayUtils.Sort
  • PasPDQSort - TPDQSorter.Sort - Akira1364's Pascal translation of PDQSort from https://github.com/Akira13641/PasPDQSort
  • LG/QuickSort - TGOrdinalArrayHelper.QuickSort
  • LG/IntroSort - TGOrdinalArrayHelper.IntroSort
  • LG/DualPivotQuickSort - TGOrdinalArrayHelper.DualPivotQuickSort
  • LG/PDQSort - TGOrdinalArrayHelper.PDQSort
  • LG/MergeSort - TGComparableArrayHelper.MergeSort
  • LG/TimSort - TGComparableTimSort.Sort
  • LG/Sort - TGOrdinalArrayHelper(mostly uses radix sort)
A negative value indicates that the algorithm failed the test(exhibits quadratic behavior).
The benchmark was compiled with FPC 3.3.1-r46955 and ran on a win7-64bit machine.

 

TinyPortal © 2005-2018