/*
 * Copyright (c) 2015, Leon Sorokin
 * All rights reserved. (MIT Licensed)
 *
 * RgbQuant.js - an image quantization lib
 */

/**
 * @namespace RgbQuant
 */
(function() {
	/**
	 * @typedef {Object} Palette
	 * @property {Array} colors - Array of colors, each represented as an array of [R, G, B, A] values.
	 * @property {Array} aInd - Array of indices mapping original colors to the palette.
	 */

	/**
	 * @typedef {Object} Options
	 * @property {number} [colors=256] - Desired number of colors, up to 256.
	 * @property {string} [method=2] - 1 = NeuQuant (older, faster), 2 = WuQuant (newer, slower, better quality).
	 * @property {number} [boxSize=[64,64]] - Bounding box size for mapping image pixels to palette.
	 * @property {number} [boxPxls=2] - Num of pointers stored per box.
	 * @property {number} [initColors=4096] - Number of colors used for initial palette selection.
	 * @property {Function} [progress] - Callback function for progress updates.
	 * @property {Array} [palette] - Pre-defined palette to use.
	 */

	/**
	 * @constructor
	 * @alias RgbQuant
	 * @param {Options} [opts] - Options for quantization.
	 */
	function RgbQuant(opts) {
		opts = opts || {};

		// desired final palette size
		this.colors = opts.colors || 256;
		// # of highest-frequency colors to start with for palette reduction
		this.initColors = opts.initColors || 4096;
		// color-distance threshold for initial reduction pass
		this.initDist = opts.initDist || 0.01;
		// subsequent passes threshold
		this.distIncr = opts.distIncr || 0.005;
		// method: 1 = NeuQuant, 2 = WuQuant
		this.method = opts.method || 2;
		// if > 0, enables handling of alpha transparency
		this.hasAlpha = opts.hasAlpha || false;
		// how many passes to run in collecting histogram
		this.pass = opts.pass === false ? 0 : 1;

		// values that define bounding box for pixels used for palette building
		// if null, uses full image
		this.boxSize = opts.boxSize || [64, 64];
		this.boxPxls = opts.boxPxls || 2;
		// if provided, use this palette (and skip quant)
		this.palette = opts.palette;

		this.pruned = this.palette ? true : false;
		// final reduced palette
		this.pal = null;
		// palette index for referring pixels
		this.pali = null;
		// sorted palette by hue
		this.pals = null;

		// for WuQuant
		this.histogram = {};
		this.vboxes = [];

		this.progress = opts.progress || function() {};

		this.history = {};

		this.setDefault(opts);
	}

	RgbQuant.prototype.setDefault = function(opts) {
		this.pass = (opts.pass === false || this.pruned) ? 0 : 1;
		this.hasAlpha = opts.hasAlpha || false;
		if (this.hasAlpha) {
			this.colors = Math.min(this.colors, 255);
		}
	}

	/**
	 * @param {Image|Array} img - Image element or pixel array.
	 */
	RgbQuant.prototype.sample = function(img) {
		if (this.pass) {
			if (Array.isArray(img) || typeof img.BYTES_PER_ELEMENT === 'number')
				var pixels = img;
			else {
				var c = document.createElement("canvas");
				c.width = img.width;
				c.height = img.height;
				var ctx = c.getContext("2d");
				ctx.drawImage(img, 0, 0);
				var pixels = ctx.getImageData(0, 0, img.width, img.height).data;
			}
			this.collect(pixels);
		}
	};

	RgbQuant.prototype.collect = function(pixels) {
		this.vboxes = [];
		this.histogram = {};

		var vbox = new VBox(0, 0, 0, 0, 0, 0);
		vbox.r1 = vbox.g1 = vbox.b1 = 255;

		var i = 0;
		if (this.boxSize) {
			var width = Math.ceil(Math.sqrt(pixels.length / 4));
			var height = Math.round(pixels.length / 4 / width);
			var bWidth = Math.floor(width / this.boxSize[0]);
			var bHeight = Math.floor(height / this.boxSize[1]);
			var nPix = this.boxPxls;
			var x, y;
			for (var j = 0; j < bWidth; j++) {
				for (var k = 0; k < bHeight; k++) {
					for (var l = 0; l < nPix; l++) {
						x = Math.floor(j * this.boxSize[0] + Math.random() * this.boxSize[0]);
						y = Math.floor(k * this.boxSize[1] + Math.random() * this.boxSize[1]);
						i = (y * width + x) * 4;
						this.addPixel(i, pixels, vbox);
					}
				}
			}
		}
		else {
			for (var len = pixels.length; i < len; i += 4)
				this.addPixel(i, pixels, vbox);
		}
		this.vboxes.push(vbox);
	};

	RgbQuant.prototype.addPixel = function(i, pixels, vbox) {
		var r = pixels[i],
			g = pixels[i+1],
			b = pixels[i+2],
			a = pixels[i+3];

		vbox.r2 = Math.max(vbox.r2, r);
		vbox.g2 = Math.max(vbox.g2, g);
		vbox.b2 = Math.max(vbox.b2, b);

		vbox.r1 = Math.min(vbox.r1, r);
		vbox.g1 = Math.min(vbox.g1, g);
		vbox.b1 = Math.min(vbox.b1, b);

		if (this.method == 1) {
			if (!(r > 250 && g > 250 && b > 250)) {
				this.init_add(
					( (r << 8) + g << 8) + b
				);
			}
		}
		else {
			var ind = getColorIndex(r, g, b);
			if (this.histogram[ind])
				this.histogram[ind]++;
			else
				this.histogram[ind] = 1;
		}
	}

	RgbQuant.prototype.medianCut = function(vboxes) {
		var vbox, cut;
		var i = 0;
		while (i < this.colors - 1) {
			vbox = vboxes.shift();
			cut = vbox.cut(this.histogram);
			vboxes.push.apply(vboxes, cut);
			i++;
		}
	}

	/**
	 * @returns {Palette}
	 */
	RgbQuant.prototype.quantize = function() {
		// short-circuit
		if (this.palette)
			this.pal = this.palette.slice(0);
		else {
			if (this.method == 1) {
				this.prune();
				this.reduce();
			}
			// WuQuant
			else {
				this.medianCut(this.vboxes);

				var pal = [];
				for (var i = 0; i < this.vboxes.length; i++) {
					pal.push(this.vboxes[i].color(this.histogram));
				}
				this.pal = pal;
			}
		}

		if (this.hasAlpha) {
			this.pal.push([0,0,0,0]);
		}

		return this.pal;
	};

	RgbQuant.prototype.reduce = function() {
		this.prune();

		var i = 0;
		var len = this.pal.length;
		var rd = [], gd = [], bd = [];
		while (len > this.colors) {
			var min_d = 1e10, min_i;
			for (i = 0; i < len; i++) {
				for (var j = i + 1; j < len; j++) {
					var d = dist(this.pal[i], this.pal[j]);
					if (d < min_d) {
						min_d = d;
						min_i = [i, j];
					}
				}
			}

			var p1 = this.pal[min_i[0]];
			var p2 = this.pal[min_i[1]];
			var n = this.pali[min_i[0]] + this.pali[min_i[1]];
			var r = (p1[0] * this.pali[min_i[0]] + p2[0] * this.pali[min_i[1]])/n;
			var g = (p1[1] * this.pali[min_i[0]] + p2[1] * this.pali[min_i[1]])/n;
			var b = (p1[2] * this.pali[min_i[0]] + p2[2] * this.pali[min_i[1]])/n;

			this.pal[min_i[0]] = [r,g,b];
			this.pali[min_i[0]] = n;

			this.pal.splice(min_i[1], 1);
			this.pali.splice(min_i[1], 1);

			len--;
		}

		return this.pal;
	};

	RgbQuant.prototype.prune = function() {
		var dist = this.initDist;
		for (var p = 0; p < 5; p++) {
			for (i = 0; i < this.pal.length; i++) {
				for (var j = i + 1; j < this.pal.length; j++) {
					if (dist(this.pal[i], this.pal[j]) < dist) {
						this.pal.splice(j, 1);
						this.pali.splice(j, 1);
					}
				}
			}
			dist += this.distIncr;
		}
	}

	RgbQuant.prototype.init_add = function(color) {
		var pali = this.pali,
			pal = this.pal;

		if (pali[color])
			pali[color]++;
		else {
			pal.push(
				[
					(color >> 16) & 0xff,
					(color >> 8) & 0xff,
					(color) & 0xff
				]
			);
			pali[color] = 1;
		}
	};

	RgbQuant.prototype.init = function(pixels) {
		this.pal = [];
		this.pali = {};

		if (this.boxSize) {
			var width = Math.ceil(Math.sqrt(pixels.length / 4));
			var height = Math.round(pixels.length / 4 / width);
			var bWidth = Math.floor(width / this.boxSize[0]);
			var bHeight = Math.floor(height / this.boxSize[1]);
			var nPix = this.boxPxls;
			var x, y;
			for (var j = 0; j < bWidth; j++) {
				for (var k = 0; k < bHeight; k++) {
					for (var l = 0; l < nPix; l++) {
						x = Math.floor(j * this.boxSize[0] + Math.random() * this.boxSize[0]);
						y = Math.floor(k * this.boxSize[1] + Math.random() * this.boxSize[1]);
						i = (y * width + x) * 4;
						var color = ( (pixels[i] << 8) + pixels[i+1] << 8) + pixels[i+2];
						this.init_add(color);
					}
				}
			}
		}
		else {
			for (var i = 0, len = pixels.length; i < len; i+=4) {
				var color = ( (pixels[i] << 8) + pixels[i+1] << 8) + pixels[i+2];
				this.init_add(color);
			}
		}

		var pal = this.pal,
			pali = this.pali,
			len = pal.length,
			newpal = [],
			newpali = [];

		var hist = [];
		for (var i = 0; i < len; i++) {
			hist[i] = [pali[ ((pal[i][0] << 8) + pal[i][1] << 8) + pal[i][2] ], pal[i]];
		}

		hist.sort(function(a,b) { return b[0] - a[0]; });

		var newlen = Math.min(len, this.initColors);
		this.pal = []; this.pali = [];
		for (var i = 0; i < newlen; i++) {
			this.pal[i] = hist[i][1];
			this.pali[i] = hist[i][0];
		}
	};

	RgbQuant.prototype.map = function(img) {
		if (img instanceof Array)
			var pixels = img;
		else {
			var c = document.createElement("canvas");
			c.width = img.width;
			c.height = img.height;
			var ctx = c.getContext("2d");
			ctx.drawImage(img, 0, 0);
			var pixels = ctx.getImageData(0, 0, img.width, img.height).data;
		}

		var out = new Uint8Array(pixels.length);

		var pal = this.pal;

		for (var i = 0, len = pixels.length; i < len; i+=4) {
			var pi = this.nearest(
				[
					pixels[i],
					pixels[i+1],
					pixels[i+2],
					pixels[i+3],
				]
			);
			out[i]   = pal[pi][0];
			out[i+1] = pal[pi][1];
			out[i+2] = pal[pi][2];
			out[i+3] = pal[pi][3];
		}

		return out;
	}

	RgbQuant.prototype.nearest = function(color) {
		var min_d = 1e10, min_i;
		for (var i = 0; i < this.pal.length; i++) {
			var d = dist(color, this.pal[i]);
			if (d < min_d) {
				min_d = d;
				min_i = i;
			}
		}
		return min_i;
	};

	RgbQuant.prototype.getHex = function() {
		var hex = [];
		for (var i = 0; i < this.pal.length; i++) {
			hex.push(
				"#" + ("000000" + ( (this.pal[i][0] << 16) | (this.pal[i][1] << 8) | this.pal[i][2] ).toString(16)).slice(-6)
			);
		}
		return hex;
	};

	// Rec. 709 (sRGB) luma coeff
	var Pr = .2126, Pl = .0722, Pg = .7152;
	function dist(a, b) {
		var dr = a[0]-b[0],
			dg = a[1]-b[1],
			db = a[2]-b[2];
		return Pr * dr * dr + Pg * dg * dg + Pl * db * db;
	}

	function getColorIndex(r, g, b) {
		return (r << 16) + (g << 8) + b;
	}

	var VBox = (function() {
		var dim = 3,
			shift = 5,
			size = 1 << shift,
			mask = size - 1;

		function VBox(r1, g1, b1, r2, g2, b2) {
			this.r1 = r1; this.g1 = g1; this.b1 = b1;
			this.r2 = r2; this.g2 = g2; this.b2 = b2;
			this._avg = this._cnt = 0;
		}

		VBox.prototype.contains = function(r, g, b) {
			return r >= this.r1 && r <= this.r2 &&
				   g >= this.g1 && g <= this.g2 &&
				   b >= this.b1 && b <= this.b2;
		}

		VBox.prototype.volume = function() {
			return (this.r2 - this.r1) * (this.g2 - this.g1) * (this.b2 - this.b1);
		}

		VBox.prototype.size = function(hist) {
			if (!this._size) {
				var npix = 0,
					r, g, b, ind;
				for (r = this.r1; r <= this.r2; r++) {
					for (g = this.g1; g <= this.g2; g++) {
						for (b = this.b1; b <= this.b2; b++) {
							ind = getColorIndex(r, g, b);
							if (hist[ind])
								npix += hist[ind];
						}
					}
				}
				this._size = npix;
			}

			return this._size;
		}

		VBox.prototype.color = function(hist) {
			if (!this._avg) {
				var mult = 1 << (8 - shift),
					sum = [0,0,0],
					npix = 0,
					r, g, b, ind;

				for (r = this.r1; r <= this.r2; r++) {
					for (g = this.g1; g <= this.g2; g++) {
						for (b = this.b1; b <= this.b2; b++) {
							ind = getColorIndex(r, g, b);
							if (hist[ind]) {
								var h = hist[ind];
								npix += h;
								sum[0] += h * (r + 0.5) * mult;
								sum[1] += h * (g + 0.5) * mult;
								sum[2] += h * (b + 0.5) * mult;
							}
						}
					}
				}

				if (npix) {
					this._avg = [
						~~(sum[0] / npix),
						~~(sum[1] / npix),
						~~(sum[2] / npix)
					];
				}
				else {
					// empty box
					this._avg = [
						~~(mult * (this.r1 + this.r2 + 1) / 2),
						~~(mult * (this.g1 + this.g2 + 1) / 2),
						~~(mult * (this.b1 + this.b2 + 1) / 2)
					];
				}
			}
			return this._avg;
		}

		VBox.prototype.cut = function(hist) {
			var self = this;

			function doCut(dim) {
				var d1 = self[dim + '1'],
					d2 = self[dim + '2'],
					count = 0,
					total = 0,
					sum = 0,
					vbox, cut,
					min, max, i, j, k, ind;

				var left, right;
				if (dim == 'r') { left = 'g'; right = 'b'; }
				else if (dim == 'g') { left = 'r'; right = 'b'; }
				else { left = 'r'; right = 'g'; }

				var partialsum = [], lookaheadsum = [];

				for (i = d1; i <= d2; i++) {
					sum = 0;
					for (j = self[left+'1']; j <= self[left+'2']; j++) {
						for (k = self[right+'1']; k <= self[right+'2']; k++) {
							ind = getColorIndex(
								dim == 'r' ? i : (left == 'r' ? j : k),
								dim == 'g' ? i : (left == 'g' ? j : k),
								dim == 'b' ? i : (left == 'b' ? j : k)
							);
							if (hist[ind])
								sum += hist[ind];
						}
					}
					total += sum;
					partialsum[i] = total;
				}

				for (i = d1; i <= d2; i++) {
					if (partialsum[i] > total / 2) {
						vbox = self.clone();
						cut = self.clone();
						var d2_1 = i - d1, d2_2 = d2 - i;
						if (d2_1 >= d2_2)
							var d2_ = Math.min(d2 - 1, ~~(i + d2_2 / 2));
						else
							var d2_ = Math.max(d1 + 1, ~~(i - d2_1 / 2));

						while (!partialsum[d2_]) d2_++;
						var c = partialsum[d2_ - 1] || 0;
						while (c == partialsum[d2_] && d2_ < d2) d2_++;

						vbox[dim+'2'] = d2_;
						cut[dim+'1'] = d2_ + 1;

						return [vbox, cut];
					}
				}
			}

			var lr = this.r2 - this.r1,
				lg = this.g2 - this.g1,
				lb = this.b2 - this.b1;

			if (lr >= lg && lr >= lb)
				return doCut('r');
			if (lg >= lr && lg >= lb)
				return doCut('g');
			if (lb >= lr && lb >= lg)
				return doCut('b');
		}

		VBox.prototype.clone = function() {
			return new VBox(this.r1, this.g1, this.b1, this.r2, this.g2, this.b2);
		}

		return VBox;
	})();

	// global functions
	this.RgbQuant = RgbQuant;
	this.dist = dist;
}).call(this);

