keyconverter.java

High performance DB query

/*
 * @(#)$Id: KeyConverter.java,v 1.2 2005/12/30 23:23:11 burkhart Exp $
 *
 * Copyright (c) 2001-2004 Regents of the University of California.
 * All rights reserved.
 *
 * This file is distributed under the terms in the attached BERKELEY-LICENSE
 * file. If you do not find these files, copies can be found by writing to:
 * Computer Science Division, Database Group, Universite of California,
 * 617 Soda Hall #1776, Berkeley, CA 94720-1776. Attention: Berkeley License
 *
 * Copyright (c) 2003-2004 Intel Corporation. All rights reserved.
 *
 * This file is distributed under the terms in the attached INTEL-LICENSE file.
 * If you do not find these files, copies can be found by writing to:
 * Intel Research Berkeley, 2150 Shattuck Avenue, Suite 1300,
 * Berkeley, CA, 94704.  Attention:  Intel License Inquiry.
 */


package pier.indexes.prefixhashtree;

import java.math.BigInteger;
import util.BitID;

/**
 * Class KeyConverter
 * 
 */
public final class KeyConverter {
	
	/**
	 * Method getKeyInBinary
	 * Used to convert a key, in byte[] form, into its binary form.
	 * A leading 'B' is added because the transformation to a BitID chops off leading zeros.
	 * (The 'B' is for binary, in case you were curious).
	 * 
	 * @param key - BitID to transform
	 * @return - byte[] of 1's and 0's with leading 'B'
	 */
	public static byte[] getKeyInBinary(byte[] key, int numBits) {
		
		if ((key.length*8) > numBits) {
			if ((key[0] == 0) && (key[1] < 0)) {
				byte[] newKey = new byte[key.length-1];
				System.arraycopy(key, 1, newKey, 0, newKey.length);
				key = newKey;
			} else {
				throw new PHTException("Key passed to getKeyInBinary has too many bits (" + 
						key.length + "," + numBits + ")!");
			}
		}
		
		byte[] returnKey = new byte[numBits + 1];
		returnKey[0] = 'B';
		
		int leadingZeros = 0;
		int numBitsInKey = key.length*8;
		
		while (leadingZeros  < (numBits - numBitsInKey)) { leadingZeros++; }
		for (int i = 1; i <= leadingZeros; i++) {
			returnKey[i] = 0;
		}

		for (int i = 0; i < key.length; i++) {
			for (int j = 7; j >= 0; j--) {
				returnKey[(8*i)+(7-j)+leadingZeros+1] = (byte) ((((int)key[i]) & ((int)Math.pow(2,j))) >> j);
			}
		}
		
		return returnKey;
	}
	
	/**
	 * Method printBitID
	 * Used to print out a key (specifically, a BitID) in a readable form, for debugging.
	 * 
	 * @param key
	 * @param binary
	 * @return
	 */
	public static String printBitID(BitID key) {
		if (key == null) { return ""; }
		byte[] theKey = key.bigIntegerValue().toByteArray();
		String returnString = "";
		for (int i = 0; i < theKey.length; i++) {
			returnString = returnString + "[" + theKey[i] + "]";
		}
		return returnString;
	}
	
	/**
	 * Method keyIsInRange
	 * Returns true if keyInQuestion falls between the two given range boundaries (inclusive).
	 * Because keyInQuestion is only a prefix, can't use regular comparisons.  Note that all BitIDs
	 * passed in must be in binary form already, or it won't work so well.
	 * 
	 * @param keyInQuestion
	 * @param leftRange
	 * @param rightRange
	 * @return
	 */
	public static boolean keyIsInRange(BitID keyInQuestion, BitID leftRange, BitID rightRange) {
		byte[] leftBits = leftRange.bigIntegerValue().toByteArray();
		byte[] rightBits = rightRange.bigIntegerValue().toByteArray();
		byte[] keyBits = keyInQuestion.bigIntegerValue().toByteArray();
	
		for (int i = 0; i < keyBits.length; i++) {
			if (leftBits[i] < keyBits[i]) {
				break;
			} else if (leftBits[i] > keyBits[i]) {
				return false;
			}
		}
		for (int j = 0; j < keyBits.length; j++) {
			if (rightBits[j] > keyBits[j]) {
				break;
			} else if (rightBits[j] < keyBits[j]) {
				return false;
			}
		}
		
		return true;
	}
}