--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/gnv-artifacts/src/main/java/de/intevation/gnv/raster/Palette.java	Fri Sep 28 12:14:00 2012 +0200
@@ -0,0 +1,436 @@
+/*
+ * 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 :