Lazarus

Free Pascal => General => Topic started by: Thaddy on September 10, 2019, 10:15:11 am

Title: Large or huge sets
Post by: Thaddy on September 10, 2019, 10:15:11 am
Large or huge sets are often requested. Just today I needed one. Wrote it in ten minutes, but maybe useful?
If the critics are not too harsh, I will add it to to the wiki.
Note it can be written *way* more efficient.
Code: Pascal  [Select][+][-]
  1. {$mode objfpc}{$inline on}
  2. { A simple way to implement large or huge sets.
  3.  (c) 2019 Thaddy de Koning. No license and not
  4.  re-licensable: free for all to use.
  5.  Copyright holds:
  6.  You can not claim license nor copyrigths }
  7. unit largesets;
  8. { Operator      Action
  9.   ---------------------------------------------
  10.   +             Union
  11.   -             Difference
  12.   *             Intersection
  13.   ><        Symmetric difference
  14.   <=        Contains
  15.   include   Include an element in the set
  16.   exclude   Exclude an element from the set
  17.   in        Check wether an element is in a set
  18. }
  19. interface
  20. uses
  21.   generics.collections;
  22.  
  23. type
  24.   TWordSet  = specialize TSortedHashSet<word >;
  25.   { The next two can cause some real memory pressure, be careful }
  26.   TDWordSet = specialize TSortedHashSet<dword>;
  27.   TQWordSet = specialize TSortedHashSet<Qword>;
  28.  
  29.   { union }
  30.   operator + (const a,b:TWordset ):TWordSet;
  31.   operator + (const a,b:TDWordset):TDWordSet;
  32.   operator + (const a,b:TQWordset):TQWordSet;
  33.  
  34.   { difference }
  35.   operator - (const a,b:Twordset ):TWordSet;
  36.   operator - (const a,b:TDwordset):TDWordSet;
  37.   operator - (const a,b:TQwordset):TQWordSet;
  38.  
  39.   { intersection }
  40.   operator * (const a,b:TwordSet ):TWordSet;
  41.   operator * (const a,b:TDwordSet):TDWordSet;
  42.   operator * (const a,b:TQwordSet):TQWordSet;
  43.  
  44.   { symmetric difference }
  45.   operator >< (const a,b:TWordSet ):TWordSet;
  46.   operator >< (const a,b:TDWordSet):TDWordSet;
  47.   operator >< (const a,b:TQWordSet):TQWordSet;
  48.  
  49.   { contains }
  50.   operator <= (const a,b:TWordSet ):Boolean;
  51.   operator <= (const a,b:TDWordSet):Boolean;
  52.   operator <= (const a,b:TQWordSet):Boolean;
  53.  
  54.   { in }
  55.   operator in (const a:word; const b:TWordset ):Boolean;
  56.   operator in (const a:dword;const b:TDWordset):Boolean;
  57.   operator in (const a:qword;const b:TQWordset):Boolean;
  58.  
  59.   { include }
  60.   procedure include(const a:TWordSet; const b:Word);
  61.   procedure include(const a:TDWordSet;const b:DWord);
  62.   procedure include(const a:TQWordSet;const b:QWord);
  63.  
  64.   { exclude }
  65.   procedure exclude(const a:TWordSet;const  b:Word);
  66.   procedure exclude(const a:TDWordSet;const b:DWord);
  67.   procedure exclude(const a:TQWordSet;const b:QWord);
  68.  
  69. implementation
  70.  
  71.   { union }
  72.   operator + (const a,b:TWordset):TWordSet;
  73.   begin  
  74.     b.UnionWith(a);
  75.     Result := b;
  76.   end;  
  77.  
  78.   operator + (const a,b:TDWordset):TDWordSet;
  79.   begin
  80.     b.UnionWith(a);
  81.     Result := b;
  82.   end;
  83.  
  84.   operator + (const a,b:TQWordset):TQWordSet;
  85.   begin
  86.     b.UnionWith(a);
  87.     Result := b;
  88.   end;
  89.  
  90.   { difference }
  91.   operator -(const a,b:Twordset):TWordSet;
  92.   begin
  93.     b.ExceptWith(a);
  94.     result:=b;
  95.   end;
  96.  
  97.   operator -(const a,b:TDwordset):TDWordSet;
  98.   begin
  99.     b.ExceptWith(a);
  100.     result:=b;
  101.   end;
  102.  
  103.   operator -(const a,b:TQwordset):TQWordSet;
  104.   begin
  105.     b.ExceptWith(a);
  106.     result:=b;
  107.   end;
  108.  
  109.   { intersection }
  110.   operator *(const a,b:TwordSet):TWordSet;
  111.   begin
  112.     b.IntersectWith(a);
  113.     Result := b;
  114.   end;
  115.  
  116.   operator *(const a,b:TDwordSet):TDWordSet;
  117.   begin
  118.     b.IntersectWith(a);
  119.     Result := b;
  120.   end;
  121.  
  122.   operator *(const a,b:TQwordSet):TQWordSet;
  123.   begin
  124.     b.IntersectWith(a);
  125.     Result := b;
  126.   end;
  127.  
  128.   { symmetric difference }
  129.   operator ><(const a,b:TWordSet):TWordSet;
  130.   begin
  131.     b.SymmetricExceptWith(a);
  132.     Result := b;
  133.   end;
  134.  
  135.   operator ><(const a,b:TDWordSet):TDWordSet;
  136.   begin
  137.     b.SymmetricExceptWith(a);
  138.     Result := b;
  139.   end;
  140.  
  141.   operator ><(const a,b:TQWordSet):TQWordSet;
  142.   begin
  143.     b.SymmetricExceptWith(a);
  144.     Result := b;
  145.   end;
  146.  
  147.   { contains }
  148.   operator <=(const a,b:TWordSet):Boolean;
  149.   var
  150.     c:word;
  151.   begin
  152.     Result := true;
  153.     for c in a do
  154.     if not b.contains(c) then
  155.     begin
  156.       Result := False;
  157.       break;
  158.     end;
  159.   end;
  160.  
  161.   operator <=(const a,b:TDWordSet):Boolean;
  162.   var
  163.     c:word;
  164.   begin
  165.     Result := true;
  166.     for c in a do
  167.     if not b.contains(c) then
  168.     begin
  169.       Result := False;
  170.       break;
  171.     end;
  172.   end;
  173.  
  174.   operator <=(const a,b:TQWordSet):Boolean;
  175.   var
  176.     c:word;
  177.   begin
  178.     Result := true;
  179.     for c in a do
  180.     if not b.contains(c) then
  181.     begin
  182.       Result := False;
  183.       break;
  184.     end;
  185.   end;
  186.  
  187.   { in }
  188.   operator in (const a:word;const b:TWordset):Boolean;
  189.   begin
  190.     Result := b.Contains(a);
  191.   end;  
  192.  
  193.   operator in (const a:dword;const b:TDWordset):Boolean;
  194.   begin
  195.     Result := b.Contains(a);
  196.   end;
  197.  
  198.   operator in (const a:qword;const b:TQWordset):Boolean;
  199.   begin
  200.     Result := b.Contains(a);
  201.   end;
  202.  
  203.   { include }
  204.   procedure include(const a:TWordSet;const b:Word);
  205.   begin
  206.     a.Add(b);
  207.   end;
  208.  
  209.   procedure include(const a:TDWordSet;const b:DWord);
  210.   begin
  211.     a.Add(b);
  212.   end;
  213.  
  214.   procedure include(const a:TQWordSet;const b:QWord);
  215.   begin
  216.     a.Add(b);
  217.   end;
  218.  
  219.   { exclude }
  220.   procedure exclude(const a:TWordSet;const b:Word);
  221.   begin
  222.     a.Remove(b);
  223.   end;
  224.  
  225.   procedure exclude(const a:TDWordSet;const b:DWord);
  226.   begin
  227.     a.Remove(b);
  228.   end;
  229.  
  230.   procedure exclude(const a:TQWordSet;const b:QWord);
  231.   begin
  232.     a.Remove(b);
  233.   end;
  234.  
  235. end.
Title: Re: Large or huge sets
Post by: marcov on September 10, 2019, 11:05:51 am
The problem is that useset is the same as for TBits.

The problem with the set 256 limit is that you have a enum (as in, with identifier names) that suddenly grows beyond 256, and you have to redo your program.  Specially when the enum set tests are used in business code that hurts.

So try if your solution also works for a large enum.

And a demo to test (how would code look?) would be nice. E.g. will my IN operator tests remain the same?
Title: Re: Large or huge sets
Post by: Ñuño_Martínez on September 10, 2019, 11:09:43 am
Not sure but I think that some operators don't work as expected.  I mean, operator + shouldn't be like this?
Code: Pascal  [Select][+][-]
  1.  
  2. OPERATOR + (CONST a, b:TWordset): TWordSet;
  3. BEGIN
  4.   RESULT := TWordSet.Create;
  5.   RESULT.Copy (b);
  6.   RESULT.UnionWith (a)
  7. END;
  8.  

Note: Never used generics.collections and I didn't look for information about it, so my code would be so wrong... :-[

Also: I'm not a big fan of operators overloading using classes for obvious reasons (i.e: I expect that the result of a + b is a new object, not to modify one of the operands).
Title: Re: Large or huge sets
Post by: Thaddy on September 10, 2019, 11:14:08 am
So try if your solution also works for a large enum.
That works.  Becase it avoids the size of enums.  work in progress.
Title: Re: Large or huge sets
Post by: Thaddy on September 10, 2019, 11:18:30 am
Not sure but I think that some operators don't work as expected.  I mean, operator + shouldn't be like this?
Also: I'm not a big fan of operators overloading using classes for obvious reasons (i.e: I expect that the result of a + b is a new object, not to modify one of the operands).
You would be amazed. This code is not fastest, but satisfies most tests.
You are wrong about the new object: that would cause leaks, and I tested against leaks.

Anyway, it is rough and probably needs refinement.

