xsens_imu
xsens_list.h
Go to the documentation of this file.
1 #ifndef XSENS_MONOLITHIC
2 
30 #endif
31 #ifndef XSENS_LIST_H
32 #define XSENS_LIST_H
33 
34 #ifndef XSENS_MONOLITHIC
35 #ifndef PSTDINT_H_INCLUDED
36 # include "pstdint.h"
37 #endif
38 #endif
39 
40 #ifndef XSENS_EXCEPTION_H
41 #include "xsens_exception.h"
42 #endif
43 
44 #ifndef XSENS_JANITORS_H
45 # include "xsens_janitors.h"
46 #endif
47 
48 
49 #define XSENS_LIST_NOTFOUND 0xFFFFFFFF
50 
51 #ifdef _XSENS_LIST_RANGE_CHECKS
52 # ifdef _MSC_VER
53 # define XSENS_LIST_THROW throw(...)
54 # else
55 # define XSENS_LIST_THROW
56 # endif
57 #else
58 # define XSENS_LIST_THROW
59 #endif
60 
61 #include <stdlib.h>
62 #include <malloc.h>
63 #include <string.h>
64 
65 namespace xsens {
66 
67 #define XSENS_LIST_LINEAR_SEARCH_TRESHOLD 10
68 
78  template <typename T>
79  class List
80  {
81  private:
82  void operator = (const List& list);
83  void qSort(uint32_t left, uint32_t right);
86  void qSortDeref(uint32_t left, uint32_t right);
87 
88  protected:
89  T* m_data;
90  uint32_t m_max;
91  uint32_t m_count;
92  JanitorClassFunc<List<T> >* m_jcf;
93  bool m_manage;
94 
96  List(const uint32_t size, T* src, bool manage);
97  public:
98 
100  typedef int32_t (*cmpFunc) (const T&,const T&);
101 
103  List();
105  List(const uint32_t size);
107  List(const List<T>& src);
109  List(const uint32_t size, const T* src);
111  ~List();
112 
114  void deleteAndClear(void);
116  void freeAndClear(void);
118  void clear(void);
120  void resize(uint32_t newSize);
122  void append(const T& item);
124  void appendList(uint32_t count, const T* lst);
126  void appendDeepCopy(const List<T>& source);
128  void appendShallowCopy(const List<T>& source);
130  template <typename TB>
131  void appendCopy(const TB& item);
133  template <typename TR>
134  void appendRelated(const TR& item);
136  void remove(const uint32_t index) XSENS_LIST_THROW;
138  void swap(const uint32_t i, const uint32_t j) XSENS_LIST_THROW;
140  void deleteAndRemove(const uint32_t index) XSENS_LIST_THROW;
142  void freeAndRemove(const uint32_t index) XSENS_LIST_THROW;
144  T& last(void) const XSENS_LIST_THROW;
146  T& minVal(void) const XSENS_LIST_THROW;
148  T& maxVal(void) const XSENS_LIST_THROW;
150  T& get(const uint32_t index) const XSENS_LIST_THROW;
152  T& operator [] (const uint32_t index) const XSENS_LIST_THROW;
154  void insert(const T& item, const uint32_t index);
156  template <typename TB>
157  void insertCopy(const TB& item, const uint32_t index);
159  uint32_t insertSorted(const T& item);
161  uint32_t insertSortedDeref(const T& item);
163  template <typename TB>
164  uint32_t insertSortedCopy(const TB& item);
166  uint32_t length(void) const { return m_count; }
168  uint32_t count(void) const { return m_count; }
170  void sortAscending(void);
172  void sortAscendingDeref(void);
174  template <typename T2>
175  void twinSortAscending(List<T2>& twin);
177  template <typename TB>
178  uint32_t find(const TB& item) const;
180  template <typename TB>
181  uint32_t findDeref(const TB& item) const;
183  template <typename TB>
184  uint32_t findSorted(const TB& item) const;
186  template <typename TB>
187  uint32_t findSortedDeref(const TB& item) const;
188 
190  template <typename TB>
191  uint32_t findSortedForInsert(const TB& item) const;
193  template <typename TB>
194  uint32_t findSortedDerefForInsert(const TB& item) const;
195 
197  template <typename TB>
198  uint32_t reverseFind(const TB& item) const;
200  template <typename TB>
201  uint32_t reverseFindDeref(const TB& item) const;
202 
204  void reverse(void);
206  void removeTail(const uint32_t count) XSENS_LIST_THROW;
207  void deleteAndRemoveTail(const uint32_t count) XSENS_LIST_THROW;
208  void freeAndRemoveTail(const uint32_t count) XSENS_LIST_THROW;
209 
211  typedef int32_t (__cdecl * InequalityFunction)(const T&, const T&);
213  uint32_t find(const T item, InequalityFunction fnc) const;
214 
215  void deleteItemsOnDestroy(void);
216  void freeItemsOnDestroy(void);
217 
219  uint32_t removeDuplicateEntries(void);
221  uint32_t removeDuplicateEntriesDeref(void);
222 
224  template <typename TB>
225  void isDeepCopyOf(const List<T>& source);
227  void isShallowCopyOf(const List<T>& source);
228 
230  const T* getBuffer(void) const { return m_data; }
232  template <typename TB>
233  bool operator == (const List<TB>& lst);
234  };
235 
236 
237 template <typename T>
238 List<T>::List()
239 {
240  m_max = 16;
241  m_count = 0;
242  m_data = (T*) malloc(m_max * sizeof(T));
243  if (!m_data)
244  throw std::bad_alloc();
245  m_jcf = NULL;
246  m_manage = true;
247 }
248 
249 template <typename T>
250 List<T>::List(uint32_t size)
251 {
252  m_max = size;
253  if (m_max == 0)
254  m_max = 1;
255  m_count = 0;
256  m_data = (T*) malloc(m_max * sizeof(T));
257  if (!m_data)
258  throw std::bad_alloc();
259  m_jcf = NULL;
260  m_manage = true;
261 }
262 
263 template <typename T>
264 List<T>::List(const List<T>& src)
265 {
266  m_max = src.m_max;
267  if (m_max == 0)
268  m_max = 1;
269  m_count = src.m_count;
270  m_data = (T*) malloc(m_max * sizeof(T));
271  if (!m_data)
272  throw std::bad_alloc();
273  m_jcf = NULL;
274  if (m_count > 0)
275  memcpy(m_data,src.m_data,m_count*sizeof(T));
276  m_manage = true;
277 }
278 
279 template <typename T>
280 List<T>::List(const uint32_t size, const T* src)
281 {
282  m_max = size;
283  if (m_max == 0)
284  m_max = 1;
285  m_count = size;
286  m_data = (T*) malloc(m_max * sizeof(T));
287  if (!m_data)
288  throw std::bad_alloc();
289  m_jcf = NULL;
290  if (m_count > 0)
291  memcpy(m_data,src,m_count * sizeof(T));
292  m_manage = true;
293 }
294 
295 template <typename T>
296 List<T>::List(const uint32_t size, T* src, bool manage)
297 {
298  m_max = size;
299  m_count = size;
300  m_data = src;
301  m_jcf = NULL;
302  m_manage = manage;
303 }
304 
305 template <typename T>
306 List<T>::~List()
307 {
308  if (m_jcf != NULL)
309  delete m_jcf;
310  if (m_manage && m_data != NULL)
311  free(m_data);
312  m_jcf = NULL;
313  m_data = NULL;
314 }
315 
316 template <typename T>
317 void List<T>::deleteAndClear(void)
318 {
319  for (unsigned i=0;i<m_count;++i)
320  delete m_data[i];
321  m_count = 0;
322 }
323 
324 template <typename T>
325 void List<T>::freeAndClear(void)
326 {
327  for (unsigned i=0;i<m_count;++i)
328  free(m_data[i]);
329  m_count = 0;
330 }
331 
332 template <typename T>
333 void List<T>::clear(void)
334 {
335  m_count = 0;
336 }
337 
338 template <typename T>
339 void List<T>::resize(uint32_t newSize)
340 {
341  if (m_manage)
342  {
343  if (newSize == m_max)
344  return;
345  if (m_count > newSize)
346  m_max = m_count;
347  else
348  m_max = newSize;
349  if (m_max == 0)
350  m_max = 1; // size 0 is not allowed
351 
352  m_data = (T*) realloc(m_data,m_max * sizeof(T));
353  }
354 }
355 
356 template <typename T>
357 void List<T>::append(const T& item)
358 {
359  if (m_count == m_max)
360  resize(m_max + 1 + m_max/2);
361  m_data[m_count++] = item;
362 }
363 
364 template <typename T>
365 void List<T>::appendList(uint32_t count, const T* lst)
366 {
367  if (m_count+count > m_max)
368  resize(m_max + count + m_max/2);
369  for (unsigned i = 0; i < count; ++i)
370  m_data[m_count++] = lst[i];
371 }
372 
373 template <typename T>
374 void List<T>::appendDeepCopy(const List<T>& source)
375 {
376  if (m_max < source.m_count + m_count)
377  resize(source.m_count + m_count);
378 
379  for (uint32_t i = 0;i<source.m_count;++i)
380  m_data[m_count++] = new T(*source.m_data[i]);
381 }
382 
383 template <typename T>
384 void List<T>::appendShallowCopy(const List<T>& source)
385 {
386  if (m_max < source.m_count + m_count)
387  resize(source.m_count + m_count);
388 
389  for (uint32_t i = 0;i<source.m_count;++i)
390  m_data[m_count++] = source.m_data[i];
391 }
392 
393 template <typename T>
394 template <typename TB>
395 void List<T>::appendCopy(const TB& item)
396 {
397  if (m_count == m_max)
398  resize(m_max + 1 + m_max/2);
399  m_data[m_count++] = new TB(item);
400 }
401 
402 template <typename T>
403 template <typename TR>
404 void List<T>::appendRelated(const TR& item)
405 {
406  if (m_count == m_max)
407  resize(m_max + 1 + m_max/2);
408  m_data[m_count++] = item;
409 }
410 
411 template <typename T>
412 T& List<T>::last(void) const XSENS_LIST_THROW
413 {
414  #ifdef _XSENS_LIST_RANGE_CHECKS
415  if (m_count == 0)
416  throw Exception("List.last: empty list");
417  #endif
418  return m_data[m_count-1];
419 }
420 
421 template <typename T>
422 T& List<T>::maxVal(void) const XSENS_LIST_THROW
423 {
424  #ifdef _XSENS_LIST_RANGE_CHECKS
425  if (m_count == 0)
426  throw Exception("List.maxVal: empty list");
427  #endif
428  T* item = &m_data[0];
429  for (uint32_t i = 1; i < m_count; ++i)
430  if (*item < m_data[i])
431  item = &m_data[i];
432  return *item;
433 }
434 
435 template <typename T>
436 T& List<T>::minVal(void) const XSENS_LIST_THROW
437 {
438  #ifdef _XSENS_LIST_RANGE_CHECKS
439  if (m_count == 0)
440  throw Exception("List.minVal: empty list");
441  #endif
442  T* item = &m_data[0];
443  for (uint32_t i = 1; i < m_count; ++i)
444  if (m_data[i] < *item)
445  item = &m_data[i];
446  return *item;
447 }
448 
449 template <typename T>
450 T& List<T>::get(const uint32_t index) const XSENS_LIST_THROW
451 {
452  #ifdef _XSENS_LIST_RANGE_CHECKS
453  if (index >= m_count)
454  throw Exception("List.get: index out of bounds");
455  #endif
456  if (index >= m_count)
457  return m_data[m_count-1];
458  return m_data[index];
459 }
460 
461 template <typename T>
462 void List<T>::insert(const T& item, const uint32_t index)
463 {
464  if (m_count == m_max)
465  resize(1 + m_max + (m_max >> 1));
466  for (unsigned i=m_count;i>index;--i)
467  m_data[i] = m_data[i-1];
468  if (index <= m_count)
469  m_data[index] = item;
470  else
471  m_data[m_count] = item;
472  m_count++;
473 }
474 
475 template <typename T>
476 template <typename TB>
477 void List<T>::insertCopy(const TB& item, const uint32_t index)
478 {
479  if (m_count == m_max)
480  resize(1 + m_max + (m_max >> 1));
481  for (unsigned i=m_count;i>index;--i)
482  m_data[i] = m_data[i-1];
483  if (index <= m_count)
484  m_data[index] = new TB(item);
485  else
486  m_data[m_count] = new TB(item);
487  m_count++;
488 }
489 
490 template <typename T>
491 T& List<T>::operator [] (const uint32_t index) const XSENS_LIST_THROW
492 {
493  #ifdef _XSENS_LIST_RANGE_CHECKS
494  if (index >= m_count)
495  throw Exception("List[]: index out of bounds");
496  #endif
497  return m_data[index];
498 }
499 
500 
501 template <typename T>
502 void List<T>::qSort(uint32_t left, uint32_t right)
503 {
504  uint32_t l_hold, r_hold;
505  T pivot;
506 
507  l_hold = left;
508  r_hold = right;
509  pivot = m_data[left];
510  while (left < right)
511  {
512  while (!(m_data[right] < pivot) && (left < right))
513  right--;
514  if (left != right)
515  {
516  m_data[left] = m_data[right];
517  left++;
518  }
519  while (!(pivot < m_data[left]) && (left < right))
520  left++;
521  if (!(left == right))
522  {
523  m_data[right] = m_data[left];
524  right--;
525  }
526  }
527  m_data[left] = pivot;
528  if (l_hold < left)
529  qSort(l_hold, left-1);
530  if (r_hold > left)
531  qSort(left+1, r_hold);
532 }
533 
534 template <typename T>
535 void List<T>::qSortDeref(uint32_t left, uint32_t right)
536 {
537  uint32_t l_hold, r_hold;
538  T pivot;
539 
540  l_hold = left;
541  r_hold = right;
542  pivot = m_data[left];
543  while (left < right)
544  {
545  while (!(*m_data[right] < *pivot) && (left < right))
546  right--;
547  if (left != right)
548  {
549  m_data[left] = m_data[right];
550  left++;
551  }
552  while (!(*pivot < *m_data[left]) && (left < right))
553  left++;
554  if (!(left == right))
555  {
556  m_data[right] = m_data[left];
557  right--;
558  }
559  }
560  m_data[left] = pivot;
561  if (l_hold < left)
562  qSortDeref(l_hold, left-1);
563  if (r_hold > left)
564  qSortDeref(left+1, r_hold);
565 }
566 
567 template <typename T>
568 void List<T>::sortAscending(void)
569 {
570  if (m_count <= 1)
571  return;
572  struct Linker {
573  Linker *prev, *next;
574  uint32_t index;
575 
576  T item;
577  };
578 
579  Linker* list = (Linker*) malloc(m_count*sizeof(Linker));
580  if (!list)
581  throw std::bad_alloc();
582 
583  list[0].prev = NULL;
584  list[0].next = NULL;
585  list[0].index = 0;
586  list[0].item = m_data[0];
587 
588  Linker* curr = list;
589 
590  for (uint32_t i = 1; i < m_count; ++i)
591  {
592  list[i].index = i;
593  list[i].item = m_data[i];
594  if (m_data[i] < m_data[curr->index])
595  {
596  while (curr->prev != NULL)
597  {
598  curr = curr->prev;
599  if (!(m_data[i] < m_data[curr->index]))
600  {
601  // insert after this
602  list[i].next = curr->next;
603  list[i].prev = curr;
604  curr->next->prev = &list[i];
605  curr->next = &list[i];
606  curr = &list[i];
607  break;
608  }
609  }
610  if (curr != &list[i])
611  {
612  list[i].prev = NULL;
613  list[i].next = curr;
614  curr->prev = &list[i];
615  curr = &list[i];
616  }
617  }
618  else
619  {
620  while (curr->next != NULL)
621  {
622  curr = curr->next;
623  if (m_data[i] < m_data[curr->index])
624  {
625  // insert before this
626  list[i].next = curr;
627  list[i].prev = curr->prev;
628  curr->prev->next = &list[i];
629  curr->prev = &list[i];
630  curr = &list[i];
631  break;
632  }
633  }
634  if (curr != &list[i])
635  {
636  list[i].prev = curr;
637  list[i].next = NULL;
638  curr->next = &list[i];
639  curr = &list[i];
640  }
641  }
642  }
643 
644  // go to start of list
645  while (curr->prev != NULL) curr = curr->prev;
646 
647  // copy sorted list back
648  for (uint32_t i = 0; i < m_count; ++i)
649  {
650  m_data[i] = curr->item;
651  curr = curr->next;
652  }
653 
654  free(list);
655 }
656 
657 template <typename T>
658 void List<T>::sortAscendingDeref(void)
659 {
660  if (m_count <= 1)
661  return;
663  struct Linker {
664  Linker *prev, *next;
665  uint32_t index;
666 
667  T item;
668  };
669 
670  Linker* list = (Linker*) malloc(m_count*sizeof(Linker));
671  if (!list)
672  throw std::bad_alloc();
673 
674  list[0].prev = NULL;
675  list[0].next = NULL;
676  list[0].index = 0;
677  list[0].item = m_data[0];
678 
679  Linker* curr = list;
680 
681  for (uint32_t i = 1; i < m_count; ++i)
682  {
683  list[i].index = i;
684  list[i].item = m_data[i];
685  if (*m_data[i] < *m_data[curr->index])
686  {
687  while (curr->prev != NULL)
688  {
689  curr = curr->prev;
690  if (!(*m_data[i] < *m_data[curr->index]))
691  {
692  // insert after this
693  list[i].next = curr->next;
694  list[i].prev = curr;
695  curr->next->prev = &list[i];
696  curr->next = &list[i];
697  curr = &list[i];
698  break;
699  }
700  }
701  if (curr != &list[i])
702  {
703  list[i].prev = NULL;
704  list[i].next = curr;
705  curr->prev = &list[i];
706  curr = &list[i];
707  }
708  }
709  else
710  {
711  while (curr->next != NULL)
712  {
713  curr = curr->next;
714  if (*m_data[i] < *m_data[curr->index])
715  {
716  // insert before this
717  list[i].next = curr;
718  list[i].prev = curr->prev;
719  curr->prev->next = &list[i];
720  curr->prev = &list[i];
721  curr = &list[i];
722  break;
723  }
724  }
725  if (curr != &list[i])
726  {
727  list[i].prev = curr;
728  list[i].next = NULL;
729  curr->next = &list[i];
730  curr = &list[i];
731  }
732  }
733  }
734 
735  // go to start of list
736  while (curr->prev != NULL) curr = curr->prev;
737 
738  // copy sorted list back
739  for (uint32_t i = 0; i < m_count; ++i)
740  {
741  m_data[i] = curr->item;
742  curr = curr->next;
743  }
744 
745  free(list);
746 }
747 
748 template <typename T>
749 template <typename T2>
750 void List<T>::twinSortAscending(List<T2>& twin)
751 {
752  if (m_count <= 1)
753  return;
754 
755  #ifdef _XSENS_LIST_RANGE_CHECKS
756  if (m_count != twin.m_count)
757  throw Exception("List.twinSortAscending: sizes do not match");
758  #endif
759  uint32_t iteration = 0;
760  uint32_t mini;
761  T tmp;
762  T2 tmp2;
763  if (m_count > 1)
764  while (iteration < m_count-1)
765  {
766  mini = iteration;
767  for (uint32_t i=iteration+1;i<m_count;++i)
768  {
769  if (m_data[i] < m_data[mini])
770  mini = i;
771  }
772  if (mini != iteration)
773  {
774  tmp = m_data[mini];
775  m_data[mini] = m_data[iteration];
776  m_data[iteration] = tmp;
777 
778  tmp2 = twin.m_data[mini];
779  twin.m_data[mini] = twin.m_data[iteration];
780  twin.m_data[iteration] = tmp2;
781  }
782  ++iteration;
783  }
784 }
785 
786 template <typename T>
787 void List<T>::remove(const uint32_t index) XSENS_LIST_THROW
788 {
789  #ifdef _XSENS_LIST_RANGE_CHECKS
790  if (index >= m_count)
791  throw Exception("List.remove: index out of bounds");
792  #endif
793  if (index == m_count-1)
794  {
795  --m_count;
796  return;
797  }
798  --m_count;
799  for (unsigned i = index;i < m_count;++i)
800  m_data[i] = m_data[i+1];
801 }
802 
803 template <typename T>
804 void List<T>::removeTail(const uint32_t count) XSENS_LIST_THROW
805 {
806  #ifdef _XSENS_LIST_RANGE_CHECKS
807  if (count > m_count)
808  throw Exception("List.removeTail: list size less than remove count");
809  #endif
810  if (m_count > count)
811  {
812  m_count -= count;
813  return;
814  }
815  m_count = 0;
816 }
817 
818 template <typename T>
819 void List<T>::deleteAndRemoveTail(const uint32_t count) XSENS_LIST_THROW
820 {
821  #ifdef _XSENS_LIST_RANGE_CHECKS
822  if (count > m_count)
823  throw Exception("List.deleteAndRemoveTail: list size less than remove count");
824  #endif
825  if (m_count > count)
826  {
827  for (unsigned i = 0;i < count;++i)
828  delete m_data[--m_count];
829  return;
830  }
831  deleteAndClear();
832 }
833 
834 template <typename T>
835 void List<T>::freeAndRemoveTail(const uint32_t count) XSENS_LIST_THROW
836 {
837  #ifdef _XSENS_LIST_RANGE_CHECKS
838  if (count > m_count)
839  throw Exception("List.freeAndRemoveTail: list size less than remove count");
840  #endif
841  if (m_count > count)
842  {
843  for (unsigned i = 0;i < count;++i)
844  free(m_data[--m_count]);
845  return;
846  }
847  freeAndClear();
848 }
849 
850 template <typename T>
851 uint32_t List<T>::removeDuplicateEntries(void)
852 {
853  uint32_t removed = 0;
854  for (uint32_t i=0;i < m_count; ++i)
855  {
856  for (uint32_t j=i+1;j < m_count; ++j)
857  {
858  if (m_data[i] == m_data[j])
859  {
860  remove(j);
861  ++removed;
862  --j;
863  }
864  }
865  }
866  return removed;
867 }
868 
869 template <typename T>
870 uint32_t List<T>::removeDuplicateEntriesDeref(void)
871 {
872  uint32_t removed = 0;
873  for (uint32_t i=0;i < m_count; ++i)
874  {
875  for (uint32_t j=i+1;j < m_count; ++j)
876  {
877  if (*(m_data[i]) == *(m_data[j]))
878  {
879  remove(j);
880  ++removed;
881  --j;
882  }
883  }
884  }
885  return removed;
886 }
887 
888 template <typename T>
889 void List<T>::deleteAndRemove(const uint32_t index) XSENS_LIST_THROW
890 {
891  #ifdef _XSENS_LIST_RANGE_CHECKS
892  if (index >= m_count)
893  throw Exception("List.deleteAndRemove: index out of bounds");
894  #endif
895  delete m_data[index];
896  if (index == m_count-1)
897  {
898  --m_count;
899  return;
900  }
901  --m_count;
902  for (unsigned i = index;i < m_count;++i)
903  m_data[i] = m_data[i+1];
904 }
905 
906 template <typename T>
907 void List<T>::freeAndRemove(const uint32_t index) XSENS_LIST_THROW
908 {
909  #ifdef _XSENS_LIST_RANGE_CHECKS
910  if (index >= m_count)
911  throw Exception("List.freeAndRemove: index out of bounds");
912  #endif
913  free(m_data[index]);
914  if (index == m_count-1)
915  {
916  --m_count;
917  return;
918  }
919  --m_count;
920  for (unsigned i = index;i < m_count;++i)
921  m_data[i] = m_data[i+1];
922 }
923 
924 template <typename T>
925 template <typename TB>
926 uint32_t List<T>::find(const TB& item) const
927 {
928  for (uint32_t i=0;i<m_count;++i)
929  if (((const T*)m_data)[i] == item)
930  return i;
931  return XSENS_LIST_NOTFOUND;
932 }
933 
934 template <typename T>
935 uint32_t List<T>::find(const T item, InequalityFunction fnc) const
936 {
937  for (uint32_t i=0;i<m_count;++i)
938  if (!fnc(m_data[i],item))
939  return i;
940  return XSENS_LIST_NOTFOUND;
941 }
942 
943 template <typename T>
944 template <typename TB>
945 uint32_t List<T>::findDeref(const TB& item) const
946 {
947  for (uint32_t i=0;i<m_count;++i)
948  if (*(m_data[i]) == item)
949  return i;
950  return XSENS_LIST_NOTFOUND;
951 }
952 
953 template <typename T>
954 template <typename TB>
955 uint32_t List<T>::reverseFind(const TB& item) const
956 {
957  // comparison is ok due to unsigned-ness of i
958  for (uint32_t i=m_count-1 ; i<m_count ; --i)
959  if (((const T*)m_data)[i] == item)
960  return i;
961  return XSENS_LIST_NOTFOUND;
962 }
963 
964 template <typename T>
965 template <typename TB>
966 uint32_t List<T>::reverseFindDeref(const TB& item) const
967 {
968  // comparison is ok due to unsigned-ness of i
969  for (uint32_t i=m_count-1 ; i<m_count ; --i)
970  if (*(m_data[i]) == item)
971  return i;
972  return XSENS_LIST_NOTFOUND;
973 }
974 
975 template <typename T>
976 template <typename TB>
977 uint32_t List<T>::findSorted(const TB& item) const
978 {
979  if (m_count < XSENS_LIST_LINEAR_SEARCH_TRESHOLD) // for small lists, it is faster to simply walk the list
980  return find(item);
981 
982  uint32_t x = m_count;
983  uint32_t n = 1;
984  uint32_t i;
985 
986  while(x >= n)
987  {
988  i = (x + n) >> 1;
989 
990  if (m_data[i-1] == item)
991  return i-1;
992  if (m_data[i-1] < item)
993  n = i+1;
994  else
995  x = i-1;
996  }
997  return XSENS_LIST_NOTFOUND;
998 }
999 
1000 template <typename T>
1001 template <typename TB>
1002 uint32_t List<T>::findSortedDeref(const TB& item) const
1003 {
1004  if (m_count < XSENS_LIST_LINEAR_SEARCH_TRESHOLD) // for small lists, it is faster to simply walk the list
1005  return findDeref(item);
1006 
1007  uint32_t x = m_count;
1008  uint32_t n = 1;
1009  uint32_t i;
1010 
1011  while(x >= n)
1012  {
1013  i = (x + n) >> 1;
1014 
1015  if (*(m_data[i-1]) < item)
1016  n = i+1;
1017  else if (*(m_data[i-1]) == item)
1018  return i-1;
1019  else
1020  x = i-1;
1021  }
1022  return XSENS_LIST_NOTFOUND;
1023 }
1024 
1025 template <typename T>
1026 template <typename TB>
1027 uint32_t List<T>::findSortedForInsert(const TB& item) const
1028 {
1029  uint32_t i;
1030  if (m_count < XSENS_LIST_LINEAR_SEARCH_TRESHOLD)
1031  {
1032  for (i=0;i<m_count;++i)
1033  if (item <= m_data[i])
1034  return i;
1035  return m_count;
1036  }
1037  else
1038  {
1039  uint32_t x = m_count;
1040  uint32_t n = 1;
1041 
1042  while(x >= n)
1043  {
1044  i = (x + n) >> 1;
1045 
1046  if (m_data[i-1] < item)
1047  n = i+1;
1048  else if (m_data[i-1] == item)
1049  return i-1;
1050  else
1051  x = i-1;
1052  }
1053  return n-1;
1054  }
1055 }
1056 
1057 template <typename T>
1058 template <typename TB>
1059 uint32_t List<T>::findSortedDerefForInsert(const TB& item) const
1060 {
1061  uint32_t i;
1062  if (m_count < XSENS_LIST_LINEAR_SEARCH_TRESHOLD)
1063  {
1064  for (i=0;i<m_count;++i)
1065  if (item <= *m_data[i])
1066  return i;
1067  return m_count;
1068  }
1069  else
1070  {
1071  uint32_t x = m_count;
1072  uint32_t n = 1;
1073 
1074  while(x >= n)
1075  {
1076  i = (x + n) >> 1;
1077 
1078  if (*(m_data[i-1]) < item)
1079  n = i+1;
1080  else if (*(m_data[i-1]) == item)
1081  return i-1;
1082  else
1083  x = i-1;
1084  }
1085  return n-1;
1086  }
1087 }
1088 
1089 template <typename T>
1090 uint32_t List<T>::insertSorted(const T& item)
1091 {
1092  uint32_t i = findSortedForInsert(item);
1093  if (i == m_count)
1094  append(item);
1095  else if (item == m_data[i])
1096  m_data[i] = item;
1097  else
1098  insert(item,i);
1099  return i;
1100 }
1101 
1102 template <typename T>
1103 uint32_t List<T>::insertSortedDeref(const T& item)
1104 {
1105  uint32_t i = findSortedDerefForInsert(*item);
1106  if (i == m_count)
1107  append(item);
1108  else if (*item == *m_data[i])
1109  m_data[i] = item;
1110  else
1111  insert(item,i);
1112  return i;
1113 }
1114 
1115 template <typename T>
1116 template <typename TB>
1117 uint32_t List<T>::insertSortedCopy(const TB& item)
1118 {
1119  uint32_t i = findSortedDerefForInsert(item);
1120  if (i == m_count)
1121  appendCopy<TB>(item);
1122  else if (item == m_data[i])
1123  m_data[i] = item;
1124  else
1125  insertCopy<TB>(item,i);
1126  return i;
1127 }
1128 
1129 template <typename T>
1130 void List<T>::deleteItemsOnDestroy(void)
1131 {
1132  if (m_jcf != NULL)
1133  {
1134  m_jcf->disable();
1135  delete m_jcf;
1136  }
1137  m_jcf = new JanitorClassFunc<List<T>, void>(*this,&List<T>::deleteAndClear);
1138 }
1139 
1140 template <typename T>
1141 void List<T>::freeItemsOnDestroy(void)
1142 {
1143  if (m_jcf != NULL)
1144  {
1145  m_jcf->disable();
1146  delete m_jcf;
1147  }
1148  m_jcf = new JanitorClassFunc<List<T>, void>(*this,&List<T>::freeAndClear);
1149 }
1150 
1151 template <typename T>
1152 template <typename TB>
1153 void List<T>::isDeepCopyOf(const List<T>& source)
1154 {
1155  m_count = 0;
1156  if (m_max < source.m_count)
1157  resize(source.m_count);
1158  m_count = source.m_count;
1159  for (uint32_t i = 0;i<m_count;++i)
1160  m_data[i] = new TB(*source.m_data[i]);
1161 }
1162 
1163 template <typename T>
1164 void List<T>::isShallowCopyOf(const List<T>& x)
1165 {
1166  m_count = 0;
1167  if (m_max < x.m_count)
1168  resize(x.m_count);
1169  m_count = x.m_count;
1170  for (uint32_t i = 0;i<m_count;++i)
1171  m_data[i] = x.m_data[i];
1172 }
1173 
1174 template <typename T>
1175 void List<T>::swap(const uint32_t i, const uint32_t j) XSENS_LIST_THROW
1176 {
1177  #ifdef _XSENS_LIST_RANGE_CHECKS
1178  if (i >= m_count || j >= m_count)
1179  throw Exception("List.swap: index out of bounds");
1180  #endif
1181  T tmp = m_data[i];
1182  m_data[i] = m_data[j];
1183  m_data[j] = tmp;
1184 }
1185 
1186 template <typename T>
1187 void List<T>::reverse(void)
1188 {
1189  uint32_t half = m_count / 2;
1190  for (uint32_t i = 0, end=m_count-1; i < half; ++i,--end)
1191  {
1192  T tmp = m_data[i];
1193  m_data[i] = m_data[end];
1194  m_data[end] = tmp;
1195  }
1196 }
1197 
1198 template <typename T>
1199 template <typename TB>
1200 bool List<T>::operator == (const List<TB>& lst)
1201 {
1202  if (m_count != lst.m_count)
1203  return false;
1204  for (uint32_t i = 0; i < m_count; ++i)
1205  if (!(m_data[i] == lst.m_data[i]))
1206  return false;
1207  return true;
1208 }
1209 
1210 } // end of xsens namespace
1211 
1212 #endif // XSENS_LIST_H
xsens::List::InequalityFunction
int32_t(__cdecl * InequalityFunction)(const T &, const T &)
Type for an equality compare function, should return true when NOT equal.
Definition: xsens_list.h:211
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.h:787
xsens::List::deleteItemsOnDestroy
void deleteItemsOnDestroy(void)
Definition: xsens_list.h:1130
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.h:1175
xsens::List::freeAndRemoveTail
void freeAndRemoveTail(const uint32_t count) XSENS_LIST_THROW
Definition: xsens_list.h:835
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.h:450
xsens::List::freeAndClear
void freeAndClear(void)
Calls free for all items in the list and then clears the list.
Definition: xsens_list.h:325
xsens::Exception
Definition: xsens_exception.h:9
xsens::List::cmpFunc
int32_t(* cmpFunc)(const T &, const T &)
A comparison function type, should return -1, 0 or 1 for <, == and >
Definition: xsens_list.h:100
xsens_janitors.h
Contains the Janitor class-interfaces and implementations.
xsens::List::operator==
bool operator==(const List< TB > &lst)
Compare each item of the lists using the T == TB operator. If they&#39;re all identical, returns true.
Definition: xsens_list.h:1200
xsens::List::deleteAndClear
void deleteAndClear(void)
Calls delete for all items in the list and then clears the list.
Definition: xsens_list.h:317
__cdecl
#define __cdecl
Definition: cmtdef.h:51
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.h:889
xsens::List
Dynamic list class.
Definition: xsens_list.h:79
xsens::List::length
uint32_t length(void) const
Returns the number of items currently in the list.
Definition: xsens_list.h:166
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.h:1187
xsens::List::List
List()
Standard constructor, creates an empty list with some room for items.
Definition: xsens_list.h:238
xsens::List::maxVal
T & maxVal(void) const XSENS_LIST_THROW
Retrieves the largest item, using the T::< operator.
Definition: xsens_list.h:422
xsens::List::reverseFindDeref
uint32_t reverseFindDeref(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.h:966
xsens::List::m_jcf
JanitorClassFunc< List< T > > * m_jcf
Used to clean up the list on exit.
Definition: xsens_list.h:92
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.h:945
xsens::List::sortAscendingDeref
void sortAscendingDeref(void)
Sorts the list in an ascending order, using the T::< operator on dereferenced list items...
Definition: xsens_list.h:658
xsens::List::getBuffer
const T * getBuffer(void) const
Returns the start of the linear data buffer.
Definition: xsens_list.h:230
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.h:926
xsens::JanitorClassFunc
Class function calling janitor class.
Definition: xsens_janitors.h:45
xsens_exception.h
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.h:1002
xsens::List::clear
void clear(void)
Clears the list without explicitly deleting anything.
Definition: xsens_list.h:333
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.h:462
xsens::List::minVal
T & minVal(void) const XSENS_LIST_THROW
Retrieves the smallest item, using the T::< operator.
Definition: xsens_list.h:436
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.h:1090
xsens::List::reverseFind
uint32_t reverseFind(const TB &item) const
Finds an item in an unsorted list (walk over all items) using the T::== operator, starting at the end...
Definition: xsens_list.h:955
xsens::List::~List
~List()
Destroy the list. This does NOT automatically delete items IN the list.
Definition: xsens_list.h:306
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.h:374
xsens::List::m_manage
bool m_manage
Definition: xsens_list.h:93
XSENS_LIST_THROW
#define XSENS_LIST_THROW
Definition: xsens_list.h:58
xsens::List::appendCopy
void appendCopy(const TB &item)
Adds a copy of a referenced item to the end of the list using newItem = new TB(item).
Definition: xsens_list.h:395
XSENS_LIST_NOTFOUND
#define XSENS_LIST_NOTFOUND
Definition: xsens_list.h:49
xsens::List::m_count
uint32_t m_count
The number of items currently in the list.
Definition: xsens_list.h:91
xsens::List::deleteAndRemoveTail
void deleteAndRemoveTail(const uint32_t count) XSENS_LIST_THROW
Definition: xsens_list.h:819
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.h:870
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.h:365
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.h:1117
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.h:907
xsens::List::resize
void resize(uint32_t newSize)
Resizes the list to at least the given size.
Definition: xsens_list.h:339
xsens::List::last
T & last(void) const XSENS_LIST_THROW
Retrieves the last item.
Definition: xsens_list.h:412
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.h:384
xsens::List::m_data
T * m_data
The array containing the items.
Definition: xsens_list.h:89
xsens
The namespace of all Xsens software since 2006.
Definition: cmt1.cpp:62
xsens::List::isShallowCopyOf
void isShallowCopyOf(const List< T > &source)
Overwrites the current list with a direct copy (a=b) of another list.
Definition: xsens_list.h:1164
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.h:851
XSENS_LIST_LINEAR_SEARCH_TRESHOLD
#define XSENS_LIST_LINEAR_SEARCH_TRESHOLD
Definition: xsens_list.h:67
xsens::List::findSortedDerefForInsert
uint32_t findSortedDerefForInsert(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.h:1059
xsens::List::sortAscending
void sortAscending(void)
Sorts the list in an ascending order, using the T::< operator.
Definition: xsens_list.h:568
xsens::List::removeTail
void removeTail(const uint32_t count) XSENS_LIST_THROW
Removes items from the end of the list.
Definition: xsens_list.h:804
xsens::List::count
uint32_t count(void) const
Returns the number of items currently in the list.
Definition: xsens_list.h:168
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.h:1103
xsens::List::freeItemsOnDestroy
void freeItemsOnDestroy(void)
Definition: xsens_list.h:1141
xsens::List::append
void append(const T &item)
Adds an item to the end of the list.
Definition: xsens_list.h:357
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.h:491
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.h:977
xsens::List::m_max
uint32_t m_max
The current size of the data array.
Definition: xsens_list.h:90
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.h:750
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.h:404
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.h:477
xsens::List::findSortedForInsert
uint32_t findSortedForInsert(const TB &item) const
Finds an item in a sorted list (binary search) using the T::== and T::< operators. If not found, it does not return XSENS_LIST_NOTFOUND but the insert position if this item would be inserted in the list.
Definition: xsens_list.h:1027
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.h:1153
Generated by   doxygen 1.8.13