package de.intevation.gnv.raster;

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

import gnu.trove.TIntStack;
import gnu.trove.TIntObjectHashMap;

import org.apache.log4j.Logger;

/**
 * @author Sascha L. Teichmann (sascha.teichmann@intevation.de)
 */
public class Vectorizer
{
    private static Logger log = Logger.getLogger(Vectorizer.class);

    public interface RingsHandler {

        void handleRings(
            List<Edge> rings,
            int        value, 
            int        width,
            int        height);

    } // interface RingsHandler

    public static final class Edge {

        public Edge prev;
        public Edge next;

        public int a;
        public int b;

        public Edge() {
        }

        public Edge(int a, int b) {
            this.a = a;
            this.b = b;
        }

        public Edge(Edge other) {
            a = other.a;
            b = other.b;
        }

        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");
        }

        public boolean isComplete() {
            Edge current = this;
            do {
                if (current.prev == null || current.next == null) {
                    return false;
                }
                current = current.next;
            }
            while (current != this);
            return true;
        }

        public int length() {
            int length = 0;
            Edge current = this;
            do { ++length; } 
            while ((current = current.next) != null && current != this);
            return length;
        }

		public Edge head() {
			Edge current = this;
			while (current.prev != null) {
				current = current.prev;
			}
			return current;
		}

        public int hashCode() {
            return (a << 16) | b;
        }

        public boolean equals(Object other) {
            Edge e = (Edge)other;
            return a == e.a && b == e.b;
        }
    } // class Edge

    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;
    }

    protected int []            raster;
    protected int               width;
    protected TIntObjectHashMap openEdges;
    protected List<Edge>        rings;
    protected boolean           simplify;

    public Vectorizer() {
        this(true);
    }

    public Vectorizer(boolean simplify) {
        openEdges     = new TIntObjectHashMap();
        rings         = new ArrayList<Edge>();
        this.simplify = simplify;
    }

    public Vectorizer(int [] raster, int width) {
        this(true, raster, width);
    }

    public Vectorizer(boolean simplify, int [] raster, int width) {
        this(simplify);
        this.raster = raster;
        this.width  = width;
    }

    public static final int tl(int i, int w) {
        int x = i % w;
        int y = i / w;
        return x + (w + 1)*y;
    }

    public static final int tr(int i, int w) {
        return tl(i, w) + 1;
    }

    public static final int bl(int i, int w) {
        return tl(i, w) + w + 1;
    }

    public static final int br(int i, int w) {
        return bl(i, w) + 1;
    }

    protected void resetRegion() {
        openEdges.clear();
        rings.clear();
    }

    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);
            }
        }
    }

    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: