package algs.blog.searching.tests;
import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
import java.io.ObjectOutputStream;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.LinkedList;


/**
 * Use reflection to generate specific information about the storage of objects
 * by the JDK hashtable. This only works for Hashtable<String,Boolean> whose 
 * values are all the same object (in this case Boolean.TRUE). Reason? Since the Java
 * serializable code does a good job in caching objects which are written, and we take
 * advantage of this fact.
 * <p>
 * 
 * @author George Heineman
 */
public class HashtableReport {
	
	/** Computed bins. */
	public final LinkedList<String>[] bins;
	
	/** Empty bins (as comma-separated string). */
	public final String emptyBins;
	
	/** Number empty. */
	public final int numEmpty;
	
	/** Size of the table. */
	public final int tableSize;
	
	/** Number of elements in hashtable. */
	public final int elements;
	
	/** Load factor. */
	public final float loadFactor;
	
	/** Threshold at which to rehash and grow. */
	public final int threshold;
	
	/** Only generated by this class. Computes relevant information. */
	private HashtableReport(LinkedList<String>[] bins, int tableSize, int elements, float loadFactor, int threshold) {
		this.bins = bins;
		this.tableSize = tableSize;
		this.elements = elements;
		this.loadFactor = loadFactor;
		this.threshold = threshold;
		
		StringBuilder str = new StringBuilder();
		int empty = 0;
		for (int i = 0; i < bins.length; i++) {
			LinkedList<String> list = bins[i];
			if (list == null) {
				str.append (i).append(",");
				empty++;
			} else {
				
			}
		}
		
		emptyBins = str.toString();
		numEmpty = empty; 
	}
	
	/** Return single line of output. */
	public String info() {
		// that's it
		StringBuilder sb = new StringBuilder("Report: size: " + tableSize + ", elements: " + elements + ", loadFactor: " + loadFactor + ", threshold: " + threshold);
		sb.append(", empty bins:" + numEmpty);
		
		int size = 0;
		int min = elements;
		int max = -1;
		for (int i = 0; i < tableSize; i++){ 
			LinkedList<String> list = bins[i];
			if (list != null) {
				int sz = list.size();
				size += sz;
				if (sz < min) { min = sz; }
				if (sz > max) { max = sz; }
			}
		}
		
		float avg = size;
		int base = (tableSize - numEmpty);
		if (base == 0) {
			sb.append(", average:0");
			sb.append(", minListSize:0");
			sb.append(", maxListSize:0");
		} else {
			avg /= base;
			sb.append(", average:" + avg);
			sb.append(", minListSize:" + min);
			sb.append(", maxListSize:" + max);
		}		
		
		return sb.toString();
	}
	
	public String toString() {
		// that's it
		StringBuilder sb = new StringBuilder("Report: size: " + tableSize + ", elements: " + elements + ", loadFactor: " + loadFactor + ", threshold: " + threshold);
		for (int i = 0; i < tableSize; i++){ 
			LinkedList<String> list = bins[i];
			if (list != null) {
				sb.append (i).append(",").append(list.size()).append(",");
				for (Iterator<String> it = list.iterator(); it.hasNext(); ) {
					sb.append(it.next());
					if (it.hasNext()) { sb.append (','); }
				}
				sb.append("\n");
			}
		}
		
		sb.append("empty bins:" + emptyBins);
		return sb.toString();
	}
	
