- Main Page
- Namespaces
- Classes
- Files
- Related Pages

# /Users/fpy/titan-1-5-MBARI/Mers/Generators/BFIG/ListManipulator.h

    00001
    00002 //
    00003 // Copyright (c) 2004           Model-based Embedded and Robotic Systems Group
    00004 // All Rights Reserved          Massachusetts Institute of Technology
    00005 //
    00006 // This software is provided as is. Model-based Embedded and Robotic Systems
    00007 // (MERS) group does not assume any responsibility.
    00008 //
    00009 // Organization:        Model-based Embedded and Robotic Systems Group
    00010 //                                      Massachusetts Institute of Technology
    00011 //
    00013 //# CHECKED MJP 08-07-2002
    00014
    00015 #ifndef __LISTMANIPULATOR__
    00016 #define __LISTMANIPULATOR__
    00017
    00018 #include <cstdlib>
    00019 #include <list>
    00020 #include <vector>
    00021
    00022 namespace Mers {
    00023         namespace Generators {
    00024                 namespace BFIG {
    00028                         template<typename T>
    00029                         class ListManipulator
    00030                         {
    00031                         public:
    00032                                 //----------------------------------
    00033                                 //      TYPE DEFINITIONS AND CONSTANTS
    00034                                 //----------------------------------
    00035                                 typedef bool (*comp_func)(T, T);
    00036                                 //template std::list<T>;
    00037                                 typedef std::list<T>  typeList;
    00038
    00039                                 //----------------------------------
    00040                                 //      CONSTRUCTOR
    00041                                 //----------------------------------
    00042                                 ListManipulator()
    00043                                 {
    00044                                 };
    00045
    00046                                 //----------------------------------
    00047                                 //      PUBLIC FUNCTION METHODS
    00048                                 //----------------------------------
    00049
    00050                                 void sort(std::vector<T> & lst, comp_func comp) const
    00051                                 {
    00053                                         std::vector<T> tmp = lst;
    00054                                         lst.clear();
    00055
    00056                                         typename std::vector<T>::iterator tmpIter;
    00057                                         for (tmpIter = tmp.begin(); tmpIter != tmp.end(); tmpIter++)
    00058                                         {
    00059                                                 merge(lst, *tmpIter, comp);
    00060                                         }
    00061                                 };
    00062
    00063                                 void  merge(std::vector<T> & lst1, std::vector<T> const & lst2, comp_func comp) const
    00064                                 {
    00065                                         typename std::vector<T>::iterator listIter;
    00066                                         typename std::vector<T>::const_iterator otherIter;
    00067
    00068                                         bool finishedOrigList = false;
    00069                                         for (otherIter = lst2.begin(), listIter = lst1.begin();
    00070                                                          otherIter != lst2.end(); otherIter++)
    00071                                         {
    00072                                                 if (finishedOrigList || listIter == lst1.end())
    00073                                                 {
    00074                                                         finishedOrigList = true;
    00075                                                         lst1.push_back((*otherIter));
    00076                                                 } else
    00077                                                 {
    00078                                                         while ( listIter != lst1.end() && comp(*listIter, *otherIter) )
    00079                                                         {
    00080                                                                 listIter++;
    00081                                                         }
    00082                                                         if (listIter == lst1.end())
    00083                                                         {
    00084                                                                 finishedOrigList = true;
    00085                                                                 lst1.push_back((*otherIter));
    00086                                                         } else
    00087                                                         {
    00088                                                                 lst1.insert(listIter, *otherIter);
    00089                                                         }
    00090                                                 }
    00091                                         }
    00092                                 };
    00093
    00094                                 void  merge(std::vector<T> & lst1, T item, comp_func comp) const
    00095                                 {
    00096                                         typename std::vector<T>::iterator iter;
    00097
    00098                                         for (iter = lst1.begin(); iter != lst1.end(); iter++)
    00099                                         {
    00100                                                 if (!(comp(*iter, item)))
    00101                                                 {
    00102                                                         lst1.insert(iter, item);
    00103                                                         return;
    00104                                                 }
    00105                                         }
    00106                                         lst1.push_back(item);
    00107                                 };
    00108
    00109
    00110                                 std::vector<T>  merge_out(std::vector<T> const &lst1, std::vector<T> const &lst2, comp_func comp) const
    00111                                 {
    00112                                         std::vector<T> res;
    00113                                         typename std::vector<T>::const_iterator firstIter;
    00114                                         typename std::vector<T>::const_iterator secondIter;
    00115
    00116                                         for (firstIter = lst1.begin(), secondIter = lst2.begin();
    00117                                                          firstIter != lst1.end() || secondIter != lst2.end();
    00118                                                          )
    00119                                         {
    00120                                                 if (firstIter == lst1.end())
    00121                                                 {
    00122                                                         res.push_back((*secondIter));
    00123                                                 } else
    00124                                                         if (secondIter == lst2.end())
    00125                                                         {
    00126                                                                 res.push_back((*firstIter));
    00127                                                         } else
    00128                                                         {
    00129                                                                 if (comp(*firstIter, *secondIter))
    00130                                                                 {
    00131                                                                         res.push_back(*firstIter);
    00132                                                                         firstIter++;
    00133                                                                 } else
    00134                                                                 {
    00135                                                                         res.push_back(*secondIter);
    00136                                                                         secondIter++;
    00137                                                                 }
    00138                                                         }
    00139                                         }
    00140
    00141                                         return res;
    00142                                 };
    00143
    00144
    00145                                 void sort(std::list<T> & lst, comp_func comp) const
    00146                                 {
    00148                                         std::list<T> tmp = lst;
    00149                                         lst.clear();
    00150
    00151                                         typename std::list<T>::iterator tmpIter;
    00152                                         for (tmpIter = tmp.begin(); tmpIter != tmp.end(); tmpIter++)
    00153                                         {
    00154                                                 merge(lst, *tmpIter, comp);
    00155                                         }
    00156                                 };
    00157
    00158                                 void  merge(std::list<T> & lst1, std::list<T> const & lst2, comp_func comp) const
    00159                                 {
    00160                                         typename std::list<T>::iterator listIter;
    00161                                         typename std::list<T>::const_iterator otherIter;
    00162
    00163                                         bool finishedOrigList = false;
    00164                                         for (otherIter = lst2.begin(), listIter = lst1.begin();
    00165                                                          otherIter != lst2.end(); otherIter++)
    00166                                         {
    00167                                                 if (finishedOrigList || listIter == lst1.end())
    00168                                                 {
    00169                                                         finishedOrigList = true;
    00170                                                         lst1.push_back((*otherIter));
    00171                                                 } else
    00172                                                 {
    00173                                                         while ( listIter != lst1.end() && comp(*listIter, *otherIter) )
    00174                                                         {
    00175                                                                 listIter++;
    00176                                                         }
    00177                                                         if (listIter == lst1.end())
    00178                                                         {
    00179                                                                 finishedOrigList = true;
    00180                                                                 lst1.push_back((*otherIter));
    00181                                                         } else
    00182                                                         {
    00183                                                                 lst1.insert(listIter, *otherIter);
    00184                                                         }
    00185                                                 }
    00186                                         }
    00187                                 };
    00188
    00189                                 void  merge(std::list<T> & lst1, T item, comp_func comp) const
    00190                                 {
    00191                                         typename std::list<T>::iterator iter;
    00192
    00193                                         for (iter = lst1.begin(); iter != lst1.end(); iter++)
    00194                                         {
    00195                                                 if (!(comp(*iter, item)))
    00196                                                 {
    00197                                                         lst1.insert(iter, item);
    00198                                                         return;
    00199                                                 }
    00200                                         }
    00201                                         lst1.push_back(item);
    00202                                 };
    00203
    00204
    00205                                 std::list<T>  merge_out(std::list<T> const &lst1, std::list<T> const &lst2, comp_func comp) const
    00206                                 {
    00207                                         std::list<T> res;
    00208                                         typename std::list<T>::const_iterator firstIter;
    00209                                         typename std::list<T>::const_iterator secondIter;
    00210
    00211                                         for (firstIter = lst1.begin(), secondIter = lst2.begin();
    00212                                                          firstIter != lst1.end() || secondIter != lst2.end();
    00213                                                          )
    00214                                         {
    00215                                                 if (firstIter == lst1.end())
    00216                                                 {
    00217                                                         res.push_back((*secondIter));
    00218                                                 } else
    00219                                                         if (secondIter == lst2.end())
    00220                                                         {
    00221                                                                 res.push_back((*firstIter));
    00222                                                         } else
    00223                                                         {
    00224                                                                 if (comp(*firstIter, *secondIter))
    00225                                                                 {
    00226                                                                         res.push_back(*firstIter);
    00227                                                                         firstIter++;
    00228                                                                 } else
    00229                                                                 {
    00230                                                                         res.push_back(*secondIter);
    00231                                                                         secondIter++;
    00232                                                                 }
    00233                                                         }
    00234                                         }
    00235
    00236                                         return res;
    00237                                 };
    00238
    00239
    00240                                 //private:
    00241
    00242                         };
    00243                 }
    00244         }
    00245 }
    00246
    00247 #endif //ndef __LISTMANIPULATOR__
    00248