//
// NeuQuant
//
// NeuQuant Neural-Net Quantization Algorithm
// ------------------------------------------
//
// Copyright (c) 1994 Anthony Dekker
//
// E-mail:   dekker@ACM.org
//
// Web:      http://www.scientificcia.com
//
// With my permission you are free to use this code for non-commercial purposes.
// For commercial implementations, please contact me to obtain a licensing agreement.
//
//
// DESCRIPTION:
//
// NeuQuant is a color quantization algorithm that reduces the number of colors
// in a true-color image. It is especially suited for reducing images to 256
// colors and less.
//
// The algorithm is based on a neural network that is trained on the input
// image. The network is a 1D self-organizing map (SOM) that learns the
// distribution of colors in the image. The neurons in the map represent the
// colors in the output palette.
//
// The algorithm proceeds as follows:
//
//  1. The network is initialized with a set of random colors.
//  2. For each pixel in the input image, the neuron that is closest to the
//     pixel's color is found.
//  3. This neuron's color is updated to be closer to the pixel's color.
//  4. The neuron's neighbors are also updated, but by a smaller amount.
//  5. The learning rate and neighborhood size are decreased over time.
//  6. After the network has been trained, the neurons' colors form the
//     output palette.
//
//  7. The input image is then mapped to the output palette by finding the
//     closest color in the palette for each pixel.
//
//  This implementation of the algorithm is based on the original C code by
//  Anthony Dekker. It has been adapted for JavaScript and modified to

if (typeof(module) !== 'undefined') {
	module.exports.RgbQuant = this.RgbQuant;
}