[M3devel] iterating over sets?

[Rodney M. Bates]

I don't think it's by any means trivial.

I have a set-of-integer module that handles heap-allocated sets of
integers whose base range is nonstatic, and it does it essentially the
way you give.  It's a real mess.  I converted it some years back from
Modula-2, then started changing its design piecemeal, as needed
by one application, so it's full of inconsistencies.

I started writing a complete replacement, but have never gotten
back to it.  I planned to do some low-level bit-twiddling stuff
for this problem, but that's down in to-be-implemented procedures.

My plan is to do binary search within a word for the next nonzero bit
by masking out half a Word.T, then testing it for all zero, etc., going
to fourths, eighths, etc. subsequently.  I plan to code it looplessly,
i.e., as a tree of IFs, since a word has static size on a given
machine.  I thought about a way to code it that would auto-adapt to
different word sizes, but don't remember that I had come up with one.

For the M3 language-provided set types, I suppose something similar
could be done in an unsafe module, but it would be dependent on
knowing how the compiler represented the sets and LOOPHOLEing
to arrays of Word.T.

For the different words of a set, I think looping through them is
probably the best you can do.  Of course, an all-zero test on a word
can be done in constant time, and is in fact, just the zero-th step
of the binary-search strategy I mentioned.

My partially-implemented module trims words that are all-zero off both
ends, whenever they can be located without unnecessary extra work.
Even so, there still can be properly embedded zero words.  Trying
to go beyond this starts to make it work more like the existing
library Sets module, which I would expect to be better if the sets
are quite sparse, but much worse (at least in space) if dense.

Jay wrote:
> Let's say I had
>  
> TYPE T = SET OF { 0 .. 256 };
>  
> Must I say:
>  
> VAR t: T;
> FOR i := FIRST(t) TO LAST(t)
>   IF i IN t DO
>    something with i
>   END
> END
>  
> Surely there's a better way involving scanning forward for the next bit 
> more than one bit at a time?
>  
>  - Jay
>  
> 
> ------------------------------------------------------------------------
> Boo! Scare away worms, viruses and so much more! Try Windows Live 
> OneCare! Try now! 
> <http://onecare.live.com/standard/en-us/purchase/trial.aspx?s_cid=wl_hotmailnews>

-- 
-------------------------------------------------------------
Rodney M. Bates, retired assistant professor
Dept. of Computer Science, Wichita State University
Wichita, KS 67260-0083
316-978-3922
rodney.bates at wichita.edu