/* streamed segment tree without twowayscan */
static void stream_ext (BOX **Ib, BOX **Ie, BOX **Pb, BOX **Pe,
  double lo, double hi, int d, void *data, BOX_Overlap_Create create)
{
  if (Ib >= Ie || Pb >= Pe) return;
  else if (d == 0 || (Ie-Ib) < CUTOFF || (Pe-Pb) < CUTOFF) onewayscan (Ib, Ie, Pb, Pe, d, data, create);
  else
  {
    BOX **Im, **Pm, *P;
    double mi;

    Im = lo_hi_inside (Ib, Ie, lo, hi, d); /* [Ib, Im) collects intervals containig [lo, hi)
                                              [Im, Ie) enumerates the remaining intervals */

    /* recurse along lower dimensions */
    stream_ext (Ib, Im, Pb, Pe, -DBL_MAX, DBL_MAX, d-1, data, create);
    stream_ext (Pb, Pe, Ib, Im, -DBL_MAX, DBL_MAX, d-1, data, create);

    /* continue down the tree
     * along 'd'th dimension */

    P = median (Pb, Pe, d, height (Pe-Pb)); /* approximate median of points */
    mi = P->extents [d];
    
    Pm = split (Pb, Pe, mi, d); /* [Pb, Pm) are in [lo, mi); [Pm, Pe) are in [mi, hi) */

    Im = overlaps (Ib, Ie, lo, mi, d); /* intervals [Ib, Im) overlap [lo, mi) */
    if (Im != Ie || Pm != Pe) stream_ext (Ib, Im, Pb, Pm, lo, mi, d, data, create);
    else stream_ext (Ib, Im, Pb, Pm, -DBL_MAX, DBL_MAX, d-1, data, create);

    Im = overlaps (Ib, Ie, mi, hi, d); /* intervals [Ib, Im) overlap [mi, hi) */
    if (Im != Ie || Pm != Pb) stream_ext (Ib, Im, Pm, Pe, mi, hi, d, data, create);
    else stream_ext (Ib, Im, Pm, Pe, -DBL_MAX, DBL_MAX, d-1, data, create);
  }
}

bool overlaps(Rect r, Circle c)
{
	return (overlaps(c.center(), r))
		|| (overlaps(r.topSide(), c))
		|| (overlaps(r.bottomSide(), c))
		|| (overlaps(r.leftSide(), c))
		|| (overlaps(r.rightSide(), c));
}

bool Collisionhandler::testOBBOverlap(Entity &a, Entity &b) {
  if (b.getType() == Entity::NOTCOLLIDABLE) {
    return false;
  }

  OBB aOBB = createOBB(a);
  OBB bOBB = createOBB(b);

  bool didCollide = overlaps(aOBB, bOBB) && overlaps(bOBB, aOBB);
  if (didCollide) {
    a.handleCollision(b);
    b.handleCollision(a);
  }
  return didCollide;
}

bool collides(Entity* const entityOne, Entity* const entityTwo)
{//Function which  uses the separating axis theorem to detect for collisions between two entities
	//Projection getProjection(const sf::Vector2f&, const Square&);
	std::vector<sf::Vector2f> axes1(entityOne->getVertexCount());
	std::vector<sf::Vector2f> axes2(entityTwo->getVertexCount());

	for (int i(0); i < entityOne->getVertexCount(); ++i)
	{//Loop through the first shape and get all normals to each side
		int index(0);
		(i + 1) == entityOne->getVertexCount() ? index = 0 : index = i + 1;

		axes1[i] = entityOne->getNormal(i, index);
	}

	for (int i(0); i < entityTwo->getVertexCount(); ++i)
	{//Loop through the second shape and get all normals to each side
		int index(0);
		(i + 1) == entityTwo->getVertexCount() ? index = 0 : index = i + 1;

		axes2[i] = entityTwo->getNormal(i, index);
	}

	for (int i(0); i < axes1.size(); ++i)
	{//Project shape2 onto shape1's axis and determine if there's a gap
		sf::Vector2f normal(axes1[i]);

		SATProjection proj1(getProjection(normal, entityOne)); //max and minimum values of the first shape projection
		SATProjection proj2(getProjection(normal, entityTwo)); //max and minimum values of the second shape projection


		if (!overlaps(proj1, proj2))
			return false;
	}

	for (int i(0); i < axes2.size(); ++i)
	{
		sf::Vector2f normal(axes2[i]);

		SATProjection proj1(getProjection(normal, entityOne)); //max and minimum values of the first shape projection
		SATProjection proj2(getProjection(normal, entityTwo)); //max and minimum values of the second shape projection


		if (!overlaps(proj1, proj2))
			return false;
	}

	return(true);
}

