Forum > General
Large or huge sets
Thaddy:
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).
Thaddy:
--- 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.
Thaddy:
--- 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.
Navigation
[0] Message Index
[#] Next page