#include "Tree.h"

#define SET_LONG(data, index, value) data[index + 0] = (unsigned char)(value >> 24); \
                                     data[index + 1] = (unsigned char)(value >> 16); \
                                     data[index + 2] = (unsigned char)(value >> 8); \
                                     data[index + 3] = (unsigned char)(value)
#define GET_LONG(data, index) ((data[index] << 24) | \
                               (data[index + 1] << 16) | \
                               (data[index + 2] << 16) | \
                                data[index + 3])

/*
Constructor that initializes point values 
*/
TREE::Shape::Area::
Area(TREE::Shape::Area * p_ptrParent,
     const MATH::D2::Point * p_ptrPoints,
     const unsigned int p_uintPoints)
{
    m_chrPolar = 0;
    m_ulngDepth = 0;
    m_ulngChildren = 0;
    m_ptrChildren = NULL;
    m_ptrParent = p_ptrParent;
    m_ulngPoints = p_uintPoints;

    unsigned int i;
    double dblAverage = 0.0;
    m_ptrPoints = new MATH::D2::Point[p_uintPoints + 1];
    m_stuCorners[0] = m_stuCorners[1] = m_ptrPoints[0].m_fltX = MATH::D2::BoxW::WrapValue(p_ptrPoints->m_fltX);
    m_stuCorners[2] = m_stuCorners[3] = m_ptrPoints[0].m_fltY = p_ptrPoints->m_fltY;
    for (i=1; i<=p_uintPoints; i++)
    {
        m_ptrPoints[i].m_fltX = MATH::D2::BoxW::WrapValue(p_ptrPoints[i].m_fltX);
        m_ptrPoints[i].m_fltY = p_ptrPoints[i].m_fltY;
        if ( m_ptrPoints[i].m_fltX < m_ptrPoints[i - 1].m_fltX )
        {
            float fltDifferenceWrap = (m_ptrPoints[i].m_fltX - MATH::D2::BoxW::m_stuWrap[0]) + (MATH::D2::BoxW::m_stuWrap[1] - m_ptrPoints[i - 1].m_fltX);
            float fltDifferenceNoWrap = m_ptrPoints[i - 1].m_fltX - m_ptrPoints[i].m_fltX;
            if ( fltDifferenceWrap < fltDifferenceNoWrap )
            {
                m_ptrPoints[i].m_fltX += MATH::D2::BoxW::m_fltWrapDistances[0];
                if ( m_stuCorners[1] < m_ptrPoints[i].m_fltX )
                    m_stuCorners[1] = m_ptrPoints[i].m_fltX;
            }
            else if ( m_stuCorners[0] > m_ptrPoints[i].m_fltX )
                m_stuCorners[0] = m_ptrPoints[i].m_fltX;
        }
        else
        {
            float fltDifferenceWrap = (m_ptrPoints[i - 1].m_fltX - MATH::D2::BoxW::m_stuWrap[0]) + (MATH::D2::BoxW::m_stuWrap[1] - m_ptrPoints[i].m_fltX);
            float fltDifferenceNoWrap = m_ptrPoints[i].m_fltX - m_ptrPoints[i - 1].m_fltX;
            if ( fltDifferenceWrap < fltDifferenceNoWrap )
            {
                m_ptrPoints[i].m_fltX -= MATH::D2::BoxW::m_fltWrapDistances[0];
                if ( m_stuCorners[0] > m_ptrPoints[i].m_fltX )
                    m_stuCorners[0] = m_ptrPoints[i].m_fltX;
            }
            else if ( m_stuCorners[1] < m_ptrPoints[i].m_fltX )
                m_stuCorners[1] = m_ptrPoints[i].m_fltX;
        }

        dblAverage += m_ptrPoints[i].m_fltY;
        if ( m_ptrPoints[i].m_fltY < m_stuCorners[2] )
            m_stuCorners[2] = m_ptrPoints[i].m_fltY;
        else if ( m_ptrPoints[i].m_fltY > m_stuCorners[3] )
            m_stuCorners[3] = m_ptrPoints[i].m_fltY;
    }

    if ( (m_ptrPoints[0].m_fltX < m_ptrPoints[p_uintPoints].m_fltX && MATH::Equal(m_ptrPoints[0].m_fltX + MATH::D2::BoxW::m_fltWrapDistances[0], m_ptrPoints[p_uintPoints].m_fltX)) ||
         (m_ptrPoints[0].m_fltX >= m_ptrPoints[p_uintPoints].m_fltX && MATH::Equal(m_ptrPoints[p_uintPoints].m_fltX + MATH::D2::BoxW::m_fltWrapDistances[0], m_ptrPoints[0].m_fltX)) )
    {
        m_chrPolar = (char)(( dblAverage >= (double)((MATH::D2::BoxW::m_stuWrap[3] + MATH::D2::BoxW::m_stuWrap[2]) * 0.5f) )
            ? 1
            : -1);
        m_stuCorners[0] = MATH::D2::BoxW::m_stuWrap[0];
        m_stuCorners[1] = MATH::D2::BoxW::m_stuWrap[1];
    }
    else
    {
        m_stuCorners[0] = MATH::D2::BoxW::WrapValue(m_stuCorners[0]);
        m_stuCorners[1] = MATH::D2::BoxW::WrapValue(m_stuCorners[1]);
        for (i=0; i<=p_uintPoints; i++)
        {
            while ( m_ptrPoints[i].m_fltX < m_stuCorners[0] )
                m_ptrPoints[i].m_fltX += MATH::D2::BoxW::m_fltWrapDistances[0];
        }
    }
}

