| Printable Version
Byteset In C#
By S. Lee Odegard
Here is a C# struct byteset that implements the Modula-3 type
SET OF BYTE. A set is a collection of
values taken from an ordinal type that has a manageable number of possible values;
which in this case are values of the range 0 to 255 inclusive. The set-valued
operators +(set union), -(set difference), *(set intersection), and /(symmetric set
difference), and the set-valued subset relations <= >=
< , and > are also implemented. The set membership relation
(e is-an-element-of b)
for a byte e and byteset b is mapped to the %
operator: e%b .
For an example, consider the output:
bs3= ( 0, 19, 38, 57, 76, 95, 114,
133, 152, 171, 190, 209, 228, 247 ) [14 items]
<= True bs6= ( 0, 38, 76, 114, 152, 190, 228 ) [7 items]
bs3-bs6 = ( 19, 57, 95, 133, 171, 209, 247 ) [7 items]
bs6 items: 0 38 76 114 152 190 228 sum to 798
This is produced by the following method that employs byteset:
class s{ public static string tout{ set{ Console.Write( value );}}}
class Class1
{
[STAThread]
static void Main(string[] args)
{
byteset bs3= byteset.Empty;
for( int i= 0; i<256; i+= 19 ){ bs3+= (byte)i;}
byteset bs6= byteset.Empty;
for( int i= 0; i<256; i+= 38 ){ bs6+= (byte)i;}
s.tout= "bs3= " + bs3.ToString() + " [" + bs3.GetModulus().ToString()
+ " items]\r\n <= " + (bs3<=bs6).ToString() + " bs6= "
+ bs6.ToString() + " [" + bs6.GetModulus().ToString()
+ " items]\r\n" ;
bs3-= bs6;
s.tout= "bs3-bs6 = " + bs3.ToString()
+ " [" + bs3.GetModulus().ToString() + " items]\r\n";
int result= 0;
s.tout= "bs6 items: ";
foreach( byte i in bs6 ){
result+= i;
s.tout= i.ToString() + " ";}
s.tout= " sum to " + result.ToString()+ "\r\n\r\n";
string ig= Console.ReadLine();//hold console open, then quit
}//Main
}//Class1
In the examples, s.tout may also be an accessor that appends
text to the main textbox in a Windows form. In that case, the final
Console.ReadLine() may be omitted. Similar code has been
employed to generate Modula-3 programs with assertion statements on random
sets to validate this C# implementation.
The following employs the byteset type to calculate the prime numbers <
255 as well as show some of the numbers sieved out in the process:
byteset bs1= byteset.FromRange( 2, 255 );
for( int i= 4; i<256; i+=2 ){//exclude even numbers except 2
bs1-= (byte)i;}
byteset bse;
byte[] sp= {3, 5, 7, 11, 13};
foreach( byte j in sp )
{
bse= bs1;
for( int i= j*j; i<256; i+=2*j ){
bs1-= (byte)i;}
if( j>5 )
{
bse-= bs1;
s.tout= "sieve " + j.ToString() + ": " + bse.ToString() + "\r\n";
s.tout= "delta ";
int delta= 0;
foreach( byte k in bse ){
s.tout= ( k-delta ).ToString() + " "; delta= k;}
s.tout= "\r\n\r\n";
}
}
s.tout= "primes < 255 are " + bs1.ToString() + "\r\n\r\n";
This has the output:
sieve 7: ( 49, 77, 91, 119, 133, 161, 203, 217 )
delta 49 28 14 28 14 28 42 14
sieve 11: ( 121, 143, 187, 209, 253 )
delta 121 22 44 22 44
sieve 13: ( 169, 221, 247 )
delta 169 52 26
primes < 255 are ( 2, 3, 5, 7, 11, 13, 17, 19,
23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67,
71, 73, 79, 83, 89, 97, 101, 103, 107, 109,
113, 127, 131, 137, 139, 149, 151, 157, 163,
167, 173, 179, 181, 191, 193, 197, 199, 211,
223, 227, 229, 233, 239, 241, 251 )
The byteset struc follows:
using System;
using System.Collections;
using System.Runtime.InteropServices;
/// <summary>
/// <p>A set representation that can contain up to 256 elements from 0..255</p>
/// <p>Comments? Questions? Bugs? Tell S. Lee Odegard, leeo@bossig.com</p>
/// <p>Version: May 1, 2002</p>
/// </summary>
[StructLayout(LayoutKind.Sequential)]
public struct byteset : ICloneable, IEnumerable
{
/// <summary>
/// byteset supports 256 elements in the range 0..255
/// </summary>
ulong bs0, bs1, bs2, bs3;
const byte mask = 0x3F;//2_00111111
#region constructors FromBytes, FromRange, byteset, Clone
/// <summary>
/// Create a byteset from bytes (unsigned short integer)
/// </summary>
/// <param name="item"></param>
static public byteset FromBytes( params byte[] i )
{
byteset b;
b.bs0= 0UL; b.bs1= 0UL; b.bs2= 0UL; b.bs3= 0UL;
foreach( byte j in i ){ switch( j>>6 )
{
case 0: b.bs0|= 1UL<<j;break;
case 1: b.bs1|= 1UL<<(j&mask);break;
case 2: b.bs2|= 1UL<<(j&mask);break;
case 3: b.bs3|= 1UL<<(j&mask);break;
}}
return b;
}
static private ulong drapeFromUintRange( byte from, byte to, byte max )
{
if( from > to || from > max ){ return 0UL;}
to= to > max? max: to;
return ( unchecked( (ulong)-1 )>>(63-to+from) )<<from;
#if design_code
res= 0UL;
for( int i= from; i<=to; i++){ res|= 1UL<<i;}
return res;
#endif
}
/// <summary>
/// Create a byteset that includes the items in the range from..to
/// </summary>
/// <param name="from"></param>
/// <param name="to"></param>
/// <returns></returns>
static public byteset FromRange( byte from, byte to )
{
byteset b= byteset.Empty;
// divide into sections: 0..63; 64..127; 128..191; 192..255;
// i.e. 60..150 -> 60..63, 64..127, 128..150
// 100..150 -> <64>100..127, 128..150<191>
// 200..250 -> <192>200..250<255>
if( from < 64 ){
b.bs0= drapeFromUintRange( from, to, 63);
from= 64;}
if( from < 128 ){
b.bs1= drapeFromUintRange( from, to, 127);
from= 128;}
if( from < 192 ){
b.bs2= drapeFromUintRange( from, to, 191);
from= 192;}
b.bs3= drapeFromUintRange( from, to, 255);
return b;
#if design_code
byteset b= byteset.Empty;
for( int i= from; i<=to; i++ ){ b+= (byte)i;}
return b;
#endif
}
/// <summary>
/// Create a byteset from array bytes (unsigned short integer)
/// </summary>
/// <param name="i"></param>
public byteset( params byte[] i )
{
this.bs0= 0UL; this.bs1= 0UL; this.bs2= 0UL; this.bs3= 0UL;
foreach( byte j in i ){ switch( j>>6 )
{
case 0: this.bs0|= 1UL<<j;break;
case 1: this.bs1|= 1UL<<(j&mask);break;
case 2: this.bs2|= 1UL<<(j&mask);break;
case 3: this.bs3|= 1UL<<(j&mask);break;
}}
}
/// <summary>
/// Create a byteset copying from an existing byteset
/// </summary>
/// <param name="b"></param>
public byteset( byteset b ){
this.bs0= b.bs0; this.bs1= b.bs1;
this.bs2= b.bs2; this.bs3= b.bs3;}
object ICloneable.Clone(){ return new byteset( this );}
public byteset Clone(){ return new byteset( this );}
#endregion
//---------------------------------------------------------------------------------
//---------------------------------------------------------------------------------
/// <summary>
/// Get byteset hash code
/// </summary>
/// <returns></returns>
public override int GetHashCode(){
return this.bs0.GetHashCode() ^ this.bs1.GetHashCode()
^ this.bs2.GetHashCode() ^ this.bs3.GetHashCode();}
private byte ulongmodulus( ulong x )
{
const ulong mask = 0xFUL;
byte result= (byte)0;
for( int i= 0; i < 16; i++ )
{
switch( x & mask )
{
case 0: break;
case 1: case 2: case 4: case 8: result+= (byte)1; break;
case 3: case 5: case 6:
case 9: case 10: case 12: result+= (byte)2; break;
case 7: case 11: case 13: case 14: result+= (byte)3; break;
case 15: result+= (byte)4; break;
}
x>>= 4;
}
return result;
}
/// <summary>
/// Get modulus (number of items) in byteset
/// </summary>
/// <returns></returns>
public byte GetModulus()
{
return (byte)(ulongmodulus( this.bs0 ) + ulongmodulus( this.bs1 )
+ ulongmodulus( this.bs2 ) + ulongmodulus( this.bs3 ));
#if design_code
byte res= (byte)0;
for( int i= 0; i<256; i++ ){ if( i % this ){ res+= 1;}}
return (byte)res;
#endif
}
#region byteset relations == != <= >= < >
/// <summary>
/// this byteset equivalent to another object?
/// </summary>
/// <param name="o"></param>
/// <returns></returns>
public override bool Equals( object o ){
if( o is byteset ){
byteset b= (byteset) o;
return this == b;}
return false;}
/// <summary>
/// Are these two bytesets equivalent?
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
/// <returns></returns>
public static bool operator==( byteset a, byteset b ){
return a.bs0 == b.bs0 && a.bs1 == b.bs1
&& a.bs2 == b.bs2 && a.bs3 == b.bs3;}
/// <summary>
/// Are these two bytesets different?
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
/// <returns></returns>
public static bool operator!=( byteset a, byteset b ){
return a.bs0 != b.bs0 || a.bs1 != b.bs1
|| a.bs2 != b.bs2 || a.bs3 != b.bs3;}
/// <summary>
/// subset: a<=b == every element of byteset a is also an element of byteset b
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
/// <returns></returns>
public static bool operator<=( byteset a, byteset b ){
return (~b.bs0 | a.bs0) != 0UL || (~b.bs1 | a.bs1) != 0UL
|| (~b.bs2 | a.bs2) != 0UL || (~b.bs3 | a.bs3) != 0UL;}
public static bool operator>=( byteset a, byteset b ){
return (~a.bs0 | b.bs0) != 0UL || (~a.bs1 | b.bs1) != 0UL
|| (~a.bs2 | b.bs2) != 0UL || (~a.bs3 | b.bs3) != 0UL;}
public static bool operator<( byteset a, byteset b ){
return (a<=b) && (a!=b);}
public static bool operator>( byteset a, byteset b ){
return (a>=b) && (a!=b);}
#endregion
#region byteset operators ~ % + - * /
/// <summary>
/// Set complement, e%(~b) == ~( e % b ); e in ~b == e not in b
/// </summary>
/// <param name="e"></param>
/// <param name="b"></param>
/// <returns></returns>
public static byteset operator~( byteset b ){
b.bs0 = ~b.bs0; b.bs1 = ~b.bs1; b.bs2= ~b.bs2; b.bs3= ~b.bs3;
return b;}
/// <summary>
/// Set membership, IN: e%b is true == byte e is an element of byteset b
/// </summary>
/// <param name="e"></param>
/// <param name="b"></param>
/// <returns></returns>
public static bool operator%( byte e, byteset b )
{ //element e is _in_ set b
switch( e>>6 )
{
case 0: return (1UL<<e & b.bs0) != 0UL;
case 1: return (1UL<<(e&mask) & b.bs1) != 0UL;
case 2: return (1UL<<(e&mask) & b.bs2) != 0UL;
case 3: return (1UL<<(e&mask) & b.bs3) != 0UL;
} return false;//placate warning about paths to return statement
}
/// <summary>
/// Set union: e%(x+y) == e%x or e%y
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
/// <returns></returns>
public static byteset operator+( byteset a, byteset b ){
a.bs0|= b.bs0; a.bs1|= b.bs1; a.bs2|= b.bs2; a.bs3|= b.bs3;
return a;}
/// <summary>
/// include in byteset a element e: useful for += assignment
/// </summary>
/// <param name="a"></param>
/// <param name="e"></param>
/// <returns></returns>
public static byteset operator+( byteset a, byte e )
{
switch( e>>6 )
{
case 0: a.bs0|= 1UL<<(e&mask);break;
case 1: a.bs1|= 1UL<<(e&mask);break;
case 2: a.bs2|= 1UL<<(e&mask);break;
case 3: a.bs3|= 1UL<<(e&mask);break;
}
return a;
}
/// <summary>
/// Set difference: e%(x-y) == e%x and not e%y
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
/// <returns></returns>
public static byteset operator-( byteset a, byteset b ){
a.bs0&= ~b.bs0; a.bs1&= ~b.bs1; a.bs2&= ~b.bs2; a.bs3&= ~b.bs3;
return a;}
/// <summary>
/// exclude from byteset a element e: useful for -= assignment
/// </summary>
/// <param name="a"></param>
/// <param name="e"></param>
/// <returns></returns>
public static byteset operator-( byteset a, byte e )
{
switch( e>>6 )
{
case 0: a.bs0&= ~(1UL<<(e&mask));break;
case 1: a.bs1&= ~(1UL<<(e&mask));break;
case 2: a.bs2&= ~(1UL<<(e&mask));break;
case 3: a.bs3&= ~(1UL<<(e&mask));break;
}
return a;
}
/// <summary>
/// Set intersection: e%(x*y) == e%x and e%y
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
/// <returns></returns>
public static byteset operator*( byteset a, byteset b ){
a.bs0&= b.bs0; a.bs1&= b.bs1; a.bs2&= b.bs2; a.bs3&= b.bs3;
return a;}
/// <summary>
/// Symmetric set difference: e%(x/y) == e%x != e%y
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
/// <returns></returns>
public static byteset operator/( byteset a, byteset b ){
a.bs0^= b.bs0; a.bs1^= b.bs1; a.bs2^= b.bs2; a.bs3^= b.bs3;
return a;}
#endregion
#region byteset string conversions Parse (unimplemented) and ToString
/// <summary>
/// Parse a byteset representation in this fashion: "( %b, %b, %b )"
/// </summary>
/// <param name="s"></param>
/// <returns></returns>
static public byteset Parse( string s ){
throw new NotImplementedException(
"byteset byteset.Parse( string s ) is not implemented." );}
/// <summary>
/// Get the string representation
/// </summary>
/// <returns></returns>
public override string ToString(){ return ToString( '(', ')' );}
public string ToString( char delimiterL, char delimiterR )
{
string output= delimiterL.ToString();
ulong bsa= 1UL;
bool h0= false;
for( int i= 0; i < 64; i++){
if( (this.bs0 & bsa)!=0){
output+= (h0? ", " : " ") + i.ToString();
h0= true;}
bsa <<= 1;}
bsa= 1UL;
for( int i= 0; i < 64; i++){
if( (this.bs1 & bsa)!=0){
output+= (h0? ", " : " ") + (i+64).ToString();
h0= true;}
bsa <<= 1;}
bsa= 1UL;
for( int i= 0; i < 64; i++){
if( (this.bs2 & bsa)!=0){
output+= (h0? ", " : " ") + (i+128).ToString();
h0= true;}
bsa <<= 1;}
bsa= 1UL;
for( int i= 0; i < 64; i++){
if( (this.bs3 & bsa)!=0){
output+= (h0? ", " : " ") + (i+192).ToString();
h0= true;}
bsa <<= 1;}
return output + " " + delimiterR.ToString() ;
}
public string ToStringCompact(){
return this.bs0.ToString( "X" ) + this.bs1.ToString( "X" )
+ this.bs2.ToString( "X" ) + this.bs3.ToString( "X" );}
#endregion
#region byteset static values Empty, Full and the equivalent MinValue, MaxValue
/// <summary>
/// Empty set
/// </summary>
static public byteset Empty{
get{
byteset b; b.bs0= 0; b.bs1= 0; b.bs2= 0; b.bs3= 0;
return b;
}}
/// <summary>
/// Full set
/// </summary>
static public byteset Full{
get{
const ulong ff= unchecked( (ulong)-1 );
byteset b;
b.bs0= ff; b.bs1= ff; b.bs2= ff; b.bs3= ff;
return b;}}
/// <summary>
/// Smallest possible byteset value or empty set
/// </summary>
static public byteset MinValue{ get{ return byteset.Empty;}}
/// <summary>
/// Largest possible byteset value or full set
/// </summary>
static public byteset MaxValue{ get{ return byteset.Full;}}
#endregion
//---------------------------------------------------------------------------------
//---------------------------------------------------------------------------------
public IEnumerator GetEnumerator(){ return new bytesetEnumerator( this );}
private class bytesetEnumerator : IEnumerator
{
private int position = -1;
private byteset b;
public bytesetEnumerator(byteset b){ this.b = b;}
public bool MoveNext(){
while( ++position < 256 && !((byte)(position)%b) ){};
return position < 256;}
public void Reset(){ position = -1;}
byte Current{ get{ return (byte)position;}}
object IEnumerator.Current{ get{ return (byte)position;}}
}
}
|
