// Written by Ari Trachtenberg 12/1998.
/* This is a heavily optimized version of Ari's tiling.C. */

/* Looks for a full-rank tiling in 8 dimensions.  Specifically, we need
	 two sets V and A in F_2^8 with the following properties:

	 1.  each set contains the zero vector 0^8
	 2.  each set has 16 vectors
	 3.  each set has full rank (i.e. it's linear combinations generate the entire vector space)
	 4.  the sets V+V intersect A+A = {0} (i.e. V+V = {x | x = v_1 + v_2, v_1,v_2 in V})

	 */

/* COMMENTING STYLE:
	 1)  #endif is usually followed by a comment explaining which #ifdef it is closing
	 2)  procedures/functions are commented as follows:
	     %R:  items in this line are REQUIRED to be true before the procedure is called
			 %M:  items in this line are MODIFIED by the procedure
			 %E:  items in this line are the EFFECTS of the procedure
			 */

/* COMPILER DIRECTIVES:
**
** Normal compilation includes: -DKEEP_INFORMED -DNAUTY -DTRAP_SIGNALS
**
** ...debugging flags
** DOUBLE_CHECK            Double check many computations using alternative means
** DEBUG_ISOMORPHIC        Includes code to debug graph isomorphism routines
** DEBUG_RECURSE_TILINGS   Includes debugging code for the recurse_tilings procedure
** DEBUG_FILL_REST         Includes debugging code for the fill_rest procedure (obsolete)
** DEBUG_INSERT            Debug the "insert" procedure
** PROFILE                 Include code to stop program after a certain point for profiling reasons
** KEEP_INFORMED           Includes extra info to keep the user informed
** TEST_BASES              Includes code to test (and debug) the basis construction in array A
** FORK                    Includes for forking 16 processes to look for the tiling
** 
** ...operational flags
** NAUTY                   Includes code to use the nauty procedure to check for isomorphisms
** SEED                    Seeds the A vector search with values from the SEEDS array
** TRAP_SIGNALS            Outputs important memory to stdout upon a signal (e.g. interrupt)
*/

/* VARIOUS CONSTANTS:
** #define NAUTY_MAX 7     // maximum size of bases on which to use the NAUTY subroutine
** #define STAT_INDEX 5    // the index of ISOMORPH_MEM used to estimate remaining search time
** #ifdef SEED
** const int SEEDS[]={0,248,247,11,23,45,94,98,163}
** // the initial seed basis of A from which to start
** // the search; note that the first seed vector must
** // be zero, and that the subsequent vectors must
** // correspond to a basis that the program will
** // see sometime in its execution
** #endif
*/

#include <iostream.h>
#include <iomanip.h>
#include <stdio.h>
#include <time.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
#include <unistd.h>
#include <signal.h>
#include "constants.h"
#include "bits.h"
#include "matrix.h"
#include "permute.h"

// defined constants
#ifdef FORK
FILE *fp;              // for the kill file
static int fork_id=-1; // uniquely identifies each fork, starting with 0
long tot_bases;        // a variable whose contents are set in setup(*)
#endif // FORK

// global variables
short HTMLIFY;         // if I want to make this outputable to an HTML document at some later stage
int A[16],V[16];       // the A and V sets, respectively

#ifdef SEED
int seed_index=0;      // the SEEDS[] array is used to seed the search of bases "A"; this is the index of SEEDS that has already been seeded into A
int init_bases=0;      // used for SEED computation to insure correct statistics
int init_isos=0;       // used to insure correct statistics to report to the user
#endif // SEED

int subspace[256];     /* stores temporarily the current subspace being considered;
											 ** each entry is blank if the vector is not in the subspace, and
											 ** otherwise contains the index (of the iteration) at which the the vector
											 ** was introduced into the subspace
											 */

int equal_cols[9];     /* keeps track of equal columns so as to remove isomorphisms;
											 **	the i'th entry of this array is an integer whose $1$ locations
											 ** correspond to equal columns (least significant bit is first)
											 **
											 ** in a sense, each entry is a partition of the columns
											 ** this array is terminated by the constant UNDEFINED
											 */

int APA[256], VPV[256];/* APA is the set A+A (in other words {a+a' | a,a' in A}.  Similarly
											 ** VPV is the set V+V.  The i'th entry of the array is FALSE if i is not
											 ** in the set and TRUE otherwise
											 */

#ifdef MAINTAIN_SIZE
int APA_size, VPV_size; /* number of non-zero entries in the APA and VPV arrays respectively */
#endif // MAINTAIN_SIZE

#ifdef NAUTY
graph **isomorphics[9];// isomorphics[ii] contains non-isomorphic bases found so far of size ii (including the all-zero vector)
int iso_sizes[9];      // iso_sizes[ii] contains the current size of isomorphics[ii]

#ifdef DOUBLE_CHECK
matrix *isomorph_mat[9]; // same data as isomorphics, but in matrix form for use with double-checking
#endif // DOUBLE_CHECK

// ... global nauty-related variables
nvector *lab,*ptn,*orbits;
static DEFAULTOPTIONS(options);
setword workspace[50];
statsblk(stats);
#endif // NAUTY

int no_list[16][2]={{224,31},{224,159},{224,223},{224,255},{224,28},{224,156},{224,220},{224,252},
										{248,135},{248,199},{248,231},{248,247},{248,255},{248,228},
										{254,225},{254,249}};
/* * initially seed with the first sixteen possible choices
**   for A[1] and A[2].  This contains the
** * list of basis vectors that we risk counting twice in our basis search;
**	  once under the current set A[1] and A[2] and once when they appear
**	  as the first and second bases in A
** * only entries [0] through [14] are actually used, the last one is a
**   place-holder
*/

double skipped_choices;// counts the number of choices skipped (roughly)
long bases;            // counts the number of bases seen so far
int vects_seen;        // keeps track of the maximum number vectors we have been able to fit into
                       // (V,A) so far

// ... for time-keeping
time_t start_time;     // when we started the program
time_t last_update;    // the last time we updated the user


// AUXILIARY AND INLINED FUNCTIONS
inline short int  weightge3(int val) {
	// %E:  returns TRUE iff val has at least three 1's in its binary representation (else FALSE)
	short int num_ones=0;

	if ((val & 1) != 0)
		num_ones++;
	if ((val & 2) != 0)
		num_ones++;
	if ((val & 4) != 0)
		num_ones++;
	if ((val & 8) != 0)
		num_ones++;
	if (num_ones>=3)
		return TRUE;

	if ((val & 16) != 0)
		num_ones++;
	if ((val & 32) != 0)
		num_ones++;
	if (num_ones>=3)
		return TRUE;

	if ((val & 64) != 0)
		num_ones++;
	if ((val & 128) != 0)
		num_ones++;
	if (num_ones>=3)
		return TRUE;
	else
		return FALSE;
}

