/*---------------------------------------------------------------------------*\

    geophase: A C++ template library for geometrical operations on non-convex
    polyhedra with non-planar faces
     
    Copyright (C) 2019 Tomislav Maric, TU Darmstadt 

    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/>.

Description
    Find extreme points of a geometry along an axis.

Authors
    Tomislav Maric maric@mma.tu-darmstadt.de

\*---------------------------------------------------------------------------*/

#ifndef ExtremePoints_HPP
#define ExtremePoints_HPP

#include <utility>
#include <vector>
#include <algorithm>

#include "constants.hpp"
#include "tag.hpp"

namespace geophase { 

    template<typename PointSequence> 
    std::enable_if_t 
    <
        tag_base_of<PointSequence, point_sequence_tag>(),
        std::pair 
        <
            typename PointSequence::value_type, 
            typename PointSequence::value_type
        >
    > 
    extreme_points(PointSequence const & points)
    {
        using Point = typename PointSequence::value_type; 

        auto result = std::make_pair<Point,Point>(
            Point{MAX,MAX,MAX},
            Point{LOWEST,LOWEST,LOWEST}
        );

        for (const auto& point : points)
        {
            assign_less(result.first, point); 
            assign_greater(result.second, point);
        }

        return result;
    }

    template <typename Vector>  
    enable_if_type_tagged_t
    <
        Vector, vector_tag, 
        std::pair<Vector, typename Vector::value_type>
    >
    project_point(
        Vector const & projectedPoint, 
        Vector const & refPoint, 
        Vector const & direction
    )
    {
        return std::make_pair(
            projectedPoint, 
            dot((projectedPoint - refPoint),direction)
        ); 
    }

    template 
    <
        typename PointSequence, 
        typename Vector
    >
    typename std::enable_if
    <
        tag_base_of<PointSequence, point_sequence_tag>(),
        std::pair
        <
            typename PointSequence::value_type,
            typename PointSequence::value_type
        >
    >::type 
    extreme_points(PointSequence const& polygon, Vector const& direction)
    {
        using Point = typename PointSequence::value_type;
        using RealType = typename Point::value_type;
        using PointProjectionPair = std::pair<Point, RealType>;

        std::vector<PointProjectionPair> pointProjectionPairs; 

        Point refPoint = {}; 

        // Project points.
        for(const auto& point : polygon)
            pointProjectionPairs.push_back(project_point(point, refPoint, direction));

        // Sort points by their by projections. 
        std::sort(
            pointProjectionPairs.begin(), 
            pointProjectionPairs.end(), 
            [](PointProjectionPair const& pp1, PointProjectionPair const& pp2){ 
                return pp1.second < pp2.second; 
            }
        );

        return std::make_pair (
            pointProjectionPairs.front().first, 
            pointProjectionPairs.back().first
        );
    }

    template <typename PolygonSequence>
    std::enable_if_t
    <
        tag_base_of<PolygonSequence, sequence_polyhedron_tag>(),
        std::pair
        <
            typename PolygonSequence::value_type::value_type, 
            typename PolygonSequence::value_type::value_type
        >
    >
    extreme_points(PolygonSequence const& polyhedron)
    {
        using Point = typename PolygonSequence::value_type::value_type; 
        auto result = std::make_pair<Point,Point>(
            Point{MAX,MAX,MAX},
            Point{LOWEST,LOWEST,LOWEST}
        );

        for (const auto& polygon : polyhedron)
            for (const auto& point : polygon)
            {
                assign_less(result.first, point); 
                assign_greater(result.second, point);
            }

        return result; 
    }

    template 
    <
        typename PolygonSequence, 
        typename Vector
    >
    std::enable_if_t
    <
        tag_base_of<PolygonSequence, sequence_polyhedron_tag>() &&
        type_tagged<Vector, vector_tag>(), 
        std::pair
        <
            typename PolygonSequence::value_type::value_type, 
            typename PolygonSequence::value_type::value_type
        >
    >
    extreme_points(PolygonSequence const& polyhedron, Vector const& direction)
    {
        using Point = typename PolygonSequence::value_type::value_type;
        using AT = typename Point::value_type; 
        using PointProjection = std::pair<Point, AT>; 

        std::vector<PointProjection> pointProjections; 
        Point refPoint = {}; 

        for(const auto& polygon : polyhedron)
            for(const auto& point : polygon)
                pointProjections.push_back(project_point(point, refPoint, direction));

        std::sort(
            pointProjections.begin(), 
            pointProjections.end(), 
            [](PointProjection const & pp1, PointProjection const &pp2)->bool{ 
                return pp1.second < pp2.second; 
            }
        );

        return std::make_pair
        (
            pointProjections.front().first,
            pointProjections.back().first
        );
    }

} // End namespace geophase 

#endif

// ************************************************************************* //
