mitab_mapindexblock.cpp

mitab,读取MapInfo的地图文件

{
    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;
    }

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

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

    if (!bFound && m_numEntries > 0)
    {
        // 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;
        }

        int nBestCandidate = ChooseSubEntryForInsert(nXMin,nYMin,nXMax,nYMax);
       
        CPLAssert(nBestCandidate != -1);

        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, nYMin, nXMax, nYMax) != 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, nYMin, nXMax, nYMax) != 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::ComputeAreaDiff()
 *
 * (static method, also used by the TABMAPObjBlock class)
 *
 * Compute the area difference between two MBRs. Used in the SplitNode
 * algorithm to decide to which of the two nodes an entry should be added.
 *
 * The returned AreaDiff value is positive if NodeMBR has to be enlarged
 * and negative if new Entry is fully contained in the NodeMBR.
 **********************************************************************/
double  TABMAPIndexBlock::ComputeAreaDiff(GInt32 nNodeXMin, GInt32 nNodeYMin,
                                          GInt32 nNodeXMax, GInt32 nNodeYMax,
                                          GInt32 nEntryXMin, GInt32 nEntryYMin,
                                          GInt32 nEntryXMax, GInt32 nEntryYMax)
{

    double dAreaDiff=0;

    double dNodeAreaBefore = MITAB_AREA(nNodeXMin,
                                        nNodeYMin,
                                        nNodeXMax,
                                        nNodeYMax);

    /* Does the node fully contain the new entry's MBR ?
     */
    GBool bIsContained = (nEntryXMin >= nNodeXMin &&
                          nEntryYMin >= nNodeYMin &&
                          nEntryXMax <= nNodeXMax &&
                          nEntryYMax <= nNodeYMax );

    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 the node
         */
        dAreaDiff = MITAB_AREA(nEntryXMin, nEntryYMin, 
                               nEntryXMax, nEntryYMax) - dNodeAreaBefore;
    }
    else
    {
        /* Need to calculate the expanded MBR to calculate the area
         * difference.
         */
        nNodeXMin = MIN(nNodeXMin, nEntryXMin);
        nNodeYMin = MIN(nNodeYMin, nEntryYMin);
        nNodeXMax = MAX(nNodeXMax, nEntryXMax);
        nNodeYMax = MAX(nNodeYMax, nEntryYMax);

        dAreaDiff = MITAB_AREA(nNodeXMin,nNodeYMin,
                               nNodeXMax,nNodeYMax) - dNodeAreaBefore;
    }

    return dAreaDiff;
}



/**********************************************************************
 *                   TABMAPIndexBlock::PickSeedsForSplit()
 *
 * (static method, also used by the TABMAPObjBlock class)
 *
 * Pick two seeds to use to start splitting this node.
 *
 * Guttman's LinearPickSeed:
 * - Along each dimension find the entry whose rectangle has the 
 *   highest low side, and the one with the lowest high side
 * - Calculate the separation for each pair
 * - Normalize the separation by dividing by the extents of the 
 *   corresponding dimension
 * - Choose the pair with the greatest normalized separation along
 *   any dimension
 **********************************************************************/
