/*!
  \file
  \brief 点の登録と取得を行うデータ構造

  \author Satofumi KAMIMURA

  $Id: PointMap.cpp 1423 2009-10-19 01:56:06Z satofumi $
*/

#include "PointMap.h"
#include <algorithm>
#include <map>


using namespace qrk;
using namespace std;

namespace
{
  enum {
    DefaultGridWidth = 100,
  };

  typedef vector<size_t> Ids;
  typedef map<size_t, Point<long> > Points;
  typedef map<long, map<long, Ids> > PointsGrid;
  typedef map<size_t, size_t> MargeTimes;
}


struct PointMap::pImpl
{
  long grid_width_;
  PointsGrid grid_map_;
  Points points_;
  MargeTimes marge_times_;


  pImpl(size_t grid_width) : grid_width_(grid_width)
  {
    if (grid_width_ <= 0) {
      grid_width_ = 1;
    }
  }


  Ids& pointsIds(const Point<long>& point)
  {
    Point<long> grid(point.x / grid_width_, point.y / grid_width_);
    return grid_map_[grid.y][grid.x];
  }


  void add(const Point<long>& point, size_t id)
  {
    points_[id] = point;
    marge_times_[id] = 1;

    pointsIds(point).push_back(id);
  }


  void marge(size_t id, const Point<long>& point)
  {
    // !!! 浮動小数点以下を切り捨てる現在の実装が、良いか悪いかを評価する

    MargeTimes::iterator it = marge_times_.find(id);
    if (it == marge_times_.end()) {
      add(point, id);
      return;
    }

    int n = it->second;
    if (n > 40) {
      // 一定数以上の点データは加算しない
      return;
    }

    Point<long> original = points_[id];
    Point<long> total(original.x * n, original.y * n);
    total += point;
    ++n;

    it->second = n;
    Point<long> marged = Point<long>(total.x / n, total.y / n);
    points_[id] = marged;

    // marge すると位置が変わるので、位置を更新する
    Ids& points = pointsIds(original);
    points.erase(std::remove(points.begin(), points.end(), id), points.end());
    pointsIds(marged).push_back(id);
  }


  void nearPoints(vector<size_t>& ids,
                  const Point<long>& point, long radius)
  {
    long width = max(static_cast<long>(radius / grid_width_),
                     static_cast<long>(1));
    Point<long> grid(point.x / grid_width_, point.y / grid_width_);
    for (long y = grid.y - width; y <= grid.y + width; ++y) {
      for (long x = grid.x - width; x <= grid.x + width; ++x) {

        PointsGrid::const_iterator y_it = grid_map_.find(y);
        if (y_it == grid_map_.end()) {
          continue;
        }

        // !!! y_it を使うようにする
        map<long, Ids>::const_iterator x_it = grid_map_[y].find(x);
        if (x_it == grid_map_[y].end()) {
          continue;
        }

        const Ids& grid_points = grid_map_[y][x];
        ids.insert(ids.end(), grid_points.begin(), grid_points.end());
      }
    }
  }
};


PointMap::PointMap(void) : pimpl(new pImpl(DefaultGridWidth))
{
}


PointMap::PointMap(size_t grid_width) : pimpl(new pImpl(grid_width))
{
}


PointMap::~PointMap(void)
{
}


void PointMap::clear(void)
{
  pimpl->grid_map_.clear();
  pimpl->points_.clear();
}


void PointMap::add(const Point<long>& point, size_t id)
{
  pimpl->add(point, id);
}


bool PointMap::exists(size_t id) const
{
  return (pimpl->points_.find(id) == pimpl->points_.end()) ? false : true;
}


void PointMap::marge(size_t id, const Point<long>& point)
{
  if (id == 0) {
    return;
  }
  pimpl->marge(id, point);
}


void PointMap::ids(std::vector<size_t>& ids) const
{
  for (MargeTimes::const_iterator it = pimpl->marge_times_.begin();
       it != pimpl->marge_times_.end(); ++it) {
    ids.push_back(it->first);
  }
}


Point<long> PointMap::point(size_t id) const
{
  if (id == 0) {
    return Point<long>(0, 0);
  }

  Points::const_iterator it = pimpl->points_.find(id);
  if (it != pimpl->points_.end()) {
    return it->second;
  } else {
    return Point<long>(0, 0);
  }
}


void PointMap::nearPoints(std::vector<size_t>& ids,
                          const Point<long>& point, long radius)
{
  pimpl->nearPoints(ids, point, radius);
}
