package net.returnvoid.color;

import java.util.ArrayList;
import java.util.HashMap;

import net.returnvoid.tools.ProcessingTools;
import net.returnvoid.tools.RMath;
import net.returnvoid.tools.StringTools;
import net.returnvoid.color.ColorDifferenceMeasure;
import net.returnvoid.color.RColor;
import net.returnvoid.io.ExportHelper;
import net.returnvoid.color.RGBColor;
import net.returnvoid.color.ColorHelper;
import net.returnvoid.color.ColorSpace;
import net.returnvoid.color.ColorDifference;
import processing.core.PApplet;
import processing.core.PImage;
import processing.data.JSONArray;
import processing.data.JSONObject;

/*
 * This code is copyright (c) Diana Lange 2017
 *
 * The library is published under the Creative Commons license NonCommercial 4.0.
 * Please check https://creativecommons.org/licenses/by-nc/4.0/ for more information.
 * 
 * This program is distributed in the hope that it will be useful, but without any warranty.
 */

/**
 * Class for storing multiple colors. The importance of the color within the
 * color palette can be weighted. It is possible to retrieve colors of the
 * palette by: <br>
 * (1) index<br>
 * (2) a given color (will return the most similar color of the palette to the
 * input)<br>
 * (3) random<br>
 * (4) weighted random : more important colors will be returned more often the
 * less important colors<br>
 * 
 * @author Diana Lange
 *
 */
public class ColorPalette {

	/**
	 * Defines which measure to use for calculating the most similar color.
	 */
	private ColorDifferenceMeasure m;

	/**
	 * The colors of the palette
	 */
	private ArrayList<RColor> colors = null;

	/**
	 * Tags for this palette, e.g. \'retro\', \'summer \'. Meant for storing and
	 * retrieving the palette
	 */
	private ArrayList<String> tags = null;

	/**
	 * Name for this palette. Meant for storing and retrieving the palette
	 */
	private String name = "";

	/**
	 * A map containing the color and the importance (> 0, int) of this color
	 * (used for calculating the weighting). The importance can be be any
	 * positive int. But the weighting of all colors in the pallete will always
	 * sum up to 1.
	 */
	private HashMap<Integer, NumberedColor> numberedColors = null;

	/**
	 * A stack to record whether a quantization of an image is done or not. The
	 * stack is indexed by the timestamp of the start of the quantization.
	 */
	private HashMap<String, QuantizeBuilder> quantizeStack = null;

	/**
	 * Sum of all the importances of the colors in this palette. Used for
	 * calculating the weighting.
	 */
	private int sum = 0;

	/**
	 * Minimal Luminance of this palette .
	 */
	private Float minL = null;

	/**
	 * Maximal Luminance of this palette .
	 */
	private Float maxL = null;

	/**
	 * Minimal Chroma of this palette .
	 */
	private Float minC = null;

	/**
	 * Maximal Chroma of this palette .
	 */
	private Float maxC = null;

	/**
	 * Builds an empty color palette.
	 */
	public ColorPalette() {
		this.numberedColors = new HashMap<Integer, NumberedColor>();
		this.quantizeStack = new HashMap<String, QuantizeBuilder>();
		this.tags = new ArrayList<String>();
		this.colors = new ArrayList<RColor>();
		this.m = ColorDifferenceMeasure.RGBEuclidean;
	}

	/**
	 * Builds an ColorPalette out of a JSON-styled String. The String should
	 * look like this:<br>
	 * 
	 * <pre>
	 * {
	 *   "name" : "String",
	 *   "tags" : ["String1","String2",...,"StringN"],
	 *   "colors" : [
	 *      {
	 *        "hexString" : {
	 *           "r" : "float",
	 *           "g" : "float",
	 *           "b" : "float"}
	 *           "a" : "float",
	 *           "importance" : "int"
	 *        }
	 *      }, ...]
	 * }
	 * </pre>
	 * 
	 * <br>
	 * The ranges of r, g, b, a should be within the RGB color range [0, 255].
	 * The importance should be >= 1.
	 * 
	 * @param jsonString The String containing JSON color infos.
	 *
	 */
	public ColorPalette(String jsonString) {

		// set up local attributes
		this.numberedColors = new HashMap<Integer, NumberedColor>();
		this.quantizeStack = new HashMap<String, QuantizeBuilder>();
		this.tags = new ArrayList<String>();
		this.colors = new ArrayList<RColor>();
		this.m = ColorDifferenceMeasure.RGBEuclidean;

		// parse the jsonString to the color palette

		// parse the whole string to a json object
		JSONObject palette = JSONObject.parse(jsonString);

		// load and save the name
		this.setName(palette.getString("name"));

		// load and save the tags
		String[] tags = palette.getJSONArray("tags").getStringArray();

		for (String tag : tags) {
			this.addTag(tag);
		}

		// get the color objects
		JSONArray jsoncolors = palette.getJSONArray("colors");

		// iterate over all color objects
		for (int i = 0; i < jsoncolors.size(); i++) {

			// get current color object
			JSONObject colorObj = jsoncolors.getJSONObject(i);

			// get the key of the current color object (has always only one key
			// and this is the hexString representation of the color)
			String colorKey = (String) (colorObj.keys().toArray()[0]);

			// get the object which contains the actual color values
			JSONObject colorValues = colorObj.getJSONObject(colorKey);

			// build a RGBColor from the received values
			RGBColor rgb = new RGBColor(colorValues.getFloat("r"), colorValues.getFloat("g"),
					colorValues.getFloat("b"));
			rgb.setAlpha(colorValues.getFloat("a"));

			// get the importance of that color
			int importance = colorValues.getInt("importance");

			// save the color to this palette
			this.add(rgb, importance);
		}
	}

	/**
	 * Creates a color palette with the given colors. All colors will be
	 * weighted equally important.
	 * 
	 * @param colors
	 *            The colors of the palette.
	 */
	public ColorPalette(RColor[] colors) {
		this();
		this.sum = colors.length;

		for (RColor c : colors) {
			this.colors.add(c);
		}

		for (RColor c : colors) {
			this.numberedColors.put(c.getColor(), new NumberedColor(c, 1));
		}

		if (colors.length > 0) {
			this.m = colors[0].getColorSpace().toColorDifferenceMeasure();
		}
	}

	/**
	 * Creates a color palette with the given colors. All colors will be
	 * weighted equally important.
	 * 
	 * @param colors
	 *            The colors of the palette.
	 */
	public ColorPalette(ArrayList<RColor> colors) {
		this();
		this.sum = colors.size();
		this.colors.addAll(colors);

		for (RColor c : colors) {
			this.numberedColors.put(c.getColor(), new NumberedColor(c, 1));
		}

		if (colors.size() > 0) {
			this.m = colors.get(0).getColorSpace().toColorDifferenceMeasure();
		}
	}

