mitab_mapindexblock.cpp

mitab,读取MapInfo的地图文件

    m_numEntries = 0;

    // Insert nSeed1 in this node
    InsertEntry(pasSrcEntries[nSeed1].XMin, 
                pasSrcEntries[nSeed1].YMin,
                pasSrcEntries[nSeed1].XMax, 
                pasSrcEntries[nSeed1].YMax,
                pasSrcEntries[nSeed1].nBlockPtr);

    // Move nSeed2 to 2nd node
    poNewNode->InsertEntry(pasSrcEntries[nSeed2].XMin, 
                           pasSrcEntries[nSeed2].YMin,
                           pasSrcEntries[nSeed2].XMax, 
                           pasSrcEntries[nSeed2].YMax,
                           pasSrcEntries[nSeed2].nBlockPtr);

    // Update cur child index if necessary
    if (nSeed1 == nSrcCurChildIndex)
        m_nCurChildIndex = m_numEntries-1;

    /*-----------------------------------------------------------------
     * Go through the rest of the entries and assign them to one 
     * of the 2 nodes.
     *
     * Criteria is minimal area difference.
     * Resolve ties by adding the entry to the node with smaller total
     * area, then to the one with fewer entries, then to either.
     *----------------------------------------------------------------*/
    for(int iEntry=0; iEntry<nSrcEntries; iEntry++)
    {
        if (iEntry == nSeed1 || iEntry == nSeed2)
            continue;

        // If one of the two nodes is almost full then all remaining
        // entries should go to the other node
        // The entry corresponding to the current child also automatically
        // stays in this node.
        if (iEntry == nSrcCurChildIndex)
        {
            InsertEntry(pasSrcEntries[iEntry].XMin, 
                        pasSrcEntries[iEntry].YMin,
                        pasSrcEntries[iEntry].XMax, 
                        pasSrcEntries[iEntry].YMax,
                        pasSrcEntries[iEntry].nBlockPtr);

            // Update current child index
            m_nCurChildIndex = m_numEntries-1;

            continue;

        }
        else if (m_numEntries >= TAB_MAX_ENTRIES_INDEX_BLOCK-1)
        {
            poNewNode->InsertEntry(pasSrcEntries[iEntry].XMin, 
                                   pasSrcEntries[iEntry].YMin,
                                   pasSrcEntries[iEntry].XMax, 
                                   pasSrcEntries[iEntry].YMax,
                                   pasSrcEntries[iEntry].nBlockPtr);
            continue;
        }
        else if (poNewNode->GetNumEntries() >= TAB_MAX_ENTRIES_INDEX_BLOCK-1)
        {
            InsertEntry(pasSrcEntries[iEntry].XMin, 
                        pasSrcEntries[iEntry].YMin,
                        pasSrcEntries[iEntry].XMax, 
                        pasSrcEntries[iEntry].YMax,
                        pasSrcEntries[iEntry].nBlockPtr);
            continue;
        }


        // Decide which of the two nodes to put this entry in
        double dAreaDiff1, dAreaDiff2;
        RecomputeMBR();
        dAreaDiff1 = ComputeAreaDiff(m_nMinX, m_nMinY, m_nMaxX, m_nMaxY,
                                     pasSrcEntries[iEntry].XMin, 
                                     pasSrcEntries[iEntry].YMin,
                                     pasSrcEntries[iEntry].XMax,
                                     pasSrcEntries[iEntry].YMax);

        GInt32 nXMin2, nYMin2, nXMax2, nYMax2;
        poNewNode->RecomputeMBR();
        poNewNode->GetMBR(nXMin2, nYMin2, nXMax2, nYMax2);
        dAreaDiff2 = ComputeAreaDiff(nXMin2, nYMin2, nXMax2, nYMax2,
                                     pasSrcEntries[iEntry].XMin, 
                                     pasSrcEntries[iEntry].YMin,
                                     pasSrcEntries[iEntry].XMax,
                                     pasSrcEntries[iEntry].YMax);
        if (dAreaDiff1 < dAreaDiff2)
        {
            // This entry stays in this node
            InsertEntry(pasSrcEntries[iEntry].XMin, 
                        pasSrcEntries[iEntry].YMin,
                        pasSrcEntries[iEntry].XMax, 
                        pasSrcEntries[iEntry].YMax,
                        pasSrcEntries[iEntry].nBlockPtr);
        }
        else
        {
            // This entry goes to new node
            poNewNode->InsertEntry(pasSrcEntries[iEntry].XMin, 
                                   pasSrcEntries[iEntry].YMin,
                                   pasSrcEntries[iEntry].XMax, 
                                   pasSrcEntries[iEntry].YMax,
                                   pasSrcEntries[iEntry].nBlockPtr);
        }
    }

    /*-----------------------------------------------------------------
     * Recompute MBR and update current node info in parent
     *----------------------------------------------------------------*/
    RecomputeMBR();
    poNewNode->RecomputeMBR();

    /*-----------------------------------------------------------------
     * Add second node info to parent and then flush it to disk.
     * This may trigger splitting of parent
     *----------------------------------------------------------------*/
    CPLAssert(m_poParentRef);
    int nMinX, nMinY, nMaxX, nMaxY;
    poNewNode->GetMBR(nMinX, nMinY, nMaxX, nMaxY);
    m_poParentRef->AddEntry(nMinX, nMinY, nMaxX, nMaxY,
                            poNewNode->GetNodeBlockPtr(), TRUE);
    poNewNode->CommitToFile();
    delete poNewNode;

    CPLFree(pasSrcEntries);

    return 0;
}

