using System;
using System.Collections.Generic;
using System.Linq;
using System.Drawing;

namespace Contours {
    public class Shape {
        class Position {
            public Point point;
            public readonly Circuit<Position, Link> links;

            public Position() {
                links = new Circuit<Position, Link>(this);
            }

            public Position(Point point): this() { this.point = point; }
        }

        class Contour {
            public bool inverted = false;
            
            public Contour parent;
            public List<Contour> childs;

            public readonly Circuit<Contour, Link> forward;
            public readonly Circuit<Contour, Link> backward;

            public Contour() {
                forward = new Circuit<Contour, Link>(this);
                backward = new Circuit<Contour, Link>(this);
            }
        }

        class Link {
            public bool forward = false;
            public Position nextPosition = null;

            public readonly Circuit<Position, Link>.Entry position;
            public readonly Circuit<Contour, Link>.Entry contour;

            public Link() {
                position = new Circuit<Position, Link>.Entry(this);
                contour = new Circuit<Contour, Link>.Entry(this);
            }

            public Link split(Shape shape, Position position) {
                Link link = new Link();
                link.position.insertBack(position.links);
                link.contour.insertAfterOf(contour);
                link.forward = forward;
                link.nextPosition = nextPosition;
                nextPosition = position;
                shape.links.Add(link);
                return link;
            }

            public Link split(Shape shape, Link positionLink) {
                return split(shape, positionLink.position.getParent());
            }
        }


        readonly List<Position> positions = new List<Position>();
        readonly List<Link> links = new List<Link>();
        readonly List<Contour> contours = new List<Contour>();
        readonly List<Contour> rootContours = new List<Contour>();


        public void clear() {
            positions.Clear();
            links.Clear();
            contours.Clear();
            rootContours.Clear();
        }

        public void setContour(IEnumerable<Point> contour) {
            setContours(new IEnumerable<Point>[] { contour });
        }

        public void setContours(IEnumerable<IEnumerable<Point>> contours) {
            clear();
            foreach(IEnumerable<Point> contour in contours) {
                if (contour.Count() >= 3) {
                    Link firstForward = null;
                    Link firstBackward = null;
                    Link previousForward = null;
                    Link previousBackward = null;
                    foreach(Point point in contour) {
                        Position position = new Position(point);

                        Link forward = new Link();
                        forward.forward = true;
                        forward.position.insertBack(position.links);
                        if (previousForward != null)
                            previousForward.nextPosition = forward.position.getParent();
                        links.Add(forward);
                        
                        Link backward = new Link();
                        backward.forward = false;
                        backward.position.insertBack(position.links);
                        if (previousBackward != null)
                            backward.nextPosition = previousBackward.position.getParent();
                        links.Add(backward);
                        
                        if (firstForward == null) firstForward = forward;
                        if (firstBackward == null) firstBackward = backward;
                        previousForward = forward;
                        previousBackward = backward;
                    }
                    previousForward.nextPosition = firstForward.position.getParent();
                    firstBackward.nextPosition = previousBackward.position.getParent();
                }
            }
            
            calculate(true);
        }

        /* TODO:
        public bool removeEmptyContours() {
            bool removed = false;
        
            bool retry = true;
            while(retry) {
                retry = false;
                for(Contour contour = contours.getFirst(); !retry && contour != null; contour = contour.shape.getNextLinear()) {
                    if (contour.forward.getCount() < 3 || contour.backward.getCount() < 3) {
                        while(contour.forward.getFirst() != null)
                            contour.forward.getFirst().unlink();
                        while(contour.backward.getFirst() != null)
                            contour.backward.getFirst().unlink();
                        contour.shape.unlink();
                        retry = true;
                        removed = true;
                        break;
                    }
                }
                if (retry) continue;
            }
            
            return removed;
        }
        */
        
        void resetTraceInformation() {
            for(int i = 0; i < contours.Count; ++i) {
                contours[i].forward.clear();
                contours[i].backward.clear();
                contours[i].childs.Clear();
                contours[i].parent = null;
            }
            contours.Clear();
            rootContours.Clear();
        }
        