Thanks for the response, both.
Title: Re: Large or huge sets
Post by: Kays on September 10, 2019, 12:06:08 pm
Large or huge sets are often requested. […]
Meh, your code doesn’t support set of real. :P
Title: Re: Large or huge sets
Post by: Thaddy on September 10, 2019, 12:20:14 pm
Large or huge sets are often requested. […]
Meh, your code doesn’t support set of real. :P
No, because that is not mathematically a viable option for real sets.
The TSortedHashset supports that to some extend...But not like real sets, like in a Pascal set. My code does.
You need to have a certain amount of bit patterns, just like normal sets.
(I know it requires a small, just a small, bit of computer science...)
Furthermore, I never pretend to have infinite scale, just larger scale if you run out of 256....If you do not understand that plz refrain from taking part of the discussion,
I just got two very informed answers that really help.
Title: Re: Large or huge sets
Post by: 440bx on September 10, 2019, 02:50:24 pm
Large or huge sets are often requested. […]
Meh, your code doesn’t support set of real. :P
I presume that comment was tongue in cheek as only countable sets can be represented digitally.  The set of reals is not countable.

Title: Re: Large or huge sets
Post by: jamie on September 10, 2019, 04:01:17 pm
There is one thing I can say about @Thaddy, good of bad, he knows how to write bloat!
 ;)
Title: Re: Large or huge sets
Post by: marcov on September 10, 2019, 04:09:39 pm
Oops. I only read quickly initially, and it seems not to be a value type, meaning you must change business code (and streaming!). Not really an option for me. I wonder if changing the class to a record<>,  and then hacking till it works might do it. However the problem is dimensioning the static data field to the size of the enum.

Hmm. maybe abusing an ansistring/dynarray. Automated but many aspects like streaming and " IN " operator cost magnitude, remains the same
Title: Re: Large or huge sets
Post by: Thaddy on September 10, 2019, 04:31:28 pm
There is one thing I can say about @Thaddy, good of bad, he knows how to write bloat!
 ;)
Do it better. You can't. In 10 minutes. Clock is ticking....
( I am  one of the few that actually produce working code all the time..with compilable code....)
Title: Re: Large or huge sets
Post by: howardpc on September 10, 2019, 06:28:30 pm
Thanks, Thaddy for sharing useful functionality.
My preference for "contains" (rather than via the slightly cryptic operator <=) is for a named function.

I think it also warrants a count function, which is what I miss most in the basic Pascal set implementation.

I would implement these as follows:
Code: Pascal  [Select][+][-]
  1.   function SetAContainsSetB(const a, b: TWordSet): Boolean;
  2.   var
  3.     c: Word;
  4.   begin
  5.     for c in a do
  6.       if not b.Contains(c) then
  7.         Exit(False);
  8.     Result := True;
  9.   end;
  10.  
  11.   function GetCount(const aSet: TWordSet): SizeInt;
  12.   begin
  13.     Exit(aSet.Count);
  14.   end;

And corresponding  code for DWord and QWord if you need such enormous data structures.
If you do need such things, you are probably better off with a database anyway. But all things have their niche uses and appeal.
Title: Re: Large or huge sets
Post by: Thaddy on September 10, 2019, 07:12:37 pm
The slightly cryptic <= is a part of long standing Pascal set syntax, Howard  ;D ....
But I will try to improve.... (I know I could do it with bitmasks, but that is not the point here)
Title: Re: Large or huge sets
Post by: howardpc on September 10, 2019, 07:34:38 pm
Well I am aware of that syntax. I was merely expressing my preference for a more verbose alternative.
To those of a mathematical bent <= is no doubt transparent and self-explanatory when used as a set operator.
Lesser mortals like myself prefer wordy self-declaring function names, a luxury which is also Pascalish.
FPC provides also for those who prefer more C-like syntax, so we can have the best of both worlds.
Title: Re: Large or huge sets
Post by: Kays on September 10, 2019, 08:47:34 pm
[…] Meh, your code doesn’t support set of real. :P
No, because that is not mathematically a viable option for real sets. […]
[…] I presume that comment was tongue in cheek as only countable sets can be represented digitally.  The set of reals is not countable.
Yes, it was tongue in cheek. Sorry, if that didn’t get through with the smiley. Of course I know there’s no bijective mapping ℝ → ℕ, so there’s no way to store 2 in a discrete manner, and bla, bla, bla. (Obviously I have *only* good memories about the math lectures. ;))
Title: Re: Large or huge sets
Post by: PascalDragon on September 11, 2019, 09:41:36 am
Large or huge sets are often requested. Just today I needed one. Wrote it in ten minutes, but maybe useful?
If the critics are not too harsh, I will add it to to the wiki.
Note it can be written *way* more efficient.
Small remark: due to the use of global operators they can't be used inside generics (at least as of now) while normal sets have no problem with that.
Title: Re: Large or huge sets
Post by: Thaddy on September 11, 2019, 09:50:31 am
Large or huge sets are often requested. Just today I needed one. Wrote it in ten minutes, but maybe useful?
If the critics are not too harsh, I will add it to to the wiki.
Note it can be written *way* more efficient.
Small remark: due to the use of global operators they can't be used inside generics (at least as of now) while normal sets have no problem with that.
I know. It is not perfect in any way, but it works.... :-X and the code is reasonably clean and not bloat as was suggested.
I was able to use this in re-examining my translation of the Delphi Gold parser system.
Title: Re: Large or huge sets
Post by: avk on September 13, 2019, 08:48:31 pm
@Thaddy, but why exactly TSortedHashSet?
Title: Re: Large or huge sets
Post by: Thaddy on September 13, 2019, 09:35:35 pm
Because it has a distinctive "set" of advantages  :D
It is reasonably fast, is sorted (essential) and does not accept duplicates. It behaves like normal, basic, Pascal sets. (But I wrote it is in no way optimal, it is also not bloat as suggested - that one is fired if he was working for me)

The approach was to have large sets with as few lines of code possible and it should match normal set behavior. Job done. And really in 10 minutes. I like simple code for complex problems....
Title: Re: Large or huge sets
Post by: Mogens Lundholm on April 18, 2020, 10:38:26 am
Large or huge sets are often requested. Just today I needed one. Wrote it in ten minutes, but maybe useful?

Get this message:
unithugeset.pas(23,3) Fatal: Cannot find generics.collections used by UnitHugeSet of the Project Inspector.
Title: Re: Large or huge sets
Post by: PascalDragon on April 18, 2020, 10:55:22 am
As mentioned in the other thread:

You either need to use FPC 3.2 or newer as Generics.Collections ships with that by default or if you want to use 3.0.4 you can download or clone this (https://github.com/maciej-izak/generics.collections) repo of the original author (hnb on this forum).
Title: Re: Large or huge sets
Post by: Mogens Lundholm on April 19, 2020, 08:42:21 am

Large or huge sets:
unit largesets;

PascalDragon wrote:
"Best to report this in the other thread, so that Thaddy knows that he might
want to fix this."

I am testing generics.collections for an object for sets

Test program with two sets, s1=[10,11], s2=[20,1000020]. The code snip writes s1, s2 and s1+s2 two times and
the expected result second time is of cause the same result as first time - but is not.
Code: Pascal  [Select][+][-]
  1. // Set 1 = [10,11], Set 2 = [20,1000020],
  2.   write('Set 1:   '); writeset(s1);
  3.   write('Set 2:   '); writeset(s2);
  4.   write('Set 1+2: '); writeset(s1+s2);
  5.  
  6.   write('Set 1:   '); writeset(s1);
  7.   write('Set 2:   '); writeset(s2);
  8.   write('Set 1+2: '); writeset(s1+s2);        
  9.  

The result output is:
Code: Pascal  [Select][+][-]
  1. Set 1:   [10,11]
  2. Set 2:   [20,1000020]
  3. Set 1+2: [10,11,20,1000020]
  4. Set 1:   [10,11]
  5. Set 2:   [10,11,20,1000020]
  6. Set 1+2: [10,11,20,1000020]
  7.  

The problem is that "operator+" overwrites the s2-variable.
 
All my efforts seem to end with the problem of the assignment operator.

E.g. operator:=(s: TNormalSet): TVarSet;

But what was needed was:

operator:=(var r: TVarSet; s: TVarSet);

So that we had the address that should be assigned to. Then
we could decide about allocation and deallocation.

Also an "operator.." - iteration and operator[] (specifying set or list) would be nice. Also "+=", "*=" etc.



Title: Re: Large or huge sets
Post by: Thaddy on April 19, 2020, 09:08:53 am
The bug seems not in my code but in the underlying generics.collections.
I will contact Maciej (a.k.a. hnb) if he can confirm this. He wrote that code.
Maciej, if you read this can you please test?

But I will do some extra tests myself. (I have a test suite for this code, but it is a bit of a mess)
Please note that I actually used this code in my gold parser translation and never ran into problems (yet)
Title: Re: Large or huge sets
Post by: PascalDragon on April 19, 2020, 12:03:20 pm
The bug seems not in my code but in the underlying generics.collections.
I will contact Maciej (a.k.a. hnb) if he can confirm this. He wrote that code.
Maciej, if you read this can you please test?

Did you even look at your code?

Code: Pascal  [Select][+][-]
  1.   operator + (const a,b:TWordset):TWordSet;
  2.   begin
  3.     b.UnionWith(a);
  4.     Result := b;
  5.   end;

You are modifying b. And TSortedHashSet<> is a class, so of course that modifies also the passed in instance.
Title: Re: Large or huge sets
Post by: Thaddy on April 19, 2020, 12:05:09 pm
Aha. tnx Sven. Will fix. Strange that - for my use - this did not show up, though.
Is this correct?
Code: Pascal  [Select][+][-]
  1.   { union }
  2.   operator + (const a,b:TWordset):TWordSet;
  3.   begin  
  4.     Result := b;
  5.     Result.UnionWith(a);
  6.   end;
 
Title: Re: Large or huge sets
Post by: Thaddy on April 26, 2020, 11:12:46 am
Aha. tnx Sven. Will fix. Strange that - for my use - this did not show up, though.
Is this correct?
Code: Pascal  [Select][+][-]
  1.   { union }
  2.   operator + (const a,b:TWordset):TWordSet;
  3.   begin  
  4.     Result := b;
  5.     Result.UnionWith(a);
  6.   end;


If it is, its fixed for all occurrences and I can add a new version.
Title: Re: Large or huge sets
Post by: PascalDragon on April 26, 2020, 12:11:14 pm
First of, sorry that I didn't answer. For some reason I had not seen that you had replied. %)

Second: Thaddy, I thought you know how classes work? Class instance variables are pointers to class instances. Simply assigning the pointer to another class instance variable will not change anything, you're operating on the same instance. You need to completely clone the set.

Here is an example that fails:

Code: Pascal  [Select][+][-]
  1. program tsets;
  2.  
  3. uses
  4.   largesets;
  5.  
  6. var
  7.   w1, w2, w3: TWordSet;
  8. begin
  9.   w1 := TWordSet.Create;
  10.   w2 := TWordSet.Create;
  11.   w1.Add($8000);
  12.   w2.Add($0004);
  13.  
  14.   Writeln(w1.Count, ' ', w2.Count);
  15.  
  16.   w3 := w1 + w2;
  17.  
  18.   Writeln(w1.Count, ' ', w2.Count);
  19.  
  20.   if w1.Count <> 1 then
  21.     Writeln('w1 was modified!');
  22.   if w2.Count <> 1 then
  23.     Writeln('w2 was modified!');
  24.   if w3.Count <> 2 then
  25.     Writeln('w3 has wrong amount of elements!');
  26. end.
Title: Re: Large or huge sets
Post by: Thaddy on April 26, 2020, 12:24:38 pm
Clear.
Title: Re: Large or huge sets
Post by: marcov on May 02, 2020, 01:17:52 pm
I tried to make a generic value type set, but it doesn't work.


Code: Pascal  [Select][+][-]
  1. program bigvalueset;
  2. // test to make value type sets.
  3.  
  4. {$define useFPCsyntax}                     // to test in objfpc mode in case there are differences, and because we invoke ord() on enums.
  5. {define testoperatoroverloading}          // try operator overloading
  6.  
  7. {$ifdef useFPCsyntax}
  8. {$Mode objfpc}
  9. {$else}
  10. {$Mode delphi}
  11. {$endif}
  12. {$modeswitch advancedrecords}
  13. type  
  14.     {$ifdef useFPCsyntax}generic {$endif}
  15.      TBigValueSet<T> =  record
  16.                            Type
  17.                             TMySet =  {$ifdef useFPCsyntax}specialize {$endif} TBigValueSet<T>;
  18.                            var
  19.                            data : array[0.. ord(high(T)) div 32] of cardinal;
  20.  
  21.                            procedure xinclude (element:T); inline;
  22.                            procedure xexclude (element:T); inline;
  23.                            function test(element:T) : boolean; inline;
  24.                            {$ifdef testoperatoroverloading}
  25.                            class operator in (A: T; const B: TMySet): boolean;  
  26.                            {$endif}
  27.                         end;
  28.  
  29. Type
  30.     TDWordSet = set of 0..31;
  31.     pdwordset = ^TDwordSet;
  32.  
  33.  
  34.  
  35. {$ifdef testoperatoroverloading}
  36. class operator TBigValueSet<T>.in (A: T; const B: TMySet): boolean;                        
  37. begin
  38. end;
  39. {$endif}
  40.  
  41. procedure TBigValueSet{$ifndef useFPCsyntax} <T>{$endif}.xinclude(element:T);
  42. begin
  43.   system.include (pdwordset(data[ord(element) div 32])^,cardinal(ord(element) and 31));
  44. end;
  45.  
  46. procedure TBigValueSet{$ifndef useFPCsyntax}<T>{$endif}.xexclude (element:T);
  47. begin
  48.  system.exclude (pdwordset(data[ord(element) div 32])^,cardinal(ord(element) and 31));
  49. end;
  50.  
  51. function TBigValueSet{$ifndef useFPCsyntax}<T>{$endif}.test (element:T):boolean;
  52. begin
  53.   result:=cardinal(ord(element) and 31) in pdwordset(data[ord(element)^ div 32])^;
  54. end;
  55.  
  56. begin
  57. end.
  58.  
Title: Re: Large or huge sets
Post by: avk on May 02, 2020, 06:23:04 pm
Something like that?
Code: Pascal  [Select][+][-]
  1. program test_bigset;
  2. {$mode objfpc}{$modeswitch advancedrecords}
  3. type
  4.   generic TBigValueSet<T> = record
  5.   private
  6.   const
  7.     LOWER   = Low(T);
  8.     UPPER   = High(T) - LOWER;
  9.     SET_LEN = (Upper shr 5 + Ord(Upper and 31 <> 0)) + Ord(UPPER = 0);
  10.   type
  11.     TDWordBits = 0..31;
  12.     TDWordSet = set of TDWordBits;
  13.     PDWordSet = ^TDWordSet;
  14.     TSet = array[0..Pred(SET_LEN)] of DWord;
  15.   var
  16.     FSet: TSet;
  17.     class operator Initialize(var s: TBigValueSet);
  18.   public
  19.     procedure Include(aValue: T);
  20.     procedure Exclude(aValue: T);
  21.     class operator +(constref L, R: TBigValueSet): TBigValueSet;
  22.     class operator -(constref L, R: TBigValueSet): TBigValueSet;
  23.     class operator *(constref L, R: TBigValueSet): TBigValueSet;
  24.     class operator ><(constref L, R: TBigValueSet): TBigValueSet;
  25.     class operator =(constref L, R: TBigValueSet): Boolean;
  26.     class operator <=(constref L, R: TBigValueSet): Boolean;
  27.     class operator in (aValue: T; const aSet: TBigValueSet): Boolean;
  28.   end;
  29.  
  30. class operator TBigValueSet.Initialize(var s: TBigValueSet);
  31. begin
  32.   s.FSet := Default(TSet);
  33. end;
  34.  
  35. procedure TBigValueSet.Include(aValue: T);
  36. begin
  37.   System.Include(PDWordSet(@FSet[(Integer(aValue) - LOWER) shr 5])^, (Integer(aValue) - LOWER) and 31);
  38. end;
  39.  
  40. procedure TBigValueSet.Exclude(aValue: T);
  41. begin
  42.   System.Exclude(PDWordSet(@FSet[(Integer(aValue) - LOWER) shr 5])^, (Integer(aValue) - LOWER) and 31);
  43. end;
  44.  
  45. class operator TBigValueSet.+(constref L, R: TBigValueSet): TBigValueSet;
  46. var
  47.   I: Integer;
  48. begin
  49.   for I := 0 to Pred(SET_LEN) do
  50.     Result.FSet[I] := L.FSet[I] or R.FSet[I];
  51. end;
  52.  
  53. class operator TBigValueSet.-(constref L, R: TBigValueSet): TBigValueSet;
  54. var
  55.   I: Integer;
  56. begin
  57.   for I := 0 to Pred(SET_LEN) do
  58.     Result.FSet[I] := L.FSet[I] and not R.FSet[I];
  59. end;
  60.  
  61. class operator TBigValueSet.*(constref L, R: TBigValueSet): TBigValueSet;
  62. var
  63.   I: Integer;
  64. begin
  65.   for I := 0 to Pred(SET_LEN) do
  66.     Result.FSet[I] := L.FSet[I] and R.FSet[I];
  67. end;
  68.  
  69. class operator TBigValueSet.><(constref L, R: TBigValueSet): TBigValueSet;
  70. var
  71.   I: Integer;
  72. begin
  73.   for I := 0 to Pred(SET_LEN) do
  74.     Result.FSet[I] := L.FSet[I] xor R.FSet[I];
  75. end;
  76.  
  77. class operator TBigValueSet.=(constref L, R: TBigValueSet): Boolean; inline;
  78. var
  79.   I: Integer;
  80. begin
  81.   for I := 0 to Pred(SET_LEN) do
  82.     if L.FSet[I] <> R.FSet[I] then
  83.       exit(False);
  84.   Result := True;
  85. end;
  86.  
  87. class operator TBigValueSet.<=(constref L, R: TBigValueSet): Boolean; inline;
  88. var
  89.   I: Integer;
  90. begin
  91.   for I := 0 to Pred(SET_LEN) do
  92.     if R.FSet[I] <> L.FSet[I] or R.FSet[I] then
  93.       exit(False);
  94.   Result := True;
  95. end;
  96.  
  97. class operator TBigValueSet.in (aValue: T; const aSet: TBigValueSet): Boolean;
  98. begin
  99.   Result := TDWordBits((Integer(aValue) - LOWER) and 31) in PDWordSet(@aSet.FSet[(Integer(aValue) - LOWER) shr 5])^;
  100. end;
  101.  
  102. type
  103.   TMyRange = -1022..1023;
  104. var
  105.   s, s2: specialize TBigValueSet<TMyRange>;
  106. begin
  107.   WriteLn('SizeOf(s) = ', SizeOf(s));
  108.   s.Include(-5);
  109.   WriteLn('-5 in s = ', -5 in s);
  110.   s.Include(1022);
  111.   WriteLn('1022 in s = ', 1022 in s);
  112.   s2.Include(-15);
  113.   s2.Include(-900);
  114.   s2 := s2 + s;
  115.   WriteLn('-5 in s2 = ', -5 in s2);
  116.   WriteLn('-15 in s2 = ', -15 in s2);
  117.   WriteLn('-900 in s2 = ', -900 in s2);
  118.   WriteLn('1022 in s2 = ', 1022 in s2);
  119.   s2 := s2 - s2;
  120.   WriteLn('-5 in s2 = ', -5 in s2);
  121.   WriteLn('-15 in s2 = ', -15 in s2);
  122.   WriteLn('-900 in s2 = ', -900 in s2);
  123.   WriteLn('1022 in s2 = ', 1022 in s2);
  124. end.
  125.  
Title: Re: Large or huge sets
Post by: marcov on May 02, 2020, 10:37:23 pm
Very nice. So my mistakes are

-  typecasting to integer works, but ord() not.
 - And the class operators need visibility modifiers?
-  management operators for initialization
- using ord in declaration works.

Any other obvious things I missed?
Title: Re: Large or huge sets
Post by: howardpc on May 03, 2020, 11:16:15 am
@avk
I think your implementation of >< requires xor, not and.
Title: Re: Large or huge sets
Post by: avk on May 03, 2020, 11:43:19 am
@howardpc, yes, thank you, it's a typo, I fixed the code.

Very nice. So my mistakes are

-  typecasting to integer works, but ord() not.
 - And the class operators need visibility modifiers?
-  management operators for initialization
- using ord in declaration works.

Any other obvious things I missed?

It's mostly Ord(). The rest is successfully compiled using FPC 3.2, at least this way:
Code: Pascal  [Select][+][-]
  1. program bigvalueset;
  2. // test to make value type sets.
  3.  
  4. {$define useFPCsyntax}                     // to test in objfpc mode in case there are differences, and because we invoke ord() on enums.
  5. {$define testoperatoroverloading}          // try operator overloading
  6.  
  7. {$ifdef useFPCsyntax}
  8. {$Mode objfpc}
  9. {$else}
  10. {$Mode delphi}
  11. {$endif}
  12. {$modeswitch advancedrecords}
  13. type
  14.     {$ifdef useFPCsyntax}generic {$endif}
  15.      TBigValueSet<T> =  record
  16.                            Type
  17.                             TMySet =  {$ifdef useFPCsyntax}specialize {$endif} TBigValueSet<T>;
  18.                            var
  19.                            data : array[0.. ord(high(T)) div 32] of cardinal;
  20.  
  21.                            procedure xinclude (element:T); inline;
  22.                            procedure xexclude (element:T); inline;
  23.                            function test(element:T) : boolean; inline;
  24.                            {$ifdef testoperatoroverloading}
  25.                            class operator in (A: T; const B: TMySet): boolean;
  26.                            {$endif}
  27.                         end;
  28.  
  29. Type
  30.     TDWordSet = set of 0..31;
  31.     pdwordset = ^TDwordSet;
  32.  
  33.  
  34.  
  35. {$ifdef testoperatoroverloading}
  36. class operator TBigValueSet{$ifndef useFPCsyntax} <T>{$endif}.in (A: T; const B: TMySet): boolean;
  37. begin
  38.   Result := B.test(A);
  39. end;
  40. {$endif}
  41.  
  42. procedure TBigValueSet{$ifndef useFPCsyntax} <T>{$endif}.xinclude(element:T);
  43. begin
  44.   system.include (pdwordset(@data[Integer(element) div 32])^,cardinal(Integer(element) and 31));
  45. end;
  46.  
  47. procedure TBigValueSet{$ifndef useFPCsyntax}<T>{$endif}.xexclude (element:T);
  48. begin
  49.  system.exclude (pdwordset(@data[Integer(element) div 32])^,cardinal(Integer(element) and 31));
  50. end;
  51.  
  52. function TBigValueSet{$ifndef useFPCsyntax}<T>{$endif}.test (element:T):boolean;
  53. begin
  54.   result:=cardinal(Integer(element) and 31) in pdwordset(@data[Integer(element) div 32])^;
  55. end;
  56.  
  57. begin
  58. end.  
  59.  

As for Ord(), it looks like a compiler bug, but I don't have full confidence.
Title: Re: Large or huge sets
Post by: marcov on May 03, 2020, 04:26:16 pm
As for Ord(), it looks like a compiler bug, but I don't have full confidence.

It might be that every built-in has to be explicitly fixed for such usage.
Title: Re: Large or huge sets
Post by: PascalDragon on May 03, 2020, 05:09:24 pm
As for Ord(), it looks like a compiler bug, but I don't have full confidence.

It might be that every built-in has to be explicitly fixed for such usage.

Correct. I have done that in revision 45232 now.
Title: Re: Large or huge sets
Post by: Mogens Lundholm on May 04, 2020, 09:49:09 am
Large or huge sets are often requested.

Waiting for the final solution, I made a TBigSet with 1024 elements. Made even a little test program. A few lines from the test program:
Code: Pascal  [Select][+][-]
  1. s1:=[1,3,5,7,9];
  2. s2:=[1,4,5,7,9,11];
  3.  
  4.   s3:=s1><s2;
  5.  
  6.   s:=BigSetToStr(s3);
  7.   if s<>'[3,4,11]' then
  8.     begin
  9.     writeln('Error test 3:',s,'- Should be [3,4,11]');
  10.     readln;
  11.     end;              
  12.  

The most strange thing: TBigset runs much faster than the built-in 256-set in a performance test (union of two sets 10000000 times) Can this be true?

Title: Re: Large or huge sets
Post by: strmckr on September 07, 2022, 10:24:55 am
Sorry for the necro post but there really isn't much discussion on large sets one of my projects needs to be able to reach a range of 1 -> 46,666 sets. 

function Equals(constref ALeft, ARight: T): Boolean;

i believe this function is missing coding for the hashtable variation Thaddy has posted
  operator =  and <>

both cannot be overloaded directly producing errors sitting the above as inherently defined yet its missing the ability to produce results

a work around was to build a function  that did >< then checked for values   to replicate the comparison function of  =, <>

when testing my code below for with identical sets it yields no results same with
  (w2 = w1 )  or (w2 <> w1)   both compile but have no result.

the version below seems to fix the problem posted by PascalDragon
 that
   W3: = w1 + w2   would modify w2  every time its called.
         {fixed by cloning the first value then merging with the new}

same problem seem to happen with ><,+,- operators. {at least on testing} similar fix applied..   

I'm a hobbyist: if this code is "bloated"  point out how to make it better 
   not bad for a 10 min fix :P
 
Code: Pascal  [Select][+][-]
  1.  {$mode objfpc}{$inline on}
  2.  
  3.     { A simple way to implement large or huge sets.
  4.      (c) 2019 Thaddy de Koning. No license and not
  5.      re-licensable: free for all to use.
  6.      Copyright holds:
  7.      You can not claim license nor copyrigths
  8.          }
  9.          {* added by strmck 2022}
  10.     unit largesets;
  11.     { Operator      Action
  12.       ---------------------------------------------
  13.       +             Union
  14.       -             Difference
  15.       *             Intersection
  16.       ><        Symmetric difference
  17.       <=        Contains
  18.           >=        Left hand side set is a superset of the one on the right *
  19.        =             equality:  use function  equality( which does (><) and evaultes if its empty)*
  20.        <>        inequality:  use function inequality( which does (><) and evaulates if its not empty)*
  21.       include2   Include an element in the set
  22.       exclude2   Exclude an element from the set
  23.       in         Check if an single element is in a set
  24.    
  25.    notes: Twordset can be modifed for Tdwordset/Tqwordset
  26.    include & exclude renamed to allow for inherinted function include/exclude to function normally
  27.    }
  28.     interface
  29.     uses
  30.       generics.collections;
  31.      
  32.     type
  33.       TWordSet  = specialize TSortedHashSet<word >;
  34.            
  35.       { union }
  36.       operator + (const a,b:TWordset):TWordSet;  
  37.      
  38.       { difference }
  39.       operator - (const a,b:Twordset ):TWordSet;  
  40.      
  41.       { intersection }
  42.       operator * (const a,b:TwordSet ):TWordSet;  
  43.      
  44.       { symmetric difference }
  45.       operator >< (const a,b:TWordSet ):TWordSet;
  46.    
  47.       { contains }
  48.       operator <= (const a,b:TWordSet ):Boolean;
  49.  
  50.         { Left hand side set is a superset of the one on the right }
  51.       operator >= (const a,b:TWordSet ):Boolean;  
  52.                  
  53.       { in }
  54.       operator in (const a:word; const b:TWordset ):Boolean;  
  55.      
  56.       { include }
  57.       procedure include2(const a:TWordSet; const b:Word);  
  58.      
  59.       { exclude }
  60.       procedure exclude2(const a:TWordSet;const  b:Word);    
  61.      
  62.          function Equality(const A,B:TWordSet):Boolean;
  63.          function inEquality(const A,B:TWordSet):Boolean;
  64.          
  65.     implementation
  66.  Var
  67.   D: TwordSet;
  68.  
  69.       { union }
  70.       operator + (const a,b:Twordset):TWordSet;
  71.       begin
  72.           d.Free;
  73.           D := TWordSet.Create;
  74.             D.unionWith(A);
  75.                 D.unionWith(B);      
  76.         Result := D;           
  77.       end;      
  78.          
  79.       { difference }
  80.       operator -(const a,b:Twordset):TWordSet;
  81.       begin
  82.            d.Free;
  83.             D := TWordSet.Create;
  84.             D.unionWith(A);
  85.                 D.ExceptWith(B);        
  86.         result:=D;
  87.       end;    
  88.          
  89.       { intersection }
  90.       operator *(const a,b:TwordSet):TWordSet;
  91.       begin
  92.           d.Free;
  93.           D := TWordSet.Create;
  94.           D.unionWith(a);
  95.           D.IntersectWith(b);      
  96.         Result := D;
  97.       end;        
  98.      
  99.       { symmetric difference }
  100.       operator ><(const a,b:TWordSet):TWordSet;
  101.       begin
  102.           d.Free;
  103.           D := TWordSet.Create;
  104.           D.unionWith(a);
  105.           D.SymmetricExceptWith(b);      
  106.         Result := D;
  107.       end;        
  108.      
  109.       { contains }
  110.       operator <=(const a,b:TWordSet):Boolean;
  111.       var
  112.         c:word;
  113.       begin
  114.         Result := true;
  115.         for c in a do
  116.         if not b.contains(c) then
  117.         begin
  118.           Result := False;
  119.           break;
  120.         end;
  121.       end;    
  122.          
  123.       { Left hand side set is a superset of the one on the right }
  124.       operator >=(const a,b:TWordSet):Boolean;
  125.       var
  126.         c:word;
  127.       begin
  128.         Result := true;
  129.         for c in b do
  130.         if not a.contains(c) then
  131.         begin
  132.           Result := False;
  133.           break;
  134.         end;
  135.       end;     
  136.  
  137.          
  138.  {equality} { first checks if either set has diffrent values}
  139.  Function Equality(const A, B: TWordSet): Boolean;
  140. var
  141.   c:word;
  142. begin
  143. d.Free;
  144. Result := true;
  145. D := TWordSet.Create;
  146. D.unionWith(a);
  147. D.SymmetricExceptWith(b);              
  148.   for c in D do
  149.      begin  
  150.     result:= False;
  151.       break;   
  152.         end;    
  153. end;
  154.  
  155.  Function inEquality(const A, B: TWordSet): Boolean;
  156. var
  157.   c:word;
  158. begin
  159. d.Free;
  160. Result := false;
  161. D := TWordSet.Create;
  162. D.unionWith(a);
  163. D.SymmetricExceptWith(b);            
  164.   for c in D do
  165.      begin  
  166.     result:= True;
  167.       break;   
  168.         end;    
  169. end;   
  170.        
  171.       { in }
  172.       operator in (const a:word;const b:TWordset):Boolean;
  173.       begin
  174.         Result := b.Contains(a);
  175.       end;
  176.      
  177.       { include }
  178.       procedure include2(const a:TWordSet;const b:Word);
  179.       begin
  180.         a.Add(b);
  181.       end;    
  182.          
  183.       { exclude }
  184.       procedure exclude2(const a:TWordSet;const b:Word);
  185.       begin
  186.         a.Remove(b);
  187.       end;    
  188.      
  189.   {counting function}    
  190. function GetCount(const aSet: TWordSet): SizeInt;
  191.   begin
  192.     Exit(aSet.Count);  
  193.     end;
  194.        
  195. end.

Test program
Code: Pascal  [Select][+][-]
  1.     program tsets;
  2.     // {$include largesets.pas}// attempt to fix sets above 256 size limit.
  3.  
  4.       uses crt,windows,Largesets;
  5.     var
  6.       w1,w2,w3: TWordSet;        
  7.           n:word;
  8.                   ch:char;
  9.     begin
  10.         Clrscr;
  11.  
  12.       gotoxy(2,1);
  13. w1 := TWordSet.Create;
  14. w2 := TWordSet.Create;
  15.  
  16.          for n in [1..2] do
  17.           include2(w1,n);
  18.          for n in [3..5] do
  19.           include2(w2,n);
  20.  
  21. W3:=w1+w2; // equals [1,2,3,4,5]
  22.    write('w3:');
  23.      for n in w3 do write(' ',n);
  24.         {  write(' w1:');   for n in w1 do write(n);
  25.           write(' w2:');   for n in w2 do write(n); }
  26.  
  27. w1.Free;
  28. w2.Free;
  29.  
  30. gotoxy(2,2);
  31. w1 := TWordSet.Create;
  32. w2 := TWordSet.Create;
  33.          for n in [1..3] do
  34.           include2(w1,n);
  35.          for n in [3] do
  36.           include2(w2,n);
  37.  
  38.    W3:=w1-w2;     // equals [1,2]
  39.     write('w3:');
  40.      for n in w3 do write(n);
  41.         {  write(' w1:');   for n in w1 do write(n);
  42.           write(' w2:');   for n in w2 do write(n);}
  43. w1.Free;
  44. w2.Free;
  45.  
  46. gotoxy(2,3);
  47.  
  48. w1 := TWordSet.Create;
  49. w2 := TWordSet.Create;
  50.          for n in [2..5] do
  51.           include2(w1,n);
  52.          for n in [1..3,5..6] do
  53.           include2(w2,n);
  54.  
  55.    W3:=w2-w1;     // equals [1,6]
  56.    write('w3:');
  57.      for n in w3 do write(n);
  58.          { write(' w1:');   for n in w1 do write(n);
  59.           write(' w2:');   for n in w2 do write(n);}
  60.          
  61. w1.Free;
  62. w2.Free;
  63. gotoxy(2,4);
  64. w1 := TWordSet.Create;
  65. w2 := TWordSet.Create;
  66.          for n in [1..3] do
  67.           include2(w1,n);
  68.          for n in [3,4,6] do
  69.           include2(w2,n);
  70.  
  71.    W3:=w1*w2; // equals [3]
  72.     write('w3:');
  73.      for n in w3 do write(n);
  74.          { write(' w1:');   for n in w1 do write(n);
  75.           write(' w2:');   for n in w2 do write(n);}
  76.  
  77. gotoxy(2,5);
  78. w1.Free;
  79. w2.Free;
  80. w1 := TWordSet.Create;
  81. w2 := TWordSet.Create;
  82.          for n in [1..3] do
  83.           include2(w1,n);
  84.          for n in [3,4,6] do
  85.           include2(w2,n);
  86.  
  87.    W3:=w1 >< w2; // equals [1,2,4,6]
  88.    write('w3:');
  89.      for n in w3 do write(n);
  90.          { write(' w1:');   for n in w1 do write(n);
  91.           write(' w2:');   for n in w2 do write(n);}
  92.  
  93.  gotoxy(2,6);
  94.  w1.Free;
  95.  w2.Free;
  96. w1 := TWordSet.Create;
  97. w2 := TWordSet.Create;
  98.          for n in [1..7] do
  99.           include2(w1,n);
  100.          for n in [1,2] do
  101.           include2(w2,n);
  102.     if (w2<=w1) then write('must work on 1 and 2');
  103.  
  104.  
  105.  gotoxy(2,7);
  106.  w1.Free;
  107.  w2.Free;
  108.   w1 := TWordSet.Create;
  109.   w2 := TWordSet.Create;
  110.          for n in [9] do
  111.           include2(w1,n);
  112.          for n in [8,9] do
  113.           include2(w2,n);
  114.         if (w2>=w1) then write('can rest on 9');
  115.  
  116. gotoxy(2,7);
  117. w1.Free;
  118. w2.Free;
  119.  w1:= TWordSet.Create;
  120.  w2 := TWordSet.Create;
  121.          for n in [1..4] do
  122.           include2(w1,n);
  123.          for n in [1..4] do
  124.           include2(w2,n);
  125.       if Equality(w1,w2) then write(' 1..4 in both sets');
  126.  
  127.  
  128. gotoxy(2,8);
  129. w1.Free;
  130. w2.Free;
  131.  w1:= TWordSet.Create;
  132.  w2 := TWordSet.Create;
  133.          for n in [1..3] do
  134.           include2(w1,n);
  135.          for n in [1..4] do
  136.           include2(w2,n);
  137.       if inEquality(w1,w2) then write(' 4 not in both sets');
  138.  
  139.          writeln(' press esc to exit');
  140.          ch:=readkey;
  141.         if (ch=#27) then exit;
  142.  
  143.     end.


Title: Re: Large or huge sets
Post by: jamie on September 07, 2022, 06:44:14 pm
Did you do a leakage test on that code?

I see many Creates with no free's and some maybe not needed.

Many that Class is just what it is, all CLASS>
Title: Re: Large or huge sets
Post by: strmckr on September 08, 2022, 08:42:27 am
updated: 
   less memory tied up in newer code.

i will note that freeing D at the end of any of the operator function has a nasty effect of pointing nothing.
  so it cannot be freed until the next call is made.

Title: Re: Large or huge sets
Post by: Arioch on September 12, 2022, 06:12:52 pm
I would think that doing all those operators on class is futile endevour, there would be really lots of memory micro-management.

Would i need it - i'd perhaps just stick with TBits - https://www.freepascal.org/docs-html/rtl/classes/tbits.html
Yes, it would need extension with LessOrEqual AKA Subset comparisons.

But more verbose code would not feel that bad to me.

If you, however, want to do expressions, then you IMHO better stick with advanced records instead.

Some problem is that only recent Delphi versions (10.4+) added true constructors and destructors to the records - https://docwiki.embarcadero.com/RADStudio/Sydney/en/Custom_Managed_Records
And FPC did not yet - https://www.freepascal.org/docs-html/ref/refse63.html

So, unless FPC can do operators over interfaces, not classes, i think the only reliable way of coding would be

1. Making interface-based wrapper over storage class, be it TBits, Delphi 2 old TBitSet ot FPC's TSortedHashlist. For the sake of ARC compiler magic - it needs to get converted to interfaces.

2. Making advanced record on top of that interface, like that

Code: Pascal  [Select][+][-]
  1.  type
  2.       TCustomWordSet  = specialize TSortedHashSet<word >;
  3.       iWordSet = interface .... end; // repeating all the needed functions of TWordSet;  
  4.       TWordSet  = class (TCustomWordSet, iWordSet) end;  
  5.  
  6. // in Delphi this would require TWordSet implement three basis methods of IUnknown. In FPC i heard IUnknown is optional not mandatory.
  7. // anyway, ARC mechanic, if not given by FPC for granted, would need to be implemented
  8.            
  9.      RWordSet = record
  10.         private
  11.            DataStorage: iWordSet;
  12.            function GetDataStorage: iWordSet; inline;
  13.            ....
  14.         public
  15.            property Bits: iWordSet read GetDataStorage;
  16.            property Bit[const index: integer]: boolean read GetBit write SetBit; default;
  17.        
  18.            operator + (const a,b:RWordset):RWordSet;  
  19.            ....
  20.      end;
  21.  
  22. function RWordSet.GetDataStorage: iWordSet;
  23. begin
  24.    if nil = DataStorage then
  25.       DataStorage := TWordSet.Create;
  26.   Result := DataStorage;
  27. end;
  28.  
  29. operator RWordSet.+(const a,b:RWordset):RWordSet;  
  30. begin
  31.     Result.Bits.UnionWith(a);
  32.     Result.Bits.UnionWith(b);
  33. end;
  34.  

But i expect this to be rather slow unless FPC would implement "compound assignment" like C's +=, /= and other.
In other terms, binary commands rather than ternary.

some hypothetical code
Code: Pascal  [Select][+][-]
  1.  setA := setA + setB;

would then posibly get optimized to a hypothetical

Code: Pascal  [Select][+][-]
  1. operator RWordSet.:+(const b:RWordset):RWordSet;
  2. begin
  3.    Resut := Self;
  4.    Self.Bits.UnionWith(b.Bits);
  5. end;
  6.  

or another hypothetical operator
Code: Pascal  [Select][+][-]
  1. operator RWordSet.AddAndDestroy(const b:RWordset):RWordSet;
  2. begin
  3.    if (b.DataStorage = nil) and (Self.DataStorage = nil) then exit;
  4.  
  5.    Resut.DataStorage := Self.DataStorage;
  6.    Self.DataStorage := nil;
  7.  
  8.    if b.DataStorage <> nil then
  9.       Result.Bits.UnionWith(b.DataStorage);
  10. end;
  11.  


But i would not hold my breath for FPC to ether have such complexity.
Title: Re: Large or huge sets
Post by: PascalDragon on September 13, 2022, 09:22:59 am
Some problem is that only recent Delphi versions (10.4+) added true constructors and destructors to the records - https://docwiki.embarcadero.com/RADStudio/Sydney/en/Custom_Managed_Records
And FPC did not yet - https://www.freepascal.org/docs-html/ref/refse63.html

FPC supports management operators (https://wiki.freepascal.org/management_operators) since 3.2.0. We just added them before Delphi did, thus they are not compatible in the way they are declared.
Title: Re: Large or huge sets
Post by: Arioch on September 13, 2022, 09:31:08 pm
Then it should be made part of documentation. Curently i did not find it in online docs.

If they work then interface-based work-aronund is not requied, of course.

But then, can FPC have operators on interface types?

Delphi actually did a bad job there. The class operators were probably borrowed for C# with its GC objects. That should had been translated to interfaces, not classes in Object Pascal.
Same goes with TEncoding - they apy belong to intefaces, not classes.
I wish FPC could fix Delphi mistakes :-)


---------

Frankly, online docs on operators is truly patchy...
I tried to find management there, but failed.

The table of operators does not link to specific declarations and descriptions.
The chapter with descriptions doe not have table of "all existing operators"...

What is "><" ? It is "symmetric difference".
Oookay.... what does it mean? Well, i can try to guess, but i want to read in authorized docs, if i guessed right or wrong!
Also, how should i then use such an operator from the app code? Crickets.

Inc operator - how is it different from Inc procedure? both mentioned, differene not spelled out. It was sounding like explicitteasing, actually.

Enumeration operator... Can i have > 1 enumerators, for different data types in for-in loops? The type parameter suggests so, but it was not spelled out and no examples given.

enumerating mulkti-dimansinal array - the end elementtype can be enumerated, de facto flattening the array. Great feature! But would i wont only enumerae 1st dimension -  can i? or not? Crickets...
Title: Re: Large or huge sets
Post by: PascalDragon on September 14, 2022, 09:28:19 am
Then it should be made part of documentation. Curently i did not find it in online docs.

No one found the time to document them. You may want to report a bug to get them documented.

But then, can FPC have operators on interface types?

You can have global operators that operate on interface types just like you can for class types. However they won't be picked up for specializations.

Frankly, online docs on operators is truly patchy...
I tried to find management there, but failed.

The table of operators does not link to specific declarations and descriptions.
The chapter with descriptions doe not have table of "all existing operators"...

What is "><" ? It is "symmetric difference".
Oookay.... what does it mean? Well, i can try to guess, but i want to read in authorized docs, if i guessed right or wrong!
Also, how should i then use such an operator from the app code? Crickets.

Inc operator - how is it different from Inc procedure? both mentioned, differene not spelled out. It was sounding like explicitteasing, actually.

Enumeration operator... Can i have > 1 enumerators, for different data types in for-in loops? The type parameter suggests so, but it was not spelled out and no examples given.

enumerating mulkti-dimansinal array - the end elementtype can be enumerated, de facto flattening the array. Great feature! But would i wont only enumerae 1st dimension -  can i? or not? Crickets...

Then file bugs for the problems you found.
Title: Re: Large or huge sets
Post by: BrunoK on September 14, 2022, 10:23:32 am
...
What is "><" ? It is "symmetric difference".
Oookay.... what does it mean? Well, i can try to guess, but i want to read in authorized docs, if i guessed right or wrong!
...
Copy paste Symmetric difference to your browser and presto, you have the reply in ~10 seconds.
Title: Re: Large or huge sets
Post by: Arioch on September 14, 2022, 08:50:02 pm
Copy paste Symmetric difference to your browser and presto, you have the reply in ~10 seconds.

It would be that very guesswork that i said is not enough.

Google does not describe this concept as applied to specific FPC types, does not give authoritative (meaning, FPC would be obliged to support it) FPC code examples.
Title: Re: Large or huge sets
Post by: Arioch on September 14, 2022, 09:01:05 pm
We just added them before Delphi did, thus they are not compatible in the way they are declared.

Same you did with generics, but then in Delphi Mode you added Delphi syntax for them
Title: Re: Large or huge sets
Post by: marcov on September 14, 2022, 09:26:10 pm
Same you did with generics, but then in Delphi Mode you added Delphi syntax for them

(8 years later, so maybe that is not the best example  ;) )
Title: Re: Large or huge sets
Post by: Arioch on September 14, 2022, 10:38:35 pm
okay, have your mega-ticket

https://gitlab.com/freepascal.org/lazarus/lazarus/-/issues/39902
Title: Re: Large or huge sets
Post by: PascalDragon on September 15, 2022, 09:27:16 am
We just added them before Delphi did, thus they are not compatible in the way they are declared.

Same you did with generics, but then in Delphi Mode you added Delphi syntax for them

I'm not saying that we won't add support for Delphi's syntax just why it isn't supported yet.

okay, have your mega-ticket

https://gitlab.com/freepascal.org/lazarus/lazarus/-/issues/39902

Great job... you added a bug report for the FPC documentation to the Lazarus project.  ::)
Title: Re: Large or huge sets
Post by: Arioch on September 15, 2022, 06:59:08 pm
Great job... you added a bug report for the FPC documentation to the Lazarus project.  ::)

