xsens_list.h

Go to the documentation of this file.
00001 #ifndef _CMT_MONOLITHIC
00002 /*! \file
00003         \brief List class interface for use in CMT
00004 
00005         The implementations of the functions are in \ref Cmtlist.hpp which is automatically
00006         included so they are inlined.
00007 
00008         This file requires xsens_janitors.h. When a library header is built with this file,
00009         make sure xsens_janitors.h is included before this file.
00010 
00011         This file requires xsens_math.h if the math switch is set to 1. When a library header
00012         is built with this file, make sure xsens_math.h is included before this file.
00013 
00014         \section FileCopyright Copyright Notice 
00015         Copyright (C) Xsens Technologies B.V., 2006.  All rights reserved.
00016 
00017         This source code is intended for use only by Xsens Technologies BV and
00018         those that have explicit written permission to use it from
00019         Xsens Technologies BV.
00020 
00021         THIS CODE AND INFORMATION IS PROVIDED "AS IS" WITHOUT WARRANTY OF ANY
00022         KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE
00023         IMPLIED WARRANTIES OF MERCHANTABILITY AND/OR FITNESS FOR A
00024         PARTICULAR PURPOSE.
00025 
00026         \section FileSwitches Switches
00027         \li        \c _XSENS_LIST_WITH_MATH        Check whether to include math files when set to 1.
00028         \li        \c _XSENS_LIST_IO                        Include code for string and file I/O when set to 1.
00029 */
00030 #endif
00031 #ifndef _XSENS_LIST_H_2006_06_08
00032 #define _XSENS_LIST_H_2006_06_08
00033 
00034 #ifndef _CMT_MONOLITHIC
00035 #ifndef _PSTDINT_H_INCLUDED
00036 #        include "pstdint.h"
00037 #endif
00038 #endif
00039 
00040 #ifndef _JANITORS_H_2006_05_01
00041 #        include "xsens_janitors.h"
00042 #endif
00043 
00044 
00045 #define XSENS_LIST_NOTFOUND        0xFFFFFFFF
00046 
00047 #ifdef _XSENS_LIST_RANGE_CHECKS
00048 #        ifdef _MSC_VER
00049 #                define XSENS_LIST_THROW throw(...)
00050 #        else
00051 #                define XSENS_LIST_THROW
00052 #        endif
00053 #else
00054 #        define XSENS_LIST_THROW
00055 #endif
00056 
00057 #include <stdlib.h>
00058 #include <malloc.h>
00059 
00060 namespace xsens {
00061 
00062 #define CMT_LIST_LINEAR_SEARCH_TRESHOLD        10
00063 
00064         /*! \brief Dynamic list class
00065 
00066                 This class can store items of the given type. If the type supports the < operator
00067                 it can also be sorted.
00068                 Items in the list can be accessed through the [] operator or the get() function.
00069 
00070                 Do NOT use any item type that requires a constructor to work correctly. Pointers to these
00071                 objects can work though.
00072         */
00073         template <typename T>
00074         class List
00075         {
00076         private:
00077                 void operator = (const List& list);        //!< intentionally NOT implemented due to ambiguous nature
00078                         //! Sorts the list in an ascending order, using the T::< operator.
00079                 void qSort(uint32_t left, uint32_t right);
00080                         //! Sorts the list in an ascending order, using the T::< operator on dereferenced list items.
00081                 void qSortDeref(uint32_t left, uint32_t right);
00082 
00083         protected:
00084                 T* m_data;                                                        //!< The array containing the items
00085                 uint32_t m_max;                                //!< The current size of the data array
00086                 uint32_t m_count;                                //!< The number of items currently in the list
00087                 JanitorClassFunc<List<T> >* m_jcf;        //!< Used to clean up the list on exit
00088                 bool m_manage;
00089 
00090                         //! Construct a list as a reference to a raw list 
00091                 List(const uint32_t size, T* src, bool manage);
00092         public:
00093 
00094                         //! A comparison function type, should return -1, 0 or 1 for <, == and >
00095                 typedef int32_t (*cmpFunc) (const T&,const T&);
00096 
00097                         //! Standard constructor, creates an empty list with some room for items.
00098                 List();
00099                         //! Construct a list with a capacity of at least the given size.
00100                 List(const uint32_t size);
00101                         //! Construct a list as a direct copy of another list
00102                 List(const List<T>& src);
00103                         //! Construct a list as a copy of a raw list 
00104                 List(const uint32_t size, const T* src);
00105                         //! Destroy the list. This does NOT automatically delete items IN the list.
00106                 ~List();
00107 
00108                         //! Calls delete for all items in the list and then clears the list.
00109                 void deleteAndClear(void);
00110                         //! Calls free for all items in the list and then clears the list.
00111                 void freeAndClear(void);
00112                         //! Clears the list without explicitly deleting anything.
00113                 void clear(void);
00114                         //! Resizes the list to at least the given size.
00115                 void resize(uint32_t newSize);
00116                         //! Adds an item to the end of the list.
00117                 void append(const T& item);
00118                         //! Adds a number of items to the end of the list.
00119                 void appendList(uint32_t count, const T* lst);
00120                         //! Adds the contents of the source list to the end of the list.
00121                 void appendDeepCopy(const List<T>& source);
00122                         //! Adds the contents of the source list to the end of the list.
00123                 void appendShallowCopy(const List<T>& source);
00124                         //! Adds a copy of a referenced item to the end of the list using newItem = new TB(item).
00125                         template <typename TB>
00126                 void appendCopy(const TB& item);
00127                         //! Adds a related item to the end of the list, using the T = TR operator.
00128                         template <typename TR>
00129                 void appendRelated(const TR& item);
00130                         //! Removes an item at the given index in the list.
00131                 void remove(const uint32_t index) XSENS_LIST_THROW;
00132                         //! Swaps two items in the list.
00133                 void swap(const uint32_t i, const uint32_t j) XSENS_LIST_THROW;
00134                         //! Removes an item at the given index in the list.
00135                 void deleteAndRemove(const uint32_t index) XSENS_LIST_THROW;
00136                         //! Removes an item at the given index in the list.
00137                 void freeAndRemove(const uint32_t index) XSENS_LIST_THROW;
00138                         //! Retrieves the last item.
00139                 T& last(void) const XSENS_LIST_THROW;
00140                         //! Retrieves the item at the given index. An index beyond the end returns the first item.
00141                 T& get(const uint32_t index) const XSENS_LIST_THROW;
00142                         //! Retrieves the item at the given index. An index beyond the end probably causes an exception.
00143                 T& operator [] (const uint32_t index) const XSENS_LIST_THROW;
00144                         //! Inserts an item at the given index, shifting any items below it down one spot.
00145                 void insert(const T& item, const uint32_t index);
00146                         //! Inserts a copy of the referenced item at the given index, shifting any items below it down one spot.
00147                         template <typename TB>
00148                 void insertCopy(const TB& item, const uint32_t index);
00149                         //! Assumes the list is sorted and inserts the item at the appropriate spot.
00150                 uint32_t insertSorted(const T& item);
00151                         //! Assumes the list is sorted by dereferenced values and inserts the item at the appropriate spot.
00152                 uint32_t insertSortedDeref(const T& item);
00153                         //! Assumes the list is sorted and inserts a copy of the referenced item at the appropriate spot.
00154                         template <typename TB>
00155                 uint32_t insertSortedCopy(const TB& item);
00156                         //! Returns the number of items currently in the list.
00157                 uint32_t length(void) const { return m_count; }
00158                         //! Sorts the list in an ascending order, using the T::< operator.
00159                 void sortAscending(void);
00160                         //! Sorts the list in an ascending order, using the T::< operator on dereferenced list items.
00161                 void sortAscendingDeref(void);
00162                         //! Sorts the first list in an ascending order, using the T::< operator, the second list will be updated the same way.
00163                         template <typename T2>
00164                 void twinSortAscending(List<T2>& twin);
00165                         //! Finds an item in an unsorted list (walk over all items) using the T::== operator
00166                         template <typename TB>
00167                 uint32_t find(const TB& item) const;
00168                         //! Finds an item in an unsorted list (walk over all items) using the T::== operator on dereferenced list items
00169                         template <typename TB>
00170                 uint32_t findDeref(const TB& item) const;
00171                         //! Finds an item in a sorted list (binary search) using the T::== and T::< operators
00172                         template <typename TB>
00173                 uint32_t findSorted(const TB& item) const;
00174                         //! Finds an item in a sorted list (binary search) using the T::== and T::< operators on dereferenced list items
00175                         template <typename TB>
00176                 uint32_t findSortedDeref(const TB& item) const;
00177                         //! Reverse the order of the list, useful for sorted lists that are read/created in the reverse order
00178                 void reverse(void);
00179                         //! Removes items from the end of the list.
00180                 void removeTail(const uint32_t count) XSENS_LIST_THROW;
00181                 void deleteAndRemoveTail(const uint32_t count) XSENS_LIST_THROW;
00182                 void freeAndRemoveTail(const uint32_t count) XSENS_LIST_THROW;
00183 
00184                         //! Type for an equality compare function, should return true when NOT equal
00185                 typedef int32_t (__cdecl * InequalityFunction)(const T&, const T&);
00186                         //! Finds an item in an unsorted list (walk over all items) using the given inequality function
00187                 uint32_t find(const T item, InequalityFunction fnc) const;
00188 
00189                 void deleteItemsOnDestroy(void);
00190                 void freeItemsOnDestroy(void);
00191 
00192                         //! Removes any duplicate entries and returns the number of items removed. Items are compared directly.
00193                 uint32_t removeDuplicateEntries(void);
00194                         //! Removes any duplicate entries and returns the number of items removed. Items are compared after dereferencing.
00195                 uint32_t removeDuplicateEntriesDeref(void);
00196 
00197                         //! Make a copy of the list, duplicating list items i with: copy[i] = new TB(*source[i])
00198                         template <typename TB>
00199                 void isDeepCopyOf(const List<T>& source);
00200                         //! Overwrites the current list with a direct copy (a=b) of another list.
00201                 void isShallowCopyOf(const List<T>& source);
00202 
00203                         //! Returns the start of the linear data buffer
00204                 const T* getBuffer(void) const { return m_data; }
00205         };
00206 
00207 
00208 template <typename T>
00209 List<T>::List()
00210 {
00211         m_max = 16;
00212         m_count = 0;
00213         m_data = (T*) malloc(m_max * sizeof(T));
00214         m_jcf = NULL;
00215         m_manage = true;
00216 }
00217 
00218 template <typename T>
00219 List<T>::List(uint32_t size)
00220 {
00221         m_max = size;
00222         if (m_max == 0)
00223                 m_max = 1;
00224         m_count = 0;
00225         m_data = (T*) malloc(m_max * sizeof(T));
00226         m_jcf = NULL;
00227         m_manage = true;
00228 }
00229 
00230 template <typename T>
00231 List<T>::List(const List<T>& src)
00232 {
00233         m_max = src.m_max;
00234         if (m_max == 0)
00235                 m_max = 1;
00236         m_count = src.m_count;
00237         m_data = (T*) malloc(m_max * sizeof(T));
00238         m_jcf = NULL;
00239         if (m_count > 0)
00240                 memcpy(m_data,src.m_data,m_count*sizeof(T));
00241         m_manage = true;
00242 }
00243 
00244 template <typename T>
00245 List<T>::List(const uint32_t size, const T* src)
00246 {
00247         m_max = size;
00248         if (m_max == 0)
00249                 m_max = 1;
00250         m_count = size;
00251         m_data = (T*) malloc(m_max * sizeof(T));
00252         m_jcf = NULL;
00253         if (m_count > 0)
00254                 memcpy(m_data,src,m_count * sizeof(T));
00255         m_manage = true;
00256 }
00257 
00258 template <typename T>
00259 List<T>::List(const uint32_t size, T* src, bool manage)
00260 {
00261         m_max = size;
00262         m_count = size;
00263         m_data = src;
00264         m_jcf = NULL;
00265         m_manage = manage;
00266 }
00267 
00268 template <typename T>
00269 List<T>::~List()
00270 {
00271         if (m_jcf != NULL)
00272                 delete m_jcf;
00273         if (m_manage && m_data != NULL)
00274                 free(m_data);
00275         m_jcf = NULL;
00276         m_data = NULL;
00277 }
00278 
00279 template <typename T>
00280 void List<T>::deleteAndClear(void)
00281 {
00282         for (unsigned i=0;i<m_count;++i)
00283                 delete m_data[i];
00284         m_count = 0;
00285 }
00286 
00287 template <typename T>
00288 void List<T>::freeAndClear(void)
00289 {
00290         for (unsigned i=0;i<m_count;++i)
00291                 free(m_data[i]);
00292         m_count = 0;
00293 }
00294 
00295 template <typename T>
00296 void List<T>::clear(void)
00297 {
00298         m_count = 0;
00299 }
00300 
00301 template <typename T>
00302 void List<T>::resize(uint32_t newSize)
00303 {
00304         if (m_manage)
00305         {
00306                 if (newSize == m_max)
00307                         return;
00308                 if (m_count > newSize)
00309                         m_max = m_count;
00310                 else
00311                         m_max = newSize;
00312                 if (m_max == 0)
00313                         m_max = 1;        // size 0 is not allowed
00314 
00315                 m_data = (T*) realloc(m_data,m_max * sizeof(T));
00316         }
00317 }
00318 
00319 template <typename T>
00320 void List<T>::append(const T& item)
00321 {
00322         if (m_count == m_max)
00323                 resize(m_max + 1 + m_max/2);
00324         m_data[m_count++] = item;
00325 }
00326 
00327 template <typename T>
00328 void List<T>::appendList(uint32_t count, const T* lst)
00329 {
00330         if (m_count+count > m_max)
00331                 resize(m_max + count + m_max/2);
00332         for (unsigned i = 0; i < count; ++i)
00333                 m_data[m_count++] = lst[i];
00334 }
00335 
00336 template <typename T>
00337 void List<T>::appendDeepCopy(const List<T>& source)
00338 {
00339         if (m_max < source.m_count + m_count)
00340                 resize(source.m_count + m_count);
00341 
00342         for (uint32_t i = 0;i<source.m_count;++i)
00343                 m_data[m_count++] = new T(*source.m_data[i]);
00344 }
00345 
00346 template <typename T>
00347 void List<T>::appendShallowCopy(const List<T>& source)
00348 {
00349         if (m_max < source.m_count + m_count)
00350                 resize(source.m_count + m_count);
00351 
00352         for (uint32_t i = 0;i<source.m_count;++i)
00353                 m_data[m_count++] = source.m_data[i];
00354 }
00355 
00356 template <typename T>
00357 template <typename TB>
00358 void List<T>::appendCopy(const TB& item)
00359 {
00360         if (m_count == m_max)
00361                 resize(m_max + 1 + m_max/2);
00362         m_data[m_count++] = new TB(item);
00363 }
00364 
00365 template <typename T>
00366 template <typename TR>
00367 void List<T>::appendRelated(const TR& item)
00368 {
00369         if (m_count == m_max)
00370                 resize(m_max + 1 + m_max/2);
00371         m_data[m_count++] = item;
00372 }
00373 
00374 template <typename T>
00375 T& List<T>::last(void) const XSENS_LIST_THROW
00376 {
00377         #ifdef _XSENS_LIST_RANGE_CHECKS
00378                 if (m_count == 0)
00379                         throw "List.last: empty list";
00380         #endif
00381         return m_data[m_count-1];
00382 }
00383 
00384 template <typename T>
00385 T& List<T>::get(const uint32_t index) const XSENS_LIST_THROW
00386 {
00387         #ifdef _XSENS_LIST_RANGE_CHECKS
00388                 if (index >= m_count)
00389                         throw "List.get: index out of bounds";
00390         #endif
00391         if (index >= m_count)
00392                 return m_data[m_count-1];
00393         return m_data[index];
00394 }
00395 
00396 template <typename T>
00397 void List<T>::insert(const T& item, const uint32_t index)
00398 {
00399         if (m_count == m_max)
00400                 resize(1 + m_max + (m_max >> 1));
00401         for (unsigned i=m_count;i>index;--i)
00402                 m_data[i] = m_data[i-1];
00403         if (index <= m_count)
00404                 m_data[index] = item;
00405         else
00406                 m_data[m_count] = item;
00407         m_count++;
00408 }
00409 
00410 template <typename T>
00411 template <typename TB>
00412 void List<T>::insertCopy(const TB& item, const uint32_t index)
00413 {
00414         if (m_count == m_max)
00415                 resize(1 + m_max + (m_max >> 1));
00416         for (unsigned i=m_count;i>index;--i)
00417                 m_data[i] = m_data[i-1];
00418         if (index <= m_count)
00419                 m_data[index] = new TB(item);
00420         else
00421                 m_data[m_count] = new TB(item);
00422         m_count++;
00423 }
00424 
00425 template <typename T>
00426 T& List<T>::operator [] (const uint32_t index) const XSENS_LIST_THROW
00427 {
00428         #ifdef _XSENS_LIST_RANGE_CHECKS
00429                 if (index >= m_count)
00430                         throw "List[]: index out of bounds";
00431         #endif
00432         return m_data[index];
00433 }
00434 
00435 
00436 template <typename T>
00437 void List<T>::qSort(uint32_t left, uint32_t right)
00438 {
00439         uint32_t l_hold, r_hold;
00440         T pivot;
00441 
00442         l_hold = left;
00443         r_hold = right;
00444         pivot = m_data[left];
00445         while (left < right)
00446         {
00447                 while (!(m_data[right] < pivot) && (left < right))
00448                         right--;
00449                 if (left != right)
00450                 {
00451                         m_data[left] = m_data[right];
00452                         left++;
00453                 }
00454                 while (!(pivot < m_data[left]) && (left < right))
00455                         left++;
00456                 if (!(left == right))
00457                 {
00458                         m_data[right] = m_data[left];
00459                         right--;
00460                 }
00461         }
00462         m_data[left] = pivot;
00463         if (l_hold < left)
00464                 qSort(l_hold, left-1);
00465         if (r_hold > left)
00466                 qSort(left+1, r_hold);
00467 }
00468 
00469 template <typename T>
00470 void List<T>::qSortDeref(uint32_t left, uint32_t right)
00471 {
00472         uint32_t l_hold, r_hold;
00473         T pivot;
00474 
00475         l_hold = left;
00476         r_hold = right;
00477         pivot = m_data[left];
00478         while (left < right)
00479         {
00480                 while (!(*m_data[right] < *pivot) && (left < right))
00481                         right--;
00482                 if (left != right)
00483                 {
00484                         m_data[left] = m_data[right];
00485                         left++;
00486                 }
00487                 while (!(*pivot < *m_data[left]) && (left < right))
00488                         left++;
00489                 if (!(left == right))
00490                 {
00491                         m_data[right] = m_data[left];
00492                         right--;
00493                 }
00494         }
00495         m_data[left] = pivot;
00496         if (l_hold < left)
00497                 qSortDeref(l_hold, left-1);
00498         if (r_hold > left)
00499                 qSortDeref(left+1, r_hold);
00500 }
00501 
00502 template <typename T>
00503 void List<T>::sortAscending(void)
00504 {
00505         if (m_count <= 1)
00506                 return;
00507         struct Linker {
00508                 Linker *prev, *next;
00509                 uint32_t index;
00510 
00511                 T item;
00512         };
00513 
00514         Linker* list = (Linker*) malloc(m_count*sizeof(Linker));
00515 
00516         list[0].prev = NULL;
00517         list[0].next = NULL;
00518         list[0].index = 0;
00519         list[0].item = m_data[0];
00520 
00521         Linker* curr = list;
00522 
00523         for (uint32_t i = 1; i < m_count; ++i)
00524         {
00525                 list[i].index = i;
00526                 list[i].item = m_data[i];
00527                 if (m_data[i] < m_data[curr->index])
00528                 {
00529                         while (curr->prev != NULL)
00530                         {
00531                                 curr = curr->prev;
00532                                 if (!(m_data[i] < m_data[curr->index]))
00533                                 {
00534                                         // insert after this
00535                                         list[i].next = curr->next;
00536                                         list[i].prev = curr;
00537                                         curr->next->prev = &list[i];
00538                                         curr->next = &list[i];
00539                                         curr = &list[i];
00540                                         break;
00541                                 }
00542                         }
00543                         if (curr != &list[i])
00544                         {
00545                                 list[i].prev = NULL;
00546                                 list[i].next = curr;
00547                                 curr->prev = &list[i];
00548                                 curr = &list[i];
00549                         }
00550                 }
00551                 else
00552                 {
00553                         while (curr->next != NULL)
00554                         {
00555                                 curr = curr->next;
00556                                 if (m_data[i] < m_data[curr->index])
00557                                 {
00558                                         // insert before this
00559                                         list[i].next = curr;
00560                                         list[i].prev = curr->prev;
00561                                         curr->prev->next = &list[i];
00562                                         curr->prev = &list[i];
00563                                         curr = &list[i];
00564                                         break;
00565                                 }
00566                         }
00567                         if (curr != &list[i])
00568                         {
00569                                 list[i].prev = curr;
00570                                 list[i].next = NULL;
00571                                 curr->next = &list[i];
00572                                 curr = &list[i];
00573                         }
00574                 }
00575         }
00576 
00577         // go to start of list
00578         while (curr->prev != NULL) curr = curr->prev;
00579 
00580         // copy sorted list back
00581         for (uint32_t i = 0; i < m_count; ++i)
00582         {
00583                 m_data[i] = curr->item;
00584                 curr = curr->next;
00585         }
00586 
00587         free(list);
00588 }
00589 
00590 template <typename T>
00591 void List<T>::sortAscendingDeref(void)
00592 {
00593         if (m_count <= 1)
00594                 return;
00595         struct Linker {
00596                 Linker *prev, *next;
00597                 uint32_t index;
00598 
00599                 T item;
00600         };
00601 
00602         Linker* list = (Linker*) malloc(m_count*sizeof(Linker));
00603 
00604         list[0].prev = NULL;
00605         list[0].next = NULL;
00606         list[0].index = 0;
00607         list[0].item = m_data[0];
00608 
00609         Linker* curr = list;
00610 
00611         for (uint32_t i = 1; i < m_count; ++i)
00612         {
00613                 list[i].index = i;
00614                 list[i].item = m_data[i];
00615                 if (*m_data[i] < *m_data[curr->index])
00616                 {
00617                         while (curr->prev != NULL)
00618                         {
00619                                 curr = curr->prev;
00620                                 if (!(*m_data[i] < *m_data[curr->index]))
00621                                 {
00622                                         // insert after this
00623                                         list[i].next = curr->next;
00624                                         list[i].prev = curr;
00625                                         curr->next->prev = &list[i];
00626                                         curr->next = &list[i];
00627                                         curr = &list[i];
00628                                         break;
00629                                 }
00630                         }
00631                         if (curr != &list[i])
00632                         {
00633                                 list[i].prev = NULL;
00634                                 list[i].next = curr;
00635                                 curr->prev = &list[i];
00636                                 curr = &list[i];
00637                         }
00638                 }
00639                 else
00640                 {
00641                         while (curr->next != NULL)
00642                         {
00643                                 curr = curr->next;
00644                                 if (*m_data[i] < *m_data[curr->index])
00645                                 {
00646                                         // insert before this
00647                                         list[i].next = curr;
00648                                         list[i].prev = curr->prev;
00649                                         curr->prev->next = &list[i];
00650                                         curr->prev = &list[i];
00651                                         curr = &list[i];
00652                                         break;
00653                                 }
00654                         }
00655                         if (curr != &list[i])
00656                         {
00657                                 list[i].prev = curr;
00658                                 list[i].next = NULL;
00659                                 curr->next = &list[i];
00660                                 curr = &list[i];
00661                         }
00662                 }
00663         }
00664 
00665         // go to start of list
00666         while (curr->prev != NULL) curr = curr->prev;
00667 
00668         // copy sorted list back
00669         for (uint32_t i = 0; i < m_count; ++i)
00670         {
00671                 m_data[i] = curr->item;
00672                 curr = curr->next;
00673         }
00674 
00675         free(list);
00676 }
00677 
00678 template <typename T>
00679 template <typename T2>
00680 void List<T>::twinSortAscending(List<T2>& twin)
00681 {
00682         if (m_count <= 1)
00683                 return;
00684 
00685         #ifdef _XSENS_LIST_RANGE_CHECKS
00686                 if (m_count != twin.m_count)
00687                         throw "List.twinSortAscending: sizes do not match";
00688         #endif
00689         uint32_t iteration = 0;
00690         uint32_t mini;
00691         T tmp;
00692         T2 tmp2;
00693         if (m_count > 1)
00694         while (iteration < m_count-1)
00695         {
00696                 mini = iteration;
00697                 for (uint32_t i=iteration+1;i<m_count;++i)
00698                 {
00699                         if (m_data[i] < m_data[mini])
00700                                 mini = i;
00701                 }
00702                 if (mini != iteration)
00703                 {
00704                         tmp = m_data[mini];
00705                         m_data[mini] = m_data[iteration];
00706                         m_data[iteration] = tmp;
00707 
00708                         tmp2 = twin.m_data[mini];
00709                         twin.m_data[mini] = twin.m_data[iteration];
00710                         twin.m_data[iteration] = tmp2;
00711                 }
00712                 ++iteration;
00713         }
00714 }
00715 
00716 template <typename T>
00717 void List<T>::remove(const uint32_t index) XSENS_LIST_THROW
00718 {
00719         #ifdef _XSENS_LIST_RANGE_CHECKS
00720                 if (index >= m_count)
00721                         throw "List.remove: index out of bounds";
00722         #endif
00723         if (index == m_count-1)
00724         {
00725                 --m_count;
00726                 return;
00727         }
00728         --m_count;
00729         for (unsigned i = index;i < m_count;++i)
00730                 m_data[i] = m_data[i+1];
00731 }
00732 
00733 template <typename T>
00734 void List<T>::removeTail(const uint32_t count) XSENS_LIST_THROW
00735 {
00736         #ifdef _XSENS_LIST_RANGE_CHECKS
00737                 if (count > m_count)
00738                         throw "List.removeTail: list size less than remove count";
00739         #endif
00740         if (m_count > count)
00741         {
00742                 m_count -= count;
00743                 return;
00744         }
00745         m_count = 0;
00746 }
00747 
00748 template <typename T>
00749 void List<T>::deleteAndRemoveTail(const uint32_t count) XSENS_LIST_THROW
00750 {
00751         #ifdef _XSENS_LIST_RANGE_CHECKS
00752                 if (count > m_count)
00753                         throw "List.deleteAndRemoveTail: list size less than remove count";
00754         #endif
00755         if (m_count > count)
00756         {
00757                 for (unsigned i = 0;i < count;++i)
00758                         delete m_data[--m_count];
00759                 return;
00760         }
00761         deleteAndClear();
00762 }
00763 
00764 template <typename T>
00765 void List<T>::freeAndRemoveTail(const uint32_t count) XSENS_LIST_THROW
00766 {
00767         #ifdef _XSENS_LIST_RANGE_CHECKS
00768                 if (count > m_count)
00769                         throw "List.freeAndRemoveTail: list size less than remove count";
00770         #endif
00771         if (m_count > count)
00772         {
00773                 for (unsigned i = 0;i < count;++i)
00774                         free(m_data[--m_count]);
00775                 return;
00776         }
00777         freeAndClear();
00778 }
00779 
00780 template <typename T>
00781 uint32_t List<T>::removeDuplicateEntries(void)
00782 {
00783         uint32_t removed = 0;
00784         for (uint32_t i=0;i < m_count; ++i)
00785         {
00786                 for (uint32_t j=i+1;j < m_count; ++j)
00787                 {
00788                         if (m_data[i] == m_data[j])
00789                         {
00790                                 remove(j);
00791                                 ++removed;
00792                                 --j;
00793                         }
00794                 }
00795         }
00796         return removed;
00797 }
00798 
00799 template <typename T>
00800 uint32_t List<T>::removeDuplicateEntriesDeref(void)
00801 {
00802         uint32_t removed = 0;
00803         for (uint32_t i=0;i < m_count; ++i)
00804         {
00805                 for (uint32_t j=i+1;j < m_count; ++j)
00806                 {
00807                         if (*(m_data[i]) == *(m_data[j]))
00808                         {
00809                                 remove(j);
00810                                 ++removed;
00811                                 --j;
00812                         }
00813                 }
00814         }
00815         return removed;
00816 }
00817 
00818 template <typename T>
00819 void List<T>::deleteAndRemove(const uint32_t index) XSENS_LIST_THROW
00820 {
00821         #ifdef _XSENS_LIST_RANGE_CHECKS
00822                 if (index >= m_count)
00823                         throw "List.deleteAndRemove: index out of bounds";
00824         #endif
00825         delete m_data[index];
00826         if (index == m_count-1)
00827         {
00828                 --m_count;
00829                 return;
00830         }
00831         --m_count;
00832         for (unsigned i = index;i < m_count;++i)
00833                 m_data[i] = m_data[i+1];
00834 }
00835 
00836 template <typename T>
00837 void List<T>::freeAndRemove(const uint32_t index) XSENS_LIST_THROW
00838 {
00839         #ifdef _XSENS_LIST_RANGE_CHECKS
00840                 if (index >= m_count)
00841                         throw "List.freeAndRemove: index out of bounds";
00842         #endif
00843         free(m_data[index]);
00844         if (index == m_count-1)
00845         {
00846                 --m_count;
00847                 return;
00848         }
00849         --m_count;
00850         for (unsigned i = index;i < m_count;++i)
00851                 m_data[i] = m_data[i+1];
00852 }
00853 
00854 template <typename T>
00855 template <typename TB>
00856 uint32_t List<T>::find(const TB& item) const
00857 {
00858         for (uint32_t i=0;i<m_count;++i)
00859                 if (((const T*)m_data)[i] == item)
00860                         return i;
00861         return XSENS_LIST_NOTFOUND;
00862 }
00863 
00864 template <typename T>
00865 uint32_t List<T>::find(const T item, InequalityFunction fnc) const
00866 {
00867         for (uint32_t i=0;i<m_count;++i)
00868                 if (!fnc(m_data[i],item))
00869                         return i;
00870         return XSENS_LIST_NOTFOUND;
00871 }
00872 
00873 template <typename T>
00874 template <typename TB>
00875 uint32_t List<T>::findDeref(const TB& item) const
00876 {
00877         for (uint32_t i=0;i<m_count;++i)
00878                 if (*(m_data[i]) == item)
00879                         return i;
00880         return XSENS_LIST_NOTFOUND;
00881 }
00882 
00883 template <typename T>
00884 template <typename TB>
00885 uint32_t List<T>::findSorted(const TB& item) const
00886 {
00887         if (m_count < CMT_LIST_LINEAR_SEARCH_TRESHOLD)                        // for small lists, it is faster to simply walk the list
00888                 return find(item);
00889 
00890         uint32_t x = m_count;
00891         uint32_t n = 1;
00892         uint32_t i;
00893 
00894         while(x >= n)
00895         {
00896                 i = (x + n) >> 1;
00897 
00898                 if (m_data[i-1] == item)
00899                         return i-1;
00900                 if (m_data[i-1] < item)
00901                         n = i+1;
00902                 else
00903                         x = i-1;
00904         }
00905         return XSENS_LIST_NOTFOUND;
00906 }
00907 
00908 template <typename T>
00909 template <typename TB>
00910 uint32_t List<T>::findSortedDeref(const TB& item) const
00911 {
00912         if (m_count < CMT_LIST_LINEAR_SEARCH_TRESHOLD)                        // for small lists, it is faster to simply walk the list
00913                 return findDeref(item);
00914 
00915         uint32_t x = m_count;
00916         uint32_t n = 1;
00917         uint32_t i;
00918 
00919         while(x >= n)
00920         {
00921                 i = (x + n) >> 1;
00922 
00923                 if (*(m_data[i-1]) == item)
00924                         return i-1;
00925                 if (*(m_data[i-1]) < item)
00926                         n = i+1;
00927                 else
00928                         x = i-1;
00929         }
00930         return XSENS_LIST_NOTFOUND;
00931 }
00932 
00933 template <typename T>
00934 uint32_t List<T>::insertSorted(const T& item)
00935 {
00936         uint32_t i;
00937         if (m_count < CMT_LIST_LINEAR_SEARCH_TRESHOLD)
00938         {
00939                 for (i=0;i<m_count;++i)
00940                         if (item < m_data[i])
00941                         {
00942                                 insert(item,i);
00943                                 return i;
00944                         }
00945                 append(item);
00946                 return m_count-1;
00947         }
00948         else
00949         {
00950                 uint32_t x = m_count;
00951                 uint32_t n = 1;
00952 
00953                 while(x >= n)
00954                 {
00955                         i = (x + n) >> 1;
00956 
00957                         if (m_data[i-1] == item)
00958                         {
00959                                 insert(item,i-1);
00960                                 return i-1;
00961                         }
00962                         if (m_data[i-1] < item)
00963                                 n = i+1;
00964                         else
00965                                 x = i-1;
00966                 }
00967                 insert(item,n-1);
00968                 return n-1;
00969         }
00970 }
00971 
00972 template <typename T>
00973 uint32_t List<T>::insertSortedDeref(const T& item)
00974 {
00975         uint32_t i;
00976         if (m_count < CMT_LIST_LINEAR_SEARCH_TRESHOLD)
00977         {
00978                 for (i=0;i<m_count;++i)
00979                         if (*item < *m_data[i])
00980                         {
00981                                 insert(item,i);
00982                                 return i;
00983                         }
00984                 append(item);
00985                 return m_count-1;
00986         }
00987         else
00988         {
00989                 uint32_t x = m_count;
00990                 uint32_t n = 1;
00991 
00992                 while(x >= n)
00993                 {
00994                         i = (x + n) >> 1;
00995 
00996                         if (*(m_data[i-1]) == *item)
00997                         {
00998                                 insert(item,i-1);
00999                                 return i-1;
01000                         }
01001                         if (*(m_data[i-1]) < *item)
01002                                 n = i+1;
01003                         else
01004                                 x = i-1;
01005                 }
01006                 insert(item,n-1);
01007                 return n-1;
01008         }
01009 }
01010 
01011 template <typename T>
01012 template <typename TB>
01013 uint32_t List<T>::insertSortedCopy(const TB& item)
01014 {
01015         uint32_t i;
01016         if (m_count < CMT_LIST_LINEAR_SEARCH_TRESHOLD)
01017         {
01018                 for (i=0;i<m_count;++i)
01019                         if (item < m_data[i])
01020                         {
01021                                 insertCopy<TB>(item,i);
01022                                 return i;
01023                         }
01024                 append(item);
01025                 return m_count-1;
01026         }
01027         else
01028         {
01029                 uint32_t x = m_count;
01030                 uint32_t n = 1;
01031 
01032                 while(x >= n)
01033                 {
01034                         i = (x + n) >> 1;
01035 
01036                         if (m_data[i-1] == item)
01037                         {
01038                                 insertCopy<TB>(item,i-1);
01039                                 return i-1;
01040                         }
01041                         if (m_data[i-1] < item)
01042                                 n = i+1;
01043                         else
01044                                 x = i-1;
01045                 }
01046                 insertCopy<TB>(item,n-1);
01047                 return n-1;
01048         }
01049 }
01050 
01051 template <typename T>
01052 void List<T>::deleteItemsOnDestroy(void)
01053 {
01054         if (m_jcf != NULL)
01055         {
01056                 m_jcf->disable();
01057                 delete m_jcf;
01058         }
01059         m_jcf = new JanitorClassFunc<List<T>, void>(*this,&List<T>::deleteAndClear);
01060 }
01061 
01062 template <typename T>
01063 void List<T>::freeItemsOnDestroy(void)
01064 {
01065         if (m_jcf != NULL)
01066         {
01067                 m_jcf->disable();
01068                 delete m_jcf;
01069         }
01070         m_jcf = new JanitorClassFunc<List<T>, void>(*this,&List<T>::freeAndClear);
01071 }
01072 
01073 template <typename T>
01074 template <typename TB>
01075 void List<T>::isDeepCopyOf(const List<T>& source)
01076 {
01077         m_count = 0;
01078         if (m_max < source.m_count)
01079                 resize(source.m_count);
01080         m_count = source.m_count;
01081         for (uint32_t i = 0;i<m_count;++i)
01082                 m_data[i] = new TB(*source.m_data[i]);
01083 }
01084 
01085 template <typename T>
01086 void List<T>::isShallowCopyOf(const List<T>& x)
01087 {
01088         m_count = 0;
01089         if (m_max < x.m_count)
01090                 resize(x.m_count);
01091         m_count = x.m_count;
01092         for (uint32_t i = 0;i<m_count;++i)
01093                 m_data[i] = x.m_data[i];
01094 }
01095 
01096 template <typename T>
01097 void List<T>::swap(const uint32_t i, const uint32_t j) XSENS_LIST_THROW
01098 {
01099         #ifdef _XSENS_LIST_RANGE_CHECKS
01100                 if (i >= m_count || j >= m_count)
01101                         throw "List.swap: index out of bounds";
01102         #endif
01103         T tmp = m_data[i];
01104         m_data[i] = m_data[j];
01105         m_data[j] = tmp;
01106 }
01107 
01108 template <typename T>
01109 void List<T>::reverse(void)
01110 {
01111         uint32_t half = m_count / 2;
01112         for (uint32_t i = 0, end=m_count-1; i < half; ++i,--end)
01113         {
01114                 T tmp = m_data[i];
01115                 m_data[i] = m_data[end];
01116                 m_data[end] = tmp;
01117         }
01118 }
01119 
01120 } // end of xsens namespace
01121 
01122 #endif        // _XSENS_LIST_H_2006_06_08
Generated on Sun May 8 08:41:38 2011 for iLab Neuromorphic Vision Toolkit by  doxygen 1.6.3