Hi,

I am trying to create a Set Type...

   TMyEnum = (me1, me2, me3); // more than 500 elements
   TMySet = set of TMyEnum;

...but I get the following error:

"Error: illegal type declaration of set elements" [1]

The problem seems to be that TMyEnum has more than 256 elements.

Can I specify such Set with some compiler option ?

My fpc is pre 2.6, any change on new versions concerning Sets limits?

Thanks.

[1] A more specific message would help too. :)

Daniel Gaspary wrote

The problem seems to be that TMyEnum has more than 256 elements. Can I specify such Set with some compiler option ?

No.

My fpc is pre 2.6, any change on new versions concerning Sets limits?

No.

Jonas

Daniel Gaspary wrote

The problem seems to be that TMyEnum has more than 256 elements. Can I specify such Set with some compiler option ?

No. As far as I understand, sets are stored in 1 byte internally - as binary values. 256 is the max number of elements (bit values) it can hold in a byte.

Regards,
- Graeme -

In our previous episode, Graeme Geldenhuys said:

Sets are up to 32-byte (256bits), enums can be up to 32-bit.

Graeme Geldenhuys wrote

No. As far as I understand, sets are stored in 1 byte internally - as binary values. 256 is the max number of elements (bit values) it can hold in a byte.

This is one area where FPC could actually improve things. The 1 byte limit is purely historical. There are no 8-bit CPUs supported by FPC that would justify it.

I am annoyed by some LCL bugs which are there only for Delphi compatibility. This issue is similar. This kind of artificial limitation could easily be fixed. I think it should apply for {$mode objfpc} only.

Juha

Juha Manninen wrote

There are no 8-bit CPUs supported by FPC that would justify it.

It is unrelated to 8 bit cpus. Even Turbo Pascal 1.0 ran on a 16 bit cpu.

I am annoyed by some LCL bugs which are there only for Delphi compatibility. This issue is similar.

It is not.

This kind of artificial limitation could easily be fixed. I think it should apply for {$mode objfpc} only.

There is a already a test for larger set support: http://svn.freepascal.org/svn/fpc/trunk/tests/test/tset6.pp

Nobody has worked yet on implementing it, but if anyone thinks it's easy to do, please go ahead. For larger sets, especially if they are sparse, a simple hashtable-based class would probably be much faster and memory efficient than simply extending the default implementation though. With operator overloading and generics you might even be able to use more or less the same syntax as with built-in sets.

Jonas

Marco van de Voort wrote

Sets are up to 32-byte (256bits), enums can be up to 32-bit.

Ok, sorry. The limitation for sets is not one byte. Still, FPC could add support for still more bytes. 64-bit CPUs are now popular and the feature could easily be implemented for other CPUs, too.

Regards,
Juha

Juha Manninen wrote

This issue is similar. This kind of artificial limitation

I always wonder how people know more than me about the compiler :)

could easily be fixed.

Go ahead.

Jonas Maebe wrote

For larger sets, especially if they are sparse, a simple hashtable-based class would probably be much faster and memory efficient

Just some background..

I was using a Set because I needed a initialized constant "container" with a variable length.

It was a array of records, the set would be one of the fields. I believe it's not possible to have dynamic array initialized inside records.

TMyRecord = record
   TheSet: TMySet;
end;
const
        MyArray: array[TMyEnum] of TMyRecord = ( (TheSet: [me1, me3]),
(TheSet: [me2, me1]) );

Now I have changed the code to a function with a case returning the record.

:)
Ok, I sent my reply too quickly. I must study the compiler at some day. I must say that I don't like the situation where I cannot backup my claims with facts.
Now I cannot. I sill study the compiler later ...

Regards,
Juha

Jonas Maebe wrote

There is a already a test for larger set support: http://svn.freepascal.org/svn/fpc/trunk/tests/test/tset6.pp Nobody has worked yet on implementing it, but if anyone thinks it's easy to do, please go ahead. For larger sets,

