How to get the highest value from a Delphi set?

Question

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.

Answer 1

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:

• Position of least significant bit that is set

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.

Answer 2

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.

Answer 3

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"