/*
 * Copyright (c) 2010 by Intevation GmbH
 *
 * This program is free software under the LGPL (>=v2.1)
 * Read the file LGPL.txt coming with the software for details
 * or visit http://www.gnu.org/licenses/ if it does not exist.
 */

package de.intevation.gnv.raster;

import de.intevation.gnv.raster.Raster.ValueToIndex;

import java.awt.Color;

import java.util.Arrays;

import org.apache.log4j.Logger;

import org.w3c.dom.Document;
import org.w3c.dom.Element;
import org.w3c.dom.NodeList;

/**
 * Lookup mechanism to map double values from a list of
 * ranges onto a set of colors and vice versa.
 * @author <a href="mailto:sascha.teichmann@intevation.de">Sascha L. Teichmann</a>
 */
public class Palette
implements   ValueToIndex
{
    private static Logger log = Logger.getLogger(Palette.class);

    /**
     * An entry in the lookup table.
     */
    public static final class Entry
    implements                Comparable
    {
        private Entry  left;
        private Entry  right;

        private int    index;

        private int    externalIndex;

        private double from;
        private double to;

        private String description;

        private Color  color;

        /**
         * Default constructor
         */
        public Entry() {
        }

        /**
         * Copy constructor
         * @param other The entry to copy.
         */
        public Entry(Entry other) {
            index         = other.index;
            externalIndex = other.externalIndex;
            from          = other.from;
            to            = other.to;
            description   = other.description;
            color         = other.color;
        }

        /**
         * Constructor to set the palette index, the exteral index,
         * the value range, the color and the description.
         * @param index The pallette index
         * @param externalIndex The external index
         * @param from Start of the interval
         * @param to End of the interval
         * @param color The color belonging to this interval.
         * @param description The description of this range.
         */
        public Entry(
            int    index,
            int    externalIndex,
            double from,
            double to,
            Color  color,
            String description
        ) {
            this.index         = index;
            this.externalIndex = externalIndex;
            this.from          = from;
            this.to            = to;
            this.color         = color;
            this.description   = description;
        }

        /**
         * Compares two entries by the start point of the interval.
         * @param other
         * @return -1 if this start point is before other. +1 if this
         * start point is after, else 0.
         */
        public int compareTo(Object other) {
            Entry e = (Entry)other;
            if (from < e.from) return -1;
            if (from > e.from) return +1;
            return 0;
        }

        /**
         * The starting point of the interval.
         * @return The starting point.
         */
        public double getFrom() {
            return from;
        }

        /**
         * The end point of the interval.
         * @return The end point.
         */
        public double getTo() {
            return to;
        }

        /**
         * The color of the entry.
         * @return The color.
         */
        public Color getColor() {
            return color;
        }

        /**
         * The external index of this entry. Useful to model
         * external joins.
         * @return The external index.
         */
        public int getExternalIndex() {
            return externalIndex;
        }

        /**
         * Searches for an entry which has a range that contains
         * the given value.
         * @param value The value to be searched.
         * @return The entry containing the value or null if no such
         * entry exists.
         */
        public Entry locateEntry(double value) {
            Entry current = this;
            while (current != null) {
                boolean b = value >= current.from;
                if (b && value <= current.to) {
                    return current;
                }
                current = b
                    ? current.right
                    : current.left;
            }
            return null;
        }

        /**
         * Returns the palette index for a given value.
         * @param value The value to search.
         * @return The index of the palette entry or -1 if
         * no such entry exists.
         */
        public int locate(double value) {
            Entry entry = locateEntry(value);
            return entry != null
                ? entry.index
                : -1;
        }

        /**
         * Searches for an interval with a given index.
         * @param index The index to be searched.
         * @return The entry with the given index or null if no
         * such entry exists.
         */
        public Entry findByIndex(int index) {
            Entry current = this;
            while (current != null) {
                if (current.index == index) {
                    break;
                }
                current = index < current.index
                    ? current.left
                    : current.right;
            }
            return current;
        }

        /**
         * The description of this entry.
         * @return The description.
         */
        public String getDescription() {
            return description;
        }

        /**
         * Determines if the range of this entry has
         * infinitive length.
         * @return true if the range of this entry has infinitive
         * length else false.
         */
        public boolean isInfinity() {
            return from == -Double.MAX_VALUE
              ||   to   ==  Double.MAX_VALUE;
        }
    } // class Entry

    /**
     * Internal table of the entrys.
     */
    protected Entry [] entries;

    /**
     * Root of the entry tree used to map values to entries.
     */
    protected Entry    lookup;

    /**
     * The list of colors used by this palette.
     */
    protected Color [] rgbs;

    private Entry buildLookup(Entry [] entries, int lo, int hi) {
        if (lo > hi) {
            return null;
        }
        int mid = (lo + hi)/2;
        Entry entry = entries[mid];
        entry.left  = buildLookup(entries, lo, mid-1);
        entry.right = buildLookup(entries, mid+1, hi);
        return entry;
    }

    /**
     * Default constructor.
     */
    public Palette() {
    }

    /**
     * Constructor to create the palette from an XML document.
     * @param document The document with palette information.
     */
    public Palette(Document document) {

        NodeList rangeNodes = document.getElementsByTagName("range");

        entries = new Entry[rangeNodes.getLength()];
        rgbs    = new Color[entries.length];

        for (int i = 0; i < entries.length; ++i) {
            Element rangeElement = (Element)rangeNodes.item(i);
            double from     = doubleValue(rangeElement.getAttribute("from"));
            double to       = doubleValue(rangeElement.getAttribute("to"));
            int    extIndex = intValue(rangeElement.getAttribute("index"), i);
            Color  color    = color(rangeElement.getAttribute("rgb"));
            String desc     = rangeElement.getAttribute("description");
            if (from > to) { double t = from; from = to; to = t; }
            entries[i] = new Entry(i, extIndex, from, to, color, desc);
            rgbs[i] = color;
        }

        buildLookup();
    }

    /**
     * Constructor to split a given palette into a given number of
     * equal sized sub entries. Ranges of infinitive length are not
     * splitted.
     * @param original The source palette.
     * @param N The number of chunks to split single ranges into.
     */
    public Palette(Palette original, int N) {
        if (N < 2)  {
            throw new IllegalArgumentException("N < 2");
        }

        Entry [] origEntries = original.entries;

        int newSize = 0;
        for (int i = 0; i < origEntries.length; ++i) {
            // cannot split infinity intervals
            newSize += origEntries[i].isInfinity() ? 1 : N;
        }

        entries = new Entry[newSize];
        rgbs    = new Color[newSize];

        for (int i = 0, j = 0; i < origEntries.length; ++i) {
            Entry origEntry = origEntries[i];
            if (origEntry.isInfinity()) {
                // infinity intervals are just copied
                Entry nEntry = new Entry(origEntry);
                entries[j] = nEntry;
                rgbs[j]    = nEntry.color;
                nEntry.index = j++;
            }
            else {
                // split interval into N parts
                double from  = origEntry.from;
                double to    = origEntry.to;
                double delta = (to - from)/N;
				for (int k = 0; k < N; ++k) {
                    Entry nEntry = new Entry(origEntry);
                    nEntry.from = from;
                    nEntry.to   = from + delta;
                    from += delta;
                    entries[j] = nEntry;
                    rgbs[j]    = nEntry.color;
                    nEntry.index = j++;
                }
            } // limited interval
        } // for all original entries

        buildLookup();
    }

    private static final int intValue(String s, int def) {
        if (s == null || (s = s.trim()).length() == 0) {
            return def;
        }
        try {
            return Integer.parseInt(s);
        }
        catch (NumberFormatException nfe) {
            log.error(nfe.getLocalizedMessage(), nfe);
        }
        return def;
    }

    private static final double doubleValue(String s) {
        if (s == null || (s = s.trim()).length() == 0) {
            return 0d;
        }
        if ((s = s.toLowerCase()).startsWith("-inf")) {
            return -Double.MAX_VALUE; // XXX: Not using Double.NEGATIVE_INFINITY!
        }

        if (s.startsWith("inf")) {
            return Double.MAX_VALUE; // XXX: Not using Double.NEGATIVE_INFINITY!
        }

        return Double.parseDouble(s);
    }

    private static final Color color(String s) {
        if (s == null || (s = s.trim()).length() == 0) {
            return null;
        }
        return Color.decode(s);
    }


    /**
     * Internal method to build the lookup tree.
     */
    protected void buildLookup() {
        Arrays.sort(entries);
        lookup = buildLookup(entries, 0, entries.length-1);
    }

    /**
     * Creates a new palette which has ranges that are subdivided
     * into a given number of sub ranges each.
     * @param N The number od sub divisions of each range.
     * @return The new created palette.
     */
    public Palette subdivide(int N) {
        return new Palette(this, N);
    }

    /**
     * Return the number of entries in this palette.
     * @return The number of entries.
     */
    public int getSize() {
        return rgbs.length;
    }

    /**
     * Return the color of an entry for a given index.
     * @param index The index.
     * @return The color.
     */
    public Color getColor(int index) {
        return rgbs[index];
    }

    /**
     * Return the RGB value
     * @param index of an entry for a given index.
     * @return rgb value
     */
    public int indexToRGB(int index) {
        return rgbs[index].getRGB();
    }

    /**
     * Searches for the index of an entry which contains the
     * given value.
     * @param value The value to be searched.
     * @return The index of the entry or -1 if no entry is found.
     */
    public int toIndex(double value) {
        return lookup.locate(value);
    }

    /**
     * Searches for the an entry which contains the given value.
     * @param value The value to be searched.
     * @return The entry which contains the value or null if
     * no such entry is found.
     */
    public Entry getEntry(double value) {
        return lookup.locateEntry(value);
    }

    /**
     * Searches the entry for a given index.
     * @param index The index of the entry.
     * @return The entry or null if no such entry is found.
     */
    public Entry getEntryByIndex(int index) {
        return lookup.findByIndex(index);
    }
}
// vim:set ts=4 sw=4 si et sta sts=4 fenc=utf8 :