Philosophically speaking: TFPSortedObjectList or TFPStringList?

[MarkMLl]

In fairness, and with respect to everybody, the question is what components/classes are already available lest OP ends up duplicating existing work.

Focussing on the Real World: earlier Warfley said "But to add you need to first do a search". I'd suggest that that is not necessarily a foregone conclusion: the addition could go into a journal reconciled by a background thread, and a search would only need to be done at retrieval (with different performance depending on whether the background thread had had a chance to do its thing).

MarkMLl

[EganSolo]

Wow!
  You guys are amazing! I love this forum!
  My starting point was motivated by a nagging feeling that I shouldn't be using TFPStringList JUST because I want objects to remain sorted. It felt like a kludge and I wanted to know if there were alternatives, so to summarize:

• MArkMLI pointed out that my google search was perhaps ill-defined. I had googled several alternatives to my questions and came back empty-handed. I should have pointed that out.
• Thaddy provided a generic alternative to TStringList. Frankly, I had tried Generics in an earlier version of fpc/laz (can't remember which one off-hand) and had stayed away from them since. It may be time to revisit. Thanks, Thaddy!
• TSet is a structure I wasn't aware of, so a shoutout to Warfley for pointing it out and a great thank you for the detailed discussion of array's performance in modern computers. That was extremely helpful.

Thank you, everyone, for your participation. I found it extremely helpful and instructive.

Egan.

[dbannon]

Yes Egan, TSet sounds interesting. What a pity is not documented anywhere in FPC space.

A red-black tree is for many situations, very appropriate.

I did find this http://history.ioinformatics.org/conf/c6_boza.pdf - looks like a 2012 conference talk. Enough to spark a bit of interest.

Davo

[PascalDragon]

Yes Egan, TSet sounds interesting. What a pity is not documented anywhere in FPC space.

They were a third party contribution (by the author of the presentation you linked). Feel free to provide patches to document them.

I did find this http://history.ioinformatics.org/conf/c6_boza.pdf - looks like a 2012 conference talk. Enough to spark a bit of interest.

There's also this paper by the same author.

[dbannon]

....
There's also this paper by the same author.

Ah, thats heaps more informative. If I can make sense of it, and find some time, I will write something, initially as a wiki page, and then if people like yourself consider it not comple rubbish, as a doc patch.

Thanks

Davo

[dbannon]

Ah, thats heaps more informative. If I can make sense of it, and find some time, I will write something, initially as a wiki page, and then if people like yourself consider it not comple rubbish, as a doc patch.

Well, I did have a quick look at it and it seems TSet is far from what I expected. The following code compiles and works but its apparently not possible for me replace the longint that TSet likes as its data with, for example a pointer to a record. So, is TSet really just capapable of managing longints (or integer, shortints) ?  Thats all ?   

I expected to be able to take pointers to a record, have its sort method redefined, much like can be done with AvgLvlTree.

Would be very good if someone could tell me I am wrong.... 

( I guess I will still write it up as a wiki page with the very basic info I have collected but I don't see it being very useful.)

Code: Pascal  [Select][+][-]

1. program TSetDemo;
2.  
3. {$mode objfpc}{$H+}
4. uses
5.     SysUtils, gvector, gset, gutil;        
6.    
7. type
8.       PNote=^TNote;
9.       TNote = record
10.             Title : string;
11.             ID    : string;
12.       end;  
13.      
14. type
15.     iLess = specialize TLess<longint>;
16.     iVector = specialize TVector<longint>;
17.     iSet = specialize TSet<longint, iLess>;
18.    
19.     // iNoteSet = specialize TSet<ShortInt, iLess>;     // that compiles    
20.     // iNoteSet = specialize TSet<PNote, iLess>;        // that does not compile
21.     // iNoteSet = specialize TSet<pointer, iLess>;      // that does not compile
22.     // iNoteSet = specialize TSet<extended, iLess>;     // that does not compile
23.    
24. procedure TestTSet();
25. var S : iSet;
26.     it : iSet.TIterator;
27. begin
28.     S := iSet.Create();
29.     S.Insert(1760);
30.     S.Insert(69);
31.     S.Insert(1024);  
32.     it := S.Min();
33.     repeat
34.         writeln(it.GetData);
35.     until not it.Next();
36.     it.Free;
37.     S.free;
38. end;            
39.  
40. begin
41.     TestTSet();
42. end.

Ref -
https://ioinformatics.org/journal/INFOL101.pdf
http://oldwww.dcs.fmph.uniba.sk/bakalarky/obhajene/getfile.php/boza11306397896881.pdf?id=159&fid=315&type=application%2Fpdf

Davo

[avk]

...
  So, is TSet really just capapable of managing longints (or integer, shortints) ?  Thats all ?   
...

You can consider this version:

Code: Pascal  [Select][+][-]

1. program TSetDemo;
2. {$mode objfpc}{$H+}
3. {$modeswitch advancedrecords}
4. uses
5.   SysUtils, gvector, gset, gutil;
6.  
7. type
8.   PNote = ^TNote;
9.   TNote = record
10.     Title : string;
11.     ID    : string;
12.   end;
13.  
14.   TLess = record
15.     class function c(L, R: PNote): Boolean; static;
16.   end;
17.  
18. class function TLess.c(L, R: PNote): Boolean;
19. begin
20.   Result := L^.ID < R^.ID;
21. end;
22.  
23. type
24.   TNoteSet = specialize TSet<PNote, TLess>;
25.  
26. procedure TestTSet;
27. var
28.   S: TNoteSet;
29.   it: TNoteSet.TIterator;
30.   p: PNote;
31. const
32.   Notes: array of TNote = (
33.     (Title: 'Title1'; ID: '111'),
34.     (Title: 'Title2'; ID: '222'),
35.     (Title: 'Title3'; ID: '333'),
36.     (Title: 'Title4'; ID: '444'));
37. begin
38.     S := TNoteSet.Create;
39.     S.Insert(@Notes[3]);
40.     S.Insert(@Notes[2]);
41.     S.Insert(@Notes[1]);
42.     S.Insert(@Notes[0]);
43.     it := S.Min;
44.     repeat
45.       p := it.GetData;
46.       writeln('Title: ', p^.Title, ', ID: ', p^.ID);
47.     until not it.Next;
48.     it.Free;
49.     S.free;
50. end;
51.  
52. begin
53.   TestTSet;
54. end.
55.  

[dbannon]

Yes AVK, you are right, indeed, I should consider !

I did not realise that the TLess is the compare function !  That all makes a lot of sense. Yep, it works, so, I will see if I can get a comparison between TSet and the AVL model.

Thanks !

Davo

[avk]

IIRC, TSet is built on top of the LLRbTree implementation, which is always slower than AvlTree. And yes, TSet is a Set, not a SortedList.
Also, it is a rather old library and in my opinion too STL-centric.

[dbannon]

Hmm, that interesting.  I was attracted to the Red-Black Tree's reputation of being faster when being frequently updated. But I guess that is a comparison between two similarly developed models.

I get the impression that the FPC AVL is pretty finely tuned.....

But this started with me complaining that TSet was undocumented. So, I'll at least have a play and create a wiki page !

Thanks AVK

Davo

[Thaddy]

IIRC, TSet is built on top of the LLRbTree implementation, which is always slower than AvlTree. And yes, TSet is a Set, not a SortedList.
Also, it is a rather old library and in my opinion too STL-centric.

With the latter I agree, with the former, no. A set (computer theory, not Pascal sets perse, however Pascal adheres to those properties) is characterized by in-order. ( and ultimately with no duplicates)
See my example that I gave previously in this discussion. In effect that is a "set" and demonstrates its properties well, I guess.

https://en.wikipedia.org/wiki/Set_(abstract_data_type)

Anyway it is one of the easiest to understand.
I also wrote a wiki entry for huge sets that conforms too.

In essence a sorted list with no duplcates allowed is a "set".
Some literature claim unsorted. That has been proven wrong - time space -. Sets are by theory in effect and in implementation - low to high.

[avk]

...
In essence a sorted list with no duplcates allowed is a "set".
...

It seems yes.

[Warfley]

You can consider this version:

Code: Pascal  [Select][+][-]

1. program TSetDemo;
2. {$mode objfpc}{$H+}
3. {$modeswitch advancedrecords}
4. uses
5.   SysUtils, gvector, gset, gutil;
6.  
7. type
8.   PNote = ^TNote;
9.   TNote = record
10.     Title : string;
11.     ID    : string;
12.   end;
13.  
14.   TLess = record
15.     class function c(L, R: PNote): Boolean; static;
16.   end;
17.  
18. class function TLess.c(L, R: PNote): Boolean;
19. begin
20.   Result := L^.ID < R^.ID;
21. end;
22.  
23. type
24.   TNoteSet = specialize TSet<PNote, TLess>;
25.  
26. procedure TestTSet;
27. var
28.   S: TNoteSet;
29.   it: TNoteSet.TIterator;
30.   p: PNote;
31. const
32.   Notes: array of TNote = (
33.     (Title: 'Title1'; ID: '111'),
34.     (Title: 'Title2'; ID: '222'),
35.     (Title: 'Title3'; ID: '333'),
36.     (Title: 'Title4'; ID: '444'));
37. begin
38.     S := TNoteSet.Create;
39.     S.Insert(@Notes[3]);
40.     S.Insert(@Notes[2]);
41.     S.Insert(@Notes[1]);
42.     S.Insert(@Notes[0]);
43.     it := S.Min;
44.     repeat
45.       p := it.GetData;
46.       writeln('Title: ', p^.Title, ', ID: ', p^.ID);
47.     until not it.Next;
48.     it.Free;
49.     S.free;
50. end;
51.  
52. begin
53.   TestTSet;
54. end.
55.  

If iterating through it, one can also use the enumerator:

Code: Pascal  [Select][+][-]

1. [...]
2.     S := TNoteSet.Create;
3.     S.Insert(@Notes[3]);
4.     S.Insert(@Notes[2]);
5.     S.Insert(@Notes[1]);
6.     S.Insert(@Notes[0]);
7.     for p in S do
8.       writeln('Title: ', p^.Title, ', ID: ', p^.ID);
9.     S.free;
10. [...]
11.  

[avk]

Are you sure?

[dbannon]

...
If iterating through it, one can also use the enumerator:

Not for what i found -

Code: Pascal  [Select][+][-]

1.       NS := TNoteSet.Create;
2.       NS.Insert(AddItem('1111', 'Title1'));
3.       NS.Insert(AddItem('2222', 'Title2'));
4.       NS.Insert(AddItem('3333', 'Title3'));
5.       NS.Insert(AddItem('4444', 'Title3'));
6.       for p in NS do
7.             writeln('Title: ', p^.Title, ', ID: ', p^.ID);
8.  

generates -

unit1.pas(95,16) Error: Cannot find an enumerator for the type "TSet$2$crc2218E6FD"

And the iterator is sure needed at dispose time.

Code: Pascal  [Select][+][-]

1.       it := NS.Min;
2.       repeat
3.         dispose(it.GetData);
4.       until not it.Next;
5.  

Davo