	/**
	 * Creates a color palette with the given colors. All colors will be
	 * weighted equally important. All input colors given will be converted to
	 * RColor.
	 * 
	 * @param colors
	 *            The colors of the palette.
	 */
	public ColorPalette(int[] colors) {
		this();
		this.sum = colors.length;

		for (int c : colors) {
			this.colors.add(RGBColor.toRGB(c));
		}

		for (int c : colors) {
			RGBColor rgb = RGBColor.toRGB(c);
			this.numberedColors.put(c, new NumberedColor(rgb, 1));
		}
	}

	/**
	 * Returns the maximal luminance (perceived brightness) of the palette.
	 * 
	 * @return The maximal Luminance of this palette.
	 */
	public Float getMaxLuminance() {
		if (maxL == null) {
			ArrayList<RColor> copies = ColorHelper.copy(colors);
			ColorHelper.convert(copies, ColorSpace.LCHColor);
			this.maxL = RMath.max('l', copies.toArray(new RColor[copies.size()]));
		}

		return maxL;
	}

	/**
	 * Returns the minimal luminance (perceived brightness) of the palette.
	 * 
	 * @return The minimal Luminance of this palette.
	 */
	public Float getMinLuminance() {
		if (minL == null) {
			ArrayList<RColor> copies = ColorHelper.copy(colors);
			ColorHelper.convert(copies, ColorSpace.LCHColor);
			this.minL = RMath.min('l', copies.toArray(new RColor[copies.size()]));
		}

		return minL;
	}

	/**
	 * Returns the maximal chroma (perceived saturation) of the palette.
	 * 
	 * @return - The maximal chroma of this palette.
	 */
	public Float getMaxChroma() {
		if (maxC == null) {
			ArrayList<RColor> copies = ColorHelper.copy(colors);
			ColorHelper.convert(copies, ColorSpace.LCHColor);
			this.maxC = RMath.max('c', copies.toArray(new RColor[copies.size()]));
		}

		return maxC;
	}

	/**
	 * Returns the minimal chroma (perceived saturation) of the palette.
	 * 
	 * @return The minimal chroma of this palette.
	 */
	public Float getMinChroma() {
		if (minC == null) {
			ArrayList<RColor> copies = ColorHelper.copy(colors);
			ColorHelper.convert(copies, ColorSpace.LCHColor);
			this.minC = RMath.min('c', copies.toArray(new RColor[copies.size()]));
		}

		return minC;
	}

	/**
	 * Returns the most important color of this palette. If all colors are
	 * equally important the first color will be returned.
	 * 
	 * @return The most important color.
	 */

	public RColor getMostImportantColor() {
		int index = 0;
		int maxImportance = 0;

		for (int i = 0; i < this.colors.size(); i++) {
			NumberedColor nc = this.numberedColors.get(colors.get(i).getColor());

			if (nc.importance > maxImportance) {
				index = i;
				maxImportance = nc.importance;
			}
		}

		return this.colors.get(index);
	}

	/**
	 * Returns the current ColorDifferenceMeasure. The measure defines how the
	 * most similar color is calculated using the get(RColor) method and how
	 * colors are merged in reduceSize(int).
	 * 
	 * @return The current ColorDifferenceMeasure.
	 */
	public ColorDifferenceMeasure getColorDifferenceMeasure() {
		return this.m;
	}

	/**
	 * Returns the current ColorSpace.
	 * 
	 * @return The current ColorSpace.
	 */
	public ColorSpace getColorSpace() {
		return this.m.toColorSpace();
	}

	/**
	 * Calculates the sum of the importance numbers of all member colors. Should
	 * be called whenever there is a change in the number of colors or a change
	 * of the importance of any color.
	 */
	private void updateSum() {
		sum = 0;
		for (NumberedColor c : numberedColors.values()) {
			sum += c.importance;
		}
	}

	/**
	 * Sets the measure which will be used to calculate the most similar color
	 * from an input to one of the palette's color. Used in get() method. When
	 * this called, the measure will be set to the Euclidean distance of the
	 * input color space.
	 * 
	 * @param space
	 *            The new color space of this palette.
	 * @return The current ColorPalette object.
	 */
	public ColorPalette setColorSpace(ColorSpace space) {
		ColorDifferenceMeasure oldM = this.m;
		this.m = space.toColorDifferenceMeasure();

		if (oldM.toColorSpace() != space) {

			this.convertColors();
		}

		return this;
	}

	/**
	 * Sets the measure which will be used to calculate the most similar color
	 * from an input to one of the palette's color. Used in get() method. When
	 * this called, the measure will be set to the Euclidean distance of the
	 * input color space.
	 * 
	 * @param c
	 *            One color.
	 * @return The current ColorPalette object.
	 */
	public ColorPalette setColorSpace(RColor c) {
		return this.setColorSpace(c.getColorSpace());
	}

	/**
	 * Sets the ColorDifferenceMeasure. The measure defines how the most similar
	 * color is calculated using the get(RColor) method and how colors are
	 * merged in reduceSize(int). All member colors are converted to the color
	 * space which correlates to this measure.
	 * 
	 * @param m
	 *            A ColorDifferenceMeasure. e.g.
	 *            ColorDifferenceMeasure.RGBEuclidean.
	 * @return The current ColorPalette object.
	 */
	public ColorPalette setColorDifferenceMeasure(ColorDifferenceMeasure m) {
		ColorDifferenceMeasure oldM = this.m;
		this.m = m;

		if (oldM.toColorSpace() != m.toColorSpace()) {

			this.convertColors();
		}

		return this;
	}

	/**
	 * Converts all member colors to the current set color space.
	 */
	private void convertColors() {
		ColorSpace space = m.toColorSpace();

		ArrayList<Integer[]> keymismatch = new ArrayList<Integer[]>();
		ArrayList<RColor> keymismatchColor = new ArrayList<RColor>();

		for (int i = 0; i < colors.size(); i++) {
			RColor oldColor = colors.get(i);
			RColor newColor = ColorHelper.convert(colors.get(i), space);
			int oldKey = oldColor.getColor();
			int newKey = newColor.getColor();

			// update color in array and in map
			this.colors.set(i, newColor);
			NumberedColor nc = this.numberedColors.get(oldKey);
			nc.c = newColor;

			// due the conversion the key might not be exactly the same
			// save mismatches to correct the keys in the map afterwards
			if (oldKey != newKey) {
				keymismatch.add(new Integer[] { oldKey, newKey });
				keymismatchColor.add(newColor);
			}
		}

		// correct the keys in the map afterwards
		for (int i = 0; i < keymismatch.size(); i++) {
			NumberedColor nc = this.numberedColors.get(keymismatch.get(i)[0]);
			// remove it old key and add the same object under the new key
			this.numberedColors.remove(keymismatch.get(i)[0]);
			this.numberedColors.put(keymismatch.get(i)[1], nc);
		}

		// min and max Luminance have to be re-calculated
		this.minL = this.maxL = null;
		this.minC = this.maxC = null;
	}

	/**
	 * Calculates the weighting of a color. The sum of all weightings of all
	 * color of the palette sums up to 1.
	 * 
	 * @param c
	 *            The color of which the weighing should be returned.
	 * @return The input's weighting or 0 if input is not member of the palette.
	 */
	public float getWeighting(RColor c) {
		if (this.numberedColors.containsKey(c.getColor())) {
			return (float) this.numberedColors.get(c.getColor()).importance / this.sum;
		} else {
			return 0;
		}
	}

