/*******************************************************************************
 * Copyright (c) 2007, 2010 Association for Decentralized Information Management
 * in Industry THTH ry.
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors:
 *     VTT Technical Research Centre of Finland - initial API and implementation
 *******************************************************************************/
package org.simantics.scenegraph.g2d.nodes.spatial;

import java.awt.Graphics2D;
import java.awt.RenderingHints;
import java.awt.Shape;
import java.awt.geom.AffineTransform;
import java.awt.geom.Rectangle2D;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Properties;
import java.util.Set;

import org.simantics.scenegraph.INode;
import org.simantics.scenegraph.g2d.G2DParentNode;
import org.simantics.scenegraph.g2d.G2DRenderingHints;
import org.simantics.scenegraph.g2d.IG2DNode;
import org.simantics.scenegraph.g2d.events.Event;
import org.simantics.scenegraph.g2d.events.EventTypes;
import org.simantics.scenegraph.g2d.events.INodeEventHandlerProvider;
import org.simantics.scenegraph.g2d.events.NodeEventHandler;
import org.simantics.scenegraph.utils.GeometryUtils;
import org.simantics.scenegraph.utils.NodeUtil;

import com.infomatiq.jsi.Rectangle;
import com.infomatiq.jsi.rtree.RTree;

import gnu.trove.TIntObjectHashMap;
import gnu.trove.TIntProcedure;

/**
 * A G2D scene graph node that spatially decomposes all of its immediate child
 * nodes into an R-Tree structure to optimize the painting of its direct child
 * based on whether they are visible in the current clip-bounds or not.
 * 
 * <p>
 * The clipping boundary, i.e. the current viewport is retrieved from
 * {@link Graphics2D#getClip()}. 
 * </p>
 * 
 * <p>
 * {@link #setDirty()} will mark the whole r-tree invalid meaning it will be
 * reconstructed from scratch when it is needed again.
 * </p>
 * 
 * TODO:
 * <ul>
 * <li>Add interface for marking children added/removed/changed to optimize
 * updates</li>
 * <li>With incremental updating, make sure that the r-tree is rebuilt every
 * once in a while. Updates will most likely cause r-tree performance to slowly
 * deteriorate.</li>
 * </ul>
 * 
 * @author Tuukka Lehtonen
 */
public class RTreeNode extends G2DParentNode implements INodeEventHandlerProvider {

    private static final boolean DISABLE_RTREE = false;

    private static final boolean DEBUG_SHRINK_CLIP_RECT = false;

    private static final long serialVersionUID = 8988645670981494042L;

    /**
     * A container for everything related to the R-tree based spatial
     * decomposition.
     */
    private static class Tree {
        public final RTree                          rtree;

        /**
         * Bounds of the whole R-tree.
         */
        public final Rectangle                      bounds;

        /**
         * May be null.
         */
        public final ArrayList<IG2DNode>            boundlessNodes;

        /**
         * Map from R-tree rectangle ID's to scene graph nodes.
         */
        public final TIntObjectHashMap<IG2DNode>    toNodes;

        /**
         * Map from R-tree rectangle ID's to current scene graph node bounds.
         * This prevents the need to unnecessarily recalculate the node bounds
         * in the node selection loop.
         */
        public final TIntObjectHashMap<Rectangle2D> toBounds;

        public Tree(RTree rtree, ArrayList<IG2DNode> boundlessNodes, TIntObjectHashMap<IG2DNode> toNodes, TIntObjectHashMap<Rectangle2D> toBounds) {
            this.rtree = rtree;
            this.bounds = rtree.getBounds();
            this.boundlessNodes = boundlessNodes;
            this.toNodes = toNodes;
            this.toBounds = toBounds;
        }
    }

    private transient volatile Tree       tree       = null;
    private transient ArrayList<IG2DNode> collected  = new ArrayList<IG2DNode>();
    private transient Set<IG2DNode>       simplified = new HashSet<IG2DNode>();

    @Override
    protected Map<String, INode> createChildMap() {
        return super.createChildMap(1 << 15);
    }

