//
// extended Javascript Serialized Object Notation
//
// -API (js.* namespaced)
//   -stringify(* obj) -> String
//   -parse(String str) -> *
//
// -Conformance
//   -Errors in expected locations except for Circular references
//
// -Performance (competitive)
//   -Non-recursive, single pass, fast fail
//   -Could be sped up to match v8's JSON speed most likely
//
// -Circular References
//   -uses mozilla's #Identifier format, #1 will appear before the first instance of the object
//     -example : [#1{x:#1},#1] would be an array with indexes of the same reference with a circular reference
//   -parser is more lax and allows any identifier in [0-9a-zA-Z_$]+ to follow the '#'
//
;(function(js) {
	function stringify(o) {
		 var stack = [o]
		 var indices = []
		 var parts = []
		 var pointer
		 var first
		 var visited = [{}]//fix for fact 0 === -0
		 var counts = [0]
		 while (pointer = stack[stack.length-1]) {
			  if(pointer !== null && pointer instanceof Object) {
					var key = undefined
					var index = visited.indexOf(pointer)
					if(index === -1) {
						visited.push(pointer)
						counts.push(1)
						index = visited.length - 1
					}
					else if(indices[stack.length-1] === undefined) {
						counts[index]++
						parts.push(index)
						stack.pop()
						continue
					}
					if(pointer instanceof Array) {
						 if(indices[stack.length-1] === undefined) {
							  parts.push(index)
							  parts.push("[")
							  first = true
							  key = indices[stack.length-1] = 0
						 }
						 else {
							key = indices[stack.length-1]
							first = false
						 }

						 if(key === pointer.length) {
							  parts.push("]")
							  parts.push(-index)
							  indices[stack.length-1] = undefined
							  stack.pop()
						 }
						 else {
							  if(!first) {
									parts.push(",")
							  }
							  indices[stack.length-1]+=1
							  stack.push(pointer[key])
						 }
					}
					else {
						first = false
						if(indices[stack.length-1] === undefined) {
							  parts.push(index)
							  parts.push("{")
							  first = true
							  var keys = []
							  for(var k in pointer) {
								keys.push(String(k))
							  }
							  indices[stack.length-1]  = keys
						 }
						key = indices[stack.length-1].shift()

						 if(key === undefined) {
							  parts.push("}")
							  parts.push(-index)
							  indices[stack.length-1] = undefined
							  stack.pop()
						 }
						 else {
							  if(!first) {
									parts.push(",")
							  }
							  parts.push('"')
							  parts.push(String(key))
							  parts.push('":')
							  stack.push(pointer[key])
						 }
					}
			  }
			  else {
					if(isNaN(pointer)||!isFinite(pointer)) pointer = null
					 parts.push(String(pointer))
					 stack.pop()
			  }
		 }
		 visited = {}
		 stack = []
		 for(var i = 0; i < parts.length; i++) {
			var item = parts[i]
			if(typeof item === "number") {
				if(item > 0) {
					if(visited[item] === undefined) {
						visited[item] = []
						stack.push(item)
					}
					if(counts[item] > 1) parts[i] = "#"+item
					else parts.splice(i,1)
				}
				else {
					parts.splice(i,1)
					stack.pop()
				}
			}
			else {
				if(stack.length) {
					visited[stack[stack.length-1]].push(item)
				}
			}
		}
		 return parts.join("")
	}

	var tokenizer = new RegExp( "("+[
		'"(?:\\[^\\n]|[^"])*"',//1
		"'(?:\\[^\\n]|[^\"])'",//2
		"[-]?(?:[0-9]+[.]?[0-9]*|[.][0-9]+)(?:[eE][-+][0-9]+)?",//3
		"true|false",//4
		"null",//5
		"[#][0-9a-zA-Z_$]+",//6
		"\\[",//7
		"\\]",//8
		"\\,",//9
		"\\:",//10
		"\\{",//11
		"\\}",//12
		"\\s+"//13
	].join(")|(")+")" , "g" )
	function parse(str) {
		str = String(str)
		var reference
		var references = {}
		var stack = [[]]
		var keys = [0]
		var matcher = tokenizer
		matcher.lastIndex = 0
		var index = 0
		var match
		var lookingForContinuable = false
		var lookingForKey = false
		var lookingForValue = false
		function addProperty(value) {
			var key = keys[stack.length-1]
			var item = stack[stack.length-1]
			if(key === undefined) {
				throw new Error("Value encountered without a Key")
			}
			item[key] = value
			if(item instanceof Array) {
				keys[stack.length-1]++
			}
			else {
				keys[stack.length-1] = undefined
			}
			if(reference !== undefined) {
				references[reference] = value
			}
			reference = undefined
			lookingForKey = false
			lookingForValue = false
			lookingForContinuable = true
		}
		while(match = matcher.exec(str)) {
			if(index != match.index) {throw new Error("Unexpected '"+str.slice(index,match.index)+"'")}
			if(match[1] !== undefined) {
				var value = match[1].slice(1,-1)
				if(lookingForKey) {
					keys[stack.length-1] = value
					lookingForKey = false
					lookingForValue = true
					lookingForContinuable = false
				}
				else {
					addProperty(value)
				}
			}
			else if(match[2] !== undefined) {
				var value = match[2].slice(1,-1)
				if(lookingForKey) {
					keys[stack.length-1] = value
					lookingForKey = false
					lookingForValue = true
					lookingForContinuable = false
				}
				else {
					addProperty(value)
				}
			}
			else if(match[3] !== undefined) {
				addProperty(Number(match[3]))
			}
			else if(match[4] !== undefined) {
				addProperty(match[4] === "true")
			}
			else if(match[5] !== undefined) {
				addProperty(null)
			}
			else if(match[6] !== undefined) {
				if(references[match[6]] !== undefined) {
					addProperty(references[match[6]])
				}
				else {
					reference = match[6]
				}
			}
			else if(match[7] !== undefined) {
				var child = []
				addProperty(child)
				lookingForContinuable = true
				lookingForValue = true
				stack[stack.length] = child
				keys[keys.length] = 0
			}
			else if(match[8] !== undefined) {
				if(!lookingForContinuable) throw new Error("Unexpected end of Array at "+index)
				stack.length--
				keys.length--
			}
			else if(match[9] !== undefined) {
				if(!lookingForContinuable || lookingForKey || lookingForValue) throw new Error("Unexpected ',' at "+index)
				var item = stack[stack.length-1]
				lookingForContinuable = false
				if(!(item instanceof Array)) {
					lookingForKey = true
				}
			}
			else if(match[10] !== undefined) {
				if(lookingForContinuable || lookingForKey) throw new Error("Unexpected ':' at "+index)
				lookingForValue = true
			}
			else if(match[11] !== undefined) {
				var child = {}
				addProperty(child)
				lookingForKey = true
				stack[stack.length] = child
				keys[keys.length] = null
			}
			else if(match[12] !== undefined) {
				if(!lookingForContinuable) throw new Error("Unexpected end of Object at "+index)
				stack.length--
				keys.length--
			}
			index = matcher.lastIndex
			if(stack.length == 1 && stack[0].length) break
		}
		if(index !== str.length){throw new Error("Unexpected '"+str.substr(index)+"'")}
		return stack[0][0]
	}
	js.parse = parse
	js.stringify = stringify
}) (typeof exports !== "undefined" ? exports : js = {}));