	/**
	 * @deprecated  This code depends upon a specific writeObject layout for JDK 1.6
	 *    which may change at any moment.
	 *     
	 * @param table
	 * @throws Exception
	 */
	@SuppressWarnings("unchecked")
	@Deprecated
	public static HashtableReport report (Hashtable<String,Boolean> table) throws Exception {
		// serialize and parse according to JDK 1.6 spec code. Note: This may change
		// at any moment, so this code is intentionally deprecated. Access via 
		// Corresponding ByteArrayInputStream.
		ByteArrayOutputStream baoo = new ByteArrayOutputStream();
		ObjectOutputStream oos = new ObjectOutputStream(baoo);
		oos.writeObject(table);
 		oos.close();
		ByteArrayInputStream bais = new ByteArrayInputStream(baoo.toByteArray());
		
		// skip magic 4-byte header
		bais.skip(4);
		int bc;
		
		bc = bais.read(); assert (bc == 0x73);    // The hashtable object
		bc = bais.read(); assert (bc == 0x72);    // class description
		String s = readString(bais);              // fully qualified name of class
		assert (s.equals("java.lang.Hashtable")); // this is the one.
		long sid = readLong(bais);                // long value representing serializable Id for this class.
		assert (sid == 1421746759512286392L);      
		bais.skip(4);                             // Somehow specifies what comes next [3 0 2 70]
		s = readString(bais);                     // "loadFactor" string
		bc = bais.read(); assert (bc == 0x49);    // some separator byte...
		s = readString(bais);                     // "threshold" string
		bc = bais.read(); assert (bc == 0x78);    // end Block data
		bc = bais.read(); assert (bc == 0x70);    // null object reference
		
		float loadFactor = Float.intBitsToFloat(readInt(bais));
		int threshold = readInt(bais);
		bc = bais.read(); assert(bc == 0x77);     // TC_BLOCK data
		bc = bais.read(); assert(bc == 8);        // 8 bytes in this block data
		
		int tableSize = readInt(bais);            // Finally! The important ones
		int elements = readInt(bais);             // how many elements
		
		// re-create structure
		LinkedList<String>[] bins = new LinkedList[tableSize];
		
		
		for (int i = 0; i < elements; i++) {
			// get key
			bc = bais.read(); assert (bc == 0x74); // TC_STRING (for key)
			String key = readString(bais);
			
			
			// Only the FIRST entry must deal with type information for Boolean.
			if (i == 0) {
				bc = bais.read(); assert (bc == 0x73);  // OBJECT
				bc = bais.read(); assert (bc == 0x72);  // class description
				s = readString(bais); assert (s.equals ("java.lang.Boolean"));
				sid = readLong(bais);                   // long value representing serializable Id for this class.
				assert (sid == -3665804199014368530L);
				bc = bais.read(); assert (bc == 0x02);  // NO IDEA
				s = readString(bais); assert (s.equals ("Z"));  // boolean value
				s = readString(bais); assert (s.equals ("value"));
				bc = bais.read(); assert (bc == 0x78);  // end Block data
				bc = bais.read(); assert (bc == 0x70);  // null object reference
				readBoolean(bais);                      // ignore value
			} else {
				bc = bais.read(); assert (bc == 0x71);
				readInt(bais);                          // somehow encodes this reference
			}
			
			// Came from given bin. Add to tail of list, since that is how it was written out
			int bin = (key.hashCode() & 0x7FFFFFFF) % tableSize;
			LinkedList<String> list = bins[bin];
			if (list == null) {
				list = new LinkedList<String>();
				bins[bin] = list;
			}
			list.addLast(key);
		}

		bc = bais.read(); assert (bc == 0x78);    // end Block data
		
		return new HashtableReport (bins, tableSize, elements, loadFactor, threshold);
	}
	
	private static long readLong(ByteArrayInputStream bais) {
		int ch1 = bais.read();
        int ch2 = bais.read();
        int ch3 = bais.read();
        int ch4 = bais.read();
        int ch5 = bais.read();
        int ch6 = bais.read();
        int ch7 = bais.read();
        int ch8 = bais.read();
		return (((long)ch1 << 56) +
                ((long)(ch2 & 255) << 48) +
                ((long)(ch3 & 255) << 40) +
                ((long)(ch4 & 255) << 32) +
                ((long)(ch5 & 255) << 24) +
                ((ch6 & 255) << 16) +
                ((ch7 & 255) <<  8) +
                ((ch8 & 255) <<  0));
	}

	private static String readString(ByteArrayInputStream bais) {
		String ret = "";
		try {
			short ct = readShort(bais);             // length of class name
			byte [] inb = new byte[ct];
			bais.read(inb);
			ret = new String (inb);
		} catch (Exception e) {
			e.printStackTrace();
		}
		return ret; 
	}

	private static short readShort(ByteArrayInputStream bais) {
		int ch1 = bais.read();
        int ch2 = bais.read();
        return (short)((ch1 << 8) + (ch2 << 0));
	}
	
	private static boolean readBoolean(ByteArrayInputStream bais) {
		int ch1 = bais.read();
        return ch1 != 0;
	}
	
	private static int readInt(ByteArrayInputStream bais) {
		int ch1 = bais.read();
        int ch2 = bais.read();
        int ch3 = bais.read();
        int ch4 = bais.read();
        return ((ch1 << 24) + (ch2 << 16) + (ch3 << 8) + (ch4 << 0));
	}

}