	/**
	 * Adds a tag (e.g. \'summer\', \'colorful\', ...) which should be
	 * associated to the palette.
	 * 
	 * @param tag
	 *            The tag.
	 * @return The current ColorPalette object.
	 */
	public ColorPalette addTag(String tag) {
		tags.add(tag);
		return this;
	}

	/**
	 * Adds one or more tags (e.g. \'summer\', \'colorful\', ...) which should
	 * be associated to the palette.
	 * 
	 * @param tags
	 *            The tags.
	 * @return The current ColorPalette object.
	 */
	public ColorPalette addTags(String... tags) {
		for (String tag : tags) {
			this.tags.add(tag);
		}
		return this;
	}

	/**
	 * Removes the given tag from the tag list associated with this palette.
	 * 
	 * @param tag
	 *            The tag to be removed.
	 * @return The current ColorPalette object.
	 */
	public ColorPalette removeTag(String tag) {
		for (String t : tags) {
			if (t.equals(tag)) {
				tags.remove(t);
				break;
			}
		}
		return this;
	}

	/**
	 * Returns all tags associated with this palette.
	 * 
	 * @return The tag list.
	 */
	public ArrayList<String> getTags() {
		return this.tags;
	}

	/**
	 * Sets a name which will be associated with this palette. The name will
	 * also be used for saving this palette (to file / json).
	 * 
	 * @param name
	 *            The new name of this palette.
	 * @return The current ColorPalette object.
	 */
	public ColorPalette setName(String name) {
		this.name = name;
		return this;
	}

	/**
	 * Removes the currently set name for this palette.
	 * 
	 * @return The current ColorPalette object.
	 */
	public ColorPalette removeName() {
		this.name = "";
		return this;
	}

	/**
	 * Returns the currently set name of this palette.
	 * 
	 * @return The palette's name.
	 */
	public String getName() {
		return this.name;
	}

	/**
	 * Adds a color to this palette. The importance will be weighted with 1. The
	 * input will be converted to RColor.
	 * 
	 * @param c
	 *            The color which will be added to the palette.
	 * @return The current ColorPalette object.
	 */
	public ColorPalette add(int c) {
		return this.add(RGBColor.toRGB(c), 1);
	}

	/**
	 * Adds a color to this palette. The input will be converted to RColor.
	 * 
	 * @param c
	 *            The color which will be added to the palette.
	 * @param importance
	 *            The importance value > 1 of this color.
	 * @return The current ColorPalette object.
	 */
	public ColorPalette add(int c, int importance) {
		return this.add(RGBColor.toRGB(c), importance);
	}

	/**
	 * Adds a color to this palette. The importance will be weighted with 1.
	 * 
	 * @param c
	 *            - The color which will be added to the palette.
	 * @return The current ColorPalette object.
	 */
	public ColorPalette add(RColor c) {
		return this.add(c, 1);
	}

	/**
	 * Adds a color to this palette.
	 * 
	 * @param c
	 *            The color which will be added to the palette.
	 * @param importance
	 *            The importance value > 1 of this color.
	 * @return The current ColorPalette object.
	 */
	public ColorPalette add(RColor c, int importance) {
		if (!this.numberedColors.containsKey(c.getColor())) {
			if (importance < 1) {
				importance = 1;
			}

			// the first color added will set up the used color difference
			// measure
			if (this.colors.size() == 0) {
				this.m = c.getColorSpace().toColorDifferenceMeasure();
			}

			// min and max Luminance have to be re-calculated
			this.minL = this.maxL = null;
			this.minC = this.maxC = null;

			// add color to lists
			this.colors.add(c);
			this.numberedColors.put(c.getColor(), new NumberedColor(c, importance));

			// recalculate the sum of all importances
			this.updateSum();
		}
		return this;
	}

	/**
	 * Resets the importance of all member colors of the palette to 1 (all
	 * colors are weighted equally).
	 * 
	 * @return The current ColorPalette object.
	 */
	public ColorPalette resetImportance() {
		for (RColor c : this.colors) {
			NumberedColor nc = this.numberedColors.get(c.getColor());
			nc.importance = 1;
			this.updateSum();
		}

		return this;
	}

	/**
	 * Increases the importance of the given color.
	 * 
	 * @param c
	 *            The color of which the importance should be increased.
	 * @param howMuch
	 *            A positive number which will be added to the current
	 *            importance.
	 * @return The current ColorPalette object.
	 */
	public ColorPalette increaseImportance(RColor c, int howMuch) {
		if (this.numberedColors.containsKey(c) && howMuch > 0) {
			NumberedColor nc = this.numberedColors.get(c);
			nc.importance += RMath.abs(howMuch);
			this.updateSum();
		}

		return this;
	}

	/**
	 * Sets the importance of a color. The given color should already be member
	 * of the palette.
	 * 
	 * @param c
	 *            - The color of which the importance should be set.
	 * @param importance
	 *            - The importance value > 0 for the input color.
	 * @return The current ColorPalette object.
	 */
	public ColorPalette applyImportance(RColor c, int importance) {

		return applyImportance(c.getColor(), importance);
	}

	/**
	 * Sets the importance of a color. The given color should already be member
	 * of the palette.
	 * 
	 * @param c
	 *            The color of which the importance should be set.
	 * @param importance
	 *            The importance value > 0 for the input color.
	 * @return The current ColorPalette object.
	 */
	public ColorPalette applyImportance(int c, int importance) {
		if (this.numberedColors.containsKey(c) && importance > 0) {
			NumberedColor nc = this.numberedColors.get(c);
			nc.importance = importance;
			this.updateSum();
		}

		return this;
	}

	/**
	 * Sets the importances of the palettes colors. The input array should be
	 * the same size as the number of colors of this palette as well as they
	 * should be alligned. The first importance value will be used for the first
	 * color of the palette and so on. Better use applyImportance(int c, int
	 * importance) or applyImportance(RColor c, int importance) if you are not
	 * sure about the color's sorting.
	 * 
	 * @param importances
	 *            - The importance values > 0 for all colors of the palette.
	 * @return The current ColorPalette object.
	 */
	public ColorPalette applyImportance(int[] importances) {
		for (int i = 0; i < importances.length && i < this.colors.size(); i++) {
			RColor c = this.colors.get(i);
			NumberedColor nc = this.numberedColors.get(c.getColor());
			if (importances[i] > 0) {
				nc.importance = importances[i];
			}
		}
		this.updateSum();
		return this;
	}

	/**
	 * Removes the given color from the palette.
	 * 
	 * @param c
	 *            The color which should be removed.
	 * @return The current ColorPalette object.
	 */
	public ColorPalette remove(RColor c) {

		if (this.numberedColors.containsKey(c.getColor())) {
			// min and max Luminance have to be re-calculated
			this.minL = this.maxL = null;
			this.minC = this.maxC = null;

			// remove the color
			this.numberedColors.remove(c.getColor());

			this.colors.remove(c);

			this.updateSum();
		}

		return this;
	}