especially if they are sparse, a simple hashtable-based class would probably be much faster and memory efficient
than simply extending the default implementation though. With operator overloading and generics you might even be
able to use more or less the same syntax as with built-in sets.

There is a generic hashset implementation in the stl package, which has no 256-element limit on set size. See
...\source\packages\fcl-stl\src\ghashset.pp
A .tex documentation file is included along with a hashsetexample.pp

Howard

As I recall (it's been almost 30 years since I looked at this) UCSD Pascal had a set size of 4096 bits. This was a p-code interpreter. I think the 32 bit set size was a result of the original TurboPascal being written for the Z-80. UCSD Pascal is long gone, TurboPascal staggers on.

Rolf

Without wanting to cause upset, before you make statements like that I think you could /really/ do with checking how many bits fit in a byte :-)

Provided that one calls a Z80 16-bit :-) More to the point: do any current CPUs have e.g. vector operations that suggest a realistic maximum size?

For larger sets... OK, how /does/ one declare a set of UTF-8 characters?

The current x86's bit test/set instructions support addressing the complete 32/64 bit address space. But the original 8086 didn't have any vector : this limitation is unrelated to
instruction sets, it's about deciding on a point at which you're going to waste a lot of memory by using a plain bitmap.

An UTF-8 character is not an ordinal data type and hence support for "set of <utf-8 character>" is orthogonal to support for larger sets. If you store them in strings or arrays, then you need a hashtable of strings or arrays (and/or support for sets of strings or arrays, which would probably be implemented using... a hashtable).

Jonas

That was pretty much my gist. Since these days Unicode is larger than 65536 codepoints I don't think there's any advantage to expanding sets from 256 to 65536 elements, efficient operations on sparse arrays of 256-element sets would be far better.

A modest expansion to be able to handle something like a bitboard for Go might be attractive though.

Mark Morgan Lloyd wrote

That was pretty much my gist. Since these days Unicode is larger than 65536 codepoints I don't think there's any advantage to expanding sets from 256 to 65536 elements, efficient operations on sparse arrays of 256-element sets would be far better.

In my case the enum has near 600 elements.

TMyEnum = (me1, me2...);

The set though would never be used to contain more than 256.

TMySet = set of TMyEnum;

Is it not viable to modify the compiler to compile the code and raise an exception if I try to add more than 256 elements to the set ?

A set is basically a bitpacked array of boolean. Element X is set to true if you add X to the set, and to false if you remove it again. That means that if you have a set with 600 possible values, you need at least 600 bits, regardless of how many elements are inside it.

The above also shows an alternative to sets in that case: you can use a bitpacked array[TMyEnum] of boolean instead. Of course, then you can't use the regular set operators.

Jonas

If the array is a named one (e.g. "TMyArraySet = bitpacked array[TMyEnum] of Boolean") then operator overloading could be used...

Regards,
Sven

Your explanation made the implementation problem clear to me. And the alternative is interesting.

Thank you.

Sven Barth wrote

If the array is a named one (e.g. "TMyArraySet = bitpacked array[TMyEnum] of Boolean") then operator overloading could be used...

Yes, but since neither open nor dynamic bitpacked arrays are supported, you'd have to reimplement this for every single pseudo-set type you want to use (except maybe if you use generics, if generics for simple types already work).

Jonas

No, because the elements in a set are dictated by their position. A set that can contain anything between 0 and 256 elements occupies 8 bytes in memory with the (bit representing the) 0 element at one end and the (bit representing the) 256 element at the other, a set to contain up to (say) 257 elements would require more space and that's not supported.

Generics do work for array, but maybe not for indices. Also you'd need to declare the operators anyway. Best solution in this case might be to encapsulate the array in a record and define the operators there...

Regards,
Sven

Sven Barth wrote

Generics do work for array, but maybe not for indices.

Only for type of element as I remember.

Also you'd need to declare the operators anyway. Best solution in this case might be to encapsulate the array in a record and define the operators there...

Maybe then it will be easier to implement compiler support using bitpacked arrays instead of creating so complex workarounds?