        void removeLink(Link link) {
            link.position.unlink();
            link.contour.unlink();
            link.nextPosition = null;
            links.Remove(link);
        }

        void removeEmptyPositions() {
            for(int i = 0; i < positions.Count; ++i)
                if (positions[i].links.empty())
                    positions.RemoveAt(i--);
        }
        
        void findIntersections() {
            bool retry = true;
            while(retry) {
                retry = false;

                // merge positions
                // this procedure may create zero-length links
                for(int i = 0; i < positions.Count; ++i) {
                    for(int j = i+1; j < positions.Count; ++j) {
                        if (positions[i].point == positions[j].point) {
                            while(positions[j].links.getFirst() != null)
                                positions[j].links.getFirst().position.insertBack(positions[i].links);
                            positions.RemoveAt(j--);
                        }
                    }
                }
                
                // remove zero-length links
                // this procedure may create empty positions
                for(int i = 0; i < links.Count; ++i)
                    if (links[i].position.getParent() == links[i].nextPosition)
                        removeLink(links[i--]);
                
                // so we need to...
                removeEmptyPositions();
                                
                // check intersections
                // this procedure may create new positions, new links and ne intersections
                // so we need to repeat all cycle when intersection found
                for(int i = 0; i < links.Count; ++i) {
                    for(int j = i+1; j < links.Count; ++j) {
                        Link a = links[i];
                        Link b = links[j];
                        Position a0 = a.position.getParent();
                        Position a1 = a.nextPosition;
                        Position b0 = b.position.getParent();
                        Position b1 = b.nextPosition;
                        Point c = new Point(0, 0);
                        retry = true; // will reset to false if no intersection
                        
                        switch(Geometry.findIntersection(a0.point, a1.point, b0.point, b1.point, out c))
                        {
                        case Geometry.IntersectionType.Cross:
                            Position p = new Position(c);
                            positions.Add(p);
                            a.split(this, p);
                            b.split(this, p);
                            break;
                        case Geometry.IntersectionType.Touch_a0:
                            b.split(this, a0);
                            break;
                        case Geometry.IntersectionType.Touch_a1:
                            b.split(this, a1);
                            break;
                        case Geometry.IntersectionType.Touch_b0:
                            a.split(this, b0);
                            break;
                        case Geometry.IntersectionType.Touch_b1:
                            a.split(this, b1);
                            break;
                        case Geometry.IntersectionType.Along_a0_b0_a1_b1:
                            a.split(this, b0);
                            b.split(this, a1);
                            break;
                        case Geometry.IntersectionType.Along_a0_b0_b1_a1:
                            a.split(this, b0).split(this, b1);
                            break;
                        case Geometry.IntersectionType.Along_a0_b1_a1_b0:
                            a.split(this, b1);
                            b.split(this, a1);
                            break;
                        case Geometry.IntersectionType.Along_a0_b1_b0_a1:
                            a.split(this, b1).split(this, b0);
                            break;
                        case Geometry.IntersectionType.Along_b0_a0_a1_b1:
                            b.split(this, a0).split(this, a1);
                            break;
                        case Geometry.IntersectionType.Along_b0_a0_b1_a1:
                            a.split(this, b1);
                            b.split(this, a0);
                            break;
                        case Geometry.IntersectionType.Along_b1_a0_a1_b0:
                            b.split(this, a1).split(this, a0);
                            break;
                        case Geometry.IntersectionType.Along_b1_a0_b0_a1:
                            a.split(this, b0);
                            b.split(this, a0);
                            break;
                        default:
                            retry = false;
                            break;
                        }
                    }
                }
            }
        }
        
        // This function removes link from it position
        // and also recursive removes part of contour to nearest fork
        void removeLinkFromPosition(Link link) {
            Position position = link.position.getParent();
            Link nextToRemove = null;
            
            // remove back link            
            if (link.nextPosition != null) {
                Link backLink = link.nextPosition.links.getFirst();
                while (backLink != null) {
                    Link l = backLink;
                    backLink = backLink.position.getNextLinear();
                    if ( l.forward != link.forward
                      && l.contour.getNext() != null
                      && l.contour.getNext().position.getParent() == position )
                    {
                        removeLink(l);
                        break;
                    }
                }
                
                if (link.nextPosition.links.getCount() == 1)
                    nextToRemove = link.nextPosition.links.getFirst();
            }

            // remove
            removeLink(link);

            // remove next
            if (nextToRemove != null)
                removeLinkFromPosition(nextToRemove);
        }
        
