#pragma once
#include "../../Utils/CriticalSection.h"
#include "../../BWAPI_Addon.h"
#include <functional>
#include <set>
#include <BWAPI.h>
#include <utility>
#include <queue>
#include <bitset>
#include <vector>
#include <memory>
#include <boost/unordered_set.hpp>
#include <boost/dynamic_bitset.hpp>
#include <boost/numeric/conversion/bounds.hpp>
#include <boost/thread/recursive_mutex.hpp>

template<class T>
class InfluenceMapRef;

/**
 * @brief Class that contains influence information (air, ground, etc.) about
 * a player on the map.
 */
template<class InfluenceType>
class InfluenceMap : public Component
{
  friend class InfluenceMapRef<InfluenceType>;
public:
  /**
   * @brief Creates an influence map of the given size for the given player.
   * @param width The width of the influence map.
   * @param height The height of the influence map.
   * @param player The player whose influence will be held in this influence map.
   */
  InfluenceMap(size_t width, size_t height, BWAPI::Player* player)
    : m_map(width * height)
    , m_width(static_cast<int>(width))
    , m_height(static_cast<int>(height))
    , m_player(player)
  {
    // FIXME
    assert(m_width  == BWAPI::Broodwar->mapWidth() && m_height == BWAPI::Broodwar->mapHeight());
  }

  ~InfluenceMap()
  {
  }

  /**
   * @brief Recomputes the influence that the player has on the map.
   */
  void update()
  {
    InfluenceType::update(*this);
  }

  /**
   * @brief Displays the influence map on the game screen.
   */
  void display() const
  {
    for (int y=0; y<m_height; ++y)
    {
      for (int x=0; x<m_width; ++x)
      {
        const InfluenceType& influence = getData(x, y);
        influence.display(x*TILE_SIZE, y*TILE_SIZE, TILE_SIZE, TILE_SIZE, m_player);
      }
    }
  }

  /**
   * @brief Checks if the position is a valid one on the map.
   * @param x the x coordinate of the position whose validity to check.
   * @param y The y coordinate of the position whose validity to check.
   * @return True if the position is valid, false otherwise.
   */
  bool isValid(int x, int y) const
  {
    return is_between<int,true>(0, m_width  - 1)(x) && is_between<int,true>(0, m_height - 1)(y);
  }

  /**
   * @brief Returns the influence at the given position.
   * @param x The x coordinate of the tile whose influence must be returned.
   * @param y The y coordinate of the tile whose influence must be returned.
   * @return The influence at the given position.
   */
  const InfluenceType& getData(int x, int y) const
  {
    return _getInfluence(x, y);
  }

  /**
   * @brief Returns the influence at the given position.
   * @param position The position where the influence must be returned.
   * @return The influence at the given position.
   */
  const InfluenceType& getData(const BWAPI::Position &position) const
  {
    return _getInfluence(position.x() / TILE_SIZE, position.y() / TILE_SIZE);
  }

  const InfluenceType& getData(const BWAPI::TilePosition &position) const
  {
    return _getInfluence(position.x(), position.y());
  }

  /**
   * @brief Resets the influence map to its initial value.
   */
  void reset()
  {
    for(matrix::iterator it = m_map.begin(); it != m_map.end(); ++it)
      it->reset();
  }

  /**
   * @brief Sets the influence at the given position.
   * @param position The position where to set the influence.
   * @param influence The new influence value to set.
   */
  void setInfluence(BWAPI::Position position, const InfluenceType& influence)
  {

    InfluenceType& inf = _getInfluence(position.x() / TILE_SIZE, position.y() / TILE_SIZE);
    inf = influence;
  }

  /**
   * @brief Sets the influence at the given position.
   * @param x The x coordinate of the tile whose influence is to be set.
   * @param y The y coordinate of the tile whose influence is to be set.
   * @param influence The new influence value to set.
   */
  void setInfluence(int x, int y, const InfluenceType& influence)
  {
    InfluenceType& inf = _getInfluence(x, y);
    inf = influence;
  }

