Main MRPT website > C++ reference for MRPT 1.5.7
xsens_list.hpp
Go to the documentation of this file.
1 /* +---------------------------------------------------------------------------+
2  | Mobile Robot Programming Toolkit (MRPT) |
3  | http://www.mrpt.org/ |
4  | |
5  | Copyright (c) 2005-2014, Individual contributors, see AUTHORS file |
6  | See: http://www.mrpt.org/Authors - All rights reserved. |
7  | Released under BSD License. See details in http://www.mrpt.org/License |
8  +---------------------------------------------------------------------------+ */
9 
10 #ifndef _XSENS_LIST_HPP_2006_06_08
11 #define _XSENS_LIST_HPP_2006_06_08
12 
13 #ifndef _XSENS_LIST_H_2006_06_08
14 # include "xsens_list.h"
15 #endif
16 
17 #ifdef _XSENS_LIST_IO
18 # include <iostream>
19 #endif
20 
21 /* Jerome Monceaux : bilock@gmail.com
22  * Add a specific case for apple
23  */
24 #ifdef __APPLE__
25 # include <malloc/malloc.h>
26 #else
27 # include <malloc.h>
28 #endif
29 
30 #include <stdlib.h>
31 #include <string.h>
32 
33 namespace xsens {
34 
35 #define CMT_LIST_LINEAR_SEARCH_TRESHOLD 10
36 
37 template <typename T>
38 List<T>::List()
39 {
40  m_max = 16;
41  m_count = 0;
42  m_data = (T*) malloc(m_max * sizeof(T));
43 // _ASSERT((void*) m_data != (void*) 0x00392E90);
44  m_jcf = NULL;
45  m_manage = true;
46 }
47 
48 template <typename T>
49 List<T>::List(uint32_t size)
50 {
51  m_max = size;
52  if (m_max == 0)
53  m_max = 1;
54  m_count = 0;
55  m_data = (T*) malloc(m_max * sizeof(T));
56  m_jcf = NULL;
57  m_manage = true;
58 }
59 
60 template <typename T>
61 List<T>::List(const List<T>& src)
62 {
63  m_max = src.m_max;
64  if (m_max == 0)
65  m_max = 1;
66  m_count = src.m_count;
67  m_data = (T*) malloc(m_max * sizeof(T));
68  m_jcf = NULL;
69  if (m_count > 0)
70  memcpy(m_data,src.m_data,m_count*sizeof(T));
71  m_manage = true;
72 }
73 
74 template <typename T>
75 List<T>::List(const uint32_t size, const T* src)
76 {
77  m_max = size;
78  if (m_max == 0)
79  m_max = 1;
80  m_count = size;
81  m_data = (T*) malloc(m_max * sizeof(T));
82  m_jcf = NULL;
83  if (m_count > 0)
84  memcpy(m_data,src,m_count * sizeof(T));
85  m_manage = true;
86 }
87 
88 template <typename T>
89 List<T>::List(const uint32_t size, T* src, bool manage)
90 {
91  m_max = size;
92  m_count = size;
93  m_data = src;
94  m_jcf = NULL;
95  m_manage = manage;
96 }
97 
98 template <typename T>
99 List<T>::~List()
100 {
101  if (m_jcf != NULL)
102  delete m_jcf;
103  if (m_manage && m_data != NULL)
104  free(m_data);
105  m_jcf = NULL;
106  m_data = NULL;
107 }
108 
109 template <typename T>
110 void List<T>::deleteAndClear(void)
111 {
112  for (unsigned i=0;i<m_count;++i)
113  delete m_data[i];
114  m_count = 0;
115 }
116 
117 template <typename T>
118 void List<T>::freeAndClear(void)
119 {
120  for (unsigned i=0;i<m_count;++i)
121  free(m_data[i]);
122  m_count = 0;
123 }
124 
125 template <typename T>
126 void List<T>::clear(void)
127 {
128  m_count = 0;
129 }
130 
131 template <typename T>
132 void List<T>::resize(uint32_t newSize)
133 {
134  if (m_manage)
135  {
136  if (newSize == m_max)
137  return;
138  if (m_count > newSize)
139  m_max = m_count;
140  else
141  m_max = newSize;
142  if (m_max == 0)
143  m_max = 1; // size 0 is not allowed
144 
145  m_data = (T*) realloc(m_data,m_max * sizeof(T));
146  }
147 }
148 
149 template <typename T>
150 void List<T>::append(const T& item)
151 {
152  if (m_count == m_max)
153  resize(m_max + 1 + m_max/2);
154  m_data[m_count++] = item;
155 }
156 
157 template <typename T>
158 void List<T>::appendList(uint32_t count, const T* lst)
159 {
160  if (m_count+count > m_max)
161  resize(m_max + count + m_max/2);
162  for (unsigned i = 0; i < count; ++i)
163  m_data[m_count++] = lst[i];
164 }
165 
166 template <typename T>
167 void List<T>::appendDeepCopy(const List<T>& source)
168 {
169  if (m_max < source.m_count + m_count)
170  resize(source.m_count + m_count);
171 
172  for (uint32_t i = 0;i<source.m_count;++i)
173  m_data[m_count++] = new T(*source.m_data[i]);
174 }
175 
176 template <typename T>
177 void List<T>::appendShallowCopy(const List<T>& source)
178 {
179  if (m_max < source.m_count + m_count)
180  resize(source.m_count + m_count);
181 
182  for (uint32_t i = 0;i<source.m_count;++i)
183  m_data[m_count++] = source.m_data[i];
184 }
185 
186 template <typename T>
187 template <typename TB>
188 void List<T>::appendCopy(const TB& item)
189 {
190  if (m_count == m_max)
191  resize(m_max + 1 + m_max/2);
192  m_data[m_count++] = new TB(item);
193 }
194 
195 template <typename T>
196 template <typename TR>
197 void List<T>::appendRelated(const TR& item)
198 {
199  if (m_count == m_max)
200  resize(m_max + 1 + m_max/2);
201  m_data[m_count++] = item;
202 }
203 
204 template <typename T>
205 T& List<T>::last(void) const XSENS_LIST_THROW
206 {
207  #ifdef _XSENS_LIST_RANGE_CHECKS
208  if (m_count == 0)
209  throw "List.last: empty list";
210  #endif
211  return m_data[m_count-1];
212 }
213 
214 template <typename T>
215 T& List<T>::get(const uint32_t index) const XSENS_LIST_THROW
216 {
217  #ifdef _XSENS_LIST_RANGE_CHECKS
218  if (index >= m_count)
219  throw "List.get: index out of bounds";
220  #endif
221  if (index >= m_count)
222  return m_data[m_count-1];
223  return m_data[index];
224 }
225 
226 template <typename T>
227 void List<T>::insert(const T& item, const uint32_t index)
228 {
229  if (m_count == m_max)
230  resize(1 + m_max + (m_max >> 1));
231  for (unsigned i=m_count;i>index;--i)
232  m_data[i] = m_data[i-1];
233  if (index <= m_count)
234  m_data[index] = item;
235  else
236  m_data[m_count] = item;
237  m_count++;
238 }
239 
240 template <typename T>
241 template <typename TB>
242 void List<T>::insertCopy(const TB& item, const uint32_t index)
243 {
244  if (m_count == m_max)
245  resize(1 + m_max + (m_max >> 1));
246  for (unsigned i=m_count;i>index;--i)
247  m_data[i] = m_data[i-1];
248  if (index <= m_count)
249  m_data[index] = new TB(item);
250  else
251  m_data[m_count] = new TB(item);
252  m_count++;
253 }
254 
255 template <typename T>
256 T& List<T>::operator [] (const uint32_t index) const XSENS_LIST_THROW
257 {
258  #ifdef _XSENS_LIST_RANGE_CHECKS
259  if (index >= m_count)
260  throw "List[]: index out of bounds";
261  #endif
262  return m_data[index];
263 }
264 
265 #if defined(_XSENS_LIST_WITH_MATH) && defined(_XSENS_LIST_IO)
266 
267 template <typename T>
268 std::ostream& operator << (std::ostream& os, List<T>& t)
269 {
270  os << '[' << t.length() << "]{ ";
271  for (unsigned i=0 ; i<t.length() ; ++i)
272  os << t[i] << " ";
273  os << '}';
274  return os;
275 }
276 
277 #ifndef _CMTMATLABHEADERS
278 #define _CMTMATLABHEADERS
279  struct MatlabFileHeader {
280  char description[116];
281  int32_t data_offset1;
282  int32_t data_offset2;
283  int16_t version;
284  int16_t endian;
285  };
286 
287  struct MatlabDataHeader {
288  int32_t data_type;
289  int32_t n_bytes;
290  };
291 
292  struct MatlabMatrixHeader {
293  int32_t flags_data_type;
294  int32_t flags_data_size;
295  int32_t flags0,flags1;
296 
297  int32_t dimensions_data_type;
298  int32_t dimensions_data_size;
299  int32_t dimensions_m, dimensions_n;
300 
301  int32_t name_type;
302  int32_t name_length;
303  };
304 #endif
305 
306 //! save list of vectors as matrix in ".mat" file for MATLAB
307 template <typename T>
308 void List<T>::saveAsMatlab(const char* filename, const char *varname) const
309 {
310  // new header
311 
312  size_t i, j;
313  MatlabFileHeader file_header;
314  MatlabMatrixHeader matrix_header;
315  int32_t name_pad;
316  MatlabDataHeader inner_header;
317  MatlabDataHeader outer_header;
318 
319  FILE* fp = fopen(filename,"wb");
320  if (fp == NULL)
321  return;
322 
323  strcpy(file_header.description,"cmtMath/Xsens");
324  for (i = strlen(file_header.description); i <116; ++i)
325  file_header.description[i] = ' ';
326  file_header.data_offset1 = 0;
327  file_header.data_offset2 = 0;
328  file_header.version = 0x0100;
329  file_header.endian = (int16_t) 'M' << 8 | 'I';
330 
331  //matlab mat;
332 
333  matrix_header.flags_data_type = 6;
334  matrix_header.flags_data_size = 8;
335  matrix_header.flags0 = 6; // mxDOUBLE_CLASS (double precision array)
336  matrix_header.flags1 = 0;
337  matrix_header.dimensions_data_type = 5;
338  matrix_header.dimensions_data_size = 8;
339  matrix_header.dimensions_m = m_count;
340  matrix_header.dimensions_n = m_data[0]->size();
341  matrix_header.name_type = 1;
342 
343  if ( varname == (char *)NULL )
344  matrix_header.name_length = 0;
345  else
346  matrix_header.name_length = (int32_t) strlen(varname);
347 
348  name_pad = matrix_header.name_length & 7;
349 
350  inner_header.data_type = 9; // double
351  inner_header.n_bytes = sizeof(double) * m_count * matrix_header.dimensions_n;
352 
353  outer_header.data_type = 14;
354  outer_header.n_bytes = sizeof(matrix_header) + matrix_header.name_length + name_pad
355  + sizeof(MatlabDataHeader) + inner_header.n_bytes;
356 
357  fwrite((char*) &file_header,sizeof(MatlabFileHeader),1,fp);
358  fwrite((char*) &outer_header,sizeof(MatlabDataHeader),1,fp);
359  fwrite((char*) &matrix_header,sizeof(MatlabMatrixHeader),1,fp);
360  fwrite(varname,sizeof(char),matrix_header.name_length,fp);
361 
362  if (name_pad != 0)
363  fwrite("\0\0\0\0\0\0\0",sizeof(char),8-name_pad,fp);
364 
365  fwrite((char*) &inner_header,sizeof(MatlabDataHeader),1,fp);
366 
367  // write actual data
368  // column major order: ORDER == COL_ORDER
369  double tmp;
370  for ( j = 0; j < (size_t) matrix_header.dimensions_n; j++ )
371  for ( i = 0; i < m_count; i++ )
372  {
373  tmp = (*m_data[i])[(unsigned)j];
374  fwrite(&tmp,sizeof(double),1,fp);
375  }
376 
377  fclose(fp);
378 }
379 #endif // _XSENS_LIST_WITH_MATH && _XSENS_LIST_IO
380 
381 template <typename T>
382 void List<T>::qSort(uint32_t left, uint32_t right)
383 {
384  uint32_t l_hold, r_hold;
385  T pivot;
386 
387  l_hold = left;
388  r_hold = right;
389  pivot = m_data[left];
390  while (left < right)
391  {
392  while (!(m_data[right] < pivot) && (left < right))
393  right--;
394  if (left != right)
395  {
396  m_data[left] = m_data[right];
397  left++;
398  }
399  while (!(pivot < m_data[left]) && (left < right))
400  left++;
401  if (!(left == right))
402  {
403  m_data[right] = m_data[left];
404  right--;
405  }
406  }
407  m_data[left] = pivot;
408  if (l_hold < left)
409  qSort(l_hold, left-1);
410  if (r_hold > left)
411  qSort(left+1, r_hold);
412 }
413 
414 template <typename T>
415 void List<T>::qSortDeref(uint32_t left, uint32_t right)
416 {
417  uint32_t l_hold, r_hold;
418  T pivot;
419 
420  l_hold = left;
421  r_hold = right;
422  pivot = m_data[left];
423  while (left < right)
424  {
425  while (!(*m_data[right] < *pivot) && (left < right))
426  right--;
427  if (left != right)
428  {
429  m_data[left] = m_data[right];
430  left++;
431  }
432  while (!(*pivot < *m_data[left]) && (left < right))
433  left++;
434  if (!(left == right))
435  {
436  m_data[right] = m_data[left];
437  right--;
438  }
439  }
440  m_data[left] = pivot;
441  if (l_hold < left)
442  qSortDeref(l_hold, left-1);
443  if (r_hold > left)
444  qSortDeref(left+1, r_hold);
445 }
446 
447 //#define XSENS_LIST_QSORT
448 //#define XSENS_LIST_COMBSORT
449 #define XSENS_LIST_JOBSORT
450 // when nothing is defined, bubble sort is used
451 
452 template <typename T>
453 void List<T>::sortAscending(void)
454 {
455  if (m_count <= 1)
456  return;
457 #if defined(XSENS_LIST_QSORT)
458  qSort(0,m_count-1);
459 #elif defined(XSENS_LIST_COMBSORT)
460 
461  uint32_t gap = m_count;
462  double dgap;
463  uint32_t swaps = 0;
464  T temp;
465 
466  while (gap > 1 || swaps > 0)
467  {
468  if (gap > 1)
469  {
470  dgap = floor(((double) gap) / 1.247330950103979);
471  gap = (uint32_t) dgap;
472  if (gap == 10 || gap == 9)
473  gap = 11;
474  }
475 
476  uint32_t gappedCount = m_count-gap;
477  swaps = 0;
478  for (uint32_t i = 0; i < gappedCount; ++i)
479  {
480  if (m_data[i] > m_data[i+gap])
481  {
482  temp = m_data[i];
483  m_data[i] = m_data[i+gap];
484  m_data[i+gap] = temp;
485  ++swaps;
486  }
487  }
488  }
489 #elif defined(XSENS_LIST_JOBSORT)
490  struct Linker {
491  Linker *prev, *next;
492  uint32_t index;
493 
494  T item;
495  };
496 
497  Linker* list = (Linker*) malloc(m_count*sizeof(Linker));
498 
499  list[0].prev = NULL;
500  list[0].next = NULL;
501  list[0].index = 0;
502  list[0].item = m_data[0];
503 
504  Linker* curr = list;
505 
506  for (uint32_t i = 1; i < m_count; ++i)
507  {
508  list[i].index = i;
509  list[i].item = m_data[i];
510  if (m_data[i] < m_data[curr->index])
511  {
512  while (curr->prev != NULL)
513  {
514  curr = curr->prev;
515  if (!(m_data[i] < m_data[curr->index]))
516  {
517  // insert after this
518  list[i].next = curr->next;
519  list[i].prev = curr;
520  curr->next->prev = &list[i];
521  curr->next = &list[i];
522  curr = &list[i];
523  break;
524  }
525  }
526  if (curr != &list[i])
527  {
528  list[i].prev = NULL;
529  list[i].next = curr;
530  curr->prev = &list[i];
531  curr = &list[i];
532  }
533  }
534  else
535  {
536  while (curr->next != NULL)
537  {
538  curr = curr->next;
539  if (m_data[i] < m_data[curr->index])
540  {
541  // insert before this
542  list[i].next = curr;
543  list[i].prev = curr->prev;
544  curr->prev->next = &list[i];
545  curr->prev = &list[i];
546  curr = &list[i];
547  break;
548  }
549  }
550  if (curr != &list[i])
551  {
552  list[i].prev = curr;
553  list[i].next = NULL;
554  curr->next = &list[i];
555  curr = &list[i];
556  }
557  }
558  }
559 
560  // go to start of list
561  while (curr->prev != NULL) curr = curr->prev;
562 
563  // copy sorted list back
564  for (uint32_t i = 0; i < m_count; ++i)
565  {
566  m_data[i] = curr->item;
567  curr = curr->next;
568  }
569 
570  free(list);
571 #else
572  uint32_t swaps;
573  T temp;
574 
575  for (uint32_t i = 1; i < m_count; ++i)
576  {
577  swaps = 0;
578  for (uint32_t j = end-1; j >= i; --j)
579  {
580  if (m_data[j] < m_data[j-1])
581  {
582  temp = m_data[j];
583  m_data[j] = m_data[j-1];
584  m_data[j-1] = temp;
585  ++swaps;
586  }
587  }
588  if (swaps == 0)
589  break;
590  }
591 #endif
592 }
593 
594 template <typename T>
595 void List<T>::sortAscendingDeref(void)
596 {
597  if (m_count <= 1)
598  return;
599 #if defined(XSENS_LIST_QSORT)
600  qSortDeref(0,m_count-1);
601 #elif defined(XSENS_LIST_COMBSORT)
602 
603  uint32_t gap = m_count;
604  double dgap;
605  uint32_t swaps = 0;
606  T temp;
607 
608  while (gap > 1 || swaps > 0)
609  {
610  if (gap > 1)
611  {
612  dgap = floor(((double) gap) / 1.247330950103979);
613  gap = (uint32_t) dgap;
614  if (gap == 10 || gap == 9)
615  gap = 11;
616  }
617 
618  uint32_t gappedCount = m_count-gap;
619  swaps = 0;
620  for (uint32_t i = 0; i < gappedCount; ++i)
621  {
622  if (*m_data[i+gap] < *m_data[i])
623  {
624  temp = m_data[i];
625  m_data[i] = m_data[i+gap];
626  m_data[i+gap] = temp;
627  ++swaps;
628  }
629  }
630  }
631 #elif defined(XSENS_LIST_JOBSORT)
632  struct Linker {
633  Linker *prev, *next;
634  uint32_t index;
635 
636  T item;
637  };
638 
639  Linker* list = (Linker*) malloc(m_count*sizeof(Linker));
640 
641  list[0].prev = NULL;
642  list[0].next = NULL;
643  list[0].index = 0;
644  list[0].item = m_data[0];
645 
646  Linker* curr = list;
647 
648  for (uint32_t i = 1; i < m_count; ++i)
649  {
650  list[i].index = i;
651  list[i].item = m_data[i];
652  if (*m_data[i] < *m_data[curr->index])
653  {
654  while (curr->prev != NULL)
655  {
656  curr = curr->prev;
657  if (!(*m_data[i] < *m_data[curr->index]))
658  {
659  // insert after this
660  list[i].next = curr->next;
661  list[i].prev = curr;
662  curr->next->prev = &list[i];
663  curr->next = &list[i];
664  curr = &list[i];
665  break;
666  }
667  }
668  if (curr != &list[i])
669  {
670  list[i].prev = NULL;
671  list[i].next = curr;
672  curr->prev = &list[i];
673  curr = &list[i];
674  }
675  }
676  else
677  {
678  while (curr->next != NULL)
679  {
680  curr = curr->next;
681  if (*m_data[i] < *m_data[curr->index])
682  {
683  // insert before this
684  list[i].next = curr;
685  list[i].prev = curr->prev;
686  curr->prev->next = &list[i];
687  curr->prev = &list[i];
688  curr = &list[i];
689  break;
690  }
691  }
692  if (curr != &list[i])
693  {
694  list[i].prev = curr;
695  list[i].next = NULL;
696  curr->next = &list[i];
697  curr = &list[i];
698  }
699  }
700  }
701 
702  // go to start of list
703  while (curr->prev != NULL) curr = curr->prev;
704 
705  // copy sorted list back
706  for (uint32_t i = 0; i < m_count; ++i)
707  {
708  m_data[i] = curr->item;
709  curr = curr->next;
710  }
711 
712  free(list);
713 #else
714  uint32_t swaps;
715  T temp;
716 
717  for (uint32_t i = 1; i < m_count; ++i)
718  {
719  swaps = 0;
720  for (uint32_t j = end-1; j >= i; --j)
721  {
722  if (*(m_data[j]) < *(m_data[j-1]))
723  {
724  temp = m_data[j];
725  m_data[j] = m_data[j-1];
726  m_data[j-1] = temp;
727  ++swaps;
728  }
729  }
730  if (swaps == 0)
731  break;
732  }
733 #endif
734 }
735 
736 template <typename T>
737 template <typename T2>
738 void List<T>::twinSortAscending(List<T2>& twin)
739 {
740  if (m_count <= 1)
741  return;
742 
743  #ifdef _XSENS_LIST_RANGE_CHECKS
744  if (m_count != twin.m_count)
745  throw "List.twinSortAscending: sizes do not match";
746  #endif
747  uint32_t iteration = 0;
748  uint32_t mini;
749  T tmp;
750  T2 tmp2;
751  if (m_count > 1)
752  while (iteration < m_count-1)
753  {
754  mini = iteration;
755  for (uint32_t i=iteration+1;i<m_count;++i)
756  {
757  if (m_data[i] < m_data[mini])
758  mini = i;
759  }
760  if (mini != iteration)
761  {
762  tmp = m_data[mini];
763  m_data[mini] = m_data[iteration];
764  m_data[iteration] = tmp;
765 
766  tmp2 = twin.m_data[mini];
767  twin.m_data[mini] = twin.m_data[iteration];
768  twin.m_data[iteration] = tmp2;
769  }
770  ++iteration;
771  }
772 }
773 
774 template <typename T>
775 void List<T>::remove(const uint32_t index) XSENS_LIST_THROW
776 {
777  #ifdef _XSENS_LIST_RANGE_CHECKS
778  if (index >= m_count)
779  throw "List.remove: index out of bounds";
780  #endif
781  if (index == m_count-1)
782  {
783  --m_count;
784  return;
785  }
786  --m_count;
787  for (unsigned i = index;i < m_count;++i)
788  m_data[i] = m_data[i+1];
789 }
790 
791 template <typename T>
792 void List<T>::removeTail(const uint32_t count) XSENS_LIST_THROW
793 {
794  #ifdef _XSENS_LIST_RANGE_CHECKS
795  if (count > m_count)
796  throw "List.removeTail: list size less than remove count";
797  #endif
798  if (m_count > count)
799  {
800  m_count -= count;
801  return;
802  }
803  m_count = 0;
804 }
805 
806 template <typename T>
807 void List<T>::deleteAndRemoveTail(const uint32_t count) XSENS_LIST_THROW
808 {
809  #ifdef _XSENS_LIST_RANGE_CHECKS
810  if (count > m_count)
811  throw "List.deleteAndRemoveTail: list size less than remove count";
812  #endif
813  if (m_count > count)
814  {
815  for (unsigned i = 0;i < count;++i)
816  delete m_data[--m_count];
817  return;
818  }
819  deleteAndClear();
820 }
821 
822 template <typename T>
823 void List<T>::freeAndRemoveTail(const uint32_t count) XSENS_LIST_THROW
824 {
825  #ifdef _XSENS_LIST_RANGE_CHECKS
826  if (count > m_count)
827  throw "List.freeAndRemoveTail: list size less than remove count";
828  #endif
829  if (m_count > count)
830  {
831  for (unsigned i = 0;i < count;++i)
832  free(m_data[--m_count]);
833  return;
834  }
835  freeAndClear();
836 }
837 
838 template <typename T>
839 uint32_t List<T>::removeDuplicateEntries(void)
840 {
841  uint32_t removed = 0;
842  for (uint32_t i=0;i < m_count; ++i)
843  {
844  for (uint32_t j=i+1;j < m_count; ++j)
845  {
846  if (m_data[i] == m_data[j])
847  {
848  remove(j);
849  ++removed;
850  --j;
851  }
852  }
853  }
854  return removed;
855 }
856 
857 template <typename T>
858 uint32_t List<T>::removeDuplicateEntriesDeref(void)
859 {
860  uint32_t removed = 0;
861  for (uint32_t i=0;i < m_count; ++i)
862  {
863  for (uint32_t j=i+1;j < m_count; ++j)
864  {
865  if (*(m_data[i]) == *(m_data[j]))
866  {
867  remove(j);
868  ++removed;
869  --j;
870  }
871  }
872  }
873  return removed;
874 }
875 
876 template <typename T>
877 void List<T>::deleteAndRemove(const uint32_t index) XSENS_LIST_THROW
878 {
879  #ifdef _XSENS_LIST_RANGE_CHECKS
880  if (index >= m_count)
881  throw "List.deleteAndRemove: index out of bounds";
882  #endif
883  delete m_data[index];
884  if (index == m_count-1)
885  {
886  --m_count;
887  return;
888  }
889  --m_count;
890  for (unsigned i = index;i < m_count;++i)
891  m_data[i] = m_data[i+1];
892 }
893 
894 template <typename T>
895 void List<T>::freeAndRemove(const uint32_t index) XSENS_LIST_THROW
896 {
897  #ifdef _XSENS_LIST_RANGE_CHECKS
898  if (index >= m_count)
899  throw "List.freeAndRemove: index out of bounds";
900  #endif
901  free(m_data[index]);
902  if (index == m_count-1)
903  {
904  --m_count;
905  return;
906  }
907  --m_count;
908  for (unsigned i = index;i < m_count;++i)
909  m_data[i] = m_data[i+1];
910 }
911 
912 template <typename T>
913 template <typename TB>
914 uint32_t List<T>::find(const TB& item) const
915 {
916  for (uint32_t i=0;i<m_count;++i)
917  if (((const T*)m_data)[i] == item)
918  return i;
919  return XSENS_LIST_NOTFOUND;
920 }
921 
922 template <typename T>
923 uint32_t List<T>::find(const T item, InequalityFunction fnc) const
924 {
925  for (uint32_t i=0;i<m_count;++i)
926  if (!fnc(m_data[i],item))
927  return i;
928  return XSENS_LIST_NOTFOUND;
929 }
930 
931 template <typename T>
932 template <typename TB>
933 uint32_t List<T>::findDeref(const TB& item) const
934 {
935  for (uint32_t i=0;i<m_count;++i)
936  if (*(m_data[i]) == item)
937  return i;
938  return XSENS_LIST_NOTFOUND;
939 }
940 
941 template <typename T>
942 template <typename TB>
943 uint32_t List<T>::findSorted(const TB& item) const
944 {
945  if (m_count < CMT_LIST_LINEAR_SEARCH_TRESHOLD) // for small lists, it is faster to simply walk the list
946  return find(item);
947 
948  uint32_t x = m_count;
949  uint32_t n = 1;
950  uint32_t i;
951 
952  while(x >= n)
953  {
954  i = (x + n) >> 1;
955 
956  if (m_data[i-1] == item)
957  return i-1;
958  if (m_data[i-1] < item)
959  n = i+1;
960  else
961  x = i-1;
962  }
963  return XSENS_LIST_NOTFOUND;
964 }
965 
966 template <typename T>
967 template <typename TB>
968 uint32_t List<T>::findSortedDeref(const TB& item) const
969 {
970  if (m_count < CMT_LIST_LINEAR_SEARCH_TRESHOLD) // for small lists, it is faster to simply walk the list
971  return findDeref(item);
972 
973  uint32_t x = m_count;
974  uint32_t n = 1;
975  uint32_t i;
976 
977  while(x >= n)
978  {
979  i = (x + n) >> 1;
980 
981  if (*(m_data[i-1]) == item)
982  return i-1;
983  if (*(m_data[i-1]) < item)
984  n = i+1;
985  else
986  x = i-1;
987  }
988  return XSENS_LIST_NOTFOUND;
989 }
990 
991 template <typename T>
992 uint32_t List<T>::insertSorted(const T& item)
993 {
994  uint32_t i;
995  if (m_count < CMT_LIST_LINEAR_SEARCH_TRESHOLD)
996  {
997  for (i=0;i<m_count;++i)
998  if (item < m_data[i])
999  {
1000  insert(item,i);
1001  return i;
1002  }
1003  append(item);
1004  return m_count-1;
1005  }
1006  else
1007  {
1008  uint32_t x = m_count;
1009  uint32_t n = 1;
1010 
1011  while(x >= n)
1012  {
1013  i = (x + n) >> 1;
1014 
1015  if (m_data[i-1] == item)
1016  {
1017  insert(item,i-1);
1018  return i-1;
1019  }
1020  if (m_data[i-1] < item)
1021  n = i+1;
1022  else
1023  x = i-1;
1024  }
1025  insert(item,n-1);
1026  return n-1;
1027  }
1028 }
1029 
1030 template <typename T>
1031 uint32_t List<T>::insertSortedDeref(const T& item)
1032 {
1033  uint32_t i;
1034  if (m_count < CMT_LIST_LINEAR_SEARCH_TRESHOLD)
1035  {
1036  for (i=0;i<m_count;++i)
1037  if (*item < *m_data[i])
1038  {
1039  insert(item,i);
1040  return i;
1041  }
1042  append(item);
1043  return m_count-1;
1044  }
1045  else
1046  {
1047  uint32_t x = m_count;
1048  uint32_t n = 1;
1049 
1050  while(x >= n)
1051  {
1052  i = (x + n) >> 1;
1053 
1054  if (*(m_data[i-1]) == *item)
1055  {
1056  insert(item,i-1);
1057  return i-1;
1058  }
1059  if (*(m_data[i-1]) < *item)
1060  n = i+1;
1061  else
1062  x = i-1;
1063  }
1064  insert(item,n-1);
1065  return n-1;
1066  }
1067 }
1068 
1069 template <typename T>
1070 template <typename TB>
1071 uint32_t List<T>::insertSortedCopy(const TB& item)
1072 {
1073  uint32_t i;
1074  if (m_count < CMT_LIST_LINEAR_SEARCH_TRESHOLD)
1075  {
1076  for (i=0;i<m_count;++i)
1077  if (item < m_data[i])
1078  {
1079  insertCopy<TB>(item,i);
1080  return i;
1081  }
1082  append(item);
1083  return m_count-1;
1084  }
1085  else
1086  {
1087  uint32_t x = m_count;
1088  uint32_t n = 1;
1089 
1090  while(x >= n)
1091  {
1092  i = (x + n) >> 1;
1093 
1094  if (m_data[i-1] == item)
1095  {
1096  insertCopy<TB>(item,i-1);
1097  return i-1;
1098  }
1099  if (m_data[i-1] < item)
1100  n = i+1;
1101  else
1102  x = i-1;
1103  }
1104  insertCopy<TB>(item,n-1);
1105  return n-1;
1106  }
1107 }
1108 
1109 template <typename T>
1110 void List<T>::deleteItemsOnDestroy(void)
1111 {
1112  if (m_jcf != NULL)
1113  {
1114  m_jcf->disable();
1115  delete m_jcf;
1116  }
1117  m_jcf = new JanitorClassFunc<List<T>, void>(*this,&List<T>::deleteAndClear);
1118 }
1119 
1120 template <typename T>
1121 void List<T>::freeItemsOnDestroy(void)
1122 {
1123  if (m_jcf != NULL)
1124  {
1125  m_jcf->disable();
1126  delete m_jcf;
1127  }
1128  m_jcf = new JanitorClassFunc<List<T>, void>(*this,&List<T>::freeAndClear);
1129 }
1130 
1131 template <typename T>
1132 template <typename TB>
1133 void List<T>::isDeepCopyOf(const List<T>& source)
1134 {
1135  m_count = 0;
1136  if (m_max < source.m_count)
1137  resize(source.m_count);
1138  m_count = source.m_count;
1139  for (uint32_t i = 0;i<m_count;++i)
1140  m_data[i] = new TB(*source.m_data[i]);
1141 }
1142 
1143 template <typename T>
1144 void List<T>::isShallowCopyOf(const List<T>& x)
1145 {
1146  m_count = 0;
1147  if (m_max < x.m_count)
1148  resize(x.m_count);
1149  m_count = x.m_count;
1150  for (uint32_t i = 0;i<m_count;++i)
1151  m_data[i] = x.m_data[i];
1152 }
1153 
1154 template <typename T>
1155 void List<T>::swap(const uint32_t i, const uint32_t j) XSENS_LIST_THROW
1156 {
1157  #ifdef _XSENS_LIST_RANGE_CHECKS
1158  if (i >= m_count || j >= m_count)
1159  throw "List.swap: index out of bounds";
1160  #endif
1161  T tmp = m_data[i];
1162  m_data[i] = m_data[j];
1163  m_data[j] = tmp;
1164 }
1165 
1166 template <typename T>
1167 void List<T>::reverse(void)
1168 {
1169  uint32_t half = m_count / 2;
1170  for (uint32_t i = 0, end=m_count-1; i < half; ++i,--end)
1171  {
1172  T tmp = m_data[i];
1173  m_data[i] = m_data[end];
1174  m_data[end] = tmp;
1175  }
1176 }
1177 
1178 } // end of xsens namespace
1179 
1180 #endif // _XSENS_LIST_HPP_2006_06_08
1181 
xsens::JanitorClassFunc
Class function calling janitor class.
Definition: xsens_janitors.h:137
xsens::List
Dynamic list class.
Definition: xsens_list.h:61
xsens::List::append
void append(const T &item)
Adds an item to the end of the list.
Definition: xsens_list.hpp:150
xsens::List::freeItemsOnDestroy
void freeItemsOnDestroy(void)
Definition: xsens_list.hpp:1121
xsens::List::appendShallowCopy
void appendShallowCopy(const List< T > &source)
Adds the contents of the source list to the end of the list.
Definition: xsens_list.hpp:177
xsens::List::m_count
uint32_t m_count
The number of items currently in the list.
Definition: xsens_list.h:72
xsens::List::insertSortedDeref
uint32_t insertSortedDeref(const T &item)
Assumes the list is sorted by dereferenced values and inserts the item at the appropriate spot.
Definition: xsens_list.hpp:1031
xsens::List::removeDuplicateEntries
uint32_t removeDuplicateEntries(void)
Removes any duplicate entries and returns the number of items removed. Items are compared directly.
Definition: xsens_list.hpp:839
xsens::List::m_data
T * m_data
The array containing the items.
Definition: xsens_list.h:70
xsens::List::operator[]
T & operator[](const uint32_t index) const XSENS_LIST_THROW
Retrieves the item at the given index. An index beyond the end probably causes an exception.
Definition: xsens_list.hpp:256
xsens::List::get
T & get(const uint32_t index) const XSENS_LIST_THROW
Retrieves the item at the given index. An index beyond the end returns the first item.
Definition: xsens_list.hpp:215
xsens::List::findDeref
uint32_t findDeref(const TB &item) const
Finds an item in an unsorted list (walk over all items) using the T::== operator on dereferenced list...
Definition: xsens_list.hpp:933
xsens::List::findSorted
uint32_t findSorted(const TB &item) const
Finds an item in a sorted list (binary search) using the T::== and T::< operators.
Definition: xsens_list.hpp:943
xsens::List::appendDeepCopy
void appendDeepCopy(const List< T > &source)
Adds the contents of the source list to the end of the list.
Definition: xsens_list.hpp:167
xsens::List::last
T & last(void) const XSENS_LIST_THROW
Retrieves the last item.
Definition: xsens_list.hpp:205
xsens::List::sortAscendingDeref
void sortAscendingDeref(void)
Sorts the list in an ascending order, using the T::< operator on dereferenced list items.
Definition: xsens_list.hpp:595
xsens::List::List
List()
Standard constructor, creates an empty list with some room for items.
Definition: xsens_list.hpp:38
xsens::List::deleteAndRemove
void deleteAndRemove(const uint32_t index) XSENS_LIST_THROW
Removes an item at the given index in the list.
Definition: xsens_list.hpp:877
xsens::List::reverse
void reverse(void)
Reverse the order of the list, useful for sorted lists that are read/created in the reverse order.
Definition: xsens_list.hpp:1167
xsens::List::deleteAndRemoveTail
void deleteAndRemoveTail(const uint32_t count) XSENS_LIST_THROW
Definition: xsens_list.hpp:807
xsens::List::freeAndRemove
void freeAndRemove(const uint32_t index) XSENS_LIST_THROW
Removes an item at the given index in the list.
Definition: xsens_list.hpp:895
xsens::List::~List
~List()
Destroy the list. This does NOT automatically delete items IN the list.
Definition: xsens_list.hpp:99
xsens::List::find
uint32_t find(const TB &item) const
Finds an item in an unsorted list (walk over all items) using the T::== operator.
Definition: xsens_list.hpp:914
xsens::List::qSortDeref
void qSortDeref(uint32_t left, uint32_t right)
Sorts the list in an ascending order, using the T::< operator on dereferenced list items.
Definition: xsens_list.hpp:415
xsens::List::findSortedDeref
uint32_t findSortedDeref(const TB &item) const
Finds an item in a sorted list (binary search) using the T::== and T::< operators on dereferenced lis...
Definition: xsens_list.hpp:968
xsens::List::insertCopy
void insertCopy(const TB &item, const uint32_t index)
Inserts a copy of the referenced item at the given index, shifting any items below it down one spot.
Definition: xsens_list.hpp:242
xsens::List::isShallowCopyOf
void isShallowCopyOf(const List< T > &source)
Overwrites the current list with a shallow (memcopy) copy of another list.
Definition: xsens_list.hpp:1144
xsens::List::swap
void swap(const uint32_t i, const uint32_t j) XSENS_LIST_THROW
Swaps two items in the list.
Definition: xsens_list.hpp:1155
xsens::List::clear
void clear(void)
Clears the list without explicitly deleting anything.
Definition: xsens_list.hpp:126
xsens::List::appendList
void appendList(uint32_t count, const T *lst)
Adds a number of items to the end of the list.
Definition: xsens_list.hpp:158
xsens::List::appendCopy
void appendCopy(const TB &item)
Adds a copy of a referenced item to the end of the list.
Definition: xsens_list.hpp:188
xsens::List::removeTail
void removeTail(const uint32_t count) XSENS_LIST_THROW
Removes items from the end of the list.
Definition: xsens_list.hpp:792
xsens::List::deleteItemsOnDestroy
void deleteItemsOnDestroy(void)
Definition: xsens_list.hpp:1110
xsens::List::insertSortedCopy
uint32_t insertSortedCopy(const TB &item)
Assumes the list is sorted and inserts a copy of the referenced item at the appropriate spot.
Definition: xsens_list.hpp:1071
xsens::List::freeAndClear
void freeAndClear(void)
Calls free for all items in the list and then clears the list.
Definition: xsens_list.hpp:118
xsens::List::removeDuplicateEntriesDeref
uint32_t removeDuplicateEntriesDeref(void)
Removes any duplicate entries and returns the number of items removed. Items are compared after deref...
Definition: xsens_list.hpp:858
xsens::List::insert
void insert(const T &item, const uint32_t index)
Inserts an item at the given index, shifting any items below it down one spot.
Definition: xsens_list.hpp:227
xsens::List::resize
void resize(uint32_t newSize)
Resizes the list to at least the given size.
Definition: xsens_list.hpp:132
xsens::List::remove
void remove(const uint32_t index) XSENS_LIST_THROW
Removes an item at the given index in the list.
Definition: xsens_list.hpp:775
xsens::List::insertSorted
uint32_t insertSorted(const T &item)
Assumes the list is sorted and inserts the item at the appropriate spot.
Definition: xsens_list.hpp:992
xsens::List::deleteAndClear
void deleteAndClear(void)
Calls delete for all items in the list and then clears the list.
Definition: xsens_list.hpp:110
xsens::List::freeAndRemoveTail
void freeAndRemoveTail(const uint32_t count) XSENS_LIST_THROW
Definition: xsens_list.hpp:823
xsens::List::twinSortAscending
void twinSortAscending(List< T2 > &twin)
Sorts the first list in an ascending order, using the T::< operator, the second list will be updated ...
Definition: xsens_list.hpp:738
xsens::List::appendRelated
void appendRelated(const TR &item)
Adds a related item to the end of the list, using the T = TR operator.
Definition: xsens_list.hpp:197
xsens::List::qSort
void qSort(uint32_t left, uint32_t right)
Sorts the list in an ascending order, using the T::< operator.
Definition: xsens_list.hpp:382
xsens::List::sortAscending
void sortAscending(void)
Sorts the list in an ascending order, using the T::< operator.
Definition: xsens_list.hpp:453
xsens::List::isDeepCopyOf
void isDeepCopyOf(const List< T > &source)
Make a copy of the list, duplicating list items i with: copy[i] = new TB(*source[i])
Definition: xsens_list.hpp:1133
t
GLdouble GLdouble t
Definition: glext.h:3610
n
GLenum GLsizei n
Definition: glext.h:4618
end
GLuint GLuint end
Definition: glext.h:3512
index
GLuint index
Definition: glext.h:3891
count
GLuint GLuint GLsizei count
Definition: glext.h:3512
src
GLuint src
Definition: glext.h:6303
x
GLenum GLint x
Definition: glext.h:3516
size
GLsizeiptr size
Definition: glext.h:3779
source
GLsizei GLsizei GLchar * source
Definition: glext.h:3908
mrpt::system::os::strcpy
char BASE_IMPEXP * strcpy(char *dest, size_t destSize, const char *source) MRPT_NO_THROWS
An OS-independent version of strcpy.
Definition: os.cpp:296
mrpt::system::os::memcpy
void BASE_IMPEXP memcpy(void *dest, size_t destSize, const void *src, size_t copyCount) MRPT_NO_THROWS
An OS and compiler independent version of "memcpy".
Definition: os.cpp:358
mrpt::system::os::fopen
FILE BASE_IMPEXP * fopen(const char *fileName, const char *mode) MRPT_NO_THROWS
An OS-independent version of fopen.
Definition: os.cpp:255
mrpt::system::os::fclose
int BASE_IMPEXP void BASE_IMPEXP fclose(FILE *f)
An OS-independent version of fclose.
Definition: os.cpp:272
operator<<
std::ostream & operator<<(std::ostream &out, MD5 md5)
Definition: md5.cpp:419
version
int version
Definition: mrpt_jpeglib.h:898
mrpt::utils::find
const_iterator find(const KEY &key) const
Definition: ts_hash_map.h:139
xsens
The namespace of all Xsens software since 2006.
Definition: cmt1.cpp:92
int16_t
__int16 int16_t
Definition: rptypes.h:45
int32_t
__int32 int32_t
Definition: rptypes.h:48
uint32_t
unsigned __int32 uint32_t
Definition: rptypes.h:49
xsens_list.h
XSENS_LIST_NOTFOUND
#define XSENS_LIST_NOTFOUND
Definition: xsens_list.h:39
XSENS_LIST_THROW
#define XSENS_LIST_THROW
Definition: xsens_list.h:45
CMT_LIST_LINEAR_SEARCH_TRESHOLD
#define CMT_LIST_LINEAR_SEARCH_TRESHOLD
Definition: xsens_list.hpp:35


Page generated by Doxygen 1.9.1 for MRPT 1.5.7 Git: 5902e14cc Wed Apr 24 15:04:01 2019 +0200 at mar 26 may 2026 13:12:03 CEST