File: rjson.js

/*
 Copyright (c) 2012, Dmytro V. Dogadailo <entropyhacker@gmail.com>

 RJSON is Recursive JSON.

 RJSON converts any JSON data collection into more compact recursive
 form. Compressed data is still JSON and can be parsed with `JSON.parse`. RJSON
 can compress not only homogeneous collections, but any data sets with free
 structure.

 RJSON is stream single-pass compressor, it extracts data schemes from a
 document, assign each schema unique number and use this number instead of
 repeating same property names again and again.

 Bellow you can see same document in both forms.

 JSON:

 {
 "id": 7,
 "tags": ["programming", "javascript"],
 "users": [
 {"first": "Homer", "last": "Simpson"},
 {"first": "Hank", "last": "Hill"},
 {"first": "Peter", "last": "Griffin"}
 ],
 "books": [
 {"title": "JavaScript", "author": "Flanagan", "year": 2006},
 {"title": "Cascading Style Sheets", "author": "Meyer", "year": 2004}
 ]
 }

 RJSON:

 {
 "id": 7,
 "tags": ["programming", "javascript"],
 "users": [
 {"first": "Homer", "last": "Simpson"},
 [2, "Hank", "Hill", "Peter", "Griffin"]
 ],
 "books": [
 {"title": "JavaScript", "author": "Flanagan", "year": 2006},
 [3, "Cascading Style Sheets", "Meyer", 2004]
 ]
 }

 RJSON allows to:

 * reduce JSON data size and network traffic when gzip isn't available. For
 example, in-browser 3D-modeling tools like [Mydeco
 3D-planner](http://mydeco.com/3d-planner/) may process and send to server
 megabytes of JSON-data;
 * analyze large collections of JSON-data without
 unpacking of whole dataset. RJSON-data is still JSON-data, so it can be
 traversed and analyzed after parsing and fully unpacked only if a document meets
 some conditions.

 */

var RJSON = (function() {
	'use strict';

	var hasOwnProperty = Object.prototype.hasOwnProperty,
		toString = Object.prototype.toString,
		getKeys = Object.keys || _keys,
		isArray = Array.isArray || _isArray;

	/**
	 * @return {*} Packed javascript data, usually a dictionary.
 * @param data
	 */
	function pack(data) {
		var schemas = {}, maxSchemaIndex = 0;

		function encodeArray(value) {

			var len = value.length, encoded = [];
			if (len === 0) return [];
			if (typeof value[0] === 'number') {
				encoded.push(0); // 0 is schema index for Array
			}

			for (var i = 0; i < len; i++) {
				var v = value[i];
				var	current = encode(v);
				var	last = encoded[encoded.length - 1];
				if (isEncodedObject(current) && isArray(last) && current[0] === last[0]) {
					// current and previous object have same schema,
					// so merge their values into one array
					encoded[encoded.length - 1] = last.concat(current.slice(1));
				} else {
					encoded.push(current);
				}
			}
			return encoded;
		}

		function encodeObject(value) {
			var schemaKeys = getKeys(value).sort();
			if (schemaKeys.length === 0) {
				return {};
			}
			var encoded,
				schema = schemaKeys.length + ':' + schemaKeys.join('|'),
				schemaIndex = schemas[schema];

			if (schemaIndex) { // known schema
				encoded = [schemaIndex];
				//noinspection JSDuplicatedDeclaration
				for (var i = 0, k; k = schemaKeys[i++]; ) {
					encoded[i] = encode(value[k]);
				}
			} else { // new schema
				schemas[schema] = ++maxSchemaIndex;
				encoded = {};
				//noinspection JSDuplicatedDeclaration
				for (var i = 0, k; k = schemaKeys[i++]; ) {
					encoded[k] = encode(value[k]);
				}
			}
			return encoded;
		}

		function encode(value) {
			if (typeof value !== 'object' || !value) {
				// non-objects or null return as is
				return value;
			} else if (isArray(value)) {
				return encodeArray(value);
			} else {
				return encodeObject(value);
			}
		}

		return encode(data);
	}

	/**
	 * @param {*} data Packed javascript data.
	 * @return {*} Original data.
	 */
	function unpack(data) {
		var schemas = {}, maxSchemaIndex = 0;

		function parseArray(value) {
			if (value.length === 0) {
				return [];
			} else if (value[0] === 0 || typeof value[0] !== 'number') {
				return decodeArray(value);
			} else {
				return decodeObject(value);
			}
		}

		function decodeArray(value) {
			var len = value.length, decoded = []; // decode array of something
			for (var i = (value[0] === 0 ? 1 : 0); i < len; i++) {
				var v = value[i], obj = decode(v);
				if (isEncodedObject(v) && isArray(obj)) {
					// several objects was encoded into single array
					decoded = decoded.concat(obj);
				} else {
					decoded.push(obj);
				}
			}
			return decoded;
		}

		function decodeObject(value) {
			var schemaKeys = schemas[value[0]],
				schemaLen = schemaKeys.length,
				total = (value.length - 1) / schemaLen,
				decoded;
			if (total > 1) {
				decoded = []; // array of objects with same schema
				for (var i = 0; i < total; i++) {
					var obj = {};
					//noinspection JSDuplicatedDeclaration
					for (var j = 0, k; k = schemaKeys[j++]; ) {
						obj[k] = decode(value[i * schemaLen + j]);
					}
					decoded.push(obj);
				}
				//noinspection JSDuplicatedDeclaration
			} else {
				decoded = {};
				for (var j = 0, k; k = schemaKeys[j++]; ) {
					decoded[k] = decode(value[j]);
				}
			}
			return decoded;
		}

		function decodeNewObject(value) {
			var schemaKeys = getKeys(value).sort();
			if (schemaKeys.length === 0) {
				return {};
			}
			schemas[++maxSchemaIndex] = schemaKeys;
			var decoded = {};
			for (var i = 0, k; k = schemaKeys[i++]; ) {
				decoded[k] = decode(value[k]);
			}
			return decoded;
		}

		function decode(value) {
			if (typeof value !== 'object' || !value) {
				// non-objects or null return as is
				return value;
			} else if (isArray(value)) {
				return parseArray(value);
			} else { // object with new schema
				return decodeNewObject(value);
			}
		}
		return decode(data);
	}

	/**
	 * Object is encoded as array and object schema index is stored as
	 * first item of the array. Valid schema index should be greater than 0,
	 * because 0 is reserved for Array schema.
	 * Several objects with same schema can be stored in the one array.
	 * @param {*} value encoded value to check.
	 * @return {boolean} true if value contains an encoded object or several
	 * objects with same schema.
	 */
	function isEncodedObject(value) {
		return isArray(value) && typeof value[0] === 'number' && value[0] !== 0;
	}

	function _keys(obj) {
		var keys = [], k;
		for (k in obj) {
			if (hasOwnProperty.call(obj, k)) {
				keys.push(k);
			}
		}
		return keys;
	}

	function _isArray(obj) {
		return toString.apply(obj) === '[object Array]';
	}

	return {
		pack: pack,
		unpack: unpack
	};

}());

// export for node.js
if (typeof module != 'undefined' && module.exports) {
	module.exports = RJSON;
}