    @Override
    public void render(Graphics2D g) {
        if (DISABLE_RTREE) {
            super.render(g);
            return;
        }

        AffineTransform ot = null;
        if (!transform.isIdentity()) {
            ot = g.getTransform();
            g.transform(transform);
        }

        g.setRenderingHint(G2DRenderingHints.KEY_TRANSFORM_UNDER_SPATIAL_ROOT, g.getTransform());

        try {
            // Get transformed clip bounds
            Shape clipShape = g.getClip();
            Rectangle2D bounds = null;
            if (clipShape instanceof Rectangle2D)
                bounds = (Rectangle2D) clipShape;
            else if (clipShape != null)
                bounds = clipShape.getBounds2D();

            // Calculate values to optimize rendering based on view scale
            final double viewScale = GeometryUtils.getScale(g.getTransform());
            if (Math.abs(viewScale) <= Double.MIN_VALUE)
                return;
            final double unitsPerPixel = 1.0 / viewScale;
            //final double simplificationUnitsPerPixelLimit = 4*unitsPerPixel;
            //System.out.println("view scale: " + viewScale + " - " + unitsPerPixel + " - " + simplificationUnitsPerPixelLimit);

            // A bit of added margin for the clipping to
            // prevent the system from clipping symbols too
            // early in case they have out-of-bounds decorations.
            if (bounds != null)
                GeometryUtils.expandRectangle(bounds, 5);

            // !DEBUG!
            if (DEBUG_SHRINK_CLIP_RECT) {
                GeometryUtils.expandRectangle(bounds, -100.0*unitsPerPixel);
                g.draw(bounds);
            }

            // Make sure that a spatial decomposition exists.
            final Tree tree = getSpatialDecomposition();

            if (bounds == null || tree.bounds == null || containedBy(tree.bounds, bounds)) {
                // Direct render if no pruning can be done.
                for (IG2DNode node : getSortedNodes()) {
                    if (node.validate()) {
                        node.render(g);
                    }
                }
            } else {
                final Object render = g.getRenderingHint(RenderingHints.KEY_RENDERING);

                collected.clear();

                if (tree.boundlessNodes != null) {
                    for (int i = 0, n = tree.boundlessNodes.size(); i < n; ++i)
                        collected.add(tree.boundlessNodes.get(i));
                }

                tree.rtree.intersects(toRectangle(bounds), new TIntProcedure() {

                    @Override
                    public boolean execute(int value) {
                        //System.out.println("exec: " + value);
                        IG2DNode node = tree.toNodes.get(value);
                        //System.out.println("  node: " + node);
                        if (node == null || !node.validate())
                            return true;

                        if (render != RenderingHints.VALUE_RENDER_QUALITY) {
                            Rectangle2D r = tree.toBounds.get(value);
                            if (r == null)
                                return true;

                            double w = r.getWidth();
                            double h = r.getHeight();

                            //System.out.println("size: " + w + " x " + h);
                            if (w < unitsPerPixel && h < unitsPerPixel) {
                                //System.out.println("Skipping node: " + node);
                                return true;
                            }

//                        if (w < simplificationUnitsPerPixelLimit && h < simplificationUnitsPerPixelLimit) {
//                            //System.out.println("simplifying node: " + node);
//                            simplified.add(node);
//                        }
                        }

                        collected.add(node);
                        return true;
                    }
                });
                Collections.sort(collected, G2DParentNode.G2DNODE_Z_COMPARATOR);
                //System.out.println("rendering " + collected.size() + "/" + getNodeCount() + " children, " + simplified.size() + " as simplified");
                if (simplified.isEmpty()) {
                    for (IG2DNode node : collected)
                        if (node.validate())
                            node.render(g);
                } else {
                    for (IG2DNode node : collected) {
                        if (node.validate()) {
                            if (simplified.contains(node)) {
                                g.draw(node.getBoundsInLocal());
                            } else {
                                node.render(g);
                            }
                        }
                    }
                    simplified.clear();
                }
            }

//        // !DEBUG / PROFILING!
//        g.setStroke(new BasicStroke(0.25f));
//        drawTree(g, tree.rtree);

        } finally {
            g.setRenderingHint(G2DRenderingHints.KEY_TRANSFORM_UNDER_SPATIAL_ROOT, null);
            if (ot != null)
                g.setTransform(ot);
        }
    }

//    private void drawTree(final Graphics2D g, RTree rtree) {
//        final Rectangle2D r = new Rectangle2D.Double();
//        tree.rtree.traverse(new IRectangleTraverseProcedure() {
//            @Override
//            public void call(double x0, double y0, double x1, double y1, int level, Object value) {
//                r.setFrameFromDiagonal(x0, y0, x1, y1);
//                g.setColor(getLevelColor(level));
//                g.draw(r);
//            }
//
//            private Color getLevelColor(int level) {
//                switch (level) {
//                    case 0: return Color.DARK_GRAY;
//                    case 1: return Color.RED;
//                    case 2: return Color.PINK;
//                    case 3: return Color.BLUE;
//                    case 4: return Color.ORANGE;
//                    default: return Color.BLACK;
//                }
//            }
//        });
//    }

