@Test public void testRangeDecomposition () { testRange(0, 15, p(0, 15)); testRange(1, 15, p(1, 1), p(2, 3), p(4, 7), p(8, 15)); testRange(16, 16, p(16, 16)); testRange(16, 17, p(16, 17)); testRange(16, 18, p(16, 17), p(18, 18)); testRange(16, 30, p(16, 23), p(24, 27), p(28, 29), p(30, 30)); testRange(22, 84, p(22, 23), p(24, 31), p(32, 63), p(64, 79), p(80, 83), p(84, 84)); testRange(5, 5, p(5, 5)); for (int start=0; start<128; ++start) { for (int end=start; end<128; ++end) { List<Pair<Integer, Integer>> rangeElts = HBaseSlicedPyramidIO.decomposeRange(start, end); Assert.assertTrue(rangeElts.size() > 0); int duplicateSizes = 0; int lastSize = 0; int lastEnd = start-1; for (Pair<Integer, Integer> elt: rangeElts) { int size = elt.getSecond() - elt.getFirst() + 1; Assert.assertTrue(size > 0); Assert.assertTrue(0 == (elt.getFirst() % size)); if (lastSize == size) ++ duplicateSizes; lastSize = size; Assert.assertEquals(lastEnd+1, elt.getFirst()+0); lastEnd = elt.getSecond(); } Assert.assertEquals(end, lastEnd); Assert.assertTrue(duplicateSizes <= 1); } } }
public static List<Pair<Integer, Integer>> decomposeRange (int start, int end) { if (start > end) return decomposeRange(end, start); int differences = start ^ (end+1); int msb = 1; while ((msb << 1) <= differences) msb = msb << 1; int midPoint = start - (start % msb) + msb; int[] startRanges = numberToBits(midPoint - start);; int[] endRanges = numberToBits(end + 1 - midPoint); List<Pair<Integer, Integer>> ranges = new ArrayList<>(); int curRangeMin = start; for (int i=0; i<startRanges.length; ++i) { if (1 == startRanges[i]) { int curRangeSize = 1 << i; ranges.add(new Pair<Integer, Integer>(curRangeMin, curRangeMin+curRangeSize-1)); curRangeMin += curRangeSize; } } for (int i=endRanges.length-1; i>=0; --i) { if (1 == endRanges[i]) { int curRangeSize = 1 << i; ranges.add(new Pair<Integer, Integer>(curRangeMin, curRangeMin+curRangeSize-1)); curRangeMin += curRangeSize; } } return ranges; }
HBaseSlicedPyramidIO extends HBasePyramidIO { public static List<Pair<Integer, Integer>> decomposeRange (int start, int end) { if (start > end) return decomposeRange(end, start); int differences = start ^ (end+1); int msb = 1; while ((msb << 1) <= differences) msb = msb << 1; int midPoint = start - (start % msb) + msb; int[] startRanges = numberToBits(midPoint - start);; int[] endRanges = numberToBits(end + 1 - midPoint); List<Pair<Integer, Integer>> ranges = new ArrayList<>(); int curRangeMin = start; for (int i=0; i<startRanges.length; ++i) { if (1 == startRanges[i]) { int curRangeSize = 1 << i; ranges.add(new Pair<Integer, Integer>(curRangeMin, curRangeMin+curRangeSize-1)); curRangeMin += curRangeSize; } } for (int i=endRanges.length-1; i>=0; --i) { if (1 == endRanges[i]) { int curRangeSize = 1 << i; ranges.add(new Pair<Integer, Integer>(curRangeMin, curRangeMin+curRangeSize-1)); curRangeMin += curRangeSize; } } return ranges; } }
HBaseSlicedPyramidIO extends HBasePyramidIO { public static List<Pair<Integer, Integer>> decomposeRange (int start, int end) { if (start > end) return decomposeRange(end, start); int differences = start ^ (end+1); int msb = 1; while ((msb << 1) <= differences) msb = msb << 1; int midPoint = start - (start % msb) + msb; int[] startRanges = numberToBits(midPoint - start);; int[] endRanges = numberToBits(end + 1 - midPoint); List<Pair<Integer, Integer>> ranges = new ArrayList<>(); int curRangeMin = start; for (int i=0; i<startRanges.length; ++i) { if (1 == startRanges[i]) { int curRangeSize = 1 << i; ranges.add(new Pair<Integer, Integer>(curRangeMin, curRangeMin+curRangeSize-1)); curRangeMin += curRangeSize; } } for (int i=endRanges.length-1; i>=0; --i) { if (1 == endRanges[i]) { int curRangeSize = 1 << i; ranges.add(new Pair<Integer, Integer>(curRangeMin, curRangeMin+curRangeSize-1)); curRangeMin += curRangeSize; } } return ranges; } HBaseSlicedPyramidIO(String zookeeperQuorum, String zookeeperPort, String hbaseMaster); }
HBaseSlicedPyramidIO extends HBasePyramidIO { public static List<Pair<Integer, Integer>> decomposeRange (int start, int end) { if (start > end) return decomposeRange(end, start); int differences = start ^ (end+1); int msb = 1; while ((msb << 1) <= differences) msb = msb << 1; int midPoint = start - (start % msb) + msb; int[] startRanges = numberToBits(midPoint - start);; int[] endRanges = numberToBits(end + 1 - midPoint); List<Pair<Integer, Integer>> ranges = new ArrayList<>(); int curRangeMin = start; for (int i=0; i<startRanges.length; ++i) { if (1 == startRanges[i]) { int curRangeSize = 1 << i; ranges.add(new Pair<Integer, Integer>(curRangeMin, curRangeMin+curRangeSize-1)); curRangeMin += curRangeSize; } } for (int i=endRanges.length-1; i>=0; --i) { if (1 == endRanges[i]) { int curRangeSize = 1 << i; ranges.add(new Pair<Integer, Integer>(curRangeMin, curRangeMin+curRangeSize-1)); curRangeMin += curRangeSize; } } return ranges; } HBaseSlicedPyramidIO(String zookeeperQuorum, String zookeeperPort, String hbaseMaster); @Override HBaseTilePutter getPutter(); void setPyramidding(boolean doPyramidding); static HBaseColumn getSliceColumn(int minSlice, int maxSlice); @Override List<TileData<T>> readTiles(String tableName,
											TileSerializer<T> serializer,
											Iterable<TileIndex> tiles); static List<Pair<Integer, Integer>> decomposeRange(int start, int end); }
