/**
 * Generates unique 64-bit ID
 * 
 * Identifier structure:
 * bits 63 (1 bit) - not used (sign bit, after 2108 year identifier will be negative till year 2246. After 2246 year identifier will break)
 * bits 62-20 (43 bits) - time in milliseconds from midnight, January 1, 1970 UTC
 * bits 19-10 (10 bits) - cluster node number. 1024 nodes are supported
 * bits 9 (1 bit) - backward time flag. In case server was time synchronized backward, for running out conflicts, period of time till this timeshift flag will be 1.
 * bits 8-0 (9 bits) - sequence generator. In case more than 1 id requested per same millisecond allows generate up to 512 different id per millisecond. After 512 ids algorithm will wait till next millisecond 
 */
public class IdGenerator {
	
	protected final static int SEQ_NUM_BITS = 9;
	
	protected final static int NODE_NUM_BITS = 10;
	
	protected final static int BACK_TIME_BITS = 1;
	
	protected final static long SEQ_NUM_MAX = 1 << SEQ_NUM_BITS;
	
	protected static int seqNum = 0;
	
	//TODO implement requesting node number on startup. 2 in power of NODE_NUM_BITS nodes supported
	protected static final int nodeNum = 0;
	
	protected static long lastTimestamp = 0;
	
	protected static long backTimeMoment = Long.MAX_VALUE;
	
	/**
	 * Returns next Id. Main method of generator
	 * 
	 * @return
	 */
	synchronized static long nextId(){
		long curTimestamp = System.currentTimeMillis();
		
		// if time was returned backwards, preparing to turning on conflict free flag
		if(curTimestamp < lastTimestamp){
			backTimeMoment = lastTimestamp;
			lastTimestamp = curTimestamp;
		}else{
			if(curTimestamp > backTimeMoment){
				backTimeMoment = Long.MAX_VALUE;
			}
		}

		// if more than 1 identifier was generated per millisecond, increment sequence counter
		if(curTimestamp == lastTimestamp){
			seqNum++;
			
			if(seqNum >= SEQ_NUM_MAX){
				seqNum = 0;
				while(curTimestamp == lastTimestamp)
				{
					curTimestamp = System.currentTimeMillis();
					try {
						Thread.sleep(1);
					} catch (InterruptedException e) {
					}
				}
				
			}
		}else{
			seqNum = 0;
		}
		
		// remembering last time when identifier was generated
		lastTimestamp = curTimestamp;
		
		// generating identifier with all its components
		return curTimestamp << (SEQ_NUM_BITS + NODE_NUM_BITS + BACK_TIME_BITS) |
				nodeNum << (SEQ_NUM_BITS + BACK_TIME_BITS) | 
				(backTimeMoment != Long.MAX_VALUE ? 1 : 0) << SEQ_NUM_BITS | seqNum;
		
	}
	
}