mitab_mapindexblock.cpp

mitab,读取MapInfo的地图文件

    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;

    m_bModified = TRUE;

    return 0;
}

/**********************************************************************
 *                   TABMAPIndexBlock::ChooseSubEntryForInsert()
 *
 * Select the entry in this index block in which the new entry should 
 * be inserted. The criteria used is to select the node whose MBR needs
 * the least enlargement to include the new entry. We resolve ties by
 * chosing the entry with the rectangle of smallest area.
 * (This is the ChooseSubtree part of Guttman's "ChooseLeaf" algorithm.)
 *
 * Returns the index of the best candidate or -1 of node is empty.
 **********************************************************************/
int     TABMAPIndexBlock::ChooseSubEntryForInsert(GInt32 nXMin, GInt32 nYMin,
                                                  GInt32 nXMax, GInt32 nYMax)
{
    GInt32 i, nBestCandidate=-1;

    double dOptimalAreaDiff=0;

    double dNewEntryArea = MITAB_AREA(nXMin, nYMin, nXMax, nYMax);

    for(i=0; i<m_numEntries; i++)
    {
        double dAreaDiff = 0;
        double dAreaBefore = MITAB_AREA(m_asEntries[i].XMin,
                                        m_asEntries[i].YMin,
                                        m_asEntries[i].XMax,
                                        m_asEntries[i].YMax);

        /* Does this entry fully contain the new entry's MBR ?
         */
        GBool bIsContained = (nXMin >= m_asEntries[i].XMin &&
                              nYMin >= m_asEntries[i].YMin &&
                              nXMax <= m_asEntries[i].XMax &&
                              nYMax <= m_asEntries[i].YMax );

        if (bIsContained)
        {
            /* If new entry is fully contained in this entry then
             * the area difference will be the difference between the area
             * of the entry to insert and the area of m_asEntries[i]
             *
             * The diff value is negative in this case.
             */
            dAreaDiff = dNewEntryArea - dAreaBefore;
        }
        else
        {
            /* Need to calculate the expanded MBR to calculate the area
             * difference.
             */
            GInt32 nXMin2, nYMin2, nXMax2, nYMax2;
            nXMin2 = MIN(m_asEntries[i].XMin, nXMin);
            nYMin2 = MIN(m_asEntries[i].YMin, nYMin);
            nXMax2 = MAX(m_asEntries[i].XMax, nXMax);
            nYMax2 = MAX(m_asEntries[i].YMax, nYMax);

            dAreaDiff = MITAB_AREA(nXMin2,nYMin2,nXMax2,nYMax2) - dAreaBefore;
        }

        /* Is this a better candidate?
         * Note, possible Optimization: In case of tie, we could to pick the 
         * candidate with the smallest area
         */

        if (/* No best candidate yet */
            (nBestCandidate == -1)
            /* or current candidate is contained and best candidate is not contained */
            || (dAreaDiff < 0 && dOptimalAreaDiff >= 0)
            /* or if both are either contained or not contained then use the one
             * with the smallest area diff, which means maximum coverage in the case
             * of contained rects, or minimum area increase when not contained 
             */
            || (((dOptimalAreaDiff < 0 && dAreaDiff < 0) ||
                 (dOptimalAreaDiff > 0 && dAreaDiff > 0)) && 
                ABS(dAreaDiff) < ABS(dOptimalAreaDiff)) )
        {
            nBestCandidate = i;
            dOptimalAreaDiff = dAreaDiff;
        }

    }

    return nBestCandidate;
}

/**********************************************************************
 *                   TABMAPIndexBlock::ChooseLeafForInsert()
 *
 * Recursively search the tree until we find the best leaf to
 * contain the specified object MBR.
 *
 * Returns the nBlockPtr of the selected leaf node entry (should be a
 * ref to a TABMAPObjectBlock) or -1 on error.
 *
 * After this call, m_poCurChild will be pointing at the selected child 
 * node, for use by later calls to UpdateLeafEntry()
 **********************************************************************/
