Line data    Source code

       1             : /******************************************************************************
       2             :  *
       3             :  * Project:  S-57 Translator
       4             :  * Purpose:  Implements DDFRecordIndex class.  This class is used to cache
       5             :  *           ISO8211 records for spatial objects so they can be efficiently
       6             :  *           assembled later as features.
       7             :  * Author:   Frank Warmerdam, warmerdam@pobox.com
       8             :  *
       9             :  ******************************************************************************
      10             :  * Copyright (c) 1999, 2001, Frank Warmerdam
      11             :  *
      12             :  * SPDX-License-Identifier: MIT
      13             :  ****************************************************************************/
      14             : 
      15             : #include "cpl_conv.h"
      16             : #include "s57.h"
      17             : 
      18             : #include <algorithm>
      19             : 
      20             : /************************************************************************/
      21             : /*                           DDFRecordIndex()                           */
      22             : /************************************************************************/
      23             : 
      24             : DDFRecordIndex::DDFRecordIndex() = default;
      25             : 
      26             : /************************************************************************/
      27             : /*                          ~DDFRecordIndex()                           */
      28             : /************************************************************************/
      29             : 
      30         195 : DDFRecordIndex::~DDFRecordIndex()
      31             : 
      32             : {
      33         195 :     Clear();
      34         195 : }
      35             : 
      36             : /************************************************************************/
      37             : /*                               Clear()                                */
      38             : /*                                                                      */
      39             : /*      Clear all entries from the index and deallocate all index       */
      40             : /*      resources.                                                      */
      41             : /************************************************************************/
      42             : 
      43         390 : void DDFRecordIndex::Clear()
      44             : 
      45             : {
      46         390 :     bSorted = false;
      47         390 :     asRecords.clear();
      48         390 : }
      49             : 
      50             : /************************************************************************/
      51             : /*                             AddRecord()                              */
      52             : /*                                                                      */
      53             : /*      Add a record to the index.  The index will assume ownership     */
      54             : /*      of the record.  If passing a record just read from a            */
      55             : /*      DDFModule it is imperative that the caller Clone()'s the        */
      56             : /*      record first.                                                   */
      57             : /************************************************************************/
      58             : 
      59       27573 : void DDFRecordIndex::AddRecord(int nKey, std::unique_ptr<DDFRecord> poRecord)
      60             : 
      61             : {
      62           0 :     DDFIndexedRecord indexRec;
      63       27573 :     indexRec.nKey = nKey;
      64       27573 :     indexRec.poRecord = std::move(poRecord);
      65       27573 :     asRecords.push_back(std::move(indexRec));
      66       27573 :     bSorted = false;
      67       27573 : }
      68             : 
      69             : /************************************************************************/
      70             : /*                             FindRecord()                             */
      71             : /*                                                                      */
      72             : /*      Though the returned pointer is not const, it should not         */
      73             : /*      be freed by application code.                                   */
      74             : /************************************************************************/
      75             : 
      76      116645 : DDFRecord *DDFRecordIndex::FindRecord(int nKey) const
      77             : 
      78             : {
      79      116645 :     if (!bSorted)
      80          30 :         Sort();
      81             : 
      82             :     /* -------------------------------------------------------------------- */
      83             :     /*      Do a binary search based on the key to find the desired record. */
      84             :     /* -------------------------------------------------------------------- */
      85      116645 :     if (!asRecords.empty() && nKey >= asRecords[0].nKey)
      86             :     {
      87      116645 :         size_t nMinIndex = 0;
      88      116645 :         size_t nMaxIndex = asRecords.size() - 1;
      89             : 
      90     1296390 :         while (nMinIndex <= nMaxIndex)
      91             :         {
      92     1296390 :             const size_t nTestIndex = (nMaxIndex + nMinIndex) / 2;
      93             : 
      94     1296390 :             if (asRecords[nTestIndex].nKey < nKey)
      95      594482 :                 nMinIndex = nTestIndex + 1;
      96      701910 :             else if (asRecords[nTestIndex].nKey > nKey)
      97      585265 :                 nMaxIndex = nTestIndex - 1;
      98             :             else
      99      116645 :                 return asRecords[nTestIndex].poRecord.get();
     100             :         }
     101             :     }
     102             : 
     103           0 :     return nullptr;
     104             : }
     105             : 
     106             : /************************************************************************/
     107             : /*                            RemoveRecord()                            */
     108             : /************************************************************************/
     109             : 
     110          18 : bool DDFRecordIndex::RemoveRecord(int nKey)
     111             : 
     112             : {
     113          18 :     if (!bSorted)
     114           0 :         Sort();
     115             : 
     116          18 :     if (asRecords.empty() || nKey < asRecords[0].nKey)
     117           0 :         return false;
     118             : 
     119             :     /* -------------------------------------------------------------------- */
     120             :     /*      Do a binary search based on the key to find the desired record. */
     121             :     /* -------------------------------------------------------------------- */
     122          18 :     size_t nMinIndex = 0;
     123          18 :     size_t nMaxIndex = asRecords.size() - 1;
     124          18 :     size_t nTestIndex = 0;
     125             : 
     126         145 :     while (nMinIndex <= nMaxIndex)
     127             :     {
     128         145 :         nTestIndex = (nMaxIndex + nMinIndex) / 2;
     129             : 
     130         145 :         if (asRecords[nTestIndex].nKey < nKey)
     131         110 :             nMinIndex = nTestIndex + 1;
     132          35 :         else if (asRecords[nTestIndex].nKey > nKey)
     133          17 :             nMaxIndex = nTestIndex - 1;
     134             :         else
     135          18 :             break;
     136             :     }
     137             : 
     138          18 :     if (nMinIndex > nMaxIndex)
     139           0 :         return false;
     140             : 
     141             :     /* -------------------------------------------------------------------- */
     142             :     /*      Delete this record.                                             */
     143             :     /* -------------------------------------------------------------------- */
     144          18 :     asRecords.erase(asRecords.begin() + nTestIndex);
     145             : 
     146          18 :     return true;
     147             : }
     148             : 
     149             : /************************************************************************/
     150             : /*                                Sort()                                */
     151             : /*                                                                      */
     152             : /*      Sort the records based on the key.                              */
     153             : /************************************************************************/
     154             : 
     155          57 : void DDFRecordIndex::Sort() const
     156             : 
     157             : {
     158          57 :     if (bSorted)
     159           0 :         return;
     160             : 
     161          57 :     std::sort(asRecords.begin(), asRecords.end(),
     162      487467 :               [](const DDFIndexedRecord &a, const DDFIndexedRecord &b)
     163      487467 :               { return a.nKey < b.nKey; });
     164             : 
     165          57 :     bSorted = true;
     166             : }
     167             : 
     168             : /************************************************************************/
     169             : /*                             GetByIndex()                             */
     170             : /************************************************************************/
     171             : 
     172       23215 : const DDFRecord *DDFRecordIndex::GetByIndex(int nIndex) const
     173             : 
     174             : {
     175       23215 :     if (!bSorted)
     176          27 :         Sort();
     177             : 
     178       23215 :     if (nIndex < 0 || nIndex >= GetCount())
     179           0 :         return nullptr;
     180             : 
     181       23215 :     return asRecords[nIndex].poRecord.get();
     182             : }
     183             : 
     184             : /************************************************************************/
     185             : /*                        GetClientInfoByIndex()                        */
     186             : /************************************************************************/
     187             : 
     188      331300 : const void *DDFRecordIndex::GetClientInfoByIndex(int nIndex) const
     189             : 
     190             : {
     191      331300 :     if (!bSorted)
     192           0 :         Sort();
     193             : 
     194      331300 :     if (nIndex < 0 || nIndex >= GetCount())
     195           0 :         return nullptr;
     196             : 
     197      331300 :     return asRecords[nIndex].pClientData;
     198             : }
     199             : 
     200             : /************************************************************************/
     201             : /*                        SetClientInfoByIndex()                        */
     202             : /************************************************************************/
     203             : 
     204        7207 : void DDFRecordIndex::SetClientInfoByIndex(int nIndex, const void *pClientData)
     205             : 
     206             : {
     207        7207 :     if (!bSorted)
     208           0 :         Sort();
     209             : 
     210        7207 :     if (nIndex < 0 || nIndex >= GetCount())
     211           0 :         return;
     212             : 
     213        7207 :     asRecords[nIndex].pClientData = pClientData;
     214             : }