        // Before trace contours we can (and should) to do some actions
        // to optimize links in each vertes.
        // So we can remove duplicated contour chunks
        // and chunks which placed inside contours of similar type
        // and not affecting to final image
        void optimizePositions() {
            foreach(Position position in positions) {
                // remove duplicates
                for(Link a = position.links.getFirst(); a != null; a = a.position.getNextLinear()) {
                    Position otherPosition = a.nextPosition;
    
                    // count forward and backward links
                    int count = 0;
                    Link forwardLink = null;
                    Link backwardLink = null;
                    Link b = a;
                    do {
                        if (b.nextPosition == otherPosition) {
                            if (b.forward) { forwardLink = b; ++count; }
                                      else { backwardLink = b; --count; }
                        }
                        b.position.getNext();
                    } while(b != a);
    
                    // remove extra links
                    Link linkToSave = count > 0 ? forwardLink
                                    : count < 0 ? backwardLink
                                    : null;
                    b = position.links.getFirst();
                    while(b != null) {
                        if (b.nextPosition == otherPosition && b != linkToSave) {
                            // remove link, a and b becomes invalid
                            removeLinkFromPosition(b);
                            // so reset a and b to repeat the current and parent cycles
                            b = a = position.links.getFirst();
                        } else {
                            b = b.position.getNextLinear();
                        }
                    }
                }

                if (position.links.getCount() >= 3) {
                    // sort links
                    Link first = position.links.getFirst();
                    Link a = first;
                    while (true) {
                        Link b = a.position.getNext();
                        Link c = b.position.getNext();
                        if ( !Geometry.isCCW(
                                position.point,
                                a.nextPosition.point,
                                b.nextPosition.point,
                                c.nextPosition.point ))
                        {
                            b.position.swapWith(c.position);
                            first = a = c;
                            continue;
                        }
                        a = b;
                        if (a == first) break;
                    };
                    
                    // remove invisible contours from position
                    first = position.links.getFirst();
                    a = first.position.getNext();
                    while(a != first) {
                        bool previous = a.position.getPrevious().forward;
                        bool current = a.forward;
                        bool next = a.position.getNext().forward;
                        if ( ( previous &&  current && !next)
                          || (!previous && !current &&  next) )
                        {
                            // remove link
                            removeLinkFromPosition(a);
                            first = position.links.getFirst();
                            a = first.position.getNext();
                        }
                    };
                }
            }
        }
        
        void buildContours() {
            for(int i = 0; i < links.Count; ++i) {
                if (links[i].forward && links[i].contour.getParent() == null) {
                    Contour contour = new Contour();
                    contours.Add(contour);
                    
                    Link forwardLink = links[i];
                    Link backwardLink = null;

                    do {
                        // find pair
                        for(Link l = forwardLink.nextPosition.links.getFirst(); l != null; l = l.position.getNext())
                            if (l.nextPosition == forwardLink.position.getParent())
                                { backwardLink = l; break; }
                        if (backwardLink == null || backwardLink.forward)
                            throw new Exception();
                        
                        forwardLink.contour.insertBack(contour.forward);
                        backwardLink.contour.insertBack(contour.backward);
                        
                        // select first link by the left (links should be CCW-ordered)
                        forwardLink = backwardLink.position.getNext();
                        if ( !forwardLink.forward
                          || forwardLink == backwardLink
                          || forwardLink.contour.getParent() != null )
                            throw new Exception();
                    } while (forwardLink != links[i]);
                }
            }
        }

        // Normally we should not have free links after tracing
        void removeFreeLinks() {
            for(int i = 0; i < links.Count; ++i)
                if (links[i].contour.getParent() == null)
                    throw new Exception();
        }

