Forum > General

Large or huge sets

(1/14) > >>

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  [+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i < x.length; i++) { x[i].style.maxHeight='none'; x[i].style.height = Math.min(x[i].clientHeight+15,306)+'px'; x[i].style.resize = "vertical";}};} ---{\$mode objfpc}{\$inline on}{ A simple way to implement large or huge sets. (c) 2019 Thaddy de Koning. No license and not re-licensable: free for all to use.  Copyright holds:  You can not claim license nor copyrigths }unit largesets;{ Operator      Action  ---------------------------------------------  +             Union  -             Difference  *             Intersection  ><        Symmetric difference  <=        Contains  include   Include an element in the set  exclude   Exclude an element from the set  in        Check wether an element is in a set}interfaceuses  generics.collections; type  TWordSet  = specialize TSortedHashSet<word >;  { The next two can cause some real memory pressure, be careful }  TDWordSet = specialize TSortedHashSet<dword>;  TQWordSet = specialize TSortedHashSet<Qword>;   { union }  operator + (const a,b:TWordset ):TWordSet;  operator + (const a,b:TDWordset):TDWordSet;  operator + (const a,b:TQWordset):TQWordSet;   { difference }  operator - (const a,b:Twordset ):TWordSet;  operator - (const a,b:TDwordset):TDWordSet;  operator - (const a,b:TQwordset):TQWordSet;   { intersection }  operator * (const a,b:TwordSet ):TWordSet;  operator * (const a,b:TDwordSet):TDWordSet;  operator * (const a,b:TQwordSet):TQWordSet;   { symmetric difference }  operator >< (const a,b:TWordSet ):TWordSet;  operator >< (const a,b:TDWordSet):TDWordSet;  operator >< (const a,b:TQWordSet):TQWordSet;   { contains }  operator <= (const a,b:TWordSet ):Boolean;  operator <= (const a,b:TDWordSet):Boolean;  operator <= (const a,b:TQWordSet):Boolean;   { in }  operator in (const a:word; const b:TWordset ):Boolean;  operator in (const a:dword;const b:TDWordset):Boolean;  operator in (const a:qword;const b:TQWordset):Boolean;   { include }  procedure include(const a:TWordSet; const b:Word);  procedure include(const a:TDWordSet;const b:DWord);  procedure include(const a:TQWordSet;const b:QWord);   { exclude }  procedure exclude(const a:TWordSet;const  b:Word);  procedure exclude(const a:TDWordSet;const b:DWord);  procedure exclude(const a:TQWordSet;const b:QWord); implementation   { union }  operator + (const a,b:TWordset):TWordSet;  begin       b.UnionWith(a);    Result := b;  end;      operator + (const a,b:TDWordset):TDWordSet;  begin    b.UnionWith(a);    Result := b;  end;   operator + (const a,b:TQWordset):TQWordSet;  begin    b.UnionWith(a);    Result := b;  end;   { difference }  operator -(const a,b:Twordset):TWordSet;  begin    b.ExceptWith(a);    result:=b;  end;    operator -(const a,b:TDwordset):TDWordSet;  begin    b.ExceptWith(a);    result:=b;  end;   operator -(const a,b:TQwordset):TQWordSet;  begin    b.ExceptWith(a);    result:=b;  end;   { intersection }  operator *(const a,b:TwordSet):TWordSet;  begin    b.IntersectWith(a);    Result := b;  end;    operator *(const a,b:TDwordSet):TDWordSet;  begin    b.IntersectWith(a);    Result := b;  end;   operator *(const a,b:TQwordSet):TQWordSet;  begin    b.IntersectWith(a);    Result := b;  end;   { symmetric difference }  operator ><(const a,b:TWordSet):TWordSet;  begin    b.SymmetricExceptWith(a);    Result := b;  end;    operator ><(const a,b:TDWordSet):TDWordSet;  begin    b.SymmetricExceptWith(a);    Result := b;  end;   operator ><(const a,b:TQWordSet):TQWordSet;  begin    b.SymmetricExceptWith(a);    Result := b;  end;   { contains }  operator <=(const a,b:TWordSet):Boolean;  var    c:word;  begin    Result := true;    for c in a do    if not b.contains(c) then    begin      Result := False;      break;    end;  end;    operator <=(const a,b:TDWordSet):Boolean;  var    c:word;  begin    Result := true;    for c in a do    if not b.contains(c) then    begin      Result := False;      break;    end;  end;   operator <=(const a,b:TQWordSet):Boolean;  var    c:word;  begin    Result := true;    for c in a do    if not b.contains(c) then    begin      Result := False;      break;    end;  end;   { in }  operator in (const a:word;const b:TWordset):Boolean;  begin    Result := b.Contains(a);  end;     operator in (const a:dword;const b:TDWordset):Boolean;  begin    Result := b.Contains(a);  end;   operator in (const a:qword;const b:TQWordset):Boolean;  begin    Result := b.Contains(a);  end;   { include }  procedure include(const a:TWordSet;const b:Word);  begin    a.Add(b);  end;    procedure include(const a:TDWordSet;const b:DWord);  begin    a.Add(b);  end;   procedure include(const a:TQWordSet;const b:QWord);  begin    a.Add(b);  end;   { exclude }  procedure exclude(const a:TWordSet;const b:Word);  begin    a.Remove(b);  end;    procedure exclude(const a:TDWordSet;const b:DWord);  begin    a.Remove(b);  end;   procedure exclude(const a:TQWordSet;const b:QWord);  begin    a.Remove(b);  end; end.

marcov:
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?

Ñuño_Martínez:
Not sure but I think that some operators don't work as expected.  I mean, operator + shouldn't be like this?

--- Code: Pascal  [+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i < x.length; i++) { x[i].style.maxHeight='none'; x[i].style.height = Math.min(x[i].clientHeight+15,306)+'px'; x[i].style.resize = "vertical";}};} --- OPERATOR + (CONST a, b:TWordset): TWordSet;BEGIN  RESULT := TWordSet.Create;  RESULT.Copy (b);  RESULT.UnionWith (a)END;
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).

--- Quote from: marcov on September 10, 2019, 11:05:51 am ---So try if your solution also works for a large enum.

--- End quote ---
That works.  Becase it avoids the size of enums.  work in progress.

--- Quote from: Ñ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?
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).

--- End quote ---
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.