/*
    ......... 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); }
    }
}