Best regards,
Paul Ishenin

Here is a unit that could be useful.

Works with pentium and Win32; not tested with other CPUs or operating system.

I hope you have 7zip, or I will create a zip file.

Greetings

Gerhard

Sorry, there are some changes neccessary:
drop the reference to unit
uAsms
delete the line
FillOnes ( ...
it was there for debugging purposes

Once upon a time, Mark Morgan Lloyd said:

Probably a typo, but 8 bit * 8 bytes = 64 elements. So I suppose you mean `[...] occupies 32 bytes in memory [...]`?

Just so nobody gets confused :-)

Definitely a typo, or rather the fingers running ahead of the brain. I was thinking of various compilers I'd come across that ordered things differently and how best to not imply that [0] invariably mapped onto $0001.

I was going to raise the possibility of declaring more than one subset using ranges, but I just noticed that
{{{
TMySet = set of 300..305; .
}}}
doesn't compile. Isn't that supported by Delphi?

Best regards,
Flávio

Try this:

unit genericset (t);
interface
type genset=pointer;
(*! The functions getnext, getlast and getfirst must never be called on an
empty set. The function
getnext should never be called on the last element of a set. *)
procedure genericsetnext(var v:t;s:genset);
procedure genericsetfirst(var v:t;s:genset);
procedure genericsetlast(var v:t;s:genset);
function genericsetislast(v:t;s:genset):boolean;
function isemptygenericset(s:genset):boolean;
function genericsetnotempty(s:genset):boolean;
procedure addtogenericset(var s:genset;v:t);
function genericsetsingleton(singleton:t):genset;
function genericsetunion(s1,s2:genset):genset;
function genericsetdifference(s1,s2:genset):genset;
function genericsetintersection(s1,s2:genset):genset;
function genericsetsymetricdifference(s1,s2:genset):genset;
function genericseteq(s1,s2:genset):boolean;
function genericsetneq(s1,s2:genset):boolean;
function isin(s:genset;v:t):boolean;
procedure genericsetisin(s:genset;v:t;var b:boolean);
procedure emptygenericset(var newset:genset);{ set newset to be empty }
function genericsetle(s1,s2:genset):boolean;{ s1<=s2}
function genericsetge(s1,s2:genset):boolean;
implementation
type pset=^setrec;
     setrec = record
	 	value:t;
		left,
		right:pset;
		bal:integer;
		end;
	cheat = record
		case boolean of
		true:(yes:pset;);
		false:(no:pointer);
		end;
		procedure phex(p:pointer);
	var r:record
		case boolean of
		true:(i:integer);
		false:(p:pointer);
		end;
	begin
		r.p:=p;
		write(r.i);
	end;
	function pointer2pset(p:pointer):pset;
	begin
	           pointer2pset:=p;
	end;
	function newnode(var key:t; l,r:pset):pset;
	var temp:pset;
	begin
		new(temp);
		with temp^ do begin
			value:=key; left:=l; right:=r;
		end;
		newnode:=temp;
	end;
	procedure genericsetisin(s:genset;v:t;var b:boolean);
	begin b:=isin(s,v);end;
	function genericsetlt(s1,s2:genset):boolean;
		begin genericsetlt:= not isemptygenericset(genericsetdifference(s2,s1))
end;
        function genericsetgt(s1,s2:genset):boolean;
		begin genericsetgt:=genericsetlt(s2,s1); end;
	function genericsetle(s1,s2:genset):boolean;
		begin genericsetle:= not genericsetgt(s1,s2); end;
	function genericsetge(s1,s2:genset):boolean;
		begin genericsetge:=genericsetle(s2,s1) end;
	function genericsetneq(s1,s2:genset):boolean;
		begin genericsetneq:= not genericseteq(s1,s2); end;
	function genericseteq(s1,s2:genset):boolean;
		begin	genericseteq:=isemptygenericset(genericsetsymetricdifference(s1,s2))
end;
	function genericsetsymetricdifference(s1,s2:genset):genset;
	begin
