## A Burrows Wheeler Transform Implementation

This is a simple, inefficient implementation of the Burrows-Wheeler transform in C++. I wrote it just to play around with the algorithm, not for any practical application. It takes a single text file as the input, then performs the transform and reverses it:

```
#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

void bwt(string input,string &bwt_str,int &primaryidx) {

vector<string> rotations;

// 1. generate rotations of input
cout << "rotations:" << endl;
for(int n=0;n<input.size();n++) {
string s;

s += input[n];
for(int i=n+1;i!=n;i++) {
if(i==input.size()) i=0;
s += input[i];
if(i==input.size()-1) i=-1;
}
rotations.push_back(s);
cout << s << endl;
}

// 2. sort
cout << "sorted:" << endl;
sort(rotations.begin(),rotations.end());
for(size_t n=0;n<rotations.size();n++) {
cout << rotations[n] << endl;
}

bwt_str.clear();
for(size_t n=0;n<rotations.size();n++) {
bwt_str += rotations[n].substr(rotations[n].size()-1,1);
if(rotations[n] == input) {primaryidx = n;}
}
cout << "bwt string: " << bwt_str << endl;
cout << "primaryidx: " << primaryidx << endl;
}

string rbwt(string bwt_str,int primaryidx) {

vector<string> cur_str;

for(size_t n=0;n<bwt_str.size();n++) {
string s;
s = bwt_str.substr(n,1);
cur_str.push_back(s);
}

for(;cur_str[0].size() < bwt_str.size();) {
vector<string> new_str = cur_str;
sort(new_str.begin(),new_str.end());

for(size_t n=0;n<cur_str.size();n++) {
cur_str[n] = cur_str[n] + new_str[n].substr(new_str[n].size()-1,1);
}
}

cout << "reversed transform:" << endl;
for(size_t n=0;n<cur_str.size();n++) {
cout << cur_str[n] << endl;
}

sort(cur_str.begin(),cur_str.end());

cout << "Original String: " << cur_str[primaryidx] << endl;

return cur_str[primaryidx];

}

int main(int argc,char **argv) {

string s;

ifstream infile(argv[1]);

for(;!infile.eof();) {
char c = (char)infile.get();

if(!infile.eof()) s += string(1,c);
}
cout << "input: " << s << "END" << endl;

string bwt_str;
int primaryidx;

bwt(s,bwt_str,primaryidx);

rbwt(bwt_str,primaryidx);
}
```