/*

    ......... 2015 Ivan Mahonin

    This program is free software: you can redistribute it and/or modify

    it under the terms of the GNU General Public License as published by

    the Free Software Foundation, either version 3 of the License, or

    (at your option) any later version.

    This program is distributed in the hope that it will be useful,

    but WITHOUT ANY WARRANTY; without even the implied warranty of

    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License

    along with this program.  If not, see <http://www.gnu.org/licenses/>.

*/

using System;

using System.Collections.Generic;

using System.Linq;

using System.Drawing;

namespace Contours {

    public class Shape {

        public class Exception: System.Exception { }

        public enum CombinationMode {

            Add,

            Subtract,

            Intersection,

            Xor

        }

        class Position {

            public Point point;

            public bool processed = false;

            public readonly Circuit<Position, Link> output;

            public readonly Circuit<Position, Link> input;

            public Position() {

                output = new Circuit<Position, Link>(this);

                input = new Circuit<Position, Link>(this);

            }

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

        }

        class Contour {

            public bool inverted = false;

            public Contour parent;

            public readonly List<Contour> childs = new List<Contour>();

            public readonly Circuit<Contour, Link> links;

            public Contour() {

                links = new Circuit<Contour, Link>(this);

            }

        }

        class Link {

            public bool alien = false;

            public bool inside = false;

            public readonly Circuit<Position, Link>.Entry p0;

            public readonly Circuit<Position, Link>.Entry p1;

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

            public Link() {

                p0 = new Circuit<Position, Link>.Entry(this);

                p1 = new Circuit<Position, Link>.Entry(this);

                contour = new Circuit<Contour, Link>.Entry(this);

            }

            public Link split(Shape shape, Position position) {

                if (position.point == p0.getParent().point)

                    return this;

                if (position.point == p1.getParent().point)

                    return p1.getCircuit().getFirst();

                shape.log.linkSplitted(this, position);

                Link link = new Link();

                link.alien = alien;

                link.p0.insertBack(position.output);

                link.p1.insertBack(p1.getCircuit());

                link.contour.insertAfterOf(contour);

                p1.insertBack(position.input);

                shape.links.Add(link);

                return link;

            }

            public Link split(Shape shape, Link positionLink) {

                return split(shape, positionLink.p0.getParent());

            }

            public void flip(Shape shape) {

                shape.log.linkFlipped(this);

                Position pos0 = p0.getParent();

                Position pos1 = p1.getParent();

                p0.insertFront(pos1.output);

                p1.insertFront(pos0.input);

            }

        }

        class Log {

            public readonly Shape shape;

            public bool enabled = true;

            public string filename = "log.txt";

            public Log(Shape shape) { this.shape = shape;  }

            string toString(Position position) {

                return string.Format(

                    "{0,2}#({1,3}, {2,3})",

                    shape.positions.IndexOf(position),

                    position.point.X,

                    position.point.Y);

            }

            string toString(Link link) {

                return string.Format(

                    "{0,2}# {1}{2} {3} {4}",

                    shape.links.IndexOf(link),

                    link.alien ? "B" : "A",

                    link.inside ? "I" : "O",

                    toString(link.p0.getParent()),

                    toString(link.p1.getParent()) );

            }

            string toString(Contour contour) {

                string s = "";

                for(Link link = contour.links.getFirst(); link != null; link = link.contour.getNextLinear()) {

                    if (s != "") s += ", ";

                    s += string.Format("({0}, {1})", link.p0.getParent().point.X, link.p0.getParent().point.Y);

                }

                return s;

            }

            public void line(string line) {

                if (!enabled) return;

                System.IO.File.AppendAllLines(filename, new string[] { line });

            }

            public void linkAdded(Link link) {

                if (!enabled) return;

                line("Link added " + toString(link));

            }

            public void linkRemoved(Link link) {

                if (!enabled) return;

                line("Link removed " + toString(link));

            }

            public void linkSplitted(Link link, Position position) {

                if (!enabled) return;

                line("Link splitted " + toString(link) + " / " + toString(position));

            }

            public void linkFlipped(Link link) {

                if (!enabled) return;

                line("Link flipped " + toString(link));

            }

            public void linkSwapped(Link a, Link b) {

                if (!enabled) return;

                line("Link swapped " + toString(a) + " <-> " + toString(b));

            }

