Large Integer Sets In Delphi

If you ever needed to do set type operations like union, intersection or difference on a collection of integer values containing more than 256 elements, you would not be able to use the standard set data type.

Sets are frequently used with enumerated values (having integer values beneath), and if needing to operate on more than 256 elements – you would need a different approach.

The approach suggested below is in using an array of integer values to mimic set functionality by implementing common set operations like: union, intersection, difference and alike. Note that in a set a value cannot appear two times, that is, a set (1,2,3) is the same as (1,1,2,3,3).

Here’s one approach you can use to have sets of up to 65536 integer elements. The unit (provided by Alan Lloyd) implements sets as integer arrays and exposes functions to do set like operations.

Here's Alan's comment: Having seen your "Set of String" on the web reminds me that a while ago I wrote a TWordSet which allows up to 65536 word-sized values for really large sets. It includes the following functions and procedures :

CountInWordSet - returns the number of elements in a set,
ContinuousWordSet - returns a wordset containing all integers from A to B,
EmptyWordSet - returns an empty set,
FullWordSet - returns a full set,
IsInWordSet - returns true if I is in WordSet,
WordSetContains - returns true if the whole of AWordSet is in BWordSet,
WordSetDifference - returns the difference of AWordSet over BWordSet,
WordSetExclude - removes an integer from WordSet,
WordSetInclude - adds an integer to WordSet,
WordSetIntersect - returns the intersection of AWordSet and BWordSet,
WordSetUnion - returns the union of AWordSet and BWordSet

unit WordSetU;
{word sets - up to 65536 members}
{Alan Lloyd, 10 July 2000}

interface

uses
  Windows, Classes, SysUtils;

type
  TWordSet = array[0..2047] of DWord;

function CountInWordSet(WordSet : TWordSet) : integer;
function ContinuousWordSet(A, B : integer) : TWordSet;
function EmptyWordSet : TWordSet;
function FullWordSet : TWordSet;
function IsInWordSet(I : integer; var WordSet : TWordSet) : boolean;
function WordSetContains(AWordSet, InBWordSet : TWordSet) : boolean;
function WordSetDifference(AWordSet, BWordSet : TWordSet) : TWordSet;
procedure WordSetExclude(var WordSet : TWordSet; I : integer);
procedure WordSetInclude(var WordSet : TWordSet; I : integer);
function WordSetIntersect(AWordSet, BWordSet : TWordSet) : TWordSet;
function WordSetUnion(AWordSet, BWordSet : TWordSet) : TWordSet;

implementation

function EmptyWordSet : TWordSet;
begin
  FillChar(Result, SizeOf(TWordSet), #0);
end;

function FullWordSet : TWordSet;
begin
  FillChar(Result, SizeOf(TWordSet), #$FF);
end;

procedure WordSetInclude(var WordSet : TWordSet; I : integer);
{adds I to WordSet}
var
  dw, b : integer;
begin
  dw := I div 32; // index of the storage DWord
  b := I mod 32;  // bit in DWord to set
  WordSet[High(TWordSet) - dw] := WordSet[High(TWordSet) - dw] or (1 shl b);
end;

procedure WordSetExclude(var WordSet : TWordSet; I : integer);
{removes I from WordSet}
var
  dw, b : integer;
begin
  dw := I div 32;
  b := I mod 32;
  WordSet[High(TWordSet) - dw] := WordSet[High(TWordSet) - dw] and not (1 shl b);
end;

function IsInWordSet(I : integer; var WordSet : TWordSet) : boolean;
{returns true if I is in WordSet}
var
  dw, b : integer;
begin
  dw := I div 32;
  b := I mod 32;
  Result := (WordSet[High(TWordSet) - dw] and (1 shl b)) > 0;
end;

function WordSetUnion(AWordSet, BWordSet : TWordSet) : TWordSet;
{returns the union of AWordSet & BWordSet}
var
  i : integer;
begin
  for i := Low(TWordSet) to High(TWordSet) do
    Result[i] := AWordSet[i] or BWordSet[i];
end;

function WordSetDifference(AWordSet, BWordSet : TWordSet) : TWordSet;
{returns the difference of AWordSet over BWordSet}
var
  i : integer;
begin
  for i := Low(TWordSet) to High(TWordSet) do
    Result[i] := AWordSet[i] and not BWordSet[i];
end;

function WordSetIntersect(AWordSet, BWordSet : TWordSet) : TWordSet;
{returns the intersection of AWordSet & BWordSet}
var
  i : integer;
begin
  for i := Low(TWordSet) to High(TWordSet) do
    Result[i] := AWordSet[i] and BWordSet[i];
end;

function WordSetContains(AWordSet, InBWordSet : TWordSet) : boolean;
{returns true if the whole of AWordSet is in BWordSet}
var
  i : integer;
begin
  Result := true;
  for i := Low(TWordSet) to High(TWordSet) do
    if not ((AWordSet[i] and InBWordSet[i]) = AWordSet[i]) then
    begin
      Result := false;
      Break;
    end; {if not ((AWordSet[i] and InBWordSet[i]) = AWordSet[i])}
end;

function CountInWordSet(WordSet : TWordSet) : integer;
{counts the number of elements in a set}
var
  i, j : integer;
begin
  Result := 0;
  for i := Low(TWordSet) to High(TWordSet) do
    if WordSet[i] <> 0 then
      for j := 0 to (SizeOf(DWord) * 8) - 1 do
        if (WordSet[i] shr j) and 1 > 0 then
          inc(Result);
end;

function ContinuousWordSet(A, B : integer) : TWordSet;
{returns a wordset containing all integers from A to B}
var
  i : integer;
begin
  FillChar(Result, SizeOf(TWordSet), #0);
  if A > B then 
  begin
    i := A;
    A := B;
    B := i;
  end;
  for i := A to B do
    WordSetInclude(Result, i);
end;

end.

var
  full_ws, years_ws, dws : TWordSet;
begin
  full_ws := FullWordSet;
  
  //specifies all "years" from 19989 to 2012
  years_ws := ContinuousWordSet(1998, 2012);

  //add 1973 if not in there (you can remove the IF part!)
  if NOT IsInWordSet(1973, years_ws) then WordSetInclude(full_ws, 1973);
  
  //all other "years" from 0 till 65536 excluding those in years_ws  
  dws := WordSetDifference(full_ws, years_ws);

  Caption := IntToStr(CountInWordSet(dws));
  //returns 65521 as the number of elements in dws.
end;