        int countIntersectionsWithContour(Point p0, Point p1, Contour contour) {
            int count = 0;
            for(Link link = contour.forward.getFirst(); link != null; link = link.contour.getNextLinear()) {
                Point pp0 = link.position.getParent().point;
                Point pp1 = link.contour.getNext().position.getParent().point;
                int d = Math.Sign( (long)(p0.Y - p1.Y)*(long)(pp1.X - pp0.X)
                                 + (long)(p1.X - p0.X)*(long)(pp1.Y - pp0.Y) );
                Point c;
                switch(Geometry.findIntersection(p0, p1, pp0, pp1, out c)) {
                case Geometry.IntersectionType.Cross:
                    count += 2*d;
                    break;
                case Geometry.IntersectionType.Touch_b0:
                    count += d;
                    break;
                case Geometry.IntersectionType.Touch_b1:
                    count -= d;
                    break;
                default:
                    break;
                }
            }
            return count;
        }

        bool isContourInverted(Contour contour) {
            Link first = contour.forward.getFirst();
            Point p0 = first.position.getParent().point;
            Point p1 = first.contour.getNext().position.getParent().point;
            Geometry.makeLongestLine(p0, ref p1);
            return countIntersectionsWithContour(p0, p1, contour) < 0;
        }
        
        bool isContourInside(Contour inner, Contour outer) {
            Link first = inner.forward.getFirst();
            Point p0 = first.position.getParent().point;
            Point p1 = first.contour.getNext().position.getParent().point;
            Geometry.makeLongestLine(p0, ref p1);
            return countIntersectionsWithContour(p0, p1, outer) != 0;
        }
        
        void organizeChildContours(Contour contour, Contour parent) {
            // set parent
            contour.parent = parent;

            // remove sub-childs from parent list
            if (parent != null)
                foreach(Contour c in contour.childs)
                    parent.childs.Remove(c);

            // sub-calls
            foreach(Contour c in contour.childs)
                organizeChildContours(c, contour);
        }
        
        void buildContoursHierarhy(bool simple) {
            // calculate directions of contours
            foreach(Contour contour in contours)
                contour.inverted = isContourInverted(contour);
                
            // find childs
            rootContours.AddRange(contours);
            for(int i = 0; i < contours.Count; ++i) {
                for(int j = 0; j < contours.Count; ++j) {
                    if (isContourInside(contours[i], contours[j])) {
                        contours[j].childs.Add(contours[i]);
                        rootContours.Remove(contours[i]);
                    } else
                    if (isContourInside(contours[j], contours[i])) {
                        contours[i].childs.Add(contours[j]);
                        rootContours.Remove(contours[j]);
                    }
                }
            }
            
            // organize childs
            foreach(Contour c in rootContours)
                organizeChildContours(c, null);
           
            // TODO: if simple then invert invisible contours instead of removing
           
            // remove invisible contours
            for(int i = 0; i < contours.Count; ++i) {
                bool parentInverted = contours[i].parent == null || contours[i].parent.inverted;
                if (parentInverted == contours[i].inverted) {
                    // remove contour
                    foreach(Contour c in contours[i].childs)
                        c.parent = contours[i].parent;
                    List<Contour> parentList = contours[i].parent == null
                                             ? rootContours
                                             : contours[i].parent.childs;
                    parentList.AddRange(contours[i].childs);
                    
                    contours[i].parent = null;
                    contours[i].childs.Clear();
                    while(!contours[i].forward.empty())
                        removeLink(contours[i].forward.getFirst());
                    while(!contours[i].backward.empty())
                        removeLink(contours[i].backward.getFirst());
                    
                    contours.RemoveAt(i--);
                }
            }

            // move contours in the holes to root
            for(int i = 0; i < rootContours.Count; ++i) {
                Contour contourA = rootContours[i];
                foreach(Contour contourB in contourA.childs) {
                    if (contourB.childs.Count != 0) {
                        foreach(Contour c in contourB.childs)
                            c.parent = null;
                        rootContours.AddRange(contourB.childs);
                    }
                }
            }
        }

        void calculate(bool simple) {
            resetTraceInformation();
            findIntersections();
            optimizePositions();
            buildContours();
            removeFreeLinks();
            buildContoursHierarhy(simple);
            removeEmptyPositions();
        }
    }
}