/**
 *  Copyright (c) 2008 Dustin Spicuzza <dustin@virtualroadside.com>
 *
 *  This program is free software; you can redistribute it and/or
 *  modify it under the terms of version 2 of the GNU General Public License
 *  as published by the Free Software Foundation.
 *
 *  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, write to the Free Software
 *  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 */


#ifndef TOMOPROCESS_RSTARTREE_RStarBoundingBox_H
#define TOMOPROCESS_RSTARTREE_RStarBoundingBox_H

#include <limits>
#include <utility>
#include <cstddef>
#include <string>
#include <sstream>

namespace rstartree {

template<std::size_t dimensions>
struct RStarBoundingBox
{
  // edges[x].first is low value, edges[x].second is high value.
  std::pair<double, double> edges[dimensions];

  // Forces all edges to their extremes so we can stretch() it.
  void reset()
  {
    for(std::size_t axis = 0; axis < dimensions; axis++) {
      edges[axis].first  = std::numeric_limits<double>::max();
      edges[axis].second = std::numeric_limits<double>::min();
    }
  }

  // Returns a new bounding box that has the maximum boundaries.
  static RStarBoundingBox MaximumBounds()
  {
    RStarBoundingBox<dimensions> bound;
    bound.reset();
    return bound;
  }

  // Fits another box inside of this box, returns true if a stretch occured.
  bool stretch(const RStarBoundingBox<dimensions> &bb)
  {
    bool ret(false);
    for(std::size_t axis = 0; axis < dimensions; axis++) {

      if(edges[axis].first > bb.edges[axis].first) {
        edges[axis].first = bb.edges[axis].first;
        ret = true;
      }

      if(edges[axis].second < bb.edges[axis].second) {
        edges[axis].second = bb.edges[axis].second;
        ret = true;
      }
    }

    return ret;
  }

  // The sum of all deltas between edges.
  inline double edgeDeltas() const
  {
    double distance(0.0);
    for(std::size_t axis = 0; axis < dimensions; axis++)
      distance += edges[axis].second - edges[axis].first;

    return distance;
  }

  // Calculates the area of a bounding box.
  inline double area() const
  {
    double _area(1.0);
    for(std::size_t axis = 0; axis < dimensions; axis++)
      _area *= (edges[axis].second - edges[axis].first);

    return _area;
  }

  // This determines if a bounding box is fully contained within this bounding box.
  inline bool encloses(const RStarBoundingBox<dimensions> &bb) const
  {
    // if (y1 < x1 || x2 < y2)
    for(std::size_t axis = 0; axis < dimensions; axis++)
      if(bb.edges[axis].first < edges[axis].first || edges[axis].second < bb.edges[axis].second)
        return false;

    return true;
  }

  // A quicker way to determine if two bounding boxes overlap.
  inline bool overlaps(const RStarBoundingBox<dimensions> &bb) const
  {
    // Do it this way so there is no equal signs (in case of doubles)
    // if(!(x1 < y2) && !(x2 > y1))
    for(std::size_t axis = 0; axis < dimensions; axis++) {
      if(!(edges[axis].first < bb.edges[axis].second) ||
         !(bb.edges[axis].first < edges[axis].second))
        return false;
    }

    return true;
  }

  // Calculates the total overlapping area of two boxes.
  double overlap(const RStarBoundingBox<dimensions> &bb) const
  {
    double _area(1.0);
    for(std::size_t axis = 0; _area && axis < dimensions; axis++) {
      // This makes it easier to understand.
      const double &x1 = edges[axis].first;
      const double &x2 = edges[axis].second;
      const double &y1 = bb.edges[axis].first;
      const double &y2 = bb.edges[axis].second;

      // Left edge outside left edge.
      if(x1 < y1) {
        // And right edge inside left edge.
        if(y1 < x2) {
          // Right edge outside right edge.
          if(y2 < x2)
            _area *= (y2 - y1);
          else
            _area *= (x2 - y1);
        
        continue;
        }
      }
      // Right edge inside left edge.
      else if(x1 < y2) {
        // Right edge outside right edge.
        if(x2 < y2)
          _area *= (x2 - x1);
        else
          _area *= (y2 - x1);

        continue;
      }

      // If we get here, there is no overlap.
      return 0.0;
    }

    return _area;
  }

  // Sums the total distances from the center of another bounding box.
  double distanceFromCenter(const RStarBoundingBox<dimensions> &bb) const
  {
    double t, distance(0.0);
    for(std::size_t axis = 0; axis < dimensions; axis++) {
      t = (edges[axis].first + edges[axis].second + 
           bb.edges[axis].first + bb.edges[axis].second) / 2.0;
      distance += t*t;
    }

    return distance;
  }

