/*
 * 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 gnu.trove.TIntObjectHashMap;
import gnu.trove.TIntStack;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.List;

import org.apache.log4j.Logger;

/**
 * Instances of this class are able to vectorize 2D integer arrays
 * with a kind of flood filling regions detection mechanism to
 * a set of line strings and polygons.
 *
 * @author <a href="mailto:sascha.teichmann@intevation.de">Sascha L. Teichmann</a>
 */
public class Vectorizer
{
    private static Logger log = Logger.getLogger(Vectorizer.class);

    /**
     * Callback to process the found line strings and polygons.
     */
    public interface RingsHandler {

        /**
         * Called from {@link #process(de.intevation.gnv.raster.Vectorizer.RingsHandler) }
         * to give the found features to the postprocessing backend.
         * @param rings The found line strings and polygons.
         * @param value The integer value of the raster surrounded by
         * the features.
         * @param width The width of the index space of the vectorized data.
         * @param height The height of the index space of the vectorized data.
         */
        void handleRings(
            List<Edge> rings,
            int        value,
            int        width,
            int        height);

    } // interface RingsHandler

    /**
     * Doubly link list representing a line string or a polygon.
     */
    public static final class Edge {

        /**
         * The predecessor.
         */
        public Edge prev;
        /**
         * The successor.
         */
        public Edge next;

        /**
         * Index of first vertex. To separate x and y values
         * you have to divide the value by the width of the
         * index space.
         */
        public int a;
        /**
         * Index of second vertex. To separate x and y values
         * you have to divide the value by the width of the
         * index space.
         */
        public int b;

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

        /**
         * Constructor to create Edge with two vertices.
         * @param a The first vertex.
         * @param b The second vertex.
         */
        public Edge(int a, int b) {
            this.a = a;
            this.b = b;
        }

        /**
         * Copy constructor
         * @param other The edge to clone.
         */
        public Edge(Edge other) {
            a = other.a;
            b = other.b;
        }

        /**
         * Chain a given edge segment to this segment. The
         * side of the chaining is determined by a given
         * parameter.
         * @param other The segment to chain.
         * @param found The side to chain.
         */
        public void chain(Edge other, int found) {

            if (found == a) {
                other.next = this;
                prev = other;
                return;
            }

            if (found == b) {
                next = other;
                other.prev = this;
                return;
            }

            throw new IllegalStateException("cannot chain");
        }

        /**
         * Tells if the list is complete which means that this
         * edge list is a closed polygon.
         * @return true if edge list is closed else false.
         */
        public boolean isComplete() {
            Edge current = this;
            do {
                if (current.prev == null || current.next == null) {
                    return false;
                }
                current = current.next;
            }
            while (current != this);
            return true;
        }

        /**
         * Returns the length of this edge list in next direction.
         * Segments in prev direction are ignored.
         * @return The length of this edge list.
         */
        public int length() {
            int length = 0;
            Edge current = this;
            do { ++length; }
            while ((current = current.next) != null && current != this);
            return length;
        }

        /**
         * Returns the head node of this edge list.
         * @return The head node.
         */
        public Edge head() {
            Edge current = this;
            while (current.prev != null) {
                current = current.prev;
            }
            return current;
        }

        /**
         * Hashes the two vertex indices to a common value.
         * @return The hash value.
         */
        @Override
        public int hashCode() {
            return (a << 16) | b;
        }

        /**
         * Two edges are considered equal if they have the same
         * a and b vertices.
         * @param other The other edge.
         * @return true if the edges are equal else false.
         */
        @Override
        public boolean equals(Object other) {
            Edge e = (Edge)other;
            return a == e.a && b == e.b;
        }
    } // class Edge

    /**
     * Simplifies a given edge list by removing collinear vertices.
     * Attention: The original list is modified.
     * @param edge The edge list to simplify.
     * @param width The width of the vertex index space.
     * @return The simplified list.
     */
    protected static Edge simplify(Edge edge, int width) {

        Edge e1 = edge, start = edge;

        int length = edge.length();

        if (length < 2) {
            return e1;
        }

        Edge e2 = edge.next;

        int count = 0;

        do {
            int e1x = e1.a % width;
            int e1y = e1.a / width;
            int e2x = e1.b % width;
            int e2y = e1.b / width;
            int e3x = e2.b % width;
            int e3y = e2.b / width;

            if ((e1x == e2x && e2x == e3x && e1x == e3x)
                    ||  (e1y == e2y && e2y == e3y && e1y == e3y)) {
                e1.b = e2.b;
                Edge removed = e1.next;
                e1.next = e2.next;
                if (e1.next != null) {
                    e1.next.prev = e1;
                }
                e2 = e1.next;
                count = 0;
                --length;
                if (removed == start) {
                    start = e1;
                }
            }
            else {
                e1 = e1.next;
                e2 = e2.next;
                ++count;
            }
        }
        while (length > 1 && e2 != null && count < length + 2);

        return start;
    }

    /**
     * The raster to be traced.
     */
    protected int []            raster;
    /**
     * The width of the raster.
     */
    protected int               width;
    /**
     * Map of the currently open edges.
     */
    protected TIntObjectHashMap openEdges;
    /**
     * List of rings already found.
     */
    protected List<Edge>        rings;
    /**
     * Flag to signal if a simplification should be performed
     * after a ring is completed.
     */
    protected boolean           simplify;

