///////////////////////////////////////////////////////////////////////
// Source file for skipgrid.cpp.  It defines needed functions        //
//            for drawing graphics that overlap.                     //
///////////////////////////////////////////////////////////////////////
//                Copyright 1998 by Joshua Cantrell                  //
//                      All Rights Reserved                          //
///////////////////////////////////////////////////////////////////////

#include <skipgrid.h>

// SkipGrid class constructor.
SkipGrid::SkipGrid(int width, int height)
   {
   sg_unit_width = 32;     // Make each horizontal run 32 pixels long.
   sg_width = width;       // The width of the skip grid in pixels.
   sg_height = height;     // The height of the skip grid in pixels.

   skipgrid_mask = (int)~0x01F;

   // The total number of pixels in skip grid.
   sg_size = sg_width * sg_height;
   // Need to align the size with sg_unit_width and create an extra patch
   //    inorder to align the grid with the skipgrid_mask.
   sg_size += (sg_unit_width - (sg_size % sg_unit_width)) + sg_unit_width;

   // Create and initialize the grid's memory block.
   grid_memory = new uint8[sg_size];
   grid_ptr = grid = (uint8 *)((int)(grid_memory + sg_unit_width) &
                               skipgrid_mask);
   for (int i=0; i < sg_size; i += sg_unit_width)
      grid[i] = SG_EMPTY_BIT | sg_unit_width;   // Set up each grid run.

   skipgrid_f1 = skipgrid_e = grid_ptr;
   skipgrid_f2 = skipgrid_end = grid_ptr + sg_unit_width;
   }


// SkipGrid class destructor.
SkipGrid::~SkipGrid()
   {
   delete [] grid_memory;
   }


///////////////////////////////////////////////////////////////////////
// findEmpty - Given an offset from the beginning of the SkipGrid,   //
//       this searches for the first unused space within the width   //
//       given from the offset position.                             //
// PARAMETERS:                                                        //
//    offset - The offset from the beginning of the grid to start    //
//          searching for an unused space.                           //
//    width - The width to search after arriving at the offset.      //
// RETURNS:                                                          //
//    0 - Success!                                                   //
//   -1 - No dice... (all used)                                      //
///////////////////////////////////////////////////////////////////////
int SkipGrid::findEmpty(int offset, int width)
   {
   setGridPos(offset);
   return nextEmpty(width);
   }


///////////////////////////////////////////////////////////////////////
// getGridPtr - Returns the current active grid pointer.             //
// PARAMETERS:                                                        //
//    - none -                                                       //
// RETURNS:                                                          //
//    The current position of the active grid pointer.               //
///////////////////////////////////////////////////////////////////////
uint8 *SkipGrid::getGridPtr(void)
   {
   return grid_ptr;
   }


///////////////////////////////////////////////////////////////////////
// getGridPos - Returns the current position of the active grid      //
//       pointer.                                                    //
// PARAMETERS:                                                        //
//    - none -                                                       //
// RETURNS:                                                          //
//    The current position of the active grid pointer.               //
///////////////////////////////////////////////////////////////////////
int SkipGrid::getGridPos(void)
   {
   return grid_ptr - grid;
   }


///////////////////////////////////////////////////////////////////////
// getIEmptyWidth - Returns the internal grid width of empty spaces  //
//       at the active grid pointer.  This should only be done if it //
//       is known that the grid pointer is in an empty region, or    //
//       unspecified results may be returned.                        //
// PARAMETERS:                                                        //
//    - none -                                                       //
// RETURNS:                                                          //
//    The amount of empty space following the active grid pointer    //
// until the next filled space or following grid section.            //
///////////////////////////////////////////////////////////////////////
uint8 SkipGrid::getIEmptyWidth(void)
   {
   return (*skipgrid_e & SG_DATA_BITS) - (grid_ptr - skipgrid_e);
   }