// ... for debugging
inline void print_array(int the_array[16], char *name) {
	// %E:  prints out the information stored in an array of size 16 whose name is "name"
	int ii,jj;
 
	cout << name << ":" << endl;
	for (ii=0; ii<16; ii++) {
		cout << "   " << setw(2) << ii << ": ";
		if (the_array[ii]==UNDEFINED)
			cout << "---" << endl;
		else {
			bits the_val(the_array[ii]);

			// pretty-printing
			for (jj=0; jj<(7-lg(the_val)); jj++)
				cout << "0";

			the_val.printon(cout,2);
			cout << "  [" << the_array[ii] << "]" << endl;
		}
	}
	cout << endl;
}

#ifdef NAUTY
void print_graph(set the_array[16], char *name) {
  // %E:  prints out the information stored in an array of size 16 whose name is "name"
  int ii,jj;

	cout << name << ":" << endl;
  for (ii=0; ii<16; ii++) {
		cout << "   " << setw(2) << ii << ": ";
    if (the_array[ii]==UNDEFINED)
      cout << "---" << endl;
    else {
      bits the_val(the_array[ii]);

      // pretty-printing
      for (jj=0; jj<(7-lg(the_val)); jj++)
        cout << "0";

      the_val.printon(cout,2);
			cout << "  [" << the_array[ii] << "]" << endl;
    }
  }
  cout << endl;
}
#endif

inline void print_space(int subspace[256],char *name) {
	// %E:  prints out the non-zero values of the 256 integer array whose name will be "name"
	int ii, jj, count;

	count=0;
	cout << name << ":" << endl;
	for (ii=0; ii<256; ii++)
		if (subspace[ii]) {
			bits the_val(ii);
			
			// pretty-printing
			cout << "   " << setw(2) << (count++) << ":  ";
			for (jj=0; jj<(7-lg(the_val)); jj++)
				cout << "0";

			the_val.printon(cout,2);
			cout << "  [" << ii << "] introduced at index " << subspace[ii] << endl;
		}
}

void print_time(time_t elapsed) {
	// %E:  pretty prints "elapsed" seconds onto cout
	int days, hours, mins, secs;

	//cout << "Time: " << elapsed << endl;

	days=(int) floor(elapsed/86400);  //86400==24*3600
	elapsed-=days*86400;
	hours=(int) floor(elapsed/3600);
	elapsed-=hours*3600;
	mins=(int) floor(elapsed/60);
	elapsed-=mins*60;
	secs=elapsed;
	
	if (days!=0)
		{ cout << days << " days " << hours << " hrs " << mins << " min " << secs << " secs"; }
	else if (hours!=0)
		{ cout << hours << " hours " << mins << " min " << secs << " secs"; }
	else if (mins!=0)
		{ cout << mins << " minutes " << secs << " secs"; }
	else
		{ cout << secs << " seconds"; }

}

inline void print_entries(int* the_array, char *name) {
	/* %R:  the_array values are assumed to be 8-bit integers
	** %E:  prints out the (reversed) information stored in the array whose name is "name" until
	**      an UNDEFINED value is reached */
	
	int ii,jj;  // looping
 
	cout << name << ":" << endl; // i.e. the name
	for (ii=0; the_array[ii]!=UNDEFINED; ii++) {
		
		cout << "   " << setw(2) << ii << ": ";
		
		// pretty-printing
		for (jj=7; jj>=0; jj--)
			if (the_array[ii]&TWO_POW[jj])
				cout << "1";
			else
				cout << "0";
		
		cout << "  [" << the_array[ii] << "]" << endl;
	}
	cout << endl;
}

inline int verify_V(int index) {
	/* %R:  index<16
	** %M:  VPV
	** %E:  Checks:
	**      * returns FALSE if V[index] is already among V[<index]
	**      * returns FALSE if
	**        adding the requested vector would violated the disjointedness of A+A and V+V
	**      * else returns TRUE
	*/

	// variables
	int ii;       // looping variable

	// optimizations
	int V_index=V[index];                           // for minor optimization

	// add entries to the_array
	for (ii=0; ii<index; ii++)
		// check if V[index] is already in V or vector is in A+A
		if (V[ii]==V_index || APA[ V[ii] ^ V_index ])
			return FALSE;

	return TRUE;                                   // i.e. all checks passed
}

inline int verify_A(int index) {
	/* %R:  index<16
	** %M:  APA
	** %E:  Checks:
	**      * returns FALSE if A[index] is already among A[<index]
	**      * returns FALSE if
	**        adding the requested vector would violated the disjointedness of A+A and V+V
	**      * else returns TRUE
	*/

	// variables
	int ii;       // looping variable

	// optimizations
	int A_index=A[index];                           // for minor optimization

	// add entries to the_array
	for (ii=0; ii<index; ii++)
		// check if A[index] is already in A or vector is in A+A
		if (A[ii]==A_index || VPV[ A[ii] ^ A_index ])
			return FALSE;

	return TRUE;                                   // i.e. all checks passed
}

inline void recompute_VPV() {
	/* %R:  assumes V has 16 elements already
	** %M:  VPV
	** %E:  recomputes VPV array based on V (erases whatever data is already in VPV first)
	 */
	int ii,jj;

	memset(VPV,FALSE,256*sizeof(int));
	for (ii=0; ii<16; ii++)
		for (jj=0; jj<ii; jj++)   // xor is commutative
			VPV[V[ii]^V[jj]]=TRUE;
}

inline void recompute_APA() {
	/* %R:  assumes A has 16 elements already
	** %M:  APA
	** %E:  recomputes APA array based on A (erases whatever data is already in APA first)
	 */
	int ii,jj;

	memset(APA,FALSE,256*sizeof(int));
	for (ii=0; ii<16; ii++)
		for (jj=0; jj<ii; jj++)   // xor is commutative
			APA[A[ii]^A[jj]]=TRUE;
}

// ... for handling signals
void curr_stat(int dummy) {
	// dump all available info
	print_array(A,"Last A seen:");
	print_array(V,"Last V seen:");
	print_space(APA,"Last A+A (not recomputed)");
	recompute_VPV();
	print_space(VPV,"Last V+V");

}

void abrt_terminate(int dummy) { cout << endl << "SIGABRT!!!" << endl; curr_stat(dummy); exit(-1);}
void int_terminate(int dummy) { cout << endl << "SIGINT!!!" << endl; curr_stat(dummy); }
void segv_terminate(int dummy) { cout << endl << "SIGSEGV!!!" << endl; curr_stat(dummy); exit(-1);}
void term_terminate(int dummy) { cout << endl << "SIGTERM!!!" << endl; curr_stat(dummy); exit(-1);}

// ... for double-checking the search process
#ifdef DOUBLE_CHECK

// issues an error if check is different from absolute
#define CONFIRM(check,absolute) if ((check)!=(absolute)) {cout << "Confirmation failed on line " << _##_LINE_##_ << endl; exit(-1);}// else {cout << "Confirmed on line " << _##_LINE_##_ << endl;}