TREE::Shape::Area::
~Area()
{
    delete [] m_ptrPoints;
    if ( m_ptrChildren )
        free(m_ptrChildren);
}

//
// Returns true if the area is oriented clockwise, false for counter-clockwise
//
bool
TREE::Shape::Area::
Clockwise(void) const
{
    float fltX = 0.0f;
    float fltLowestY = std::numeric_limits<float>::max();
    unsigned int uintIndex = (unsigned int)(-1);
    for (unsigned int i=0; i<m_ulngPoints; i++)
    {
        if ( m_ptrPoints[i].m_fltY < fltLowestY ||
            (m_ptrPoints[i].m_fltY == fltLowestY && m_ptrPoints[i].m_fltX > fltX) )
        {
            fltLowestY = m_ptrPoints[i].m_fltY;
            fltX = m_ptrPoints[i].m_fltX;
            uintIndex = i;
        }
    }

    float fltCrossProduct;
    if ( uintIndex )
    {
        fltCrossProduct = (m_ptrPoints[uintIndex].m_fltX - m_ptrPoints[uintIndex - 1].m_fltX) * (m_ptrPoints[uintIndex + 1].m_fltY - m_ptrPoints[uintIndex].m_fltY) -
                          (m_ptrPoints[uintIndex].m_fltY - m_ptrPoints[uintIndex - 1].m_fltY) * (m_ptrPoints[uintIndex + 1].m_fltX - m_ptrPoints[uintIndex].m_fltX);
    }
    else
    {
        fltCrossProduct = (m_ptrPoints[0].m_fltX - m_ptrPoints[m_ulngPoints - 1].m_fltX) * (m_ptrPoints[1].m_fltY - m_ptrPoints[0].m_fltY) -
                          (m_ptrPoints[0].m_fltY - m_ptrPoints[m_ulngPoints - 1].m_fltY) * (m_ptrPoints[1].m_fltX - m_ptrPoints[0].m_fltX);
    }


    if ( m_chrPolar >= 0 )
        return ( fltCrossProduct < 0.0f );
    else
        return ( fltCrossProduct >= 0.0f );
}

bool
TREE::Shape::Area::
Hit(const MATH::D2::Point & p_stuPoint) const
{
    float fltPoint = p_stuPoint.m_fltX;
    if ( fltPoint < m_stuCorners[0] )
        fltPoint += MATH::D2::BoxW::m_fltWrapDistances[0];

    bool blnInside = false;
    for (unsigned int i=0; i<m_ulngPoints; i++)
    {
        //
        // There is no crossing if the point is either above or below the line, or the line is horizontal
        //
        if ( (((p_stuPoint.m_fltY >= m_ptrPoints[i].m_fltY) && (p_stuPoint.m_fltY < m_ptrPoints[i + 1].m_fltY)) ||
              ((p_stuPoint.m_fltY >= m_ptrPoints[i + 1].m_fltY) && (p_stuPoint.m_fltY < m_ptrPoints[i].m_fltY))) &&
             (fltPoint < ((((m_ptrPoints[i + 1].m_fltX - m_ptrPoints[i].m_fltX) * (p_stuPoint.m_fltY - m_ptrPoints[i].m_fltY)) / (m_ptrPoints[i + 1].m_fltY - m_ptrPoints[i].m_fltY)) + m_ptrPoints[i].m_fltX)) )
        {
            blnInside = !blnInside;
        }
    }

    return blnInside;
}

void
TREE::Shape::Area::
Orient(const bool p_blnClockwise)
{
    if ( p_blnClockwise == Clockwise() )
        return;

    unsigned int uintStart = 0;
    unsigned int uintEnd = m_ulngPoints - 1;
    while ( uintStart < uintEnd )
    {
        MATH::D2::Point stuTemp = m_ptrPoints[uintStart];
        m_ptrPoints[uintStart] = m_ptrPoints[uintEnd];
        m_ptrPoints[uintEnd] = stuTemp;
        uintStart++;
        uintEnd--;
    }

    m_ptrPoints[m_ulngPoints] = m_ptrPoints[0];
}