Indeed... do not race against clock in dead midnight :-(

But cannot tracker admins move the ticket to another, related tracker, like they can on StackOverflow?  Because i definitely can not, only copy-paste...
Title: Re: Large or huge sets
Post by: avra on September 16, 2022, 10:12:26 am
Copy paste Symmetric difference to your browser and presto, you have the reply in ~10 seconds.

It would be that very guesswork that i said is not enough.

Google does not describe this concept as applied to specific FPC types, does not give authoritative (meaning, FPC would be obliged to support it) FPC code examples.
If you google for "><" "symmetric difference" pascal, then this is the first link you get: https://wiki.freepascal.org/symmetric_difference. And it has FPC code example. The very next link is https://www.freepascal.org/docs-html/ref/refsu49.html.
Title: Re: Large or huge sets
Post by: Thaddy on September 18, 2022, 10:40:47 am
Side note:
It is bloody irritating that google search prefers wiki entries over real documentation. Our wiki is much worse than the real official documentation. Does not matter too much in this case, but it is annoying and may put people on the wrong foot. The wiki contains too much dubious entries.

Side note two: set >< syntax is indeed very old, why should it be confusing on inappropriate? It isn't.
I use sets a lot, the old hand that made that remark obviously does not know how to work with sets except for the bare minimum. Also note - huge - sets are what big data is all about and based on simple mathematical "Set theory"
Title: Re: Large or huge sets
Post by: MarkMLl on September 18, 2022, 01:21:12 pm
Side note:
It is bloody irritating that google search prefers wiki entries over real documentation. Our wiki is much worse than the real official documentation. Does not matter too much in this case, but it is annoying and may put people on the wrong foot. The wiki contains too much dubious entries.

Might help if it were available in PDF form via a standard protocol. It's a long time since I've seen Google indexing something only available via FTP.

I wish there were some way of depressing the ranking of a wiki page that hadn't been reviewed for an extended period. However the real problem is users who quite simply fail to understand the difference between fully-maintained version-specific documentation and hearsay from a random page suggested by Google.

MarkMLl
Title: Re: Large or huge sets
Post by: Arioch on September 18, 2022, 02:23:14 pm
Now, official wiki at the official project TLD is hardly a
hearsay from a random page

When i - a newb and a stranger - was offered to just go and  edit LAZ wiki, instead of triggering talks in tracker - i freaked out

Now, you can put a banner in every page of wiki, saying "it is just draft and hearsay, try to find information in official doc first, here and there". This is at least under your control.

And Google probably operates in positive feedback loop. People see top search results - and click themm, and give links to them from forums/blogs. Google observes that behavior and upranks those pages, and this go rounds. Few years ago i was googling how to correctly compare floats in Pascal, so as to not write yet ad hoc retelling of ABC to yet another newb on Stack Overflow. And the top result was some UK FAQ site that bona fide suggested if FloatToSr(x) = FloatTostr(y) then...  They seem to take down that advice now, luckily.
Title: Re: Large or huge sets
Post by: jamie on September 18, 2022, 03:17:30 pm
@Arioch

   Do you own a license of recent Delphi?
Title: Re: Large or huge sets
Post by: Arioch on September 18, 2022, 03:22:33 pm
i prefer XE2 and can have it at work, i can have latest Community at home, but it sadly lacks sources
Title: Re: Large or huge sets
Post by: MarkMLl on September 18, 2022, 04:02:22 pm
Now, official wiki at the official project TLD is hardly a
hearsay from a random page

When i - a newb and a stranger - was offered to just go and  edit LAZ wiki, instead of triggering talks in tracker - i freaked out

I wasn't necessarily thinking of the wiki as hearsay etc., and I'd direct you to your later example about comparing floating point numbers.

However the fact remains that- at least in this project and community- the wiki is /not/ official documentation.

Quote
Now, you can put a banner in every page of wiki, saying "it is just draft and hearsay, try to find information in official doc first, here and there". This is at least under your control.

More importantly, and more relevant to my point, is that the wiki contains lots of stuff on "paths not taken": either discussion on relating to "approach A" when what Lazarus actually implemented was "approach B", or one-person subprojects where the person lost interest (possibly after demanding some precondition which he was told was quite simply not viable).

I share your feelings about Google being an echo chamber, but a particularly worrying thing is that when I watch people trying to use "The Interwebs" I see them go to the first page suggested by Google, read one screen, then backtrack and go to the second page. A particularly pernicious example is when they go to Wikipedia to look up e.g. a medical condition using their 'phone, and fail to realise that (a) coloured text is a link they can follow and (b) in the interest of brevity everything after the initial para has been compressed so they have to click on the section header before they see anything useful.

So they might start off being directed by Google to- say- the Wikipedia article on COVID, see nothing they recognise as useful or intelligible, backtrack and be given a Facebook Anti-vax page as the next suggestion.

MarkMLl
Title: Re: Large or huge sets
Post by: strmckr on September 20, 2022, 08:56:05 am
Quote
What is "><" ? It is "symmetric difference".

yes its symmetrical difference from set theory

a >< b    would be the set of digits not found in both sets.

if
  a is [1..5]
  b is [ 5,6] 
    then the  >< of AB  is [1..4,6]

which is exactly the opposite of intersection
     a*b  = [5]

constructively the instructions are
( (A+B)  - (A*B) )   

web linked above by others seems to be in order....

i am a self taught coder:  using Free-pascal IDE compiler
  there is lots i don't know how to use  if you have a way that i can use or learn from  pls divulge or link with examples


i need a code that can make a data point of 9 values  each storing a set  terms out of a size of 46656 possibles 

 0-80 points each mark up with corresponding active sets of a list out of the 46656 sets.
   so that i can do the following set-wise operations  +,-, *, =, <>, ><,  and check the 0..80 points are not empty or not
 
 like regular sets can use :    a * b = [] ,  or   a*b <> []  or  a*b = C 

while comparing n points to each other.

currently I'm attempting to use thaddys examples with my mods,

 works but i run into issues that i cannot update the initial data points with new information / changes on successive runs {they just never seem  to empty or clear or even reset}

or successive runs triggers a memory limit fault and crashes everything.
 
Title: Re: Large or huge sets
Post by: Thaddy on September 20, 2022, 09:50:51 pm
I will look into that. What is the data size of the individual elements? 40K elements should not be a problem unless the data size itself is huge (multiple Gb) or exceeds max(prtUint) for your platform.
One solution is to use windowed access. Basically intermediate storage.
I was not aware about the modification issue.
Your program should not crash anyway, as an EOutOfMemory exception can still recover somewhat or exit gracefully, since it is preallocated.
Requires the use of exceptions, though. And I warned about creating a huge set with higher unsigned integer types like qword.

Those cases need to be resolved in a different way, but it can follow the same algorithm.
Title: Re: Large or huge sets
Post by: strmckr on September 21, 2022, 08:58:46 am
Quote
And I warned about creating a huge set with higher unsigned integer types like
noted im just using:  Twordset

the data size of each set?
     N has size range of 1 - <600{max} depends on test case i'm checking
                      on a blank examination space a 46656 set is present for each N

the set range is
     [0..46655] 
 
 {each of these represents a 9 digit template where the 9 digits have a positional tag.}  -> not worried about this part

each: number 1-9 (n) 
where N is a set specifically of all the sets from the range that are applicable to N
     
 then   i have

[1..9][0..80] of set
   so that each N digit has 80 points  where each  0..80 is a set of x from N  that match 

code needs to be able to do

N(x) + N(x) = N 
{two cells match the full set of N}
   
   if i tried that directly using normal set syntax the system cant compute it at all so wrote a function for it.
 
testing code inserted into my per-working function that generated all 46656 sets, and a break down of N saved as its own  file.

Code: Pascal  [Select][+][-]
  1. // 46,656 potential  single digit grids.
  2.  
  3. procedure potential;
  4.  
  5. type
  6. hold = array of integer;
  7. base = array of numberset;
  8. digit = array of numberset;
  9.  
  10.  
  11. var
  12.    w1,w2,w3:TWordSet;  
  13.  
  14. setstuff: array [digits] of Twordset;
  15. Cellsetstuff: array [ digits,cell] of twordset;
  16.  
  17. locked:  array [digits] of numberset;
  18. deleted:  array [digits] of numberset;
  19.  
  20. stuff: array [digits] of numberset;
  21.  
  22. alist:array[digits] of word;
  23.  
  24. xn,w,p,n,n2,xn2,q,g,L,j,m,o,xn3,xn4,xn5:integer;
  25. output: text;
  26.  
  27. step: base;
  28. h: hold;
  29. z:digit;
  30.  
  31. begin
  32.  
  33. for n:=1 to 9 do
  34.  begin
  35.  setstuff[n]:= twordset.create;
  36.    for q in digitcell[n] do      
  37.     cellsetstuff[n,q]:=twordset.create;        
  38. end;
  39.  
  40.   for n:= 1 to 9 do
  41.     alist[n]:=0;
  42.        
  43. for N:= 1 to 9 do
  44. begin
  45. locked[n]:=[];
  46. deleted[n]:=[];
  47. stuff[n]:= [];
  48.  
  49. for xn:= 0 to 80 do
  50.  begin
  51.  
  52.   if s[xn] = [n]
  53.    then
  54.       locked[n]:= locked[n]+ [xn];
  55.  
  56.    if (s[xn] <> [n] ) and not( n in pm[xn])
  57.     then
  58.      deleted[n]:= deleted[n] + [xn];
  59.  
  60.   end;
  61.  end;
  62.  
  63. {startin cell}
  64.  
  65.   {delete the exsiting output if you want to rebuild it unhash this section}
  66. {assign(output,'C:\sudoku\pom\output.txt');
  67. erase(output);
  68. rewrite(output);
  69. close(output);  }
  70.  
  71. assign(output,'c:\sudoku\pom\exclusions.txt');
  72. erase(output);
  73. rewrite(output);
  74. close(output);
  75.  
  76. {smashes all prebuilt  txt files  of potential solutions for digits 1-9  }
  77.  for n:= 1 to 9 do
  78.   begin
  79.     case n of
  80.       1: assign(output,'C:\sudoku\pom\1.txt');
  81.       2: assign(output,'C:\sudoku\pom\2.txt');
  82.       3: assign(output,'C:\sudoku\pom\3.txt');
  83.       4: assign(output,'C:\sudoku\pom\4.txt');
  84.       5: assign(output,'C:\sudoku\pom\5.txt');
  85.       6: assign(output,'C:\sudoku\pom\6.txt');
  86.       7: assign(output,'C:\sudoku\pom\7.txt');
  87.       8: assign(output,'C:\sudoku\pom\8.txt');
  88.       9: assign(output,'C:\sudoku\pom\9.txt');
  89.      end;
  90.  
  91. erase(output);
  92. rewrite(output);
  93. close(output);
  94. end;
  95.  
  96. setlength(step,0);
  97. setlength(z,0);
  98. setlength(h,0);
  99.  
  100.  for xn:= 80 downto 72 do
  101.  
  102.   begin
  103.  
  104.   w:=0;    {step count}
  105.  
  106.   setlength(h,(w+1));  {set the array size to w}
  107.  
  108.   h[w]:=xn;        {starting point for first substep}
  109.  
  110.   setlength(step,(w+1));   {set the array size to w}
  111.  
  112.   step[w]:= [xn];  { keeps track of what cells are used at each step W }
  113.  
  114.   setlength(z,w+1);  {prevent occupy "new starting point" }
  115.  
  116.   z[w]:= peer[xn] + [xn]; {used cells  starting point}
  117.  
  118.    repeat
  119.  
  120.     for p:= h[w] downto (72-((w+1)*9)) do    {iteration of peers}
  121.  
  122.       if  p in ([0..80] - z[w] ) // added check used state
  123.        then
  124.          begin
  125.  
  126.           h[w]:=h[w]-1;    { advance the peer count for step w}
  127.  
  128.           inc(w);        {increase the step count}
  129.  
  130.           setlength(h,(w+1));
  131.           setlength(step,(w+1));     {increse the array size  to w}
  132.  
  133.           step[w]:= step[w-1] + [p] ;   {set the step cell active for the newly created step w}
  134.  
  135.           h[w]:= 71 - ((w)*9) ;  {set the new step w as 71 potential choice cells}
  136.  
  137.           setlength(z,w+1);  { increase size to w}
  138.  
  139.           z[w]:= z[w-1] +  peer[p] + [p]; {used cells  new  point}
  140.  
  141.           break;
  142.  
  143.         end
  144.        else
  145.           h[w]:=h[w]-1;  {if the above is false then advance the peer number}
  146.  
  147.  
  148. if w = 8
  149.   then
  150.    begin
  151.  
  152.  
  153. { generate the whole list to a specific file}
  154. {assign(output,'C:\sudoku\pom\output.txt');
  155. append(output);
  156. for n in step[w] do
  157.     write(output,n,' ');
  158.  
  159.     writeln(output);
  160.  
  161.     close(output); }
  162.  
  163.  for n:= 1 to 9 do
  164.   begin
  165.  
  166.     case n of
  167.       1: assign(output,'C:\sudoku\pom\1.txt');
  168.  
  169.       2: assign(output,'C:\sudoku\pom\2.txt');
  170.  
  171.       3:  assign(output,'C:\sudoku\pom\3.txt');
  172.  
  173.       4: assign(output,'C:\sudoku\pom\4.txt');
  174.  
  175.       5: assign(output,'C:\sudoku\pom\5.txt');
  176.  
  177.       6: assign(output,'C:\sudoku\pom\6.txt');
  178.  
  179.       7: assign(output,'C:\sudoku\pom\7.txt');
  180.  
  181.       8:  assign(output,'C:\sudoku\pom\8.txt');
  182.  
  183.       9:  assign(output,'C:\sudoku\pom\9.txt');
  184.        end;
  185.  
  186.   if ( step[w]  * locked[n] = locked[n] )
  187.   and ( step[w] * deleted[n] = [] )
  188.    then
  189.      begin
  190.          inc(alist[n]);
  191.        append(output);
  192.  
  193.        for q in (step[w] - locked[n])  do
  194.              begin
  195.           write(output, q,' ');
  196.                  
  197.                   include2(cellsetstuff[n,q],alist[n]);
  198.                   include2(setstuff[n],alist[n]);
  199.                   end;
  200.  
  201.         writeln(output);
  202.         close(output);
  203.  
  204.         stuff[n]:= stuff[n] + (step[w] - locked[n]);
  205.  
  206.      end;
  207.  
  208.  
  209. end; { N choice}
  210.  
  211.  end;   {w=8}
  212.  
  213.  
  214.     if ((h[w] < 0 )  and (w > 0 ))
  215.       or (w=8)
  216.       or ( ( [0..80] - z[w] = [] ) and (W < 8) and (w > 0) )
  217.        or ( (h[w] < (72 - ( (w+1)*9) ) )  and (w > 0)  )
  218.  
  219.     {the following resets the step to the previous state}
  220.      then
  221.       repeat
  222.       begin
  223.        w:=(w-1);
  224.        setlength(h,(w+1));
  225.        h[w]:= h[w];
  226.        setlength(step,(w+1));
  227.        setlength(z,w+1);
  228.  
  229.         end;
  230.        until   ( w = 0 ) or (h[w] > ((71 - (w+1)*9))  )
  231.  
  232.     until ((w = 0) and (h[w] < 0) ) or  ( ( w = 0) and (h[w] < (72 -( (w+1)*9) ) ) )
  233.  
  234.  end;
  235.  {size printing of all sets}
  236.  for n:= 1 to 9 do
  237.  begin
  238.  gotoxy(2,60+n);
  239.   write(n,':=  ',alist[n]);
  240.   end;
  241.  
  242.  {size 1}
  243.   for n:= 1 to 9 do
  244.  if  (stuff[n] <> [])
  245.  and (stuff[n] *  (digitcell[n]  -  (locked[n] + deleted[n]) ) = stuff[n])
  246.  and (  ((digitcell[n]  -  (locked[n] + deleted[n]) ) - stuff[n])  <> [] )
  247.   then
  248.     begin
  249.      assign(output,'C:\sudoku\pom\exclusions.txt');
  250.      append(output);
  251.         write(output,n, ' @: ');
  252.                         // cell has no templates out of all of them.    
  253.         for  xn  in  ((digitcell[n]  -  (locked[n] + deleted[n])) - stuff[n])do
  254.           begin
  255.             write(output,xn,' ');
  256.                     covered2[n]:=covered2[n]+[xn];
  257.                     active:=true;
  258.                    end;
  259.                    
  260.                    //cell is exclusivly in all sets
  261.                   for xn in digitcell[n] do  
  262.                    if equality(cellsetstuff[n,xn],setstuff[n])
  263.            then  
  264.               begin
  265.                              active:=true;
  266.                  covered[xn]:=covered[xn] + (pm[xn]-[n]);
  267.                                  write(output,'*',xn,'<>( ');
  268.                                 for o in pm[xn]-[n] do
  269.                                  write(output,o,' ');
  270.                                   write(output,') ')
  271.                 end;                                   
  272.                    
  273.                    
  274.            writeln(output);
  275.            close(output);
  276.                    
  277.                    
  278.      end; {size 1}
  279.  
  280.  {size 2}
  281.  for n in [1..9] do
  282.     for xn in digitcell[n] do
  283.            for xn2 in digitcell[n]*[(xn+1)..80] do    
  284.           begin
  285.        w1:=twordset.create;
  286.            
  287.        w1:= cellsetstuff[n,xn] + cellsetstuff[n,xn2];
  288.  
  289.          if  setstuff[n]<=w1
  290.            then
  291.                     begin                        
  292.                           for q in [1..9]-[n] do
  293.                            begin
  294.                  for g in setstuff[q] do
  295.                   if [xn,xn2] * digitcell[q] = [xn,xn2]
  296.                                    then                                  
  297.                                     if (g in (cellsetstuff[q,xn]))
  298.                                      and (g in (cellsetstuff[q,xn2]))
  299.                                       then
  300.                                           begin                                                          
  301.                         w2:=twordset.create;
  302.                                                
  303.                                            for L in digitcell[q] do
  304.                                              if (g in cellsetstuff[q,l])
  305.                                                    then
  306.                                                      begin
  307.                                                      exclude2(cellsetstuff[q,L],g);    
  308.                                                          include2(w2,l);
  309.                                                          end;
  310.  
  311.  
  312.         assign(output,'C:\sudoku\pom\exclusions.txt');
  313.      append(output);
  314.           write(output,'(',n,')',xn,',',xn2,':(');
  315.             for m in setstuff[n] do write(output,' ',m); write(output,' ) & ');
  316.          write(output,'(',q,')',xn,',',xn2,':(');
  317.                 for o in (setstuff[q]) do write(output,' ',o); write(output,' ) ');
  318.               write(output,'RT: ', G,' @ Digit: ',q, ' =>> <> ');
  319.                          
  320.                           exclude2(setstuff[q],g);                       
  321.                                                    
  322.                                                  for L in digitcell[q] do
  323.                                                     begin
  324.                                                            {no templates left for cells}
  325.                               w3:= setstuff[q] - cellsetstuff[q,l];                              
  326.                                                            if equality(w3,cellsetstuff[q,l])
  327.                                                               then
  328.                                                                     begin
  329.                                                                       write(output,L,' ');
  330.                                                                           active:=true;
  331.                                                                           covered2[q]:=covered2[q] + [L];
  332.                                                                           end;
  333.                                                                 {digits are locked to all sets}          
  334.                                                                 if equality(cellsetstuff[q,l],setstuff[q])
  335.                                    then  
  336.                                      begin
  337.                                                                          active:=true;
  338.                                       covered[l]:=covered[l] + (pm[l]-[q]);
  339.                                                                           write(output,'*',L,'<>( ');
  340.                                                                            for o in pm[l]-[q] do
  341.                                                                              write(output,o,' ');
  342.                                                                                  write(output,') ')
  343.                                      end;                                                                        
  344.                                                          end;
  345.                                                        
  346.                                                        
  347.                                                          
  348.                   writeln(output);
  349.            close(output);      
  350.                    
  351.                    include2(setstuff[q],g);
  352.                    for L in w2 do
  353.                    begin
  354.                                 include2(cellsetstuff[q,L],g); 
  355.                            end;
  356.                    w2.free;
  357.                          break;                                        
  358.  
  359.                                           end;                                     
  360.                                         end;                                     
  361.                  end;
  362.                                  w1.free;
  363.                                  
  364.             end;        {size 2}                 
  365.  
  366. end;

 when i run this code, then reload the stat : and run again
i get
EacessViolation: access Violation
or
  some random memory limit error when i remove the "break" from the above code.

this code for me: is something I've wanted to add to my program for years but lacking large sets has hindered my progress on it.
Title: Re: Large or huge sets
Post by: avk on September 22, 2022, 03:17:22 pm
@strmckr, just curious, are you trying to make your own sudoku solver?
Title: Re: Large or huge sets
Post by: Thaddy on September 22, 2022, 03:24:39 pm
You are over-indexing: 0..80 should be 0..79. Programmers count from zero and not up until 81...
Title: Re: Large or huge sets
Post by: strmckr on September 22, 2022, 09:09:59 pm
a typo in the description of function..

Sorry should read
   it as  0-80 in my code for the 81 cells


Quote
@strmckr, just curious, are you trying to make your own sudoku solver?
  not trying,  I have a pretty extensive solver
 I've had it posted  online In players and programers forums since roughly 07
 HERE (http://forum.enjoysudoku.com/post249996.html#P249996)

(old version of my present code I have been rebuilding alot of since I learned some new stuff)

Been wanting t add p.o.m to it but it needs 46656 templates to function. My solvers set based so its never been able to go that high with how fps is programed with 256 limit.

Title: Re: Large or huge sets
Post by: MarkMLl on September 22, 2022, 10:00:48 pm
not trying,  I have a pretty extensive solver

If I might be permitted an aside... a number of years ago I asked a question on a private conferencing system (CIX, in the UK) relating to a knight's tour on (I think) a 12x12 board. A gentleman called Stuart Vernon promptly posted a solution, but somebody pointed out that it wasn't /strictly/ correct since while it touched all squares the start and end positions were different. A few minutes later he posted a solution to meet that requirement.

At that point somebody remarked on his speed and asked whether he was doing it by hand, and he explained what he was doing. I forget his background, but he had a fully-subscribed copy of a high-end Constraint Logic Programming package (possibly ECLiPSe, when it was anything-but free), which he was using to design soduku problems for various clients: the twist being that each one had a carefully-calibrated level of difficulty :-)

MarkMLl
Title: Re: Large or huge sets
Post by: strmckr on September 22, 2022, 11:39:28 pm
 Sounds like dlx with extra constraints. There is a few other ways to make it start and end on its own move
.
   I do have a code  that Can solve my own version of knight moves or be modified to solve chess restricted moves.  (  It is iterative and backtracking.)

  I call my piece Sinbad seen   here (http://forum.enjoysudoku.com/fairy-chess-piece-tour-puzzles-including-numbrix-hidato-t30443.html?hilit=Sinbad)
Title: Re: Large or huge sets
Post by: avk on September 23, 2022, 01:27:02 pm
As for me, at one time I was completely fascinated by how these problems are formulated in terms of graph theory.
Title: Re: Large or huge sets
Post by: MarkMLl on September 23, 2022, 03:40:34 pm
Sounds like dlx with extra constraints. There is a few other ways to make it start and end on its own move.

More like that dlx is a specialised solver for one particular problem. I believe Stuart was paying several thousand pounds a year for ECLiPSe or whatever he had.

MarkMLl
TinyPortal © 2005-2018