///////////////////////////////////////////////////////////////////////
// fillIEmpty - Fills in the space at the currently active grid      //
//       pointer in the amount of the given width.  This only works  //
//       if you are certain the active grid pointer is in an empty   //
//       space, otherwise unspecified results may occur.  It also    //
//       only works inbetween grid sections.  If your width goes     //
//       beyond a grid section, or the first filled area,            //
//       unspecified results may occur.                              //
// PARAMETERS:                                                        //
//    width - The width to fill at the active grid pointer location. //
//                                                                   //
///////////////////////////////////////////////////////////////////////
void SkipGrid::fillIEmpty(uint8 width)
   {
   uint8 *goal_pos = grid_ptr + width;
   if (skipgrid_e == grid_ptr)
      {
      if (*skipgrid_e & SG_EMPTY_BIT)  // This only occurs when
                                       //    skipgrid_e == skipgrid_f1.
         {
         *skipgrid_e = width;  // f1,e,gp      f2      f1    e   f2
         skipgrid_e += width;  //    V         V       V     V   V
         }                     //    ----------#### to ######----####
      else
         {                      //   f1 e,gp     f2    f1      e   f2
         *skipgrid_f1 += width; //   V   V       V     V       V   V
         skipgrid_e += width;   //   ####--------## to ########----##
         }
      if ((skipgrid_e == skipgrid_f2) && (skipgrid_f2 != skipgrid_end))
         {                             // f1  e,f2          f1      e   f2
                                       // V    V            V       V   V
         *skipgrid_f1 += *skipgrid_f2; // ########----## to ########----##
         skipgrid_e = skipgrid_f2 + *skipgrid_f2;
         if (skipgrid_e != skipgrid_end)
            skipgrid_f2 = skipgrid_e + *skipgrid_e;
         else
            skipgrid_f2 = skipgrid_e;
         }
      else
         {
         *skipgrid_e = skipgrid_f2 - skipgrid_e;   // Recalculate gap.
         }
      }
   else
      {
      if (grid_ptr + width == skipgrid_f2)
         {
         *skipgrid_e -= width;
         if (skipgrid_f2 == skipgrid_end)
            {
            *grid_ptr = width;         //  f1    e  gp   f2            f1  e,f2
            skipgrid_f1 = grid_ptr;    //  V     V  V    V             V    V
            skipgrid_e = skipgrid_f2;  //  ######--------  to ######---#####
            }
         else
            {
            *grid_ptr = width + *skipgrid_f2; // f1 e gp f2           f1   e f2
            skipgrid_f1 = grid_ptr;           // V  V V  V            V    V V
            skipgrid_e = grid_ptr + *grid_ptr;// ###-----##-- to ###--#####--
	         if (skipgrid_e == skipgrid_end)
               skipgrid_f2 = skipgrid_e;
            else
               skipgrid_f2 = skipgrid_e + *skipgrid_e;
            }
         }
      else
         {
         *skipgrid_e -= skipgrid_f2 - grid_ptr;
         *grid_ptr = width;             //  f1  e  gp   f2           f1 e f2
	      skipgrid_f1 = grid_ptr;        //  V   V  V    V            V  V V
         skipgrid_e = grid_ptr + width; //  ####--------## to ####---###--##
         *skipgrid_e = skipgrid_f2 - skipgrid_e;
         }
      }
   grid_ptr = goal_pos;    // Set the grid pointer to the goal location.
                           //    This may be the end of the grid section.
   }


///////////////////////////////////////////////////////////////////////
// getEmptyWidth - Returns the grid width of empty spaces at the     //
//       active grid pointer within the given width limit.  This     //
//       should only be done if it is known that the grid pointer    //
//       is in an empty region, or unspecified results may be        //
//       returned.                                                   //
// PARAMETERS:                                                       //
//    limit - The maximum width sought.  Any limit should not be     //
//          wide enough to exceed the bounds of the grid's data.     //
// RETURNS:                                                          //
//    The amount of empty space following the active grid pointer    //
// until the next filled space or width limit is met.                //
///////////////////////////////////////////////////////////////////////
int SkipGrid::getEmptyWidth(int limit)
   {
   int size = skipgrid_f2 - grid_ptr;  // Find initial empty space
   uint8 *grid_pos = grid_ptr;
   uint8 *grid_f = skipgrid_f2;

   // Add up the chunks of following empty space in following grid segments.
   while ((limit > size) && (*grid_f & SG_EMPTY_BIT))
      {
      grid_pos = grid_f;
      grid_f += *grid_f & SG_DATA_BITS;
      size += grid_f - grid_pos;
      }

   // Don't let the width be over the limit size.
   if (limit < size) return limit;
   return size;
   }