short check_Abasis(int Alast) {
	/* %R:  Alast>0
		 %E:  returns true iff entries A[1..Alast] are linearly independent
		 */
	matrix the_mat=matrix(Alast,8,A+1);
	short response=the_mat.reduce();
	the_mat.destroy();
	return response;
}

short check_intersect(int Alast,int Vlast) {
	/* %R:  Alast>0, Vlast>0
		 %E:  returns true iff the sum of every two entries from A[0..Alast]
		      is different from the sum of every two entries from V[0..Vlast]
					(except A[0]+A[0]=V[0]+V[0]=0) AND there are no repeated entries
					in A (respectively V)
					*/

	int ii,jj;
	int thisAPA[256],thisVPV[256];
	
	// initialize
	for (ii=0; ii<256; ii++)
		thisAPA[ii]=thisVPV[ii]=0;

	// compute thisAPA and thisVPV
	for (ii=0; ii<=Alast; ii++)
		for (jj=ii+1; jj<=Alast; jj++)
			if (A[ii]==A[jj])
				return FALSE;
			else
				thisAPA[ A[ii]^A[jj] ] = 1;
	for (ii=0; ii<=Vlast; ii++)
		for (jj=ii+1; jj<=Vlast; jj++)
			if (V[ii]==V[jj])
				return FALSE;
			else
				thisVPV[ V[ii]^V[jj] ] = 1;

	// check for equality
	for (ii=0; ii<256; ii++)
		if (thisAPA[ii] && thisVPV[ii])
			return FALSE; // found an instance where they are both 1

	return TRUE;
}
#endif // DOUBLE_CHECK

#ifdef NAUTY
inline void insert(graph **new_graph_ptr, graph **the_isomorph, int isomorph_size,int compare(const void *, const void *))
	/* %R:  the_isomorph must contain isomorph_size-1 graphs (graph *'s) that are sorted
	**      by means of the "compare" function
	** %M:  the_isomorph
	** %E:  inserts *new_graph_ptr into the_isomorph while maintaining order (w/r to "compare");
	**      this is a simple insertion into a sorted array using binary search
	*/
{
	long int loc=0;
	
	// find the proper location
	// while (loc<isomorph_size-1 && compare(new_graph_ptr,the_isomorph+loc)==1)
	//  loc++;
	// ... by binary search
	long int beg,end, half_way;
	if (isomorph_size==1 || compare(new_graph_ptr,the_isomorph)==-1)
		loc=0;             // item belongs at the beginning of the list
	else 	if  (compare(new_graph_ptr,the_isomorph+isomorph_size-2)==1)
		loc=isomorph_size-1; // item belongs at the end of the list
	else {               // actually have to search
		beg=0; end=isomorph_size-2;
		while (end-beg>1) {
			half_way=(end+beg)/2;
			if (compare(new_graph_ptr,the_isomorph+half_way)==-1)
				end=half_way;
			else
				beg=half_way;
		}
		loc=end;            // I need to replace the bigger index
	}

	// move the remaining elements
	memmove(the_isomorph+loc+1,the_isomorph+loc,(isomorph_size-loc-1)*sizeof(graph *));

	// add the new graph
	the_isomorph[loc]=*new_graph_ptr;

#ifdef DEBUG_INSERT
	for (loc=0; loc<isomorph_size-1; loc++)
		if (compare(the_isomorph+loc,the_isomorph+loc+1)!=-1)
			ERR("Error:  Insert did not result in a properly sorted list");
#endif

}

// ... nauty-related procedures
inline int nauty_compare(const void *p1, const void *p2, int height)
	/* %R:  assumes p1 and p2 are (graph **)'s, size (p1 or p2) >=height>0
		 %E:  returns 1 if (*p1) is lexicographically later than (*p2),
		      0 if they are equal,
					and -1 if (*p1) is earlier;
					only considers the first "height" vectors in both graphs
					*/
{
  int ii;
	for (ii=0; ii<height; ii++)
    if (((*((graph **)p1))[ii]&BITMASK(0))!=((*((graph **)p2))[ii]&BITMASK(0))) // we will now return something
			if (((*((graph **)p1))[ii]&BITMASK(0)) < ((*((graph **)p2))[ii]&BITMASK(0)))
				return -1;
			else
				return 1;
  return 0;   // they are equal
}

//inlines for the various values of "height"; needed to mask the extra parameter from bsearch()
inline int nauty_compare_16(const void *p1, const void *p2) { return nauty_compare(p1,p2,16);}  
inline int nauty_compare_15(const void *p1, const void *p2) { return nauty_compare(p1,p2,15);}  
inline int nauty_compare_14(const void *p1, const void *p2) { return nauty_compare(p1,p2,14);}
inline int nauty_compare_13(const void *p1, const void *p2) { return nauty_compare(p1,p2,13);}
inline int nauty_compare_12(const void *p1, const void *p2) { return nauty_compare(p1,p2,12);}
inline int nauty_compare_11(const void *p1, const void *p2) { return nauty_compare(p1,p2,11);}
inline int nauty_compare_10(const void *p1, const void *p2) { return nauty_compare(p1,p2,10);}
inline int nauty_compare_9(const void *p1, const void *p2) { return nauty_compare(p1,p2,9);}  
inline int nauty_compare_8(const void *p1, const void *p2) { return nauty_compare(p1,p2,8);}
inline int nauty_compare_7(const void *p1, const void *p2) { return nauty_compare(p1,p2,7);}
inline int nauty_compare_6(const void *p1, const void *p2) { return nauty_compare(p1,p2,6);}
inline int nauty_compare_5(const void *p1, const void *p2) { return nauty_compare(p1,p2,5);}
inline int nauty_compare_4(const void *p1, const void *p2) { return nauty_compare(p1,p2,4);}
inline int nauty_compare_3(const void *p1, const void *p2) { return nauty_compare(p1,p2,3);}
inline int nauty_compare_2(const void *p1, const void *p2) { return nauty_compare(p1,p2,2);}
inline int nauty_compare_1(const void *p1, const void *p2) { return nauty_compare(p1,p2,1);}
#endif

// ACTUAL SEARCH PROCEDURES