    /**
     * Default constructor. Simplification is turned on.
     */
    public Vectorizer() {
        this(true);
    }

    /**
     * Constructor to create a vectorized with an explicit
     * simplification policy.
     * @param simplify Indicates if simplification should be
     * used on ring completion.
     */
    public Vectorizer(boolean simplify) {
        openEdges     = new TIntObjectHashMap();
        rings         = new ArrayList<Edge>();
        this.simplify = simplify;
    }

    /**
     * Constructor to create a vectorizer with a given raster and width.
     * Simplification is turn on.
     * @param raster The raster to be vectorized.
     * @param width The width of the raster.
     */
    public Vectorizer(int [] raster, int width) {
        this(true, raster, width);
    }

    /**
     * Constructor to create a vectorizer with a given raster, width
     * and an explicit simplification policy.
     * @param simplify Indicates if simplification should be
     * used on ring completion.
     * @param raster The raster to be vectorized.
     * @param width The width of the raster.
     */
    public Vectorizer(boolean simplify, int [] raster, int width) {
        this(simplify);
        this.raster = raster;
        this.width  = width;
    }

    /**
     * Returns (x, y+1) for given vertex in index space.
     * @param i vertex in index space.
     * @param w width of raster.
     * @return (x, y+1) in index space.
     */
    public static final int tl(int i, int w) {
        int x = i % w;
        int y = i / w;
        return x + (w + 1)*y;
    }

    /**
     * Returns tl(i, w) + 1.
     * @param i vertex in index space.
     * @param w width of raster.
     * @return tl(i, w) + 1.
     */
    public static final int tr(int i, int w) {
        return tl(i, w) + 1;
    }

    /**
     * Returns tl(i, w) + w + 1.
     * @param i vertex in index space.
     * @param w width of raster.
     * @return tl(i, w) + w + 1.
     */
    public static final int bl(int i, int w) {
        return tl(i, w) + w + 1;
    }

    /**
     * Returns bl(i, w) + 1.
     * @param i vertex in index space.
     * @param w width of raster.
     * @return bl(i, w) + 1.
     */
    public static final int br(int i, int w) {
        return bl(i, w) + 1;
    }

    /**
     * Resets open resources after a set of features were found.
     */
    protected void resetRegion() {
        openEdges.clear();
        rings.clear();
    }

    /**
     * Adds an edge to the map of open edges, joins it
     * with its direct neighbors of if complete add the
     * list to the complete features.
     * @param edge
     */
    protected void emit(Edge edge) {

        Edge otherA = (Edge)openEdges.remove(edge.a);
        if (otherA != null) {
            otherA.chain(edge, edge.a);
        }

        Edge otherB = (Edge)openEdges.remove(edge.b);
        if (otherB != null) {
            otherB.chain(edge, edge.b);
        }

        if (edge.isComplete()) {
            rings.add(simplify ? simplify(edge, width + 1) : edge);
        }
        else {
            if (otherA == null) {
                openEdges.put(edge.a, edge);
            }
            if (otherB == null) {
                openEdges.put(edge.b, edge);
            }
        }
    }

    /**
     * Vectorize the raster. The found features are fed into
     * the given ring handler.
     * @param handler The RingHandler to postprocess the found features.
     * @return The number of regions found.
     */
    public int process(RingsHandler handler) {

        BitSet visited = new BitSet(raster.length);

        TIntStack stack = new TIntStack();

        int regions = 0;

        int height = raster.length / width;

        for (int i = 0; i < raster.length; ++i) {
            if (visited.get(i)) {
                continue;
            }

            ++regions;

            int currentValue = raster[i];
            visited.set(i);

            int current = i;
            visited.set(current);

            for (;;) {
                int tl = tl(current, width);
                int tr = tr(current, width);
                int bl = bl(current, width);
                int br = br(current, width);

                int t = current - width;

                if (t < 0) {
                    emit(new Edge(tr, tl));
                }
                else {
                    if (raster[t] != currentValue) {
                        emit(new Edge(tr, tl));
                    }
                    else {
                        if (!visited.get(t)) {
                            visited.set(t);
                            stack.push(t);
                        }
                    }
                }

                int b = current + width;

                if (b >= raster.length) {
                    emit(new Edge(bl, br));
                }
                else {
                    if (raster[b] != currentValue) {
                        emit(new Edge(bl, br));
                    }
                    else {
                        if (!visited.get(b)) {
                            visited.set(b);
                            stack.push(b);
                        }
                    }
                }

                int x = current % width;

                if (x == 0) {
                    emit(new Edge(tl, bl));
                }
                else {
                    int l = current - 1;
                    if (raster[l] != currentValue) {
                        emit(new Edge(tl, bl));
                    }
                    else {
                        if (!visited.get(l)) {
                            visited.set(l);
                            stack.push(l);
                        }
                    }
                }

                if (x == width - 1) {
                    emit(new Edge(br, tr));
                }
                else {
                    int r = current + 1;
                    if (raster[r] != currentValue) {
                        emit(new Edge(br, tr));
                    }
                    else {
                        if (!visited.get(r)) {
                            visited.set(r);
                            stack.push(r);
                        }
                    }
                }

                if (stack.size() == 0) {
                    break;
                }

                current = stack.pop();
            }

            handler.handleRings(
                rings,
                currentValue,
                width + 1,
                height + 1);

            resetRegion();
        }

        return regions;
    }
}
// vim:set ts=4 sw=4 si et sta sts=4 fenc=utf8 :