glbitarray.h

00001 #ifndef GRINLIZ_BITARRAY_INCLUDED
00002 #define GRINLIZ_BITARRAY_INCLUDED
00003 
00004 
00005 #include "gltypes.h"
00006 
00007 namespace grinliz {
00008 
00014 template< int WIDTH, int HEIGHT >
00015 class BitArray
00016 {
00017   public:
00018         enum {
00019                 ROW_WIDTH  = ( ( WIDTH+31 ) / 32 ),     
00020                 WORDSIZE = ROW_WIDTH * HEIGHT,
00021         };
00022 
00023         BitArray()                                      { memset( array, 0, WORDSIZE*4 ); cache = 0; }  
00024 
00026         U32 IsSet( int x, int y ) const { 
00027                 GLASSERT( x >= 0 && x < WIDTH );
00028                 GLASSERT( y >= 0 && y < HEIGHT );
00029                 return array[ y*ROW_WIDTH + (x>>5) ] & ( 0x1 << (x & 31)); 
00030         }
00032         void Set( int x, int y )        { 
00033                 GLASSERT( x >= 0 && x < WIDTH );
00034                 GLASSERT( y >= 0 && y < HEIGHT );
00035                 array[ y*ROW_WIDTH + (x>>5) ] |=   ( 0x1 << ( x & 31 ) ); 
00036         }
00038         void Clear( int x, int y )      { 
00039                 GLASSERT( x >= 0 && x < WIDTH );
00040                 GLASSERT( y >= 0 && y < HEIGHT );       
00041                 array[ y*ROW_WIDTH + (x>>5) ] &= (~( 0x1 << ( x & 31 ) ) ); 
00042         }
00044         void ClearRect( const Rectangle2I& rect )       {
00045                                                                                                         // FIXME: use a mask to make this more efficient.
00046                                                                                                         for( int j=rect.min.y; j<=rect.max.y; ++j )
00047                                                                                                                 for( int i=rect.min.x; i<=rect.max.x; ++i )
00048                                                                                                                         Clear( i, j );
00049                                                                                                 }
00051         void SetRect( const Rectangle2I& rect ) {
00052                                                                                                         // FIXME: use a mask to make this more efficient.
00053                                                                                                         for( int j=rect.min.y; j<=rect.max.y; ++j )
00054                                                                                                                 for( int i=rect.min.x; i<=rect.max.x; ++i )
00055                                                                                                                         Set( i, j );
00056                                                                                                 }
00058         bool IsRectEmpty( const Rectangle2I& rect ) const {
00059                                                                                                         // FIXME: use a mask to make this more efficient.
00060                                                                                                         for( int j=rect.min.y; j<=rect.max.y; ++j )
00061                                                                                                                 for( int i=rect.min.x; i<=rect.max.x; ++i )
00062                                                                                                                         if ( IsSet( i, j ) )
00063                                                                                                                                 return false;
00064                                                                                                         return true;
00065                                                                                                 }
00066 
00068         bool IsRectSet( const Rectangle2I& rect ) const {
00069                                                                                                         // FIXME: use a mask to make this more efficient.
00070                                                                                                         for( int j=rect.min.y; j<=rect.max.y; ++j )
00071                                                                                                                 for( int i=rect.min.x; i<=rect.max.x; ++i )
00072                                                                                                                         if ( !IsSet( i, j ) )
00073                                                                                                                                 return false;
00074                                                                                                         return true;
00075                                                                                                 }
00077         void ClearAll()                         { memset( array, 0, WORDSIZE*4 ); }
00079         void SetAll()                           { memset( array, 0xff, WORDSIZE*4 ); }
00080 
00082         void CacheY( int y )            { cache = &array[ROW_WIDTH*y]; }
00084         U32 IsSetCache( int x )         { return cache[ x>>5 ] & ( 0x1 << (x & 31)); }
00085 
00086         // Private. (But friend iterators are no fun.)
00087         U32 array[ WORDSIZE ];
00088         U32* cache;
00089 };
00090 
00094 template< int WIDTH, int HEIGHT >
00095 class BitArrayRowIterator
00096 {
00097   public:
00098         BitArrayRowIterator( const BitArray<WIDTH, HEIGHT>& _array ) : bitArray( _array ), mask( 0 ), loc( 0 )  {}
00099 
00101         void Begin( int x, int y)       {       loc = &bitArray.array[ y*bitArray.ROW_WIDTH + (x/32) ];
00102                                                                         U32 bit = x & 31;
00103                                                                         mask = 0x01 << bit;
00104                                                                 }
00106         void Next()                                     {       mask <<= 1;
00107                                                                         if ( !mask ) {
00108                                                                                 mask = 0x01;
00109                                                                                 ++loc;
00110                                                                         }
00111                                                                 }
00113         U32 IsSet()                                     {       return ( *loc ) & ( mask ); }
00115         bool WordEmpty()                        {       return !(*loc); }
00116 
00117   private:
00118         const BitArray<WIDTH, HEIGHT>& bitArray;
00119         U32 mask;
00120         const U32 *loc;
00121 };
00122 };
00123 #endif
00124 

Generated on Thu Jul 20 20:45:31 2006 for Kyra by  doxygen 1.4.7