mitab_mapindexblock.cpp

用于读取TAB、MIF、SHP文件的类

/**********************************************************************
 *                   TABMAPIndexBlock::GetNumFreeEntries()
 *
 * Return the number of available entries in this block.
 *
 * __TODO__ This function could eventually be improved to search
 *          children leaves as well.
 **********************************************************************/
int     TABMAPIndexBlock::GetNumFreeEntries()
{
    /* nMaxEntries = (m_nBlockSize-4)/20;*/

    return (TAB_MAX_ENTRIES_INDEX_BLOCK - m_numEntries);
}

/**********************************************************************
 *                   TABMAPIndexBlock::GetEntry()
 *
 * Fetch a reference to the requested entry.
 *
 * @param iIndex index of entry, must be from 0 to GetNumEntries()-1. 
 *
 * @return a reference to the internal copy of the entry, or NULL if out
 * of range. 
 **********************************************************************/
TABMAPIndexEntry *TABMAPIndexBlock::GetEntry( int iIndex )
{
    if( iIndex < 0 || iIndex >= m_numEntries )
        return NULL;

    return m_asEntries + iIndex;
}

/**********************************************************************
 *                   TABMAPIndexBlock::GetCurMaxDepth()
 *
 * Return maximum depth in the currently loaded part of the index tree
 **********************************************************************/
int     TABMAPIndexBlock::GetCurMaxDepth()
{
    if (m_poCurChild)
        return m_poCurChild->GetCurMaxDepth() + 1;

    return 1;  /* No current child... this node counts for one. */
}

/**********************************************************************
 *                   TABMAPIndexBlock::GetMBR()
 *
 * Return the MBR for the current block.
 **********************************************************************/
void TABMAPIndexBlock::GetMBR(GInt32 &nXMin, GInt32 &nYMin, 
                                     GInt32 &nXMax, GInt32 &nYMax)
{
    nXMin = m_nMinX;
    nYMin = m_nMinY;
    nXMax = m_nMaxX;
    nYMax = m_nMaxY; 
}

/**********************************************************************
 *                   TABMAPIndexBlock::InsertEntry()
 *
 * Add a new entry to this index block.  It is assumed that there is at
 * least one free slot available, so if the block has to be split then it
 * should have been done prior to calling this function.
 *
 * Returns 0 on success, -1 on error.
 **********************************************************************/
int     TABMAPIndexBlock::InsertEntry(GInt32 nXMin, GInt32 nYMin,
                                      GInt32 nXMax, GInt32 nYMax,
                                      GInt32 nBlockPtr)
{
    if (m_eAccess != TABWrite && m_eAccess != TABReadWrite)
    {
        CPLError(CE_Failure, CPLE_AssertionFailed,
               "Failed adding index entry: File not opened for write access.");
        return -1;
    }

    if (GetNumFreeEntries() < 1)
    {
        CPLError(CE_Failure, CPLE_AssertionFailed,
                 "Current Block Index is full, cannot add new entry.");
        return -1;
    }

    /*-----------------------------------------------------------------
     * Update count of entries and store new entry.
     *----------------------------------------------------------------*/
    m_numEntries++;
    CPLAssert(m_numEntries <= TAB_MAX_ENTRIES_INDEX_BLOCK);

    m_asEntries[m_numEntries-1].XMin = nXMin;
    m_asEntries[m_numEntries-1].YMin = nYMin;
    m_asEntries[m_numEntries-1].XMax = nXMax;
    m_asEntries[m_numEntries-1].YMax = nYMax;
    m_asEntries[m_numEntries-1].nBlockPtr = nBlockPtr;

    return 0;
}

/**********************************************************************
 *                   TABMAPIndexBlock::AddEntry()
 *
 * Recursively search the tree until we encounter the best leaf to
 * contain the specified object MBR and add the new entry to it.
 *
 * In the even that the selected leaf node would be full, then it will be
 * split and this split can propagate up to its parent, etc.
 *
 * If bAddInThisNodeOnly=TRUE, then the entry is added only locally and
 * we do not try to update the child node.  This is used when the parent 
 * of a node that is being splitted has to be updated.
 *
 * Returns 0 on success, -1 on error.
 **********************************************************************/