  /**
   * @brief Iterates over all tiles of the influence map.
   * @param functor Functor to be called on each tile.
   * @return The functor applied to the tiles.
   */
  template<class Functor>
  Functor for_each(Functor functor) const
  {
    for (int y=0; y<m_height; ++y)
      for (int x=0; x<m_width; ++x)
        functor(x, y, *this);

    return functor;
  }

  //template<class Evaluator>
  //std::pair<int,int> hill_climbing(int x, int y, Evaluator evaluator, int maxSearchDepth = boost::numeric::bounds<int>::highest())
  //{
  //  typedef std::pair<int,int> Pos;
  //  
  //  while (maxSearchDepth-- > 0)
  //  {
  //    std::vector<Pos> succ = InfluenceMaps::detail::getAdjacentTiles(x, y, *this, true);
  //    
  //    Evaluator::return_type minValue = evaluator(x, y, *this);
  //    std::vector<Pos>::const_iterator minPos = succ.end();
  //    
  //    for (std::vector<Pos>::const_iterator i=succ.begin(); i!=succ.end(); ++i)
  //    { 
  //      Evaluator::return_type value = evaluator(i->first, i->second, *this);
  //      if (value < minValue)
  //      {
  //        minValue = value;
  //        minPos = i;
  //      }
  //    }
  //
  //    if (minPos == succ.end())
  //    {
  //      //SPAR_LOG(LogTypes.PERCEPTUAL_STATE, "[HILL CLIMBING] Reached local minimum (%d,%d)", x, y);
  //      return std::make_pair(x, y);
  //    }
  //    else
  //    {
  //      x = minPos->first;
  //      y = minPos->second;
  //    }
  //  }
  //
  //  return std::make_pair(x, y);
  //}

  /**
   * @return The width of the map.
   */
  size_t getWidth()  const { return static_cast<size_t>(m_width);  }

  /**
   * @return The height of the map.
   */
  size_t getHeight() const { return static_cast<size_t>(m_height); }

  /**
   * @return The player whose influence is computed on this map.
   */
  const BWAPI::Player* const getPlayer() const { return m_player; }

protected:
  virtual void _output(std::ostream& out) const
  {
    if (m_player == BWAPI::Broodwar->self())
      out << "Own";
    else if (m_player == BWAPI::Broodwar->enemy())
      out << "Enemy";
    else
      out << "Neutral";
    out << " " << InfluenceType::name() << " influence map";
  }

private:
  template<class U> InfluenceMap(const InfluenceMap<U>&);
  template<class U> InfluenceMap& operator=(const InfluenceMap<U>&);
  InfluenceMap& operator=(const InfluenceMap<InfluenceType>&);
  InfluenceMap(const InfluenceMap &other);

  /**
   * @brief Returns the influence at the given position.
   * @param x the x coordinate of the tile whose influence must be returned.
   * @param y the y coordinate of the tile whose influence must be returned.
   * @return the influence at the given position.
   */
  InfluenceType& _getInfluence(int x, int y)
  {
    assert(isValid(x, y));

    return m_map[x + y*m_width];
  }
  const InfluenceType& _getInfluence(int x, int y) const
  {
    assert(isValid(x, y));

    return m_map[x + y*m_width];
  }

  typedef std::vector<InfluenceType> matrix; // Could use BWAPI::RectangleArray
  matrix m_map;
  const int m_width;
  const int m_height;
  BWAPI::Player* const m_player;
};

template<class T>
class InfluenceMapRef : boost::noncopyable
{
public:
  typedef InfluenceMap<T> map_type;
#ifdef USE_MULTITHREADED_SCHEDULER
  typedef boost::shared_ptr<const map_type> map_ptr;
#else
  typedef const map_type * map_ptr;
#endif
private:
#ifdef USE_MULTITHREADED_SCHEDULER
  boost::shared_ptr<map_type> m_map;
  mutable CriticalSection m_mutex;
#else
  map_type * m_map;
#endif
public:
  InfluenceMapRef(size_t width, size_t height, BWAPI::Player* player) : m_map(new map_type(width, height, player)) {}