TREE::Shape::Node::
Node(const MATH::D2::BoxW & p_stuCorners)
    : m_ulngAreas(0),
      m_ulngLowestDepth(0),
      m_ulngContainmentIndex(0),
      m_blnContainsRootAreas(false),
      m_stuCorners(p_stuCorners)
{
    m_ptrChildren[0] = m_ptrChildren[1] = m_ptrChildren[2] = m_ptrChildren[3] = NULL;
    m_ptrAreas = (TREE::Shape::Area **)(malloc(TREE_MAX_POINTS_PER_NODE * sizeof(TREE::Shape::Area *)));
}

TREE::Shape::Node::
~Node()
{
    unsigned int i;
    for (i=0; i<4; i++)
        delete m_ptrChildren[i];

    for (i=0; i<m_ulngAreas; i++)
        delete m_ptrAreas[i];
    free(m_ptrAreas);
}

unsigned long
TREE::Shape::Node::
Depth(void) const
{
    unsigned long ulngDepth = 0;
    for (unsigned char i=0; i<4; i++)
    {
        if ( m_ptrChildren[i] )
        {
            unsigned long ulngTemp = m_ptrChildren[i]->Depth();
            if ( ulngDepth < ulngTemp )
                ulngDepth = ulngTemp;
        }
    }

    return ulngDepth + 1;
}

unsigned int
TREE::Shape::Node::
Find(const MATH::D2::BoxW & p_stuCorners,
     const bool p_blnFindOnlyParents,
     const TREE::Shape::Area ** p_ptrAreaList,
     const unsigned int p_uintAreaListLength) const
{
    unsigned int i;
    unsigned int uintAreas = 0;

    for (i=0; i<4; i++)
    {
        if ( m_ptrChildren[i] &&
             (p_blnFindOnlyParents == false || m_ptrChildren[i]->m_blnContainsRootAreas) &&
             p_stuCorners.Intersect(m_ptrChildren[i]->m_stuCorners) )
        {
            uintAreas += m_ptrChildren[i]->Find(p_stuCorners,
                                                p_blnFindOnlyParents,
                                                ( uintAreas < p_uintAreaListLength ) ? p_ptrAreaList + uintAreas : NULL,
                                                ( uintAreas < p_uintAreaListLength ) ? p_uintAreaListLength - uintAreas : 0);
        }
    }

    for (i=0; i<m_ulngAreas; i++)
    {
        if ( (p_blnFindOnlyParents == false || m_ptrAreas[i]->m_ptrParent == NULL) &&
             p_stuCorners.Intersect(m_ptrAreas[i]->m_stuCorners) )
        {
            if ( uintAreas < p_uintAreaListLength )
                p_ptrAreaList[uintAreas] = m_ptrAreas[i];
            uintAreas++;
        }
    }

    return uintAreas;
}

bool
TREE::Shape::Node::
FindArea(const TREE::Shape::Area * p_ptrArea,
         const TREE::Shape::Node ** p_ptrParents,
         const unsigned long p_ulngParents,
         unsigned long * p_ptrIndices) const
{
    for (unsigned long i=p_ulngParents; i<=p_ulngParents; i--)
    {
        for (unsigned long j=0; j<p_ptrParents[i]->m_ulngAreas; j++)
        {
            if ( p_ptrParents[i]->m_ptrAreas[j] == p_ptrArea )
            {
                p_ptrIndices[0] = p_ulngParents - i;
                p_ptrIndices[1] = j;
                return true;
            }
        }
    }

    return false;
}

TREE::Shape::Area *
TREE::Shape::Node::
Hit(const MATH::D2::Point & p_stuPoint) const
{
    unsigned int i;

    for (i=0; i<4; i++)
    {
        if ( m_ptrChildren[i] &&
             m_ptrChildren[i]->m_stuCorners.Intersect(p_stuPoint) )
        {
            TREE::Shape::Area * ptrArea = m_ptrChildren[i]->Hit(p_stuPoint);
            if ( ptrArea )
                return ptrArea;
        }
    }

    for (i=m_ulngLowestDepth; i<=m_ulngLowestDepth; i--)
    {
        for (unsigned int j=0; j<m_ulngAreas; j++)
        {
            if ( i == m_ptrAreas[j]->m_ulngDepth &&
                 m_ptrAreas[j]->m_stuCorners.Intersect(p_stuPoint) )
            {
                if ( m_ptrAreas[j]->Hit(p_stuPoint) )
                    return m_ptrAreas[j];
            }
        }
    }

    return NULL;
}