/**********************************************************************
 *                   TABMAPIndexBlock::SplitRootNode()
 *
 * (private method)
 *
 * Split a Root Node.
 * First, a level of nodes must be added to the tree, then the contents
 * of what used to be the root node is moved 1 level down and then that
 * node is split like a regular node.
 *
 * Returns 0 on success, -1 on error
 **********************************************************************/
int TABMAPIndexBlock::SplitRootNode(GInt32 nNewEntryXMin, GInt32 nNewEntryYMin,
                                    GInt32 nNewEntryXMax, GInt32 nNewEntryYMax)
{
    CPLAssert(m_poBlockManagerRef);
    CPLAssert(m_poParentRef == NULL);

    /*-----------------------------------------------------------------
     * Since a root note cannot be split, we add a level of nodes
     * under it and we'll do the split at that level.
     *----------------------------------------------------------------*/
    TABMAPIndexBlock *poNewNode = new TABMAPIndexBlock(m_eAccess);

    if (poNewNode->InitNewBlock(m_fp, 512, 
                                m_poBlockManagerRef->AllocNewBlock()) != 0)
    {
        return -1;
    }
    poNewNode->SetMAPBlockManagerRef(m_poBlockManagerRef);

    // Move all entries to the new child
    int nSrcEntries = m_numEntries;
    m_numEntries = 0;
    for(int iEntry=0; iEntry<nSrcEntries; iEntry++)
    {
        poNewNode->InsertEntry(m_asEntries[iEntry].XMin, 
                               m_asEntries[iEntry].YMin,
                               m_asEntries[iEntry].XMax, 
                               m_asEntries[iEntry].YMax,
                               m_asEntries[iEntry].nBlockPtr);
    }
    
    /*-----------------------------------------------------------------
     * Transfer current child object to new node.
     *----------------------------------------------------------------*/
    if (m_poCurChild)
    {
        poNewNode->SetCurChildRef(m_poCurChild, m_nCurChildIndex);
        m_poCurChild->SetParentRef(poNewNode);
        m_poCurChild = NULL;
        m_nCurChildIndex = -1;
    }

    /*-----------------------------------------------------------------
     * Place info about new child in current node.
     *----------------------------------------------------------------*/
    poNewNode->RecomputeMBR();
    int nMinX, nMinY, nMaxX, nMaxY;
    poNewNode->GetMBR(nMinX, nMinY, nMaxX, nMaxY);
    InsertEntry(nMinX, nMinY, nMaxX, nMaxY, poNewNode->GetNodeBlockPtr());

    /*-----------------------------------------------------------------
     * Keep a reference to the new child
     *----------------------------------------------------------------*/
    poNewNode->SetParentRef(this);
    m_poCurChild = poNewNode;
    m_nCurChildIndex = m_numEntries -1;

    /*-----------------------------------------------------------------
     * And finally force the child to split itself
     *----------------------------------------------------------------*/
    return m_poCurChild->SplitNode(nNewEntryXMin, nNewEntryYMin,
                                   nNewEntryXMax, nNewEntryYMax);
}


/**********************************************************************
 *                   TABMAPIndexBlock::RecomputeMBR()
 *
 * Recompute current block MBR, and update info in parent.
 **********************************************************************/
void TABMAPIndexBlock::RecomputeMBR()
{
    GInt32 nMinX, nMinY, nMaxX, nMaxY;

    nMinX = 1000000000;
    nMinY = 1000000000;
    nMaxX = -1000000000;
    nMaxY = -1000000000;

    for(int i=0; i<m_numEntries; i++)
    {
        if (m_asEntries[i].XMin < nMinX)
            nMinX = m_asEntries[i].XMin;
        if (m_asEntries[i].XMax > nMaxX)
            nMaxX = m_asEntries[i].XMax;

        if (m_asEntries[i].YMin < nMinY)
            nMinY = m_asEntries[i].YMin;
        if (m_asEntries[i].YMax > nMaxY)
            nMaxY = m_asEntries[i].YMax;
    }

    if (m_nMinX != nMinX ||
        m_nMinY != nMinY ||
        m_nMaxX != nMaxX ||
        m_nMaxY != nMaxY )
    {
        m_nMinX = nMinX;
        m_nMinY = nMinY;
        m_nMaxX = nMaxX;
        m_nMaxY = nMaxY;

        m_bModified = TRUE;

        if (m_poParentRef)
            m_poParentRef->UpdateCurChildMBR(m_nMinX, m_nMinY, 
                                             m_nMaxX, m_nMaxY,
                                             GetNodeBlockPtr());
    }

}