  // Determines if two bounding box are identical.
  bool operator==(const RStarBoundingBox<dimensions> &bb)
  {
    for(std::size_t axis = 0; axis < dimensions; axis++) {
      if(edges[axis].first != bb.edges[axis].first ||
         edges[axis].second != bb.edges[axis].second)
        return false;
    }

    return true;
  }

  // Very slow, use for debugging only.
  std::string ToString() const
  {
    std::stringstream name("");
    name << "[";
    for(std::size_t axis = 0; axis < dimensions; axis++) {
      name << "(" << edges[axis].first << "," << edges[axis].second << ")";
      if(axis != dimensions - 1) name << ",";
    }
    name << "]";

    return name.str();
  }
};

template<std::size_t dimensions>
struct RStarBoundedItem
{
  typedef RStarBoundingBox<dimensions> BoundingBox;
  BoundingBox bound;
};

/**********************************************************
 * Functor used to iterate over a set and stretch a
 * bounding box
 **********************************************************/

// for_each(items.begin(), items.end(), StretchBoundedItem::BoundingBox(bound));
template<typename BoundedItem>
struct StretchBoundingBox:
  public std::unary_function< const BoundedItem * const, void >
{
  typename BoundedItem::BoundingBox* m_bound;
  explicit StretchBoundingBox(typename BoundedItem::BoundingBox* bound):
    m_bound(bound) {}

  void operator()(const BoundedItem * const item)
  { m_bound->stretch(item->bound); }
};

/**********************************************************
 * R* Tree related functors used for sorting BoundedItems
 *
 * TODO: Take advantage of type traits
 **********************************************************/

template<typename BoundedItem>
struct SortBoundedItemsByFirstEdge:
  public std::binary_function< const BoundedItem * const, const BoundedItem * const, bool >
{
  const std::size_t m_axis;
  explicit SortBoundedItemsByFirstEdge(const std::size_t axis): m_axis(axis) {}

  bool operator()(const BoundedItem * const bi1, const BoundedItem * const bi2) const
  { return (bi1->bound.edges[m_axis].first < bi2->bound.edges[m_axis].first); }
};

template<typename BoundedItem>
struct SortBoundedItemsBySecondEdge:
  public std::binary_function< const BoundedItem * const, const BoundedItem * const, bool >
{
  const std::size_t m_axis;
  explicit SortBoundedItemsBySecondEdge(const std::size_t axis): m_axis(axis) {}

  bool operator()(const BoundedItem * const bi1, const BoundedItem * const bi2) const
  { return (bi1->bound.edges[m_axis].second < bi2->bound.edges[m_axis].second); }
};

template<typename BoundedItem>
struct SortBoundedItemsByDistanceFromCenter:
  public std::binary_function< const BoundedItem * const, const BoundedItem * const, bool >
{
  const typename BoundedItem::BoundingBox * const m_center;
  explicit SortBoundedItemsByDistanceFromCenter(const typename BoundedItem::BoundingBox * const center):
    m_center(center) {}

  bool operator()(const BoundedItem * const bi1, const BoundedItem * const bi2) const
  { return (bi1->bound.distanceFromCenter(*m_center) < bi2->bound.distanceFromCenter(*m_center)); }
};

template<typename BoundedItem>
struct SortBoundedItemsByAreaEnlargement:
  public std::binary_function< const BoundedItem * const, const BoundedItem * const, bool >
{
  const double area;
  explicit SortBoundedItemsByAreaEnlargement(const typename BoundedItem::BoundingBox *center):
    area(center->area()) {}

  bool operator()(const BoundedItem * const bi1, const BoundedItem * const bi2) const
  { return (area - bi1->bound.area() < area - bi2->bound.area()); }
};

template<typename BoundedItem>
struct SortBoundedItemsByOverlapEnlargement:
  public std::binary_function< const BoundedItem * const, const BoundedItem * const, bool >
{
  const typename BoundedItem::BoundingBox * const m_center;
  explicit SortBoundedItemsByOverlapEnlargement(const typename BoundedItem::BoundingBox * const center):
    m_center(center) {}

  bool operator()(const BoundedItem * const bi1, const BoundedItem * const bi2) const
  { return (bi1->bound.overlap(*m_center) < bi2->bound.overlap(*m_center)); }
};

} // namespace rstartree

#endif // TOMOPROCESS_RSTARTREE_RStarBoundingBox_H