#include "sorting.h"
#include <algorithm>
#include <iostream>
#include <assert.h>
using namespace std;
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
int tmp [N];
int A [N];
for(int i = 0; i < N; i++){
A[i] = i;
tmp[i] = S[i];
}
//go backwards
for(int i = M-1; i >= 0; i--){
swap(A[X[i]], A[Y[i]]);
}
for(int i = 0; i < M; i++){
swap(A[X[i]], A[Y[i]]);
swap(S[X[i]], S[Y[i]]);
bool done = false;
for(int j = 0; j < N; j++){
if(S[j] != A[j]){
int kva = 0;
for(int k = 0; k < N; k++){
if(S[k] == A[j]){
kva = k;
}
}
swap(S[j], S[kva]);
P[i] = j;
Q[i] = kva;
done = true;
break;
}
}
if(!done){
P[i] = 0;
Q[i] = 0;
}
}
for(int i = 0; i < N; i++){
assert(S[i] == i);
}
for(int i = 0; i < M; i++){
swap(tmp[X[i]], tmp[Y[i]]);
swap(tmp[P[i]], tmp[Q[i]]);
}
for(int i = 0; i < N; i++){
assert(tmp[i] == i);
}
assert(false);
cerr << "ASSERTS OK" << endl;
/*for(int i = 0; i < N; i++){
cerr << A[i] << " ";
}
cerr << endl;
for(int i = 0; i < N; i++){
cerr << S[i] << " ";
}
cerr << endl;*/
return M;
}
