import std.stdio, std.string;



// Basic set, 32 maximum values ( change to ulong for 64 values )
struct Set
{
  uint    value = 0;

  static Set opCall( uint v ) { Set r; r.value = v; return r; }
  static Set opCall( Set s ) { Set r; r.value = s.value; return r; }

  char[] toString(){ return std.string.format( "%b", value ); }

  Set  opOr( uint other ) { return Set( value | other ); }

  void opIndexAssign( bool on, int index )
  {
    uint mask = (1<<index);
    if ( on )  value = value | mask;
    else value = value & ( uint.max - ~mask );
    assert( opIndex( index ) == on );
  }

  bool opIndex( uint index ) {
    uint mask = (1<<index);
    return (value & mask) > 0;
  }

  // equivalence
  bool    opEquals( Set s ) { return value==s.value; }

  //union
  Set     opAdd( Set t )    { return Set( value | t.value ); }

  //difference
  Set     opSub( Set t )    { return Set( value & (~t.value) ); }

  // intersection
  Set     opXor( Set t )    { return Set( value & t.value ); }
  alias   opXor intersect ;

  // inverse
  Set     opCom()           { return Set( uint.max - value ); }
  Set     opNeg()           { return opCom(); }
  Set     dup()             { return Set( this.value ); }

  // version of opApply which calls delegate if the bit at (position) is set
  int     opApply( int  delegate( inout int position ) dg )
  {
    int r=0, mask = 1;
    for( int n=0; n<32; n++ )
    {
      if ( (value & mask)!=0 )
      {
        r = dg( n );
        if (r) break;
      }
      mask <<= 1 ;
    }
    return r;
  }

  // version of opApply which calls delegate with all bit positions and values
  int     opApply( int delegate( inout int position, inout bit is_set ) dg )
  {
    int r=0, mask = 1;
    for( int n=0; n<32; n++ ) {
      bool is_set = (value & mask)!=0;
      r = dg(n,is_set);
      if (r) break;
      mask = mask << 1 ;
    }
    return r;
  }
}



// Arbitrary sized Set
class   BitSet
{
  ubyte[]   data;
  uint      count = 0;
  short     min = 0, max  = 0;

  this( uint start, uint end )
  {
    assert( end >=start );
    min = start;
    max = end;
    count = end - start + 1;
    data.length = (count + 7) / 8;
    writefln("min=%s,max=%s,count=%s", min,max,count);
  }

  void  clear() { data[] = 0; }

  bool opIndex( int index )
  {
    index = index - min;
    assert( index >=0 );
    assert( index <=count );
    uint mask = (1<<(index&7));
    return (data[index>>3] & mask) > 0;
  }

  void opIndexAssign( bool on, uint index )
  {
    index = index - min;
    assert( index >=0 );
    assert( index <=count );
    uint mask = (1<<(index&7));
    if ( on ) data[index>>3] |= mask;
    else data[index>>3] &= ~mask;
  }

  void  opIndexAssign( bool on, int a, int b )
  {
    int st = a - min;
    int end = b - a + 1;
    assert( st >=0 );
    assert( end <=count );
    while( st < end )
    {
      opIndexAssign( on, st );
      st++;
    }
  }

  private void check( BitSet other )
  {
    if (( other.min != this.min )||
        ( other.max != this.max ) ) throw new Exception("Attempted operations on non matching BitSets!" );
  }


  // equivalence
  bool    opEquals( BitSet other )
  {
    check( other );
    return data[]==other.data[];
  }

  //union
  BitSet  opAdd( BitSet other )
  {
    check( other );
    BitSet result = new BitSet( this.min, this.max );
    foreach( int index, ubyte b; data ) result.data[index] = b | other.data[index];
    return result;
  }

  //difference
  BitSet    opSub( BitSet other )
  {
    BitSet result = new BitSet( this.min, this.max );
    foreach( int index, ubyte b; data ) result.data[index] = b & (~other.data[index]);
    return result;
  }

  // intersection
  BitSet     opXor( BitSet other ) { return this.intersect( other ); }
  BitSet     intersect( BitSet other )
  {
    BitSet result = new BitSet( this.min, this.max );
    foreach( int index, ubyte b; data ) result.data[index] = b & other.data[index];
    return result;
  }

  // inverse
  BitSet     opCom() { return inverse(); }
  BitSet    inverse()
  {
    BitSet result = new BitSet( this.min, this.max );
    foreach( int index, ubyte b; data ) result.data[index] = ~b;
    return result;
  }

  BitSet     dup()
  {
    BitSet result = new BitSet( this.min, this.max );
    result.data[] = this.data[];
    return result;
  }

}

template SetOf(T)
{
  BitSet    SetOf() { return new BitSet( T.min, T.max ); }
}





// Some tests


enum { Start, One, Two, Three };
static char[][] names = [ "Start", "One", "Two", "Three" ];

enum Fruit { Apple, Orange, Banana, Mango, Pineapple };


void main( char[][] args )
{
  Set set ;

  set[Start] = true;
  assert( set[Start] );
  set[One] = true;
  assert( set[Start] && set[One] );

  Set neg = ~set;
  assert( neg[Start]==false );
  assert( neg[One]==false );
  assert( neg[Two] );
  assert( neg[Three] );

  writefln("Set : %s", set.toString() );
  writefln("Neg : %s", neg.toString() );

  char[] name( int n ) { return ( n <= Three ) ? names[n] : ""; }

  writef("Set on:" ); foreach( int index; set ) writef("%s,", name(index) );
  writef("\nNeg Set:" ); foreach( int index; neg ) writef("%s,", name(index) );
  writefln();

  Set all = neg + set ;

  for( int n=Start; n<=Three; n++ ) if ( !all[n] ) throw new Exception("Missing");
  assert( all-neg == set );


  BitSet fruits = SetOf!(Fruit);
  fruits[Fruit.Orange] = true;
  fruits[Fruit.Apple] = true;

  if ( fruits[Fruit.Apple] ) writefln("Has apple" );

  BitSet other = ~fruits;
  if ( other[Fruit.Apple]==false ) writefln("Has no apple" );

  fruits.clear();
  fruits[Fruit.Apple,Fruit.Mango] = true;

  for( Fruit val = Fruit.min; val <= Fruit.max; val++ )
  {
    if ( fruits[val] ) writef("1" ); else writef("0");
  }
  writefln();
}