Count elements in set

[LemonParty]

Hello.

Is there an intrinsic to count elements in set? Include sets with more than 32 elements.

[Kays]

[…] Is there an intrinsic to count elements in set? […]

No, Extended Pascal defines a built‑in cardinality function, but it isn’t implemented by the FPC (yet).

[Martin_fr]

https://www.freepascal.org/docs-html/rtl/system/popcnt.html

[Kays]

https://www.freepascal.org/docs-html/rtl/system/popcnt.html

Well, that doesn’t work on sets.

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

1. program popCntTest(input, output);
2.         type
3.                 flag = (A, B, C);
4.                 flags = set of flag;
5.         var
6.                 option: flags;
7.         begin
8.                 option := [A, C];
9.                 writeLn(popCnt(option))
10.         end.

Code: Text  [Select][+][-]

1. popCntTest.pas(9,24) Error: Incompatible type for arg no. 1: Got "flags", expected "QWord"

And it’s capped to bitSizeOf(ALUSInt) (not necessarily always more than 32).

[Thaddy]

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

1. {$ifdef fpc}{$mode objfpc}{$endif}
2. type
3.   flag = (A, B, C);
4.   flags = set of flag;
5. var
6.   option:flag;
7.   options:flags;
8.   i:integer = 0;
9. begin
10.   options := [A, C];
11.   for option in options do inc(i);
12.   writeln(i);  // 2          
13. end.

[creaothceann]

that doesn’t work on sets

Sets are implemented as one or several integers, so you could use PopCnt on parts of the set: https://godbolt.org/z/EoqrsrvYY

[Thaddy]

@LemonParty
two solutions, the second for 3.3.1. only (works a bit like an intrinsic).

We discussed something like the first on the forum back in 2019:

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

1. program countdays;
2. {$mode objfpc}{$asmmode intel}
3. type
4.   dayname =  (Monday, Tuesday, Wednesday,Thursday, Friday, Saturday, Sunday);
5.   daynames = set of dayname;
6. const
7.   workweek:daynames = [Monday, Tuesday, Wednesday,Thursday, Friday];  
8.   weekend:daynames = [Saturday, Sunday];
9.  
10. function daycount(const num:daynames): integer; assembler; nostackframe;
11. // this is for 64 bit, for 32 bit use popcnt eax,eax
12. asm
13.   popcnt eax, ecx  
14. end;
15.  
16. begin
17.   writeln(daycount(weekend));
18.   writeln(daycount(workweek));
19. end.

In trunk, you can create a generic popcount like so:

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

1. {$mode delphi}{$if fpc_fullversion < 30301}{$error needs 3.3.1}{$ifend}
2. {$modeswitch implicitfunctionspecialization}
3. {$modeswitch functionreferences}
4. type
5.   // 128 bits
6.   poword = ^oword;
7.   oword  = record
8.   a,b:qword;
9.   end;
10.   // 256 bits
11.   phword = ^HWord;
12.   HWord  = record
13.   a,b,c,d:qword;
14.   end;
15.  
16.   dayname =  (Monday, Tuesday, Wednesday,Thursday, Friday, Saturday, Sunday);
17.   daynames = set of dayname;
18.   monthname = (January, February, March,April, May, June, July, August, September, October, November, December);
19.   monthnames = set of monthname;
20. const
21.   workweek:daynames = [Monday, Tuesday, Wednesday,Thursday, Friday];  
22.   weekend:daynames = [Saturday, Sunday];
23.   winter:monthnames = [December, January, February];
24.   spring:monthnames = [March,April, May];
25.   summer:monthnames = [June, July, August];
26.   fall:monthnames = [September, October, November];
27.  
28. function popcount<T{:set}>(const aSet:T): integer; inline;
29. var
30.   a,b,c,d:qword;
31. begin
32.   Result := 0;
33.    if GetTypeKind(T) = tkSet then
34.    case SizeOf(aSet) of
35.    1      : Result := popcnt(PByte(@aSet)^);     // 8
36.    2      : Result := popcnt(PWord(@aSet)^);     // 16
37.    3..4   : Result := popcnt(PCardinal(@aSet)^); // 32
38.    8..16  : Result := popcnt(PQword(@aSet)^);    // 64
39.    17..32 : begin                                // 128
40.               a:= poword(@aSet)^.a;
41.               b:= poword(@aSet)^.b;
42.               Result := popcnt(PQword(@a)^)+popcnt(PQword(@b)^)
43.            end;
44.    33..64 :begin                                 // 256
45.               a:= phword(@aSet)^.a;
46.               b:= phword(@aSet)^.b;
47.               c:= phword(@aSet)^.c;
48.               d:= phword(@aSet)^.d;
49.               Result := popcnt(PQword(@a)^)+
50.                         popcnt(PQword(@b)^)+
51.                         popcnt(PQword(@c)^)+
52.                         popcnt(PQword(@d)^)
53.            end;
54.    else
55.      result := 0;  // raise exception.create('set too large or not a set');
56.    end;
57. end;
58.  
59. begin
60.   writeln(popcount(weekend));
61.   writeln(popcount(workweek));
62.   writeln(popcount(summer));
63. end.
64.  

