[fpc-devel] Re: Testing for..in feature

[Bram Kuijvenhoven]

Alexander Klenin wrote:
> The best Succ(X) algorithm I can think of that works correctly on
> sparse enums is O(log enum_size).

As Florian does, I assume you discard the solution to use a lookup table from 'sparse values' to 'dense values'. Obviously that may quickly consume large amounts of memory, especially if the enum contains powers of two.

In theory, for .. in .. for sparse enums can be implemented in O(n) though. But then you should avoid using Succ.

Or, the memory location for a sparse enum variable could always contain a linear, 'dense' index into the table which holds the actual, 'sparse' values. Obviously this has a performance impact over not supporting Succ for sparse enums, but it doesn't change the runtime complexity of any code.

The question remains whether you're willing to put that much effort into it and whether  you can live with the impact of doing table lookups each time the enum value needs to be casted to an integer (such as when calling C code).

Regards,

Bram