unsigned long
TREE::Shape::Node::
Memory(void) const
{
    unsigned long ulngSize = sizeof(TREE::Shape::Node) +
                             (m_ulngAreas * sizeof(TREE::Shape::Area *));

    unsigned long i;
    for (i=0; i<m_ulngAreas; i++)
    {
        ulngSize += sizeof(TREE::Shape::Area) +
                    (m_ptrAreas[i]->m_ulngChildren * sizeof(TREE::Shape::Area *)) +
                    ((m_ptrAreas[i]->m_ulngPoints + 1) * sizeof(MATH::D2::Point));
    }

    for (i=0; i<4; i++)
    {
        if ( m_ptrChildren[i] )
            ulngSize += m_ptrChildren[i]->Memory();
    }

    return ulngSize;
}

bool
TREE::Shape::Node::
Retrieve(std::istream & p_clsIn,
         std::vector<char> & p_clsBuffer,
         unsigned char * p_ptrData,
         const TREE::Shape::Node ** p_ptrParents,
         const unsigned long p_ulngParents,
         const MATH::D2::BoxW * p_ptrCorners,
         bool p_blnEnclosed)
{
    m_ulngLowestDepth = GET_LONG(p_ptrData, 0);
    m_ulngContainmentIndex = GET_LONG(p_ptrData, 4);
    m_ulngAreas = GET_LONG(p_ptrData, 8);
    m_blnContainsRootAreas = ( p_ptrData[13] != 0 );
    char chrChildren = (char)(p_ptrData[14]);

    //
    // Read and process the areas
    //
    unsigned long i;
    p_ptrParents[p_ulngParents] = this;
    MATH::D2::BoxW stuCorners(0.0f, 0.0f, 0.0f, 0.0f);
    m_ptrAreas = (TREE::Shape::Area **)(malloc((( m_ulngAreas < TREE_MAX_POINTS_PER_NODE ) ? TREE_MAX_POINTS_PER_NODE : m_ulngAreas) * sizeof(TREE::Shape::Area *)));
    for (i=0; i<m_ulngAreas; i++)
    {
        p_clsIn.read((char *)(p_ptrData), 38);
        if ( p_clsIn.fail() )
            return false;

        //
        // Skip this area if it's parent was skipped, or if it's not inside the retrieval zone
        //
        unsigned long ulngIndexParent = GET_LONG(p_ptrData, 0);
        unsigned long ulngIndexArea   = GET_LONG(p_ptrData, 4);
        unsigned long ulngPoints      = GET_LONG(p_ptrData, 8);
        TREE::Shape::ConvertFloat(&(stuCorners.m_fltValues[0]), p_ptrData + 22, 4);

        TREE::Shape::Area * ptrParent;
        if ( ulngIndexParent != (unsigned long)(-1) || ulngIndexArea != (unsigned long)(-1) )
        {
            if ( ulngIndexParent > p_ulngParents ||
                 ulngIndexArea > p_ptrParents[p_ulngParents - ulngIndexParent]->m_ulngAreas )
            {
                return false;
            }

            ptrParent = p_ptrParents[p_ulngParents - ulngIndexParent]->m_ptrAreas[ulngIndexArea];
            if ( ptrParent == NULL || (p_ptrCorners != NULL && stuCorners.Intersect(*p_ptrCorners) == 0) )
            {
                p_clsIn.seekg(ulngPoints * 8, std::ios_base::cur);
                if ( p_clsIn.fail() )
                    return false;
                m_ptrAreas[i] = NULL;
                continue;
            }
        }
        else
        {
            m_blnContainsRootAreas = true;
            ptrParent = NULL;
        }

        m_ptrAreas[i] = new Area;
        m_ptrAreas[i]->m_ptrParent = ptrParent;
        if ( ptrParent )
        {
            unsigned long j;
            for (j=0; j<ptrParent->m_ulngChildren; j++)
            {
                if ( ptrParent->m_ptrChildren[j] == NULL )
                {
                    ptrParent->m_ptrChildren[j] = m_ptrAreas[i];
                    break;
                }
            }

            if ( j >= ptrParent->m_ulngChildren )
                return false;
        }

        //
        // Read and set Area properties
        //
        m_ptrAreas[i]->m_ulngPoints     = ulngPoints;
        m_ptrAreas[i]->m_ulngChildren   = GET_LONG(p_ptrData, 12);
        m_ptrAreas[i]->m_ulngDepth      = GET_LONG(p_ptrData, 16);
        m_ptrAreas[i]->m_chrPolar       = (char)(p_ptrData[20]);
        m_ptrAreas[i]->m_chrContainment = (char)(p_ptrData[21]);
        m_ptrAreas[i]->m_stuCorners     = stuCorners;
        m_ptrAreas[i]->m_ptrChildren    = ( m_ptrAreas[i]->m_ulngChildren > 0 ) ? new TREE::Shape::Area *[m_ptrAreas[i]->m_ulngChildren] : NULL;
        memset(m_ptrAreas[i]->m_ptrChildren, 0, m_ptrAreas[i]->m_ulngChildren * sizeof(Area *));

        //
        // Read the Area points
        //
        p_clsBuffer.reserve(ulngPoints * 8);
        p_clsIn.read(&(p_clsBuffer[0]), ulngPoints * 8);
        if ( p_clsIn.fail() )
            return false;
        m_ptrAreas[i]->m_ptrPoints = new MATH::D2::Point[ulngPoints + 1];
        TREE::Shape::ConvertFloat((float *)(m_ptrAreas[i]->m_ptrPoints),
                                  &(p_clsBuffer[0]),
                                  ulngPoints * 2);
        m_ptrAreas[i]->m_ptrPoints[m_ptrAreas[i]->m_ulngPoints] = m_ptrAreas[i]->m_ptrPoints[0];
    }

    //
    // Read the children
    //
    MATH::D2::BoxW stuBox;
    for (unsigned char m=0; m<4; m++)
    {
        if ( chrChildren & (1 << m) )
        {
            p_clsIn.read((char *)(p_ptrData), 18);
            if ( p_clsIn.fail() )
                return false;

            stuBox = m_stuCorners.Sector(m);
            int intIntersection = ( p_blnEnclosed == false )
                ? p_ptrCorners->Intersect(stuBox)
                : 3;

            if ( intIntersection )
            {
                m_ptrChildren[m] = new TREE::Shape::Node(stuBox);
                if ( m_ptrChildren[m]->Retrieve(p_clsIn,
                                                p_clsBuffer,
                                                p_ptrData,
                                                p_ptrParents,
                                                p_ulngParents + 1,
                                                p_ptrCorners,
                                                ( intIntersection == 3 || intIntersection == 5)) == false )
                {
                    return false;
                }
            }
            else
            {
                unsigned long ulngSize = GET_LONG(p_ptrData, 0);
                p_clsIn.seekg(ulngSize - 18, std::ios_base::cur);
                if ( p_clsIn.fail() )
                    return false;
            }
        }
    }

    unsigned long j;
    for (i=j=0; i<m_ulngAreas; i++)
    {
        if ( m_ptrAreas[i] == NULL )
            continue;

        unsigned long k, l;
        for (k=l=0; k<m_ptrAreas[i]->m_ulngChildren; k++)
        {
            if ( m_ptrAreas[i]->m_ptrChildren[k] )
                m_ptrAreas[i]->m_ptrChildren[l++] = m_ptrAreas[i]->m_ptrChildren[k];
        }

        if ( l < m_ptrAreas[i]->m_ulngChildren )
        {
            m_ptrAreas[i]->m_ptrChildren = (TREE::Shape::Area **)(realloc(m_ptrAreas[i]->m_ptrChildren, l * sizeof(TREE::Shape::Area *)));
            m_ptrAreas[i]->m_ulngChildren = l;
        }

        m_ptrAreas[j++] = m_ptrAreas[i];
    }

    if ( j < m_ulngAreas )
    {
        m_ptrAreas = (TREE::Shape::Area **)(realloc(m_ptrAreas, j * sizeof(TREE::Shape::Area *)));
        m_ulngAreas = j;
    }

    return true;
}

