/*******************************************************************************
 * This file is part of Shadowfax
 * Copyright (C) 2015 Bert Vandenbroucke (bert.vandenbroucke@gmail.com)
 *
 * Shadowfax is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Affero General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * Shadowfax is distributed in the hope that it will be useful,
 * but WITOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU Affero General Public License for more details.
 *
 * You should have received a copy of the GNU Affero General Public License
 * along with Shadowfax. If not, see <http://www.gnu.org/licenses/>.
 ******************************************************************************/

/**
 * @file BinarySearchTree.hpp
 *
 * @brief Binary search tree for Fortune's algorithm: header
 *
 * @author Bert Vandenbroucke (bert.vandenbroucke@ugent.be)
 */
#ifndef BINARYSEARCHTREE_HPP
#define BINARYSEARCHTREE_HPP

#if ndim_ == 2

#include "Vec.hpp"  // for Vec
#include <cmath>    // for sqrt
#include <ostream>  // for ostream

class BinaryLeaf;
class CircleEvent;
class DelCont;
class DoublyConnectedEdgeList;
class Edge;

/**
 * @brief Mesh generator for Fortune's algorithm
 */
class FortuneSite {
  private:
    /*! @brief Position of the mesh generator */
    Vec _position;

  public:
    /**
     * @brief Constructor
     *
     * @param position Position of the mesh generator
     */
    FortuneSite(Vec position) : _position(position) {}
    ~FortuneSite() {}

    /**
     * @brief Get the position of the generator
     *
     * @return Position of the generator
     */
    Vec get_position() {
        return _position;
    }
};

/**
 * @brief Internal node of the BinarySearchTree
 *
 * The BinaryInternalNode either has two children which are themselves
 * internal nodes, or a BinaryLeaf, which corresponds to the lowest level in
 * this part of the tree.
 * If the node has two children, it traces out an edge of the Voronoi diagram.
 */
class BinaryInternalNode {
  private:
    /*! @brief Left generator of the associated edge */
    FortuneSite* _pleft;

    /*! @brief Right generator of the associated edge */
    FortuneSite* _pright;

    /*! @brief Children if this node is an internal node */
    BinaryInternalNode* _children[2];

    /*! @brief Parent node */
    BinaryInternalNode* _parent;

    /*! @brief Associated edge */
    Edge* _edge;

    /*! @brief Single child if this node is a leaf of the tree */
    BinaryLeaf* _leaf;

    void check_balance(int n);
    int depth();
    void rebalance();

    FortuneSite* get_pleft();
    FortuneSite* get_pright();

    void set_pleft(FortuneSite* pleft);
    void set_pright(FortuneSite* pright);
    void set_child(BinaryInternalNode* child, unsigned int index);
    void set_parent(BinaryInternalNode* parent);

    void check_balance_recursive();

  public:
    BinaryInternalNode(FortuneSite* pleft, FortuneSite* pright,
                       BinaryInternalNode* parent);
    ~BinaryInternalNode();

    void erase();

    /**
     * @brief Get the leaf of this node
     *
     * @return Leaf stored in this node
     */
    BinaryLeaf* get_leaf() {
        return _leaf;
    }

    BinaryInternalNode* get_child(unsigned int index);
    void set_edge(Edge* edge);
    Edge* get_edge();

    BinaryLeaf* add(FortuneSite* site, double ybeach, CircleEvent** events);
    void make_leaf(BinaryLeaf* leaf);
    void add_subnode(FortuneSite* pleft, FortuneSite* pright,
                     unsigned int index, BinaryLeaf** new_leaves);
    void add_leaf(BinaryLeaf* leaf, unsigned int index);

    void remove(BinaryLeaf* leaf, double ybeach, CircleEvent** events,
                Edge** edges);
    void convert_child(BinaryInternalNode* child,
                       BinaryInternalNode* grandchild, BinaryLeaf* leaf,
                       double ybeach, CircleEvent** events, Edge** edges);
    BinaryInternalNode* get_parent();

    void plot(std::ostream& stream, double origin, double width, int level);

    void trim_edges();

    void get_halfedges(DoublyConnectedEdgeList& vorlist, DelCont* container);

    /**
     * @brief Calculate the y-coordinate of the intersection point of the arcs
     * generated by the two given generators and the given beachline
     *
     * @param left Coordinates of the left generator
     * @param right Coordinates of the right generator
     * @param ybeach y-coordinate of the beachline
     * @return y-coordinate of the intersection point
     */
    static double intersection(Vec left, Vec right, double ybeach) {
        double a1 = 2. * (left[1] - ybeach);
        if(a1 > 0.) {
            a1 = 1. / a1;
        } else {
            return left[0];
        }
        double a2 = 2. * (right[1] - ybeach);
        if(a2 > 0.) {
            a2 = 1. / a2;
        } else {
            return right[0];
        }
        if(a1 == a2) {
            return 0.5 * (left[0] + right[0]);
        }
        double b1 = a1 * left[0];
        double b2 = a2 * right[0];
        double c1 = 0.5 * (left[1] + ybeach) + b1 * left[0];
        double c2 = 0.5 * (right[1] + ybeach) + b2 * right[0];
        b1 *= -2.;
        b2 *= -2.;
        double adiff = a1 - a2;
        double bdiff = b1 - b2;
        double cdiff = c1 - c2;
        return 0.5 * (-bdiff + sqrt(bdiff * bdiff - 4. * adiff * cdiff)) /
               adiff;
    }