genericsetsymetricdifference:=genericsetdifference(genericsetunion(s1,s2),genericsetintersection(s1,s2));
	end;
	function genericsetintersection(s1,s2:genset):genset;
	var temp:genset;
		procedure rec(p:pset);
		begin
			if pnil then
			with p^ do begin
				if isin(s2,value) then addtogenericset(temp,value);
				rec(right);rec(left);
			end
		end;
	begin
		emptygenericset(temp);
		rec(pointer2pset(s1 ));
		genericsetintersection:=temp;
	end;
	function genericsetunion(s1,s2:genset):genset;
	var temp:genset;
		procedure rec(p:pset);
		begin
			if pnil then
			with p^ do begin
				addtogenericset(temp,value);
				rec(right);rec(left);
			end
		end;
	begin
		{emptygenericset(temp);
		rec(pointer2pset(s1 ));}
		temp:=s1;
		rec(pointer2pset(s2 ));
		genericsetunion:=temp;
	end;
	function genericsetnotempty(s:genset):boolean;begin genericsetnotempty:=not
isemptygenericset(s) end;
	function isemptygenericset(s:genset):boolean;begin isemptygenericset:=s=nil
end;
	procedure emptygenericset(var newset:genset);
	begin
		newset :=nil;
	end;
	function newset(v:t;l,r:pset):pset;
	var temp:pset;
	begin
		new(temp);
		with temp^ do
		begin
		   value:=v;left:=l;right:=nil;bal:=0;
		end;
		newset:=temp
	end;
	function find(p:pset;v:t):pset;
	begin
		if p=nil then find:=nil
		else with p^ do
		begin
		{   writeln('find ',v,' key ', p^.value);}
		   if v<value then find:=find(left,v)
		   else if value &lt; v then find:=find(right,v)
		   	else find:=p;
		end;
	end;
	function del(var p:pset;v:t):pset;
        var dup,copy:pset;
	begin
		if p=nil then  del:=nil else begin
                  new (dup); dup^:=p^; copy:=p; p:=dup;
		  with p^ do
		  begin
		   if v&lt;value then del:=del(left,v)
		   else if value &lt; v then del:=del(right,v)
		   	else begin
				del:=left;
			        p:=right;
			end;
                  end;
		end;
	end;
        function isin(s:genset;v:t):boolean;begin
	      {  writeln('isin ', v);}
		isin:=find(pointer2pset(s ),v)&lt;>nil;
	 end;
	procedure genericsetlast(var v:t;p1:genset);
		procedure genericsetright(p:pset);
		begin
			with p^ do
			begin
				if right=nil then v:=value
				else genericsetright(right)
			end
		end;
	begin
		genericsetright(pointer2pset(p1 ));
	end;
	function genericsetislast(v:t;p1:genset):boolean;
	var v2:t;
	begin
		genericsetlast(v2,p1);
		genericsetislast:=v2=v;
	end;
	procedure genericsetfirst(var v:t;p1:genset);
		procedure genericsetleft(p:pset);
		begin
			with p^ do
			begin
				if left=nil then v:=value
				else genericsetleft(left)
			end
		end;
	begin
		genericsetleft(pointer2pset(p1 ));
	end;
    function genericsetnextnode(p:pset;v:t):pset;
	  var p1:pset;
	  begin
	  	if p=nil then genericsetnextnode:=nil else
		with p^ do
		begin
		  if v<value then begin
		  	p1:=genericsetnextnode(left,v);
			if p1=nil then genericsetnextnode:=p else genericsetnextnode:=p1
		  end
		  else genericsetnextnode:=genericsetnextnode(right,v);
		end
	  end;
	procedure genericsetnext(var v:t;s:genset);
	(*! Note that the genset s should never be nil when this is called. *)
	  var p2:pset;
	begin
		p2:=genericsetnextnode(pointer2pset(s ),v);
		v:=p2^.value;
	end;
	type tree=pset;
        typekey=t;
        procedure lrot( var tp : tree );
        var     temp : tree;
                a : integer;
        begin
                temp := tp;
                tp:= tp^.right;
                temp^.right := tp^.left;
                tp^.left := temp;
                {*** adjust balance ***}
                a := temp^.bal;
                temp^.bal := a - 1 - ( tp^.bal max  0 );
                tp^.bal := ( a-2)min( a+tp^.bal-2)min( tp^.bal-1);
        end;
        procedure rrot( var tp : tree );
        var     temp : tree;
                b : integer;
        begin
                temp := tp;
                tp := tp^.left;
                temp^.left := tp^.right;
                tp^.right := temp;
                {*** adjust balance ***}
                b := temp^.bal;
                temp^.bal := b + 1 + ( -tp^.bal max 0 );
                tp^.bal := -(( -b-2)min( -b-tp^.bal-2)min( -tp^.bal-1));
        end;
	function insert( key : typekey; var tp : tree ) : integer;
	var     incr : integer;dup:tree;
	begin
		insert := 0;
		if tp = nil then begin
                	tp:= NewNode( key, nil, nil );
                	tp^.bal := 0;
                	insert := 1;
                end
		else if tp^.value = key then begin
                	 {*** Key already in table ***}
		end
		else begin
		   // make sure it is applicative and does not
		   // alter the original tree
		   new(dup);
		   dup^:=tp^;
		   tp:=dup;
		   with tp^ do
		   begin
        		if value&lt; key then
				 incr := insert( key, right )
                else
				 incr := -insert( key, left );
        		bal := bal + incr;
        		if (incr &lt;> 0) and (bal  0) then
                		if bal < -1 then
				begin
                        {*** left subtree too tall: right rotation needed
***}
                        		if left^.bal < 0 then   rrot( tp )
                                	else    begin   lrot( left ); rrot( tp )