unsigned long
TREE::Shape::Node::
Size(void) const
{
    unsigned long ulngSize = 4 + // size (value we are calculating now)
                             4 + // m_ulngLowestDepth
                             4 + // m_ulngContainmentIndex
                             4 + // m_ulngAreas
                             //sizeof(UTIL::D2::Box) + // m_stuCorners
                             1 +          // m_blnContainsRootAreas
                             1;           // child flags

    unsigned long i;
    for (i=0; i<m_ulngAreas; i++)
    {
        ulngSize += 8 +                                // parent node displacement, parent area displacement
                    4 +                                // m_ulngPoints
                    4 +                                // m_ulngChildren
                    4 +                                // m_ulngDepth
                    1 +                                // m_chrPolar
                    1 +                                // m_chrContainment
                    16 +                               // m_stuCorners
                    (m_ptrAreas[i]->m_ulngPoints * 8); // m_ptrPoints
    }

    for (i=0; i<4; i++)
    {
        if ( m_ptrChildren[i] )
            ulngSize += m_ptrChildren[i]->Size();
    }

    return ulngSize;
}

bool
TREE::Shape::Node::
Store(std::ostream & p_clsOut,
      std::vector<char> & p_clsBuffer,
      unsigned char * p_ptrBuffer,
      const TREE::Shape::Node ** p_ptrParents,
      const unsigned long p_ulngParents) const
{
    unsigned long ulngSize = Size();
    unsigned char uchrData[38];
    SET_LONG(p_ptrBuffer, 0, ulngSize);
    SET_LONG(p_ptrBuffer, 4, m_ulngLowestDepth);
    SET_LONG(p_ptrBuffer, 8, m_ulngContainmentIndex);
    SET_LONG(p_ptrBuffer, 12, m_ulngAreas);
    p_ptrBuffer[16] = ( m_blnContainsRootAreas ) ? 1 : 0;
    p_ptrBuffer[17] = (unsigned char)((( m_ptrChildren[0] ) ? 0x1 : 0) |
                                      (( m_ptrChildren[1] ) ? 0x2 : 0) |
                                      (( m_ptrChildren[2] ) ? 0x4 : 0) |
                                      (( m_ptrChildren[3] ) ? 0x8 : 0));
    p_clsOut.write((const char *)(p_ptrBuffer), 18);
    if ( p_clsOut.fail() )
        return false;

    unsigned long i;
    p_ptrParents[p_ulngParents] = this;
    for (i=0; i<m_ulngAreas; i++)
    {
        unsigned long ulngParentIndices[2];
        if ( m_ptrAreas[i]->m_ptrParent != NULL )
        {
            if ( FindArea(m_ptrAreas[i]->m_ptrParent,
                          p_ptrParents,
                          p_ulngParents,
                          &(ulngParentIndices[0])) == false )
            {
                return false;
            }
        }
        else
            ulngParentIndices[0] = ulngParentIndices[1] = (unsigned long)(-1);

        p_clsBuffer.reserve(m_ptrAreas[i]->m_ulngPoints * 8);
        SET_LONG(p_ptrBuffer, 0, ulngParentIndices[0]);
        SET_LONG(p_ptrBuffer, 4, ulngParentIndices[1]);
        SET_LONG(p_ptrBuffer, 8, m_ptrAreas[i]->m_ulngPoints);
        SET_LONG(p_ptrBuffer, 12, m_ptrAreas[i]->m_ulngChildren);
        SET_LONG(p_ptrBuffer, 16, m_ptrAreas[i]->m_ulngDepth);
        uchrData[20] = (unsigned char)(m_ptrAreas[i]->m_chrPolar);
        uchrData[21] = (unsigned char)(m_ptrAreas[i]->m_chrContainment);
        TREE::Shape::ConvertFloat(&(p_ptrBuffer[22]), m_ptrAreas[i]->m_stuCorners.m_fltValues, 4);
        TREE::Shape::ConvertFloat(&(p_clsBuffer[0]), (float *)(m_ptrAreas[i]->m_ptrPoints), m_ptrAreas[i]->m_ulngPoints);
        p_clsOut.write((const char *)(p_ptrBuffer), 38);
        p_clsOut.write((const char *)(&(p_clsBuffer[0])), m_ptrAreas[i]->m_ulngPoints * 8);
        if ( p_clsOut.fail() )
            return false;
    }

    for (i=0; i<4; i++)
    {
        if ( m_ptrChildren[i] &&
             m_ptrChildren[i]->Store(p_clsOut,
                                     p_clsBuffer,
                                     p_ptrBuffer,
                                     p_ptrParents,
                                     p_ulngParents + 1) == false )
        {
            return false;
        }
    }

    return true;
}