            public void positionState(Position position) {

                line("position " + toString(position));

                for(Link link = position.output.getFirst(); link != null; link = link.p0.getNextLinear())

                    line("    output " + toString(link));

                for(Link link = position.input.getFirst(); link != null; link = link.p1.getNextLinear())

                    line("    input " + toString(link));

            }

            public void state(string title) {

                if (!enabled) return;

                line("-- current state (" + title + ") --");

                line("-- links --");

                foreach(Link link in shape.links)

                    line("    " + toString(link));

                line("-- positions --");

                foreach(Position position in shape.positions)

                    positionState(position);

                line("-- contours --");

                foreach(Contour contour in shape.contours)

                    line("    " + toString(contour));

                line("-- current state end --");

            }

        }

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

        readonly Log log;

        public Shape() { log = new Log(this); }

        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<IEnumerable<Point>>> contours) {

            List<IEnumerable<Point>> list = new List<IEnumerable<Point>>();

            foreach(IEnumerable<IEnumerable<Point>> c in contours)

                list.AddRange(c);

            setContours(list);

        }

        public void setContours(IEnumerable<IEnumerable<Point>> contours) {

            clear();

            log.line("---- setContours begin ----");

            foreach(IEnumerable<Point> contour in contours) {

                if (contour.Count() >= 3) {

                    Link first = null;

                    Link previous = null;

                    foreach(Point point in contour) {

                        Position position = new Position(point);

                        positions.Add(position);

                        Link link = new Link();

                        link.p0.insertBack(position.output);

                        if (previous != null)

                            previous.p1.insertBack(link.p0.getParent().input);

                        links.Add(link);

                        if (first == null) first = link;

                        previous = link;

                    }

                    previous.p1.insertBack(first.p0.getParent().input);

                }

            }

            log.state("loaded");

            findIntersections();

            log.state("intersections solved");

            removeDuplicateLinks();

            log.state("duplicates removed");

            fixLinksDirections();

            log.state("directions fixed");

            buildContours();

            removeFreeLinks();

            concatenateLinks();

            log.state("links concatenated");

            buildContoursHierarhy();

            removeEmptyPositions();

            log.state("setContours complete");

            log.line("---- setContours end ----");

        }

        // returns list of root contour groups

        // first contour in group is outer contour, others - inner

        public List<List<List<Point>>> getContours() {

            List<List<List<Point>>> groups = new List<List<List<Point>>>();

            foreach(Contour root in rootContours) {

                List<List<Point>> list = new List<List<Point>>();

                list.Add(contourToList(root));

                foreach(Contour c in root.childs)

                    list.Add(contourToList(c));

                groups.Add(list);

            }

            return groups;

        }

        List<Point> contourToList(Contour contour) {

            List<Point> list = new List<Point>();

            for(Link link = contour.links.getFirst(); link != null; link = link.contour.getNextLinear())

                list.Add(link.p0.getParent().point);

            return list;

        }

        void resetTraceInformation() {

            for(int i = 0; i < contours.Count; ++i) {

                contours[i].links.clear();

                contours[i].childs.Clear();

                contours[i].parent = null;

            }

            contours.Clear();

            rootContours.Clear();

        }

        void removeLink(Link link) {

            log.linkRemoved(link);

            link.p0.unlink();

            link.p1.unlink();

            link.contour.unlink();

            links.Remove(link);

        }

        void removeEmptyPositions() {

            for(int i = 0; i < positions.Count; ++i)

                if (positions[i].output.empty() != positions[i].input.empty())

                    throw new Exception();

                else

                if (positions[i].output.empty() && positions[i].input.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].output.getFirst() != null)

                                positions[j].output.getFirstEntry().insertBack(positions[i].output);

                            while(positions[j].input.getFirst() != null)

                                positions[j].input.getFirstEntry().insertBack(positions[i].input);

