1 : /******************************************************************************
2 : * $Id: ddfrecordindex.cpp 10645 2007-01-18 02:22:39Z warmerdam $
3 : *
4 : * Project: S-57 Translator
5 : * Purpose: Implements DDFRecordIndex class. This class is used to cache
6 : * ISO8211 records for spatial objects so they can be efficiently
7 : * assembled later as features.
8 : * Author: Frank Warmerdam, warmerdam@pobox.com
9 : *
10 : ******************************************************************************
11 : * Copyright (c) 1999, 2001, Frank Warmerdam
12 : *
13 : * Permission is hereby granted, free of charge, to any person obtaining a
14 : * copy of this software and associated documentation files (the "Software"),
15 : * to deal in the Software without restriction, including without limitation
16 : * the rights to use, copy, modify, merge, publish, distribute, sublicense,
17 : * and/or sell copies of the Software, and to permit persons to whom the
18 : * Software is furnished to do so, subject to the following conditions:
19 : *
20 : * The above copyright notice and this permission notice shall be included
21 : * in all copies or substantial portions of the Software.
22 : *
23 : * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
24 : * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
25 : * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
26 : * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
27 : * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
28 : * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
29 : * DEALINGS IN THE SOFTWARE.
30 : ****************************************************************************/
31 :
32 : #include "s57.h"
33 : #include "cpl_conv.h"
34 :
35 : CPL_CVSID("$Id: ddfrecordindex.cpp 10645 2007-01-18 02:22:39Z warmerdam $");
36 :
37 : /************************************************************************/
38 : /* DDFRecordIndex() */
39 : /************************************************************************/
40 :
41 60 : DDFRecordIndex::DDFRecordIndex()
42 :
43 : {
44 60 : bSorted = FALSE;
45 :
46 60 : nRecordCount = 0;
47 60 : nRecordMax = 0;
48 60 : pasRecords = NULL;
49 :
50 60 : nLastObjlPos = 0; /* rjensen. added for FindRecordByObjl() */
51 60 : nLastObjl = 0; /* rjensen. added for FindRecordByObjl() */
52 60 : }
53 :
54 : /************************************************************************/
55 : /* ~DDFRecordIndex() */
56 : /************************************************************************/
57 :
58 60 : DDFRecordIndex::~DDFRecordIndex()
59 :
60 : {
61 60 : Clear();
62 60 : }
63 :
64 : /************************************************************************/
65 : /* Clear() */
66 : /* */
67 : /* Clear all entries from the index and deallocate all index */
68 : /* resources. */
69 : /************************************************************************/
70 :
71 120 : void DDFRecordIndex::Clear()
72 :
73 : {
74 : // It turns out that deleting these records here is very expensive
75 : // due to the linear search in DDFModule::RemoveClone(). For now we
76 : // just leave the clones depending on DDFModule::~DDFModule() to clean
77 : // them up eventually.
78 :
79 : //for( int i = 0; i < nRecordCount; i++ )
80 : // delete pasRecords[i].poRecord;
81 :
82 120 : CPLFree( pasRecords );
83 120 : pasRecords = NULL;
84 :
85 120 : nRecordCount = 0;
86 120 : nRecordMax = 0;
87 :
88 120 : nLastObjlPos = 0; /* rjensen. added for FindRecordByObjl() */
89 120 : nLastObjl = 0; /* rjensen. added for FindRecordByObjl() */
90 :
91 120 : bSorted = FALSE;
92 120 : }
93 :
94 : /************************************************************************/
95 : /* AddRecord() */
96 : /* */
97 : /* Add a record to the index. The index will assume ownership */
98 : /* of the record. If passing a record just read from a */
99 : /* DDFModule it is imperitive that the caller Clone()'s the */
100 : /* record first. */
101 : /************************************************************************/
102 :
103 47170 : void DDFRecordIndex::AddRecord( int nKey, DDFRecord * poRecord )
104 :
105 : {
106 47170 : if( nRecordCount == nRecordMax )
107 : {
108 174 : nRecordMax = (int) (nRecordCount * 1.3 + 100);
109 : pasRecords = (DDFIndexedRecord *)
110 174 : CPLRealloc( pasRecords, sizeof(DDFIndexedRecord)*nRecordMax );
111 : }
112 :
113 47170 : bSorted = FALSE;
114 :
115 47170 : pasRecords[nRecordCount].nKey = nKey;
116 47170 : pasRecords[nRecordCount].poRecord = poRecord;
117 47170 : pasRecords[nRecordCount].pClientData = NULL;
118 :
119 47170 : nRecordCount++;
120 47170 : }
121 :
122 : /************************************************************************/
123 : /* FindRecord() */
124 : /* */
125 : /* Though the returned pointer is not const, it should be */
126 : /* considered internal to the index and not modified or freed */
127 : /* by application code. */
128 : /************************************************************************/
129 :
130 202 : DDFRecord * DDFRecordIndex::FindRecord( int nKey )
131 :
132 : {
133 202 : if( !bSorted )
134 26 : Sort();
135 :
136 : /* -------------------------------------------------------------------- */
137 : /* Do a binary search based on the key to find the desired record. */
138 : /* -------------------------------------------------------------------- */
139 202 : int nMinIndex = 0, nMaxIndex = nRecordCount-1;
140 :
141 1276 : while( nMinIndex <= nMaxIndex )
142 : {
143 1074 : int nTestIndex = (nMaxIndex + nMinIndex) / 2;
144 :
145 1074 : if( pasRecords[nTestIndex].nKey < nKey )
146 468 : nMinIndex = nTestIndex + 1;
147 606 : else if( pasRecords[nTestIndex].nKey > nKey )
148 404 : nMaxIndex = nTestIndex - 1;
149 : else
150 202 : return pasRecords[nTestIndex].poRecord;
151 : }
152 :
153 0 : return NULL;
154 : }
155 :
156 : /************************************************************************/
157 : /* FindRecordByObjl() */
158 : /* Rodney Jensen */
159 : /* Though the returned pointer is not const, it should be */
160 : /* considered internal to the index and not modified or freed */
161 : /* by application code. */
162 : /************************************************************************/
163 :
164 0 : DDFRecord * DDFRecordIndex::FindRecordByObjl( int nObjl )
165 : {
166 0 : if( !bSorted )
167 0 : Sort();
168 :
169 : /* -------------------------------------------------------------------- */
170 : /* Do a linear search based on the nObjl to find the desired record. */
171 : /* -------------------------------------------------------------------- */
172 0 : int nMinIndex = 0;
173 0 : if (nLastObjl != nObjl) nLastObjlPos=0;
174 :
175 0 : for (nMinIndex = nLastObjlPos; nMinIndex < nRecordCount; nMinIndex++)
176 : {
177 0 : if (nObjl == pasRecords[nMinIndex].poRecord->GetIntSubfield( "FRID", 0, "OBJL", 0 ) )
178 : {
179 0 : nLastObjlPos=nMinIndex+1; /* add 1, don't want to look at same again */
180 0 : nLastObjl=nObjl;
181 0 : return pasRecords[nMinIndex].poRecord;
182 : }
183 : }
184 :
185 0 : nLastObjlPos=0;
186 0 : nLastObjl=0;
187 :
188 0 : return NULL;
189 : }
190 :
191 : /************************************************************************/
192 : /* RemoveRecord() */
193 : /************************************************************************/
194 :
195 16 : int DDFRecordIndex::RemoveRecord( int nKey )
196 :
197 : {
198 16 : if( !bSorted )
199 0 : Sort();
200 :
201 : /* -------------------------------------------------------------------- */
202 : /* Do a binary search based on the key to find the desired record. */
203 : /* -------------------------------------------------------------------- */
204 16 : int nMinIndex = 0, nMaxIndex = nRecordCount-1;
205 16 : int nTestIndex = 0;
206 :
207 116 : while( nMinIndex <= nMaxIndex )
208 : {
209 100 : nTestIndex = (nMaxIndex + nMinIndex) / 2;
210 :
211 100 : if( pasRecords[nTestIndex].nKey < nKey )
212 52 : nMinIndex = nTestIndex + 1;
213 48 : else if( pasRecords[nTestIndex].nKey > nKey )
214 32 : nMaxIndex = nTestIndex - 1;
215 : else
216 16 : break;
217 : }
218 :
219 16 : if( nMinIndex > nMaxIndex )
220 0 : return FALSE;
221 :
222 : /* -------------------------------------------------------------------- */
223 : /* Delete this record. */
224 : /* -------------------------------------------------------------------- */
225 16 : delete pasRecords[nTestIndex].poRecord;
226 :
227 : /* -------------------------------------------------------------------- */
228 : /* Move all the list entries back one to fill the hole, and */
229 : /* update the total count. */
230 : /* -------------------------------------------------------------------- */
231 : memmove( pasRecords + nTestIndex,
232 : pasRecords + nTestIndex + 1,
233 16 : (nRecordCount - nTestIndex - 1) * sizeof(DDFIndexedRecord) );
234 :
235 16 : nRecordCount--;
236 :
237 16 : return TRUE;
238 : }
239 :
240 : /************************************************************************/
241 : /* DDFCompare() */
242 : /* */
243 : /* Compare two DDFIndexedRecord objects for qsort(). */
244 : /************************************************************************/
245 :
246 283326 : static int DDFCompare( const void *pRec1, const void *pRec2 )
247 :
248 : {
249 283326 : if( ((const DDFIndexedRecord *) pRec1)->nKey
250 : == ((const DDFIndexedRecord *) pRec2)->nKey )
251 0 : return 0;
252 283326 : else if( ((const DDFIndexedRecord *) pRec1)->nKey
253 : < ((const DDFIndexedRecord *) pRec2)->nKey )
254 230332 : return -1;
255 : else
256 52994 : return 1;
257 : }
258 :
259 : /************************************************************************/
260 : /* Sort() */
261 : /* */
262 : /* Sort the records based on the key. This is currently */
263 : /* implemented as a bubble sort, and could gain in efficiency */
264 : /* by reimplementing as a quick sort; however, I believe that */
265 : /* the keys will always be in order so a bubble sort should */
266 : /* only require one pass to verify this. */
267 : /************************************************************************/
268 :
269 38 : void DDFRecordIndex::Sort()
270 :
271 : {
272 38 : if( bSorted )
273 0 : return;
274 :
275 38 : qsort( pasRecords, nRecordCount, sizeof(DDFIndexedRecord), DDFCompare );
276 :
277 38 : bSorted = TRUE;
278 : }
279 :
280 : /************************************************************************/
281 : /* GetByIndex() */
282 : /************************************************************************/
283 :
284 16782 : DDFRecord * DDFRecordIndex::GetByIndex( int nIndex )
285 :
286 : {
287 16782 : if( !bSorted )
288 12 : Sort();
289 :
290 16782 : if( nIndex < 0 || nIndex >= nRecordCount )
291 0 : return NULL;
292 : else
293 16782 : return pasRecords[nIndex].poRecord;
294 : }
295 :
296 : /************************************************************************/
297 : /* GetClientInfoByIndex() */
298 : /************************************************************************/
299 :
300 2428 : void * DDFRecordIndex::GetClientInfoByIndex( int nIndex )
301 :
302 : {
303 2428 : if( !bSorted )
304 0 : Sort();
305 :
306 2428 : if( nIndex < 0 || nIndex >= nRecordCount )
307 0 : return NULL;
308 : else
309 2428 : return pasRecords[nIndex].pClientData;
310 : }
311 :
312 : /************************************************************************/
313 : /* SetClientInfoByIndex() */
314 : /************************************************************************/
315 :
316 2356 : void DDFRecordIndex::SetClientInfoByIndex( int nIndex, void *pClientData )
317 :
318 : {
319 2356 : if( !bSorted )
320 0 : Sort();
321 :
322 2356 : if( nIndex < 0 || nIndex >= nRecordCount )
323 0 : return;
324 : else
325 2356 : pasRecords[nIndex].pClientData = pClientData;
326 : }
327 :
|
