/*----------------------------------------------------------------------------*
 | This file is part of DEU (Doom Editing Utilities), created by the DEU team:|
 | Raphael Quinet, Brendon Wyber, Ted Vessenes and others.  See README.1ST or |
 | the "about" dialog box for full credits.                                   |
 |                                                                            |
 | DEU is an open project: if you think that you can contribute, please join  |
 | the DEU team.  You will be credited for any code (or ideas) included in    |
 | the next version of the program.                                           |
 |                                                                            |
 | If you want to make any modifications and re-distribute them on your own,  |
 | you must follow the conditions of the DEU license.  Read the file LICENSE  |
 | in this directory or README.1ST in the top directory.  If do not have a    |
 | copy of these files, you can request them from any member of the DEU team, |
 | or by mail: Raphael Quinet, Rue des Martyrs 9, B-4550 Nandrin (Belgium).   |
 |                                                                            |
 | This program comes with absolutely no warranty.  Use it at your own risks! |
 *----------------------------------------------------------------------------*

 W_SELECT.C - Selection of objects

*/

/* the includes */
#include "deu.h"
#include "d_misc.h"
#include "g_gfx.h"
#include "w_levels.h"
#include "w_select.h"


/*
   Check if (a part of) a LineDef is inside a given block.
*/

Bool IsLineDefInside(LevelPtr level, Int16 ldnum, Int16 x0, Int16 y0, Int16 x1, Int16 y1)
{
  Int16 lx0 = level->vertexes[level->linedefs[ldnum].start].x;
  Int16 ly0 = level->vertexes[level->linedefs[ldnum].start].y;
  Int16 lx1 = level->vertexes[level->linedefs[ldnum].end].x;
  Int16 ly1 = level->vertexes[level->linedefs[ldnum].end].y;
  Int16 i;

  /* do you like mathematics? */
  if (lx0 >= x0 && lx0 <= x1 && ly0 >= y0 && ly0 <= y1)
    return TRUE; /* the LineDef start is entirely inside the square */
  if (lx1 >= x0 && lx1 <= x1 && ly1 >= y0 && ly1 <= y1)
    return TRUE; /* the LineDef end is entirely inside the square */
  if ((ly0 > y0) != (ly1 > y0))
    {
      i = lx0 + (Int16) ((Int32) (y0 - ly0) * (Int32) (lx1 - lx0) / (Int32) (ly1 - ly0));
      if (i >= x0 && i <= x1)
        return TRUE; /* the LineDef crosses the y0 side (left) */
    }
  if ((ly0 > y1) != (ly1 > y1))
    {
      i = lx0 + (Int16) ((Int32) (y1 - ly0) * (Int32) (lx1 - lx0) / (Int32) (ly1 - ly0));
      if (i >= x0 && i <= x1)
        return TRUE; /* the LineDef crosses the y1 side (right) */
    }
  if ((lx0 > x0) != (lx1 > x0))
    {
      i = ly0 + (Int16) ((Int32) (x0 - lx0) * (Int32) (ly1 - ly0) / (Int32) (lx1 - lx0));
      if (i >= y0 && i <= y1)
        return TRUE; /* the LineDef crosses the x0 side (down) */
    }
  if ((lx0 > x1) != (lx1 > x1))
    {
      i = ly0 + (Int16) ((Int32) (x1 - lx0) * (Int32) (ly1 - ly0) / (Int32) (lx1 - lx0));
      if (i >= y0 && i <= y1)
        return TRUE; /* the LineDef crosses the x1 side (up) */
    }
  return FALSE;
}



