two-top.cpp

//~~~START:Wed, 19-Oct-2022, 12:50:27 IST
//~~~Author:Rajesh Pandian M | mrprajesh.co.in 
#include <bits/stdc++.h>
using namespace std;

template <typename T>
void print(const vector<T> &vec){
  for(const auto &v: vec)
    cout << setw(2) << v << ' ';
  cout<< '\n';
}

//Possible implementations of swap_ranges in c++17
//Assumes vectors are of same size and to be swaped items are of same size
// Not used in our functions. Just keeping for references.
template<class ForwardIt1, class ForwardIt2>
constexpr ForwardIt2 swap_rangess(ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2) {
  while (first1 != last1) {
      std::iter_swap(first1++, first2++);
  }
  return first2;
}

// Assumes two vectors need not be same size 
// To be swaped items need not be of same size
template<class ForwardIt1, class ForwardIt2>
constexpr ForwardIt2 swap_vectors(ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2) {
  
  while (first1 != last1 && first2 !=last2 ) {
    std::iter_swap(first1++, first2++);
  }
  
  if(first1 != last1){
    std::move(first1,last1,first2);
  }
  if(first2 != last2){
    std::move(first2,last2,first1);
  }
    
  return first2;
}

void two_opt(vector<int> r, int i, int j){
    //~ if(i >=0 && j >=0 && i < r.size() && j <= r.size())
      reverse(r.begin()+i, r.begin()+j);
      printf("(%d,%d): ",i,j);
      print(r);
}

void two_opt_star(vector<int> r1,vector<int> r2, int i, int j){
  size_t nElementA = r1.size()-i;
  size_t nElementB = r2.size()-j;
  cout<< "#elements from r1: "<< nElementA << " idxfrom:" << i << endl;
  cout<< "#elements from r2: "<< nElementB << " idxfrom:" << j << endl;

  size_t r1Size = r1.size();
  size_t r2Size = r2.size();
  
  if(nElementA < nElementB) 
    r1.resize(r1Size - nElementA + nElementB); 
  else if (nElementA > nElementB)
    r2.resize(r2Size + nElementA - nElementB);
  
  //~ print(r1);print(r2);
  
  swap_vectors(r1.begin()+i,r1.end(), r2.begin()+j,r2.end());
  

  r1.resize(r1Size - nElementA + nElementB); r1.shrink_to_fit();
  r2.resize(r2Size + nElementA - nElementB); r2.shrink_to_fit();
  
  print(r1);print(r2);
}


int main(int argc, char* argv[]){
  
  
  //~ To Test Two-opt
  //~ vector<int> r1 = { 0, 1, 2, 3, 4, 5, 6, 7};
  //~ for(int i=0, end=r1.size(); i < end; ++i ){
    //~ for(int j=0; j <= end; ++j){
      //~ two_opt(r1,i,j);
    //~ }
  //~ }
  
  //                          v
  vector<int> r1 = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  vector<int> r2 = {10,11,12,13,14,15,16,17,18,19};
  //                                   ^
  
  //~ std::cout<< "R1Size: " << r1.size()  << '\n';
  //~ std::cout<< "R2Size: " << r2.size()  << '\n';
  
  print(r1);print(r2);
  
  int i = 3;   
  int j = 6;   
  // assert i < j?
  two_opt_star(r1,r2,i,j);
  
  
  //~ for(int i=0, end=r1.size(); i < end; ++i ){
    //~ for(int j=0, endJ=r2.size(); j < endJ; ++j){
      //~ two_opt_star(r1,r2, i,j);
    //~ }
  //~ }
  
  return 0;
}

output of two-opt

(0,0):  0  1  2  3  4  5  6  7
(2,5):  0  1  4  3  2  5  6  7 

output of two-opt-star

 0  1  2  3  4  5  6  7  8  9 
10 11 12 13 14 15 16 17 18 19 
#elements from r1: 7 idxfrom:3
#elements from r2: 4 idxfrom:6
 0  1  2 16 17 18 19 
10 11 12 13 14 15  3  4  5  6  7  8  9