void
TREE::Shape::Node::
Contain(const unsigned long p_ulngIndex) 
{
    TREE::Shape::Area * ptrArea = m_ptrAreas[p_ulngIndex];
    for (unsigned long i=p_ulngIndex; i>m_ulngContainmentIndex; i--)
    {
        m_ptrAreas[i] = m_ptrAreas[i - 1];
        if ( m_ptrAreas[i] == ptrArea->m_ptrParent )
            Contain(i++);
    }
    m_ptrAreas[m_ulngContainmentIndex++] = ptrArea;
}

void
TREE::Shape::Node::
Insert(TREE::Shape::Area * p_ptrArea)
{
    int intIntersection;

    if ( p_ptrArea->m_ptrParent == NULL )
        m_blnContainsRootAreas = true;

    //
    // Before we try to insert the area into this node or child nodes, see
    // if any current area in this node has the new area as parent
    //
    unsigned long i;
    for (i=0; i<m_ulngAreas; i++)
    {
        if ( m_ptrAreas[i]->m_ptrParent == p_ptrArea )
        {
            TREE::Shape::Area * ptrTemp = m_ptrAreas[i];
            m_ptrAreas[i] = p_ptrArea;
            p_ptrArea = ptrTemp;
        }
    }

    if ( m_ulngAreas < TREE_MAX_POINTS_PER_NODE )
    {
        m_ptrAreas[m_ulngAreas++] = p_ptrArea;
        if ( m_ulngLowestDepth < p_ptrArea->m_ulngDepth )
            m_ulngLowestDepth = p_ptrArea->m_ulngDepth;
        return;
    }

    //
    // This node is full... see if any children can accept the new area
    //
    unsigned char j;
    for (j=0; j<4; j++)
    {
        if ( m_ptrChildren[j] )
        {
            intIntersection = p_ptrArea->m_stuCorners.Intersect(m_ptrChildren[j]->m_stuCorners);
            if ( intIntersection == 4 || intIntersection == 5 )
            {
                m_ptrChildren[j]->Insert(p_ptrArea);
                return;
            }
        }
        else
        {
            MATH::D2::BoxW stuBox = m_stuCorners.Sector(j);
            intIntersection = p_ptrArea->m_stuCorners.Intersect(stuBox);
            if ( intIntersection == 4 || intIntersection == 5 )
            {
                m_ptrChildren[j] = new TREE::Shape::Node(stuBox);
                m_ptrChildren[j]->m_ptrAreas[0] = p_ptrArea;
                return;
            }
        }
    }

    //
    // No children can accept the new area; see if we can put current
    // areas into children to make room in this node for the new area
    //
    unsigned long ulngIndex = m_ulngAreas - 1;
    while ( m_ulngContainmentIndex < m_ulngAreas )
    {
        for (j=0; j<4; j++)
        {
            if ( m_ptrChildren[j] )
            {
                intIntersection = m_ptrAreas[ulngIndex]->m_stuCorners.Intersect(m_ptrChildren[j]->m_stuCorners);
                if ( intIntersection == 4 || intIntersection == 5 )
                    break;
            }
            else
            {
                MATH::D2::BoxW stuBox = m_stuCorners.Sector(j);
                intIntersection = m_ptrAreas[ulngIndex]->m_stuCorners.Intersect(stuBox);
                if ( intIntersection == 4 || intIntersection == 5 )
                {
                    m_ptrChildren[j] = new TREE::Shape::Node(stuBox);
                    break;
                }
            }
        }

        if ( j < 4 )
        {
            m_ptrChildren[j]->Insert(m_ptrAreas[ulngIndex]);
            m_ptrAreas[ulngIndex] = p_ptrArea;
            m_ulngLowestDepth = 0;
            for (i=0; i<m_ulngAreas; i++)
            {
                if ( m_ulngLowestDepth < m_ptrAreas[i]->m_ulngDepth )
                    m_ulngLowestDepth = m_ptrAreas[i]->m_ulngDepth;
            }
            return;
        }

        //
        // The area cannot fit into any children, so move it to the contained portion of the array
        //
        Contain(ulngIndex);
    }

    //
    // No children can accept the new area... simply add it to this node
    //
    m_ptrAreas = (TREE::Shape::Area **)(realloc(m_ptrAreas, (m_ulngAreas + 1) * sizeof(TREE::Shape::Area *)));
    m_ulngContainmentIndex = m_ulngAreas + 1;
}

