CODEWITHSUNDEEP
algorithmdelphiset
Mason Wheeler
Mason Wheeler

Reputation: 84590

How to get the highest value from a Delphi set?

Is there any way to extract the highest (or lowest) value in a set? For example, if I have the following "set of byte":

[0, 1, 2, 4, 5, 28, 199]

is there any function I could run on that and get back 199 as the result?

EDIT: There's an obvious brute-force solution involving a for..in loop. If possible, I'd like to find a better way than that.

Upvotes: 2

Views: 6558

Answers (5)

Andrea Ocera
Andrea Ocera

Reputation: 11

Highest and lowest, not use of Math unit:

type
  TCharSet = set of Char;

function MaxOfSet(aSet: TCharSet):Char;
var
  Data:array[0..SizeOf(TCharSet)-1] of Byte absolute aSet;
  i,r:Byte;
begin
  if aSet<>[] then begin
     i:=SizeOf(TCharSet)-1;
     while (i>0) and (Data[i]=0) do
        Dec(i);
     r:=i*8;
     i:=Data[i];
     while (i and $80)=0 do begin
        i:=i shl 1;
        Dec(r)
     end;
     Result:=Chr(r+7)
  end
  else
     raise Exception.Create('Unable to extract max value from an empty set');
end;

function MinOfSet(aSet: TCharSet):Char;
var
  Data:array[0..SizeOf(TCharSet)-1] of Byte absolute aSet;
  i,r:Byte;
begin
  if aSet<>[] then begin
     i:=0;
     while (i<SizeOf(TCharSet)-1) and (Data[i]=0) do
        Inc(i);
     r:=i*8;
     i:=Data[i];
     while (i and 1)=0 do begin
        i:=i shr 1;
        Inc(r)
     end;
     Result:=Chr(r)
  end
  else
     raise Exception.Create('Unable to extract min value from an empty set');
end;

Upvotes: 1

Hermann D&#246;ppes
Hermann D&#246;ppes

Reputation: 11

Nearly the same, but shorter:

type
  TByteSet = set of Byte;

function MaxSet(S: TByteSet): Byte;
var
  CardArr: Array [0..7] of Cardinal absolute S;
  i: Byte;
begin
  i := 7;
  while (i > 0) AND (CardArr[i] = 0) do
    Dec(i);
  Result := i + Floor(Log2(CardArr[i]));
end;

Upvotes: 1

Allen Bauer
Allen Bauer

Reputation: 16862

Here is a little quicker version that uses knowledge of the internal structure of the byte set.

type
  TByteSet = set of Byte;

function HighestElement(const ByteSet: TByteSet): Byte;
type
  TSetBytes = array[0..SizeOf(TByteSet) - 1] of Byte;
var
  I, J: Integer;
  B: Byte;
  SetBytes: TSetBytes;
begin
  if ByteSet <> [] then
  begin
    SetBytes := TSetBytes(ByteSet);
    // Start at the top and work down, one byte at a time
    for I := SizeOf(TByteSet) - 1 downto 0 do
    begin
      // Any bits set here
      B := SetBytes[I];
      if B <> 0 then
      begin
        Result := I * 8;
        for J := 0 to 7 do
          if (B shr J) and 1 <> 0 then
          begin
            Result := Result + J;
            Exit;
          end;
      end;
    end;
  end else
    // No elements set
end;

You can change the type of the set, TByteSet, to nearly any set type, and this function should still work. Just replace TByteSet within the function decl and body with the type of your set. You can also modify it to return the actual element type if using a set of AnsiChar, or a set of some enumeration type. To get the lowest value, change the "I" for loop to "0 to SizeOf(TByteSet) - 1" and the if test in the "J" loop to "if (B shl J) and $80 <> 0"

Upvotes: 2

Juliet
Juliet

Reputation: 81526

Sets are unordered, so you're not going to get much better than a loop. If you're constantly looking up the min/max value of a set, then use a heap data structure, which provides O(1) lookup to get the min/max value and O(log n) lookup on any other value.

Upvotes: 6

Rob Kennedy
Rob Kennedy

Reputation: 163317

A loop really is the formally correct way to do it.

type
  TSetType = set of TEnumType;

function HighestMember(const s: TSetType): TEnumType;
begin
  for Result := High(Result) downto Low(Result) do
    if Result in s then
      exit;
  raise Exception.Create('empty sets have no highest member');
end;

Any other kind of solution will require type-casting or assembler, both of which force you to lose type-safety — they go "outside the language," so to speak.

If you can guarantee that your set has no more than 32 possible elements, then the set can be overlaid with an ordinary integer, and your question is equivalent to asking for the position of the highest bit set in a 32-bit integer. That's been asked here before, pretty much:

If you don't have a 32-element restriction on the set type, then you have Delphi's 256-element limit, and any bit-twiddling solution will need to handle a 32-byte input.

Upvotes: 15

Related Questions