end
				end
                		else    if bal > 1 then
				begin
                        {*** right subtree too tall: left rotation needed
***}
                        		if right^.bal > 0 then  lrot( tp )
                                	else    begin   rrot( right ); lrot( tp )
end
				end
                	else    insert := 1;
		   end;
        	end
	end;
	procedure addtogenericset(var s:genset; v:t);
	var p:pset;count:integer;
	begin
		if not isin(s,v) then begin
			p:=pointer2pset(S );
			count:=insert(v,p);
			s :=p;
		end;
	end;
	procedure removefromgenericset(var s:genset; v:t);
	var p,p2:pset;g:genset;
	begin
		if  isin(s,v) then begin
			p:=pointer2pset(S );
			p2:=del(p,v);
			g:=p2;
			s :=p;
			s:=genericsetunion(s,g);
		end;
	end;
	function genericsetsingleton(singleton :t):genset;
	var s:genset;
	begin
		emptygenericset(s);
		addtogenericset(s,singleton);
		genericsetsingleton:= s;
	end;
	function genericsetdifference(s1,s2:genset):genset;
	const threshold=2;
	var temp:genset;
		procedure rec(p:pset);
		begin
			if pnil then
			with p^ do begin
				if not isin(s2,value) then addtogenericset(temp,value);
				rec(right);rec(left);
			end
		end;
		procedure recb(p:pset);
		begin
			if pnil then
			with p^ do begin
				removefromgenericset(temp,value);
				recb(right);recb(left);
			end
		end;
		(*! this traverses the set just far enough to detemine if a set is bigger
than
                    a threshold size *)
		function big(p:pset;i:integer):integer;
		var j:integer;
		begin
			if i>threshold then big:=i else
			begin
				if p=nil then big := i
				else
				begin
					j:= big(p^.left,i+1) ;
					if j>threshold then big:=j
					else big:=big(p^.right,j);
				end
			end;
		end;
	begin
		if big(pointer2pset(s2),0)>threshold then begin
			emptygenericset(temp);
			rec(pointer2pset(s1 ));
		end
		else begin
			temp:=s1;
			recb(pointer2pset(s2));
		end;
		genericsetdifference:=temp;
	end;
BEGIN
end.