/**********************************************************************
 *                   TABMAPIndexBlock::UpateCurChildMBR()
 *
 * Update current child MBR info, and propagate info in parent.
 *
 * nBlockPtr is passed only to validate the consistency of the tree.
 **********************************************************************/
void TABMAPIndexBlock::UpdateCurChildMBR(GInt32 nXMin, GInt32 nYMin,
                                         GInt32 nXMax, GInt32 nYMax,
                                         GInt32 nBlockPtr)
{
    CPLAssert(m_poCurChild);
    CPLAssert(m_asEntries[m_nCurChildIndex].nBlockPtr == nBlockPtr);

    if (m_asEntries[m_nCurChildIndex].XMin == nXMin &&
        m_asEntries[m_nCurChildIndex].YMin == nYMin &&
        m_asEntries[m_nCurChildIndex].XMax == nXMax &&
        m_asEntries[m_nCurChildIndex].YMax == nYMax)
    {
        return;  /* Nothing changed... nothing to do */
    }

    m_bModified = TRUE;

    m_asEntries[m_nCurChildIndex].XMin = nXMin;
    m_asEntries[m_nCurChildIndex].YMin = nYMin;
    m_asEntries[m_nCurChildIndex].XMax = nXMax;
    m_asEntries[m_nCurChildIndex].YMax = nYMax;

    m_nMinX = 1000000000;
    m_nMinY = 1000000000;
    m_nMaxX = -1000000000;
    m_nMaxY = -1000000000;

    for(int i=0; i<m_numEntries; i++)
    {
        if (m_asEntries[i].XMin < m_nMinX)
            m_nMinX = m_asEntries[i].XMin;
        if (m_asEntries[i].XMax > m_nMaxX)
            m_nMaxX = m_asEntries[i].XMax;
    
        if (m_asEntries[i].YMin < m_nMinY)
            m_nMinY = m_asEntries[i].YMin;
        if (m_asEntries[i].YMax > m_nMaxY)
            m_nMaxY = m_asEntries[i].YMax;
    }

    if (m_poParentRef)
        m_poParentRef->UpdateCurChildMBR(m_nMinX, m_nMinY, m_nMaxX, m_nMaxY,
                                         GetNodeBlockPtr());

}


/**********************************************************************
 *                   TABMAPIndexBlock::SetMAPBlockManagerRef()
 *
 * Pass a reference to the block manager object for the file this 
 * block belongs to.  The block manager will be used by this object
 * when it needs to automatically allocate a new block.
 **********************************************************************/
void TABMAPIndexBlock::SetMAPBlockManagerRef(TABBinBlockManager *poBlockMgr)
{
    m_poBlockManagerRef = poBlockMgr;
};

/**********************************************************************
 *                   TABMAPIndexBlock::SetParentRef()
 *
 * Used to pass a reference to this node's parent.
 **********************************************************************/
void    TABMAPIndexBlock::SetParentRef(TABMAPIndexBlock *poParent)
{
    m_poParentRef = poParent;
}

/**********************************************************************
 *                   TABMAPIndexBlock::SetCurChildRef()
 *
 * Used to transfer a child object from one node to another
 **********************************************************************/
void    TABMAPIndexBlock::SetCurChildRef(TABMAPIndexBlock *poChild,
                                         int nChildIndex)
{
    m_poCurChild = poChild;
    m_nCurChildIndex = nChildIndex;
}

/**********************************************************************
 *                   TABMAPIndexBlock::Dump()
 *
 * Dump block contents... available only in DEBUG mode.
 **********************************************************************/
#ifdef DEBUG

void TABMAPIndexBlock::Dump(FILE *fpOut /*=NULL*/)
{
    if (fpOut == NULL)
        fpOut = stdout;

    fprintf(fpOut, "----- TABMAPIndexBlock::Dump() -----\n");
    if (m_pabyBuf == NULL)
    {
        fprintf(fpOut, "Block has not been initialized yet.");
    }
    else
    {
        fprintf(fpOut,"Index Block (type %d) at offset %d.\n", 
                                                m_nBlockType, m_nFileOffset);
        fprintf(fpOut,"  m_numEntries          = %d\n", m_numEntries);

        /*-------------------------------------------------------------
         * Loop through all entries, dumping each of them
         *------------------------------------------------------------*/
        if (m_numEntries > 0)
            ReadAllEntries();

        for(int i=0; i<m_numEntries; i++)
        {
            fprintf(fpOut, "    %6d -> (%d, %d) - (%d, %d)\n",
                    m_asEntries[i].nBlockPtr,
                    m_asEntries[i].XMin, m_asEntries[i].YMin,
                    m_asEntries[i].XMax, m_asEntries[i].YMax );
        }

    }

    fflush(fpOut);
}
#endif // DEBUG