/** Perform sparc64-specific tasks when an address space is removed from the
 * processor.
 *
 * Demap TSBs.
 *
 * @param as Address space.
 */
void as_deinstall_arch(as_t *as)
{
	/*
	 * Note that we don't and may not lock the address space. That's ok
	 * since we only read members that are currently read-only.
	 *
	 * Moreover, the as->asid is protected by asidlock, which is being held.
	 *
	 */
	
#ifdef CONFIG_TSB
	uintptr_t base = ALIGN_DOWN(config.base, 1 << KERNEL_PAGE_WIDTH);
	
	ASSERT(as->arch.itsb && as->arch.dtsb);
	
	uintptr_t tsb = (uintptr_t) as->arch.itsb;
	
	if (!overlaps(tsb, 8 * MMU_PAGE_SIZE, base, 1 << KERNEL_PAGE_WIDTH)) {
		/*
		 * TSBs were allocated from memory not covered
		 * by the locked 4M kernel DTLB entry. We need
		 * to demap the entry installed by as_install_arch().
		 */
		dtlb_demap(TLB_DEMAP_PAGE, TLB_DEMAP_NUCLEUS, tsb);
	}
#endif
}

/**
 * @brief Makes the door immediately open or closed.
 * @param door_open true to make it opened, false to make it closed.
 */
void Door::set_open(bool door_open) {

  state = door_open ? OPEN : CLOSED;

  if (door_open) {
    set_collision_modes(COLLISION_NONE); // to avoid being the hero's facing entity
  }
  else {
    get_sprite().set_current_animation("closed");
    set_collision_modes(COLLISION_FACING_POINT | COLLISION_SPRITE);

    // ensure that we are not closing the door on the hero
    if (is_on_map() && overlaps(get_hero())) {
      get_hero().avoid_collision(*this, (get_direction() + 2) % 4);
    }
  }

  if (is_on_map()) {
    update_dynamic_tiles();

    if (is_saved()) {
      get_savegame().set_boolean(savegame_variable, door_open);
    }

    if (door_open) {
      get_lua_context().door_on_opened(*this);
    }
    else {
      get_lua_context().door_on_closed(*this);
    }
  }
}

/**
 * \copydoc Detector::test_collision_custom
 */
bool Separator::test_collision_custom(Entity& entity) {

  // Trigger the collision if the center point crosses the middle of the
  // separator.

  const Point& separator_center = get_center_point();
  const Point& center = entity.get_center_point();

  if (!overlaps(center)) {
    return false;
  }

  if (is_horizontal()) {
    if (center.y < separator_center.y) {
      // The entity is above the separator.
      return center.y == separator_center.y - 1;
    }
    else {
      // The entity is below the separator.
      return center.y == separator_center.y;
    }
  }
  else {
    if (center.x < separator_center.x) {
      // The entity is west of the separator.
      return center.x == separator_center.x - 1;
    }
    else {
      // The entity is east of the separator.
      return center.x == separator_center.x;
    }
  }
}

static
bool couldEndLiteral(const ue2_literal &s, NFAVertex initial,
                     const NGHolder &h) {
    ue2::flat_set<NFAVertex> curr, next;
    curr.insert(initial);

    for (auto it = s.rbegin(), ite = s.rend(); it != ite; ++it) {
        const CharReach &cr_s = *it;
        bool matched = false;
        next.clear();

        for (auto v : curr) {
            if (v == h.start) {
                // We can't see what we had before the start, so we must assume
                // the literal could overlap with it.
                return true;
            }
            const CharReach &cr_v = h[v].char_reach;
            if (overlaps(cr_v, cr_s)) {
                insert(&next, inv_adjacent_vertices(v, h));
                matched = true;
            }
        }

        if (!matched) {
            return false;
        }

        curr.swap(next);
    }

    return true;
}