///////////////////////////////////////////////////////////////////////
// fillEmpty - Fills in the space at the currently active grid       //
//       pointer in the amount of the given width.  This only works  //
//       if you are certain the active grid pointer is in an empty   //
//       space, otherwise unspecified results may occur.  This works //
//       through grid sections boundaries.  It fills up until the    //
//       given width limit, or the empty space is exhausted.         //
// PARAMETERS:                                                        //
//    limit - The limit of the width to fill at the active grid      //
//          pointer location.                                        //
// RETURNS:                                                          //
//    The amount of empty space filled following the active grid     //
// pointer.                                                          //
///////////////////////////////////////////////////////////////////////
int SkipGrid::fillEmpty(int limit)
   {
   int size = skipgrid_f2 - grid_ptr;
   int width;

   if (size > limit) size = limit;
   if ((*skipgrid_f2 & SG_EMPTY_BIT) && ((limit + grid_ptr) >= skipgrid_f2))
      {
      fillIEmpty(size);
      skipgrid_f1 = skipgrid_e = skipgrid_f2;
      skipgrid_f2 = skipgrid_e + (*skipgrid_e & SG_DATA_BITS);
      size += skipgrid_f2 - skipgrid_e;
      while ((size < limit) && (*skipgrid_f2 & SG_EMPTY_BIT))
         {
         *skipgrid_e = sg_unit_width;
         skipgrid_f1 = skipgrid_e = skipgrid_f2;
         skipgrid_f2 = skipgrid_e + (*skipgrid_e & SG_DATA_BITS);
         size += skipgrid_f2 - skipgrid_e;
         }
      width = (skipgrid_f2 - skipgrid_e) - (size - limit);
      if (limit < size) size = limit;
      grid_ptr = skipgrid_e;
      skipgrid_end = (uint8 *)((int)grid_ptr & skipgrid_mask) + sg_unit_width;
      }
   else
      {
      width = size;
      }
   fillIEmpty(width);
   return size;
   }


///////////////////////////////////////////////////////////////////////
// clearGrid - Clears/sets-up the complete grid for use.  This also  //
//       positions the active grid pointer at the beginning and      //
//       automatically points the other pointers at correct default  //
//       positions.                                                  //
// PARAMETERS:                                                        //
//    - none -                                                       //
//                                                                   //
///////////////////////////////////////////////////////////////////////
void SkipGrid::clearGrid(void)
   {
   uint8 *grid_end = grid + sg_size;
   for (grid_ptr = grid; grid_ptr < grid_end; grid_ptr += sg_unit_width)
      *grid_ptr = SG_EMPTY_BIT | sg_unit_width;
   skipgrid_f1 = grid;
   skipgrid_e = grid;
   skipgrid_f2 = grid + sg_unit_width;
   skipgrid_end = skipgrid_f2;
   grid_ptr = skipgrid_e;
   }