void fill_rest_A(int last_val, int Aind) {
  /* %R:  * array A already has its first 9 vectors entered, which are full rank
	**      * array V already has all of its vectors entered, which are full rank
	**      * APA and VPV are appropriately maintained with respect to A and V
	** %M:  A
	** %E:  attempts to fill in A without violating tiling properties
	*/
  // variables
  int ii;            // for looping

#ifdef KEEP_INFORMED
  //keep track of vects_seen ... for my informational purposes only for now
  if (vects_seen<Aind+16) {
    vects_seen=Aind+16;
    cout << "Saw " << vects_seen << " vectors" << endl;
    print_array(V,"V");
    print_array(A,"A");

		#ifdef DEBUG_FILL_REST
		// check V and A for consistency
		int Atest[256];
		int jj;
		for (ii=0; ii<256; ii++)
			Atest[ii]=0;
		for (ii=0; ii<Aind; ii++)
			for (jj=0; jj<Aind; jj++)
				Atest[ A[ii]^A[jj] ] = ii*100+jj;
		for (ii=0; ii<16; ii++)
			for (jj=1; jj<ii; jj++)
				if (Atest[ V[ii] ^ V[jj] ]) {
					cout << "Atest[ " << (V[ii] ^ V[jj]) << "] = " << (Atest[ V[ii] ^ V[jj] ]) << endl;
					cout << "ii=" << ii << "; jj=" << jj << endl;
					ERR("Failed disjointedness test!");
				}
		cout << "Passed DEBUGGing test!" << endl;
		#endif
  }
#endif

  if (Aind==15) // i.e. filled in everything but the last vector of A
    {
			// compute A[15] as the sum of the other vectors by property 3
			A[15]=0; // A[0] should be 0
			for (ii=1; ii<15; ii++)
				A[15]^=A[ii];
			
			/* we can always insist that the last row be the largest,
				 and other cases will be isomorphic to it */
			if (A[15]<last_val) { // this is the isomorphic case
				A[15]=UNDEFINED;
				return;
			}	
			
			if (verify_A(15)) {
				cout << "---------------------" << endl;
				cout << "---------------------" << endl;
				cout << "---------------------" << endl;
				cout << "Victory...I think :-)" << endl;
				print_array(V,"V");
				print_array(A,"A");
				recompute_APA();
				print_space(APA,"A+A");
				recompute_VPV();
				print_space(VPV,"V+V");
				cout << "---------------------" << endl;
				cout << "---------------------" << endl;
				cout << "---------------------" << endl;
				exit(-1);
			}
			
#ifdef DOUBLE_CHECK
			CONFIRM(check_intersect(15,15),FALSE);
#endif // DOUBLE_CHECK

			A[15]=UNDEFINED;             // old A[15] value
			return;                      // go back to the previous recursion level
		}

	int max_check;
	max_check = 242+Aind;        // i.e. 256-(14-Aind)

	for (ii=last_val; ii<max_check; ii++) {
		// ... CAN ii fit into array A?
		A[Aind]=ii;   // try adding ii to A and see if any properties are violated
		
		if (verify_A(Aind))            // verify properties
			fill_rest_A(ii+1,Aind+1);    // verification passed...recurse
#ifdef DOUBLE_CHECK
		else
			CONFIRM(check_intersect(Aind,15),FALSE);
#endif // DOUBLE_CHECK
		// return to previous state
		A[Aind]=UNDEFINED;
	}

#ifdef MAINTAIN_SIZE
	cout << "V+V size: " << VPV_size << "; A+A size: " << APA_size << " (Aind="
			 << Aind << "); combined: " << (VPV_size+APA_size) << endl;
#endif
}

void fill_rest_V(int last_val, int Vind) {
	/* %R:  * arrays A and V already have their first 9 vectors entered which are full rank
	**      * APA and VPV are appropriately maintained with respect to A and V
	** %E:  attempts to fill in V without violating tiling properties
	 */
	int ii;            // for looping
	if (Vind==15) {    // all undetermined vectors for V have been added
    // compute V[15] as the sum of the other vectors by assumption 3
    V[15]=0; // V[0] should be 0
    for (ii=1; ii<15; ii++)
      V[15]^=V[ii];

		/* we can always insist that the last row be the largest,
			 and other cases will be isomorphic to it */
		if (V[15]<last_val) {
			V[15]=UNDEFINED;
			return;
		}

		if (verify_V(15)) {                // try to add to VPV
#ifdef MAINTAIN_SIZE
			// compute VPV_size
			VPV_size=0;
			for (ii=0; ii<256; ii++)
				if (VPV[ii])
					VPV_size++;
#endif

			// recompute VPV
			recompute_VPV();

			fill_rest_A(7,9);                 // i.e. try filling in the remainder of A next
		}
#ifdef DOUBLE_CHECK
		else
			CONFIRM(check_intersect(9,15),FALSE);
#endif // DOUBLE_CHECK

    V[15]=UNDEFINED;                    // old V[15] value
    return;                             // go back to the previous recursion level
  }

	// otherwise go through possible values of V
	int max_check;
	max_check = 241+Vind;    // i.e. 256-(15-Vind) {all vectors must be in order}

	for (ii=last_val; ii<max_check; ii++) {
		// ... CAN ii go into V?
		V[Vind]=ii;   // try adding ii to V and see if any properties are violated
		
		if (verify_V(Vind))
			fill_rest_V(ii+1,Vind+1); // added one entry to V
#ifdef DOUBLE_CHECK
		else
			CONFIRM(check_intersect(9,Vind),FALSE);
#endif // DOUBLE_CHECK		
		// return to previous state
		V[Vind]=UNDEFINED;
	}
}