	/**
	 * Removes the given color from the palette.
	 * 
	 * @param c
	 *            The color which should be removed.
	 * @return The current ColorPalette object.
	 */
	public ColorPalette remove(int c) {
		if (this.numberedColors.containsKey(c)) {

			return remove(this.numberedColors.get(c).c);
		}

		return this;
	}

	/**
	 * Merges two color palettes - adds another color palette to this one.
	 * 
	 * @param other
	 *            Any other color palette. Duplicate colors are allowed. "other"
	 *            will not be changed by this method.
	 * @return The current ColorPalette object.
	 */
	public ColorPalette merge(ColorPalette other) {

		for (int i = 0; i < other.size(); i++) {
			RColor otherColor = other.get(i);
			int otherImportance = other.numberedColors.get(otherColor.getColor()).importance;

			// color is already part of this color palette
			if (this.numberedColors.containsKey(otherColor.getColor())) {
				this.increaseImportance(this.numberedColors.get(otherColor.getColor()).c, otherImportance);
				continue;
			}

			// add new colors from other palette
			this.add(otherColor, otherImportance);
		}

		return this;
	}

	/**
	 * Sorts the colors by luminance beginning with the lowest luminance.
	 * 
	 * @return The current color palette.
	 */
	public ColorPalette sort() {
		return sort("luminance");

	}

	/**
	 * Sorts the colors by a parameter beginning with the lowest.
	 * 
	 * @param how
	 *            Defines how the palette is sorted. Possible parameters are:
	 *            "luminance", "chroma", "hue" (hue in HSB), "huelch (hue in
	 *            CieLCH), "brightness", "saturation", "red", "green", "blue",
	 *            "weighting".
	 * 
	 * @return The current color palette.
	 */
	public ColorPalette sort(String how) {

		how = how.toLowerCase();

		int mode = 0; // luminance
		if (how.equals("luminance")) {
			mode = 0;
		} else if (how.equals("hue")) {
			mode = 1;
		} else if (how.equals("chroma")) {
			mode = 2;
		} else if (how.equals("brightness")) {
			mode = 3;
		} else if (how.equals("saturation")) {
			mode = 4;
		} else if (how.equals("red")) {
			mode = 5;
		} else if (how.equals("green")) {
			mode = 6;
		} else if (how.equals("blue")) {
			mode = 7;
		} else if (how.equals("weighting")) {
			mode = 8;
		} else {
			// hue in LCHColor space
			mode = 9;
		}

		boolean sorted = false;
		while (!sorted) {
			sorted = true;

			for (int i = 0; i < this.colors.size() - 1; i++) {
				Float val1 = 0f;
				Float val2 = 0f;

				switch (mode) {
				case 0:
					val1 = this.colors.get(i).toLab().getLuminance();
					val2 = this.colors.get(i + 1).toLab().getLuminance();
					break;
				case 1:
					val1 = this.colors.get(i).toHSB().getHue();
					val2 = this.colors.get(i + 1).toHSB().getHue();
					break;
				case 2:
					val1 = this.colors.get(i).toLab().getChroma();
					val2 = this.colors.get(i + 1).toLab().getChroma();
					break;
				case 3:
					val1 = this.colors.get(i).toHSB().getBrightness();
					val2 = this.colors.get(i + 1).toHSB().getBrightness();
					break;
				case 4:
					val1 = this.colors.get(i).toHSB().getSaturation();
					val2 = this.colors.get(i + 1).toHSB().getSaturation();
					break;
				case 5:
					val1 = this.colors.get(i).toRGB().getRed();
					val2 = this.colors.get(i + 1).toRGB().getRed();
					break;
				case 6:
					val1 = this.colors.get(i).toRGB().getGreen();
					val2 = this.colors.get(i + 1).toRGB().getGreen();
					break;
				case 7:
					val1 = this.colors.get(i).toRGB().getBlue();
					val2 = this.colors.get(i + 1).toRGB().getBlue();
					break;
				case 8:
					val1 = this.getWeighting(this.colors.get(i));
					val2 = this.getWeighting(this.colors.get(i + 1));
					break;
				case 9:
					val1 = this.colors.get(i).toLCH().getHue();
					val2 = this.colors.get(i + 1).toLCH().getHue();
					break;
				default:
					val1 = this.colors.get(i).toLab().getLuminance();
					val2 = this.colors.get(i + 1).toLab().getLuminance();
					break;
				}

				if (val1 < val2) {
					RColor tmp = this.colors.get(i);
					this.colors.set(i, this.colors.get(i + 1));
					this.colors.set(i + 1, tmp);
					sorted = false;
				}
			}
		}

		return this;

	}

	/**
	 * Creates a true copy of this palette.
	 * 
	 * @return The copied palette.
	 */
	public ColorPalette copy() {
		ColorPalette copy = new ColorPalette();
		copy.m = this.m;
		copy.maxC = this.maxC != null ? new Float(this.maxC) : null;
		copy.maxL = this.maxL != null ? new Float(this.maxL) : null;
		copy.minC = this.minC != null ? new Float(this.minC) : null;
		copy.minL = this.minL != null ? new Float(this.minL) : null;

		copy.name = new String(this.name);
		for (String tag : this.tags) {
			copy.tags.add(new String(tag));
		}

		for (RColor color : this.colors) {
			copy.add(color.copy());
			copy.applyImportance(color.getColor(), this.numberedColors.get(color.getColor()).importance);
		}

		return copy;
	}

	/**
	 * Reduces the number of colors to the given <b>size</b>. The reduction is
	 * done by detecting similar colors in the palette and incremental merging
	 * them.
	 * 
	 * @param size
	 *            The new number of colors for this palette (size > 1 and size <
	 *            palette.size()).
	 * @return The current palette.
	 */
	public ColorPalette reduceSize(int size) {
		size = RMath.abs(size);
		if (size < 1) {
			size = 1;
		}

		while (this.size() > size) {

			// find the most similar color for each

			// key: colorIndex1, colorIndex2
			// value: difference of colorIndex1 to colorIndex2
			HashMap<String, Float> indexToDiffMap = new HashMap<String, Float>();
			float diff = 0;
			float minDiff = 100000;
			int minDiffIndex = 0;
			for (int i = 0; i < this.colors.size(); i++) {
				diff = 0;
				minDiff = 10000;
				minDiffIndex = 0;
				for (int j = i + 1; j < this.colors.size(); j++) {

					diff = ColorDifference.difference(this.colors.get(i), this.colors.get(j), m);

					if (diff < minDiff) {
						minDiff = diff;
						minDiffIndex = j;
					}

				}

				String key = i + "," + minDiffIndex;
				indexToDiffMap.put(key, minDiff);
			}

			// find the lowest difference for all colors
			minDiff = 100000;
			String minDiffKey = "";
			for (String key : indexToDiffMap.keySet()) {
				if (indexToDiffMap.get(key) < minDiff) {
					minDiffKey = key;
					minDiff = indexToDiffMap.get(key);
				}
			}

			// merge the colors with highest similarity
			String[] indexes = minDiffKey.split(",");

			int index1 = Integer.parseInt(indexes[0]);
			int index2 = Integer.parseInt(indexes[1]);

			// create mixed color and get sum of importance
			RColor mergedColor = ColorHelper.getMeanColor(m, this.colors.get(index1), this.colors.get(index2));

			int sumOfMergedColor = this.numberedColors.get(this.colors.get(index1).getColor()).importance
					+ this.numberedColors.get(this.colors.get(index2).getColor()).importance;

			// remove old colors
			this.remove(this.colors.get(index2));
			this.remove(this.colors.get(index1));

			// add merged color
			this.add(mergedColor, sumOfMergedColor);
		}
		return this;
	}