//add an Event to the schedule (and sort the schedule from earliest to latest)
bool addEvent(hackathon_scheduler::AddEvent::Request  &req,
         	 hackathon_scheduler::AddEvent::Response &res)
{
  hackathon_scheduler::Event e = req.event;
  ROS_INFO("Attempting to add event %s of type %s with parameters %s to schedule at time %s",e.taskName.c_str(),e.taskType.c_str(),e.parameters.c_str(),e.startTime.c_str());

  //determine if given event overlaps another event in the schedule
  for (std::vector<hackathon_scheduler::Event>::iterator it = schedule.begin();
       it != schedule.end(); ++it)
  {
    if (overlaps(e,*it)) {
      res.success=false;
      ROS_INFO("Events %s at %s of type %s and %s at %s of type %s overlap! Not adding event %s", 
          e.taskName.c_str(), e.startTime.c_str(), e.taskType.c_str(),
          (*it).taskName.c_str(), (*it).startTime.c_str(), (*it).taskType.c_str(),
          e.taskName.c_str());
      return true;
    }
  }

  //if no conflicts, add the event to the schedule
  schedule.push_back(e);
  ROS_INFO("Added event %s of type %s with parameters %s to schedule at time %s",e.taskName.c_str(),e.taskType.c_str(),e.parameters.c_str(),e.startTime.c_str());
  //sort the schedule from earliest to latest
  sort(schedule.begin(), schedule.end(), event_earlier_than_key());
  printSchedule();
  res.success=true;
  return true;
}

/**
 * \brief This function is called when an enemy's sprite collides with a sprite of this entity.
 * \param enemy the enemy
 * \param enemy_sprite the enemy's sprite that overlaps the hero
 * \param this_sprite the arrow sprite
 */
void Hookshot::notify_collision_with_enemy(
    Enemy& enemy, Sprite& enemy_sprite, Sprite& /* this_sprite */) {

  if (!overlaps(get_hero())) {
    enemy.try_hurt(EnemyAttack::HOOKSHOT, *this, &enemy_sprite);
  }
}

bool LiveRange::overlapsInst(InstNumberT OtherBegin, bool UseTrimmed) const {
  bool Result = false;
  for (auto I = (UseTrimmed ? TrimmedBegin : Range.begin()), E = Range.end();
       I != E; ++I) {
    if (OtherBegin < I->first) {
      Result = false;
      break;
    }
    if (OtherBegin < I->second) {
      Result = true;
      break;
    }
  }
  // This is an equivalent but less inefficient implementation. It's expensive
  // enough that we wouldn't want to run it under any build, but it could be
  // enabled if e.g. the LiveRange implementation changes and extra testing is
  // needed.
  if (BuildDefs::extraValidation()) {
    LiveRange Temp;
    Temp.addSegment(OtherBegin, OtherBegin + 1);
    bool Validation = overlaps(Temp);
    (void)Validation;
    assert(Result == Validation);
  }
  return Result;
}

/**
 * @brief Notifies this entity that it was just enabled or disabled.
 * @param enabled \c true if the entity is now enabled.
 */
void Chest::notify_enabled(bool enabled) {

  // Make sure the chest does not appear on the hero.
  if (enabled && overlaps(get_hero())) {
    get_hero().avoid_collision(*this, 3);
  }
}

 std::vector<ValueT>
 overlaps(const Dimension<T>& dim,
          const typename Dimension<T>::End end) const
 {
     auto box = makePlaneAcrossDimensionEnd(dim, end);
     return overlaps(box);
 }

/**
 * \brief Returns whether the specified point is in the jumper's shape.
 *
 * This function is used only for a jumper with diagonal direction.
 *
 * \param point the point to check
 * \return true if this point is overlapping the jumper
 */
bool Jumper::is_point_in_diagonal(const Rectangle& point) const {

  if (!overlaps(point.get_x(), point.get_y())) {
    return false;
  }

  bool collision = false;
  int x = point.get_x() - this->get_x();
  int y = point.get_y() - this->get_y();
  int width = get_width();

  switch (get_direction()) {

  case 1:
    collision = (y >= x) && (y - 8 < x);
    break;

  case 3:
    collision = (x + y <= width) && (x + y > width - 8);
    break;

  case 5:
    collision = (x >= y) && (x - 8 < y);
    break;

  case 7:
    collision = (x + y >= width) && (x + y < width + 8);
    break;

  default:
    Debug::die("Invalid direction of jumper");
  }

  return collision;
}

void BossEntity::update()
{
    if(active)
    {
        if(health <= 0)
            state = STATE_DYING;

        switch(state)
        {
            case STATE_MOVING:
                updateMoving();
                break;

            case STATE_ATTACKING:
                updateAttacking();
                break;

            case STATE_PANIC:
                updatePanic();
                break;
            case STATE_DYING:
                updateDying();
                break;
        }
    }
    else
    {
        if(overlaps(*camera))
            active = true;
    }
}

