/*jshint curly:true, eqeqeq:true, strict:true, boss:true, laxcomma:true */

(function(global, attach){
	'use strict';

	var LZ77 = function(global){

		var
			self = {}
		,	settings = {
				refPrefix: '`',
				refIntBase: 96,
				refIntFloorCode: " ".charCodeAt(0),
				refIntCeilCode: undefined,
				maxStringDistance: undefined,
				minStringLength: 5,
				maxStringLength: undefined,
				defaultWindow: 144,
				maxWindow: undefined,
				windowLength: undefined
			}
		;

		var setup = function(params) {
			params = params || {};
			settings = extend(settings, params);
	
			settings.refIntCeilCode = settings.refIntFloorCode + settings.refIntBase - 1;
			settings.maxStringDistance = Math.pow(settings.refIntBase, 2) - 1;
			settings.maxStringLength = Math.pow(settings.refIntBase, 1) - 1 + settings.minStringLength;
			settings.maxWindow = settings.maxStringDistance + settings.minStringLength;
		};

		var each = function(obj, iterator, context) {
			var breaker = {};
			if (obj === null) { return; }
			if (Array.prototype.forEach && obj.forEach === Array.prototype.forEach) {
				obj.forEach(iterator, context);
			} else if (obj.length === +obj.length) {
				for (var i = 0, l = obj.length; i < l; i++) {
					if (iterator.call(context, obj[i], i, obj) === breaker) { return; }
				}
			} else {
				for (var key in obj) {
					if (obj.hasOwnProperty(key)) {
						if (iterator.call(context, obj[key], key, obj) === breaker) { return; }
					}
				}
			}
		};

		var extend = function(obj) {
			each(Array.prototype.slice.call(arguments, 1), function(source) {
				if (source) {
					for (var prop in source) {
						obj[prop] = source[prop];
					}
				}
			});
			return obj;
		};

		var encodeRefInt = function(value, width) {
			if ((value >= 0) && (value < (Math.pow(settings.refIntBase, width) - 1))) {
				var encoded = "";
				while (value > 0) {
					encoded = (String.fromCharCode((value % settings.refIntBase) + settings.refIntFloorCode)) + encoded;
					value = Math.floor(value / settings.refIntBase);
				}
				var missingLength = width - encoded.length;
				var i = 0;
				for (; i < missingLength; i++) {
					encoded = String.fromCharCode(settings.refIntFloorCode) + encoded;
				}
				return encoded;
			} else {
				throw "Reference int out of range: " + value + " (width = " + width + ")";
			}
		};

		var encodeRefLength = function(length) {
			return encodeRefInt(length - settings.minStringLength, 1);
		};

		var decodeRefInt = function(data, width) {
			var 
				value = 0
			,	charCode
			,	i = 0
			;
			for (; i < width; i++) {
				value *= settings.refIntBase;
				charCode = data.charCodeAt(i);
				if ((charCode >= settings.refIntFloorCode) && (charCode <= settings.refIntCeilCode)) {
					value += charCode - settings.refIntFloorCode;
				} else {
					throw "Invalid char code in reference int: " + charCode;
				}
			}
			return value;
		};

		var decodeRefLength = function(data) {
			return decodeRefInt(data, 1) + settings.minStringLength;
		};

		self.compress = function(source, params) {
			setup(params);

			var windowLength = settings.windowLength || settings.defaultWindow;
			if (windowLength > settings.maxWindow) { throw "Window length too large"; }

			var
				compressed = ""
			,	pos = 0
			,	lastPos = source.length - settings.minStringLength
			;
	
			while (pos < lastPos) {
				var
					searchStart = Math.max(pos - windowLength, 0)
				,	matchLength = settings.minStringLength
				,	foundMatch = false
				,	bestMatch = {
						distance: settings.maxStringDistance,
						length: 0
					}
				,	newCompressed = null
				,	isValidMatch
				,	realMatchLength
				;
		
				while ((searchStart + matchLength) < pos) {
					isValidMatch = ((source.substr(searchStart, matchLength) === source.substr(pos, matchLength)) && (matchLength < settings.maxStringLength));
					if (isValidMatch) {
						matchLength++;
						foundMatch = true;
					} else {
						realMatchLength = matchLength - 1;
						if (foundMatch && (realMatchLength > bestMatch.length)) {
							bestMatch.distance = pos - searchStart - realMatchLength;
							bestMatch.length = realMatchLength;
						}
						matchLength = settings.minStringLength;
						searchStart++;
						foundMatch = false;
					}
				}
		
				if (bestMatch.length) {
					newCompressed = settings.refPrefix + encodeRefInt(bestMatch.distance, 2) + encodeRefLength(bestMatch.length);
					pos += bestMatch.length;
				} else {
					if (source.charAt(pos) !== settings.refPrefix) {
						newCompressed = source.charAt(pos);
					} else {
						newCompressed = settings.refPrefix + settings.refPrefix;
					}
					pos++;
				}
				compressed += newCompressed;
			}

			return compressed + source.slice(pos).replace(/`/g, "``");
		};

		self.decompress = function(source, params) {
			var
				decompressed = ""
			,	pos = 0
			,	currentChar
			,	nextChar
			,	distance
			,	length
			;
	
			setup(params);
			while (pos < source.length) {
				currentChar = source.charAt(pos);
				if (currentChar !== settings.refPrefix) {
					decompressed += currentChar;
					pos++;
				} else {
					nextChar = source.charAt(pos + 1);
					if (nextChar !== settings.refPrefix) {
						distance = decodeRefInt(source.substr(pos + 1, 2), 2);
						length = decodeRefLength(source.charAt(pos + 3));
						decompressed += decompressed.substr(decompressed.length - distance - length, length);
						pos += settings.minStringLength - 1;
					} else {
						decompressed += settings.refPrefix;
						pos += 2;
					}
				}
			}
			return decompressed;
		};

		return self;
	}();

	if (typeof define !== 'undefined' && define.amd) {

		define([], function() { return lz77; });
	} else if (typeof module !== 'undefined' && module.exports) {

		module.exports = lz77;
	} else if (attach !== undefined) {

		attach.lz77 = lz77;
	} else {

		this.lz77 = lz77;
	}
})();