int  TABMAPIndexBlock::PickSeedsForSplit(TABMAPIndexEntry *pasEntries,
                                         int numEntries,
                                         int nSrcCurChildIndex,
                                         GInt32 nNewEntryXMin, 
                                         GInt32 nNewEntryYMin,
                                         GInt32 nNewEntryXMax, 
                                         GInt32 nNewEntryYMax,
                                         int &nSeed1, int &nSeed2)
{
    GInt32 nSrcMinX=0, nSrcMinY=0, nSrcMaxX=0, nSrcMaxY=0;
    int nLowestMaxX=-1, nHighestMinX=-1, nLowestMaxY=-1, nHighestMinY=-1;
    GInt32 nLowestMaxXId=-1, nHighestMinXId=-1, nLowestMaxYId=-1, nHighestMinYId=-1;

    nSeed1=-1;
    nSeed2=-1;

    // Along each dimension find the entry whose rectangle has the 
    // highest low side, and the one with the lowest high side
    for(int iEntry=0; iEntry<numEntries; iEntry++)
    {
        if (nLowestMaxXId == -1 ||
            pasEntries[iEntry].XMax < nLowestMaxX)
        {
            nLowestMaxX = pasEntries[iEntry].XMax;
            nLowestMaxXId = iEntry;
        }

        if (nHighestMinXId == -1 ||
            pasEntries[iEntry].XMin > nHighestMinX)
        {
            nHighestMinX = pasEntries[iEntry].XMin;
            nHighestMinXId = iEntry;
        }

        if (nLowestMaxYId == -1 ||
            pasEntries[iEntry].YMax < nLowestMaxY)
        {
            nLowestMaxY = pasEntries[iEntry].YMax;
            nLowestMaxYId = iEntry;
        }

        if (nHighestMinYId == -1 ||
            pasEntries[iEntry].YMin > nHighestMinY)
        {
            nHighestMinY = pasEntries[iEntry].YMin;
            nHighestMinYId = iEntry;
        }

        // Also keep track of MBR of all entries
        if (iEntry == 0)
        {
            nSrcMinX = pasEntries[iEntry].XMin;
            nSrcMinY = pasEntries[iEntry].YMin;
            nSrcMaxX = pasEntries[iEntry].XMax;
            nSrcMaxY = pasEntries[iEntry].YMax;
        }
        else
        {
            nSrcMinX = MIN(nSrcMinX, pasEntries[iEntry].XMin);
            nSrcMinY = MIN(nSrcMinY ,pasEntries[iEntry].YMin);
            nSrcMaxX = MAX(nSrcMaxX ,pasEntries[iEntry].XMax);
            nSrcMaxY = MAX(nSrcMaxY ,pasEntries[iEntry].YMax);
        }
    }

    int nSrcWidth, nSrcHeight;
    nSrcWidth = ABS(nSrcMaxX - nSrcMinX);
    nSrcHeight = ABS(nSrcMaxY - nSrcMinY);

    // Calculate the separation for each pair (note that it may be negative
    // in case of overlap)
    // Normalize the separation by dividing by the extents of the 
    // corresponding dimension
    double dX, dY;

    dX = (double)(nHighestMinX - nLowestMaxX) / nSrcWidth;
    dY = (double)(nHighestMinY - nLowestMaxY) / nSrcHeight;

    // Choose the pair with the greatest normalized separation along
    // any dimension
    if (dX > dY)
    {
        nSeed1 = nHighestMinXId;
        nSeed2 = nLowestMaxXId;
    }
    else
    {
        nSeed1 = nHighestMinYId;
        nSeed2 = nLowestMaxYId;
    }

    // If nSeed1==nSeed2 then just pick any two (giving pref to current child)
    if (nSeed1 == nSeed2)
    {
        if (nSeed1 != nSrcCurChildIndex && nSrcCurChildIndex != -1)
            nSeed1 = nSrcCurChildIndex;
        else if (nSeed1 != 0)
            nSeed1 = 0;
        else
            nSeed1 = 1;
    }

    // Decide which of the two seeds best matches the new entry. That seed and
    // the new entry will stay in current node (new entry will be added by the
    // caller later). The other seed will go in the 2nd node
    double dAreaDiff1, dAreaDiff2;
    dAreaDiff1 = ComputeAreaDiff(pasEntries[nSeed1].XMin, 
                                 pasEntries[nSeed1].YMin,
                                 pasEntries[nSeed1].XMax,
                                 pasEntries[nSeed1].YMax,
                                 nNewEntryXMin, nNewEntryYMin,
                                 nNewEntryXMax, nNewEntryYMax);

    dAreaDiff2 = ComputeAreaDiff(pasEntries[nSeed2].XMin, 
                                 pasEntries[nSeed2].YMin,
                                 pasEntries[nSeed2].XMax,
                                 pasEntries[nSeed2].YMax,
                                 nNewEntryXMin, nNewEntryYMin,
                                 nNewEntryXMax, nNewEntryYMax);

    /* Note that we 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 the New Entry should fit in the same
     * area.
     */
    if (nSeed1 != nSrcCurChildIndex && 
        (dAreaDiff1 > dAreaDiff2 || nSeed2 == nSrcCurChildIndex))
    {
        // Seed2 stays in this node, Seed1 moves to new node
        // ... swap Seed1 and Seed2 indices
        int nTmp = nSeed1;
        nSeed1 = nSeed2;
        nSeed2 = nTmp;
    }

    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.
 *
 * nNewEntry* are the coord. 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(GInt32 nNewEntryXMin, GInt32 nNewEntryYMin,
                                    GInt32 nNewEntryXMax, GInt32 nNewEntryYMax)
{
    CPLAssert(m_poBlockManagerRef);

    /*-----------------------------------------------------------------
     * Create a 2nd node
     *----------------------------------------------------------------*/
    TABMAPIndexBlock *poNewNode = new TABMAPIndexBlock(m_eAccess);
    if (poNewNode->InitNewBlock(m_fp, 512, 
                                m_poBlockManagerRef->AllocNewBlock()) != 0)
    {
        return -1;
    }
    poNewNode->SetMAPBlockManagerRef(m_poBlockManagerRef);

    /*-----------------------------------------------------------------
     * Make a temporary copy of the entries in current node
     *----------------------------------------------------------------*/
    int nSrcEntries = m_numEntries;
    TABMAPIndexEntry *pasSrcEntries = (TABMAPIndexEntry*)CPLMalloc(m_numEntries*sizeof(TABMAPIndexEntry));
    memcpy(pasSrcEntries, &m_asEntries, m_numEntries*sizeof(TABMAPIndexEntry));

    int nSrcCurChildIndex = m_nCurChildIndex;

    /*-----------------------------------------------------------------
     * Pick Seeds for each node
     *----------------------------------------------------------------*/
    int nSeed1, nSeed2;
    PickSeedsForSplit(pasSrcEntries, nSrcEntries, nSrcCurChildIndex,
                      nNewEntryXMin, nNewEntryYMin, 
                      nNewEntryXMax, nNewEntryYMax,
                      nSeed1, nSeed2);

    /*-----------------------------------------------------------------
     * Reset number of entries in this node and start moving new entries
     *----------------------------------------------------------------*/