Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  package com.tectonica.util;
  
  import java.util.Arrays;

A memory-efficient data structure for storing a 3-dimensional bit array. The data is not compacted and the array is not assumed to be sparse. However, the implementation is based on a vector of long-primitives, stored consecutively in memory and taking the least amount possible of overhead footprint. The class assumes that the interesting data is stored in axis-Z, and therefore provides special APIs for this particular axis.

Author(s):
Zach Melamed
 
 public class BitCube
 {
 	private final static int ADDRESS_BITS_PER_WORD = 6;
 	private final static int BITS_PER_WORD = 1 << ;
 
 	private final long[] words;
 
 	private final int xAxisSize;
 	private final int yAxisSize;
 	private final int zAxisSize;
 	private final int zWordCount;
 	private final int yWordCount;
 
 	public BitCube(int xAxisSizeint yAxisSizeint zAxisSize)
 	{
 		this. = xAxisSize;
 		this. = yAxisSize;
 		this. = zAxisSize;
 		 = wordLocalIndex(zAxisSize - 1) + 1;
 		 = yAxisSize * ;
 		 = new long[xAxisSize * ];
 	}
 
 	private int wordLocalIndex(int bitIndex)
 	{
 		return bitIndex >> ;
 	}
 
 	private int wordIndex(int xint yint z)
 	{
 		return (x * ) + (y * ) + wordLocalIndex(z);
 	}
 
 	public long getBufferSize() // in bytes
 	{
 		return (1L * .) << ( - 3);
 	}
 
 	public int getXAxisSize()
 	{
 		return ;
 	}
 
 	public int getYAxisSize()
 	{
 		return ;
 	}
 
 	public int getZAxisSize()
 	{
 		return ;
 	}
 
 	private void checkDimensions(int xint yint z)
 	{
 		assert (x >= 0 && x < );
 		assert (y >= 0 && y < );
 		assert (z >= 0 && z < );
 	}
 
 	public boolean get(int xint yint z)
 	{
 		checkDimensions(xyz);
 		int i = wordIndex(xyz);
 		return ([i] & (1L << z)) != 0L;
 	}
 
 	public void set(int xint yint zboolean value)
 	{
 		checkDimensions(xyz);
 		long mask = 1L << z;
 		int i = wordIndex(xyz);
 		if (value)
 			[i] |= mask;
 		else
 			[i] &= ~mask;
 	}
 
 	public boolean getAndSet(int xint yint zboolean value)
 	{
 		checkDimensions(xyz);
 		long mask = 1L << z;
 		int i = wordIndex(xyz);
 		boolean wasSet = ([i] & mask) != 0L;
 		if (value)
 			[i] |= mask;
		else
			[i] &= ~mask;
		return wasSet;
	}
	public void setAxisX(int yint zboolean value)
	{
		checkDimensions(0, yz);
		long mask = 1L << z;
		for (int x = 0, i = wordIndex(xyz); x < x++, i += )
		{
			if (value)
				[i] |= mask;
			else
				[i] &= ~mask;
		}
	}
	public void setAxisY(int xint zboolean value)
	{
		checkDimensions(x, 0, z);
		long mask = 1L << z;
		for (int y = 0, i = wordIndex(xyz); y < y++, i += )
		{
			if (value)
				[i] |= mask;
			else
				[i] &= ~mask;
		}
	}
	public void setAxisZ(int xint yboolean value)
	{
		checkDimensions(xy, 0);
		int firstWordIndex = wordIndex(xy, 0);
		int lastWordIndex = firstWordIndex +  - 1;
		if ( > 1)
			Arrays.fill(firstWordIndexlastWordIndexvalue ? ~0L : 0L);
		[lastWordIndex] = value ? (~0L >>> -) : 0L;
	}
	public int nextSetBitZ(int xint yint z)
	{
		checkDimensions(xyz);
		return nextSetBit(zwordIndex(xy, 0));
	}
	private int nextSetBit(int bitIndexint baseWordIndex)
	{
		int u = wordLocalIndex(bitIndex);
		if (u == )
			return -1;
		long word = [baseWordIndex + u] & (~0L << bitIndex);
		while (true)
		{
			if (word != 0)
				return (u * ) + Long.numberOfTrailingZeros(word);
			if (++u == )
				return -1;
			word = [baseWordIndex + u];
		}
	}

Given X and Y, returns how bits in axis-Z are set
	public int getBitCountZ(int xint y)
	{
		checkDimensions(xy, 0);
		int index = wordIndex(xy, 0);
		int bitCount = 0;
		for (int i = indexi < index + i++)
			bitCount += Long.bitCount([i]);
		return bitCount;
	}
	public static interface SearchListener
	{
		void initialize(int size);
		void add(int index);
	}
	public void searchAxisZ(int xint ySearchListener listener)
	{
		listener.initialize(getBitCountZ(xy));
		int base = wordIndex(xy, 0);
		for (int i = nextSetBit(0, base); i >= 0; i = nextSetBit(i + 1, base))
			listener.add(i);
	}

Given X and Y, returns an array of indices in axis-Z where the bits are set
	public int[] getAxisZ(int xint y)
	{
		searchAxisZ(xylistener);
		return listener.result;
	}
	private static class BasicSearchListener implements SearchListener
	{
		int[] result;
		int counter;
		public void initialize(int size)
		{
			 = new int[size];
			 = 0;
		}
		public void add(int index)
		{
			[++] = index;
		}
	};
New to GrepCode? Check out our FAQ X