  void update()
  {
#ifdef USE_MULTITHREADED_SCHEDULER
    assert(BWAPI::isOnMainThread());
    
    if(!m_map.unique())
    {
      map_type & m = *m_map;
      std::auto_ptr<map_type> clone(new map_type(m.m_width, m.m_height, m.m_player));
      clone->update();
      CriticalSection::scoped_lock lock(m_mutex);
      m_map.reset(clone.release());
    }
    else
    {
      CriticalSection::scoped_lock lock(m_mutex);
      m_map->update();
    }
#else
    m_map->update();
#endif
  }

  void display()
  {
    const map_ptr p = get();
    p->display();
  }

  map_ptr get() const
  {
#ifdef USE_MULTITHREADED_SCHEDULER
    if(BWAPI::isOnMainThread()) // no need to lock if on main thread, since no update can occur
      return m_map;

    CriticalSection::scoped_lock lock(m_mutex);
#endif
    return m_map;
  }
};

template<class T>
std::ostream & operator<<(std::ostream &os, const InfluenceMapRef<T> &map)
{
  const typename InfluenceMapRef<T>::map_ptr p = map.get();
  os << *p;
  return os;
}

namespace InfluenceMaps
{
  /**********************************************************************************************/
  /*                                            ALL                                             */
  /**********************************************************************************************/
  namespace detail
  {
    typedef boost::tuples::null_type Nothing;

    /**
     * @brief Adapter functor that redirects a call to a functor with the correct number of actual influence maps.
     */
    struct FunctorAdapter
    {
      template<class Functor, class T0>
      typename Functor::return_type operator()(Functor functor, int x, int y, const boost::tuple<const InfluenceMap<T0>&>& maps) const
      {
        return functor(x, y, maps.get<0>());
      }

      template<class Functor, class T0, class T1>
      typename Functor::return_type operator()(Functor functor, int x, int y, const boost::tuple<const InfluenceMap<T0>&, const InfluenceMap<T1>&>& maps) const
      {
        return functor(x, y, maps.get<0>(), maps.get<1>());
      }

      template<class Functor, class T0, class T1, class T2>
      typename Functor::return_type operator()(Functor functor, int x, int y, const boost::tuple<const InfluenceMap<T0>&, const InfluenceMap<T1>&, const InfluenceMap<T2>&>& maps) const
      {
        return functor(x, y, maps.get<0>(), maps.get<1>(), maps.get<2>());
      }
    };
  };

  /**********************************************************************************************/
  /*                                    BREADTH FIRST SEARCH                                    */
  /**********************************************************************************************/
  namespace detail
  {
    /**
     * @brief Returns a set containing the valid tiles adjacent to the given position.
     * Do not use directly.
     * @param x The x coordinate of the tile whose adjacent tiles to return.
     * @param y The y coordinate of the tile whose adjacent tiles to return.
     * @param adj The set in which to add the adjacent tiles.
     * @param map The influence map to use.
     * @param shuffle Whether the adjacent tiles returned should be randomly shuffled.
     */
    template<class InfluenceType>
    std::vector<std::pair<int,int>> getAdjacentTiles(int x, int y, const InfluenceMap<InfluenceType> &map, bool shuffle = false)
    {
      using ::std::make_pair;

      std::vector<std::pair<int,int>> adj;
      adj.reserve(4);

      static const int vx[] = {0, 0, -1, 1};
      static const int vy[] = {-1, 1, 0, 0};

      for (int i=0; i<4; ++i)
      {
        if (map.isValid(x+vx[i], y+vy[i])) adj.push_back(make_pair(x+vx[i], y+vy[i]));
      }

      if (shuffle) std::random_shuffle(adj.begin(), adj.end());

      return adj;
    }

    /**
     * Open list wrappers
     */
    struct VectorOpenList
    {
      VectorOpenList(size_t w, size_t h)
        : m_w(w), m_vector(w*h, false) {}

      bool contains(int x, int y) const
      {
        return m_vector[x + y*m_w];
      }

      void insert(int x, int y)
      {
        m_vector[x + y*m_w] = true;
      }

    private:
      size_t m_w;
      std::vector<bool> m_vector;
    };

    template<size_t N>
    struct BitSetOpenList
    {
      BitSetOpenList(size_t w, size_t h)
        : m_w(w)
      {
        unused(h);
        assert(m_bitset.size() >= w*h);
      }

      bool contains(int x, int y) const
      {
        return m_bitset[x + y*m_w];
      }

      void insert(int x, int y)
      {
        m_bitset.set(x + y*m_w);
      }

    private:
      size_t m_w;
      std::bitset<N> m_bitset;
    };

    struct DynamicBitSetOpenList
    {
      DynamicBitSetOpenList(size_t w, size_t h)
        : m_w(w), m_bitset(w * h) {}

      bool contains(int x, int y) const
      {
        return m_bitset[x + y*m_w];
      }

      void insert(int x, int y)
      {
        m_bitset[x + y*m_w] = true;
      }

    private:
      size_t m_w;
      boost::dynamic_bitset<> m_bitset;
    };

    template<class SetType>
    struct SetOpenList
    {
      SetOpenList(size_t w, size_t h)
        : m_w(w) {}

      bool contains(int x, int y) const
      {
        return m_set.find(x + y*m_w) != m_set.end();
      }

      void insert(int x, int y)
      {
        m_set.insert(x + y*m_w);
      }

    private:
      size_t m_w;
      SetType m_set;
    };
    typedef SetOpenList<std::set<int>> StdSetOpenList;
    typedef SetOpenList<boost::unordered_set<int>> UnorderedSetOpenList;

    // Choose open list implementation type
//  typedef VectorOpenList          OpenListType;
    typedef BitSetOpenList<256*256> OpenListType;
//  typedef DynamicBitSetOpenList   OpenListType;
//  typedef StdSetOpenList          OpenListType;
//  typedef UnorderedSetOpenList    OpenListType;

    /**
     * @brief Functor that performs a breadth-first search on a variable number of influence maps.
     * Do not use this functor directly; use InfluenceMaps::breadth_first_search(...) instead.
     */
    template<class GoalTest, class T0, class T1=Nothing, class T2=Nothing, class T3=Nothing>
    struct breadth_first_search
    {
      std::pair<int,int> operator()(
        int x,
        int y,
        GoalTest test,
        const boost::tuple<
          const InfluenceMap<typename T0>&,
          typename static_if_else<
            boost::is_same<typename T1,Nothing>::value,
            Nothing,
            const InfluenceMap<typename T1>&>::type,
          typename static_if_else<
            boost::is_same<typename T2,Nothing>::value,
            Nothing,
            const InfluenceMap<typename T2>&>::type,
          typename static_if_else<
            boost::is_same<typename T3,Nothing>::value,
            Nothing,
            const InfluenceMap<typename T3>&>::type
        >& maps)
      {
        FunctorAdapter functor;

        using ::std::pair;
        using ::std::make_pair;

        const InfluenceMap<typename T0>& map0 = maps.get<0>();
        const size_t width  = map0.getWidth();
        const size_t height = map0.getHeight();

        ::std::queue<pair<int,int>> Q;
        OpenListType M(width, height);

        pair<int,int> p(x,y);
        Q.push(p);
        M.insert(x, y);
        
        unsigned long visited = 0L;

        while(!Q.empty())
        {
          const pair<int,int> v = Q.front();
          int vx = v.first;
          int vy = v.second;
          Q.pop();

          ++visited;

          if (functor(test, vx, vy, maps))
          {
            x = vx;
            y = vy;
            break;
          }
          else
          {
            std::vector<pair<int,int>> succ = getAdjacentTiles(vx, vy, map0);
            for (std::vector<pair<int,int>>::const_iterator i=succ.begin(); i!=succ.end(); ++i)
            {
              if (!M.contains(i->first, i->second))
              {
                Q.push(*i);
                M.insert(i->first, i->second);
              }
            }
          }
        }

        //SPAR_LOG(LogTypes.PERCEPTUAL_STATE, "[BREADTH FIRST SEARCH] No goal state found! %ul nodes visited, %ul nodes in list", visited, M.size());
        return make_pair(x,y);
      }
    };
  };

