package jp.phdax.bitvector;

public class BitVector {
	
	private final int size;
	private final long[] bits;
	private int[] rankIdx;
	private int[] selectIdx;
	private int wholeRank1;
	private static final long MOD64MASK = 0b111111;
	
	BitVector(int size, long[] bits) {
		this.size = size;
		this.bits = bits;
		
		rankIdx = new int[bits.length];
		selectIdx = new int[bits.length];
		
		int sum=0;
		int decimal64 = 0;
		for(int i=0; i<bits.length; i++) {
			//rank用インデックス：各longのtrueビットの累積値を記録する
			rankIdx[i] = sum;
			sum += Long.bitCount(bits[i]);
			//select用インデックス：trueビットが累積で64の倍数を超えた位置を記録していく
			if(decimal64 * 64 < sum) {
				selectIdx[decimal64] = decimal64*64 + bitPos(bits[i], sum%64);
				decimal64++;
			}
		}
	}
	
	public boolean pos(int idx) {
		return ((bits[idx >>> 6] >>> (idx & MOD64MASK)) & 1) != 0;
	}
	
	public int rank1(int idx) {
		return 0;
	}
	
	public int rank0(int idx) {
		return 0;
	}

	public int select1(int rank) {
		return 0;
	}
	
	public int select0(int rank) {
		return 0;
	}
	
	private static final int bitPos(long bits, int num) {
		return 0;
	}
}

@@ -226,16 +226,66 @@
 111111;%0A
+%09private static final int MOD64MASK_I = 0b111111;%0A
 %09%0A%09BitVe
@@ -664,13 +664,11 @@
 al64
- * 64
+%3C%3C6
  %3C s
@@ -713,11 +713,11 @@
 al64
-*64
+%3C%3C6
  + b
@@ -738,11 +738,20 @@
  sum
-%2564
+&MOD64MASK_I
 );%0A%09
@@ -775,16 +775,36 @@
 %09%09%7D%0A%09%09%7D%0A
+%09%09wholeRank1 = sum;%0A
 %09%7D%0A%09%0A%09pu
@@ -932,99 +932,413 @@
 %7B%0A%09%09
-return 0;%0A%09%7D%0A%09%0A%09public int rank0(int idx) %7B%0A%09%09return 0;%0A%09%7D%0A%0A%09public int select1(int rank) %7B
+if(idx %3C 0) return 0;%0A%09%09if(size %3C= idx) return wholeRank1;%0A%09%09int mod = idx & MOD64MASK_I;%0A%09%09int rank = rankIdx%5Bidx %3E%3E%3E 6%5D;%0A%09%09rank += Long.bitCount(bits%5Bidx%5D & (-1 %3E%3E%3E (64-mod)));%0A%09%09return rank;%0A%09%7D%0A%09%0A%09public int rank0(int idx) %7B%0A%09%09if(idx %3C 0) return 0;%0A%09%09if(size %3C= idx) return size-wholeRank1;%0A%09%09return idx - rank1(idx) + 1;%0A%09%7D%0A%0A%09public int select1(int rank) %7B%0A%09%09if(rank %3C 0 %7C%7C size %3C= rank) return -1;%0A%09%09
 %0A%09%09r
@@ -1342,32 +1342,33 @@
 %09%09return 0;%0A%09%7D%0A%09
+%09
 %0A%09public int sel
@@ -1380,24 +1380,69 @@
 int rank) %7B%0A
+%09%09if(rank %3C 0 %7C%7C size %3C= rank) return -1;%0A%09%09%0A
 %09%09return 0;%0A

implement rank method