- Main Page
- Classes
- Files

- File List

# OptFrame/Util/NSVector.hpp

    00001 /*
    00002 Author: Sabir Ribas
    00003 Date: 2010-03-10
    00004 Change Log:
    00005         2010-03-10      NSVector idealization and development of safe insertion, remotion and Shiftk neighborhood structure for one or more vectors (e.g. vector<T> or vector< vector<T> >).
    00006         2010-03-16      Development of Swapk neighborhood structure for template vector of vector.
    00007 */
    00008
    00009 #ifndef NSVECTOR_HPP
    00010 #define NSVECTOR_HPP
    00011
    00012 #include <vector>
    00013 #include <cstdio>
    00014 #include <iostream>
    00015 #include <cmath>
    00016
    00017 using namespace std;
    00018
    00019 template <class T>
    00020 class NSVector
    00021 {
    00022 public:
    00023
    00024         /* safe insertion and remotion - 2010-03-10 */
    00025
    00026         static bool insert(vector<T> & v, unsigned int rank, T o)
    00027         {
    00028                 if (rank < 0 || rank > v.size()) { cerr << "Warning [NSVector]: out of range insertion" << endl; return false; }
    00029                 v.insert(v.begin()+rank,o);
    00030                 return true;
    00031         };
    00032
    00033         static bool remove(vector<T> & v, unsigned int rank)
    00034         {
    00035                 if (rank < 0 || rank >= v.size()) { cerr << "Warning [NSVector]: out of range remotion" << endl; return false; }
    00036                 v.erase(v.begin()+rank);
    00037                 return true;
    00038         };
    00039
    00040         /* Shiftk - 2010-03-10 */
    00041
    00042         static bool shift1_apply(vector<T> & v, unsigned int rank1, unsigned int rank2)
    00043         {
    00044                 if (rank1 < 0 || rank1 >= v.size() || rank2 < 0 || rank2 >= v.size())
    00045                 { cerr << "Warning [NSVector]: out of range shift1" << endl; return false; }
    00046                 /*
    00047                 if (rank1 < rank2){
    00048                         v.insert(v.begin()+rank2+1,v[rank1]);
    00049                         v.erase(v.begin()+rank1);
    00050                 } else
    00051                 if (rank1 > rank2){
    00052                         v.insert(v.begin()+rank2,v[rank1]);
    00053                         v.erase(v.begin()+rank1+1);
    00054                 }
    00055                 */
    00056                 T aux;
    00057                 if(rank1 < rank2)
    00058                         for(int i = rank1; i < rank2; i++)
    00059                         {
    00060                                 aux = v[i];
    00061                                 v[i] = v[i+1];
    00062                                 v[i+1] = aux;
    00063                         }
    00064                 else
    00065                         for(int i = rank1; i > rank2; i--)
    00066                         {
    00067                                 aux = v[i];
    00068                                 v[i] = v[i-1];
    00069                                 v[i-1] = aux;
    00070                         }
    00071                 return true;
    00072         };
    00073
    00074         static bool shiftk_apply(vector<T> & v, unsigned int k, unsigned int rank1, unsigned int rank2)
    00075         {
    00076                 if (rank1 < 0 || rank1 + k > v.size() || rank2 < 0 || rank2 + k > v.size())
    00077                 { cerr << "Warning [NSVector]: out of range shiftk" << endl; return false; }
    00078                 if (rank1 < rank2) for (int i = k-1; i+1 > 0; i--) shift1_apply(v,rank1+i,rank2+i); else
    00079                 if (rank1 > rank2) for (int i = 0; i < k; i++) shift1_apply(v,rank1+i,rank2+i);
    00080                 return true;
    00081         };
    00082
    00083         static pair<int,pair<int,int> > shiftk_apply(vector<T> & v, pair<int,pair<int,int> > & m)
    00084         {
    00085                 int k = m.first, rank1 = m.second.first, rank2 = m.second.second;
    00086                 if (shiftk_apply(v,k,rank1,rank2)) return pair<int,pair<int,int> >(k, pair<int,int>(rank2,rank1));
    00087         };
    00088
    00089         static int shift1_size(const vector<T> &v) { return v.size()*v.size(); };
    00090
    00091         static pair<int,pair<int,int> > shiftk_move(const vector<T> &v, int k, int i)
    00092         {
    00093                 return pair<int,pair<int,int> >(k, pair<int,int>((i/v.size()), (i%v.size())));
    00094         };
    00095
    00096         static bool shiftk_canBeApplied(const vector<T> & v, pair<int,pair<int,int> > & m)
    00097         {
    00098                 int k = m.first, rank1 = m.second.first, rank2 = m.second.second;
    00099                 return !(rank1 < 0 || rank1 + k > v.size() || rank2 < 0 || rank2 + k > v.size() || rank1 == rank2);
    00100         };
    00101
    00102         static vector< pair<int,pair<int,int> > > * shiftk_appliableMoves(const vector<T> & v,int k)
    00103         {
    00104                 vector< pair<int,pair<int,int> > > * moves = new vector< pair<int,pair<int,int> > >;
    00105                 for (int i = 0 ; i < NSVector<int>::shift1_size(v) ; i++)
    00106                 {
    00107                         pair<int,pair<int,int> > m = NSVector<int>::shiftk_move(v,k,i);
    00108                         if (NSVector<int>::shiftk_canBeApplied(v,m)) moves->push_back(m);
    00109                 }
    00110                 return moves;
    00111         };
    00112
    00113         /* Shiftk with Two Vectors - 2010-03-10 */
    00114
    00115         static bool shift1_apply(vector<T> & v1, vector<T> & v2, unsigned int rank1, unsigned int rank2)
    00116         {
    00117                 if (rank1 < 0 || rank1 >= v1.size() || rank2 < 0 || rank2 > v2.size())
    00118                 { cerr << "Warning [NSVector]: out of range shift1 (v1,v2)" << endl; return false; }
    00119                 insert(v2,rank2,v1[rank1]);
    00120                 remove(v1,rank1);
    00121                 return true;
    00122         };
    00123
    00124         static bool shiftk_apply(vector<T> & v1, vector<T> & v2, unsigned int k, unsigned int rank1, unsigned int rank2)
    00125         {
    00126                 if (rank1 < 0 || rank1 + k > v1.size() || rank2 < 0 || rank2 > v2.size())
    00127                 { cerr << "Warning [NSVector]: out of range shiftk (v1,v2)" << endl; return false; }
    00128                 for (int i = k-1; i+1 > 0; i--) shift1_apply(v1,v2,rank1+i,rank2);
    00129                 return true;
    00130         };
    00131
    00132         static pair<int,pair<int,int> > shiftk_apply(vector<T> & v1, vector<T> & v2, pair<int,pair<int,int> > & m)
    00133         {
    00134                 int k = m.first, rank1 = m.second.first, rank2 = m.second.second;
    00135                 if (shiftk_apply(v1,v2,k,rank1,rank2)) return pair<int,pair<int,int> >(k, pair<int,int>(rank2,rank1));
    00136         };
    00137
    00138         static int shift1_size(const vector<T> &v1,const vector<T> &v2) { return v1.size()*(v2.size()+1); };
    00139
    00140         static pair<int,pair<int,int> > shiftk_move(const vector<T> &v1,const vector<T> &v2, int k, int i)
    00141         {
    00142                 return pair<int,pair<int,int> >(k, pair<int,int>((i/(v2.size()+1)), (i%(v2.size()+1))));
    00143         };
    00144
    00145         static bool shiftk_canBeApplied(vector<T> & v1, vector<T> & v2, pair<int,pair<int,int> > & m)
    00146         {
    00147                 int k = m.first, rank1 = m.second.first, rank2 = m.second.second;
    00148                 return !(rank1 < 0 || rank1 + k > v1.size() || rank2 < 0 || rank2 > v2.size());
    00149         };
    00150
    00151         static vector< pair<int,pair<int,int> > > * shiftk_appliableMoves(vector<T> & v1, vector<T> & v2, int k)
    00152         {
    00153                 vector< pair<int,pair<int,int> > > * moves = new vector< pair<int,pair<int,int> > >;
    00154                 for (int i = 0 ; i < NSVector<int>::shift1_size(v1,v2) ; i++)
    00155                 {
    00156                         pair<int,pair<int,int> > m = NSVector<int>::shiftk_move(v1,v2,k,i);
    00157                         if (NSVector<int>::shiftk_canBeApplied(v1,v2,m)) moves->push_back(m);
    00158                 }
    00159                 return moves;
    00160         };
    00161
    00162         static bool shiftk_canBeApplied(const vector< vector<T> > & v, pair<int, pair< pair<int,int>, pair<int,int> > > & m)
    00163         {
    00164                 int k = m.first, a = m.second.first.first, rank1 = m.second.first.second, b = m.second.second.first, rank2 = m.second.second.second;
    00165                 return !(rank1 < 0 || rank1 + k > v[a].size() || rank2 < 0 || rank2 > v[b].size() || a==b);
    00166         };
    00167
    00168         static vector< pair<int, pair< pair<int,int>,pair<int,int> > > > * shiftk_appliableMoves(const vector< vector<T> > & v, int k)
    00169         {
    00170                 vector< pair<int,pair< pair<int,int>, pair<int,int> > > > * moves = new vector< pair<int,pair< pair<int,int>, pair<int,int> > > >;
    00171
    00172                 for (int a = 0 ; a < v.size() ; a++)
    00173                 {
    00174                         for (int b = 0 ; b < v.size() ; b++)
    00175                         {
    00176                                 if (a==b) continue;
    00177
    00178                                 int size = NSVector<int>::shift1_size(v[a],v[b]);
    00179
    00180                                 for (int i = 0 ; i < size ; i++)
    00181                                 {
    00182                                         pair<int, pair<int,int> > mLinha = NSVector<int>::shiftk_move(v[a],v[b],k,i);
    00183                                         pair<int,pair< pair<int,int>,pair<int,int> > > m;
    00184                                         m.first = mLinha.first;
    00185                                         m.second.first.first = a;
    00186                                         m.second.first.second = mLinha.second.first;
    00187                                         m.second.second.first = b;
    00188                                         m.second.second.second = mLinha.second.second;
    00189                                         if (NSVector<int>::shiftk_canBeApplied(v,m)) moves->push_back(m);
    00190                                 }
    00191                         }
    00192                 }
    00193
    00194                 return moves;
    00195         };
    00196
    00197         static pair<int,pair < pair<int,int>,pair<int,int> > >
    00198         shiftk_apply(vector< vector<T> > & v, pair<int,pair < pair<int,int>,pair<int,int> > > & m)
    00199         {
    00200                 int k = m.first, a = m.second.first.first, rank1 = m.second.first.second, b = m.second.second.first, rank2 = m.second.second.second;
    00201                 if (shiftk_apply(v[a],v[b],k,rank1,rank2))
    00202                         return pair<int,pair < pair<int,int>,pair<int,int> > >(k,
    00203                                 pair< pair<int,int> ,pair<int,int> > ( pair<int,int>(b,rank2) , pair<int,int>(a,rank1) ) );
    00204         };
    00205
    00206         /* Swapk */
    00207
    00208         //...
    00209
    00210         /* Swapk with Two Vectors - 2010-03-16 */
    00211
    00212         static bool swap1_apply(vector<T> & v1, vector<T> & v2, unsigned int rank1, unsigned int rank2)
    00213         {
    00214                 if (rank1 < 0 || rank1 >= v1.size() || rank2 < 0 || rank2 >= v2.size())
    00215                 { cerr << "Warning [NSVector]: out of range swap1 (v1,v2)" << endl; return false; }
    00216                 T aux = v1[rank1];
    00217                 v1[rank1] = v2[rank2];
    00218                 v2[rank2] = aux;
    00219                 return true;
    00220         };
    00221
    00222         static bool swapk_apply(vector<T> & v1, vector<T> & v2, unsigned int k1, unsigned int k2, unsigned int rank1, unsigned int rank2)
    00223         {
    00224                 if (rank1 < 0 || rank1 + k1 > v1.size() || rank2 < 0 || rank2 + k2 > v2.size())
    00225                 { cerr << "Warning [NSVector]: out of range swapk (v1,v2)" << endl; return false; }
    00226                 if (k1 == k2) for (int i = 0; i < k1; i++) swap1_apply(v1,v2,rank1+i,rank2+i); else
    00227                 if (k1 > k2) {
    00228                         for (int i = 0; i < k1 - k2; i++) swap1_apply(v1,v2,rank1+i,rank2+i);
    00229                         shiftk_apply(v1,v2,k1-k2,rank1+k2,rank2+k2);
    00230                 } else
    00231                 if (k1 < k2) {
    00232                         for (int i = 0; i < k2 - k1; i++) swap1_apply(v1,v2,rank1+i,rank2+i);
    00233                         shiftk_apply(v2,v1,k2-k1,rank2+k1,rank1+k1);
    00234                 }
    00235                 return true;
    00236         };
    00237
    00238         static pair< pair<int,int> , pair<int,int> > shiftk_apply(vector<T> & v1, vector<T> & v2, pair< pair<int,int> , pair<int,int> > & m)
    00239         {
    00240                 int k1 = m.first.first, k2 = m.first.second, rank1 = m.second.first, rank2 = m.second.second;
    00241                 if (swapk_apply(v1,v2,k1,k2,rank1,rank2)) return pair< pair<int,int> , pair<int,int> >( pair<int,int>(k2,k1) , pair<int,int>(rank2,rank1));
    00242         };
    00243
    00244         static int swap1_size(const vector<T> &v1, const vector<T> &v2) { return v1.size()*v2.size(); };
    00245
    00246         static pair< pair<int,int>,pair<int,int> > swapk_move(const vector<T> &v1,const vector<T> &v2, int k1, int k2, int i)
    00247         {
    00248                 return pair< pair<int,int>,pair<int,int> >( pair<int,int>(k1,k2), pair<int,int>( i/v2.size() , i%v2.size() ) );
    00249         };
    00250
    00251         static bool swapk_canBeApplied(const vector<T> & v1, const vector<T> & v2, pair< pair<int,int>,pair<int,int> > & m)
    00252         {
    00253                 int k1 = m.first.first, k2 = m.first.second, rank1 = m.second.first, rank2 = m.second.second;
    00254                 return !(rank1 < 0 || rank1 + k1 > v1.size() || rank2 < 0 || rank2 + k2 > v2.size());
    00255         };
    00256
    00257         static vector< pair< pair<int,int>,pair<int,int> > > * swapk_appliableMoves(vector<T> & v1, vector<T> & v2, int k1, int k2)
    00258         {
    00259                 vector< pair< pair<int,int>,pair<int,int> > > * moves = new vector< pair< pair<int,int>,pair<int,int> > >;
    00260                 for (int i = 0 ; i < NSVector<int>::swap1_size(v1,v2) ; i++)
    00261                 {
    00262                         pair< pair<int,int>,pair<int,int> > m = NSVector<int>::swapk_move(v1,v2,k1,k2,i);
    00263                         if (NSVector<int>::swapk_canBeApplied(v1,v2,m)) moves->push_back(m);
    00264                 }
    00265                 return moves;
    00266         };
    00267
    00268         static bool swapk_canBeApplied(const vector< vector<T> > & v, pair< pair<int,int>, pair< pair<int,int>, pair<int,int> > > & m)
    00269         {
    00270                 int k1 = m.first.first, k2 = m.first.second,
    00271                         a  = m.second.first.first, rank1 = m.second.first.second, b = m.second.second.first, rank2 = m.second.second.second;
    00272                 return !(rank1 < 0 || rank1 + k1 > v[a].size() || rank2 < 0 || rank2 + k2 > v[b].size() || a==b);
    00273         };
    00274
    00275         static vector< pair< pair<int,int> , pair< pair<int,int>,pair<int,int> > > > * swapk_appliableMoves(const vector< vector<T> > & v, int k1, int k2)
    00276         {
    00277                 vector< pair< pair<int,int> , pair< pair<int,int>,pair<int,int> > > > * moves =
    00278                         new vector< pair< pair<int,int> , pair< pair<int,int>,pair<int,int> > > >;
    00279
    00280                 for (int a = 0 ; a < v.size() ; a++)
    00281                 {
    00282                         //for (int b = 0 ; b < v.size() ; b++)
    00283                         for (int b = a+1 ; b < v.size() ; b++)
    00284                         {
    00285                                 //if (a==b) continue;
    00286
    00287                                 int size = NSVector<int>::swap1_size(v[a],v[b]);
    00288
    00289                                 for (int i = 0 ; i < size ; i++)
    00290                                 {
    00291                                         pair< pair<int,int> , pair<int,int> > mLinha = NSVector<int>::swapk_move(v[a],v[b],k1,k2,i);
    00292                                         pair< pair<int,int> , pair< pair<int,int>,pair<int,int> > > m;
    00293                                         m.first = mLinha.first; // pair
    00294                                         m.second.first.first = a;
    00295                                         m.second.first.second = mLinha.second.first;
    00296                                         m.second.second.first = b;
    00297                                         m.second.second.second = mLinha.second.second;
    00298                                         if (NSVector<int>::swapk_canBeApplied(v,m)) moves->push_back(m);
    00299                                 }
    00300                         }
    00301                 }
    00302
    00303                 return moves;
    00304         };
    00305
    00306         static pair< pair<int,int> , pair < pair<int,int>,pair<int,int> > >
    00307         swapk_apply(vector< vector<T> > & v, pair< pair<int,int> , pair < pair<int,int>,pair<int,int> > > & m)
    00308         {
    00309                 int k1 = m.first.first, k2 = m.first.second,
    00310                         a  = m.second.first.first, rank1 = m.second.first.second, b = m.second.second.first, rank2 = m.second.second.second;
    00311                 if (swapk_apply(v[a],v[b],k1,k2,rank1,rank2))
    00312                         return pair< pair<int,int> ,pair < pair<int,int>,pair<int,int> > >( pair<int,int>(k2,k1) ,
    00313                                 pair< pair<int,int>,pair<int,int> > ( pair<int,int>(b,rank2) , pair<int,int>(a,rank1) ) );
    00314         };
    00315
    00316         /* Swapk - 2010-02-11 */
    00317
    00318         static bool swap1_apply(vector<T> & v, unsigned int rank1, unsigned int rank2)
    00319         {
    00320                 if (rank1 < 0 || rank1 >= v.size() || rank2 < 0 || rank2 >= v.size())
    00321                 { cerr << "Warning [NSVector]: out of range swap1" << endl; return false; }
    00322
    00323                 T aux = v[rank1];
    00324                 v[rank1] = v[rank2];
    00325                 v[rank2] = aux;
    00326
    00327                 return true;
    00328         };
    00329
    00330         static bool swapk_apply(vector<T> & v, unsigned int k1, unsigned int k2, unsigned int rank1, unsigned int rank2)
    00331         {
    00332                 if (rank1 < 0 || rank1 + k1 > v.size() || rank2 < 0 || rank2 + k2 > v.size())
    00333                 { cerr << "Warning [NSVector]: out of range swapk" << endl; return false; }
    00334                 int k = min(k1,k2);
    00335                 for (int i = 0; i < k; i++) swap1_apply(v,rank1+i,rank2+i);
    00336                 if (k2 > k1) shiftk_apply(v,k2-k,rank2+k,rank1+k); else
    00337                 if (k1 > k2) shiftk_apply(v,k1-k,rank1+k,rank2+k);
    00338                 return true;
    00339         };
    00340
    00341         static pair<pair<int,int>,pair<int,int> > swapk_apply(vector<T> & v, pair<pair<int,int>,pair<int,int> > & m)
    00342         {
    00343                 int k1 = m.first.first, k2 = m.first.second, rank1 = m.second.first, rank2 = m.second.second;
    00344                 if (swapk_apply(v,k1,k2,rank1,rank2)) return pair<pair<int,int>,pair<int,int> >(pair<int,int>(k2,k1),pair<int,int>(rank2,rank1));
    00345         };
    00346
    00347         static int swap1_size(const vector<T> &v) { return v.size()*v.size(); };
    00348
    00349         static pair<pair<int,int>,pair<int,int> > swapk_move(const vector<T> &v, int k1, int k2, int i)
    00350         {
    00351                 return pair<pair<int,int>,pair<int,int> >(pair<int,int>(k1,k2), pair<int,int>((i/v.size()), (i%v.size())));
    00352         };
    00353
    00354         static bool swapk_canBeApplied(const vector<T> & v, pair<pair<int,int>,pair<int,int> > & m)
    00355         {
    00356                 int k1 = m.first.first, k2 = m.first.second, rank1 = m.second.first, rank2 = m.second.second;
    00357                 return !(rank1 < 0 || rank1 + k1 > v.size() || rank2 < 0 || rank2 + k2 > v.size() || rank1 == rank2 ||
    00358                                 !( rank2+k2 <= rank1 && ! rank1+k1 <= rank2 || ! rank2+k2 <= rank1 && rank1+k1 <= rank2 ) );
    00359         };
    00360
    00361         static vector< pair<pair<int,int>,pair<int,int> > > * swapk_appliableMoves(const vector<T> & v,int k1,int k2)
    00362         {
    00363                 vector< pair<pair<int,int>,pair<int,int> > > * moves = new vector< pair<pair<int,int>,pair<int,int> > >;
    00364                 for (int i = 0 ; i < NSVector<int>::swap1_size(v) ; i++)
    00365                 {
    00366                         pair<pair<int,int>,pair<int,int> > m = NSVector<int>::swapk_move(v,k1,k2,i);
    00367                         if (NSVector<int>::swapk_canBeApplied(v,m)) moves->push_back(m);
    00368                 }
    00369                 return moves;
    00370         };
    00371
    00372 };
    00373
    00374 #endif /* NSVECTOR_HPP */

All Classes Functions