  /**
   * @brief Performs a breadth-first search on an influence map.
   * @param x X coordinate of the starting tile.
   * @param y Y coordinate of the starting tile.
   * @param test Goal test functor.
   * @param map The influence map on which to search.
   * @return The first tile that satisfies the goal test.
   */
  template<class GoalTest, class T0>
  std::pair<int,int> breadth_first_search(int x, int y, GoalTest test, const typename InfluenceMapRef<T0>::map_ptr map)
  {
    return InfluenceMaps::detail::breadth_first_search<GoalTest,T0>()(
      x,
      y,
      test,
      boost::tuples::tie(*map));
  }

  /**
   * @brief Performs a breadth-first search on two influence maps simultaneously.
   * @param x X coordinate of the starting tile.
   * @param y Y coordinate of the starting tile.
   * @param test Goal test functor.
   * @param map0 The first influence map on which to search.
   * @param map1 The second influence map on which to search.
   * @return The first tile that satisfies the goal test.
   */
  template<class GoalTest, class T0, class T1>
  std::pair<int,int> breadth_first_search(int x, int y, GoalTest test, const typename InfluenceMapRef<T0>::map_ptr map0, const typename InfluenceMapRef<T1>::map_ptr map1)
  {
    assert(map0.getWidth()  == map1.getWidth() &&
           map0.getHeight() == map1.getHeight());
    return InfluenceMaps::detail::breadth_first_search<GoalTest,T0,T1>()(
      x,
      y,
      test,
      boost::tuples::tie(*map0, *map1));
  }

  /**
   * @brief Performs a breadth-first search on three influence maps simultaneously.
   * @param x X coordinate of the starting tile.
   * @param y Y coordinate of the starting tile.
   * @param test Goal test functor.
   * @param map0 The first influence map on which to search.
   * @param map1 The second influence map on which to search.
   * @param map2 The third influence map on which to search.
   * @return The first tile that satisfies the goal test.
   */
  template<class GoalTest, class T0, class T1, class T2>
  std::pair<int,int> breadth_first_search(int x, int y, GoalTest test, const typename InfluenceMapRef<T0>::map_ptr map0, const typename InfluenceMapRef<T1>::map_ptr map1, const typename InfluenceMapRef<T2>::map_ptr map2)
  {
    assert(map0->getWidth()  == map1->getWidth()  &&
           map1->getWidth()  == map2->getWidth()  &&
           map0->getHeight() == map1->getHeight() &&
           map1->getHeight() == map2->getHeight());
    return InfluenceMaps::detail::breadth_first_search<GoalTest,T0,T1>()(
      x,
      y,
      test,
      boost::tuples::tie(*map0, *map1, *map2));
  }

  /**********************************************************************************************/
  /*                                      GRADIENT DESCENT                                      */
  /**********************************************************************************************/
  namespace detail
  {
    /**
     * @brief Functor that performs a gradient descent on a variable number of influence maps.
     * Do not use this functor directly; use InfluenceMaps::gradient_descent(...) instead.
     */
    template<class Gradient, class StopCriterion, class T0, class T1=Nothing, class T2=Nothing, class T3=Nothing>
    struct gradient_descent
    {
      std::pair<int,int> operator()(
        int x,
        int y,
        Gradient gradient,
        StopCriterion stop,
        const boost::tuple<
          const InfluenceMap<typename T0>&,
          typename static_if_else<
            boost::is_same<typename T1,Nothing>::value,
            Nothing,
            const InfluenceMap<typename T1>&>::type,
          typename static_if_else<
            boost::is_same<typename T2,Nothing>::value,
            Nothing,
            const InfluenceMap<typename T2>&>::type,
          typename static_if_else<
            boost::is_same<typename T3,Nothing>::value,
            Nothing,
            const InfluenceMap<typename T3>&>::type
        >& maps)
      {
        FunctorAdapter functor;

        for(;;)
        {
          std::pair<double,double> grad = functor(gradient, x, y, maps);
          
          if (stop(grad)) break;

          // TODO Replace with a line search algorithm
          double norm = std::sqrt(static_cast<double>(grad.first*grad.first + grad.second*grad.second));
          double initial_step = 1.5 / norm; // Travel about 1.5 tile...
          double diff_step = initial_step / 16.0;
          bool ok = false;
          for (double step = initial_step; step > 0.0; step -= diff_step)
          {
            int nx = x - static_cast<int>(floor(step * grad.first + 0.5));
            int ny = y - static_cast<int>(floor(step * grad.second + 0.5));

            if (maps.get<0>().isValid(nx, ny))
            {
              x = nx;
              y = ny;
              ok = true;
              break;
            }
          }

          if (!ok) break;
        }

        //SPAR_LOG(LogTypes.PERCEPTUAL_STATE, "[GRADIENT DESCENT] Reached local minimum (%d,%d)", x, y);
        return std::make_pair(x, y);
      }
    };
  };