/*
   Get the Sector number of the SideDef opposite to this SideDef.
   (returns -1 if it cannot be found)
*/
/*! use pointers instead of indexes */
Int16 GetOppositeSector(LevelPtr level, Int16 ld1, Bool firstside)
{
  Int16 x0, y0, dx0, dy0;
  Int16 x1, y1, dx1, dy1;
  Int16 x2, y2, dx2, dy2;
  Int16 ld2, dist;
  Int16 bestld, bestdist, bestmdist;

  /* get the coords for this LineDef */
  x0  = level->vertexes[level->linedefs[ld1].start].x;
  y0  = level->vertexes[level->linedefs[ld1].start].y;
  dx0 = level->vertexes[level->linedefs[ld1].end].x - x0;
  dy0 = level->vertexes[level->linedefs[ld1].end].y - y0;

  /* find the normal vector for this LineDef */
  x1  = (dx0 + x0 + x0) / 2;
  y1  = (dy0 + y0 + y0) / 2;
  if (firstside == TRUE)
    {
      dx1 = dy0;
      dy1 = -dx0;
    }
  else
    {
      dx1 = -dy0;
      dy1 = dx0;
    }

  bestld = -1;
  /* use a parallel to an axis instead of the normal vector (faster method) */
  if (abs(dy1) > abs(dx1))
    {
      if (dy1 > 0)
        {
          /* get the nearest LineDef in that direction (increasing Y's: North) */
          bestdist = 32767;
          bestmdist = 32767;
          for (ld2 = 0; ld2 < level->num_linedefs; ld2++)
            if (ld2 != ld1 && ((level->vertexes[level->linedefs[ld2].start].x > x1) != (level->vertexes[level->linedefs[ld2].end].x > x1)))
              {
                x2  = level->vertexes[level->linedefs[ld2].start].x;
                y2  = level->vertexes[level->linedefs[ld2].start].y;
                dx2 = level->vertexes[level->linedefs[ld2].end].x - x2;
                dy2 = level->vertexes[level->linedefs[ld2].end].y - y2;
                dist = y2 + (Int16) ((Int32) (x1 - x2) * (Int32) dy2 / (Int32) dx2);
                if (dist > y1 && (dist < bestdist || (dist == bestdist && (y2 + dy2 / 2) < bestmdist)))
                  {
                    bestld = ld2;
                    bestdist = dist;
                    bestmdist = y2 + dy2 / 2;
                  }
              }
        }
      else
        {
          /* get the nearest LineDef in that direction (decreasing Y's: South) */
          bestdist = -32767;
          bestmdist = -32767;
          for (ld2 = 0; ld2 < level->num_linedefs; ld2++)
            if (ld2 != ld1 && ((level->vertexes[level->linedefs[ld2].start].x > x1) != (level->vertexes[level->linedefs[ld2].end].x > x1)))
              {
                x2  = level->vertexes[level->linedefs[ld2].start].x;
                y2  = level->vertexes[level->linedefs[ld2].start].y;
                dx2 = level->vertexes[level->linedefs[ld2].end].x - x2;
                dy2 = level->vertexes[level->linedefs[ld2].end].y - y2;
                dist = y2 + (Int16) ((Int32) (x1 - x2) * (Int32) dy2 / (Int32) dx2);
                if (dist < y1 && (dist > bestdist || (dist == bestdist && (y2 + dy2 / 2) > bestmdist)))
                  {
                    bestld = ld2;
                    bestdist = dist;
                    bestmdist = y2 + dy2 / 2;
                  }
              }
        }
    }
  else
    {
      if (dx1 > 0)
        {
          /* get the nearest LineDef in that direction (increasing X's: East) */
          bestdist = 32767;
          bestmdist = 32767;
          for (ld2 = 0; ld2 < level->num_linedefs; ld2++)
            if (ld2 != ld1 && ((level->vertexes[level->linedefs[ld2].start].y > y1) != (level->vertexes[level->linedefs[ld2].end].y > y1)))
              {
                x2  = level->vertexes[level->linedefs[ld2].start].x;
                y2  = level->vertexes[level->linedefs[ld2].start].y;
                dx2 = level->vertexes[level->linedefs[ld2].end].x - x2;
                dy2 = level->vertexes[level->linedefs[ld2].end].y - y2;
                dist = x2 + (Int16) ((Int32) (y1 - y2) * (Int32) dx2 / (Int32) dy2);
                if (dist > x1 && (dist < bestdist || (dist == bestdist && (x2 + dx2 / 2) < bestmdist)))
                  {
                    bestld = ld2;
                    bestdist = dist;
                    bestmdist = x2 + dx2 / 2;
                  }
              }
        }
      else
        {
          /* get the nearest LineDef in that direction (decreasing X's: West) */
          bestdist = -32767;
          bestmdist = -32767;
          for (ld2 = 0; ld2 < level->num_linedefs; ld2++)
            if (ld2 != ld1 && ((level->vertexes[level->linedefs[ld2].start].y > y1) != (level->vertexes[level->linedefs[ld2].end].y > y1)))
              {
                x2  = level->vertexes[level->linedefs[ld2].start].x;
                y2  = level->vertexes[level->linedefs[ld2].start].y;
                dx2 = level->vertexes[level->linedefs[ld2].end].x - x2;
                dy2 = level->vertexes[level->linedefs[ld2].end].y - y2;
                dist = x2 + (Int16) ((Int32) (y1 - y2) * (Int32) dx2 / (Int32) dy2);
                if (dist < x1 && (dist > bestdist || (dist == bestdist && (x2 + dx2 / 2) > bestmdist)))
                  {
                    bestld = ld2;
                    bestdist = dist;
                    bestmdist = x2 + dx2 / 2;
                  }
              }
        }
    }
  
   /* no intersection: the LineDef was pointing outwards! */
  if (bestld < 0)
    return -1;
  
  /* now look if this LineDef has a SideDef bound to one sector */
  if (abs(dy1) > abs(dx1))
    {
      if ((level->vertexes[level->linedefs[bestld].start].x < level->vertexes[level->linedefs[bestld].end].x) == (dy1 > 0))
        x0 = level->linedefs[bestld].sidedef1;
      else
        x0 = level->linedefs[bestld].sidedef2;
    }
  else
    {
      if ((level->vertexes[level->linedefs[bestld].start].y < level->vertexes[level->linedefs[bestld].end].y) != (dx1 > 0))
        x0 = level->linedefs[bestld].sidedef1;
      else
        x0 = level->linedefs[bestld].sidedef2;
    }

  /* there is no SideDef on this side of the LineDef! */
  if (x0 < 0)
    return -1;

  /* OK, we got it -- return the Sector number */
  return level->sidedefs[x0].sector;
}