Note there is no set or ordinal constraint yet, so be careful.
Works for any set, though.
Just as fast as the various popcnt overloads. (expands to the dword overload)

[bytebites]

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

1. program popcnttest;
2. {$mode objfpc}
3. {$AsmMode intel}
4. type
5.   flag = (
6.   A1, A2, A3, A4, A5, A6, A7, A8, A9, A10,
7.   B1, B2, B3, B4, B5, B6, B7, B8, B9, B10,
8.   C1, C2, C3, C4, C5, C6, C7, C8, C9, C10,
9.   D1, D2, D3, D4, D5, D6, D7, D8, D9, D10
10.   );
11.   flags = set of flag;
12. var
13.   options: flags;
14.   i: qword absolute options;
15.  
16. function setcount(const num:flags): integer; assembler; nostackframe;
17. // this is for 64 bit, for 32 bit use popcnt eax,eax
18. asm
19.   popcnt eax, ecx
20. end;
21.  
22. generic function popcnt<T{:set}>(const aSet:T): integer; inline;
23. begin
24.    Result := popcnt(PCardinal(@aSet)^);
25. end;
26.  
27. begin
28.   options := [A1, C1, B1, B4, D7, D10];
29.   writeln(BinStr(i,64));
30.   writeln(sizeof(options));
31.   writeLn(popCnt(i));
32.   writeLn(setcount(options));
33.   writeLn(specialize popcnt<flags>(options))
34. end.
35.  

Linux-64 result:

0000000000000000000000001001000000000000000100000010010000000001
32
6
9
4

[Thaddy]

Edited my second example a bit: the generic version now limits to sets and covers all set lengths upto and including 256 elements in the correct way. They are not always 32 bit, that is misleading.
A set can be 1,2,4,8,16 or 32 bytes long.

So @Bytebytes, your code - and my first example - is wrong.
Also note I now test the generic for the constraint to set.
My second example is right, at least I think so.
Also note that depending on cpu the asm popcnt is called anyway and does not need a table.
[edit]
Improved  version: localized octword and hexword. Added Set exceptions

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