  /**
   * @brief Performs a gradient descent on an influence map.
   * @param x X coordinate of the starting tile.
   * @param y Y coordinate of the starting tile.
   * @param gradient Gradient functor.
   * @param stop Stop criterion functor.
   * @param map0 The influence map on which to perform the gradient descent.
   * @return A tile that satisfies the stop criterion.
   */
  template<class Gradient, class StopCriterion, class T0>
  std::pair<int,int> gradient_descent(int x, int y, Gradient gradient, StopCriterion stop, const typename InfluenceMapRef<T0>::map_ptr map0)
  {
    return InfluenceMaps::detail::gradient_descent<Gradient,StopCriterion,T0>()(x, y, gradient, stop, boost::tuples::tie(*map0));
  }

  /**
   * @brief Performs a gradient descent on three two maps simultaneously.
   * @param x X coordinate of the starting tile.
   * @param y Y coordinate of the starting tile.
   * @param gradient Gradient functor.
   * @param stop Stop criterion functor.
   * @param map0 The first influence map on which to perform the gradient descent.
   * @param map1 The second influence map on which to perform the gradient descent.
   * @return A tile that satisfies the stop criterion.
   */
  template<class Gradient, class StopCriterion, class T0, class T1>
  std::pair<int,int> gradient_descent(int x, int y, Gradient gradient, StopCriterion stop, const typename InfluenceMapRef<T0>::map_ptr map0, const typename InfluenceMapRef<T1>::map_ptr map1)
  {
    assert(map0->getWidth()  == map1->getWidth() &&
           map0->getHeight() == map1->getHeight());
    return InfluenceMaps::detail::gradient_descent<Gradient,StopCriterion,T0,T1>()(x, y, gradient, stop, boost::tuples::tie(*map0, *map1));
  }

  /**
   * @brief Performs a gradient descent on three influence maps simultaneously.
   * @param x X coordinate of the starting tile.
   * @param y Y coordinate of the starting tile.
   * @param gradient Gradient functor.
   * @param stop Stop criterion functor.
   * @param map0 The first influence map on which to perform the gradient descent.
   * @param map1 The second influence map on which to perform the gradient descent.
   * @param map2 The third influence map on which to perform the gradient descent.
   * @return A tile that satisfies the stop criterion.
   */
  template<class Gradient, class StopCriterion, class T0, class T1, class T2>
  std::pair<int,int> gradient_descent(int x, int y, Gradient gradient, StopCriterion stop, const typename InfluenceMapRef<T0>::map_ptr map0, const typename InfluenceMapRef<T1>::map_ptr map1, const typename InfluenceMapRef<T2>::map_ptr map2)
  {
    assert(map0->getWidth()  == map1->getWidth()  &&
           map1->getWidth()  == map2->getWidth()  &&
           map0->getHeight() == map1->getHeight() &&
           map1->getHeight() == map2->getHeight());
    return InfluenceMaps::detail::gradient_descent<Gradient,StopCriterion,T0,T1,T2>()(x, y, gradient, stop, boost::tuples::tie(*map0, *map1, *map2));
  }
};