public double estimateFractionForKey(ByteKey key) {
    checkNotNull(key, "key");
    checkArgument(!key.isEmpty(), "Cannot compute fraction for an empty key");
    checkArgument(
        key.compareTo(startKey) >= 0, "Expected key %s >= range start key %s", key, startKey);

    if (key.equals(endKey)) {
      return 1.0;
    }
    checkArgument(containsKey(key), "Cannot compute fraction for %s outside this %s", key, this);

    byte[] startBytes = startKey.getBytes();
    byte[] endBytes = endKey.getBytes();
    byte[] keyBytes = key.getBytes();
    // If the endKey is unspecified, add a leading 1 byte to it and a leading 0 byte to all other
    // keys, to get a concrete least upper bound for the desired range.
    if (endKey.isEmpty()) {
      startBytes = addHeadByte(startBytes, (byte) 0);
      endBytes = addHeadByte(endBytes, (byte) 1);
      keyBytes = addHeadByte(keyBytes, (byte) 0);
    }

    // Pad to the longest of all 3 keys.
    int paddedKeyLength = Math.max(Math.max(startBytes.length, endBytes.length), keyBytes.length);
    BigInteger rangeStartInt = paddedPositiveInt(startBytes, paddedKeyLength);
    BigInteger rangeEndInt = paddedPositiveInt(endBytes, paddedKeyLength);
    BigInteger keyInt = paddedPositiveInt(keyBytes, paddedKeyLength);

    // Keys are equal subject to padding by 0.
    BigInteger range = rangeEndInt.subtract(rangeStartInt);
    if (range.equals(BigInteger.ZERO)) {
      LOG.warn(
          "Using 0.0 as the default fraction for this near-empty range {} where start and end keys"
              + " differ only by trailing zeros.",
          this);
      return 0.0;
    }

    // Compute the progress (key-start)/(end-start) scaling by 2^64, dividing (which rounds),
    // and then scaling down after the division. This gives ample precision when converted to
    // double.
    BigInteger progressScaled = keyInt.subtract(rangeStartInt).shiftLeft(64);
    return progressScaled.divide(range).doubleValue() / Math.pow(2, 64);
  }
@Test
  public void testEstimateFractionForKey() {
    final double delta = 0.0000001;

    /* 0x80 is halfway between [] and [] */
    assertEquals(0.5, ByteKeyRange.ALL_KEYS.estimateFractionForKey(ByteKey.of(0x80)), delta);

    /* 0x80 is halfway between [00] and [] */
    ByteKeyRange after0 = ByteKeyRange.of(ByteKey.of(0), ByteKey.EMPTY);
    assertEquals(0.5, after0.estimateFractionForKey(ByteKey.of(0x80)), delta);

    /* 0x80 is halfway between [0000] and [] */
    ByteKeyRange after00 = ByteKeyRange.of(ByteKey.of(0, 0), ByteKey.EMPTY);
    assertEquals(0.5, after00.estimateFractionForKey(ByteKey.of(0x80)), delta);

    /* 0x7f is halfway between [] and [fe] */
    ByteKeyRange upToFE = ByteKeyRange.of(ByteKey.EMPTY, ByteKey.of(0xfe));
    assertEquals(0.5, upToFE.estimateFractionForKey(ByteKey.of(0x7f)), delta);

    /* 0x40 is one-quarter of the way between [] and [] */
    assertEquals(0.25, ByteKeyRange.ALL_KEYS.estimateFractionForKey(ByteKey.of(0x40)), delta);

    /* 0x40 is one-half of the way between [] and [0x80] */
    ByteKeyRange upTo80 = ByteKeyRange.of(ByteKey.EMPTY, ByteKey.of(0x80));
    assertEquals(0.50, upTo80.estimateFractionForKey(ByteKey.of(0x40)), delta);

    /* 0x40 is one-half of the way between [0x30] and [0x50] */
    ByteKeyRange range30to50 = ByteKeyRange.of(ByteKey.of(0x30), ByteKey.of(0x50));
    assertEquals(0.50, range30to50.estimateFractionForKey(ByteKey.of(0x40)), delta);

    /* 0x40 is one-half of the way between [0x30, 0, 1] and [0x4f, 0xff, 0xff, 0, 0] */
    ByteKeyRange range31to4f =
        ByteKeyRange.of(ByteKey.of(0x30, 0, 1), ByteKey.of(0x4f, 0xff, 0xff, 0, 0));
    assertEquals(0.50, range31to4f.estimateFractionForKey(ByteKey.of(0x40)), delta);

    /* Exact fractions from 0 to 47 for a prime range. */
    ByteKeyRange upTo47 = ByteKeyRange.of(ByteKey.EMPTY, ByteKey.of(47));
    for (int i = 0; i <= 47; ++i) {
      assertEquals("i=" + i, i / 47.0, upTo47.estimateFractionForKey(ByteKey.of(i)), delta);
    }

    /* Exact fractions from 0 to 83 for a prime range. */
    ByteKeyRange rangeFDECtoFDEC83 =
        ByteKeyRange.of(ByteKey.of(0xfd, 0xec), ByteKey.of(0xfd, 0xec, 83));
    for (int i = 0; i <= 83; ++i) {
      assertEquals(
          "i=" + i,
          i / 83.0,
          rangeFDECtoFDEC83.estimateFractionForKey(ByteKey.of(0xfd, 0xec, i)),
          delta);
    }
  }