1
2 ///////////////////////////////////////////////////////////
3 // //
4 // SAGA //
5 // //
6 // System for Automated Geoscientific Analyses //
7 // //
8 // Application Programming Interface //
9 // //
10 // Library: SAGA_API //
11 // //
12 //-------------------------------------------------------//
13 // //
14 // mat_indexing.cpp //
15 // //
16 // Copyright (C) 2005 by Olaf Conrad //
17 // //
18 //-------------------------------------------------------//
19 // //
20 // This file is part of 'SAGA - System for Automated //
21 // Geoscientific Analyses'. //
22 // //
23 // This library is free software; you can redistribute //
24 // it and/or modify it under the terms of the GNU Lesser //
25 // General Public License as published by the Free //
26 // Software Foundation, either version 2.1 of the //
27 // License, or (at your option) any later version. //
28 // //
29 // This library is distributed in the hope that it will //
30 // be useful, but WITHOUT ANY WARRANTY; without even the //
31 // implied warranty of MERCHANTABILITY or FITNESS FOR A //
32 // PARTICULAR PURPOSE. See the GNU Lesser General Public //
33 // License for more details. //
34 // //
35 // You should have received a copy of the GNU Lesser //
36 // General Public License along with this program; if //
37 // not, see <http://www.gnu.org/licenses/>. //
38 // //
39 //-------------------------------------------------------//
40 // //
41 // contact: Olaf Conrad //
42 // Institute of Geography //
43 // University of Goettingen //
44 // Goldschmidtstr. 5 //
45 // 37077 Goettingen //
46 // Germany //
47 // //
48 // e-mail: oconrad@saga-gis.org //
49 // //
50 ///////////////////////////////////////////////////////////
51
52 //---------------------------------------------------------
53 #include "mat_tools.h"
54
55
56 ///////////////////////////////////////////////////////////
57 // //
58 // //
59 // //
60 ///////////////////////////////////////////////////////////
61
62 //---------------------------------------------------------
CSG_Index(void)63 CSG_Index::CSG_Index(void)
64 {
65 _On_Construction();
66 }
67
68 //---------------------------------------------------------
_On_Construction(void)69 void CSG_Index::_On_Construction(void)
70 {
71 m_nValues = 0;
72 m_Index = NULL;
73 m_bProgress = false;
74 }
75
76 //---------------------------------------------------------
~CSG_Index(void)77 CSG_Index::~CSG_Index(void)
78 {
79 Destroy();
80 }
81
82 //---------------------------------------------------------
Destroy(void)83 bool CSG_Index::Destroy(void)
84 {
85 if( m_Index )
86 {
87 SG_Free(m_Index);
88 }
89
90 m_nValues = 0;
91 m_Index = NULL;
92
93 return( true );
94 }
95
96
97 ///////////////////////////////////////////////////////////
98 // //
99 ///////////////////////////////////////////////////////////
100
101 //---------------------------------------------------------
CSG_Index(int nValues,CSG_Index_Compare & Compare)102 CSG_Index::CSG_Index(int nValues, CSG_Index_Compare &Compare)
103 {
104 _On_Construction();
105
106 Create(nValues, Compare);
107 }
108
109 //---------------------------------------------------------
Create(int nValues,CSG_Index_Compare & Compare)110 bool CSG_Index::Create(int nValues, CSG_Index_Compare &Compare)
111 {
112 if( _Set_Array(nValues) && _Set_Index(&Compare) )
113 {
114 return( true );
115 }
116
117 Destroy();
118
119 return( false );
120 }
121
122 //---------------------------------------------------------
CSG_Index(int nValues,CSG_Index_Compare * pCompare)123 CSG_Index::CSG_Index(int nValues, CSG_Index_Compare *pCompare)
124 {
125 _On_Construction();
126
127 Create(nValues, pCompare);
128 }
129
130 //---------------------------------------------------------
Create(int nValues,CSG_Index_Compare * pCompare)131 bool CSG_Index::Create(int nValues, CSG_Index_Compare *pCompare)
132 {
133 if( pCompare && _Set_Array(nValues) && _Set_Index(pCompare) )
134 {
135 return( true );
136 }
137
138 Destroy();
139
140 return( false );
141 }
142
143
144 ///////////////////////////////////////////////////////////
145 // //
146 ///////////////////////////////////////////////////////////
147
148 //---------------------------------------------------------
149 class CSG_Index_Compare_Int : public CSG_Index::CSG_Index_Compare
150 {
151 public:
152 int *m_Values; bool m_Ascending;
153
CSG_Index_Compare_Int(int * Values,bool Ascending)154 CSG_Index_Compare_Int(int *Values, bool Ascending) : m_Values(Values), m_Ascending(Ascending) {}
155
Compare(const int _a,const int _b)156 virtual int Compare (const int _a, const int _b)
157 {
158 int a = m_Ascending ? _a : _b;
159 int b = m_Ascending ? _b : _a;
160
161 return( m_Values[a] - m_Values[b] );
162 }
163 };
164
165 //---------------------------------------------------------
CSG_Index(int nValues,int * Values,bool bAscending)166 CSG_Index::CSG_Index(int nValues, int *Values, bool bAscending)
167 {
168 _On_Construction();
169
170 Create(nValues, Values, bAscending);
171 }
172
173 //---------------------------------------------------------
Create(int nValues,int * Values,bool bAscending)174 bool CSG_Index::Create(int nValues, int *Values, bool bAscending)
175 {
176 CSG_Index_Compare_Int Compare(Values, bAscending);
177
178 return( Create(nValues, &Compare) );
179 }
180
181
182 ///////////////////////////////////////////////////////////
183 // //
184 ///////////////////////////////////////////////////////////
185
186 //---------------------------------------------------------
187 class CSG_Index_Compare_Double : public CSG_Index::CSG_Index_Compare
188 {
189 public:
190 double *m_Values; bool m_Ascending;
191
CSG_Index_Compare_Double(double * Values,bool Ascending)192 CSG_Index_Compare_Double(double *Values, bool Ascending) : m_Values(Values), m_Ascending(Ascending) {}
193
Compare(const int _a,const int _b)194 virtual int Compare (const int _a, const int _b)
195 {
196 int a = m_Ascending ? _a : _b;
197 int b = m_Ascending ? _b : _a;
198
199 double d = m_Values[a] - m_Values[b];
200
201 return( d < 0. ? -1 : d > 0. ? 1 : 0 );
202 }
203 };
204
205 //---------------------------------------------------------
CSG_Index(int nValues,double * Values,bool bAscending)206 CSG_Index::CSG_Index(int nValues, double *Values, bool bAscending)
207 {
208 _On_Construction();
209
210 Create(nValues, Values, bAscending);
211 }
212
213 //---------------------------------------------------------
Create(int nValues,double * Values,bool bAscending)214 bool CSG_Index::Create(int nValues, double *Values, bool bAscending)
215 {
216 CSG_Index_Compare_Double Compare(Values, bAscending);
217
218 return( Create(nValues, &Compare) );
219 }
220
221
222 ///////////////////////////////////////////////////////////
223 // //
224 ///////////////////////////////////////////////////////////
225
226 //---------------------------------------------------------
227 class CSG_Index_Compare_Function : public CSG_Index::CSG_Index_Compare
228 {
229 public:
230 TSG_PFNC_Compare m_Function;
231
CSG_Index_Compare_Function(TSG_PFNC_Compare Function)232 CSG_Index_Compare_Function(TSG_PFNC_Compare Function) : m_Function(Function) {}
233
Compare(const int _a,const int _b)234 virtual int Compare (const int _a, const int _b)
235 {
236 return( m_Function(_a, _b) );
237 }
238 };
239
240 //---------------------------------------------------------
CSG_Index(int nValues,TSG_PFNC_Compare fCompare)241 CSG_Index::CSG_Index(int nValues, TSG_PFNC_Compare fCompare)
242 {
243 _On_Construction();
244
245 Create(nValues, fCompare);
246 }
247
248 //---------------------------------------------------------
Create(int nValues,TSG_PFNC_Compare fCompare)249 bool CSG_Index::Create(int nValues, TSG_PFNC_Compare fCompare)
250 {
251 CSG_Index_Compare_Function Compare(fCompare);
252
253 return( Create(nValues, &Compare) );
254 }
255
256
257 ///////////////////////////////////////////////////////////
258 // //
259 ///////////////////////////////////////////////////////////
260
261 //---------------------------------------------------------
Show_Progress(bool bProgress)262 void CSG_Index::Show_Progress(bool bProgress)
263 {
264 m_bProgress = bProgress;
265 }
266
267 //---------------------------------------------------------
Add_Entry(int Position)268 bool CSG_Index::Add_Entry(int Position)
269 {
270 if( Position < 0 || Position >= m_nValues - 1 )
271 {
272 return( _Set_Array(m_nValues + 1) );
273 }
274
275 if( _Set_Array(m_nValues + 1) )
276 {
277 for(int i=Position, Value=m_nValues-1; i<m_nValues; i++)
278 {
279 int v = m_Index[i]; m_Index[i] = Value; Value = v;
280 }
281
282 return( true );
283 }
284
285 return( false );
286 }
287
288 //---------------------------------------------------------
Del_Entry(int Position)289 bool CSG_Index::Del_Entry(int Position)
290 {
291 if( Position < 0 || Position >= m_nValues - 1 )
292 {
293 return( _Set_Array(m_nValues - 1) );
294 }
295
296 int Value = m_Index[Position];
297
298 for(int i=Position; i<m_nValues-1; i++)
299 {
300 m_Index[i] = m_Index[i + 1];
301 }
302
303 m_Index[m_nValues - 1] = Value;
304
305 return( _Set_Array(m_nValues - 1) );
306 }
307
308 //---------------------------------------------------------
_Set_Array(int nValues)309 bool CSG_Index::_Set_Array(int nValues)
310 {
311 if( nValues < 1 )
312 {
313 return( Destroy() );
314 }
315
316 if( nValues == m_nValues )
317 {
318 return( true );
319 }
320
321 if( m_nValues > nValues ) // keep current sorting as far as possible...
322 {
323 for(int i=0, j=nValues; i<nValues && j<m_nValues; i++)
324 {
325 if( m_Index[i] >= nValues )
326 {
327 while( m_Index[j] >= nValues )
328 {
329 j++;
330
331 if( j >= m_nValues )
332 {
333 return( false ); // this should never happen!
334 }
335 }
336
337 int c = m_Index[i]; m_Index[i] = m_Index[j]; m_Index[j] = c;
338 }
339 }
340 }
341
342 int *Index = (int *)SG_Realloc(m_Index, nValues * sizeof(int));
343
344 if( !Index )
345 {
346 return( false );
347 }
348
349 m_Index = Index;
350
351 if( m_nValues < nValues ) // keep current sorting as far as possible...
352 {
353 for(int i=m_nValues; i<nValues; i++)
354 {
355 m_Index[i] = i;
356 }
357 }
358
359 m_nValues = nValues;
360
361 return( true );
362 }
363
364
365 ///////////////////////////////////////////////////////////
366 // //
367 ///////////////////////////////////////////////////////////
368
369 //---------------------------------------------------------
370 #define SG_INDEX_SWAP(a, b) {itemp=(a);(a)=(b);(b)=itemp;}
371
372 //---------------------------------------------------------
_Set_Index(CSG_Index_Compare * pCompare)373 bool CSG_Index::_Set_Index(CSG_Index_Compare *pCompare)
374 {
375 const int M = 7;
376
377 int indxt, itemp,
378 i, j, k, a,
379 l = 0,
380 ir = m_nValues - 1,
381 nstack = 64,
382 jstack = 0;
383
384 //-----------------------------------------------------
385 CSG_Array_Int istack(nstack);
386
387 int nProcessed = 0;
388
389 //-----------------------------------------------------
390 for(;;)
391 {
392 if( ir - l < M )
393 {
394 if( m_bProgress && !SG_UI_Process_Set_Progress((double)(nProcessed += M - 1), (double)m_nValues) )
395 {
396 SG_UI_Msg_Add_Error(_TL("index creation stopped by user"));
397
398 SG_UI_Process_Set_Ready();
399
400 return( false );
401 }
402
403 for(j=l+1; j<=ir; j++)
404 {
405 a = indxt = m_Index[j];
406
407 for(i=j-1; i>=0; i--)
408 {
409 if( pCompare->Compare(m_Index[i], a) <= 0 )
410 {
411 break;
412 }
413
414 m_Index[i + 1] = m_Index[i];
415 }
416
417 m_Index[i + 1] = indxt;
418 }
419
420 if( jstack == 0 )
421 {
422 break;
423 }
424
425 ir = istack[jstack--];
426 l = istack[jstack--];
427 }
428 else
429 {
430 k = (l + ir) >> 1;
431 SG_INDEX_SWAP(m_Index[k], m_Index[l + 1]);
432
433 if( pCompare->Compare(m_Index[l + 1], m_Index[ir]) > 0 )
434 SG_INDEX_SWAP (m_Index[l + 1], m_Index[ir]);
435
436 if( pCompare->Compare(m_Index[l ], m_Index[ir]) > 0 )
437 SG_INDEX_SWAP (m_Index[l ], m_Index[ir]);
438
439 if( pCompare->Compare(m_Index[l + 1], m_Index[l ]) > 0 )
440 SG_INDEX_SWAP (m_Index[l + 1], m_Index[l ]);
441
442 i = l + 1;
443 j = ir;
444 a = indxt = m_Index[l];
445
446 for(;;)
447 {
448 do i++; while( pCompare->Compare(m_Index[i], a) < 0 );
449 do j--; while( pCompare->Compare(m_Index[j], a) > 0 );
450
451 if( j < i )
452 {
453 break;
454 }
455
456 SG_INDEX_SWAP(m_Index[i], m_Index[j]);
457 }
458
459 m_Index[l] = m_Index[j];
460 m_Index[j] = indxt;
461 jstack += 2;
462
463 if( jstack >= nstack )
464 {
465 istack.Set_Array(nstack += 64);
466 }
467
468 if( ir - i + 1 >= j - l )
469 {
470 istack[jstack ] = ir;
471 istack[jstack - 1] = i;
472 ir = j - 1;
473 }
474 else
475 {
476 istack[jstack ] = j - 1;
477 istack[jstack - 1] = l;
478 l = i;
479 }
480 }
481 }
482
483 //-----------------------------------------------------
484 if( m_bProgress )
485 {
486 SG_UI_Process_Set_Ready();
487 }
488
489 return( true );
490 }
491
492 ///////////////////////////////////////////////////////////
493 // //
494 // //
495 // //
496 ///////////////////////////////////////////////////////////
497
498 //---------------------------------------------------------
CSG_PriorityQueue(size_t maxSize)499 CSG_PriorityQueue::CSG_PriorityQueue(size_t maxSize) : m_Items(NULL), m_nItems(0), m_maxSize(0)
500 {
501 m_pLeaf[0] = m_pLeaf[1] = NULL;
502
503 Create(maxSize);
504 }
505
506 //---------------------------------------------------------
~CSG_PriorityQueue(void)507 CSG_PriorityQueue::~CSG_PriorityQueue(void)
508 {
509 Destroy();
510 }
511
512 //---------------------------------------------------------
Create(size_t maxSize)513 void CSG_PriorityQueue::Create(size_t maxSize)
514 {
515 Destroy();
516
517 if( maxSize > 1 )
518 {
519 m_maxSize = maxSize;
520
521 m_Items = (CSG_PriorityQueueItem **)SG_Malloc(m_maxSize * sizeof(CSG_PriorityQueueItem *));
522 }
523 }
524
525 //---------------------------------------------------------
Destroy(void)526 void CSG_PriorityQueue::Destroy(void)
527 {
528 if( m_Items )
529 {
530 SG_Free(m_Items);
531
532 m_Items = NULL;
533 }
534
535 if( m_pLeaf[0] )
536 {
537 delete(m_pLeaf[0]);
538
539 m_pLeaf[0] = NULL;
540 }
541
542 if( m_pLeaf[1] )
543 {
544 delete(m_pLeaf[1]);
545
546 m_pLeaf[1] = NULL;
547 }
548 }
549
550
551 ///////////////////////////////////////////////////////////
552 // //
553 ///////////////////////////////////////////////////////////
554
555 //---------------------------------------------------------
_Insert_Position(CSG_PriorityQueueItem * pItem)556 size_t CSG_PriorityQueue::_Insert_Position(CSG_PriorityQueueItem *pItem)
557 {
558 if( m_nItems == 0 )
559 {
560 return( 0 );
561 }
562
563 size_t a = 0;
564 size_t b = m_nItems - 1;
565
566 if( pItem->Compare(m_Items[a]) < 0 )
567 {
568 return( a );
569 }
570
571 if( pItem->Compare(m_Items[b]) > 0 )
572 {
573 return( b + 1 );
574 }
575
576 for(size_t d=(b-a)/2 ; d>0; d/=2)
577 {
578 size_t i = a + d;
579
580 if( pItem->Compare(m_Items[i]) > 0 )
581 {
582 a = a < i ? i : a + 1;
583 }
584 else
585 {
586 b = b > i ? i : b - 1;
587 }
588 }
589
590 for(size_t i=a; i<=b; i++)
591 {
592 if( pItem->Compare(m_Items[i]) < 0 )
593 {
594 return( i );
595 }
596 }
597
598 return( b );
599 }
600
601 //---------------------------------------------------------
Add(CSG_PriorityQueueItem * pItem)602 void CSG_PriorityQueue::Add(CSG_PriorityQueueItem *pItem)
603 {
604 if( m_Items && m_nItems < m_maxSize )
605 {
606 size_t Position = _Insert_Position(pItem);
607
608 memmove(m_Items + Position + 1, m_Items + Position, sizeof(CSG_PriorityQueueItem *) * (m_nItems - Position));
609
610 m_Items[Position] = pItem;
611 }
612 else
613 {
614 if( !m_pLeaf[0] )
615 {
616 size_t Divide = m_maxSize / 2;
617
618 m_pLeaf[0] = new CSG_PriorityQueue(m_maxSize);
619 m_pLeaf[1] = new CSG_PriorityQueue(m_maxSize);
620
621 m_pLeaf[0]->m_nItems = Divide;
622 m_pLeaf[1]->m_nItems = m_maxSize - Divide;
623
624 memcpy(m_pLeaf[0]->m_Items, m_Items , m_pLeaf[0]->m_nItems * sizeof(CSG_PriorityQueueItem *));
625 memcpy(m_pLeaf[1]->m_Items, m_Items + m_pLeaf[0]->m_nItems, m_pLeaf[1]->m_nItems * sizeof(CSG_PriorityQueueItem *));
626
627 SG_Free(m_Items);
628 m_Items = NULL;
629 }
630
631 if( pItem->Compare(m_pLeaf[1]->Minimum()) > 0 )
632 {
633 m_pLeaf[1]->Add(pItem);
634 }
635 else
636 {
637 m_pLeaf[0]->Add(pItem);
638 }
639 }
640
641 m_nItems++;
642 }
643
644
645 ///////////////////////////////////////////////////////////
646 // //
647 ///////////////////////////////////////////////////////////
648
649 //---------------------------------------------------------
Poll(void)650 CSG_PriorityQueue::CSG_PriorityQueueItem * CSG_PriorityQueue::Poll(void)
651 {
652 if( m_nItems > 0 )
653 {
654 m_nItems--;
655
656 if( m_Items )
657 {
658 return( m_Items[m_nItems] );
659 } // else if( m_pLeaf[0] )
660
661 CSG_PriorityQueueItem *pItem = m_pLeaf[1]->Poll();
662
663 if( m_pLeaf[1]->m_nItems == 0 )
664 {
665 delete(m_pLeaf[1]);
666
667 CSG_PriorityQueue *pLeaf = m_pLeaf[0];
668
669 // m_nItems = pLeaf->m_nItems;
670 m_Items = pLeaf->m_Items;
671 m_pLeaf[0] = pLeaf->m_pLeaf[0];
672 m_pLeaf[1] = pLeaf->m_pLeaf[1];
673
674 pLeaf->m_Items = NULL;
675 pLeaf->m_pLeaf[0] = NULL;
676 pLeaf->m_pLeaf[1] = NULL;
677 delete(pLeaf);
678 }
679
680 return( pItem );
681 }
682
683 return( NULL );
684 }
685
686
687 ///////////////////////////////////////////////////////////
688 // //
689 // //
690 // //
691 ///////////////////////////////////////////////////////////
692
693 //---------------------------------------------------------
694