tikhomirov@260: /*
tikhomirov@260:  * Copyright (c) 2011 TMate Software Ltd
tikhomirov@260:  *  
tikhomirov@260:  * This program is free software; you can redistribute it and/or modify
tikhomirov@260:  * it under the terms of the GNU General Public License as published by
tikhomirov@260:  * the Free Software Foundation; version 2 of the License.
tikhomirov@260:  *
tikhomirov@260:  * This program is distributed in the hope that it will be useful,
tikhomirov@260:  * but WITHOUT ANY WARRANTY; without even the implied warranty of
tikhomirov@260:  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
tikhomirov@260:  * GNU General Public License for more details.
tikhomirov@260:  *
tikhomirov@260:  * For information on how to redistribute this software under
tikhomirov@260:  * the terms of a license other than GNU General Public License
tikhomirov@260:  * contact TMate Software at support@hg4j.com
tikhomirov@260:  */
tikhomirov@260: package org.tmatesoft.hg.util;
tikhomirov@260: 
tikhomirov@260: import org.tmatesoft.hg.internal.Experimental;
tikhomirov@260: 
tikhomirov@260: /**
tikhomirov@260:  * WORK IN PROGRESS, DO NOT USE
tikhomirov@260:  * Memory-friendly alternative to HashMap-backed Pool. Set where object can be obtained (not only queried for presence)
tikhomirov@260:  * 
tikhomirov@260:  * cpython repo, use of HashMap Pool results in ~6 Mb of Map.Entry and Map.Entry[],
tikhomirov@260:  * while use of SparseSet result in 2 Mb. 
tikhomirov@260:  * 
tikhomirov@260:  * @author Artem Tikhomirov
tikhomirov@260:  * @author TMate Software Ltd.
tikhomirov@260:  */
tikhomirov@260: @Experimental(reason="Requires tuning to accomodate to collection size. Present state (6-6-6) is too much for a lot of uses")
tikhomirov@260: public class SparseSet<T> {
tikhomirov@260: 	
tikhomirov@260: 	public static void main(String[] args) {
tikhomirov@260: 		SparseSet<String> ss = new SparseSet<String>();
tikhomirov@260: 		String one = Integer.toString(156), two = Integer.toString(1024), three = Integer.toString(1123123);
tikhomirov@260: 		ss.put(one);
tikhomirov@260: 		ss.put(two);
tikhomirov@260: 		ss.put(three);
tikhomirov@260: 		System.out.println(one == ss.get(one));
tikhomirov@260: 		System.out.println(two == ss.get(two));
tikhomirov@260: 		System.out.println(three == ss.get(three));
tikhomirov@260: 		System.out.println(null == ss.get("one"));
tikhomirov@260: 		System.out.println(one == ss.get(Integer.toString(156)));
tikhomirov@260: 		System.out.println(two == ss.get(Integer.toString(1024)));
tikhomirov@260: 		System.out.println(three == ss.get(Integer.toString(1123123)));
tikhomirov@260: 		ss.dump();
tikhomirov@260: 	}
tikhomirov@260: 
tikhomirov@260: 	private static class IndexBranch {
tikhomirov@260: 		private final LeafBranch[] leafs = new LeafBranch[64];
tikhomirov@260: 	}
tikhomirov@260: 	private static class LeafBranch {
tikhomirov@260: 		private final Object[] data = new Object[64];
tikhomirov@260: 	}
tikhomirov@260: 
tikhomirov@260: 	private final int[] fixups = new int[] {0x1, 0x10, 0xA, 0xD, 0x1F }; // rehash attempts
tikhomirov@260: 	private final IndexBranch[] level2 = new IndexBranch[64];
tikhomirov@260: 	private int size = 0;
tikhomirov@260: 
tikhomirov@260: 	public void put(T o) {
tikhomirov@260: 		int hash = o.hashCode();
tikhomirov@260: 		//
tikhomirov@260: 		// 8 bits per level
tikhomirov@260: //		int i1 = (hash >>> 24) & 0xFF, i2 = (hash >>> 16) & 0xFF , i3 = (hash >>> 8) & 0xFF, i4 = hash & 0xFF;
tikhomirov@260: 		//
tikhomirov@260: 		// 10, 8, 8 and 6 bits
tikhomirov@260: //		final int i1 = (hash >>> 22) & 0x3FF, i2 = (hash >>> 14) & 0xFF , i3 = (hash >>> 6) & 0xFF, i4 = hash & 0x3F;
tikhomirov@260: 		//
tikhomirov@260: 		// 8, 6, 6, 6, 6
tikhomirov@260: 		// 10, 6, 6, 6, 4
tikhomirov@260: 		//
tikhomirov@260: 		// 6, 5, 5, 5 = 21 bit
tikhomirov@260: //		hash = hash ^ (hash >>> 24); // incorporate upper byte we don't use into lower to value it
tikhomirov@260: //		final int i1 = (hash >>> 18) & 0x3F, i2 = (hash >>> 12) & 0x1F , i3 = (hash >>> 7) & 0x1F, i4 = (hash >>> 2) & 0x1F;
tikhomirov@260: 		// 6, 5, 5
tikhomirov@260: //		hash = hash ^ (hash >>> 16);
tikhomirov@260: //		final int i1 = (hash >>> 10) & 0x3F, i2 = (hash >>> 5) & 0x1F , i3 = hash & 0x1F;
tikhomirov@260: 		//
tikhomirov@260: 		// 6, 6, 6
tikhomirov@260: 		final int i1 = (hash >>> 15) & 0x3F, i2 = (hash >>> 6) & 0x3F , i3 = hash & 0x3F;
tikhomirov@260: 		LeafBranch l3 = leafBranchPut(i1, i2);
tikhomirov@260: 		if (l3.data[i3] == null) {
tikhomirov@260: 			l3.data[i3] = o;
tikhomirov@260: 			size++;
tikhomirov@260: 			return;
tikhomirov@260: 		}
tikhomirov@260: 		int neighbour = (i3+1) & 0x3F; 
tikhomirov@260: 		if (l3.data[neighbour] == null) {
tikhomirov@260: 			l3.data[neighbour] = o;
tikhomirov@260: 			size++;
tikhomirov@260: 			return;
tikhomirov@260: 		}
tikhomirov@260: 		int conflictCount = 0;
tikhomirov@260: 		for (int fixup : fixups) {
tikhomirov@260: //			if (showConflicts) {
tikhomirov@260: //				System.out.printf("(fixup: 0x%x) ", fixup);
tikhomirov@260: //			}
tikhomirov@260: 			l3 = leafBranchPut(i1 ^ fixup, i2);
tikhomirov@260: 			conflictCount++;
tikhomirov@260: 			if (l3.data[i3] != null) {
tikhomirov@260: //				if (showConflicts) {
tikhomirov@260: //					System.out.printf("i1 failed ");
tikhomirov@260: //				}
tikhomirov@260: 				l3 = leafBranchPut(i1, i2 ^ fixup);
tikhomirov@260: 				conflictCount++;
tikhomirov@260: //				if (showConflicts) {
tikhomirov@260: //					System.out.printf("i2 %s ",  (l3.data[i3] == null) ? "ok" : "failed");
tikhomirov@260: //				}
tikhomirov@260: //			} else {
tikhomirov@260: //				if (showConflicts) {
tikhomirov@260: //					System.out.printf("i1 ok");
tikhomirov@260: //				}
tikhomirov@260: 			}
tikhomirov@260: //			if (showConflicts) {
tikhomirov@260: //				System.out.println();
tikhomirov@260: //			}
tikhomirov@260: 			if (l3.data[i3] == null) {
tikhomirov@260: 				l3.data[i3] = o;
tikhomirov@260: //				System.out.printf("Resolved conflict in %d steps (fixup 0x%X)\n", conflictCount, fixup);
tikhomirov@260: 				size++;
tikhomirov@260: 				return;
tikhomirov@260: 			}
tikhomirov@260: 		}
tikhomirov@260: 		throw new IllegalStateException(String.valueOf(o));
tikhomirov@260: 	}
tikhomirov@260: 	
tikhomirov@260: 	@SuppressWarnings("unchecked")
tikhomirov@260: 	public T get(T o) {
tikhomirov@260: 		int hash = o.hashCode();
tikhomirov@260: 		//hash = hash ^ (hash >>> 16);
tikhomirov@260: 		final int i1 = (hash >>> 15) & 0x3F, i2 = (hash >>> 6) & 0x3F , i3 = hash & 0x3F;
tikhomirov@260: 		//
tikhomirov@260: 		LeafBranch l3 = leafBranchGet(i1, i2);
tikhomirov@260: 		if (l3 == null || l3.data[i3] == null) {
tikhomirov@260: 			return null;
tikhomirov@260: 		}
tikhomirov@260: 		if (o.equals(l3.data[i3])) {
tikhomirov@260: 			return (T) l3.data[i3];
tikhomirov@260: 		}
tikhomirov@260: 		//
tikhomirov@260: 		int neighbour = (i3+1) & 0x3F; 
tikhomirov@260: 		if (o.equals(l3.data[neighbour])) {
tikhomirov@260: 			return (T) l3.data[neighbour];
tikhomirov@260: 		}
tikhomirov@260: 
tikhomirov@260: 		//
tikhomirov@260: 		// resolve conflict
tikhomirov@260: 		for (int fixup : fixups) {
tikhomirov@260: 			Object data = leafValueGet(i1 ^ fixup, i2, i3);
tikhomirov@260: 			if (data == null) {
tikhomirov@260: 				return null;
tikhomirov@260: 			}
tikhomirov@260: 			if (o.equals(data)) {
tikhomirov@260: 				return (T)data;
tikhomirov@260: 			}
tikhomirov@260: 			data = leafValueGet(i1, i2 ^ fixup, i3);
tikhomirov@260: 			if (data == null) {
tikhomirov@260: 				return null;
tikhomirov@260: 			}
tikhomirov@260: 			if (o.equals(data)) {
tikhomirov@260: 				return (T)data;
tikhomirov@260: 			}
tikhomirov@260: 		}
tikhomirov@260: 		dump();
tikhomirov@260: 		throw new IllegalStateException(String.format("[%d,%d,%d] hash: 0x%X, hash2: 0x%X, %s", i1, i2, i3, o.hashCode(), hash, o));
tikhomirov@260: 	}
tikhomirov@260: 
tikhomirov@260: 	public int size() {
tikhomirov@260: 		return size;
tikhomirov@260: 	}
tikhomirov@260: 	private LeafBranch leafBranchPut(int i1, int i2) {
tikhomirov@260: 		IndexBranch l2 = level2[i1];
tikhomirov@260: 		if (l2 == null) {
tikhomirov@260: 			level2[i1] = l2 = new IndexBranch();
tikhomirov@260: 		}
tikhomirov@260: 		LeafBranch l3 = l2.leafs[i2];
tikhomirov@260: 		if (l3 == null) {
tikhomirov@260: 			l2.leafs[i2] = l3 = new LeafBranch();
tikhomirov@260: 		}
tikhomirov@260: 		return l3;
tikhomirov@260: 	}
tikhomirov@260: 
tikhomirov@260: 	private LeafBranch leafBranchGet(int i1, int i2) {
tikhomirov@260: 		IndexBranch l2 = level2[i1];
tikhomirov@260: 		if (l2 == null) {
tikhomirov@260: 			return null;
tikhomirov@260: 		}
tikhomirov@260: 		return l2.leafs[i2];
tikhomirov@260: 	}
tikhomirov@260: 
tikhomirov@260: 	private Object leafValueGet(int i1, int i2, int i3) {
tikhomirov@260: 		IndexBranch l2 = level2[i1];
tikhomirov@260: 		if (l2 == null) {
tikhomirov@260: 			return null;
tikhomirov@260: 		}
tikhomirov@260: 		LeafBranch l3 = l2.leafs[i2];
tikhomirov@260: 		if (l3 == null) {
tikhomirov@260: 			return null;
tikhomirov@260: 		}
tikhomirov@260: 		return l3.data[i3];
tikhomirov@260: 	}
tikhomirov@260: 
tikhomirov@260: 	public void dump() {
tikhomirov@260: 		int count = 0;
tikhomirov@260: 		for (int i = 0; i < level2.length; i++) {
tikhomirov@260: 			IndexBranch l2 = level2[i];
tikhomirov@260: 			if (l2 == null) {
tikhomirov@260: 				continue;
tikhomirov@260: 			}
tikhomirov@260: 			for (int j = 0; j < l2.leafs.length; j++) {
tikhomirov@260: 				LeafBranch l3 = l2.leafs[j];
tikhomirov@260: 				if (l3 == null) {
tikhomirov@260: 					continue;
tikhomirov@260: 				}
tikhomirov@260: 				for (int k = 0; k < l3.data.length; k++) {
tikhomirov@260: 					Object d = l3.data[k];
tikhomirov@260: 					if (d != null) {
tikhomirov@260: 						System.out.printf("[%3d,%3d,%3d] %s\n", i,j,k,d);
tikhomirov@260: 						count++;
tikhomirov@260: 					}
tikhomirov@260: 				}
tikhomirov@260: 			}
tikhomirov@260: 		}
tikhomirov@260: 		System.out.printf("Total: %d elements", count);
tikhomirov@260: 	}
tikhomirov@260: }