	/**
	 * Returns the number of colors in this palette.
	 * 
	 * @return The number of colors in this palette.
	 */
	public int size() {
		return colors.size();
	}

	/**
	 * Returns a random color of the color palette.
	 * 
	 * @return A color of the palette or null if there is no color in the
	 *         palette.
	 */
	public RColor getRandom() {
		if (colors.size() == 0) {
			return null;
		}

		// System.err.println("randomm color");

		return colors.get(RMath.random(colors.size()));
	}

	/**
	 * Returns a random color of the color palette by the color's importance.
	 * This means that this method will return the color with a high importance
	 * more often then the color with low importance.
	 * 
	 * @return A color of the palette or null if there is no color in the
	 *         palette.
	 */
	public RColor getRandomWeighted() {
		if (this.sum == colors.size()) {
			return getRandom();
		}

		float rval = RMath.random((float) sum);
		int importanceSum = 0;
		RColor foundColor = null;
		for (Integer key : this.numberedColors.keySet()) {
			// System.out.println(key);
			NumberedColor nc = this.numberedColors.get(key);
			if (importanceSum <= rval && rval < (importanceSum + nc.importance)) {
				foundColor = nc.c;

				break;
			}

			importanceSum += nc.importance;
		}

		if (foundColor == null) {
			foundColor = getRandom();
		}

		return foundColor;
	}

	/**
	 * Returns a color of the palette which is similar to the input color (but
	 * maybe not the most similar color).
	 * 
	 * @param c
	 *            The input color.
	 * @param dithering
	 *            The value for the dithering (0, 1).
	 * @return A color of the palette.
	 */
	public RColor getDithered(RColor c, float dithering) {

		dithering *= 0.95;

		if (dithering < 0) {
			return get(c);
		} else if (dithering > 0.95) {
			dithering = 0.95f;
		}

		// find the most similar color to the input and the second
		// most similar and the most different color
		// the most different color is needed to calculate the range
		// of difference values for the input
		float lowestDist = 10000000;
		float secondLowestDist = 10000000;
		float hightestDist = 0;

		int lowestDistIndex = 0;
		int secondLowestDistIndex = 0;

		float diff = 0;
		for (int i = 0; i < colors.size(); i++) {
			diff = ColorDifference.difference(c, colors.get(i), m);

			if (diff < lowestDist) {
				lowestDist = diff;
				lowestDistIndex = i;
			} else if (diff < secondLowestDist) {
				secondLowestDist = diff;
				secondLowestDistIndex = i;
			}

			if (diff > hightestDist) {
				hightestDist = diff;
			}
		}

		// calculate the range of differences for the input
		float range = hightestDist - lowestDist;

		// calculate the range between first and second most similar colors
		float firstRange = secondLowestDist - lowestDist;

		// find mean difference range
		float meanRange = (range / (colors.size() - 1));

		// evaluate firstRange against meanRange i.e. how confident is that the
		// found most similar color is the real most similar color (firstRange
		float amt = 1 - firstRange / meanRange;
		float rand = RMath.random(0, amt);

		return rand <= (1 - dithering) ? colors.get(lowestDistIndex) : colors.get(secondLowestDistIndex);

	}

	/**
	 * Replaces all colors of all pixels of the input image with a color of the
	 * palette. Creates a quantized and dithered image. The returned String can
	 * be used to determined wheter the quantization is fished or not. Example
	 * usage:<br>
	 * 
	 * <pre>
	 * String stamp = myPalette.getDithered(myImage, 0.25);
	 * 
	 * &frasl;&frasl; return true when all pixels of the input image have been
	 * &frasl;&frasl; replaced
	 * boolean finished = myPalette.finishedImage(stamp);
	 * </pre>
	 * 
	 * @param img
	 *            The input image.
	 * @param dithering
	 *            The value for the dithering (0, 1).
	 * @return A timestamp (time when the quanitization started).
	 */
	public String getDithered(PImage img, float dithering) {

		/*
		 * RGBColor rgb = new RGBColor(0); img.loadPixels(); for (int i = 0; i <
		 * img.pixels.length; i++) { // get color of current pixel and use it to
		 * set the color // of the rgb object rgb.set(img.pixels[i]);
		 * 
		 * // override the pixel color with the color of the palette
		 * img.pixels[i] = this.getDithered(rgb, dithering).getColor(); }
		 * 
		 * img.updatePixels();
		 */

		int threadsNum = img.pixels.length / 30000;
		threadsNum = RMath.constrain(threadsNum, 4, 30);

		QuantizeBuilder builder = new QuantizeBuilder(img, threadsNum, 1, dithering);
		return builder.timestamp;
	}

	/**
	 * Returns a color of the palette which is similar to the input color. A
	 * little random is added so not everytime the function is called with same
	 * parameters the output will be the same. The amt value sets how much
	 * likely the color of the palette will be the most similar color to the
	 * input. The lower amt is, the more likely the output will be the most
	 * similar color to the input. The higher amt is, the more likely the output
	 * will be the second most similar color to the input. If amt ist smaller or
	 * equal to zero, the output will be the same as get(RColor). If not defined
	 * otherwise, the Euclidean distance of the colors space of the color
	 * palette's colors will be used for the calculation of the similarity.
	 * 
	 * @param c
	 *            The input color.
	 * @param amt
	 *            The value for the noise (>= 0).
	 * @return A color of the palette.
	 */
	public RColor getNoisy(RColor c, float amt) {

		if (amt < 0) {
			return get(c);
		}

		// get the color that is most similar to the input
		int index = ColorDifference.getMostSimilarColor(c, colors, m);
		RColor c1 = index == -1 ? getRandom() : colors.get(index);

		// get the second most similar color
		int index2 = ColorDifference.getMostSimilarColor(c1, colors, true, m);
		RColor c2 = index2 == -1 ? getRandom() : colors.get(index2);

		// calculate the differces to the input
		float diff1 = ColorDifference.difference(c, c1, m); // low
		float diff2 = ColorDifference.difference(c, c2, m); // high

		/*
		 * scale the random range so the outcome will not depend on the values
		 * of the difference (which depends on the chosen measure) but from the
		 * distance of the two diff values. The random range for the actual most
		 * similar color of the input will always be smaller than the other one.
		 * But the span of random(min, max) will depend on the given amt value.
		 * the higher the amt value the higher the span will be and the higher
		 * it will be more likely that the second most similar color will be
		 * chosen. The smaller the span the more likely the first most similar
		 * color will be chosen
		 */

		float abs = RMath.abs(diff1 - diff2);
		float startDiff = diff1 - abs * amt;
		float r1 = RMath.random(startDiff, diff1);
		float r2 = RMath.random(startDiff, diff2);

		// the color of the smaller random value will be returned
		return r1 > r2 ? c2 : c1;
	}