    @ClientSide
    public void setDirty() {
        tree = null;
    }

    private Tree getSpatialDecomposition() {
        Tree t = tree;
        if (t == null) {
            t = decompose();
            tree = t;
        }
        return t;
    }

    Properties props = new Properties();

    private Tree decompose() {
        RTree rtree = new RTree();
        rtree.init(props);
        IG2DNode[] nodes = getSortedNodes();
        TIntObjectHashMap<IG2DNode> toNodes = new TIntObjectHashMap<IG2DNode>(nodes.length);
        TIntObjectHashMap<Rectangle2D> toBounds = new TIntObjectHashMap<Rectangle2D>(nodes.length);
        int rid = 0;
        ArrayList<IG2DNode> boundlessNodes = null;
        for (IG2DNode node : nodes) {
            Rectangle2D bounds = node.getBounds();
            if (bounds != null) {
                Rectangle r = toRectangle(bounds);
                int id = ++rid;
                rtree.add(r, id);
                toNodes.put(id, node);
                toBounds.put(id, bounds);
            } else {
                if (boundlessNodes == null)
                    boundlessNodes = new ArrayList<IG2DNode>();
                boundlessNodes.add(node);
            }
        }
        return new Tree(rtree, boundlessNodes, toNodes, toBounds);
    }

    /**
     * @param rect
     * @return
     */
    public static Rectangle toRectangle(Rectangle2D rect) {
        return new Rectangle((float) rect.getMinX(), (float) rect.getMinY(), (float) rect.getMaxX(), (float) rect.getMaxY());
    }

    public List<IG2DNode> intersectingNodes(Rectangle2D rect, List<IG2DNode> result) {
        final Tree tree = getSpatialDecomposition();
        if (rect == null || tree.bounds == null || containedBy(tree.bounds, rect)) {
            IG2DNode[] nodes = getSortedNodes();
            for (IG2DNode node : nodes) {
                if (node.validate()) {
                    result.add(node);
                }
            }
        } else {
            tree.rtree.intersects(toRectangle(rect), value -> {
                //System.out.println("exec: " + value);
                IG2DNode node = tree.toNodes.get(value);
                //System.out.println("  node: " + node);
                if (node == null || !node.validate())
                    return true;

                result.add(node);
                return true;
            });
        }
        Collections.sort(result, G2DParentNode.G2DNODE_Z_COMPARATOR);
        return result;
    }

    /**
     * Determine whether this rectangle is contained by the passed rectangle
     * 
     * @param contained the rectangle tested to see if it contained by container
     * @param container The rectangle that might contain this rectangle
     * 
     * @return <code>true</code> if the container contains contained,
     *         <code>false</code> if it does not
     */
    public static boolean containedBy(Rectangle contained, Rectangle2D container) {
        return container.getMaxX() >= contained.maxX && container.getMinX() <= contained.minX
        && container.getMaxY() >= contained.maxY && container.getMinY() <= contained.minY;
    }

    @Override
    public void init() {
        super.init();
        //addEventHandler(this);
    }

    @Override
    public void cleanup() {
        //removeEventHandler(this);
        super.cleanup();
    }

    @Override
    public int getEventMask() {
        return EventTypes.MouseMask;
    }

    @Override
    public boolean handleEvent(Event e) {
        // Propagate mouse events to children based on bounds.
        //System.out.println("R-TREE HANDLE EVENT: " + e);
        return false;
    }

    @Override
    public NodeEventHandler getEventHandler() {
        // TODO: add an event handler here and propagate mouse events spatially 
        return NodeUtil.getNodeEventHandler(this);
    }

}