void recurse_tilings(int index, int last_val) {
	/* %R:  * index is the first index of A into which we will be inserting an element
	**      * last_val is the smallest possible value for the next element to be inserted
	** %M:  A
	** %E:  * recursively look for full-rank, dimension 8 tilings;
	**      * this procedure recursively generates all non-isomorphic, minimum distance $3$
	**      bases of $F_2^8$, putting them in A[1]...A[9].
	**      For each basis that is picked, the procedure
	**      calls auxiliary procedure fill_rest_V() to fill in the remaining elements of $V$
	**      and then $A$
	*/

	// constants known at compile time
#define LARGEST_POSS 255        // the largest 8-bit vector (in counting order) of weight >=3
	
	// other variables
	int ii, jj, count;            // for looping
	int temp_cols[9];             // temporary array for storing equal_cols entries
	// for nauty
#ifdef NAUTY
	graph **canon_ptr;            // the canonical graph for the sub-basis considered so far
#ifdef DOUBLE_CHECK
	graph **canon_ptr2;           // for double-checking work
#endif
	graph **found_graph;
	matrix my_mat;
	graph *A_graph;
#endif
	
#ifdef DEBUG_RECURSE_TILINGS
	int sub_size=0;
	for (ii=0; ii<256; ii++)
		if (subspace[ii]) sub_size++;
	//	print_array(A,"A");
	//	print_space(subspace,"Subspace");
	//  cout << "index is " << index << endl;
	//  cout << "subspace size: " << sub_size << endl;
	if (sub_size!=1 && sub_size!=2 && sub_size!=4 && sub_size!=8 && sub_size!=16 && sub_size!=32 &&
			sub_size!=64 && sub_size!=128 && sub_size!=256) {
		cout << "ERR:  Subspace compromised: error!" << endl;
		exit(-1);
	}
#endif

#ifndef TEST_BASES
#define MAX_INDEX 9  // the normal recursion limit
#else
#define MAX_INDEX 5   // the recursion limit for testing purposes
#endif // TEST_BASES

	if (index==MAX_INDEX) {
		// RECURSION TERMINATING CONDITION: we have a valid set of full_rank vectors
		bases++;
		//print_array(A,"A:");

		// ...update the user?
#ifdef PROFILE
		if (bases>=25) {
			cout << "Found:  " << bases << " bases." << endl;
			cout << "Elapsed time: ";
			print_time(time(NULL)-start_time);
			cout << endl;
			exit(-1);  // exit and dump profiling data
		}
#else // !PROFILE
		if (time(NULL)-last_update > USER_WAIT) {
			last_update=time(NULL);
			cout << "Current status ";
#ifdef FORK
			cout << "FOR PROCESS #" << fork_id;
#endif // FORK
			cout << " after " << (last_update-start_time) << " seconds: " << endl;
			print_array(A,"A");
			cout << endl;
 
			double frac_comp=0.0;  // fraction of the space completed
			
			// try to compute an approximation for the number of vectors we've gone through
#ifndef NAUTY // use another heuristic
			for (ii=3; ii<index; ii++)
				frac_comp+=(((double) A[ii])/256.0)/pow(256,(ii-3));
#else  // NAUTY
			frac_comp=(((double) iso_sizes[STAT_INDEX])/ISOMORPH_MEM[STAT_INDEX]); // use the latest computed number of bases known
#endif // !NAUTY
			
			//frac_comp/=2; // 2 different choices for the first two bases
			cout << "  approximate fraction complete: " << frac_comp << endl;
			cout << "  Percentage completed: " << setprecision(10) << frac_comp*100 << "%." << endl;

			cout << "  Bases found so far: " << bases << endl;
#ifdef NAUTY
			cout << "  Isomorphics sizes:  ";
			cout << "  ";
			for (ii=0; ii<9; ii++)
				cout << iso_sizes[ii] << " ";
			cout << endl;
      cout << "  Skipped choices: " << skipped_choices << endl;  
#endif // NAUTY

#ifdef KEEP_INFORMED
			cout << "  Largest number of determined vectors at any time: " << vects_seen << endl;
#endif // KEEP_INFORMED
			cout << "  Average milli-seconds/basis: " << setprecision(5);
#ifdef SEED
			cout << ((float) (1000.0)*(last_update-start_time)/(bases-init_bases)) << endl;
#else
			cout << ((float) (1000.0)*(last_update-start_time)/bases) << endl;
#endif
			cout << "  Estimated remaining running time: ";
#ifdef SEED
			double remain_sec;
			if (iso_sizes[STAT_INDEX]==init_isos)
				remain_sec=-1.0;
			else
				remain_sec=floor((last_update-start_time)/(iso_sizes[STAT_INDEX]-init_isos)*(ISOMORPH_MEM[STAT_INDEX]-iso_sizes[STAT_INDEX]));
#else
			double remain_sec=floor((last_update-start_time)*(1.0/frac_comp-1.0));
#endif
			print_time((long) remain_sec); // assume constant rate
			cout << "     [" << remain_sec << " seconds]" << endl << endl;
		}
#endif // !PROFILE

#if defined(SEED)// && !defined(READ_BASES)
		// check if we have reached the seed yet or not
		if (seed_index<9) {           // i.e. we haven't seeded everything yet
			if (A[seed_index]!=SEEDS[seed_index])
				return;                    // i.e. keep going
			else
				while (seed_index<9 && A[seed_index]==SEEDS[seed_index]) { // i.e. keep looking (this might not be necessary)
					cout << "Reached seed index " << seed_index << " (" << SEEDS[seed_index] << ")" << endl;
					seed_index++;              // we have seen one more basis
				}

			if (seed_index==9) {
				cout << "The seed basis has been reached!" << endl;
				cout << "Elapsed time: ";
				print_time(time(NULL)-start_time);
				cout << endl << "Resetting clock and storing current location." << endl;
				start_time=time(NULL);
				cout << "Saw " << bases << " bases and " << iso_sizes[STAT_INDEX]
						 << " relevant iso_sizes." << endl;
				init_bases=bases;
				init_isos=iso_sizes[STAT_INDEX];

				cout << endl << endl;
				cout << "--------------------------------" << endl;
				print_array(A,"A:");
				cout << "--------------------------------" << endl;
				cout << "--------------------------------" << endl << endl;
			}
			return;                       // keep going
		}
#endif // SEED //|| !READ_BASES

#ifndef TEST_BASES
		// ...fill up the rest of the array
		// ......first construct the APA array
#ifdef MAINTAIN_SIZE
		APA_size=0;                    // initial APA size
#endif // MAINTAIN_SIZE
		for (ii=0; ii<9; ii++)
			for (jj=0; jj<9; jj++)
#ifdef MAINTAIN_SIZE
				if (!(APA[A[ii]^A[jj]])) {
					APA_size++;              // found one more new vector
					APA[A[ii]^A[jj]]=TRUE;   // set to 1 all elements of A+A that we have so far
				}
#else  // !MAINTAIN_SIZE
		APA[A[ii]^A[jj]]=TRUE;         // set to 1 all elements of A+A that we have so far
#endif // MAINTAIN_SIZE

#ifdef NAUTY
    fill_rest_V(3,9);              // start filling V array at the number 3 (lower numbers already there
		//cout << "DONE WITH BASIS" << endl;
#endif // NAUTY

		// ......reconstruct the old APA array (i.e. all zeroes)
		for (ii=0; ii<9; ii++)
			for (jj=0; jj<9; jj++)
				APA[A[ii]^A[jj]]=FALSE;    // set to 0 all elements of A+A that were previously set
#endif // TEST_BASES
	} // end of recursion terminating condition


	else { // this is the GENERAL case of the recursion
		
		// go through each possible value of A[index]
		for (A[index]=last_val; A[index]<=LARGEST_POSS;A[index]++) {
#ifdef DOUBLE_CHECK
			if (A[index]==256) exit(-1); // ... this is a major error and should never happen
#endif
			
			// ... is A[index] linearly dependent on the other vectors?
			if (subspace[A[index]]) {
#ifdef DOUBLE_CHECK
				CONFIRM(check_Abasis(index),FALSE);
#endif // DOUBLE_CHECK
				continue;       // the vector is already in the subspace
			}
			
			// ... is A[index] of weight >=3?
			if (!weightge3(A[index])) {
#ifdef DOUBLE_CHECK
				CONFIRM(check_intersect(index,9),FALSE);
#endif // DOUBLE_CHECK
				continue;     // the weight was too small
			}

			   // ... is A[index] of dist >3 from A[<index]?
			for (ii=1; ii<index; ii++)
				if (!weightge3(A[index]^A[ii]))
					break;                              // the weight was too small
			if (ii!=index) {
#ifdef DOUBLE_CHECK
				CONFIRM(check_intersect(index,9),FALSE);
#endif // DOUBLE_CHECK
				continue;                // the previous loop had been broken; weight too small
			}
		
			// is A[1..index] heuristically isomorphic to a previously seen set of vectors?
			/*   specifically, we insist that any set of equal columns of A correspond to a
			**   lexicographically increasing sequence of bits in A[index]
			*/

			/* implementation note:
			** ... first copy equal_cols into temp_cols; this backup will be reused after the
			**     recursive call to recurse_tilings; it has been placed here because, as a side-effect,
			**     it calculates the size of equal_cols (i.e. a SLIGHT optimization here)
			*/
			for (count=0; equal_cols[count]!=UNDEFINED; count++)
				temp_cols[count]=equal_cols[count];
			temp_cols[count]=UNDEFINED;             // terminate temp_cols
			// ... back to checking for heuristic isomorphism
			if (count!=8) { /* if count==8 then equal_cols is the identity matrix; no isomorphism info.
											** can be gleaned (as far as I know
											*/
				short fail=FALSE;                     // set to TRUE if A[index] has failed this test
				for (ii=0; ii<count && !fail; ii++) { // i.e. for each equal_cols entry
					short ones=TRUE;                    // start off looking for 1's until we see our first 0
					for (jj=0; jj<8; jj++) {            /* go through each bit, making sure all 1's in equal
																							** cols come before all 0's (prevents isomorphic cases)
																							*/
						if (equal_cols[ii]&TWO_POW[jj])
							if (ones) {
								if (!(A[index]&TWO_POW[jj]))    // i.e. the bit in A[index] is a 0
									ones=FALSE;                 // go into 0-hunt mode
							}
							else                            // we were in zeroes mode
								if (A[index]&TWO_POW[jj]) {   // saw a 1 in 0-hunt mode...discard the choice
									fail=TRUE;
									break; }
					}
				}
				if (fail)
					continue;                           // the isomorphism test failed
			}
				
#ifdef DEBUG_RECURSE_TILINGS
			int copy_test[256];
			for (ii=0; ii<256; ii++)
				copy_test[ii]=subspace[ii];
#endif

			// are two vectors in A are on the no_list?
			// ...(if so, they are isomorphic to a different case we did/will see)
			int found[15]; memset(found,0,15*sizeof(int)); // initialize found to 0's
			for (ii=1; ii<=index; ii++)
				for (jj=0; jj<15; jj++)
					if (A[ii]==no_list[jj][0] || A[ii]==no_list[jj][1])
						found[jj]++;                               // found an element of the no-list
			short fail=FALSE;                              // set to TRUE if A[index] has failed this test
			for (ii=0; ii<15; ii++)
				if (found[ii]==2) {                          // found two vectors from another set
					if ((no_list[ii][0]*256+no_list[ii][1])<(A[1]*256+A[2])) {
						fail=TRUE;                               //  only accept one vector in a set
						break;
					}
				}
			if (fail) {
				// print_array(A,"Test failed on A=");
				continue;
			}

#ifdef NAUTY
			// is A[1...index] isomorphic to a previous case we have seen?
			//  this is the complete isomophism check, done by the "nauty" procedure
			if (index<=NAUTY_MAX) {         // then use NAUTY to further limit choices
				canon_ptr=new (graph *)[1];   // i.e. one graph
				(*canon_ptr) = new graph[17]; // over-estimate should be ok
				my_mat=matrix(index,8,A+1);
				A_graph=my_mat.make_nauty_graph(&lab,&ptn,index); // make a graph out of the first index rows (not including the zero vector)
				
				// determine the canonical graph of A_graph
				nauty(A_graph,lab,ptn,NILGRAPH,orbits,&options,&stats,workspace,50,1,8+index,*canon_ptr);
				//print_array(*canon_ptr,"*canon_ptr");
				// clean up
#ifndef DOUBLE_CHECK // if it is defined, then we will make use of my_mat later
				my_mat.destroy();
#endif
				delete[] A_graph;
			
				int (*nauty_compare_index)(const void *p1, const void *p2);

				switch(index) {
				case 8: nauty_compare_index=&nauty_compare_16; break;
				case 7: nauty_compare_index=&nauty_compare_15; break;
				case 6: nauty_compare_index=&nauty_compare_14; break;
				case 5: nauty_compare_index=&nauty_compare_13; break;
				case 4: nauty_compare_index=&nauty_compare_12; break;
				default: nauty_compare_index=&nauty_compare_11; break;
				}
		
				// search to see if canonical graph of A_graph is already in the isomorphism list
				found_graph=(graph **)bsearch(canon_ptr,isomorphics[index],iso_sizes[index],sizeof(graph *),nauty_compare_index);

				if (iso_sizes[index]==ISOMORPH_MEM[index]) // memory exhausted:  don't save the graph
					{delete[] (*canon_ptr); delete[] canon_ptr;}
				else if (found_graph==NULL) {   // insert into the isomorphism list at the right spot
					if (iso_sizes[index]==ISOMORPH_MEM[index]-1) { // announce that we ran out of memory
						cout << "Ran out of isomorphics memory at index " << index << "." << endl;
						cout << "No more entries being added at this index." << endl;
					}
					
					iso_sizes[index]++;
					// quickly insert our new canonical graph in sorted order
					insert(canon_ptr, isomorphics[index],iso_sizes[index],nauty_compare_index);
#ifdef DOUBLE_CHECK
					isomorph_mat[index][iso_sizes[index]-1]=my_mat;
#endif

					delete[] canon_ptr;
				}
				else { // graph was found in the list, or isomorph memory has been exhausted
					// already saw this basis; clean up and return
#ifdef DOUBLE_CHECK
					// look for an isomorphic matrix in the list
					short found=FALSE;
					int row_perm[15];
					for (ii=0; ii<iso_sizes[index]; ii++)
						if (my_mat.isomorphicq(isomorph_mat[index]+ii,row_perm)) {
							found=TRUE;
							break;       // ok...found it
						}
					if (!found) {
						cout << "Confirmation failed on line " << __LINE__ << "!" << endl;
						// search for the exception

						canon_ptr2=new (graph*)[1];
						(*canon_ptr2) = new graph[17];
						for (ii=0; ii<17; ii++)
							(*canon_ptr2)[ii]=0;
						
						for (ii=0; ii<iso_sizes[index]; ii++) {
							A_graph=isomorph_mat[index][ii].make_nauty_graph(&lab,&ptn,index);
							nauty(A_graph,lab,ptn,NILGRAPH,orbits,&options,&stats,workspace,50,1,8+index,*canon_ptr2);
							if (nauty_compare_index(canon_ptr,canon_ptr2)==0) {
								cout << "Nauty found isomorphism with isomorph_mat[index][" << ii << "]" << endl;
								exit(-1);
							}
						}
						cout << "No nauty isomorphism found???" << endl;
						exit(-1);
					}
					CONFIRM(found,TRUE); // just for outputting purposes
					my_mat.destroy();
#endif // DOUBLE_CHECK
					delete[] (*canon_ptr); delete[] canon_ptr;
					skipped_choices+=pow(256,9-index);

					continue;        // we've already seen this basis
				}
			}
#endif // NAUTY
			
			// all tests were passed!!!; update the subspace
			for (ii=0; ii<256; ii++)
				// add ii to the subspace, keeping track of which iteration added it
				if (subspace[ii] && !subspace[ii^A[index]])
					subspace[ii^A[index]]=index;
			
			if (count!=8) { // if equal_cols is an identity matrix, don't bother trying to split it
				// ... now "count" contains the number of entries in equal_cols; update equal_cols,
				//     forming new entries as necessary
				int curr_ind=count-1;                   // the current index at which we insert equal_col info
				for (ii=0; ii<count; ii++) {
					int first=TRUE;                       // true until the first time we split the ii'th entry
					int second=FALSE;                     // true after first time we split up to second time
					int compare_to=-1;                    /* compare all bits to this one, which is determined
																								** the first time we see a bit of equal_cols[ii]
																								*/

					for (jj=0; jj<8; jj++)
						if ((equal_cols[ii]&TWO_POW[jj]) &&               // used to be equal
								(MAKE_BIT(A[index]&TWO_POW[jj])!=compare_to)) // but is not any more
							if (first) {                                    // need to clear up a new index
								first=FALSE;
								second=TRUE;
								compare_to=MAKE_BIT(A[index]&TWO_POW[jj]);    // this is the bit to which to compare
							}
							else { 
								if (second) {                                 // we now introduce a new index
									second=FALSE;                               // we are no longer second
									equal_cols[++curr_ind]=0;                   // increment index and make new entry 0
								}
								equal_cols[curr_ind]|=TWO_POW[jj];            // add on to current knowledge
								equal_cols[ii]^=TWO_POW[jj];                  // take it out of the old array
							}
				}

				equal_cols[++curr_ind]=UNDEFINED;
			
#ifdef DEBUG_RECURSE_TILINGS
				// check for overflow
				if (curr_ind > 8) {
					cout << "ERR:  Current index = " << curr_ind << " > 8 for equal_col computation, "
							 << "which shouldn't happen!" << endl;
					exit(-1);
				}
			
				// check correctness of equal_cols
				// convert each column into an integer
				int cols[8];
				for (ii=0; ii<8; ii++) {
					cols[ii]=0;
					for (jj=0; jj<=index; jj++)
						if (A[jj]&TWO_POW[ii])
							cols[ii]|=TWO_POW[jj];
				}
			
				// check the equal_cols values
				for (ii=0; equal_cols[ii]!=UNDEFINED; ii++) {
					int first_col=FALSE;
					for (jj=0; jj<8; jj++)
						if (equal_cols[ii]&TWO_POW[jj]) {
							if (!first_col) 
								first_col=cols[jj];
							else
								if (cols[jj]!=first_col) {
									cout << "ERR:  equal_cols values not correct!:::" << endl;
									cout << "      cols[" << jj << "] != " << first_col << endl;
									print_array(A,"A");
									print_entries(equal_cols,"equal_cols");
									exit(-1);
								}
						}
						else // make sure the two columns are indeed different
							if (first_col && (cols[jj]==first_col)) {
								cout << "ERR:  equal_cols values are wrong!:::" << endl;
								cout << "      cols[" << jj << "] == " << first_col << " in iteration " << ii << "." << endl;
								print_array(A,"A");
								print_entries(equal_cols,"equal_cols");
								print_entries(temp_cols,"temp_cols");
								exit(-1);
							}
				}
#endif
			}

			// THE MAIN RECURSIVE CALL
			// go on to the next tiling; only try values > A[index]+1 after this point
			recurse_tilings(index+1, A[index]+1);

			if (count!=8) // if count was 8, then we really didn't change anything
				// reset equal_cols from temp_cols;
				for (ii=0; ii<=count; ii++)
					equal_cols[ii]=temp_cols[ii];
			
			/* return the subspace to what it used to be;
				 all contributions from A[ii] must have been unique or else we had a linear dependency */
			for (ii=0; ii<256; ii++)
				if (subspace[ii]==index)   // i.e. was it introduced at the last level?
					subspace[ii]=0; // i.e. reset to 0

#ifdef DEBUG_RECURSE_TILINGS
			for (ii=0; ii<256; ii++)
				if (copy_test[ii]!=subspace[ii]) {
					cout << "Major error at " << ii << endl;
					cout << "copy_test: " << copy_test[ii] << " vs subspace: " << subspace[ii] << endl;
					print_array(A,"A");
					print_space(subspace,"Subspace");
					exit(-1);
				}
			// cout << "integrity test passed!" << endl;
#endif			
		}
	}
}