    /**
     * @brief Calculate the midpoint and radius of the circle through the three
     * given points
     *
     * @param p1 Coordinates of the first point
     * @param p2 Coordinates of the second point
     * @param p3 Coordinates of the third point
     * @param midpoint Vec to store the midpoint of the circle in
     * @return Radius of the circle
     */
    static double get_circle(Vec p1, Vec p2, Vec p3, Vec& midpoint) {
        midpoint[0] = 0.;
        midpoint[1] = 0.;
        double D = 2. * (p1[0] * (p2[1] - p3[1]) + p2[0] * (p3[1] - p1[1]) +
                         p3[0] * (p1[1] - p2[1]));
        if(!D) {
            return 0.;
        }
        double p1p1 = p1.norm2();
        double p2p2 = p2.norm2();
        double p3p3 = p3.norm2();
        midpoint[0] = (p1p1 * (p2[1] - p3[1]) + p2p2 * (p3[1] - p1[1]) +
                       p3p3 * (p1[1] - p2[1])) /
                      D;
        midpoint[1] = (p1p1 * (p3[0] - p2[0]) + p2p2 * (p1[0] - p3[0]) +
                       p3p3 * (p2[0] - p1[0])) /
                      D;
        double midminp1x = midpoint[0] - p1[0];
        double midminp1y = midpoint[1] - p1[1];
        return sqrt(midminp1x * midminp1x + midminp1y * midminp1y);
    }
};

/**
 * @brief Leaf of the BinarySearchTree
 *
 * Every BinaryLeaf corresponds to an arc of the beachline in Fortune's
 * algorithm and is associated with a FortuneSite that traces it out and a
 * CircleEvent that signals the disappearance of the arc.
 */
class BinaryLeaf {
  private:
    /*! @brief Generator of the arc associated to the leaf */
    FortuneSite* _site;

    /*! @brief CircleEvent at which the arc disappears */
    CircleEvent* _event;

    /*! @brief Previous leaf in the tree */
    BinaryLeaf* _prev_leaf;

    /*! @brief Next leaf in the tree */
    BinaryLeaf* _next_leaf;

    /*! @brief Parent node */
    BinaryInternalNode* _parent;

  public:
    BinaryLeaf(FortuneSite* site, BinaryInternalNode* parent);
    ~BinaryLeaf() {}

    /**
     * @brief Get the generator of the arc associated with this leaf
     *
     * @return The generator of the arc
     */
    FortuneSite* get_site() {
        return _site;
    }

    void set_next_leaf(BinaryLeaf* next_leaf);
    void set_prev_leaf(BinaryLeaf* prev_leaf);

    /**
     * @brief Get the previous leaf in the tree
     *
     * @return The previous leaf in the tree
     */
    BinaryLeaf* get_prev_leaf() {
        return _prev_leaf;
    }

    /**
     * @brief Get the next leaf in the tree
     *
     * @return The next leaf in the tree
     */
    BinaryLeaf* get_next_leaf() {
        return _next_leaf;
    }

    void deactivate();

    /**
     * @brief Set the parent node of this leaf
     *
     * @param parent Parent node of this leaf
     */
    void set_parent(BinaryInternalNode* parent) {
        _parent = parent;
    }

    /**
     * @brief Get the parent node of this leaf
     *
     * @return The parent node of this leaf
     */
    BinaryInternalNode* get_parent() {
        return _parent;
    }

    double get_value(double x, double ybeach);

    /**
     * @brief Set the CircleEvent for this leaf
     *
     * @param event CircleEvent for this leaf
     */
    void set_event(CircleEvent* event) {
        _event = event;
    }
};

/**
 * @brief Binary search tree used in Fortune's algorithm
 */
class BinarySearchTree {
  private:
    /*! @brief Root node of the tree */
    BinaryInternalNode* _root;
    //    BinaryLeaf* _first_leaf;

  public:
    BinarySearchTree();
    ~BinarySearchTree();

    BinaryLeaf* add(FortuneSite* site, double ybeach, CircleEvent** events);
    void remove(BinaryLeaf* leaf, double ybeach, CircleEvent** events,
                Edge** edges);
    void plot(std::ostream& stream);
    void plot_beachline(std::ostream& stream, double ybeach);

    void trim_edges();
    void get_halfedges(DoublyConnectedEdgeList& vorlist, DelCont* container);

    void removetest();

    void print();
};

#endif

#endif  // BINARYSEARCHTREE_HPP
