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

#ifndef _SKIPGRID_H
#define _SKIPGRID_H

#include "newtypes.h"
#include "stdio.h"
#include "stdlib.h"

// These macros only apply to the first byte of grid sections
#define SG_EMPTY_BIT 0x80
#define SG_DATA_BITS 0x7F

///////////////////////////////////////////////////////////////////////
// SkipGrid - This class handles a 2D lookup array that helps to     //
//           increase the efficiency of avoiding overdrawing         //
//           objects.                                                //
// Key:                   f1        e   gp  f2                       //
//   # = used             V         V   V   V                        //
//   - = unused           ##########--------########                 //
//                                                                   //
//                        f1   gp   e       f2                       //
//                        V    V    V       V                        //
//                        ##########--------########                 //
//                                                                   //
//                       f1,e  gp           f2                       //
//                        V    V            V                        //
//                        ------------------########                 //
//                                                                   //
//                                f1   gp          e,f2              //
//                                V    V            V                //
//                        --------##################                 //
//                                                                   //
// f1 - points at the front of an active region.  This will be       //
//       filled unless at the beginning of grid section and the      //
//       beginning is empty.                                         //
// e - points at the middle of an active region.  This will be       //
//       empty unless at the end of a grid section.                  //
// f2 - points at the end of an active region.  This will be filled  //
//       unless at the end of a grid section.                        //
// gp - points at the active point in the grid.  Also known as       //
//       the active grid pointer.  It is always in the region        //
//       between [f1,f2).*                                           //
//                                                                   //
// * '[' or ']' = inclusive, '(' or ')' = exclusive                  //
///////////////////////////////////////////////////////////////////////
class SkipGrid
   {
   private:
      uint8 *skipgrid_f1;  // The beginning of search region that is full.
      uint8 *skipgrid_e;   // The empty area sandwiched between f1 and f2.
      uint8 *skipgrid_f2;  // The end of the empty part of the search region.
      uint8 *skipgrid_end; // The pointer to the element just beyond the end
                           //    of the selected skipgrid region.
      int skipgrid_mask;   // The mask for truncating positions to get grid
                           //    grid positions.
      int sg_unit_width;   // width of a skipgrid segment.
      int sg_width;  // width of skipgrid elements.
      int sg_height; // height of skipgrid elements.
      int sg_size;   // total size of skipgrid.
      uint8 *grid_memory;  // The pointer where the grid is allocated.
      uint8 *grid;   // The actual grid.
      uint8 *grid_ptr;  // The active point in the grid.
   public:
      SkipGrid(int width, int height);
      ~SkipGrid();
      uint8 *getGridPtr(void);
      int getGridPos(void);
      int findEmpty(int offset, int width);
      uint8 getIEmptyWidth(void);

      void fillIEmpty(uint8 width);

      int getEmptyWidth(int limit);

      int fillEmpty(int limit);

      void clearGrid(void);

      void setGridPos(int offset);

      void advanceGridPos(int offset);

      int nextEmpty(int limit);

   };


#endif