SAGA API  v9.9
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 bool 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 //---------------------------------------------------------
123 CSG_Index::CSG_Index(sLong nValues, CSG_Index_Compare &Compare)
124 {
125  _On_Construction();
126 
127  Create(nValues, Compare);
128 }
129 
130 //---------------------------------------------------------
131 bool 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 //---------------------------------------------------------
144 CSG_Index::CSG_Index(sLong nValues, CSG_Index_Compare *pCompare)
145 {
146  _On_Construction();
147 
148  Create(nValues, pCompare);
149 }
150 
151 //---------------------------------------------------------
152 bool 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 //---------------------------------------------------------
170 class CSG_Index_Compare_Int : public CSG_Index::CSG_Index_Compare
171 {
172 public:
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 //---------------------------------------------------------
187 CSG_Index::CSG_Index(sLong nValues, int *Values, bool bAscending)
188 {
189  _On_Construction();
190 
191  Create(nValues, Values, bAscending);
192 }
193 
194 //---------------------------------------------------------
195 bool 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 //---------------------------------------------------------
208 class CSG_Index_Compare_Double : public CSG_Index::CSG_Index_Compare
209 {
210 public:
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 //---------------------------------------------------------
227 CSG_Index::CSG_Index(sLong nValues, double *Values, bool bAscending)
228 {
229  _On_Construction();
230 
231  Create(nValues, Values, bAscending);
232 }
233 
234 //---------------------------------------------------------
235 bool 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 //---------------------------------------------------------
248 class CSG_Index_Compare_Function : public CSG_Index::CSG_Index_Compare
249 {
250 public:
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 //---------------------------------------------------------
262 CSG_Index::CSG_Index(sLong nValues, TSG_PFNC_Compare fCompare)
263 {
264  _On_Construction();
265 
266  Create(nValues, fCompare);
267 }
268 
269 //---------------------------------------------------------
270 bool 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 //---------------------------------------------------------
283 void CSG_Index::Show_Progress(bool bProgress)
284 {
285  m_bProgress = bProgress;
286 }
287 
288 //---------------------------------------------------------
289 bool 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 //---------------------------------------------------------
310 bool 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 //---------------------------------------------------------
330 bool 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 //---------------------------------------------------------
394 bool 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 //---------------------------------------------------------
520 CSG_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 //---------------------------------------------------------
528 CSG_PriorityQueue::~CSG_PriorityQueue(void)
529 {
530  Destroy();
531 }
532 
533 //---------------------------------------------------------
534 void 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 //---------------------------------------------------------
547 void 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 //---------------------------------------------------------
577 size_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 //---------------------------------------------------------
623 void 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 //---------------------------------------------------------
671 CSG_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 //---------------------------------------------------------
CSG_Index::Show_Progress
void Show_Progress(bool bProgress=true)
Definition: mat_indexing.cpp:283
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:520
CSG_Index::CSG_Index
CSG_Index(void)
Definition: mat_indexing.cpp:63
_TL
#define _TL(s)
Definition: api_core.h:1559
SG_INDEX_SWAP
#define SG_INDEX_SWAP(a, b)
Definition: mat_indexing.cpp:391
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:671
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:528
CSG_PriorityQueue::Add
void Add(CSG_PriorityQueueItem *pItem)
Definition: mat_indexing.cpp:623
CSG_Index::Invert
bool Invert(void)
Definition: mat_indexing.cpp:102
CSG_Index::Create
bool Create(sLong nValues, CSG_Index_Compare &Compare)
Definition: mat_indexing.cpp:131
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:534
CSG_Index::Add_Entry
bool Add_Entry(sLong Position=-1)
Definition: mat_indexing.cpp:289
CSG_PriorityQueue::Minimum
CSG_PriorityQueueItem * Minimum(void) const
Definition: mat_tools.h:309
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:277
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:553
CSG_PriorityQueue::CSG_PriorityQueueItem
Definition: mat_tools.h:282
CSG_Index::Del_Entry
bool Del_Entry(sLong Position=-1)
Definition: mat_indexing.cpp:310
CSG_Index::Destroy
bool Destroy(void)
Definition: mat_indexing.cpp:83
CSG_PriorityQueue::Destroy
void Destroy(void)
Definition: mat_indexing.cpp:547