<html>
<head>
<style>
.hmmessage P
{
margin:0px;
padding:0px
}
body.hmmessage
{
FONT-SIZE: 10pt;
FONT-FAMILY:Tahoma
}
</style>
</head>
<body class='hmmessage'>I was asking about Modula-3 syntax and built in mechanisms.<BR>
<BR>Here are the ways to implement this sort of thing.<BR>
<BR>There are two main scenarios:<BR>
<BR>a small set<BR> this can be either 0..n or n..m<BR> "small" is n or m-n<BR>
<BR>a big set<BR> again 0..n or n..m<BR> offseting the start is trivial<BR>
<BR>A small set should be represented by an array of some integer type,<BR>such as array of 8 bit int, or 16 bit int, or 32 bit, or 64 bit int<BR>
<BR>It should support operations such as:<BR>
<BR>Operations my question needs:<BR> FindFirstSetBit<BR> FindNextSetBit(start)<BR>
<BR>Operation of course needed:<BR> GetBit(offset)<BR>
<BR>Operations other uses of this data structure would want, though maybe not a "set":<BR> FindFirstClearBit<BR> FindNextClearBit(start)<BR> FindClearBits(start,count)<BR> FindSetBits(start,count)<BR> SetBits(start,count)<BR> ClearBits(start,count)<BR>
You might want to combine some of them -- FindClearBitsAndSet, FindSetBitsAndClear.<BR>
<BR>Operations that Modula-3 already has:<BR> union<BR> intersect<BR> difference<BR> symmetric_difference<BR>
<BR>I was asked stuff about this as an interview question years ago.<BR>
<BR>Depending on processor support, one implementation is an array of bytes and you<BR>have roughly the following small tables:<BR>
<BR>typedef unsigned char byte;<BR>byte MaximumBitsSet[256];<BR>byte MaximumBitsClear[256];<BR>byte BitsSetLeft[256];<BR>byte BitsClearLeft[256];<BR>byte BitsSetRight[256];<BR>byte BitsClearRight[256];<BR>byte OffsetOfMaximumBitsSet[256];<BR>byte OffsetOfMaximumBitsClear[256];<BR>
<BR>Some of this might be redundant.<BR>You could pack them the other way:<BR>
<BR>typedef struct BitInfo_t {<BR> byte MaximumBitsSet; // or 3 bit bitfield<BR> byte MaximumBitsClear;<BR> etc.<BR>} BitInfo_t;<BR>
<BR>BitInfo_t BitInfo[256];<BR>
<BR>From here you can reasonably easily reasonably efficiently implement<BR>the functions I identified.<BR>
<BR>Now, if your processor supports intructions to compute some of these<BR>figures efficiently, esp. on a 32 bit or 64 bit integer, that might<BR>be more efficient. There's a term here "population count" and an instruction<BR>in some processors. Maybe also "lzcnt" -- leading zero count.<BR>
<BR>If the set does not start at 0, you just offset things at some point. Easy.<BR>
<BR>For a large set, this will use too much memory.<BR>You can use simply a sorted array of integers.<BR>And use binary search against that.<BR>Not terrible.<BR>
<BR>Or you can use an array of offset, length pairs.<BR>"extents" perhaps this is called.<BR>You would sort this by offset, and again use binary search.<BR>This would tend to be more compact.<BR>
<BR>You could be adaptive.<BR>You could set some thresholds of size or density at which you would switch<BR>the representation from one to the other.<BR>Of course you if I am frequently adding/removing items to a set, you don't<BR>want to frequently change the representation.<BR>
<BR>I'm still pondering 64 bit integer support in the x86 back end.<BR>The basic dilemna is a stack of pairs or the existing stack of singletons where<BR>sometimes you'd use two stack items at a time. I'm leaning toward<BR>a stack of pairs.<BR>
<BR>After that we can discuss something like:<BR> FindFirstMemberInSet<BR> FindNextMemberInSet<BR>
and adding that to the language, etc.<BR>
<BR>FIRST and NEXT seem natural but I believe FIRST already means<BR>the first possible value, not the first present value.<BR>
<BR>On Windows, run link /dump /exports %windir%\system32\ntdll.dll | findstr /i bit.<BR>You'll see some of this stuff and more.<BR>
<BR> - Jay<BR><BR><BR><BR><BR><BR>
<HR id=stopSpelling>
<BR>
> Date: Wed, 31 Oct 2007 23:09:11 +0100<BR>> From: lemming@henning-thielemann.de<BR>> Subject: Re: [M3devel] iterating over sets?<BR>> To: jay.krell@cornell.edu<BR>> CC: m3devel@elegosoft.com<BR>> <BR>> <BR>> On Wed, 31 Oct 2007, Jay wrote:<BR>> <BR>> > Let's say I had<BR>> ><BR>> > TYPE T = SET OF { 0 .. 256 };<BR>> ><BR>> > Must I say:<BR>> ><BR>> > VAR t: T;<BR>> > FOR i := FIRST(t) TO LAST(t)<BR>> > IF i IN t DO<BR>> > something with i<BR>> > END<BR>> > END<BR>> <BR>> You may speed up search by splitting the set into subsets.<BR>> <BR>> E.g.<BR>> <BR>> IF t * T{16..31} = T{} THEN<BR>> skip this block completely<BR>> ELSE<BR>> inspect that block in detail<BR>> END;<BR><BR><br /><hr />Climb to the top of the charts! Play Star Shuffle: the word scramble challenge with star power. <a href='http://club.live.com/star_shuffle.aspx?icid=starshuffle_wlmailtextlink_oct' target='_new'>Play Now!</a></body>
</html>