//////////////////////////////////////////////////////////////////////////
//
// This file is part of the BWEM Library.
// BWEM is free software, licensed under the MIT/X11 License. 
// A copy of the license is provided with the library in the LICENSE file.
// Copyright (c) 2015, 2017, Igor Dimitrijevic
//
//////////////////////////////////////////////////////////////////////////


#ifndef BWEM_CP_H
#define BWEM_CP_H

#include <BWAPI.h>
#include "bwapiExt.h"
#include <deque>
#include "utils.h"
#include "defs.h"


namespace BWEM {

class Neutral;
class Area;
class Map;

namespace detail { class Graph; }





//////////////////////////////////////////////////////////////////////////////////////////////
//                                                                                          //
//                                  class ChokePoint
//                                                                                          //
//////////////////////////////////////////////////////////////////////////////////////////////
//
// ChokePoints are frontiers that BWEM automatically computes from Brood War's maps
// A ChokePoint represents (part of) the frontier between exactly 2 Areas. It has a form of line.
// A ChokePoint doesn't contain any MiniTile: All the MiniTiles whose positions are returned by its Geometry()
// are just guaranteed to be part of one of the 2 Areas.
// Among the MiniTiles of its Geometry, 3 particular ones called nodes can also be accessed using Pos(middle), Pos(end1) and Pos(end2).
// ChokePoints play an important role in BWEM:
//   - they define accessibility between Areas.
//   - the Paths provided by Map::GetPath are made of ChokePoints.
// Like Areas and Bases, the number and the addresses of ChokePoint instances remain unchanged.
//
// Pseudo ChokePoints:
// Some Neutrals can be detected as blocking Neutrals (Cf. Neutral::Blocking).
// Because only ChokePoints can serve as frontiers between Areas, BWEM automatically creates a ChokePoint
// for each blocking Neutral (only one in the case of stacked blocking Neutral).
// Such ChokePoints are called pseudo ChokePoints and they behave differently in several ways.
//
// ChokePoints inherit utils::Markable, which provides marking ability
// ChokePoints inherit utils::UserData, which provides free-to-use data.

class ChokePoint : public utils::Markable<ChokePoint, int>, public utils::UserData
{
public:
    // ChokePoint::middle denotes the "middle" MiniTile of Geometry(), while
    // ChokePoint::end1 and ChokePoint::end2 denote its "ends".
    // It is guaranteed that, among all the MiniTiles of Geometry(), ChokePoint::middle has the highest altitude value (Cf. MiniTile::Altitude()).
    enum node {end1, middle, end2, node_count};

    // Type of all the Paths used in BWEM (Cf. Map::GetPath).
    // See also the typedef CPPath.
    typedef std::vector<const ChokePoint *> Path;

    // Tells whether this ChokePoint is a pseudo ChokePoint, i.e., it was created on top of a blocking Neutral.
    bool                                    IsPseudo() const        { return m_pseudo; }

    // Returns the two Areas of this ChokePoint.
    const std::pair<const Area *, const Area *> & GetAreas() const    { return m_Areas; }

    // Returns the center of this ChokePoint.
    const BWAPI::WalkPosition &                Center() const            { return Pos(middle); }

    // Returns the position of one of the 3 nodes of this ChokePoint (Cf. node definition).
    // Note: the returned value is contained in Geometry()
    const BWAPI::WalkPosition &                Pos(node n) const        { bwem_assert(n < node_count); return m_nodes[n]; }

    // Pretty much the same as Pos(n), except that the returned MiniTile position is guaranteed to be part of pArea.
    // That is: Map::GetArea(PosInArea(n, pArea)) == pArea.
    const BWAPI::WalkPosition &                PosInArea(node n, const Area * pArea) const;

    // Returns the set of positions that defines the shape of this ChokePoint.
    // Note: none of these MiniTiles actually belongs to this ChokePoint (a ChokePoint doesn't contain any MiniTile).
    //       They are however guaranteed to be part of one of the 2 Areas.
    // Note: the returned set contains Pos(middle), Pos(end1) and Pos(end2).
    // If IsPseudo(), returns {p} where p is the position of a walkable MiniTile near from BlockingNeutral()->Pos().
    const std::deque<BWAPI::WalkPosition> &    Geometry() const        { return m_Geometry; }

