#include <cassert>
#include <iostream>
#include <algorithm>
#include "random.h"
#include "index.h"
#include "sorting.h"
#include "sorting_cost.h"

using namespace std;

int main()
{
  for (bigint n = 0;n <= 128;++n)
    for (bigint wordsize = 0;wordsize < 20;++wordsize) {
      cout << "sorttest " << n << ' ' << wordsize << '\n' << flush;

      vector<vector<bit>> x;
      for (bigint j = 0;j < n;++j) {
        vector<bit> xj;
        for (bigint w = 0;w < wordsize;++w)
          xj.push_back(bit(random_bool()));
        x.push_back(xj);
      }

      vector<vector<bit>> y = x;

      bigint ops = -bit::ops();
      sorting(y);
      assert(ops+bit::ops() == sorting_cost(n,wordsize));

      vector<bigint> xint;
      for (bigint j = 0;j < n;++j)
        xint.push_back(index_value(x.at(j)));

      vector<bigint> yint;
      for (bigint j = 0;j < n;++j)
        yint.push_back(index_value(y.at(j)));

      sort(xint.begin(),xint.end());
      for (bigint j = 0;j < n;++j)
        assert(xint.at(j) == yint.at(j));
    }

  return 0;
}