generate-pushid.coffee

###*
 * Fancy ID generator that creates 20-character string identifiers with the following properties:
 *
 * 1. They're based on timestamp so that they sort *after* any existing ids.
 * 2. They contain 72-bits of random data after the timestamp so that IDs won't collide with other clients' IDs.
 * 3. They sort *lexicographically* (so the timestamp is converted to characters that will sort properly).
 * 4. They're monotonically increasing.  Even if you generate more than one in the same timestamp, the
 *    latter ones will sort after the former ones.  We do this by using the previous random bits
 *    but "incrementing" them by 1 (only in the case of a timestamp collision).
###
	
generatePushID = (->
	# Modeled after base64 web-safe chars, but ordered by ASCII.
	pushChars = "-0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz"

	# Timestamp of last push, used to prevent local collisions if you push twice in one ms.
	lastPushTime = 0

	# We generate 72-bits of randomness which get turned into 12 characters and appended to the
	# timestamp to prevent collisions with other clients.  We store the last characters we
	# generated because in the event of a collision, we'll use those same characters except
	# "incremented" by one.
	lastRandChars = []
	return ->
		now = new Date().getTime()
		duplicateTime = now is lastPushTime
		lastPushTime = now

		timeStampChars = [0..7].map((e)->
			r = pushChars.charAt(now % 64)
			now =Math.floor(now / 64)
			return r
		).reverse().join ''
		throw new Error('We should have converted the entire timestamp.') if now isnt 0

		lastRandChars = [0...12].map (e)-> ~~(Math.random()*64)
		if duplicateTime
			# If the timestamp hasn't changed since last push, use the same random number, incremented by 1
			lastRandChars[lastRandChars.length-1]++
			lastRandChars[lastRandChars.length-1] = 0 if lastRandChars[lastRandChars.length-1] > 64
		
		throw new Error('Length should be 20.') if lastRandChars.length+timeStampChars.length isnt 20

		return timeStampChars+lastRandChars.map((e)->pushChars.charAt(e)).join('')

)()