//int intDebug = 0;

bool
TREE::Shape::
InsertGshhs(std::istream & p_clsIn,
            const MATH::D2::BoxW * p_ptrCorners)
{
    #define BIG_ENDIAN(data, index) ((data[(index) + 0] << 24) + (data[(index) + 1] << 16) + (data[(index) + 2] << 8) + data[(index) + 3])

    struct Gshhs
    {
        union
        {
            struct
            {
                int   intId;
                int   intPoints;
                int   intLevel;
                int   intFrame[4];
                int   intArea;
                int   intVersion;
            };
            int intValues[9];
        };
        short shtGreenwich;
        short shtSource;
    };

    unsigned char uchrData[40];
    unsigned char * ptrBuffer = NULL;
    MATH::D2::Point * ptrPoints = NULL;
    unsigned int uintPointsAllocated = 0;
    p_clsIn.read((char *)(&(uchrData[0])), 40);
    while ( p_clsIn.good() )
    {
        Gshhs stuTemp;
        for (unsigned int i=0; i<9; i++)
            stuTemp.intValues[i] = BIG_ENDIAN(uchrData, 4 * i);
        stuTemp.shtGreenwich = (uchrData[36] << 8) + uchrData[37];
        stuTemp.shtSource = (uchrData[38] << 8) + uchrData[39];

        if ( p_ptrCorners )
        {
            MATH::D2::BoxW stuBox(0.000001f * (float)(stuTemp.intFrame[0]),
                                  0.000001f * (float)(stuTemp.intFrame[1]),
                                  0.000001f * (float)(stuTemp.intFrame[2]),
                                  0.000001f * (float)(stuTemp.intFrame[3]));
            stuBox.Adjust();
            if ( p_ptrCorners->Intersect(stuBox) == 0 )
            {
                p_clsIn.seekg(8 * stuTemp.intPoints, std::ios_base::cur);
                continue;
            }
        }

        if ( uintPointsAllocated < (unsigned int)(stuTemp.intPoints) )
        {
            ptrBuffer = (unsigned char *)realloc(ptrBuffer, 8 * stuTemp.intPoints);
            ptrPoints = (MATH::D2::Point *)realloc(ptrPoints, stuTemp.intPoints * sizeof(MATH::D2::Point));
            uintPointsAllocated = (unsigned int)(stuTemp.intPoints);
        }

        p_clsIn.read((char *)(ptrBuffer), 8 * stuTemp.intPoints);
        if ( p_clsIn.fail() )
        {
            free(ptrPoints);
            return false;
        }

        for (unsigned int i=0; i<(unsigned int)(stuTemp.intPoints); i++)
        {
            ptrPoints[i].m_fltX = 0.000001f * (float)(BIG_ENDIAN(ptrBuffer, i * 8));
            ptrPoints[i].m_fltY = 0.000001f * (float)(BIG_ENDIAN(ptrBuffer, (i * 8) + 4));
        }

        TREE::Shape::Area * ptrParent = m_stuRoot.Hit(ptrPoints[0]);
        TREE::Shape::Area * ptrArea = new TREE::Shape::Area(ptrParent,
                                                            ptrPoints,
                                                            (const unsigned int)(stuTemp.intPoints - 1));
        if ( ptrParent != NULL )
        {
            ptrParent->m_ptrChildren = (TREE::Shape::Area **)realloc(ptrParent->m_ptrChildren, (ptrParent->m_ulngChildren + 1) * sizeof(TREE::Shape::Area *));
            ptrParent->m_ptrChildren[ptrParent->m_ulngChildren++] = ptrArea;

            do
            {
                ptrArea->m_ulngDepth++;
                ptrParent = ptrParent->m_ptrParent;
            } while ( ptrParent );
        }

        ptrArea->Orient(false);
        m_stuRoot.Insert(ptrArea);
        p_clsIn.read((char *)(&(uchrData[0])), 40);
    }

    if ( ptrBuffer )
        free(ptrBuffer);
    if ( ptrPoints )
        free(ptrPoints);

    return true;
}

