BitVectorUtil { public static void divide01(BitVector org, BitVector vec0, BitVector vec1){ if(org.size() == 0) return; if(org.size() == 1){ if(!org.isZero(0)) throw new IllegalArgumentException("invalid bv for trie"); vec0.append1(); return; } boolean zeroCounting = org.isZero(0); int n = org.size(); for(int i = 1; i < n; i++){ if(zeroCounting){ if(org.isZero(i)){ vec0.append1(); } else{ vec0.append0(); zeroCounting = false; } } else{ if(org.isZero(i)){ vec1.append0(); zeroCounting = true; } else{ vec1.append1(); } } } }  static void divide01(BitVector org, BitVector vec0, BitVector vec1); static void appendBitStrings(BitVector bv, String[] bs);  }
@Test public void test() throws Exception{ BytesSuccinctBitVector r = new BytesSuccinctBitVector(); r.append1(); r.append0(); r.append1(); r.append1(); r.append1(); r.append0(); r.append1(); r.append1(); r.append1(); r.append0(); r.append0(); r.append1(); r.append1(); r.append0(); r.append0(); r.append0(); r.append0(); r.append1(); r.append0(); r.append0(); r.append0(); BytesSuccinctBitVector r0 = new BytesSuccinctBitVector(); BytesSuccinctBitVector r1 = new BytesSuccinctBitVector(); r0.append0(); r1.append0(); BitVectorUtil.divide01(r, r0, r1); Assert.assertEquals("101110111001100001000", r.toString()); Assert.assertEquals("00010111011", r0.toString()); Assert.assertEquals("00110110100", r1.toString()); Assert.assertEquals(1, r1.select0(r0.rank0(0)) + 1); Assert.assertEquals(5, r1.select0(r0.rank0(2)) + 1); Assert.assertEquals(8, r1.select0(r0.rank0(4)) + 1); Assert.assertEquals(10, r1.select0(r0.rank0(8)) + 1); }