#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <iostream>
using namespace std;

class Checksums
{
  int N;
  static const int maxNfactor = 3;
  int **M;
  int rank;
protected:
  int K;
  int maxN;
private:
  void swap(int i, int j);
  void doxor(int i, int j);
  void cleanlast();
  void cleanall();
  void gaussian();
  int uselast();
  void newp(int *p);
  void newprand();
  void newpdegree(int q);
public:
  Checksums(int K_);
  ~Checksums();
  int rcvpacket();
  int rcvpacket(int q);
  int rcvpacket(int *p);
  void pr();
  int sample();
};

class ChecksumsPerf: public Checksums
{
  int *prob;
public:
  ChecksumsPerf(int K_);
  ~ChecksumsPerf();
  void rate(int T);
};

void randseed();

int main()
{
  randseed();
  ChecksumsPerf c(20);
  c.rate(100003);
}

void ChecksumsPerf::rate(int T)
{
  for(int i=0;i<=maxN-K;i++)
    prob[i]=0;
  for(int t=0;t<T;t++)
  {
    int excess=sample();
    for(int i=excess;i<=maxN-K;i++)
      prob[i]++;
  }
  char s[1024];
  sprintf(s,"perf-K%d-maxN%d-T%d.csv",K,maxN,T);
  FILE *f=fopen(s,"w");
  fprintf(f,"   ,Perf: K=%d maxN=%d T=%d\r\n",K,maxN,T);
  for(int i=0;i<=maxN-K;i++)
    fprintf(f,"%3d, %f\r\n",i,(double)prob[i]/T);
  fclose(f);
}

ChecksumsPerf::ChecksumsPerf(int K_)
: Checksums(K_)
{
  prob=new int[maxN-K+1];
}

ChecksumsPerf::~ChecksumsPerf()
{
  delete[] prob;
}

int Checksums::sample()
{
  N=0;
  rank=0;
  int i;
  for(i=1; i<=maxN && rcvpacket(3)<K; i++)
    ;
  return i-K;
}

int Checksums::rcvpacket()
{
  newprand();
  return uselast();
}

int Checksums::rcvpacket(int q)
{
  newpdegree(q);
  return uselast();
}

int Checksums::rcvpacket(int *p)
{
  newp(p);
  return uselast();
}

int Checksums::uselast()
{
  cleanlast();
  if(rank<K)
    if(M[N-1][rank])
    {
      swap(rank,N-1);
      rank++;
      cleanall();
      gaussian();
    }
  return rank;
}

void Checksums::gaussian()
{
  int i;
  if(!(rank<K))
    return;
  for(i=rank;i<N;i++)
    if(M[i][rank])
      break;
  if(i>=N)
    return;
  swap(rank,i);
  rank++;
  cleanall();
  gaussian();
}

void Checksums::cleanall()
{
  for(int i=rank;i<N;i++)
    if(M[i][rank-1])
      doxor(i,rank-1);
}

void Checksums::cleanlast()
{
  for(int i=0;i<rank;i++)
    if(M[N-1][i])
      doxor(N-1,i);
}

void Checksums::doxor(int i, int j)
{
  for(int k=0;k<K;k++)
    M[i][k]^=M[j][k];
}

void Checksums::swap(int i, int j)
{
  int *row;
  row=M[i];
  M[i]=M[j];
  M[j]=row;
}

void Checksums::newpdegree(int q)
{
  N++;
  for(int i=0;i<K;i++)
    M[N-1][i]=0;

  for(int n=0;n<q;n++)
  {
    int i = rand()%(K-n);
    int j = -1;
    for(;i>=0;i--)
    {
      j++;
      for(;M[N-1][j];j++)
        ;
    }
    M[N-1][j]=1;
  }
}

void Checksums::newprand()
{
  N++;
  for(int i=0;i<K;i++)
    M[N-1][i]=rand()%2;
}

void Checksums::pr()
{
  printf("M[%d][%d]=\r\n",N,K);
  for(int i=0;i<N;i++)
  {
    printf("%3d:",i);
    for(int j=0;j<K;j++)
      printf(" %s",M[i][j]?"X":"-");
    printf("\r\n");
  }
}

void Checksums::newp(int *p)
{
  N++;
  for(int i=0;i<K;i++)
    M[N-1][i]=p[i];
}

Checksums::Checksums(int K_)
{
  K=K_;
  maxN=K*maxNfactor;
  N=0;
  M=new (int*)[maxN];
  for(int i=0;i<maxN;i++)
    M[i]=new int[K];
  rank=0;
}

Checksums::~Checksums()
{
  for(int i=0;i<maxN;i++)
    delete[] M[i];
  delete[] M;
}

void randseed()
{
  int ti=time(0);
  printf("srand=%d\r\n",ti);
  srand(ti);
}