SAGA API v9.10
Loading...
Searching...
No Matches
mat_indexing.cpp
Go to the documentation of this file.
1
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// //
51
52//---------------------------------------------------------
53#include "mat_tools.h"
54
55
57// //
58// //
59// //
61
62//---------------------------------------------------------
63CSG_Index::CSG_Index(void)
64{
65 _On_Construction();
66}
67
68//---------------------------------------------------------
69void CSG_Index::_On_Construction(void)
70{
71 m_nValues = 0;
72 m_Index = NULL;
73 m_bProgress = false;
74}
75
76//---------------------------------------------------------
77CSG_Index::~CSG_Index(void)
78{
79 Destroy();
80}
81
82//---------------------------------------------------------
83bool 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
98// //
100
101//---------------------------------------------------------
102bool CSG_Index::Invert(void)
103{
104 if( m_nValues > 0 )
105 {
106 for(sLong a=0, b=m_nValues-1; a<b; a++, b--)
107 {
108 sLong i = m_Index[a]; m_Index[a] = m_Index[b]; m_Index[b] = i;
109 }
110
111 return( true );
112 }
113
114 return( false );
115}
116
117
119// //
121
122//---------------------------------------------------------
123CSG_Index::CSG_Index(sLong nValues, CSG_Index_Compare &Compare)
124{
125 _On_Construction();
126
127 Create(nValues, Compare);
128}
129
130//---------------------------------------------------------
131bool CSG_Index::Create(sLong nValues, CSG_Index_Compare &Compare)
132{
133 if( _Set_Array(nValues) && _Set_Index(&Compare) )
134 {
135 return( true );
136 }
137
138 Destroy();
139
140 return( false );
141}
142
143//---------------------------------------------------------
144CSG_Index::CSG_Index(sLong nValues, CSG_Index_Compare *pCompare)
145{
146 _On_Construction();
147
148 Create(nValues, pCompare);
149}
150
151//---------------------------------------------------------
152bool CSG_Index::Create(sLong nValues, CSG_Index_Compare *pCompare)
153{
154 if( pCompare && _Set_Array(nValues) && _Set_Index(pCompare) )
155 {
156 return( true );
157 }
158
159 Destroy();
160
161 return( false );
162}
163
164
166// //
168
169//---------------------------------------------------------
170class CSG_Index_Compare_Int : public CSG_Index::CSG_Index_Compare
171{
172public:
173 int *m_Values; bool m_Ascending;
174
175 CSG_Index_Compare_Int(int *Values, bool Ascending) : m_Values(Values), m_Ascending(Ascending) {}
176
177 virtual int Compare (const sLong _a, const sLong _b)
178 {
179 sLong a = m_Ascending ? _a : _b;
180 sLong b = m_Ascending ? _b : _a;
181
182 return( m_Values[a] - m_Values[b] );
183 }
184};
185
186//---------------------------------------------------------
187CSG_Index::CSG_Index(sLong nValues, int *Values, bool bAscending)
188{
189 _On_Construction();
190
191 Create(nValues, Values, bAscending);
192}
193
194//---------------------------------------------------------
195bool CSG_Index::Create(sLong nValues, int *Values, bool bAscending)
196{
197 CSG_Index_Compare_Int Compare(Values, bAscending);
198
199 return( Create(nValues, &Compare) );
200}
201
202
204// //
206
207//---------------------------------------------------------
208class CSG_Index_Compare_Double : public CSG_Index::CSG_Index_Compare
209{
210public:
211 double *m_Values; bool m_Ascending;
212
213 CSG_Index_Compare_Double(double *Values, bool Ascending) : m_Values(Values), m_Ascending(Ascending) {}
214
215 virtual int Compare (const sLong _a, const sLong _b)
216 {
217 sLong a = m_Ascending ? _a : _b;
218 sLong b = m_Ascending ? _b : _a;
219
220 double d = m_Values[a] - m_Values[b];
221
222 return( d < 0. ? -1 : d > 0. ? 1 : 0 );
223 }
224};
225
226//---------------------------------------------------------
227CSG_Index::CSG_Index(sLong nValues, double *Values, bool bAscending)
228{
229 _On_Construction();
230
231 Create(nValues, Values, bAscending);
232}
233
234//---------------------------------------------------------
235bool CSG_Index::Create(sLong nValues, double *Values, bool bAscending)
236{
237 CSG_Index_Compare_Double Compare(Values, bAscending);
238
239 return( Create(nValues, &Compare) );
240}
241
242
244// //
246
247//---------------------------------------------------------
248class CSG_Index_Compare_Function : public CSG_Index::CSG_Index_Compare
249{
250public:
251 TSG_PFNC_Compare m_Function;
252
253 CSG_Index_Compare_Function(TSG_PFNC_Compare Function) : m_Function(Function) {}
254
255 virtual int Compare (const sLong _a, const sLong _b)
256 {
257 return( m_Function(_a, _b) );
258 }
259};
260
261//---------------------------------------------------------
262CSG_Index::CSG_Index(sLong nValues, TSG_PFNC_Compare fCompare)
263{
264 _On_Construction();
265
266 Create(nValues, fCompare);
267}
268
269//---------------------------------------------------------
270bool CSG_Index::Create(sLong nValues, TSG_PFNC_Compare fCompare)
271{
272 CSG_Index_Compare_Function Compare(fCompare);
273
274 return( Create(nValues, &Compare) );
275}
276
277
279// //
281
282//---------------------------------------------------------
283void CSG_Index::Show_Progress(bool bProgress)
284{
285 m_bProgress = bProgress;
286}
287
288//---------------------------------------------------------
289bool CSG_Index::Add_Entry(sLong Position)
290{
291 if( Position < 0 || Position >= m_nValues - 1 )
292 {
293 return( _Set_Array(m_nValues + 1) );
294 }
295
296 if( _Set_Array(m_nValues + 1) )
297 {
298 for(sLong i=Position, Value=m_nValues-1; i<m_nValues; i++)
299 {
300 sLong v = m_Index[i]; m_Index[i] = Value; Value = v;
301 }
302
303 return( true );
304 }
305
306 return( false );
307}
308
309//---------------------------------------------------------
310bool CSG_Index::Del_Entry(sLong Position)
311{
312 if( Position < 0 || Position >= m_nValues - 1 )
313 {
314 return( _Set_Array(m_nValues - 1) );
315 }
316
317 sLong Value = m_Index[Position];
318
319 for(sLong i=Position; i<m_nValues-1; i++)
320 {
321 m_Index[i] = m_Index[i + 1];
322 }
323
324 m_Index[m_nValues - 1] = Value;
325
326 return( _Set_Array(m_nValues - 1) );
327}
328
329//---------------------------------------------------------
330bool CSG_Index::_Set_Array(sLong nValues)
331{
332 if( nValues < 1 )
333 {
334 return( Destroy() );
335 }
336
337 if( nValues == m_nValues )
338 {
339 return( true );
340 }
341
342 if( m_nValues > nValues ) // keep current sorting as far as possible...
343 {
344 for(sLong i=0, j=nValues; i<nValues && j<m_nValues; i++)
345 {
346 if( m_Index[i] >= nValues )
347 {
348 while( m_Index[j] >= nValues )
349 {
350 j++;
351
352 if( j >= m_nValues )
353 {
354 return( false ); // this should never happen!
355 }
356 }
357
358 sLong c = m_Index[i]; m_Index[i] = m_Index[j]; m_Index[j] = c;
359 }
360 }
361 }
362
363 sLong *Index = (sLong *)SG_Realloc(m_Index, nValues * sizeof(sLong));
364
365 if( !Index )
366 {
367 return( false );
368 }
369
370 m_Index = Index;
371
372 if( m_nValues < nValues ) // keep current sorting as far as possible...
373 {
374 for(sLong i=m_nValues; i<nValues; i++)
375 {
376 m_Index[i] = i;
377 }
378 }
379
380 m_nValues = nValues;
381
382 return( true );
383}
384
385
387// //
389
390//---------------------------------------------------------
391#define SG_INDEX_SWAP(a, b) {itemp=(a);(a)=(b);(b)=itemp;}
392
393//---------------------------------------------------------
394bool CSG_Index::_Set_Index(CSG_Index_Compare *pCompare)
395{
396 const int M = 7;
397
398 sLong indxt, itemp,
399 i, j, k, a,
400 l = 0,
401 ir = m_nValues - 1,
402 nstack = 64,
403 jstack = 0;
404
405 //-----------------------------------------------------
406 CSG_Array_sLong istack(nstack);
407
408 sLong nProcessed = 0;
409
410 //-----------------------------------------------------
411 for(;;)
412 {
413 if( ir - l < M )
414 {
415 if( m_bProgress && !SG_UI_Process_Set_Progress(nProcessed += M - 1, m_nValues) )
416 {
417 SG_UI_Msg_Add_Error(_TL("index creation stopped by user"));
418
419 SG_UI_Process_Set_Ready();
420
421 return( false );
422 }
423
424 for(j=l+1; j<=ir; j++)
425 {
426 a = indxt = m_Index[j];
427
428 for(i=j-1; i>=0; i--)
429 {
430 if( pCompare->Compare(m_Index[i], a) <= 0 )
431 {
432 break;
433 }
434
435 m_Index[i + 1] = m_Index[i];
436 }
437
438 m_Index[i + 1] = indxt;
439 }
440
441 if( jstack == 0 )
442 {
443 break;
444 }
445
446 ir = istack[jstack--];
447 l = istack[jstack--];
448 }
449 else
450 {
451 k = (l + ir) >> 1;
452 SG_INDEX_SWAP(m_Index[k], m_Index[l + 1]);
453
454 if( pCompare->Compare(m_Index[l + 1], m_Index[ir]) > 0 )
455 SG_INDEX_SWAP (m_Index[l + 1], m_Index[ir]);
456
457 if( pCompare->Compare(m_Index[l ], m_Index[ir]) > 0 )
458 SG_INDEX_SWAP (m_Index[l ], m_Index[ir]);
459
460 if( pCompare->Compare(m_Index[l + 1], m_Index[l ]) > 0 )
461 SG_INDEX_SWAP (m_Index[l + 1], m_Index[l ]);
462
463 i = l + 1;
464 j = ir;
465 a = indxt = m_Index[l];
466
467 for(;;)
468 {
469 do i++; while( pCompare->Compare(m_Index[i], a) < 0 );
470 do j--; while( pCompare->Compare(m_Index[j], a) > 0 );
471
472 if( j < i )
473 {
474 break;
475 }
476
477 SG_INDEX_SWAP(m_Index[i], m_Index[j]);
478 }
479
480 m_Index[l] = m_Index[j];
481 m_Index[j] = indxt;
482 jstack += 2;
483
484 if( jstack >= nstack )
485 {
486 istack.Set_Array(nstack += 64l);
487 }
488
489 if( ir - i + 1 >= j - l )
490 {
491 istack[jstack ] = ir;
492 istack[jstack - 1] = i;
493 ir = j - 1;
494 }
495 else
496 {
497 istack[jstack ] = j - 1;
498 istack[jstack - 1] = l;
499 l = i;
500 }
501 }
502 }
503
504 //-----------------------------------------------------
505 if( m_bProgress )
506 {
507 SG_UI_Process_Set_Ready();
508 }
509
510 return( true );
511}
512
514// //
515// //
516// //
518
519//---------------------------------------------------------
520CSG_PriorityQueue::CSG_PriorityQueue(size_t maxSize) : m_Items(NULL), m_nItems(0), m_maxSize(0)
521{
522 m_pLeaf[0] = m_pLeaf[1] = NULL;
523
524 Create(maxSize);
525}
526
527//---------------------------------------------------------
532
533//---------------------------------------------------------
534void CSG_PriorityQueue::Create(size_t maxSize)
535{
536 Destroy();
537
538 if( maxSize > 1 )
539 {
540 m_maxSize = maxSize;
541
542 m_Items = (CSG_PriorityQueueItem **)SG_Malloc(m_maxSize * sizeof(CSG_PriorityQueueItem *));
543 }
544}
545
546//---------------------------------------------------------
547void CSG_PriorityQueue::Destroy(void)
548{
549 if( m_Items )
550 {
551 SG_Free(m_Items);
552
553 m_Items = NULL;
554 }
555
556 if( m_pLeaf[0] )
557 {
558 delete(m_pLeaf[0]);
559
560 m_pLeaf[0] = NULL;
561 }
562
563 if( m_pLeaf[1] )
564 {
565 delete(m_pLeaf[1]);
566
567 m_pLeaf[1] = NULL;
568 }
569}
570
571
573// //
575
576//---------------------------------------------------------
577size_t CSG_PriorityQueue::_Insert_Position(CSG_PriorityQueueItem *pItem)
578{
579 if( m_nItems == 0 )
580 {
581 return( 0 );
582 }
583
584 size_t a = 0;
585 size_t b = m_nItems - 1;
586
587 if( pItem->Compare(m_Items[a]) < 0 )
588 {
589 return( a );
590 }
591
592 if( pItem->Compare(m_Items[b]) > 0 )
593 {
594 return( b + 1 );
595 }
596
597 for(size_t d=(b-a)/2 ; d>0; d/=2)
598 {
599 size_t i = a + d;
600
601 if( pItem->Compare(m_Items[i]) > 0 )
602 {
603 a = a < i ? i : a + 1;
604 }
605 else
606 {
607 b = b > i ? i : b - 1;
608 }
609 }
610
611 for(size_t i=a; i<=b; i++)
612 {
613 if( pItem->Compare(m_Items[i]) < 0 )
614 {
615 return( i );
616 }
617 }
618
619 return( b );
620}
621
622//---------------------------------------------------------
623void CSG_PriorityQueue::Add(CSG_PriorityQueueItem *pItem)
624{
625 if( m_Items && m_nItems < m_maxSize )
626 {
627 size_t Position = _Insert_Position(pItem);
628
629 memmove(m_Items + Position + 1, m_Items + Position, sizeof(CSG_PriorityQueueItem *) * (m_nItems - Position));
630
631 m_Items[Position] = pItem;
632 }
633 else
634 {
635 if( !m_pLeaf[0] )
636 {
637 size_t Divide = m_maxSize / 2;
638
639 m_pLeaf[0] = new CSG_PriorityQueue(m_maxSize);
640 m_pLeaf[1] = new CSG_PriorityQueue(m_maxSize);
641
642 m_pLeaf[0]->m_nItems = Divide;
643 m_pLeaf[1]->m_nItems = m_maxSize - Divide;
644
645 memcpy(m_pLeaf[0]->m_Items, m_Items , m_pLeaf[0]->m_nItems * sizeof(CSG_PriorityQueueItem *));
646 memcpy(m_pLeaf[1]->m_Items, m_Items + m_pLeaf[0]->m_nItems, m_pLeaf[1]->m_nItems * sizeof(CSG_PriorityQueueItem *));
647
648 SG_Free(m_Items);
649 m_Items = NULL;
650 }
651
652 if( pItem->Compare(m_pLeaf[1]->Minimum()) > 0 )
653 {
654 m_pLeaf[1]->Add(pItem);
655 }
656 else
657 {
658 m_pLeaf[0]->Add(pItem);
659 }
660 }
661
662 m_nItems++;
663}
664
665
667// //
669
670//---------------------------------------------------------
671CSG_PriorityQueue::CSG_PriorityQueueItem * CSG_PriorityQueue::Poll(void)
672{
673 if( m_nItems > 0 )
674 {
675 m_nItems--;
676
677 if( m_Items )
678 {
679 return( m_Items[m_nItems] );
680 } // else if( m_pLeaf[0] )
681
682 CSG_PriorityQueueItem *pItem = m_pLeaf[1]->Poll();
683
684 if( m_pLeaf[1]->m_nItems == 0 )
685 {
686 delete(m_pLeaf[1]);
687
688 CSG_PriorityQueue *pLeaf = m_pLeaf[0];
689
690 // m_nItems = pLeaf->m_nItems;
691 m_Items = pLeaf->m_Items;
692 m_pLeaf[0] = pLeaf->m_pLeaf[0];
693 m_pLeaf[1] = pLeaf->m_pLeaf[1];
694
695 pLeaf->m_Items = NULL;
696 pLeaf->m_pLeaf[0] = NULL;
697 pLeaf->m_pLeaf[1] = NULL;
698 delete(pLeaf);
699 }
700
701 return( pItem );
702 }
703
704 return( NULL );
705}
706
707
709// //
710// //
711// //
713
714//---------------------------------------------------------
SG_UI_Msg_Add_Error
void SG_UI_Msg_Add_Error(const char *Message)
Definition api_callback.cpp:553
SG_UI_Process_Set_Ready
bool SG_UI_Process_Set_Ready(void)
Definition api_callback.cpp:305
SG_UI_Process_Set_Progress
bool SG_UI_Process_Set_Progress(int Position, int Range)
Definition api_callback.cpp:255
SG_Malloc
SAGA_API_DLL_EXPORT void * SG_Malloc(size_t size)
Definition api_memory.cpp:65
sLong
signed long long sLong
Definition api_core.h:158
SG_Free
SAGA_API_DLL_EXPORT void SG_Free(void *memblock)
Definition api_memory.cpp:83
SG_Realloc
SAGA_API_DLL_EXPORT void * SG_Realloc(void *memblock, size_t size)
Definition api_memory.cpp:77
_TL
#define _TL(s)
Definition api_core.h:1568
CSG_Array_sLong
Definition api_core.h:479
CSG_Array_sLong::Set_Array
bool Set_Array(sLong nValues, bool bShrink=true)
Definition api_core.h:498
CSG_Index::CSG_Index_Compare
Definition mat_tools.h:203
CSG_Index::Invert
bool Invert(void)
Definition mat_indexing.cpp:102
CSG_Index::Destroy
bool Destroy(void)
Definition mat_indexing.cpp:83
CSG_Index::CSG_Index
CSG_Index(void)
Definition mat_indexing.cpp:63
CSG_Index::Del_Entry
bool Del_Entry(sLong Position=-1)
Definition mat_indexing.cpp:310
CSG_Index::~CSG_Index
virtual ~CSG_Index(void)
Definition mat_indexing.cpp:77
CSG_Index::Show_Progress
void Show_Progress(bool bProgress=true)
Definition mat_indexing.cpp:283
CSG_Index::Create
bool Create(sLong nValues, CSG_Index_Compare &Compare)
Definition mat_indexing.cpp:131
CSG_Index::Add_Entry
bool Add_Entry(sLong Position=-1)
Definition mat_indexing.cpp:289
CSG_PriorityQueue::CSG_PriorityQueueItem
Definition mat_tools.h:282
CSG_PriorityQueue::CSG_PriorityQueueItem::Compare
virtual int Compare(CSG_PriorityQueueItem *pItem)=0
CSG_PriorityQueue::Poll
CSG_PriorityQueueItem * Poll(void)
Definition mat_indexing.cpp:671
CSG_PriorityQueue::Add
void Add(CSG_PriorityQueueItem *pItem)
Definition mat_indexing.cpp:623
CSG_PriorityQueue::Create
void Create(size_t maxSize=256)
Definition mat_indexing.cpp:534
CSG_PriorityQueue::CSG_PriorityQueue
CSG_PriorityQueue(size_t maxSize=256)
Definition mat_indexing.cpp:520
CSG_PriorityQueue::Destroy
void Destroy(void)
Definition mat_indexing.cpp:547
CSG_PriorityQueue::~CSG_PriorityQueue
virtual ~CSG_PriorityQueue(void)
Definition mat_indexing.cpp:528
SG_INDEX_SWAP
#define SG_INDEX_SWAP(a, b)
Definition mat_indexing.cpp:391
mat_tools.h
TSG_PFNC_Compare
int(* TSG_PFNC_Compare)(const sLong a, const sLong b)
Definition mat_tools.h:196