[beyond fixing]FPGMAP accepts duplicates using ADD

[jamie]

Do you really think allowing the ADD to simply attach to the list when there is matching keys already in the list?

  From what i understand MAPs dont allow for duplicating keys, in fact it seems the duplicate property seems to be ignored.

[paweld]

TFPGMap allows duplicates depending on the configuration. By default, when sorting is disabled, duplicates are allowed.
https://www.freepascal.org/docs-html/rtl/fgl/tfpsmap.duplicates.html

[jamie]

I read all of that, the duplicates property has no effect. In fact all other aspects methods do follow the correct path.

 Setting or adding using the default property works as it should, no duplicates and adds to the list only if not there or simply replaces the data content if key already exist. That is how a map should work.
 Its the ADD that does not follow this if there is already existing keys in the list.

I see this as bug since the duplicate appears to do nothing.

Jamie

[marcov]

As far as I can see ordering is only used for sort and find.   I sometimes wonder why people use FGL (or fcl-stl for that matter) in the first place, instead of rtl-generics.  These packages were mostly for pre FPC 3 generics, full of workarounds for issues that no longer exist.

However that doesn't mean the alternatives shouldn't be fixed. Please file a bug with a short example program to test.

[paweld]

For dupIgnore to work, you need to enable sorting.

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

1. program Project1;
2.  
3. {$mode objfpc}{$H+}
4.  
5. uses
6.   Classes, SysUtils, fgl;
7.  
8. type
9.   TMap = specialize TFPGMap<Integer, Integer>;
10.  
11. var
12.   map1, map2: TMap;
13.   i: Integer;
14.   s: String;
15. begin
16.   //
17.   map1 := TMap.Create;
18.   map1.Add(1, 1);
19.   map1.Add(2, 1);
20.   map1.Add(3, 1);
21.   map1.Add(4, 1);
22.   map1.Add(1, 2);
23.   map1.Add(3, 2);
24.   map1.Add(1, 3);
25.   //
26.   map2 := TMap.Create;
27.   map2.Sorted := True;
28.   for i := 0 to map1.Count - 1 do
29.     map2.Add(map1.Keys[i], map1.Data[i]);
30.   //
31.   s := '';
32.   for i := 0 to map1.Count - 1 do
33.     s := s + Format('%d: (%d x %d), ', [i + 1, map1.Keys[i], map1.Data[i]]);
34.   WriteLn('map1: count: ', map1.Count, ' > ', s);
35.   s := '';
36.   for i := 0 to map2.Count - 1 do
37.     s := s + Format('%d: (%d x %d), ', [i + 1, map2.Keys[i], map2.Data[i]]);
38.   WriteLn('map2: count: ', map2.Count, ' > ', s);
39.   map1.Free;
40.   map2.Free;
41.   ReadLn;
42. end.            

output:

Code: [Select]

map1: count: 7 > 1: (1 x 1), 2: (2 x 1), 3: (3 x 1), 4: (4 x 1), 5: (1 x 2), 6: (3 x 2), 7: (1 x 3),
map2: count: 4 > 1: (1 x 3), 2: (2 x 1), 3: (3 x 2), 4: (4 x 1),
@marcov: I use it because it's simple and fast - it's more than enough for my needs.

[jamie]

Inregsrdless, using add should not allow duplicated keys, sort or no sort.

Btw, i used constand strings as the key so it appears that maybe string conent is not being compared but maybe the pointer to string, which could be different but same content. Just a hunch.
If that is the case then maybe a string compare should be used instead of pointer search.

[marcov]

@marcov: I use it because it's simple and fast - it's more than enough for my needs.

To be fair, I also use lightcontainers for simple stuff, specially when ordering is important.

[Zvoni]

@marcov: I use it because it's simple and fast - it's more than enough for my needs.

To be fair, I also use lightcontainers for simple stuff, specially when ordering is important.

Same here.
For simple Key/Value i usually use TStringList.