void setup(int first, int second) {
	/* %M:  A
	** %E:  sets up A with first vector "first" and second vector "second" and recurses to
	**      attempt to find tilings
	*/
	
	// variables
	int ii, jj;               // for looping
	static int next_proc=0;   // when I should fork for the next process
	static int num_proc=0;    // how many processes we have so far

	// constants known at compile time
#define SMALLEST_POSS 7     // the smallest 8-bit vector (in counting order) of weight >=3

#ifdef FORK
	const long NUM_BASES[16]= {1798666,1928586,2204627,1647596,15944537,17993024,20881918,15543236,
														 5646385,6724950,10267097,12329605,4543995,41874798,8413365,15124583};

	fork_id++;                // increment for each call
	pid_t child_address;
	if (fork_id==next_proc) { // time to fork
		// resetart time counters
		start_time=time(NULL);
		last_update=start_time-USER_WAIT; // for initial display of information

		// figure out when next to fork
		if (++num_proc==FORK_PROC)// i.e. we have only one process left
			next_proc=17;           // keep going until the end
		else
			next_proc+=16/FORK_PROC;

		if (child_address=fork()) // i.e. I am the parent
			{
				fprintf(fp,"kill %d\n",child_address); // kills the child proc when the kill file is processed
				sleep(USER_WAIT/(FORK_PROC+5));        // stagger the processes
				return;                   // ... and go on to the next setup
			}
		tot_bases=NUM_BASES[fork_id]; // record the number of bases left
	}
	else
		return;                       // let the child deal with it
#endif
	
	// set A and subspace entries
	A[1]=first; A[2]=second;
	subspace[A[1]]=1; subspace[A[2]]=2; subspace[A[1]^A[2]]=2;  // i.e. make in the subspace
	// set up the no_list
	for (ii=0; ii<15; ii++)
		if (A[1]==no_list[ii][0] && A[2]==no_list[ii][1]) {       // found the item...make it unchecked
			int temp[1][2];             // for swapping no_list[ii] and no_list[15]
			temp[0][0]=no_list[15][0]; temp[0][1]=no_list[15][1];
			no_list[15][0]=no_list[ii][0]; no_list[15][1]=no_list[ii][1];
			no_list[ii][0]=temp[0][0]; no_list[ii][1]=temp[0][1];
		}

	// ... set equal_cols entries
	equal_cols[0]=equal_cols[1]=equal_cols[2]=equal_cols[3]=0;  // i.e. initialize to 0

	//     there are four possible columns now:  00, 01, 10, and 11; each will get an entry
	for (ii=0; ii<8; ii++) { // find all like columns
		int curr_top=MAKE_BIT(A[1]&TWO_POW[ii]);
		int curr_bot=MAKE_BIT(A[2]&TWO_POW[ii]);
		if (curr_top==0 && curr_bot==0)
			equal_cols[0]|=TWO_POW[ii];
		else if (curr_top==0 && curr_bot==1)
			equal_cols[1]|=TWO_POW[ii];
		else if (curr_top==1 && curr_bot==0)
			equal_cols[2]|=TWO_POW[ii];
		else if (curr_top==1 && curr_bot==1)
			equal_cols[3]|=TWO_POW[ii];
	}
	//      get rid of redundant entries
	int max=4; // the maximum number of equal_col entries we can have
	for (ii=0; ii<max; ii++)
		if (!equal_cols[ii]) { // then move other entries up
			for (jj=ii+1; jj<4; jj++)
				equal_cols[jj-1]=equal_cols[jj];
			ii--;                // reindex ii properly
			max--;
		}
	equal_cols[ii]=UNDEFINED;// terminate

	// START UP THE RECURSION
	recurse_tilings(3,SMALLEST_POSS);   // the starting index is 3 because vectors 1 and 2 are in V
	
	// reset A and subspace entries
	subspace[A[1]]=0; subspace[A[2]]=0; subspace[A[1]^A[2]]=0;  // i.e. make not in the subspace
	A[1]=UNDEFINED; A[2]=UNDEFINED;

	// give user feedback
	cout << "*******************************************" << endl;
	cout << "*******************************************" << endl;
	cout << "*******************************************" << endl;
	cout << "Finished with A[0]=" << first << ",A[1]=" << second << "." << endl;
	cout << "Found " << bases << " bases." << endl;
#ifdef NAUTY
	cout << "Isomorphics sizes" << endl;
	for (ii=0; ii<9; ii++)
		cout << iso_sizes[ii] << " ";
	cout << endl;
#endif    
	cout << "*******************************************" << endl;
	cout << "*******************************************" << endl;
	cout << "*******************************************" << endl;

#ifdef FORK
	if (fork_id+1==next_proc) { // the next iteration would be the last
		cout << "Forked process completed.  Goodbye." << endl;
		_exit(1);
	}
#endif
}