HBaseSlicedPyramidIO extends HBasePyramidIO { public static List<Pair<Integer, Integer>> decomposeRange (int start, int end) { if (start > end) return decomposeRange(end, start); int differences = start ^ (end+1); int msb = 1; while ((msb << 1) <= differences) msb = msb << 1; int midPoint = start - (start % msb) + msb; int[] startRanges = numberToBits(midPoint - start);; int[] endRanges = numberToBits(end + 1 - midPoint); List<Pair<Integer, Integer>> ranges = new ArrayList<>(); int curRangeMin = start; for (int i=0; i<startRanges.length; ++i) { if (1 == startRanges[i]) { int curRangeSize = 1 << i; ranges.add(new Pair<Integer, Integer>(curRangeMin, curRangeMin+curRangeSize-1)); curRangeMin += curRangeSize; } } for (int i=endRanges.length-1; i>=0; --i) { if (1 == endRanges[i]) { int curRangeSize = 1 << i; ranges.add(new Pair<Integer, Integer>(curRangeMin, curRangeMin+curRangeSize-1)); curRangeMin += curRangeSize; } } return ranges; } HBaseSlicedPyramidIO(String zookeeperQuorum, String zookeeperPort, String hbaseMaster); @Override HBaseTilePutter getPutter(); void setPyramidding(boolean doPyramidding); static HBaseColumn getSliceColumn(int minSlice, int maxSlice); @Override List<TileData<T>> readTiles(String tableName,
											TileSerializer<T> serializer,
											Iterable<TileIndex> tiles); static List<Pair<Integer, Integer>> decomposeRange(int start, int end);  }