int     TABMAPIndexBlock::AddEntry(GInt32 nXMin, GInt32 nYMin,
                                   GInt32 nXMax, GInt32 nYMax,
                                   GInt32 nBlockPtr,
                                   GBool bAddInThisNodeOnly /*=FALSE*/)
{
    int i;
    GBool bFound = FALSE;

    if (m_eAccess != TABWrite && m_eAccess != TABReadWrite)
    {
        CPLError(CE_Failure, CPLE_AssertionFailed,
               "Failed adding index entry: File not opened for write access.");
        return -1;
    }

    /*-----------------------------------------------------------------
     * Update MBR now... even if we're going to split current node later.
     *----------------------------------------------------------------*/
    if (nXMin < m_nMinX)
        m_nMinX = nXMin;
    if (nXMax > m_nMaxX)
        m_nMaxX = nXMax;
    
    if (nYMin < m_nMinY)
        m_nMinY = nYMin;
    if (nYMax > m_nMaxY)
        m_nMaxY = nYMax;

    /*-----------------------------------------------------------------
     * Look for the best candidate to contain the new entry
     * __TODO__ For now we'll just look for the first entry that can 
     *          contain the MBR, but we could probably have a better
     *          search criteria to optimize the resulting tree
     *----------------------------------------------------------------*/

    /*-----------------------------------------------------------------
     * If bAddInThisNodeOnly=TRUE then we add the entry only locally
     * and do not need to look for the proper leaf to insert it.
     *----------------------------------------------------------------*/
    if (bAddInThisNodeOnly)
        bFound = TRUE;

    /*-----------------------------------------------------------------
     * First check if current child could be a valid candidate.
     *----------------------------------------------------------------*/
    if (!bFound &&
        m_poCurChild && (m_asEntries[m_nCurChildIndex].XMin <= nXMin &&
                         m_asEntries[m_nCurChildIndex].XMax >= nXMax &&
                         m_asEntries[m_nCurChildIndex].YMin <= nYMin &&
                         m_asEntries[m_nCurChildIndex].YMax >= nYMax ) )
    {

        bFound = TRUE;
    }

    /*-----------------------------------------------------------------
     * Scan all entries to find a valid candidate
     * We look for the entry whose center is the closest to the center
     * of the object to add.
     *----------------------------------------------------------------*/
    if (!bFound)
    {
        int nObjCenterX = (nXMin + nXMax)/2;
        int nObjCenterY = (nYMin + nYMax)/2;

        // Make sure blocks currently in memory are written to disk.
        if (m_poCurChild)
        {
            m_poCurChild->CommitToFile();
            delete m_poCurChild;
            m_poCurChild = NULL;
            m_nCurChildIndex = -1;
        }

        // Look for entry whose center is closest to center of new object
        int nBestCandidate = -1;
        int nMinDist = 2000000000;

        for(i=0; i<m_numEntries; i++)
        {
            int nX = (m_asEntries[i].XMin + m_asEntries[i].XMax)/2;
            int nY = (m_asEntries[i].YMin + m_asEntries[i].YMax)/2;

            int nDist = (nX-nObjCenterX)*(nX-nObjCenterX) +
                             (nY-nObjCenterY)*(nY-nObjCenterY);

            if (nBestCandidate==-1 || nDist < nMinDist)
            {
                nBestCandidate = i;
                nMinDist = nDist;
            }
        }
        
        if (nBestCandidate != -1)
        {
            // Try to load corresponding child... if it fails then we are
            // likely in a leaf node, so we'll add the new entry in the current
            // node.
            TABRawBinBlock *poBlock = NULL;

            // Prevent error message if referred block not committed yet.
            CPLPushErrorHandler(CPLQuietErrorHandler);

            if ((poBlock = TABCreateMAPBlockFromFile(m_fp, 
                                       m_asEntries[nBestCandidate].nBlockPtr,
                                       512, TRUE, TABReadWrite)) &&
                poBlock->GetBlockClass() == TABMAP_INDEX_BLOCK)
            {
                m_poCurChild = (TABMAPIndexBlock*)poBlock;
                poBlock = NULL;
                m_nCurChildIndex = nBestCandidate;
                m_poCurChild->SetParentRef(this);
                m_poCurChild->SetMAPBlockManagerRef(m_poBlockManagerRef);
                bFound = TRUE;
            }
                
            if (poBlock)
                delete poBlock;
            
            CPLPopErrorHandler();
            CPLErrorReset();
        }
    }

    if (bFound && !bAddInThisNodeOnly)
    {
        /*-------------------------------------------------------------
         * Found a child leaf... pass the call to it.
         *------------------------------------------------------------*/
        if (m_poCurChild->AddEntry(nXMin, nYMin, nXMax, nYMax, nBlockPtr) != 0)
            return -1;
    }
    else
    {
        /*-------------------------------------------------------------
         * Found no child to store new object... we're likely at the leaf
         * level so we'll store new object in current node
         *------------------------------------------------------------*/

        /*-------------------------------------------------------------
         * First thing to do is make sure that there is room for a new
         * entry in this node, and to split it if necessary.
         *------------------------------------------------------------*/
        if (GetNumFreeEntries() < 1)
        {
            if (m_poParentRef == NULL)
            {
                /*-----------------------------------------------------
                 * Splitting the root node adds one level to the tree, so
                 * after splitting we just redirect the call to the new
                 * child that's just been created.
                 *----------------------------------------------------*/
                if (SplitRootNode((nXMin+nXMax)/2, (nYMin+nYMax)/2) != 0)
                    return -1;  // Error happened and has already been reported

                CPLAssert(m_poCurChild);
                return m_poCurChild->AddEntry(nXMin, nYMin, nXMax, nYMax,
                                              nBlockPtr, TRUE);
            }
            else
            {
                /*-----------------------------------------------------
                 * Splitting a regular node
                 *----------------------------------------------------*/
                if (SplitNode((nXMin+nXMax)/2, (nYMin+nYMax)/2) != 0)
                    return -1; 
            }
        }

        if (InsertEntry(nXMin, nYMin, nXMax, nYMax, nBlockPtr) != 0)
            return -1;
    }

    /*-----------------------------------------------------------------
     * Update current node MBR and the reference to it in our parent.
     *----------------------------------------------------------------*/
    RecomputeMBR();

    return 0;
}