// the function for looking for the tilings
void find_tilings() {
	// %E:  an exhaustive search for the tilings --- this starts off the whole recursion

	// variables
	int ii;                // for looping
	tm *loc_tim;           // the local time at the start of the procedure

	// initialization
	start_time=time(NULL);
	last_update=start_time-USER_WAIT; // for initial display of information
	bases=0;
	// ... initialize the subspace
	for (ii=0; ii<256; ii++)
		subspace[ii]=0;      // initially not in the subspace
	subspace[0]=1;         // the 0 vector is always in the subspace initially

	loc_tim=localtime(&start_time);
	cout << "Starting (optimized) tiling search on: ";
	cout << asctime(loc_tim) << endl << endl;
	
#ifdef SEED
	cout << "Searching for the seed basis..." << endl;
#endif

	/* there are 16 cases for the first two vectors of A, as detailed in Prof. Vardy's e-mail
	** we consider each of them in turn
	*/

	// Go through the various possibilities for the first two vectors of A
 	setup(224,31); 
 	setup(224,159);
 	setup(224,223);
	setup(224,255);
	setup(224,28); 
 	setup(224,156);
	setup(224,220);
	setup(224,252);
	
	setup(248,135);
	setup(248,199);
 	setup(248,231);
 	setup(248,247);
	setup(248,255);
	setup(248,228);
	
	setup(254,225);
	setup(254,249);
	
#ifndef FORK
	cout << "Found:  " << bases << " bases." << endl;
	cout << "Elapsed time: ";
	print_time(time(NULL)-start_time);
	cout << endl;
#endif
}