///////////////////////////////////////////////////////////////////////
// setGridPos - Given an offset from the beginning of the SkipGrid,  //
//       this sets the active grid pointer to the given position.    //
// PARAMETERS:                                                        //
//    offset - The offset from the beginning of the grid to set as   //
//          the active grid pointer position.                        //
//                                                                   //
///////////////////////////////////////////////////////////////////////
void SkipGrid::setGridPos(int offset)
   {
   uint8 *goal_ptr = grid + offset;    // Find goal position in grid.

   // Determine whether the advance can be done at the current active grid
   //    pointer position or not.
   if ((grid_ptr > goal_ptr) ||
       (((int)grid_ptr & skipgrid_mask) != ((int)goal_ptr & skipgrid_mask)))
      {
      grid_ptr = goal_ptr;     // Advance to offset position in grid
      // Advance skipgrid to correct starting position.
      skipgrid_f1 = ((int)grid_ptr & skipgrid_mask); // Align pntr with grid
      skipgrid_end = skipgrid_f1 + sg_unit_width;
      if (*skipgrid_f1 & SG_EMPTY_BIT)  // First pixel is actually empty.
         {                              //  f1,e          f1,e
                                        //   V             V
         skipgrid_e = skipgrid_f1;      //   -######### or ------####
         skipgrid_f2 = skipgrid_e + (*skipgrid_e & SG_DATA_BITS);
         }
      else
         {
         skipgrid_e = skipgrid_f1 + *skipgrid_f1;  // f1  e   f2    f1       e,f2
         if (skipgrid_e == skipgrid_end)           // V   V   V     V         V
            skipgrid_f2 = skipgrid_e;              // ####----## or ##########
         else
            skipgrid_f2 = skipgrid_e + *skipgrid_e;
         }
      }
   else        // Can advance from the current active grid pointer position.
      {
      grid_ptr = goal_ptr;     // Advance to offset position in grid
      }

   // Advance f1, e, and f2 pointers to surround grid_ptr.
   while (grid_ptr > skipgrid_f2)
      {
      skipgrid_f1 = skipgrid_f2;
      skipgrid_e = skipgrid_f1 + *skipgrid_f1;
      if (skipgrid_e == skipgrid_end)
         {
         skipgrid_f2 = skipgrid_e;
         break;
         }
      skipgrid_f2 = skipgrid_e + *skipgrid_e;
      }
   }


///////////////////////////////////////////////////////////////////////
// advanceGridPos - Given an offset from the active grid pointer,    //
//       this sets the active grid pointer to the given position.    //
// PARAMETERS:                                                        //
//    offset - The offset from the active grid pointer for moving    //
//          the active grid pointer position.                        //
//                                                                   //
///////////////////////////////////////////////////////////////////////
void SkipGrid::advanceGridPos(int offset)
   {
   setGridPos(offset + (grid - grid_ptr));
   }


///////////////////////////////////////////////////////////////////////
// nextEmpty - Starting from the active grid pointer, this searches  //
//       for the first unused space within the width given from the  //
//       offset position.                                            //
// PARAMETERS:                                                        //
//    limit - The width to search after arriving at the offset.      //
// RETURNS:                                                          //
//    0 - Success!                                                   //
//   -1 - No dice... (all used)                                      //
///////////////////////////////////////////////////////////////////////
int SkipGrid::nextEmpty(int limit)
   {
   uint8 *skipgrid_last = grid_ptr + limit;
   if (skipgrid_e > grid_ptr)    // Advance grid_ptr to an empty position.
      {
      //size = skipgrid_e - grid_ptr;
      grid_ptr = skipgrid_e;
      }
   // Advance to first empty location within range.
   while ((skipgrid_e == skipgrid_end) && (skipgrid_e < skipgrid_last))
      {
      skipgrid_end += sg_unit_width;
      skipgrid_f1 = skipgrid_e;
      if (*skipgrid_f1 & SG_EMPTY_BIT)  // First pixel is actually empty.
         {
         skipgrid_f2 = skipgrid_f1 + (*skipgrid_f1 & SG_DATA_BITS);
         break;
         }
      skipgrid_e = skipgrid_f1 + *skipgrid_f1;
      if (skipgrid_e != skipgrid_end)
         {
         skipgrid_f2 = skipgrid_e + *skipgrid_e;
         break;
         }
      skipgrid_f2 = skipgrid_e;
      }
   if (skipgrid_e > skipgrid_last)
      {
      grid_ptr = skipgrid_last;  // We reached the end-of-the-line.
      return -1;
      }
   if (grid_ptr < skipgrid_e)
      grid_ptr = skipgrid_e;     // We found an empty region.
   return 0;
   }