// newfrold.cc (c) Kris COOLSAET, Belgium
// ============================================================
// More info: http://turing.hogent.be/~kc/cds/part15.htm
//
// Computes new CDSs from a given CDS by multiplying
// every element with the same constant and computing 'shifts'.
// Displays all possible CDSs and lists - for each shift - the
// multiplication constants needed to arrive there 
//
// usage:    newfrold.cc el1 el2 ... el modulus
//
// history:
//   97/01/10    First version
//

// ------------------------------------------------------------
// METHOD USED
// ------------------------------------------------------------

/* In principle we simply multiply every CDS with successive
constants z, such that z has no common divisor with the modulus
and check whether this yields a new CDS. If this is the case, we
add it to a list of stored CDSs.

There are some finer points :

- For each shift we only store a single CDS. We choose to store that CDS
for which the second element is minimal.

- All CDSs found are stored in an unordered array in which we
  use a linear search. [ Ordered array or even binary tree
  would be more efficient, but is this really worth the trouble ? ]

- CDSs are given a sequence number as they are generated. This sequence
number is used to keep track of which multiplier generates which set.

- Multiplying a CDS with a constant yields an unsorted list which we
sort using selection sort. [ Quicksort or Heapsort would be better, but
again, is this really worth the trouble ? ]

*/

#include <stdlib.h>
#include <iostream.h>
#include <iomanip.h>

// ------------------------------------------------------------
// USAGE
// ------------------------------------------------------------

void usage (char *progname)
{
  cerr << "usage: " << progname << " el1 el2 ... el\n";
  exit (1);
}

// ------------------------------------------------------------
// GLOBAL VARIABLES
// ------------------------------------------------------------

int size;         // must be global to use qsort
int modulus;

// ------------------------------------------------------------
// NORMALIZE
// ------------------------------------------------------------
// Shift CDS such that its second element is as small as possible

int *normalize (int *cds)
{
  // find position of minimal difference
  int minpos = size-1;
  int min    = modulus-cds[minpos];

  for (int i=0; i < size-1; i++) {
    int diff = cds[i+1] - cds[i];
    if (diff < min) { 
      min = diff; minpos = i;
    }
  }
  
  // reorder elements
  int *res = new int [size];
  int j=0; 
  int shift= cds[minpos];
  for (int i=minpos; i < size; i++)
    res[j++] = cds[i]-shift;
  for (int i=0; i < minpos; i++)
    res[j++] = cds[i]+modulus-shift;
  
  return res;
}

// ------------------------------------------------------------
// MULTIPLY
// ------------------------------------------------------------

void sort (int *cds)
  // Lousy, should be improved
{
  for (int i=2; i < size; i++) {
    int tmp = cds[i];
    int j; 
    for (j=1; j < i && cds[j] <= tmp; j++);
    for (int k=i-1; k>=j; k--)
      cds[k+1]=cds[k];
    cds[j]=tmp;
  }
}
 
int *multiply (int *cds, int z)
  // multiplies cds by z  (using modular arithmetic)
{ 
  int *res = new int[size];
  res[0] = 0;
  for (int i=1; i < size; i++)
    res[i] = (cds[i] * z) % modulus;
  sort (res);
  return res;
}

// ------------------------------------------------------------
// CMPCDS
// ------------------------------------------------------------

int samecds (int *cds1, int *cds2)
  // checks equality of CDSs
{ 
  int i;
  for (i=1; i < size && cds1[i]==cds2[i]; i++);

  return i == size;
}

// ------------------------------------------------------------
// ADDCDS
// ------------------------------------------------------------
// Multiplies cds by given constant and adds it to the list
// of all CDSs generated. Returns sequence number

int ** cdslist;      // list of all CDSs generated
int nrcdss;          // current number of cdsss

int addcds (int *cds, int z)
{
  // create product
  int *cds1 = multiply (cds, z);
  int *cds2 = normalize (cds1);
  delete [] cds1;
  
  // look for it
  int i;
  for (i=0; i < nrcdss && !samecds (cds2,cdslist[i]); i++);
  if (i < nrcdss) 
    delete [] cds2;
  else 
    cdslist[nrcdss++] = cds2;
  return i;
}

// ------------------------------------------------------------
// INITMLIST
// ------------------------------------------------------------
// Initializes mlist. Stores -1 in all positions that have a common
// divisor with modulus. 0 otherwise

int *mlist;           // list of multipliers

void initmlist (void)
{
  mlist = new int [modulus];
  for (int i=0; i < modulus; i++)
    mlist[i] = 0;
  for (int i=2; i < modulus; i++) 
    if (mlist[i] ==0 && modulus % i == 0) // all divisors not yet marked
      for (int j=i; j < modulus; j+= i)   // mark multiples of divisor
	mlist[j] = -1;
}

// ------------------------------------------------------------
// GENLIST
// ------------------------------------------------------------
// Main routine. Generates all CDSs

void genlist (int *cds)
{
  cdslist = new (int *)[modulus]; // very conservative !
  nrcdss = 0;
  initmlist ();
  for (int z=1; z < modulus; z++) 
    if (mlist[z]==0) {            // only if no common divisor 
      int ix = addcds (cds, z);
      mlist [z] = ix;
    }
}

// ------------------------------------------------------------
// PRSHIFTS
// ------------------------------------------------------------
// Print all shifts of a given cds

void prshifts (int *cds)
{
  for (int i=0; i < size; i++) {
    // shift is printed in numerical order
    for (int j=i; j < size; j++)  {
      int diff = (cds[j] % modulus) - (cds[i] % modulus);
      if (diff < 0) diff += modulus;
      cout << setw (4) << diff;
    }
    for (int j=0; j < i; j++)  {
      int diff = (cds[j] % modulus) - (cds[i] % modulus);
      if (diff < 0) diff += modulus;
      cout << setw (4) << diff;
    }
    cout << endl;
  }
}

// ------------------------------------------------------------
// PRLIST
// ------------------------------------------------------------
// Print resulting list

void prlist (void)
{
  for (int i=0; i < nrcdss; i++) {
    cout << "Shift nr. " << i+1 << endl;
    cout << "  Multipliers:";
    // print multipliers [ inefficient algorithm, can you do better ? ]
    for (int k=1; k < modulus; k++) 
      if (mlist[k] == i) cout << ' ' << k;
    cout << endl;
    // print shifts
    prshifts (cdslist[i]);
    cout << endl;
  }
}

// ------------------------------------------------------------
// MAIN
// ------------------------------------------------------------

int main (int argc, char **argv)
{
  // check usage
  if (argc < 3) usage (argv[0]);
  argc--; argv++;

  // parse arguments
  modulus = atoi (argv[argc-1]);
  argc--; 
  size = argc;

  int *diffset = new int [size];
  for (int i=0; i < size; i++)
    diffset[i] = atoi (argv[i]);

  // do it
  genlist (diffset);
  prlist ();

  // cleanup
  delete [] diffset;
  return 0;
}