    // If !IsPseudo(), returns false.
    // Otherwise, returns whether this ChokePoint is considered blocked.
    // Normally, a pseudo ChokePoint either remains blocked, or switches to not blocked when BlockingNeutral()
    // is destroyed and there is no remaining Neutral stacked with it.
    // However, in the case where Map::AutomaticPathUpdate() == false, Blocked() will always return true
    // whatever BlockingNeutral() returns.
    // Cf. Area::AccessibleNeighbours().
    bool                                    Blocked() const            { return m_blocked; }

    // If !IsPseudo(), returns nullptr.
    // Otherwise, returns a pointer to the blocking Neutral on top of which this pseudo ChokePoint was created,
    // unless this blocking Neutral has been destroyed.
    // In this case, returns a pointer to the next blocking Neutral that was stacked at the same location,
    // or nullptr if no such Neutral exists.
    Neutral *                                BlockingNeutral() const    { return m_pBlockingNeutral; }

    // If AccessibleFrom(cp) == false, returns -1.
    // Otherwise, returns the ground distance in pixels between Center() and cp->Center().
    // Note: if this == cp, returns 0.
    // Time complexity: O(1)
    // Note: Corresponds to the length in pixels of GetPathTo(cp). So it suffers from the same lack of accuracy.
    //       In particular, the value returned tends to be slightly higher than expected when GetPathTo(cp).size() is high.
    int                                        DistanceFrom(const ChokePoint * cp) const;

    // Returns whether this ChokePoint is accessible from cp (through a walkable path).
    // Note: the relation is symmetric: this->AccessibleFrom(cp) == cp->AccessibleFrom(this)
    // Note: if this == cp, returns true.
    // Time complexity: O(1)
    bool                                    AccessibleFrom(const ChokePoint * cp) const    { return DistanceFrom(cp) >= 0; }

    // Returns a list of ChokePoints, which is intended to be the shortest walking path from this ChokePoint to cp.
    // The path always starts with this ChokePoint and ends with cp, unless AccessibleFrom(cp) == false.
    // In this case, an empty list is returned.
    // Note: if this == cp, returns [cp].
    // Time complexity: O(1)
    // To get the length of the path returned in pixels, use DistanceFrom(cp).
    // Note: all the possible Paths are precomputed during Map::Initialize().
    //       The best one is then stored for each pair of ChokePoints.
    //       However, only the center of the ChokePoints is considered.
    //       As a consequence, the returned path may not be the shortest one.
    const ChokePoint::Path &                GetPathTo(const ChokePoint * cp) const;

    // Returns the pixel width of the Chokepoint, start from node n1 and ending at node n2
    int                                      Width() const { return int(this->Pos(this->end1).getDistance(this->Pos(this->end2))) * 8;}

    Map *                                    GetMap() const;

    ChokePoint &                            operator=(const ChokePoint &) = delete;

////////////////////////////////////////////////////////////////////////////
//    Details: The functions below are used by the BWEM's internals

    typedef int                                index;
                                            ChokePoint(detail::Graph * pGraph, index idx, const Area * area1, const Area * area2, const std::deque<BWAPI::WalkPosition> & Geometry, Neutral * pBlockingNeutral = nullptr);
                                            ChokePoint(const ChokePoint & Other);
    void                                    OnBlockingNeutralDestroyed(const Neutral * pBlocking);
    index                                    Index() const            { return m_index; }
    const ChokePoint *                        PathBackTrace() const                            { return m_pPathBackTrace; }
    void                                    SetPathBackTrace(const ChokePoint * p) const    { m_pPathBackTrace = p; }

private:
    const detail::Graph *                    GetGraph() const        { return m_pGraph; }
    detail::Graph *                            GetGraph()                { return m_pGraph; }

    detail::Graph * const                                m_pGraph;
    const bool                                            m_pseudo;
    const index                                            m_index;
    const std::pair<const Area *, const Area *>            m_Areas;
    BWAPI::WalkPosition                                    m_nodes[node_count];
    std::pair<BWAPI::WalkPosition, BWAPI::WalkPosition>    m_nodesInArea[node_count];
    const std::deque<BWAPI::WalkPosition>                m_Geometry;
    bool                                                m_blocked;
    Neutral *                                            m_pBlockingNeutral;
    mutable const ChokePoint *                            m_pPathBackTrace = nullptr;
};


typedef ChokePoint::Path CPPath;



} // namespace BWEM


#endif