/*
   Get the Sector in which a Thing is, or -1 if it is outside the map.
*/

Int16 GetSectorForThing(LevelPtr level, UInt16 thingnum)
{
  Int16 y, n, x, bestx;
  Int16 lx0, ly0, lx1, ly1;
  LDPtr ldptr, bestldptr;

  y = level->things[thingnum].ypos;
  /* I look for the first LineDef crossing an horizontal half-line drawn */
  /* from the thing */
  bestx = level->map_maxX + 1;
  bestldptr = NULL;
  ldptr = level->linedefs;
  for (n = 0; n < level->num_linedefs; n++)
    {
      ly0 = level->vertexes[ldptr->start].y;
      ly1 = level->vertexes[ldptr->end].y;
      if ((ly0 > y) != (ly1 > y))
        {
          lx0 = level->vertexes[ldptr->start].x;
          lx1 = level->vertexes[ldptr->end].x;
          x = lx0 + (Int16) ((Int32) (y - ly0) * (Int32) (lx1 - lx0)
                             / (Int32) (ly1 - ly0));
          /* compare x with best value so far */
          if (x >= level->things[thingnum].xpos && x < bestx)
            {
              /* prevent errors if y == ly0 or ly1 */
              if (ly1 == y && ly0 <= y)
                x++;
              else if (ly0 == y && ly1 >= y)
                x++;
              /* if x is still better, keep it */
              if (x < bestx)
                {
                  bestx     = x;     /* lower X = closer */
                  bestldptr = ldptr; /* store the LineDef pointer */
                }
            }
        }
      else if ((ly0 == y) && (ly1 == y))
        {
          lx0 = level->vertexes[ldptr->start].x;
          lx1 = level->vertexes[ldptr->end].x;
          x = level->things[thingnum].xpos;
          if (x >= MIN(lx0, lx1) && x <= MAX(lx0, lx1))
            {
              /* special case: the Thing is on a LineDef - return directly */
              n = ldptr->sidedef1;
              if (n >= 0)
                return level->sidedefs[n].sector;
              else
                return -1;
            }
        }

#ifdef BUGGY_TURBOC_3
      ldptr = ldptr + 1;
#else
      ldptr++;
#endif
    }
  if (bestldptr == NULL)
    return -1;
  /* now look if this LineDef has a SideDef bound to one sector */
  if (level->vertexes[bestldptr->start].y > level->vertexes[bestldptr->end].y)
    n = bestldptr->sidedef1;
  else
    n = bestldptr->sidedef2;
  if (n >= 0)
    return level->sidedefs[n].sector;
  else
    return -1;
}



/*
   Check if there is something of interest inside the given box.
*/