/**********************************************************************
 *                   TABMAPIndexBlock::SplitNode()
 *
 * Split current Node, update the references in the parent node, etc.
 * Note that Root Nodes cannot be split using this method... SplitRootNode()
 * should be used instead.
 *
 * nNewEntryX, nNewEntryY are the coord. of the center of the new entry that 
 * will be added after the split.  The split is done so that the current
 * node will be the one in which the new object should be stored.
 *
 * Returns 0 on success, -1 on error.
 **********************************************************************/
int     TABMAPIndexBlock::SplitNode(int nNewEntryX, int nNewEntryY)
{
    int nSrcEntries = m_numEntries;
    int nWidth, nHeight, nCenterX1, nCenterY1, nCenterX2, nCenterY2;

    CPLAssert(m_poBlockManagerRef);

    /*-----------------------------------------------------------------
     * Create a 2nd node, and assign both nodes a MBR that is half
     * of the biggest dimension (width or height) of the current node's MBR
     *
     * We also want to keep this node's current child in here.
     * Since splitting happens only during an addentry() operation and 
     * then both the current child and nNewEntryX/Y should fit in the same
     * area.
     *----------------------------------------------------------------*/
    TABMAPIndexBlock *poNewNode = new TABMAPIndexBlock(m_eAccess);
    if (poNewNode->InitNewBlock(m_fp, 512, 
                                m_poBlockManagerRef->AllocNewBlock()) != 0)
    {
        return -1;
    }
    poNewNode->SetMAPBlockManagerRef(m_poBlockManagerRef);


    nWidth = ABS(m_nMaxX - m_nMinX);
    nHeight = ABS(m_nMaxY - m_nMinY);

    if (nWidth > nHeight)
    {
        // Split node horizontally
        nCenterY1 = nCenterY2 = m_nMinY + nHeight/2;

        if (nNewEntryX < (m_nMinX + m_nMaxX)/2)
        {
            nCenterX1 = m_nMinX + nWidth/4;
            nCenterX2 = m_nMaxX - nWidth/4;
        }
        else