bool
TREE::Shape::
Retrieve(std::istream & p_clsIn,
         const MATH::D2::BoxW * p_ptrCorners)
{
    unsigned char uchrData[38];
    p_clsIn.read((char *)(&(uchrData[0])), 20);
    if ( p_clsIn.fail() )
        return false;

    unsigned long ulngDepth = GET_LONG(uchrData, 0);
    TREE::Shape::ConvertFloat(&(m_stuRoot.m_stuCorners.m_fltValues[0]), &(uchrData[4]), 4);
    const TREE::Shape::Node ** ptrNodes = new const TREE::Shape::Node *[ulngDepth];
    p_clsIn.read((char *)(&(uchrData[0])), 18);
    if ( p_clsIn.fail() )
        return false;

    std::vector<char> clsBuffer;
    bool blnReturn = m_stuRoot.Retrieve(p_clsIn,
                                        clsBuffer,
                                        &(uchrData[0]),
                                        ptrNodes,
                                        0,
                                        p_ptrCorners,
                                        ( p_ptrCorners == NULL));
    delete [] ptrNodes;
    return blnReturn;
}

bool
TREE::Shape::
Store(std::ostream & p_clsOut) const
{
    unsigned char uchrData[20];
    unsigned long ulngDepth = m_stuRoot.Depth();
    SET_LONG(uchrData, 0, ulngDepth);
    TREE::Shape::ConvertFloat(&(uchrData[4]), m_stuRoot.m_stuCorners.m_fltValues, 4);
    p_clsOut.write((char *)(&(uchrData[0])), 20);
    if ( p_clsOut.fail() )
        return false;

    const TREE::Shape::Node ** ptrNodes = new const TREE::Shape::Node *[ulngDepth];

    std::vector<char> clsBuffer;
    bool blnReturn = m_stuRoot.Store(p_clsOut,
                                     clsBuffer,
                                     &(uchrData[0]),
                                     ptrNodes,
                                     0);
    delete [] ptrNodes;
    return blnReturn;
}