	/**
	 * Replaces all colors of all pixels of the input image with a color of the
	 * palette. Creates a noisy quantized. The returned String can be used to
	 * determined wheter the quantization is fished or not. Example usage:<br>
	 * 
	 * <pre>
	 * String stamp = myPalette.getNoisy(myImage, 0.25);
	 * 
	 * &frasl;&frasl; return true when all pixels of the input image have been
	 * &frasl;&frasl; replaced
	 * boolean finished = myPalette.finishedImage(stamp);
	 * </pre>
	 * 
	 * @param img
	 *            The input image.
	 * @param amt
	 *            The value for the noise (>= 0).
	 * @return A timestamp (time when the quanitization started).
	 */
	public String getNoisy(PImage img, float amt) {

		int threadsNum = img.pixels.length / 30000;
		threadsNum = RMath.constrain(threadsNum, 4, 30);

		QuantizeBuilder builder = new QuantizeBuilder(img, threadsNum, 2, amt);
		return builder.timestamp;
	}

	/**
	 * Returns a color of the palette which is similar to the input color. If
	 * not defined otherwise, the Euclidean distance of the colors space of the
	 * color palette's colors will be used for the calculation of the
	 * similarity.
	 * 
	 * @param c
	 *            The input color.
	 * 
	 * @return A color of the palette.
	 */
	public RColor get(RColor c) {

		if (colors.size() == 0) {
			return null;
		}

		int index = ColorDifference.getMostSimilarColor(c, colors, m);

		if (index == -1) {
			return getRandom();
		}

		return colors.get(index);
	}

	/**
	 * Replaces all colors of all pixels of the input image with a color of the
	 * palette. Creates a quantized image. The returned String can be used to
	 * determined wheter the quantization is fished or not. Example usage:<br>
	 * 
	 * <pre>
	 * String stamp = myPalette.get(myImage);
	 * 
	 * &frasl;&frasl; return true when all pixels of the input image have been
	 * &frasl;&frasl; replaced
	 * boolean finished = myPalette.finishedImage(stamp);
	 * </pre>
	 * 
	 * @param img
	 *            The input image.
	 * @return A timestamp (time when the quanitization started).
	 */
	public String get(PImage img) {
		int threadsNum = img.pixels.length / 30000;
		threadsNum = RMath.constrain(threadsNum, 4, 30);

		QuantizeBuilder builder = new QuantizeBuilder(img, threadsNum);
		return builder.timestamp;
	}

	/**
	 * Returns the color at the given index or null if the index is out of
	 * bounds. You can get the number of colors by using the ColorPalette's
	 * size() function.
	 * 
	 * @param index
	 *            The index of the color which should be returned.
	 * @return A color of the palette.
	 */
	public RColor get(int index) {
		if (index < 0 || index >= colors.size()) {
			return null;
		}
		return this.colors.get(index);
	}

	/**
	 * Finds a lerped color within the color palette.
	 * 
	 * @param tplusi
	 *            The parameter describes the returned color's position within
	 *            the palette. It is calculated with t + i, where t is a float
	 *            in range of [0, 1) and i is an int in range of [0, size() -
	 *            1). For example, if the color in the middle of the first and
	 *            second color of the palette should be returned, than i=1 and
	 *            t=0.5 and therefor tplusi=1.5.
	 * @return A RColor.
	 */
	public RColor find(float tplusi) {
		int i = (int) tplusi;

		if (i < 0) {
			i = 0;
		} else if (i >= colors.size() - 1) {
			i = colors.size() - 2;
		}
		float amt = tplusi - i;

		return ColorHelper.lerpColors(colors.get(i), colors.get(i + 1), amt);
	}

	/**
	 * Returns the index of the most similar color to the input color. If not
	 * defined otherwise, the Euclidean distance of the colors space of the
	 * color palette's colors will be used for the calculation of the
	 * similarity.
	 * 
	 * @param c
	 *            The input color.
	 * @return The index of the most similar color.
	 */
	public int getIndex(RColor c) {

		int index = ColorDifference.getMostSimilarColor(c, colors, m);

		return index;
	}

	/**
	 * Returns whether a quantization of an image is finished. The input String
	 * should be the timestamp when the quantization started (this String is
	 * returned by the get(PImage), getDithered(PImage, float), getNoisy(PImage,
	 * float) methods).
	 * 
	 * @param timestamp
	 *            The timestamp of the start of quantization.
	 * @return True if quantization is still in process. False if quantization
	 *         is finished or input String could not be found.
	 */
	public boolean finishedImage(String timestamp) {
		return !this.quantizeStack.containsKey(timestamp);
	}

	/**
	 * Creates a String representation of one color in the form of:<br>
	 * 
	 * <pre>
	 * {
	 *  "hexColorString" : {
	 * 	"r" : "floatRed",
	 * 	"g" : "floatGreen",
	 * 	"b" : "floatBlue",
	 * 	"a" : "floatAlpha",
	 * 	"importance" : "positiveInt"
	 * }}
	 * </pre>
	 * 
	 * Used for building a JSON String.
	 * 
	 * @param c
	 *            The input color.
	 * @return - A String representing the color information.
	 */
	private String getColorString(RColor c) {
		String txt = "{";
		RGBColor rgb = c.toRGB();
		txt += StringTools.getStringEcp(rgb.getOpHexString()) + " : {";
		txt += StringTools.getKeyValue("r", rgb.getRed() + "") + ",";
		txt += StringTools.getKeyValue("g", rgb.getGreen() + "") + ",";
		txt += StringTools.getKeyValue("b", rgb.getBlue() + "") + ",";
		txt += StringTools.getKeyValue("a", rgb.getAlpha() + "") + ",";
		txt += StringTools.getKeyValue("importance", this.numberedColors.get(c.getColor()).importance + "");
		txt += "}}";
		return txt;
	}

	/**
	 * Creates a String representing the input colors. Each color will be
	 * represented in form of:<br>
	 * 
	 * <pre>
	 * {
	 *  "hexColorString" : {
	 * 	"r" : "floatRed",
	 * 	"g" : "floatGreen",
	 * 	"b" : "floatBlue",
	 * 	"a" : "floatAlpha",
	 * 	"importance" : "positiveInt"
	 * }}
	 * </pre>
	 * 
	 * The colors will be separated with commas; all colors will be framed with
	 * array brackets.
	 * 
	 * <pre>
	 * [color1, color2, ..., colorN]
	 * </pre>
	 * 
	 * Used for building a JSON String
	 * 
	 * @param colors
	 *            The input colors.
	 * @return A String representing the color information.
	 */
	private String getColorStrings(ArrayList<RColor> colors) {
		String txt = "[";

		for (RColor c : colors) {
			txt += getColorString(c) + ",";
		}

		return txt.substring(0, txt.length() - 1) + "]";
	}

