Yet another generics collection

[sash]

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() ?

[avk]

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]

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]

@sash, eventually I added TGSimpleObjGraph. It would be interesting to know your opinion.

[sash]

@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;

?

[avk]

- 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]

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?

[avk]

Yeah, exactly.

[avk]

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.