1. {$mode delphi}{$if fpc_fullversion < 30301}{$error needs 3.3.1}{$ifend}
2. {$modeswitch implicitfunctionspecialization}
3. {$modeswitch functionreferences}
4. uses sysutils;
5. type  
6.   ESetException = class(Exception);
7.   dayname =  (Monday, Tuesday, Wednesday,Thursday, Friday, Saturday, Sunday);
8.   daynames = set of dayname;
9.   monthname = (January, February, March,April, May, June, July, August, September, October, November, December);
10.   monthnames = set of monthname;
11. const
12.   workweek:daynames = [Monday, Tuesday, Wednesday,Thursday, Friday];  
13.   weekend:daynames = [Saturday, Sunday];
14.   winter:monthnames = [December, January, February];
15.   spring:monthnames = [March,April, May];
16.   summer:monthnames = [June, July, August];
17.   fall:monthnames = [September, October, November];
18.  
19. function popcount<T{:set}>(const aSet:T): integer; inline;
20. type
21.   // 128 bits - octword
22.   poword = ^oword;oword  = record a,b:qword;end;
23.   // 256 bits - hexword
24.   phword = ^HWord;HWord  = record a,b,c,d:qword;end;
25. var
26.   a,b,c,d:qword;
27. begin
28.    if GetTypeKind(T) = tkSet then
29.   // * MUST* dereference!!!
30.    case SizeOf(aSet) of
31.    1      : Result := popcnt(PByte(@aSet)^);     // 8
32.    2      : Result := popcnt(PWord(@aSet)^);     // 16
33.    4      : Result := popcnt(PCardinal(@aSet)^); // 32
34.    8      : Result := popcnt(PQword(@aSet)^);    // 64
35.    16     : begin                                // 128
36.               a:= poword(@aSet)^.a;
37.               b:= poword(@aSet)^.b;
38.               Result := popcnt(a)+popcnt(b);
39.            end;
40.    32     :begin                                 // 256
41.               a:= phword(@aSet)^.a;
42.               b:= phword(@aSet)^.b;
43.               c:= phword(@aSet)^.c;
44.               d:= phword(@aSet)^.d;
45.               Result := popcnt(a)+popcnt(b)+popcnt(c)+popcnt(d);
46.           end;
47.    else
48.      raise ESetException.Create('Set too large');
49.    end
50.  else raise ESetException.Create('Not a set');
51. end;
52.  
53. begin
54.   writeln(popcount(weekend));
55.   writeln(popcount(workweek));
56.   writeln(popcount(summer));
57. end.

[bytebites]

Your nongengeric daycount is still wrong.

Other issue

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

1. popcnt(PQword(@a)^)

is same as

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

1. popcnt(a)

[Bart]

Edited my second example a bit: the generic version now limits to sets and covers all set lengths upto and including 256 elements in the correct way. They are not always 32 bit, that is misleading.
A set can be 1,2,4,8,16 or 32 bytes long.

Nice piece of code.
But why does your code test for ranges, as if a set (tkSet) with size 3 or 19 could exist?
And isn't "popcnt(PByte(@aSet)^)" the same as "popcnt(Byte(aSet))" (no dereference needed)?

Bart

[Thaddy]

I corrected that.

[Thaddy]

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

1. popcnt(a)

not if a is a set....... You can't use a set var for popcnt.
My version works for 1,2 and 4 byte.
If you would want to use it you would need overrides for any set type to have.
Anyway, I'll add the generic one to my tools.

[bytebites]

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

1. popcnt(a)

not if a is a set....... You can't use a set var for popcnt.
My version works for 1,2 and 4 byte.
If you would want to use it you would need overrides for any set type to have.
Anyway, I'll add the generic one to my tools.

How dword suddenly becomes to set?

[avk]

Edited my second example a bit: the generic version now limits to sets and covers all set lengths upto and including 256 elements in the correct way. They are not always 32 bit, that is misleading.
A set can be 1,2,4,8,16 or 32 bytes long.
...

Just as a counterexample:

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

1. program test;
2. {$mode objfpc}{$packset 1}
3. type
4.   TRange36  = 0..35;
5.   TRange101 = 0..100;
6.   TRange151 = 0..150;
7. var
8.   s1: set of TRange36;
9.   s2: set of TRange101;
10.   s3: set of TRange151;
11. begin
12.   WriteLn('Size of s1 = ', SizeOf(s1));
13.   WriteLn('Size of s2 = ', SizeOf(s2));
14.   WriteLn('Size of s3 = ', SizeOf(s3));
15. end.
16.  

and it prints:

Code: [Select]

Size of s1 = 5
Size of s2 = 13
Size of s3 = 19