///////////////////////////////////////////////////////
// Quadcode support routines
// by Kenneth Van Camp
///////////////////////////////////////////////////////
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#ifdef_TURBOC__
#include <iostream.h>
#else
#include <stream.hpp>
#endif
#include "qc.h"
// The following macro returns the number of bytes reqd
// to store a quadcode, given the number of quits:
#define QC_NBYTES(q) (((q) - 1) / 4 + 1)
// These are shifts & masks to extract a single quit
static int QCshifts[4] = { 6, 4, 2, 0 };
static int QCmasks[4] = { 3<<6, 3<<4, 3<<2, 3 };
// This is the inverse mask:
static int QCimasks[4] =
{ 0xff^(3<<6), 0xff^(3<<4), 0xff^(3<<2), 0xff^3 };
// And these are masks for each bit in a normal byte:
static int bitmasks[8] =
{ 1, 1<<1, 1<<2, 1<<3, 1<<4, 1<<5, 1<<6, 1<<7 };
#ifndef STAT_QC
void QuadCode::FreeMem (void)
// Free dynamic memory.
{
if (nquits > 0 && qca)
delete qca;
qca = NULL;
nquits = 0;
} // QuadCode::FreeMem
#endif // STAT_QC
QuadCode::QuadCode (COORD i, COORD j, int nq)
// QuadCode constructor from (I,J) coordinates of the
// upper-left corner of the qc.
// i is the vertical row# of quadcode (0 at top)
// j is the horizontal column# of quadcode
// nq is the # of quits in quadcode
{
#ifndef STAT_QC
qca = NULL;
#endif
nquits = 0;
assert (nq > 0 && nq <= MAXQUITS);
// We traverse both the (i,j) coordinates and the qc
// from the msb to the lsb and msq to msq. Note the
// following assumes MAXQUITS is a multiple of 8.
#ifdef MSB_FIRST
BYTE *ip = (BYTE *)&i + (MAXQUITS - nq) / 8;
BYTE *jp = (BYTE *)&j + (MAXQUITS - nq) / 8;
#else
BYTE *ip = (BYTE *)&i + sizeof(COORD) - 1 -
(MAXQUITS - nq) / 8;
BYTE *jp = (BYTE *)&j + sizeof(COORD) - 1 -
(MAXQUITS - nq) / 8;
#endif
int bit = 7 - (MAXQUITS - nq) % 8;
int nbytes = QC_NBYTES (nq);
#ifndef STAT_QC
qca = new BYTE [nbytes];
assert (qca != NULL);
#endif
memset (qca, '\0', nbytes);
BYTE *p = qca;
nquits = nq;
int pos = 0; // position within qc (0,1,2,3)
for ( ; nq > 0; nq--)
{
if (*ip & bitmasks[bit])
*p |= i << (QCshifts[pos] + 1);
if (*jp & bitmasks[bit])
*p |= 1 << QCshifts[pos];
// Advance to next quit
if (++pos > 3)
{
pos = 0;
p++;
}
// Back up to next bit
if (--bit < 0)
{
bit = 7;
#ifdef MSB_FIRST
ip++; jp++;
#else
ip--; jp--;
#endif
} // if --bit
) // for nq
} // QuadCode::QuadCode
void QuadCode::Init (const char *chqc)
// QuadCode initializer from string.
// chqc is the quadcode in a null-terminated
// character representation - i.e., "123"
{
int nq = strlen (chqc);
#ifndef STAT_QC
qca = NULL;
#endif
nquits = 0;
assert (nq > 0 && nq <= MAXQUITS);
size_t nbytes = QC_NBYTES (nq);
#ifndef STAT_QC
qca = new BYTE [nbytes];
assert (qca != NULL);
#endif
memset (qca, '\0', nbytes);
// Store quadcode in binary form, from msq to lsq.
int i;
int pos; // pos within byte of this quit (0,1,2,3)
BYTE *p; // ptr to current byte in qc
for (i = 0, pos = 0, p = qca; i < nq; i++)
{
int val = chqc[i] - '0';
assert (val >= 0 && val <= 3);
*p |= val << QCshifts[pos];
if (++pos > 3)
{
pos = 0;
p++;
}
} // for i
nquits = nq;
} // QuadCode::Init
in the beginning (i.e., near the end of the list) have
int QuadCode::GetQuit (int quit)
// Return single quit from quadcode.
// quit is the pos# of the quit to extract (zero-based).
// Pos 0 is the high-order quit ('1' in "123").
{
assert {quit <= nquits && quit >= 0);
int byte = quit / 4;
int pos = quit % 4;
return ( (*(qca + byte) & QCmasks[pos]) >>
QCshifts[pos]);
} // QuadCode::GetQuit
void QuadCode::SetQuit (int quit, int val)
// Set value of a single quit.
// quit is the pos# of the quit to extract (zero-based).
// val is the value of the quit (0, 1, 2 or 3).
{
assert (quit <= nquits && quit >= 0 && val >= 0 &&
val < 4);
BYTE *p = qca + quit / 4;
int pos = quit % 4;
// Clear out the old value
*p &= (255 - QCmasks[pos]);
// Put in the new value
*p |= val << QCshifts[pos];
} // QuadCode::SetQuit
void QuadCode::ToIJ (COORD &i, COORD &j, int &nq)
// Convert quadcode value to (I,J).
// The offsets returned are the coords of the
// upper-left corner of the quadcode.
// i is the row#
// j is the col#
// nq is the #quits
{
i = j = nq = 0;
if (nquits < 1)
return;
assert (nquits <= MAXQUITS);
nq = nquits;
// Go from lsq to msq. Following loop is based on the
// conversion algorithm by Gargantini:
#ifdef MSB_FIRST
BYTE *ip = (BYTE *)&i + sizeof(COORD) - 1;
BYTE *jp = (BYTE *)&j + sizeof(COORD) - 1;
#else
BYTE *ip = (BYTE *)&i;
BYTE *jp = (BYTE *)&j;
#endif
int quit, // current quit# in qc
bit = 0; // current bit# in byte of (i,j)
for (quit = nquits-1; quit >= 0; quit--)
{
int val = GetQuit (quit);
// Bit pos 0 gives J val, bit pos 1 gives I val.
int ival = val >> 1;
int jval = val & 1;
*ip |= (ival << bit);
*jp |= (jval << bit);
// Advance to next bit
if (bit == 7)
{
bit = 0;
#ifdef MSB_FIRST
ip--; jp--;
#else
ip++; jp++;
#endif
}
else
bit++;
} // for quit
} // QuadCode::ToIJ
int QuadCode::Compare (QuadCode &qc)
// Compare one quadcode to another.
// Return 0 if the two quadcodes are equal; -1 if the
// current quadcode is less than qc; or +1 if the
// current quadcode is greater than qc.
// qc is the quadcode to compare to
{
// Check for zero-length quadcodes
if (nquits == 0)
{
if (qc.nquits == 0)
return 0;
else
return -1;
}
else if (qc.nquits == 0)
return 1;
BYTE *p1 = qca;
BYTE *p2 = qc.qca;
BYTE *end1 = p1 + QC_NBYTES (nquits) - 1;
BYTE *end2 = p2 + QC_NBYTES (qc.nquits) - 1;
// Compare each byte of the two quadcodes.
for ( ; p1 <= end1 && p2 <= end2; p1++, p2++)
if (*p1 != *p2)
{
if (*p1 < *p2)
return -1;
else
return 1;
}
if (nquits == qc.nquits)
// quadcodes same
return 0;
else if (nquits < qc.nquits)
// this quadcode contains qc
return -1;
else
// qc contains this quadcode
return 1;
} // QuadCode::Compare
int QuadCode::Sibling (const QuadCode *qc)
// Compare one quadcode to another.
// Return TRUE if they are siblings, FALSE if not.
// qc is the quadcode to compare to
{
// Must be the same length, can't be empty.
if (qc == NULL || nquits != qc->nquits || nquits==0)
return (FALSE);
BYTE *p1 = qca;
BYTE *p2 = qc->qca;
BYTE *end1 = p1 + QC_NBYTES (nquits) - 1;
// Compare each byte of the two quadcodes.
// If any differ except the last, then not siblings.
for ( ; p1 < end1; p1++, p2++)
if (*p1 != *p2)
return (FALSE);
if (*p1 == *p2)
// Quadcodes are same
return (FALSE);
// Make sure final byte matches in all but last quit.
int pos = (nquits-1) % 4;
return
((*p1 & QCimasks[pos]) == (*p2 & QCimasks[pos]));
} // QuadCode::Sibling
int QuadCode::Contains (QuadCode &qc)
// Compare one quadcode to another.
// Return TRUE if the current quadcode contains qc
// (i.e., is equal to it or is a parent of it), or
// FALSE otherwise.
// qc is the quadcode to compare to
{
if (nquits > qc.nquits)
return (FALSE);
if (nquits == 0)
return (TRUE);
BYTE *p1 = qca;
BYTE *p2 = qc.qca;
BYTE *end1 = p1 + QC_NBYTES (nquits) - 1;
BYTE *end2 = p2 + QC_NBYTES (qc.nquits) - 1;
// Compare each byte of the two quadcodes.
for { ; p1 <= end1 && p2 <= end2; p1++, p2++)
if (*p1 != *p2)
{
// Found a byte that differs. This quadcode
// contains qc iff: (1) We are at the last byte
// of this quadcode; and (2) All quits in this
// quadcode before the last one match the
// corresponding quits in qc.
if (p1 != end1)
return (FALSE);
int lastpos = (nquits - 1) % 4;
int pos;
for (pos = lastpos; pos >= 0; pos--)
if ((*p1 & QCmasks[pos]) !=
(*p2 & QCmasks[pos]))
return (FALSE);
// They match up to nquits.
return (TRUE);
}
// All bytes match - either qc's are same or this is
// the parent.
return (TRUE);
} // QuadCode::Contains
void QuadCode::MakeParent (void)
// Make quadcode into its parent.
{
// Clear the bits that saved the last quit. Don't
// bother to reclaim storage if size is reduced.
nquits--;
int byte = nquits / 4;
int pos = nquits % 4;
*(qca + byte) &= QCimasks[pos];
} // QuadCode::MakeParent
QuadCode &QuadCode::operator= (QuadCode &qc)
// Assign one quadcode the same value as another.
// The target quadcode is assumed to be initialized.
// qc is the quadcode to copy
{
#ifdef STAT_QC
memcpy (qca, qc.qca, NBYTE_QC);
#else
FreeMem();
size_t nbytes = QC_NBYTES (qc.nquits);
qca = new BYTE [nbytes];
assert (qca != NULL);
memcpy (qca, qc.qca, nbytes);
#endif // STAT_QC
nquits = qc.nquits;
return (*this);
} // QuadCode::operator=
ostream &operator<< (ostream &stream, QuadCode &qc)
// Overload "Put to" operator for output to stream.
// stream is the stream to print to
// qc is the quadcode to print
{
int quit;
for (quit = 0; quit < qc.nquits; quit++)
stream << (char)(qc.GetQuit (quit) + '0');
return (stream);
} // operator<<
istream &operator>> (istream &stream, QuadCode &qc)
// Overload "Get From" operator for input from stream.
// stream is the stream to get from
// qc is the quadcode to store the result in
{
char tmp[80];
qc.FreeMem();
stream >> tmp;
qc.Init (tmp);
return (stream);
} // operator>>
// End of File