Int16 GetCurObject(LevelPtr level, int objtype, Int16 x0, Int16 y0, Int16 x1, Int16 y1)
{
  Int16 n, m, cur, curx;
  Int16 lx0, ly0, lx1, ly1;
  Int16 midx, midy;

  cur = -1;
  if (x1 < x0)
    {
      n = x0;
      x0 = x1;
      x1 = n;
    }
  if (y1 < y0)
    {
      n = y0;
      y0 = y1;
      y1 = n;
    }

  switch (objtype)
    {
    case OBJ_THINGS:
      for (n = 0; n < level->num_things; n++)
        if (level->things[n].xpos >= x0 && level->things[n].xpos <= x1 && level->things[n].ypos >= y0 && level->things[n].ypos <= y1)
          {
            cur = n;
            break;
          }
      break;
    case OBJ_VERTEXES:
      for (n = 0; n < level->num_vertexes; n++)
        if (level->vertexes[n].x >= x0 && level->vertexes[n].x <= x1 && level->vertexes[n].y >= y0 && level->vertexes[n].y <= y1)
          {
            cur = n;
            break;
          }
      break;
    case OBJ_LINEDEFS:
      for (n = 0; n < level->num_linedefs; n++)
        {
          if (IsLineDefInside(level, n, x0, y0, x1, y1))
            {
              cur = n;
              break;
            }
        }
      break;
    case OBJ_SECTORS:
      /* hack, hack...  I look for the first LineDef crossing an horizontal half-line drawn from the cursor */
      curx = level->map_maxX + 1;
      cur = -1;
      midx = (x0 + x1) / 2;
      midy = (y0 + y1) / 2;
      for (n = 0; n < level->num_linedefs; n++)
        if ((level->vertexes[level->linedefs[n].start].y > midy) != (level->vertexes[level->linedefs[n].end].y > midy))
          {
            lx0 = level->vertexes[level->linedefs[n].start].x;
            ly0 = level->vertexes[level->linedefs[n].start].y;
            lx1 = level->vertexes[level->linedefs[n].end].x;
            ly1 = level->vertexes[level->linedefs[n].end].y;
            m = lx0 + (Int16) ((long) (midy - ly0) * (long) (lx1 - lx0) / (long) (ly1 - ly0));
            if (m >= midx && m < curx)
              {
                curx = m;
                cur = n;
              }
          }
      /* now look if this LineDef has a SideDef bound to one sector */
      if (cur >= 0)
        {
          if (level->vertexes[level->linedefs[cur].start].y > level->vertexes[level->linedefs[cur].end].y)
            cur = level->linedefs[cur].sidedef1;
          else
            cur = level->linedefs[cur].sidedef2;
          if (cur >= 0)
            cur = level->sidedefs[cur].sector;
          else
            cur = -1;
      }
      else
        cur = -1;
      break;
    }
  return cur;
}



/*
   Select all objects inside a given box.
*/

SelPtr SelectObjectsInBox(LevelPtr level, int objtype, Int16 x0, Int16 y0, Int16 x1, Int16 y1)
{
  Int16  n, m;
  SelPtr list;

  list = NULL;
  if (x1 < x0)
    {
      n = x0;
      x0 = x1;
      x1 = n;
    }
  if (y1 < y0)
    {
      n = y0;
      y0 = y1;
      y1 = n;
    }

  switch (objtype)
    {
   case OBJ_THINGS:
      for (n = 0; n < level->num_things; n++)
        if (level->things[n].xpos >= x0 && level->things[n].xpos <= x1 && level->things[n].ypos >= y0 && level->things[n].ypos <= y1)
          SelectObject(&list, n);
      break;
    case OBJ_VERTEXES:
      for (n = 0; n < level->num_vertexes; n++)
         if (level->vertexes[n].x >= x0 && level->vertexes[n].x <= x1 && level->vertexes[n].y >= y0 && level->vertexes[n].y <= y1)
           SelectObject(&list, n);
      break;
    case OBJ_LINEDEFS:
      for (n = 0; n < level->num_linedefs; n++)
      {
        /* the two ends of the line must be in the box */
        m = level->linedefs[n].start;
         if (level->vertexes[m].x < x0 || level->vertexes[m].x > x1 || level->vertexes[m].y < y0 || level->vertexes[m].y > y1)
           continue;
        m = level->linedefs[n].end;
         if (level->vertexes[m].x < x0 || level->vertexes[m].x > x1 || level->vertexes[m].y < y0 || level->vertexes[m].y > y1)
           continue;
        SelectObject(&list, n);
      }
      break;
    case OBJ_SECTORS:
      /* hack: select all sectors... */
      for (n = 0; n < level->num_sectors; n++)
        SelectObject(&list, n);
      /* ... then remove the unwanted ones from the list */
      for (n = 0; n < level->num_linedefs; n++)
        {
          m = level->linedefs[n].start;
          if (level->vertexes[m].x < x0 || level->vertexes[m].x > x1 || level->vertexes[m].y < y0 || level->vertexes[m].y > y1)
            {
              m = level->linedefs[n].sidedef1;
              if (m >= 0 && level->sidedefs[m].sector >= 0)
                UnSelectObject(&list, level->sidedefs[m].sector);
              m = level->linedefs[n].sidedef2;
              if (m >= 0 && level->sidedefs[m].sector >= 0)
                UnSelectObject(&list, level->sidedefs[m].sector);
              continue;
            }
          m = level->linedefs[n].end;
          if (level->vertexes[m].x < x0 || level->vertexes[m].x > x1 || level->vertexes[m].y < y0 || level->vertexes[m].y > y1)
            {
              m = level->linedefs[n].sidedef1;
              if (m >= 0 && level->sidedefs[m].sector >= 0)
                UnSelectObject(&list, level->sidedefs[m].sector);
              m = level->linedefs[n].sidedef2;
              if (m >= 0 && level->sidedefs[m].sector >= 0)
                UnSelectObject(&list, level->sidedefs[m].sector);
              continue;
            }
        }
      break;
    }
  return list;
}



/* end of file */