Recent

Author Topic: Question about set implementations  (Read 2065 times)

dkettle

  • New member
  • *
  • Posts: 7
Question about set implementations
« on: June 06, 2021, 05:52:11 pm »
Is there a package or library that implements sets of arbitrary data types (not just the built-in integer types)? I want to declare a set of records, something like this:

Code: Pascal  [Select][+][-]
  1. MyRecordType =
  2.     Record
  3.        ...
  4.     End;
  5.  
  6. MySet = SomePkg.Set of MyRecordType;

If not, I'll just use an array and make sure that each element is unique. But it will save me time if something already exists.

Thanks.

jamie

  • Hero Member
  • *****
  • Posts: 6090
Re: Question about set implementations
« Reply #1 on: June 06, 2021, 06:01:18 pm »
No, sets are more for compiler help to make your code readable , they can be stored because they do use space in memory of course but they won't do as you wish..

 You can have an array of Tobjects as the base if you wish, in which case you need to create them but for that you could use a TLIST that already handles that..


 You can also do the same using the OBJECT model and base it from a known type for the array, but it still needs to be dynamically created for it to work since you stated each element is going to be different..

 But something tells me you are over complicating things.

 You could have a Set field within each record too.

 P.S
  Look into using a Variant CASE within a record, that way they are all the same but can be used differently
« Last Edit: June 06, 2021, 06:04:44 pm by jamie »
The only true wisdom is knowing you know nothing

PascalDragon

  • Hero Member
  • *****
  • Posts: 5446
  • Compiler Developer
Re: Question about set implementations
« Reply #2 on: June 07, 2021, 09:05:41 am »
Is there a package or library that implements sets of arbitrary data types (not just the built-in integer types)? I want to declare a set of records, something like this:

You can use one of the generic types from Generics.Collections:

Code: Pascal  [Select][+][-]
  1. type
  2.   // alternatives are THashSet<>, TSortedSet<> or TSortedHashSet<>
  3.   // in mode Delphi you need to remove the "specialize"
  4.   MySet = specialize THashSet<MyRecordType>;

You then need to use the methods of the set class (all provided by the parent class TCustomSet<>) to add or remove elements.

marcov

  • Administrator
  • Hero Member
  • *
  • Posts: 11383
  • FPC developer.
Re: Question about set implementations
« Reply #3 on: June 07, 2021, 09:09:55 am »
If you want a value type bitset that is also possible, but then you need to define the range of possibilities before using.

I distilled the below code from earlier posts on this forum:

Code: [Select]
    program bigvalueset;
    {$mode objfpc}{$modeswitch advancedrecords}
    type
      generic TBigValueSet<T> = record
      private
      const
        LOWER   = Low(T);
        UPPER   = High(T) - LOWER;
        SET_LEN = (Upper shr 5 + Ord(Upper and 31 <> 0)) + Ord(UPPER = 0);
      type
        TDWordBits = 0..31;
        TDWordSet = set of TDWordBits;
        PDWordSet = ^TDWordSet;
        TSet = array[0..Pred(SET_LEN)] of DWord;
      var
        FSet: TSet;
        class operator Initialize(var s: TBigValueSet);
      public
        procedure Include(aValue: T);
        procedure Exclude(aValue: T);
        class operator +(constref L, R: TBigValueSet): TBigValueSet;
        class operator -(constref L, R: TBigValueSet): TBigValueSet;
        class operator *(constref L, R: TBigValueSet): TBigValueSet;
        class operator ><(constref L, R: TBigValueSet): TBigValueSet;
        class operator =(constref L, R: TBigValueSet): Boolean;
        class operator <=(constref L, R: TBigValueSet): Boolean;
        class operator in (aValue: T; const aSet: TBigValueSet): Boolean;
      end;
     
    class operator TBigValueSet.Initialize(var s: TBigValueSet);
    begin
      s.FSet := Default(TSet);
    end;
     
    procedure TBigValueSet.Include(aValue: T);
    begin
      System.Include(PDWordSet(@FSet[(Integer(aValue) - LOWER) shr 5])^, (Integer(aValue) - LOWER) and 31);
    end;
     
    procedure TBigValueSet.Exclude(aValue: T);
    begin
      System.Exclude(PDWordSet(@FSet[(Integer(aValue) - LOWER) shr 5])^, (Integer(aValue) - LOWER) and 31);
    end;
     
    class operator TBigValueSet.+(constref L, R: TBigValueSet): TBigValueSet;
    var
      I: Integer;
    begin
      for I := 0 to Pred(SET_LEN) do
        Result.FSet[I] := L.FSet[I] or R.FSet[I];
    end;
     
    class operator TBigValueSet.-(constref L, R: TBigValueSet): TBigValueSet;
    var
      I: Integer;
    begin
      for I := 0 to Pred(SET_LEN) do
        Result.FSet[I] := L.FSet[I] and not R.FSet[I];
    end;
     
    class operator TBigValueSet.*(constref L, R: TBigValueSet): TBigValueSet;
    var
      I: Integer;
    begin
      for I := 0 to Pred(SET_LEN) do
        Result.FSet[I] := L.FSet[I] and R.FSet[I];
    end;
     
    class operator TBigValueSet.><(constref L, R: TBigValueSet): TBigValueSet;
    var
      I: Integer;
    begin
      for I := 0 to Pred(SET_LEN) do
        Result.FSet[I] := L.FSet[I] xor R.FSet[I];
    end;
     
    class operator TBigValueSet.=(constref L, R: TBigValueSet): Boolean; inline;
    var
      I: Integer;
    begin
      for I := 0 to Pred(SET_LEN) do
        if L.FSet[I] <> R.FSet[I] then
          exit(False);
      Result := True;
    end;
     
    class operator TBigValueSet.<=(constref L, R: TBigValueSet): Boolean; inline;
    var
      I: Integer;
    begin
      for I := 0 to Pred(SET_LEN) do
        if R.FSet[I] <> L.FSet[I] or R.FSet[I] then
          exit(False);
      Result := True;
    end;
     
    class operator TBigValueSet.in (aValue: T; const aSet: TBigValueSet): Boolean;
    begin
      Result := TDWordBits((Integer(aValue) - LOWER) and 31) in PDWordSet(@aSet.FSet[(Integer(aValue) - LOWER) shr 5])^;
    end;
     
    type
      TMyRange = -1022..1023;
    var
      s, s2: specialize TBigValueSet<TMyRange>;
    begin
      WriteLn('SizeOf(s) = ', SizeOf(s));
      s.Include(-5);
      WriteLn('-5 in s = ', -5 in s);
      s.Include(1022);
      WriteLn('1022 in s = ', 1022 in s);
      s2.Include(-15);
      s2.Include(-900);
      s2 := s2 + s;
      WriteLn('-5 in s2 = ', -5 in s2);
      WriteLn('-15 in s2 = ', -15 in s2);
      WriteLn('-900 in s2 = ', -900 in s2);
      WriteLn('1022 in s2 = ', 1022 in s2);
      s2 := s2 - s2;
      WriteLn('-5 in s2 = ', -5 in s2);
      WriteLn('-15 in s2 = ', -15 in s2);
      WriteLn('-900 in s2 = ', -900 in s2);
      WriteLn('1022 in s2 = ', 1022 in s2);
    end.
 

dkettle

  • New member
  • *
  • Posts: 7
Re: Question about set implementations
« Reply #4 on: June 07, 2021, 01:37:33 pm »
Is there a package or library that implements sets of arbitrary data types (not just the built-in integer types)? I want to declare a set of records, something like this:

You can use one of the generic types from Generics.Collections:

Code: Pascal  [Select][+][-]
  1. type
  2.   // alternatives are THashSet<>, TSortedSet<> or TSortedHashSet<>
  3.   // in mode Delphi you need to remove the "specialize"
  4.   MySet = specialize THashSet<MyRecordType>;

You then need to use the methods of the set class (all provided by the parent class TCustomSet<>) to add or remove elements.

Thanks! I'll give it a try.

 

TinyPortal © 2005-2018