/**
 * \brief Updates this entity.
 */
void Destructible::update() {

  MapEntity::update();

  if (is_suspended()) {
    return;
  }

  if (is_being_cut && get_sprite().is_animation_finished()) {

    if (!get_can_regenerate()) {
      // Remove this destructible from the map.
      remove_from_map();
    }
    else {
      is_being_cut = false;
      regeneration_date = System::now() + 10000;
    }
  }

  else if (is_waiting_for_regeneration()
      && System::now() >= regeneration_date
      && !overlaps(get_hero())) {
    get_sprite().set_current_animation("regenerating");
    is_regenerating = true;
    regeneration_date = 0;
    get_lua_context().destructible_on_regenerating(*this);
  }
  else if (is_regenerating && get_sprite().is_animation_finished()) {
    get_sprite().set_current_animation("on_ground");
    is_regenerating = false;
  }
}

/**
 * \brief This function is called when an enemy's sprite collides with a sprite of this entity.
 * \param enemy the enemy
 * \param enemy_sprite the enemy's sprite that overlaps the hero
 * \param this_sprite the arrow sprite
 */
void Arrow::notify_collision_with_enemy(
    Enemy& enemy, Sprite& enemy_sprite, Sprite& this_sprite) {

  if (!overlaps(hero) && is_flying()) {
    enemy.try_hurt(ATTACK_ARROW, *this, &enemy_sprite);
  }
}

/**
 * @brief Updates the item.
 */
void Destructible::update() {

  MapEntity::update();

  if (suspended) {
    return;
  }

  if (is_being_cut && get_sprite().is_animation_finished()) {

    if (!features[subtype].can_regenerate) {
      // remove the item from the map
      destruction_callback();
      remove_from_map();
    }
    else {
      is_being_cut = false;
      regeneration_date = System::now() + 10000;
    }
  }

  else if (is_disabled() && System::now() >= regeneration_date && !overlaps(get_hero())) {
    get_sprite().set_current_animation("regenerating");
    is_regenerating = true;
    regeneration_date = 0;
  }
  else if (is_regenerating && get_sprite().is_animation_finished()) {
    get_sprite().set_current_animation("on_ground");
    is_regenerating = false;
  }
}

void ParallelBlockCommunicator2D::duplicateOverlaps(MultiBlock2D& multiBlock, modif::ModifT whichData) const
{
    MultiBlockManagement2D const& multiBlockManagement = multiBlock.getMultiBlockManagement();
    PeriodicitySwitch2D const& periodicity             = multiBlock.periodicity();

    // Implement a caching mechanism for the communication structure.
    if (overlapsModified) {
        overlapsModified = false;
        LocalMultiBlockInfo2D const& localInfo = multiBlockManagement.getLocalInfo();
        std::vector<Overlap2D> overlaps(multiBlockManagement.getLocalInfo().getNormalOverlaps());
        for (pluint iOverlap=0; iOverlap<localInfo.getPeriodicOverlaps().size(); ++iOverlap) {
            PeriodicOverlap2D const& pOverlap = localInfo.getPeriodicOverlaps()[iOverlap];
            if (periodicity.get(pOverlap.normalX,pOverlap.normalY)) {
                overlaps.push_back(pOverlap.overlap);
            }
        }
        delete communication;
        communication = new CommunicationStructure2D (
                                overlaps,
                                multiBlockManagement, multiBlockManagement,
                                multiBlock.sizeOfCell() );
    }

    communicate(*communication, multiBlock, multiBlock, whichData);
}

bool MC2BoundingBox::getInterSection( const MC2BoundingBox& bbox, MC2BoundingBox& interSection ) const
{
   if( overlaps( bbox ) ){
      // The bboxes contains an intersection.
      if( minLat < bbox.minLat )
         interSection.setMinLat( bbox.minLat );
      else
         interSection.setMinLat( minLat );

      if( maxLat > bbox.maxLat )
         interSection.setMaxLat( bbox.maxLat );
      else
         interSection.setMaxLat( maxLat );

      if( minLon-bbox.minLon < 0 )
         interSection.setMinLon( bbox.minLon );
      else
         interSection.setMinLon( minLon );

      if( maxLon - bbox.maxLon > 0 )
         interSection.setMaxLon( bbox.maxLon );
      else
         interSection.setMaxLon( maxLon );

      return true;
   }
   else
      return false;
}