package jsat.utils;

import java.util.Arrays;

/**
 * This class provides some useful methods and utilities for implementing Closed
 * Hashing structures
 * 
 * @author Edward Raff
 */
public class ClosedHashingUtil
{
    /**
     * Applying this bitwise AND mask to a long will give the bits corresponding
     * to an integer. 
     */
    public static final int INT_MASK = -1;
    /**
     * This value indicates that that status of an open addressing space is 
     * EMPTY, meaning any value can be stored in it
     */
    public static final byte EMPTY = 0;
    /**
     * This value indicates that the status of an open addressing space is 
     * OCCUPIED, meaning it is in use. 
     */
    public static final byte OCCUPIED = EMPTY + 1;
    /**
     * This value indicates that the status of an open addressing space is 
     * DELETED, meaning i should not stop a search for a value - but the code
     * is free to overwrite the values at this location and change the status 
     * to {@link #OCCUPIED}. 
* This can not be set to {@link #EMPTY} unless we can guarantee that no * value is stored in a index chain that stops at this location. */ public static final byte DELETED = OCCUPIED + 1; /** * This store the value {@link Integer#MIN_VALUE} in the upper 32 bits of a * long, so that the lower 32 bits can store any regular integer. This * allows a fast way to return 2 integers from one method in the form of a * long. The two values can then be recovered from the upper and lower 32 * bits of the long. This is meant to be used as a nonsense default value, * indicating that no information is present in the upper 32 bits. */ public static final long EXTRA_INDEX_INFO = ((long) Integer.MIN_VALUE) << 32; /** * Gets the next twin prime that is near a power of 2 and greater than or * equal to the given value * * @param m the integer to get a twine prime larger than * @return the a twin prime greater than or equal to */ public static int getNextPow2TwinPrime(int m) { int pos = Arrays.binarySearch(twinPrimesP2, m+1); if(pos >= 0) return twinPrimesP2[pos]; else return twinPrimesP2[-pos - 1]; } /** * This array lits twin primes that are just larger than a power of 2. The * prime in the list will be the larger of the twins, so the smaller can be * obtained by subtracting 2 from the value stored. The list is stored in * sorted order.
* Note, the last value stored is just under 231, where the other * values are just over 2x for x < 31 * */ public static final int[] twinPrimesP2 = { 7, //2^2 , twin with 5 13, //2^3 , twin with 11 19, //2^4 , twin with 17 43, //2^5 , twin with 41 73, //2^6 , twin with 71 139, //2^7 , twin with 137 271, //2^8 , twin with 269 523, //2^9 , twin with 632 1033, //2^10 , twin with 1031 2083, //2^11 , twin with 2081 4129, //2^12 , twin with 4127 8221, //2^13 , twin with 8219 16453, //2^14 , twin with 16451 32803, //2^15 , twin with 32801 65539, //2^16 , twin with 65537 131113, //2^17 , twin with 131111 262153, //2^18 , twin with 262151 524353, //2^19 , twin with 524351 1048891, //2^20 , twin with 1048889 2097259, //2^21 , twin with 2097257 4194583, //2^22 , twin with 4194581 8388619, //2^23 , twin with 8388617 16777291, //2^24 , twin with 16777289 33554503, //2^25 , twin with 33554501 67109323, //2^26 , twin with 67109321 134217781, //2^27 , twin with 134217779 268435579, //2^28 , twin with 268435577 536871019, //2^29 , twin with 536871017 1073741833, //2^30 , twin with 1073741831 2147482951, //first twin under 2^31, twin with 2147482949 }; }

Ads help maintain this website.