GInt32  TABMAPIndexBlock::ChooseLeafForInsert(GInt32 nXMin, GInt32 nYMin,
                                              GInt32 nXMax, GInt32 nYMax)
{
    GBool bFound = FALSE;

    if (m_numEntries < 0)
        return -1;

    /*-----------------------------------------------------------------
     * Look for the best candidate to contain the new entry
     *----------------------------------------------------------------*/

    // Make sure blocks currently in memory are written to disk.
    // TODO: Could we avoid deleting m_poCurChild if it's already 
    //       the best candidate for insert?
    if (m_poCurChild)
    {
        m_poCurChild->CommitToFile();
        delete m_poCurChild;
        m_poCurChild = NULL;
        m_nCurChildIndex = -1;
    }

    int nBestCandidate = ChooseSubEntryForInsert(nXMin,nYMin,nXMax,nYMax);
       
    CPLAssert(nBestCandidate != -1);
    if (nBestCandidate == -1)
        return -1;  /* This should never happen! */

    // 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)
    {
        /*-------------------------------------------------------------
         * Found a child leaf... pass the call to it.
         *------------------------------------------------------------*/
        return m_poCurChild->ChooseLeafForInsert(nXMin, nYMin, nXMax, nYMax);
    }

    /*-------------------------------------------------------------
     * Found no child index node... we must be at the leaf level 
     * (leaf points at map object data blocks) so we return a ref 
     * to the TABMAPObjBlock for insertion
     *------------------------------------------------------------*/
    return m_asEntries[nBestCandidate].nBlockPtr;
}


/**********************************************************************
 *                   TABMAPIndexBlock::GetCurLeafEntryMBR()
 *
 * Get the MBR for specified nBlockPtr in the leaf at the end of the
 * chain of m_poCurChild refs.
 *
 * This method requires that the chain of m_poCurChild refs already point
 * to a leaf that contains the specified nBlockPtr, it is usually called
 * right after ChooseLeafForInsert().
 *
 * Returns 0 on success, -1 on error.
 **********************************************************************/
int     TABMAPIndexBlock::GetCurLeafEntryMBR(GInt32 nBlockPtr,
                                             GInt32 &nXMin, GInt32 &nYMin,
                                             GInt32 &nXMax, GInt32 &nYMax)
{
    if (m_poCurChild)
    {
        /* Pass the call down to current child */
        return m_poCurChild->GetCurLeafEntryMBR(nBlockPtr,
                                                nXMin, nYMin, nXMax, nYMax);
    }

    /* We're at the leaf level, look for the entry */
    for(int i=0; i<m_numEntries; i++)
    {
        if (m_asEntries[i].nBlockPtr == nBlockPtr)
        {
            /* Found it. Return its MBR */
            nXMin = m_asEntries[i].XMin;
            nYMin = m_asEntries[i].YMin;
            nXMax = m_asEntries[i].XMax;
            nYMax = m_asEntries[i].YMax;

            return 0;
        }
    }

    /* Not found! This should not happen if method is used properly. */
    CPLError(CE_Failure, CPLE_AssertionFailed,
             "Entry to update not found in GetCurLeafEntryMBR()!");
    return -1; 

}


/**********************************************************************
 *                   TABMAPIndexBlock::UpdateLeafEntry()
 *
 * Update the MBR for specified nBlockPtr in the leaf at the end of the
 * chain of m_poCurChild refs and update MBR of parents if required.
 *
 * This method requires that the chain of m_poCurChild refs already point
 * to a leaf that contains the specified nBlockPtr, it is usually called
 * right after ChooseLeafForInsert().
 *
 * Returns 0 on success, -1 on error.
 **********************************************************************/
int     TABMAPIndexBlock::UpdateLeafEntry(GInt32 nBlockPtr,
                                          GInt32 nXMin, GInt32 nYMin,
                                          GInt32 nXMax, GInt32 nYMax )
{
    if (m_poCurChild)
    {
        /* Pass the call down to current child */
        return m_poCurChild->UpdateLeafEntry(nBlockPtr,
                                             nXMin, nYMin, nXMax, nYMax);
    }

    /* We're at the leaf level, look for the entry to update */
    for(int i=0; i<m_numEntries; i++)
    {
        if (m_asEntries[i].nBlockPtr == nBlockPtr)
        {
            /* Found it. */
            TABMAPIndexEntry *psEntry = &m_asEntries[i];

            if (psEntry->XMin != nXMin ||
                psEntry->YMin != nYMin ||
                psEntry->XMax != nXMax ||
                psEntry->YMax != nYMax )
            {
                /* MBR changed. Update MBR of entry */
                psEntry->XMin = nXMin;
                psEntry->YMin = nYMin;
                psEntry->XMax = nXMax;
                psEntry->YMax = nYMax;

                m_bModified = TRUE;

                /* Update MBR of this node and all parents */
                RecomputeMBR();
            }

            return 0;
        }
    }

    /* Not found! This should not happen if method is used properly. */
    CPLError(CE_Failure, CPLE_AssertionFailed,
             "Entry to update not found in UpdateLeafEntry()!");
    return -1; 
}


/**********************************************************************
 *                   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*/)