/**
	Formats strings 

		var s01 = window.sprintf('Binary: %b', 10);
		// s01 ==> 'Binary: 1010'
	
		var s02 = window.sprintf('Unicode: %c', 65);
		// s02 ==> 'Unicode: A'

		var s03 = window.sprintf('Decimal: %d', 100);
		// s03 ==> 'Decimal: 100'

		var s04 = window.sprintf('Exponential notation: %e', 123456);
		// s04 ==> 'Exponential notation: 1.23456e+5'

		var s05 = window.sprintf('Floating point formatting: %10.1f', 65);
		// s05 ==> 'Floating point formatting:       65.0'

		var s06 = window.sprintf('Octal: %o', 10);
		// s06 ==> 'Octal: 12'
	
		var s07 = window.sprintf('String: %s', 'basketball');
		// s07 ==> 'String: basketball'
	
		var s08 = window.sprintf('Absolute value: %u', -65);
		// s08 ==> 'Absolute value: 65'
	
		var s09 = window.sprintf('Hexadecimal lowercase: %x', 123);
		// s09 ==> 'Hexadecimal lowercase: 7b'
	
		var s10 = window.sprintf('Hexadecimal uppercase: %X', 123);
		// s10 ==> 'Hexadecimal uppercase: 7B'
	
		// sprintf takes a variable amount of arguments
		var s11 = window.sprintf('My name is %s and I am %d', 'tyler', 22);
		// s11 ==> 'My name is tyler and I am 22'

	@method sprintf
	@for window

	@param {String} format A formatted string, containing 0 or more conversion specifications.
	@params vals {String|Number} A variable amount of arguments which will be inserted into the format string.
	
	@return {String} A formatted string
**/
window.sprintf = (function() {
	var get_type = function(variable) {
		return Object.prototype.toString.call(variable).slice(8, -1).toLowerCase();
	};

	var str_repeat = function(input, multiplier) {
		for (var output = []; multiplier > 0; output[--multiplier] = input) {/* do nothing */}
		return output.join('');
	};


	var str_format = function() {
		if (!str_format.cache.hasOwnProperty(arguments[0])) {
			str_format.cache[arguments[0]] = str_format.parse(arguments[0]);
		}
		return str_format.format.call(null, str_format.cache[arguments[0]], arguments);
	};

	str_format.format = function(parse_tree, argv) {
		var cursor = 1, tree_length = parse_tree.length, node_type = '', arg, output = [], i, k, match, pad, pad_character, pad_length;
		for (i = 0; i < tree_length; i++) {
			node_type = get_type(parse_tree[i]);
			if (node_type === 'string') {
				output.push(parse_tree[i]);
			} else if (node_type === 'array') {
				match = parse_tree[i]; // convenience purposes only
				if (match[2]) { // keyword argument
					arg = argv[cursor];
					for (k = 0; k < match[2].length; k++) {
						if (!arg.hasOwnProperty(match[2][k])) {
							throw (window.sprintf('[sprintf] property "%s" does not exist', match[2][k]));
						}
						arg = arg[match[2][k]];
					}
				} else if (match[1]) { // positional argument (explicit)
					arg = argv[match[1]];
				} else { // positional argument (implicit)
					arg = argv[cursor++];
				}

				if (/[^s]/.test(match[8]) && (get_type(arg) != 'number')) {
					throw (window.sprintf('[sprintf] expecting number but found %s', get_type(arg)));
				}
				switch (match[8]) {
					case 'b': arg = arg.toString(2); break;
					case 'c': arg = String.fromCharCode(arg); break;
					case 'd': arg = parseInt(arg, 10); break;
					case 'e': arg = match[7] ? arg.toExponential(match[7]) : arg.toExponential(); break;
					case 'f': arg = match[7] ? parseFloat(arg).toFixed(match[7]) : parseFloat(arg); break;
					case 'o': arg = arg.toString(8); break;
					case 's': arg = ((arg = String(arg)) && match[7] ? arg.substring(0, match[7]) : arg); break;
					case 'u': arg = Math.abs(arg); break;
					case 'x': arg = arg.toString(16); break;
					case 'X': arg = arg.toString(16).toUpperCase(); break;
				}
				arg = (/[def]/.test(match[8]) && match[3] && arg >= 0 ? '+'+ arg : arg);
				pad_character = match[4] ? match[4] == '0' ? '0' : match[4].charAt(1) : ' ';
				pad_length = match[6] - String(arg).length;
				pad = match[6] ? str_repeat(pad_character, pad_length) : '';
				output.push(match[5] ? arg + pad : pad + arg);
			}
		}
		return output.join('');
	};

	str_format.cache = {};

	str_format.parse = function(fmt) {
		var _fmt = fmt, match = [], parse_tree = [], arg_names = 0;
		while (_fmt) {
			if ((match = /^[^\x25]+/.exec(_fmt)) !== null) {
				parse_tree.push(match[0]);
			} else if ((match = /^\x25{2}/.exec(_fmt)) !== null) {
				parse_tree.push('%');
			} else if ((match = /^\x25(?:([1-9]\d*)\$|\(([^\)]+)\))?(\+)?(0|'[^$])?(-)?(\d+)?(?:\.(\d+))?([b-fosuxX])/.exec(_fmt)) !== null) {
				if (match[2]) {
					arg_names |= 1;
					var field_list = [], replacement_field = match[2], field_match = [];
					if ((field_match = /^([a-z_][a-z_\d]*)/i.exec(replacement_field)) !== null) {
						field_list.push(field_match[1]);
						while ((replacement_field = replacement_field.substring(field_match[0].length)) !== '') {
							if ((field_match = /^\.([a-z_][a-z_\d]*)/i.exec(replacement_field)) !== null) {
								field_list.push(field_match[1]);
							} else if ((field_match = /^\[(\d+)\]/.exec(replacement_field)) !== null) {
								field_list.push(field_match[1]);
							} else {
								throw ('[sprintf] huh?');
							}
						}
					} else {
						throw ('[sprintf] huh?');
					}
					match[2] = field_list;
				} else {
					arg_names |= 2;
				}
				if (arg_names === 3) {
					throw ('[sprintf] mixing positional and named placeholders is not (yet) supported');
				}
				parse_tree.push(match);
			} else {
				throw ('[sprintf] huh?');
			}
			_fmt = _fmt.substring(match[0].length);
		}
		return parse_tree;
	};

	return str_format;
})();

/**
	Formats strings.  Exactly the same as sprintf except it takes an array of arguments.

		var s = sprintf('My name is %s and I am %d', ['tyler', 22]);
		// s ==> 'My name is tyler and I am 22'

	@method vsprintf

	@param {String} format A formatted string, containing 0 or more conversion specifications.
	@params {Array} vals An array containing values that will be inserted into the format string.

	@return {String} A formatted string
**/
window.vsprintf = function(fmt, argv) {
	argv.unshift(fmt);
	return window.sprintf.apply(null, argv);
};