Multidimensional Packed Bit Array

[Thomas Bruckner]

Hello,

I've looked online for an implementation of a multidimensional packed
bit array (like BitArray but with more than one dimension), and could
not find any, so I'm trying to create my own. However with limited
success sofar. I'm having troubles with calculating the required size of
the storage and also with the bit shifts... my brain is turning in
circles trying to figure this out ;-)

Anyone want to help with this?

Thomas Bruckner
using System;
using System.Collections.Generic;
using System.Text;

namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
// new array 4 dimensions each with 2, 2, 4 and 4 elements
MultiBitArray mba = new MultiBitArray(new int[] { 2, 2, 4,
4 });

for (int i = 0; i <= 3; i++)
{
for (int j = 0; j <= 3; j++)
{
for (int k = 0; k < 15; k++)
{
for (int l = 0; l < 15; l++)
{
int[] coord = new int[] { i, j, k, l};

// make sure it is initially false

System.Diagnostics.Debug.Assert(mba.GetValue(coord ) == false);

// set to true, and check
mba.SetValue(coord, true);

System.Diagnostics.Debug.Assert(mba.GetValue(coord ) == true);

Console.WriteLine(
mba.GetLocation(coord).ToString());
}
}
}
}

Console.ReadKey();
}
}

public class MultiBitArray
{
/// <summary>
/// Number of dimensions.
/// </summary>
private int dimCount;

/// <summary>
/// bite size of each dimension (may be different)
/// </summary>
private int[] bitSize;

/// <summary>
/// storage for bits
/// </summary>
internal byte[] storage;

public MultiBitArray(int[] bitSize)
{
this.dimCount = bitSize.Length;
this.bitSize = bitSize;

AllocStorage();
}

/// <summary>
/// Allocates storage space for bits.
/// </summary>
private void AllocStorage()
{
long storageSize = 1;

for (int i = 0; i < this.dimCount; i++)
{
storageSize *= (this.bitSize[i] * dimCount);
}

// i can't even figure out how to determine the
// amount of memory... so I set it very large for testing
//storageSize *= 4;

this.storage = new byte[storageSize];
}

/// <summary>
/// Gets the location of a bit according to dimension indexes
/// </summary>
internal int GetLocation(int[] coord)
{
int location = 0;
int bitcount = 0;

for (int i = 0; i < dimCount; i++)
{
location = (location << bitcount) | coord[i];
bitcount = this.bitSize[i];
}

return location;
}

/// <summary>
/// Read a bit.
/// </summary>
public bool GetValue(int[] coord)
{
int location = GetLocation(coord);
return (this.storage[location / 8] & (byte)(1 << (location
% 8))) != 0;
}

/// <summary>
/// Set a bit.
/// </summary>
public void SetValue(int[] coord, bool value)
{
int location = GetLocation(coord);
this.storage[location / 8] |= (byte)(1 << (location % 8));
}
}
}

[=?ISO-8859-1?Q?Arne_Vajh=F8j?=]

Thomas Bruckner wrote:

I've looked online for an implementation of a multidimensional packed
bit array (like BitArray but with more than one dimension), and could
not find any, so I'm trying to create my own.

What feature do you need that an array of BitArray does not provide ?

Arne

[Bill Butler]

<ch*******@gmail.comwrote in message
news:a4**********************************@v32g2000 hsa.googlegroups.com...
<snip>

>he wanted to know the size, so if I use [2,2]=4bits, [3,3,3]=27bits
[3,3,4]=36 bits then

Correct, that is how you determine the storage in bits (as Colin said)

>thus

[2,2] 2*3+2 = 8
[3,3,3] 3*9+3*2+3=36
[3,3,4] 3*9+3*2+4=37

is mathemagical to me..

That is because x*9+y*3+z is the way to calculate the index into the
storage.

If you have [3,3,3] =size 27
this means that
x={0,1,2}
y={0,1,2}
z={0,1,2}

if you plug each possible combination of x,y,z into the equation you
will get an index that varies from 0 thru 26 (one less than the size of
the storage)
[2,2] 1*2 + 1 = 3 = 4-1
[3,3,3] 2*9+2*3+2 = 26 = 27-1
[3,3,4] 2*12+2*4+3=35 = 36 - 1

or more generally

[a,b,c] == b*c*x + c*y + z

and plugging in the max values we get
b*c*(a-1) + c*(b-1) + (c-1) =
b*c*a - b*c + b*c - c + c - 1 = a*b*c - 1

Hopefully I cleared things up a bit (probably just muddied them worse)

Bill

[christery]

But u are probably correct...

>

//CY- Dölj citerad text -

- Visa citerad text -

So I was trying for the size, and you for the position of the bit in
the array...
think Arne has the right solution an array of arrays...

Think I can follow (draw) your thoughts on 2,2 and 3,3,3 but lost at
(drawing) 4,4,4 ;)

No, dont answer that,,, just silly talk

//CY