Listing 1 (QC.H)

///////////////////////////////////////////////////////
// Header file for quadcodes
//  by Kenneth Van Camp
///////////////////////////////////////////////////////
typedef unsigned char BYTE;
typedef long          COORD;

// The following should be defined on computers that
// store their most-significant byte first in integers:
// #define MSB_FIRST

// Store (I,J) coordinates in long integers, so this is
// the only limitation on the accuracy of storage:
#define NBITS_COORD sizeof(COORD) * 8

// Define the following to use static-length QuadCodes.
// If not defined, dynamic allocation is used:
#define STAT_QC

#ifdef STAT_QC
# define NBYTE_QC   8    // # bytes to store a quadcode
# define MAXQUITS   (min (NBITS_COORD, 4*NBYTE_QC))
#else
# define MAXQUITS  NBITS_COORD
#endif

// class QuadCode: Store a single quadcode
// (2 bits per quit).
class QuadCode
{
  protected:
#ifdef STAT_QC
    BYTE qca[NBYTE_QC];    // storage area for quadcode
    void FreeMem (void)    // free dynamic memory
       { nquits=0; }
#else
    BYTE *qca;             // storage area for quadcode
    void FreeMem (void);   // free dynamic memory
#endif
    void Init              // initializer from string
       (const char *chqc);

  public:
    int nquits;            // # of quits in qc
    QuadCode (void)        // default constructor
       { nquits = 0; }
    QuadCode               // constructor from (I,J)
       (COORD i, COORD j, int nq);
    QuadCode               // constructor from string
       (const char *chqc)
       { Init (chqc); }
#ifndef STAT_QC
    ~QuadCode (void)       // destructor
       { FreeMem(); }
#endif
    int GetQuit            // extract single quit
       (int quit);
    void SetQuit           // set single quit
       (int quit, int val);
    void ToIJ              // convert to (I,J)
       (COORD &i, COORD &j, int &nq);
    int Compare            // compare two quadcodes
       (QuadCode &qc);
    int Sibling            // is qc a sibling?
       (const QuadCode *qc);
    int Contains           // does one qc contain other?
       (QuadCode &qc);
    void MakeParent        // make qc into its parent
       (void);
    QuadCode &operator= (QuadCode &qc);
    int operator< (QuadCode &qc)
      { return (this->Compare (qc) < 0); }
    int operator> (QuadCode &qc)
      { return (this->Compare (qc) > 0); }
    int operator<= (QuadCode &qc)
      { return (this->Compare (qc) <= 0); }
    int operator>= (QuadCode &qc)
      { return (this->Compare (qc) >= 0); }
    int operator== (QuadCode &qc)
      { return (this->Compare (qc) == 0); }
    int operator!= (QuadCode &qc)
      { return (this->Compare (qc) != 0); }

    friend ostream &operator<<
      (ostream &stream, QuadCode &qc);
    friend istream &operator>>
      (istream &stream, QuadCode &qc);
}; // class QuadCode

// class QCNode: A node in a linked list of quadcodes.
class QCNode: public QuadCode
{
  private:
    QCNode *next;         // next node in linked list
    // Friend classes for access to 'next'.
    friend Region, RegionDisplay;
    // Same for its "put to" operator.
    friend ostream &operator<<
      (ostream &stream, Region &reg);

  public:
    QCNode (void)         // default constructor
       { next = NULL; }
    QCNode                // constructor from (I,J)
       (COORD i, COORD j, int nq):
       QuadCode (i, j, nq)  // calls qc constr first
       { next = NULL; }
}; // class QCNode

// struct Point: One point on outline of region.
struct Point
{
  COORD i, j;
};

// struct PointListHeader: An array of points.
struct PointListHeader
{
  int length;             // # of points in array
  COORD ndiv;             // # (I,J) divisions in grid
  struct Point *pointptr; // array of points
};

// class Region: A linked list of QuadCodes
class Region
{
  protected:
    QCNode *first_qcnode; // start of linked list
    COORD ndiv;           // # (I,J) divisions in grid
    void ScanOutAET       // create qc's along one row
       (COORD i_to_scan, int &nqc_compress, int nquits);
    void AddRow           // add row of qc's
       (COORD i, COORD j1, COORD j2, int nquits);
    void AddQC            // add a single qc
       (COORD i, COORD j, int nquits);
    int MaxQuits (void);  // find max #quits in a qc

  public:
    Region (void)         // default constructor
      { first_qcnode = NULL; ndiv = 0; }
    Region                // constructor from outline
       (PointListHeader &vertext_list);
    ~Region (void);       // destructor
    int Compress (void);  // region compressor
    int InRegion          // is qc in region?
       (QuadCode &qc);
    int NumQC (void);     // count quadcodes in region
    friend ostream &operator<<
      (ostream &stream, Region &reg);
}; // class Region
/* End of File */