                            positions.RemoveAt(j--);

                        }

                    }

                }

                // remove zero-length links

                // this procedure may create empty positions

                for(int i = 0; i < links.Count; ++i)

                    if (links[i].p0.getParent() == links[i].p1.getParent())

                        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.p0.getParent();

                        Position a1 = a.p1.getParent();

                        Position b0 = b.p0.getParent();

                        Position b1 = b.p1.getParent();

                        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;

                        }

                    }

                }

            }

        }

        void removeDuplicateLinks() {

            foreach(Position position in positions)

                position.processed = false;

            foreach(Position position in positions) {

                position.processed = true;

                Link ol = position.output.getFirst();

                Link il = position.input.getFirst();

                while(ol != null || il != null) {

                    Link linkOut = ol;

                    Link linkIn = il;

                    Position nextPosition = linkOut == null

                                          ? linkIn.p0.getParent()

                                          : linkOut.p1.getParent();

                    while(ol != null && ol.p1.getParent() == nextPosition)

                        ol = ol.p0.getNextLinear();

                    while(il != null && il.p0.getParent() == nextPosition)

                        il = il.p1.getNextLinear();

                    if (nextPosition.processed) continue;

                    bool remove = true;

                    Link first = null;

                    for(Link lb = linkOut; lb != null;) {

                        Link linkB = lb;

                        lb = lb.p0.getNextLinear();

                        if (linkB.p1.getParent() == nextPosition) {

                            remove = !remove;

                            if (first == null) first = linkB; else removeLink(linkB);

                        }

                    }

                    for(Link lb = linkIn; lb != null;) {

                        Link linkB = lb;

                        lb = lb.p1.getNextLinear();

                        if (linkB.p0.getParent() == nextPosition) {

                            remove = !remove;

                            if (first == null) first = linkB; else removeLink(linkB);

                        }

                    }

                    if (remove) removeLink(first);

                }

            }

        }

        void fixLinksDirections() {

            log.line("-- fixLinksDirections begin --");

            if (positions.Count == 0) return;

            foreach(Link linkA in links) {

                Point p0 = linkA.p0.getParent().point;

                Point p1 = linkA.p1.getParent().point;

                Point d = new Point(p1.X - p0.X, p1.Y - p0.Y);

                p1 = new Point(p0.X - d.Y, p0.Y + d.X);

                Geometry.makeLongestLine(p0, ref p1);

                bool inside = true;

                foreach(Link linkB in links) {

                    if (linkA != linkB) {

                        Point pp0 = linkB.p0.getParent().point;

                        Point pp1 = linkB.p1.getParent().point;

                        Point c = new Point(0, 0);

                        switch( Geometry.findIntersection(p0, p1, pp0, pp1, out c) ) {

                            case Geometry.IntersectionType.Cross:

                                inside = !inside;

                                break;

                            case Geometry.IntersectionType.Touch_b0:

                                if ((long)(pp1.X-p0.X)*(long)d.X + (long)(pp1.Y-p0.Y)*(long)d.Y > 0)

                                    inside = !inside;

                                break;

                            case Geometry.IntersectionType.Touch_b1:

                                if ((long)(pp0.X-p0.X)*(long)d.X + (long)(pp0.Y-p0.Y)*(long)d.Y > 0)

                                    inside = !inside;

                                break;

                            case Geometry.IntersectionType.Touch_a0_b0:

                                if ((long)(pp1.X-p0.X)*(long)d.X + (long)(pp1.Y-p0.Y)*(long)d.Y > 0

                                 && (long)(pp1.Y-p0.Y)*(long)d.X - (long)(pp1.X-p0.X)*(long)d.Y > 0)

                                    inside = !inside;

                                break;

                            case Geometry.IntersectionType.Touch_a0_b1:

                                if ((long)(pp0.X-p0.X)*(long)d.X + (long)(pp0.Y-p0.Y)*(long)d.Y > 0

                                 && (long)(pp0.Y-p0.Y)*(long)d.X - (long)(pp0.X-p0.X)*(long)d.Y > 0)

                                    inside = !inside;

                                break;

                            default:

                                break;

                        }

                    }

                }

                if (inside) linkA.flip(this);

            }

            log.line("-- fixLinksDirections end --");

        }

        void findLinksInside() {

            for(int i = 0; i < links.Count; ++i) {

                int intersectionsCount = 0;

                Point p0 = links[i].p0.getParent().point;

                Point p1 = links[i].p1.getParent().point;

                Geometry.makeLongestLine(p0, ref p1);

                for(int j = 0; j < links.Count; ++j) {

                    if (i != j && links[i].alien != links[j].alien) {

                        Point c = new Point(0, 0);

                        Point pp0 = links[j].p0.getParent().point;

                        Point pp1 = links[j].p1.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) );

                        switch(Geometry.findIntersection(p0, p1, pp0, pp1, out c)) {

                            case Geometry.IntersectionType.Cross:

                                intersectionsCount += 2*d;

                                break;

                            case Geometry.IntersectionType.Touch_b0:

                            case Geometry.IntersectionType.Touch_b1:

                                intersectionsCount += d;

                                break;

                            default:

                                break;

                        }

                    }

                }

                links[i].inside = intersectionsCount == 2;

            }

        }

        bool combine(CombinationMode mode, bool self, bool alien) {

            switch(mode) {

                case CombinationMode.Add: return self || alien;

                case CombinationMode.Subtract: return self && !alien;

                case CombinationMode.Intersection: return self && alien;

                case CombinationMode.Xor: return self != alien;

                default: break;

            }

            return false;

        }

        void removeUnusedLinks(CombinationMode mode) {

            foreach(Position position in positions)

                position.processed = false;

            foreach(Position position in positions) {

                position.processed = true;

                Link ol = position.output.getFirst();

                Link il = position.input.getFirst();

                while(ol != null || il != null) {

                    Link linkOut = ol;

                    Link linkIn = il;

                    Position nextPosition = linkOut == null

                                          ? linkIn.p0.getParent()

                                          : linkOut.p1.getParent();

                    while(ol != null && ol.p1.getParent() == nextPosition)

                        ol = ol.p0.getNextLinear();

                    while(il != null && il.p0.getParent() == nextPosition)

                        il = il.p1.getNextLinear();

                    if (nextPosition.processed) continue;

                    bool forwardSelf = false;

                    bool forwardAlien = false;

                    Link forwardLink = null;

                    bool backwardSelf = false;

                    bool backwardAlien = false;

                    Link backwardLink = null;

                    for(Link lb = linkOut; lb != null;) {

                        Link linkB = lb;

                        lb = lb.p0.getNextLinear();

                        if (linkB.p1.getParent() == nextPosition) {

                            if (linkB.alien) {

                                forwardAlien = true;

                                if (linkB.inside) forwardSelf = backwardSelf = true;

                            } else {

                                forwardSelf = true;

                                if (linkB.inside) forwardAlien = backwardAlien = true;

                            }

                            if (forwardLink == null) forwardLink = linkB; else removeLink(linkB);

                        }

                    }

                    for(Link lb = linkIn; lb != null;) {

                        Link linkB = lb;

                        lb = lb.p1.getNextLinear();

                        if (linkB.p0.getParent() == nextPosition) {

                            if (linkB.alien) {

                                backwardAlien = true;

                                if (linkB.inside) forwardSelf = backwardSelf = true;

                            } else {

                                backwardSelf = true;

                                if (linkB.inside) forwardAlien = backwardAlien = true;

                            }

                            if (backwardLink == null) backwardLink = linkB; else removeLink(linkB);

                        }

                    }

                    bool forward = combine(mode, forwardSelf, forwardAlien);

                    bool backward = combine(mode, backwardSelf, backwardAlien);

                    if (forwardLink == null && backwardLink == null)

                        throw new Exception();

                    if (forward && !backward) {

                        if (forwardLink == null) backwardLink.flip(this);

                            else if (backwardLink != null) removeLink(backwardLink);

                    } else

                    if (!forward && backward) {

                        if (backwardLink == null) forwardLink.flip(this);

                            else if (forwardLink != null) removeLink(forwardLink);

                    } else {

                        if (forwardLink != null) removeLink(forwardLink);

                        if (backwardLink != null) removeLink(backwardLink);

                    }

                }

            }

        }

        void buildContours() {

            for(int i = 0; i < links.Count; ++i) {

                if (links[i].contour.getParent() == null) {

                    Contour contour = new Contour();

                    contours.Add(contour);

                    Link link = links[i];

                    do {

                        if (link.contour.getParent() != null)

                            throw new Exception();

                        link.contour.insertBack(contour.links);

                        // find first link CW order (so we turns left)

                        Link nextLink = link.p1.getParent().output.getFirst();

                        for(Link l = nextLink.p0.getNext(); l != null; l = l.p0.getNextLinear())

                            if ( Geometry.isCCW(

                                    link.p1.getParent().point,

                                    link.p0.getParent().point,

                                    nextLink.p1.getParent().point,

                                    l.p1.getParent().point ))

                                { nextLink = l; }

                        // select first link by the left (links should be CCW-ordered)

                        link = nextLink;

                    } while (link != links[i]);

                }

            }

        }

        void concatenateLinks() {

            foreach(Contour contour in contours) {

                for(Link linkA = contour.links.getFirst(); linkA != null;) {

                    Link linkB = linkA.contour.getNext();

                    if ( Geometry.isPointAtLine(

                            linkA.p1.getParent().point,

                            linkA.p0.getParent().point,

                            linkB.p1.getParent().point ))

                    {

                        linkA.p1.insertAfterOf(linkB.p1);

                        removeLink(linkB);

                        if (linkA == linkB) break;

                    } else {

                        linkA = linkA.contour.getNextLinear();

                    }

                }

            }

        }

        // 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.links.getFirst(); link != null; link = link.contour.getNextLinear()) {

                Point pp0 = link.p0.getParent().point;

                Point pp1 = link.contour.getNext().p0.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:

                case Geometry.IntersectionType.Touch_b1:

                    count += d;

                    break;

                default:

                    break;

                }

            }

            return count;

        }

        bool isContourInverted(Contour contour) {

            Link first = contour.links.getFirst();

            Point p0 = first.p0.getParent().point;

            Point p1 = first.contour.getNext().p0.getParent().point;

            Geometry.makeLongestLine(p0, ref p1);

            return countIntersectionsWithContour(p0, p1, contour) < 0;

        }

        bool isContourInside(Contour inner, Contour outer) {

            Link first = inner.links.getFirst();

            Point p0 = first.p0.getParent().point;

            Point p1 = first.contour.getNext().p0.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() {

            // 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 = i+1; 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);

            // 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].links.empty())

                        removeLink(contours[i].links.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(CombinationMode combinationMode) {

            log.state("calculation begin");

            resetTraceInformation();

            findIntersections();

            log.state("intersections solved");

            findLinksInside();

            log.state("inside found");

            removeUnusedLinks(combinationMode);

            log.state("unused links removed");

            buildContours();

            removeFreeLinks();

            concatenateLinks();

            log.state("links concatenated");

            buildContoursHierarhy();

            removeEmptyPositions();

            log.state("calculation complete");

        }

        public static Shape combine(CombinationMode mode, Shape a, Shape b) {

            Shape sum = new Shape();

            sum.log.enabled = a.log.enabled && b.log.enabled;

            sum.log.line(string.Format("---- combine {0} begin ----", mode));

            // clone a

            for(int i = 0; i < a.positions.Count; ++i)

                sum.positions.Add(new Position(a.positions[i].point));

            for(int i = 0; i < a.positions.Count; ++i) {

                for(Link link = a.positions[i].output.getFirst(); link != null; link = link.p0.getNextLinear()) {

                    Link l = new Link();

                    l.alien = false;

                    l.p0.insertBack(sum.positions[i].output);

                    l.p1.insertBack(sum.positions[a.positions.IndexOf(link.p1.getParent())].input);

                    sum.links.Add(l);

                }

            }

            // clone b

            for(int i = 0; i < b.positions.Count; ++i)

                sum.positions.Add(new Position(b.positions[i].point));

            for(int i = 0; i < b.positions.Count; ++i) {

                for(Link link = b.positions[i].output.getFirst(); link != null; link = link.p0.getNextLinear()) {

                    Link l = new Link();

                    l.alien = true;

                    l.p0.insertBack(sum.positions[a.positions.Count + i].output);

                    l.p1.insertBack(sum.positions[a.positions.Count + b.positions.IndexOf(link.p1.getParent())].input);

                    sum.links.Add(l);

                }

            }

            sum.calculate(mode);

            sum.log.line("---- combine end ----");

            return sum;

        }

        public static Shape add(Shape a, Shape b)

            { return combine(CombinationMode.Add, a, b); }

        public static Shape subtract(Shape a, Shape b)

            { return combine(CombinationMode.Subtract, a, b); }

        public static Shape intersection(Shape a, Shape b)

            { return combine(CombinationMode.Intersection, a, b); }

        public static Shape xor(Shape a, Shape b)

            { return combine(CombinationMode.Xor, a, b); }

    }

}