/*
  Berechnung von Frequenzen ohne Intermodulation.

  Modulationen ( f1 < f2 ):
  f1
  2*f1
  3*f1

  f1 + f2
  f2 - f1
  
  2*f1 - f2
  2*f2 - f1

  3*f1 - 2*f2
  3*f2 - 2*f1

  4*f1 - 3*f2
  4*f2 - 3*f1
  
  gcc -O3 -Wall -Wextra  -pedantic -o freq2 freq2.c 
  gcc -gdwarf-3 -Wall -Wextra  -pedantic -o freq2 freq2.c 

 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare_ints(const void* a, const void* b)
{
  int arg1 = *(const int*)a;
  int arg2 = *(const int*)b;
  return (arg1 > arg2) - (arg1 < arg2);   
}

int modulation_mem(int nfreqs, int **mods )
{
  // Gross genug fuer alle Kombinationen in modulations().
  int nmods = 3*nfreqs + 4*nfreqs*(nfreqs-1);
  *mods = (int*) malloc(nmods*sizeof(int));
  memset( *mods, 0, nmods*sizeof(int));
  return 0;
}

int modulations( const int *freqs, const int nfreqs, int **mods)
{
  int cnt = 0;
  // f1 < f2 < ... < fn
  for( int i=0; i<nfreqs; ++i ) {
    // f1
    (*mods)[cnt++] = freqs[i];
    // 2*f1
    (*mods)[cnt++] = 2*freqs[i];
    // 3*f1
    (*mods)[cnt++] = 3*freqs[i];

    for( int j=i+1; j<nfreqs; ++j ) {
      // f1 + f2
      (*mods)[cnt++] = freqs[i] + freqs[j];
      // f2 - f1
      (*mods)[cnt++] = abs(freqs[j] - freqs[i]);
      // 2*f1 - f2
      (*mods)[cnt++] = abs(2*freqs[i] - freqs[j]);
      // 2*f2 - f1
      (*mods)[cnt++] = abs(2*freqs[j] - freqs[i]);
      // 3*f1 - 2*f2
      (*mods)[cnt++] = abs(3*freqs[i] - 2*freqs[j]);
      // 3*f2 - 2*f1
      (*mods)[cnt++] = abs(3*freqs[j] - 2*freqs[i]);
      // 4*f1 - 3*f2
      (*mods)[cnt++] = abs(4*freqs[i] - 3*freqs[j]);
      // 4*f2 - 3*f1
      (*mods)[cnt++] = abs(4*freqs[j] - 3*freqs[i]);      
    }
  }
  qsort( *mods, cnt, sizeof(int), compare_ints);
  return cnt;
}

/* Sind die Modulationen gueltig.
   mods ist sortiert.
 */
int valid_mods( const int* mods, int nms, int bw)
{
  for( int i=0; i<nms-1; ++i ) {
    if( abs(mods[i]-mods[i+1]) < bw ) {
      // Modulation < bw
      return 0;
    }
    /*
    if( mods[i]==mods[i+1] ) {
      // Modulation mit Differenz = 0.
      return 0;
    }
    */
  }
  return 1;
}

void show_mods( const int* mods, int nms)
{
  printf("modulations: " );
  for( int i=0; i<nms; ++i ) {
    printf( "%d ", mods[i] );
  }
}

void show_freqs(int cnt, const int* freqs, int n)
{
  printf("%3d freqs: ", cnt );
  for( int i=0; i<n; ++i ) {
    printf( "%d ", freqs[i] );
  }
}

int next_freqs(int what, int **freqs, int nfreqs, int n2, int max, int bw)
{
  if( n2<0 ) {
    return -1;
  }
  if( what == 0 ) {    
    // selbe Stufe
    (*freqs)[n2] += bw;
  } else if( what == 1 ) {
    // naechste Stufe
    if( n2 < nfreqs-1 ) {
      n2++;
      (*freqs)[n2] = (*freqs)[n2-1] + bw;
    } else {
      n2 = -1;
    }
  }
  
  if( n2>=0 ) {
    if( (*freqs)[n2] > max ) {
      n2 = next_freqs(0, freqs, nfreqs, n2-1, max, bw);
    }
  }
  
  return n2;
}

int main( int argc, char *argv[] )
{
  int n = 6;
  int start = 0;
  int max = 50;
  int bw = 1;
  int cnt = 0;
  
  if( argc == 5 ) {
    sscanf(argv[1], "%d", &n);
    sscanf(argv[2], "%d", &start);
    sscanf(argv[3], "%d", &max);
    sscanf(argv[4], "%d", &bw);
    
    if( n < 3 ) {
      printf("Usage: freq2 N min max bw\nN must be greater 2.\n");
      return 2;
    }
  } else {
    printf("Usage: freq2 N min max bw\n");
    return 1;
  }
  
  int nms, n2;
  int *mods = 0;
  int *freqs = (int*) malloc( n*sizeof(int));
  modulation_mem( n, &mods);
  
  freqs[0] = start;
  freqs[1] = start + bw;
  n2 = 1;
  
  nms = modulations(freqs, n2+1, &mods);
  
  while( n2>=0 ) {
    if( valid_mods( mods, nms, bw ) ) {
      if( n2 == n-1 ) {
	// Loesung. Alle Frequenzen gesetzt.
	show_freqs(++cnt, freqs, n2+1);
	//printf("\t\t");
	//show_mods( mods, nms );
	printf( "\n" );	
	if( freqs[n-1] < max ) {
	  // Suche nur kuerzere Loesungen:
	  max = freqs[n-1];
	}
	// Suche weiter in der letzten Stufe 
	n2 = next_freqs(0, &freqs, n, n2, max, bw);
      } else {
	// Gueltig, aber noch keine Loesung
	// Suche weiter in der naechsten Stufe
	n2 = next_freqs(1, &freqs, n, n2, max, bw);
      }
    } else {
      // Nicht gueltig: weiter oder backtrack
      n2 = next_freqs(0, &freqs, n, n2, max, bw);
    }
    if( n2 < 0 ) {
      printf("Alle Min. Kombinationen durchsucht.\n");
      break;
    }
    nms = modulations(freqs, n2+1, &mods);
  }
    
  free(mods);
  free(freqs);
}