SAGA API  v9.6
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 //---------------------------------------------------------
63 CSG_Index::CSG_Index(void)
64 {
65  _On_Construction();
66 }
67 
68 //---------------------------------------------------------
69 void CSG_Index::_On_Construction(void)
70 {
71  m_nValues = 0;
72  m_Index = NULL;
73  m_bProgress = false;
74 }
75 
76 //---------------------------------------------------------
77 CSG_Index::~CSG_Index(void)
78 {
79  Destroy();
80 }
81 
82 //---------------------------------------------------------
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 
98 // //
100 
101 //---------------------------------------------------------
102 CSG_Index::CSG_Index(sLong nValues, CSG_Index_Compare &Compare)
103 {
104  _On_Construction();
105 
106  Create(nValues, Compare);
107 }
108 
109 //---------------------------------------------------------
110 bool CSG_Index::Create(sLong 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 //---------------------------------------------------------
123 CSG_Index::CSG_Index(sLong nValues, CSG_Index_Compare *pCompare)
124 {
125  _On_Construction();
126 
127  Create(nValues, pCompare);
128 }
129 
130 //---------------------------------------------------------
131 bool CSG_Index::Create(sLong 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 
145 // //
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 
154  CSG_Index_Compare_Int(int *Values, bool Ascending) : m_Values(Values), m_Ascending(Ascending) {}
155 
156  virtual int Compare (const sLong _a, const sLong _b)
157  {
158  sLong a = m_Ascending ? _a : _b;
159  sLong b = m_Ascending ? _b : _a;
160 
161  return( m_Values[a] - m_Values[b] );
162  }
163 };
164 
165 //---------------------------------------------------------
166 CSG_Index::CSG_Index(sLong nValues, int *Values, bool bAscending)
167 {
168  _On_Construction();
169 
170  Create(nValues, Values, bAscending);
171 }
172 
173 //---------------------------------------------------------
174 bool CSG_Index::Create(sLong nValues, int *Values, bool bAscending)
175 {
176  CSG_Index_Compare_Int Compare(Values, bAscending);
177 
178  return( Create(nValues, &Compare) );
179 }
180 
181 
183 // //
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 
192  CSG_Index_Compare_Double(double *Values, bool Ascending) : m_Values(Values), m_Ascending(Ascending) {}
193 
194  virtual int Compare (const sLong _a, const sLong _b)
195  {
196  sLong a = m_Ascending ? _a : _b;
197  sLong 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 //---------------------------------------------------------
206 CSG_Index::CSG_Index(sLong nValues, double *Values, bool bAscending)
207 {
208  _On_Construction();
209 
210  Create(nValues, Values, bAscending);
211 }
212 
213 //---------------------------------------------------------
214 bool CSG_Index::Create(sLong nValues, double *Values, bool bAscending)
215 {
216  CSG_Index_Compare_Double Compare(Values, bAscending);
217 
218  return( Create(nValues, &Compare) );
219 }
220 
221 
223 // //
225 
226 //---------------------------------------------------------
227 class CSG_Index_Compare_Function : public CSG_Index::CSG_Index_Compare
228 {
229 public:
230  TSG_PFNC_Compare m_Function;
231 
232  CSG_Index_Compare_Function(TSG_PFNC_Compare Function) : m_Function(Function) {}
233 
234  virtual int Compare (const sLong _a, const sLong _b)
235  {
236  return( m_Function(_a, _b) );
237  }
238 };
239 
240 //---------------------------------------------------------
241 CSG_Index::CSG_Index(sLong nValues, TSG_PFNC_Compare fCompare)
242 {
243  _On_Construction();
244 
245  Create(nValues, fCompare);
246 }
247 
248 //---------------------------------------------------------
249 bool CSG_Index::Create(sLong nValues, TSG_PFNC_Compare fCompare)
250 {
251  CSG_Index_Compare_Function Compare(fCompare);
252 
253  return( Create(nValues, &Compare) );
254 }
255 
256 
258 // //
260 
261 //---------------------------------------------------------
262 void CSG_Index::Show_Progress(bool bProgress)
263 {
264  m_bProgress = bProgress;
265 }
266 
267 //---------------------------------------------------------
268 bool CSG_Index::Add_Entry(sLong 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(sLong i=Position, Value=m_nValues-1; i<m_nValues; i++)
278  {
279  sLong v = m_Index[i]; m_Index[i] = Value; Value = v;
280  }
281 
282  return( true );
283  }
284 
285  return( false );
286 }
287 
288 //---------------------------------------------------------
289 bool CSG_Index::Del_Entry(sLong Position)
290 {
291  if( Position < 0 || Position >= m_nValues - 1 )
292  {
293  return( _Set_Array(m_nValues - 1) );
294  }
295 
296  sLong Value = m_Index[Position];
297 
298  for(sLong 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 //---------------------------------------------------------
309 bool CSG_Index::_Set_Array(sLong 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(sLong 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  sLong c = m_Index[i]; m_Index[i] = m_Index[j]; m_Index[j] = c;
338  }
339  }
340  }
341 
342  sLong *Index = (sLong *)SG_Realloc(m_Index, nValues * sizeof(sLong));
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(sLong 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 
366 // //
368 
369 //---------------------------------------------------------
370 #define SG_INDEX_SWAP(a, b) {itemp=(a);(a)=(b);(b)=itemp;}
371 
372 //---------------------------------------------------------
373 bool CSG_Index::_Set_Index(CSG_Index_Compare *pCompare)
374 {
375  const int M = 7;
376 
377  sLong 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_sLong istack(nstack);
386 
387  sLong nProcessed = 0;
388 
389  //-----------------------------------------------------
390  for(;;)
391  {
392  if( ir - l < M )
393  {
394  if( m_bProgress && !SG_UI_Process_Set_Progress(nProcessed += M - 1, 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 += 64l);
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 
493 // //
494 // //
495 // //
497 
498 //---------------------------------------------------------
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 //---------------------------------------------------------
507 CSG_PriorityQueue::~CSG_PriorityQueue(void)
508 {
509  Destroy();
510 }
511 
512 //---------------------------------------------------------
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 //---------------------------------------------------------
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 
552 // //
554 
555 //---------------------------------------------------------
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 //---------------------------------------------------------
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 
646 // //
648 
649 //---------------------------------------------------------
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 
688 // //
689 // //
690 // //
692 
693 //---------------------------------------------------------
CSG_Index::Show_Progress
void Show_Progress(bool bProgress=true)
Definition: mat_indexing.cpp:262
CSG_Array_sLong::Set_Array
bool Set_Array(sLong nValues, bool bShrink=true)
Definition: api_core.h:498
CSG_PriorityQueue::CSG_PriorityQueue
CSG_PriorityQueue(size_t maxSize=256)
Definition: mat_indexing.cpp:499
CSG_Index::CSG_Index
CSG_Index(void)
Definition: mat_indexing.cpp:63
_TL
#define _TL(s)
Definition: api_core.h:1489
SG_INDEX_SWAP
#define SG_INDEX_SWAP(a, b)
Definition: mat_indexing.cpp:370
CSG_PriorityQueue::CSG_PriorityQueueItem::Compare
virtual int Compare(CSG_PriorityQueueItem *pItem)=0
CSG_Index::~CSG_Index
virtual ~CSG_Index(void)
Definition: mat_indexing.cpp:77
CSG_Index::CSG_Index_Compare
Definition: mat_tools.h:203
SG_Malloc
SAGA_API_DLL_EXPORT void * SG_Malloc(size_t size)
Definition: api_memory.cpp:65
CSG_Index::CSG_Index_Compare::Compare
virtual int Compare(const sLong a, const sLong b)=0
CSG_PriorityQueue::Poll
CSG_PriorityQueueItem * Poll(void)
Definition: mat_indexing.cpp:650
SG_Free
SAGA_API_DLL_EXPORT void SG_Free(void *memblock)
Definition: api_memory.cpp:83
mat_tools.h
CSG_PriorityQueue::~CSG_PriorityQueue
virtual ~CSG_PriorityQueue(void)
Definition: mat_indexing.cpp:507
CSG_PriorityQueue::Add
void Add(CSG_PriorityQueueItem *pItem)
Definition: mat_indexing.cpp:602
CSG_Index::Create
bool Create(sLong nValues, CSG_Index_Compare &Compare)
Definition: mat_indexing.cpp:110
TSG_PFNC_Compare
int(* TSG_PFNC_Compare)(const sLong a, const sLong b)
Definition: mat_tools.h:196
sLong
signed long long sLong
Definition: api_core.h:158
CSG_PriorityQueue::Create
void Create(size_t maxSize=256)
Definition: mat_indexing.cpp:513
CSG_Index::Add_Entry
bool Add_Entry(sLong Position=-1)
Definition: mat_indexing.cpp:268
CSG_PriorityQueue::Minimum
CSG_PriorityQueueItem * Minimum(void) const
Definition: mat_tools.h:307
SG_UI_Process_Set_Progress
bool SG_UI_Process_Set_Progress(int Position, int Range)
Definition: api_callback.cpp:255
CSG_PriorityQueue
Definition: mat_tools.h:275
SG_UI_Process_Set_Ready
bool SG_UI_Process_Set_Ready(void)
Definition: api_callback.cpp:305
CSG_Array_sLong
Definition: api_core.h:479
SG_Realloc
SAGA_API_DLL_EXPORT void * SG_Realloc(void *memblock, size_t size)
Definition: api_memory.cpp:77
SG_UI_Msg_Add_Error
void SG_UI_Msg_Add_Error(const char *Message)
Definition: api_callback.cpp:556
CSG_PriorityQueue::CSG_PriorityQueueItem
Definition: mat_tools.h:280
CSG_Index::Del_Entry
bool Del_Entry(sLong Position=-1)
Definition: mat_indexing.cpp:289
CSG_Index::Destroy
bool Destroy(void)
Definition: mat_indexing.cpp:83
CSG_PriorityQueue::Destroy
void Destroy(void)
Definition: mat_indexing.cpp:526