	/**
	 * This method saves a JSON file containing this palettes color information.
	 * The filename will be a concatenation of this palettes name and the number
	 * of colors. If no name is set, a timestamp and the number of colors will
	 * be used as filename. The files will be saved in a folder named "export"
	 * in your current sketch folder. Example usage in Processing:<br>
	 * 
	 * <pre>
	 * myPalette.save(this);
	 * </pre>
	 * 
	 * @param parent
	 *            A PApplet object.
	 * 
	 * @return The current ColorPalette object.
	 */
	public ColorPalette save(PApplet parent) {
		return save(ProcessingTools.getSketchPath(parent) + "\\export");
	}

	/**
	 * This method saves a JSON file containing this palettes color information.
	 * The filename will be a concatenation of this palettes name and the number
	 * of colors. If no name is set, a timestamp and the number of colors will
	 * be used as filename.
	 * 
	 * @param folder
	 *            The name of the folder, where the palette should be saved. Can
	 *            also be a relative path to the folder. Make sure to escape the
	 *            backslashes when providing a relative path. Example usage in
	 *            Processing:
	 * 
	 *            <pre>
	 *            // will save the file in the current sketch folder in a sub-folder named
	 * // "colors"
	 *            myPalette.save(this, "colors");
	 * 
	 *            // will save the file in the folder "temp" which will be above the
	 * // current sketch folder
	 *            myPalette.save(this, "..\\temp");
	 *            </pre>
	 * 
	 * @param parent
	 *            A PApplet object.
	 * 
	 * @return The current ColorPalette object.
	 */
	public ColorPalette save(PApplet parent, String folder) {
		return save(ProcessingTools.getSketchPath(parent) + "\\" + folder);
	}

	/**
	 * This method saves a JSON file containing this palettes color information.
	 * 
	 * @param folder
	 *            The name of the folder, where the palette should be saved. Can
	 *            also be a relative path to the folder. Make sure to escape the
	 *            backslashes when providing a relative path. Example usage in
	 *            Processing:
	 * 
	 *            <pre>
	 *            // will save the file in the current sketch folder in a sub-folder named
	 * // "colors"
	 *            myPalette.save(this, "colors");
	 * 
	 *            // will save the file in the folder "temp" which will be above the
	 * // current sketch folder
	 *            myPalette.save(this, "..\\temp");
	 *            </pre>
	 * 
	 * @param name
	 *            The name of the file (without file extension) under which the
	 *            palette should be saved. Make sure this is a valid file name.
	 *            Read <a href="https://en.wikipedia.org/wiki/Filename" target=
	 *            "_blank">Wiki: Filename</a> for further informations.
	 * @param parent
	 *            A PApplet object.
	 * 
	 * @return The current ColorPalette object.
	 */
	public ColorPalette save(PApplet parent, String folder, String name) {
		return save(ProcessingTools.getSketchPath(parent) + "\\" + folder, name);
	}

	/**
	 * This method saves a JSON file containing this palettes color information.
	 * The filename will be a concatenation of this palettes name and the number
	 * of colors. If no name is set, a timestamp and the number of colors will
	 * be used as filename.
	 * 
	 * @param path
	 *            An absolute path to the place where the palette should be
	 *            saved. Make sure this path exists! Otherwise (e.g. if you want
	 *            to provide a relative path) please use the save(PApplet)
	 *            method.
	 * 
	 * @return The current ColorPalette object.
	 */
	public ColorPalette save(String path) {
		String filename = "";

		if (this.name == null || this.name.length() == 0) {
			filename = StringTools.timestamp() + "_" + this.colors.size();
		} else {
			filename = this.name + "_" + this.colors.size();
		}

		return save(path, filename);
	}

	/**
	 * This method saves a JSON file containing this palettes color information.
	 * 
	 * @param path
	 *            An absolute path to the place where the palette should be
	 *            saved. Make sure this path exists! Otherwise (e.g. if you want
	 *            to provide a relative path) please use the save(PApplet)
	 *            method.
	 * @param name
	 *            The name of the file (without file extension) under which the
	 *            palette should be saved. Make sure this is a valid file name.
	 *            Read <a href="https://en.wikipedia.org/wiki/Filename" target=
	 *            "_blank">Wiki: Filename</a> for further informations.
	 * @return The current ColorPalette object.
	 */
	public ColorPalette save(String path, String name) {

		name += ".color.json";

		String tagKey = StringTools.getKeyValue("tags", tags);
		String nameKey = StringTools.getKeyValue("name", this.name);
		String colorKey = StringTools.getKeyValue("colors", getColorStrings(colors), false);

		String jsonString = "{" + StringTools.join(",", nameKey, tagKey, colorKey) + "}";

		String reply = ExportHelper.writeTextFile(path, name, jsonString);

		if (reply != null) {
			System.err.println(reply);
		}
		/*
		 * { name : "", tags : ["", "", ""], colors: [{"hex" : {"r" : "red", "g"
		 * : "green", "b" : "blue", "a" : "alpha", "importance" : "int"}}] }
		 */

		return this;
	}

	/**
	 * Draws a simple representation of this color palette within a rectangular
	 * form.
	 * 
	 * @param parent
	 *            A PApplet object (Canvas to draw to).
	 * @param x
	 *            The x-value of the rectangle (left).
	 * @param y
	 *            The y-value of the rectangle (top).
	 * @param w
	 *            The with of the rectangle.
	 * @param h
	 *            The height of the rectangle.
	 * @return The current ColorPalette object.
	 */
	public ColorPalette draw(PApplet parent, float x, float y, float w, float h) {
		
		parent.pushStyle();
		float cpx = x;
		parent.noStroke();
		for (RColor c : this.colors) {

			float weighting = this.getWeighting(c);

			float cpw = w * weighting;

			parent.fill(c.getColor());
			parent.rect(cpx - 0.5f, y, cpw + 1, h);

			cpx += cpw;
		}
		parent.popStyle();

		return this;
	}

	/**
	 * Returns all colors of this palette. Usage:<br>
	 * 
	 * <pre>
	 * color[] theColors = myColorPalette.toColors();
	 * </pre>
	 */
	public int[] toColors() {
		int[] colors = new int[this.colors.size()];
		for (int i = 0; i < colors.length; i++) {
			colors[i] = this.colors.get(i).getColor();
		}

		return colors;
	}