And i remember looking under the hood of TStringlist/TStrings, and found out, that IgnoreDup only works if sorted is true, too.
Because when adding/inserting into a sorted list, it actually does a Search/Find with yes/no-action afterwards (Yes=Replace value, No=Add Key/Value)

[jamie]

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

1. procedure TForm1.Button1Click(Sender: TObject);
2. Type
3.   TTestGen = Specialize TFPGMap<Integer,String>;{uses FGL}
4. var
5.   O:TTestGen;
6. begin
7.   O := TTestGen.Create;
8.   O.Duplicates := DupError;
9.   O.Add(1,'Data1');
10.   O.Add(1,'Data2'); //This duplicates the same existing key.
11.   O[1]:='Data2'; //This will not duplcate keys.
12.   Caption := O.Count.Tostring; //Now we have 2 keys of the same content.
13.   O.Free;
14. end;                                                                    
15.  

I thought maybe it was the string constants I was using as a KEY value but apparently, it's not, using ADD will simply duplicate existing keys no matter the types.
 But using the default works, it does not duplicate keys.

 I've been tracking down bad data used in MAPS and I have come across this as the cause, I need to stop using the ADD method, it does not work properly.


 Maybe it's been fixed, this is from FPC 3.2.2

[Thaddy]

For duplicates to work, the map needs to be sorted.
If you set the map to sorted, a duplicate error will be thrown.
If the list is not sorted, adding items becomes really expensive because the whole list needs to be scanned on every addition, O(N) so there is some logic to that.

It is also documented:
https://www.freepascal.org/docs-html/rtl/fgl/tfpsmap.duplicates.html
which explicitly states that the value is ignored if not sorted.
Maybe you overlooked that since it is only documented for the ancestor TFpsMap.

[Thaddy]

To add: you can easily implement it but it does not make any sense to allow that: on large lists the becomes neigh impossible to work with. One of the original sins in the non-generic TList.

[jamie]

One of us has an English barrier problem.

The issue is, duplicates are not supposed to happen!


using all other methods work as expected, [] ,SetOrAdd , or whatever that was.

  Don't worry about it, I get it. some want to simply burn the bits on the server making there presents known to everyone that browses this formum.

Simply put, TFPGMAP has a feature or bug that is simply counter intuitive or broken.
 Simple fix is not to use ADD for now or add to my own Generics as a replacement, a corrected version.

[marcov]

@marcov: I use it because it's simple and fast - it's more than enough for my needs.

To be fair, I also use lightcontainers for simple stuff, specially when ordering is important.

Same here.
For simple Key/Value i usually use TStringList.

Lightcontainers allows non string keys, and doesn't suffer as much from performance degradation on larger lists. I actually made the (non generic) version in 2005 when a dataset grew to 200000 items (and later some to 1.6M items), and the TStringlist ordered insertion performance degradation became very noticeable. Also in some cases I used integers as keys, but converted to strings.

But I couldn't go to a hash, because the algorithm needed to inspect values adjacent to a lookup. 

Basically where tstringlist is an array wrapper, lightcontainers is an array of array wrapper, where the deepest level of arrays are kept at a certain size (say 512-1024 items) to keep insertion relatively fast. It works with iterators to visit though. So it is not 100% drop in for TStringlist, but is very similar.

I later generalised using generics  to support non string keys, and have for..in iterator support etc. I don't know if I handle duplicates though, that wasn't really needed.

[marcov]

One of us has an English barrier problem.

The issue is, duplicates are not supposed to happen!

TStringlist behaves the same, duplicates only on sorted collections. See https://www.freepascal.org/docs-html/current/rtl/classes/tstringlist.duplicates.html

[Thaddy]

What is the barrier? O(N).....

Great example of not knowing what you are talking about.

An unsorted list needs to be examined one (1) member ar a time. That is called linear...
The larger a list becomes, the longer it takes. As opposed to O(log N)
Now, when a list is sorted, the lookup is simple, at most 7 probes in a worse case scenario.
Adding/inserting is a bit more costly but still much faster. Basics.

Go back to school. This is silly. No, plain stupid.  from a member with lots of experience..

It is so stupid it is beyond belief.