// the main function
int main()
{
	// variables
	int ii;       // for looping
	
#ifdef TRAP_SIGNALS
	// register signal handler
	signal (SIGABRT, abrt_terminate);
	signal (SIGINT,  int_terminate);
	signal (SIGSEGV, segv_terminate);
	signal (SIGTERM, term_terminate);
#endif

	// initialize with values we know to exist
	// ... initialize the VPV array with the known vectors
	for (ii=0; ii<256; ii++)
		if (weightge3(ii))
			VPV[ii]=0; // only bits of weight <3 are in VPV initially
		else
			VPV[ii]=1; // initial index is 1
	// ... initialze the APA array with all FALSE's
	memset(APA,FALSE,256*sizeof(int)); // set APA to all zeroes

	// ... initialize the A and V array
	for (ii=0; ii<256; ii++)
		A[0]=V[0]=0;
	for (ii=1; ii<16; ii++) {
		A[ii]=V[ii]=UNDEFINED; }
	
	// ... initialize the V array with known entries
	V[1]=1;
	for (ii=2; ii<=8; ii++)
		V[ii]=2<<(ii-2);

#ifdef NAUTY
	// ... set up nauty-related variables
	lab = new nvector[17];
	ptn = new nvector[17];
	orbits = new nvector[17];
	for (ii=0; ii<=NAUTY_MAX; ii++) {
		// ... allocate room for isomorphics
		if (!(isomorphics[ii]=new (graph *)[ISOMORPH_MEM[ii]])) {
			cout << "Isomorphics index" << ii << "." << endl;
			ERR("ERR:  Ran out of memory for allocating isomorphics!");
		}
		// ... initialize iso_sizes
		iso_sizes[ii]=0;
	
#ifdef DOUBLE_CHECK
		isomorph_mat[ii]=new matrix[ISOMORPH_MEM[ii]];
#endif
	}

	// ..... set up nauty options
	options.writeautoms=FALSE;
	options.writemarkers=FALSE;
	options.getcanon=TRUE;
#endif

#ifdef FORK
	// set up the kill file
	fp = fopen("kill_proc","w");
#endif

	// START THE SEARCH!
	find_tilings();

	cout << "All done looking at tilings!" << endl;

#ifdef NAUTY
	// clean up memory
	delete[] lab;
	delete[] ptn;
	delete[] orbits;
#endif

#ifdef FORK
	fclose(fp);
#endif
}