	/**
	 * Returns all colors of this palette (Shallow copies). Usage:<br>
	 * 
	 * <pre>
	 * RColor[] theColors = myColorPalette.getColors();
	 * </pre>
	 */
	public RColor[] getColors() {
		return this.colors.toArray(new RColor[this.colors.size()]);
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see java.lang.Object#toString()
	 */
	public String toString() {

		String txt = "name: " + this.name + "\n";
		txt += "tags: " + (tags.size() > 0 ? StringTools.join(tags, ", ") : "") + "\n";

		for (Integer key : this.numberedColors.keySet()) {

			txt += "[" + this.getWeighting(this.numberedColors.get(key).c) + "] " + this.numberedColors.get(key) + "\n";
		}
		return txt;
	}

	/**
	 * A class to apply the colors of the palette to an image (image
	 * quantization). Since this may take a while to calculate for each pixel of
	 * the image, the calculation is splitted to several threads with each
	 * thread being responsible for just a partition of the image.
	 * 
	 * @author Diana Lange
	 *
	 */
	private class QuantizeBuilder extends Thread {

		/**
		 * The time when the quantization started.
		 */
		private String timestamp;

		/**
		 * The input image (the color for each pixel will be replaced by the
		 * color of the palette).
		 */
		private PImage img;

		/**
		 * The number of threads.
		 */
		private Integer threads;

		/**
		 * Sets which method to use for quantization. 0 = get(), 1 =
		 * getDithered(), 2 = getNoisy();
		 */
		private Integer method;

		/**
		 * The amount of noise / dithering the image should have(just used if
		 * method=1 or method=2).
		 */
		private Float dithering;

		/**
		 * Creates a new quantization builder.
		 * 
		 * @param img
		 *            The input image (all pixels will be replaced by the colors
		 *            of the palette).
		 * @param threads
		 *            The number of threads (>= 1).
		 * @param method
		 *            Which method should be used for quantization. 0 = get(), 1
		 *            = getDithered(), 2 = getNoisy();
		 * @param amt
		 *            The amount of dithering or noise [0, 1].
		 */
		public QuantizeBuilder(PImage img, int threads, int method, float amt) {
			this.timestamp = StringTools.timestamp() + "_" + StringTools.nf(RMath.random(1000), 4);
			this.threads = threads;
			this.img = img;
			this.method = method;
			this.dithering = amt;

			// add to stack to be able to observer whether quantization is
			// finished or not
			quantizeStack.put(this.timestamp, this);
			this.start();
		}

		/**
		 * Creates a new quantization builder. The used method for quantization
		 * is myPalette.get(PImage).
		 * 
		 * @param img
		 *            The input image (all pixels will be replaced by the colors
		 *            of the palette).
		 * @param threads
		 *            The number of threads (>= 1).
		 */
		public QuantizeBuilder(PImage img, int threads) {
			this(img, threads, 0, 0);
		}

		/**
		 * Create partitions of the image (number of partitions is set by
		 * <b>threads</b> and quantize that partition.
		 */
		@Override
		public void run() {
			img.loadPixels();
			int steps = img.pixels.length / threads;

			ArrayList<PartialQuantizeBuilder> builders = new ArrayList<PartialQuantizeBuilder>(steps);
			for (int i = 0; i < threads; i++) {

				// get range of pixels depending on the partition
				Integer startRange = i * steps;
				Integer endRange = startRange + steps;
				if (i == threads - 1) {
					endRange = img.pixels.length - 1;
				}

				// quantize that partition
				// quantize(startRange, endRange);
				builders.add(new PartialQuantizeBuilder(img, method, dithering, startRange, endRange));
			}

			boolean running = true;
			while (running) {
				running = false;
				for (PartialQuantizeBuilder b : builders) {
					if (b.getState() != State.TERMINATED) {
						running = true;
						try {
							this.wait(300);
						} catch (Exception e) {
						}
						break;
					}
				}
			}

			builders.clear();
			builders = null;

			// remove item from stack since the quantization for this image is
			// finished
			quantizeStack.remove(timestamp);
		}

		/**
		 * Quantizes a partition of the given image.
		 */
		private class PartialQuantizeBuilder extends Thread {
			/**
			 * The input image (the color for each pixel will be replaced by the
			 * color of the palette).
			 */
			private PImage img;

			/**
			 * Sets which method to use for quantization. 0 = get(), 1 =
			 * getDithered(), 2 = getNoisy();
			 */
			private Integer method;

			/**
			 * The amount of noise / dithering the image should have(just used
			 * if method=1 or method=2).
			 */
			private Float dithering;

			/**
			 * The index of the beginning of the partition [0,
			 * img.pixels.length), startRange < endRange.
			 */
			private Integer startRange;

			/**
			 * The index of the end of the partition [0, img.pixels.length),
			 * startRange < endRange.
			 */
			private Integer endRange;

			/**
			 * Builds a new PartialQuantizeBuilder.
			 * 
			 * @param img
			 *            The input image (all pixels will be replaced by the
			 *            colors of the palette).
			 * @param method
			 *            Which method should be used for quantization. 0 =
			 *            get(), 1 = getDithered(), 2 = getNoisy();
			 * @param amt
			 *            The amount of dithering or noise [0, 1].
			 * @param startRange
			 *            The index of the beginning of the partition [0,
			 *            img.pixels.length), startRange < endRange.
			 * @param endRange
			 *            The index of the end of the partition [0,
			 *            img.pixels.length), startRange < endRange.
			 */
			public PartialQuantizeBuilder(PImage img, int method, float amt, Integer startRange, Integer endRange) {

				this.startRange = startRange;
				this.endRange = endRange;
				this.img = img;
				this.method = method;
				this.dithering = amt;

				this.start();
			}

			@Override
			public void run() {
				RGBColor rgb = new RGBColor(0);

				// cut partition into 4 parts
				// after the finish of a part the pixels will ge updated
				int steps = 4;

				int range = (endRange - startRange) / steps;

				for (int i = 0; i < steps; i++) {

					int start = startRange + range * i;
					int end = start + range - 1;
					if (i == steps - 1) {
						end = endRange;
					}

					for (int j = start; j <= end; j++) {
						// get color of current pixel and use it to set the
						// color
						// of the rgb object
						rgb.set(img.pixels[j]);

						// override the pixel color with the color of the
						// palette
						if (method == 0) {
							img.pixels[j] = get(rgb).getColor();
						} else if (method == 1) {
							img.pixels[j] = getDithered(rgb, dithering).getColor();
						} else {
							img.pixels[j] = getNoisy(rgb, dithering).getColor();
						}
					}
					img.updatePixels();
				}
			}

		}

	}

	/**
	 * A class for the importance-color mapping.
	 * 
	 * @author Diana Lange
	 *
	 */
	private class NumberedColor {
		/**
		 * A positive number (> 0) representing this colors importance in the
		 * current palette.
		 */
		int importance;

		/**
		 * The color.
		 */
		RColor c;

		/**
		 * Creates a NumberedColor object.
		 * 
		 * @param c
		 *            The color.
		 * @param importance
		 *            The importance of that color in the current palette.
		 */
		private NumberedColor(RColor c, int importance) {
			this.c = c;
			this.importance = importance;
		}

		/**
		 * Creates a NumberedColor object. The importance will be set to 1.
		 * 
		 * @param c
		 *            The color.
		 * @param importance
		 *            The importance of that color in the current palette.
		 */
		private NumberedColor(RColor c) {
			this(c, 1);
		}

		/*
		 * (non-Javadoc)
		 * 
		 * @see java.lang.Object#toString()
		 */
		public String toString() {
			return importance + "x " + c;
		}
	}
}
