/* A program that generates optimal selection functions.
 *
 * Copyright (c) 2002 Kenneth Oksanen <cessu@iki.fi>
 * 
 * This file is distributed under the GNU General Public License
 * version 2 or newer.
 */

/* Begin of configuration section. */

/* Maximum number of elements to select from. */
#ifndef N
#define N  13
#endif

#ifndef I
#define I  7
#endif

/* How much memory are we allowed to allocate from the heap? */
/* #define MAX_N_BYTES  (1024 * 1024) */
#define MAX_N_BYTES  (400 * 1024 * 1024)

/* How much work will we spend on graph (orderset_t) isomorphism
   recognition code? */
#define N_TOPO_ITERATIONS  3

#define N_TOPO_ITERATIONS2  2

/* Shall we automatically perform the pairwise comparisons?
 */
/* #define ASSUME_INITIAL_PAIRWISE */

/* Is it possible that to items are equal?  Define this macro if yes.
 */
/* #define MAY_BE_EQUAL */

/* Is it possible that to items may have undefined order, i.e. the
   input set is only partially ordered.  Define this macro if yes. */
/* #define MAY_BE_UNDEFINED */

/* Define NDEBUG if you want to omit all assertions and thereby speed
   things up a little. */
#define NDEBUG  1

/* Shall the output be C code instead of a functional pseudo-code */
/* #define PRODUCE_C */

/* Shall the output be input to GraphViz's dot input file? */
/* #define PRODUCE_DOT */

/* A value larger or equal to `ceil(log_2(N))' */
#define BITS_IN_N   4

typedef unsigned int cost_t;
#define COST_INFINITE  0x3FF

/* Current cost at the root of the search tree. */
cost_t current_search_cost;

/* Parameters that control the format of output. */
#define VAR_NAME(i)   ("abcdefghijklmnopqrstuvxyz"[i])

/* Humm, should write a configure script, but too lazy for
   now.... :-S */
typedef unsigned int uint32_t;

/* End of configuration section. */

#define VERSION  "1.6"


#ifdef MAY_BE_UNDEFINED
#ifndef MAY_BE_EQUAL
#warning Can not handle partial orders without possible equality.
#warning Defining MAY_BE_EQUAL and trying in any case...
#define MAY_BE_EQUAL
#endif
#endif


#ifndef __GNUC__
#error Sorry, this code contains gcc-specific extensions.
#endif

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

#include <sys/times.h>
#include <unistd.h>
#include <math.h>

/* Requires GNU readline library. */
#include <readline/readline.h>


typedef enum {
  UNTESTED = 0,			/* Must be 0 */
  GREATER,
#ifdef MAY_BE_EQUAL
  EQUAL,
#endif
#ifdef MAY_BE_UNDEFINED
  GREATER_OR_EQUAL,
  INDIFFERENT,
  LESS_OR_EQUAL,
#endif
  LESS,
  N_ORDERS			/* Must be last */
} order_t;


static order_t opposite[N_ORDERS] = {
  UNTESTED,
  LESS,
#ifdef MAY_BE_EQUAL
  EQUAL,
#endif
#ifdef MAY_BE_UNDEFINED
  LESS_OR_EQUAL,
  INDIFFERENT,
  GREATER_OR_EQUAL,
#endif
  GREATER
};


static const char *order_name[N_ORDERS] = {
  "UNTESTED",
  "GREATER",
#ifdef MAY_BE_EQUAL
  "EQUAL",
#endif
#ifdef MAY_BE_UNDEFINED
  "GREATER_OR_EQUAL",
  "INDIFFERENT",
  "LESS_OR_EQUAL",
#endif
  "LESS"
};


static const char order_char[N_ORDERS] = {
  ' ',
  '>',
#ifdef MAY_BE_EQUAL
  '=',
#endif
#ifdef MAY_BE_UNDEFINED
  '',
  '?',
  '',
#endif
  '<'
};


struct parents_t;

typedef struct orderset_t {
  /* Non-zero iff this orderset has been solved. */
  unsigned int solved : 1;
  /* Non-zero iff this orderset can not be removed from the cache. */
  unsigned int locked : 1;
  /* The two variables to optimally compare in this orderset. */
  unsigned int a : BITS_IN_N;
  unsigned int b : BITS_IN_N;
  /* How many variables are there in this orderset.  (The algorithm
     discards uninteresting ones.) */
  unsigned char n : BITS_IN_N;
  /* Which variable was asked from this orderset? 0 < i < n */
  unsigned char i : BITS_IN_N;
  /* Cost for solving this orderset, or if this orderset has not been
     solved, then a cost that is not sufficient to solve this
     orderset. */
  cost_t cost : 10;

#define N_PROBES  4
#define MAX_PRIORITY  0xFFFF
#define INITIAL_PRIORITY  0xFF
  unsigned int priority : 16;

  /* This is used to get some theoretically human-readable output. */
  unsigned int number : 16;

#ifdef MAY_BE_UNDEFINED
#define N_CMPS  ((((N * (N - 1)) / 2) + 15) / 10)
#else
#define N_CMPS  ((((N * (N - 1)) / 2) + 15) / 16)
#endif
  uint32_t order[N_CMPS];
} orderset_t;


/* Forward declaration. */
static cost_t search(orderset_t *, cost_t);


static int order_offset[N];

static void init_offsets(void)
{
  int s = -1, i;

  for (i = 0; i < N; i++) {
    order_offset[i] = s;
    s += N - i - 2;
  }
}


static inline void set_order(orderset_t *orderset, int a, int b, order_t order)
{
  int n = orderset->n;
  unsigned int ix, shmt;
  uint32_t mask;

  assert(a != b);
  assert(a < n);
  assert(b < n);
  /* assert(order > UNTESTED); */

  if (a < b)
    ix = order_offset[a] + b;
  else {
    ix = order_offset[b] + a;
    order = opposite[order];
  }
#ifdef MAY_BE_UNDEFINED
  shmt = (ix % 10) * 3;
  ix = ix / 10;
  mask = 0x7 << shmt;
#else
  shmt = (ix % 16) * 2;
  ix = ix / 16;
  mask = 0x3 << shmt;
#endif

  assert(ix < N_CMPS);
  assert(shmt < 32);

  orderset->order[ix] = (orderset->order[ix] & ~mask) | (order << shmt);
}

static inline order_t get_order(orderset_t *orderset, int a, int b)
{
  int n = orderset->n;
  order_t order;
  unsigned int ix, shmt;
  uint32_t mask;

  assert(a < n);
  assert(b < n);

  if (a == b) {
#ifdef MAY_BE_EQUAL
    return EQUAL;
#else
    assert(0);
    return N_ORDERS;
#endif
  }

  if (a < b)
    ix = order_offset[a] + b;
  else
    ix = order_offset[b] + a;
#ifdef MAY_BE_UNDEFINED
  shmt = (ix % 10) * 3;
  ix = ix / 10;
  mask = 0x7;
#else
  shmt = (ix % 16) * 2;
  ix = ix / 16;
  mask = 0x3;
#endif
  order = (orderset->order[ix] >> shmt) & mask;
  if (a > b)
    order = opposite[order];

  assert(order < N_ORDERS);

  return order;
}


static inline void copy_orderset(orderset_t *to, orderset_t *from)
{
  assert(to != NULL);
  assert(from != NULL);

  memcpy(to, from, sizeof(orderset_t));
  to->locked = 0;
}


static inline int orderset_is_equal(orderset_t *x, orderset_t *y)
{
  if (x == y)
    return 1;
  if (x->n != y->n
      || x->i != y->i
      || memcmp(x->order, y->order, N_CMPS * sizeof(x->order[0])))
    return 0;
  return 1;
}


static void inline clear_orderset(orderset_t *orderset)
{
  memset(orderset, 0, sizeof(*orderset));
}


static void print_orderset(orderset_t *orderset, 
			   unsigned char new_n,
			   unsigned char *new_a)
{
  order_t order;
  int a, b, c, n = orderset->n, is_first = 1;
  unsigned char new_a_reserve[N], old_a[N];

  if (new_a != NULL) {
    n = new_n;
    for (a = 0; a < n; a++)
      old_a[new_a[a]] = a;
  } else {
    for (a = 0; a < n; a++)
      old_a[a] = new_a_reserve[a] = a;
    new_a = new_a_reserve;
  }

#ifdef PRODUCE_DOT
  orderset_t os;

  if (new_a != new_a_reserve)
    /* PRODUCE_DOT not been implemented for new_a-indirection. */
    abort();
  clear_orderset(&os);
  copy_orderset(&os, orderset);
  for (a = 0; a < os.n; a++)
    for (b = 0; b < os.n; b++)
      if (a != b && get_order(&os, b, a) == LESS)
	for (c = 0; c < os.n; c++)
	  if (a != c && b != c && get_order(&os, c, b) == LESS)
	    set_order(&os, a, c, UNTESTED);
  printf("  subgraph cluster_find%d {\n", os.number);
  for (a = 0; a < n; a++)
    printf("    %c%d [label=\"%c\",peripheries=0];\n",
	   VAR_NAME(a), os.number, VAR_NAME(a));
  for (a = 0; a < n - 1; a++)
    for (b = a + 1; b < n; b++)
      switch (get_order(&os, a, b)) {
      case GREATER:
	printf("    %c%d -> %c%d\n",
	       VAR_NAME(a), os.number, VAR_NAME(b), os.number);
	break;
      case LESS:
	printf("    %c%d -> %c%d\n",
	       VAR_NAME(b), os.number, VAR_NAME(a), os.number);
	break;
      default:
	break;
      }
#if 0
  if (os.a != os.b)
    printf("    edge [style=dotted,arrowhead=none,arrowtail=none]\n"
	   "    %c%d -> %c%d [style=dotted];\n"
	   "    { rank=same; %c%d %c%d }\n",
	   VAR_NAME(os.a), os.number, VAR_NAME(os.b), os.number,
	   VAR_NAME(os.a), os.number, VAR_NAME(os.b), os.number);
#endif
  puts("  }");
#else
  printf("n=%d, i=%d", n, orderset->i + 1);
  if (orderset->solved)
    printf(", %c?%c", VAR_NAME(new_a[orderset->a]),
	   VAR_NAME(new_a[orderset->b]));
  for (a = 0; a < n - 1; a++)
    for (b = a + 1; b < n; b++) {
      order_t o;
      int is_transitive;

      if ((o = get_order(orderset, a, b)) == UNTESTED)
	continue;
      for (is_transitive = c = 0; c < n; c++)
	if (c != a
	    && c != b
	    && get_order(orderset, a, c) == o
	    && get_order(orderset, c, b) == o) {
	  is_transitive = 1;
	  break;
	}
      if (is_transitive)
	continue;
      if (is_first) {
	is_first = 0;
	printf(": ");
      } else
	printf(",");
      printf("%c%c%c", 
	     VAR_NAME(new_a[a]),
	     order_char[get_order(orderset, a, b)],
	     VAR_NAME(new_a[b]));
    }
  if (is_first)
    printf(": no comparisons done");
  putchar('\n');
#endif
}

/* Return non-zero on success, zero on failure. */
static int set_order_and_closure(orderset_t *orderset, int a, int b,
				 order_t order)
{
  int i, n = orderset->n;
  order_t old_order = get_order(orderset, a, b);

  switch (order) {
  case LESS:
    switch (old_order) {
    case LESS:
      break;
    case UNTESTED:
#ifdef MAY_BE_UNDEFINED
    case LESS_OR_EQUAL:
    case INDIFFERENT:
#endif
      set_order(orderset, a, b, LESS);
      for (i = 0; i < n; i++)
	if (i != a && i != b) {
	  switch (get_order(orderset, b, i)) {
	  case LESS:
#ifdef MAY_BE_EQUAL
	  case EQUAL:
#endif
	    if (!set_order_and_closure(orderset, a, i, LESS))
	      return 0;
	    break;
	  }
	  switch (get_order(orderset, a, i)) {
	  case GREATER:
#ifdef MAY_BE_EQUAL
	  case EQUAL:
#endif
	    if (!set_order_and_closure(orderset, b, i, GREATER))
	      return 0;
	    break;
	  }
	}
      break;
    default:
      return 0;
      break;
    }
    break;
    
#ifdef MAY_BE_EQUAL
  case EQUAL:
    switch (old_order) {
    case EQUAL:
      break;
    case UNTESTED:
#ifdef MAY_BE_UNDEFINED
    case GREATER_OR_EQUAL:
    case INDIFFERENT:
    case LESS_OR_EQUAL:
#endif
    make_a_b_equal:
      set_order(orderset, a, b, EQUAL);
      for (i = 0; i < n; i++)
	if (i != a && i != b) {
	  switch (get_order(orderset, b, i)) {
	  case EQUAL:
	    if (!set_order_and_closure(orderset, a, i, EQUAL))
	      return 0;
	    break;
	  case GREATER:
	    if (!set_order_and_closure(orderset, a, i, GREATER))
	      return 0;
	    break;
	  case LESS:
	    if (!set_order_and_closure(orderset, a, i, LESS))
	      return 0;
	    break;
	  }
	  switch (get_order(orderset, a, i)) {
	  case EQUAL:
	    if (!set_order_and_closure(orderset, b, i, EQUAL))
	      return 0;
	    break;
	  case GREATER:
	    if (!set_order_and_closure(orderset, b, i, GREATER))
	      return 0;
	    break;
	  case LESS:
	    if (!set_order_and_closure(orderset, b, i, LESS))
	      return 0;
	    break;
	  }
	}
      break;
    default:
      return 0;
      break;
    }
    break;
#endif

#ifdef MAY_BE_UNDEFINED
  case GREATER_OR_EQUAL:
    switch (old_order) {
    case GREATER:
    case GREATER_OR_EQUAL:
    case EQUAL:
      break;
    case LESS_OR_EQUAL:
      goto make_a_b_equal;
      break;
    case UNTESTED:
    case INDIFFERENT:
      set_order(orderset, a, b, GREATER_OR_EQUAL);
      for (i = 0; i < n; i++)
	if (i != a && i != b) {
	  switch (get_order(orderset, a, i)) {
	  case LESS:
	    if (!set_order_and_closure(orderset, b, i, LESS))
	      return 0;
	    break;
	  case LESS_OR_EQUAL:
	  case EQUAL:
	    if (!set_order_and_closure(orderset, b, i, LESS))
	      return 0;
	    break;
	  }
	  switch (get_order(orderset, b, i)) {
	  case GREATER:
	    if (!set_order_and_closure(orderset, a, i, GREATER))
	      return 0;
	    break;
	  case GREATER_OR_EQUAL:
	  case EQUAL:
	    if (!set_order_and_closure(orderset, a, i, GREATER_OR_EQUAL))
	      return 0;
	    break;
	  }
	}
      break;
    }
    break;
  case INDIFFERENT:
    if (old_order == UNTESTED) {
      set_order(orderset, a, b, INDIFFERENT);
      for (i = 0; i < n; i++)
	if (i != a && i != b) {
	  switch (get_order(orderset, a, i)) {
	  case GREATER:
	  case GREATER_OR_EQUAL:
	    if (!set_order_and_closure(orderset, b, i, GREATER_OR_EQUAL))
	      return 0;
	    break;
	  case EQUAL:
	  case INDIFFERENT:
	    if (!set_order_and_closure(orderset, b, i, INDIFFERENT))
	      return 0;
	    break;
	  case LESS:
	  case LESS_OR_EQUAL:
	    if (!set_order_and_closure(orderset, b, i, LESS_OR_EQUAL))
	      return 0;
	    break;
	  }
	  switch (get_order(orderset, b, i)) {
	  case GREATER:
	  case GREATER_OR_EQUAL:
	    if (!set_order_and_closure(orderset, a, i, GREATER_OR_EQUAL))
	      return 0;
	    break;
	  case EQUAL:
	  case INDIFFERENT:
	    if (!set_order_and_closure(orderset, a, i, INDIFFERENT))
	      return 0;
	    break;
	  case LESS:
	  case LESS_OR_EQUAL:
	    if (!set_order_and_closure(orderset, a, i, LESS_OR_EQUAL))
	      return 0;
	    break;
	  }
	}
    }
    break;
  case LESS_OR_EQUAL:
    switch (old_order) {
    case LESS:
    case LESS_OR_EQUAL:
    case EQUAL:
      break;
    case GREATER_OR_EQUAL:
      goto make_a_b_equal;
      break;
    case UNTESTED:
    case INDIFFERENT:
      set_order(orderset, a, b, LESS_OR_EQUAL);
      for (i = 0; i < n; i++)
	if (i != a && i != b) {
	  switch (get_order(orderset, a, i)) {
	  case GREATER:
	    if (!set_order_and_closure(orderset, b, i, GREATER))
	      return 0;
	    break;
	  case GREATER_OR_EQUAL:
	  case EQUAL:
	    if (!set_order_and_closure(orderset, b, i, GREATER))
	      return 0;
	    break;
	  }
	  switch (get_order(orderset, b, i)) {
	  case LESS:
	    if (!set_order_and_closure(orderset, a, i, LESS))
	      return 0;
	    break;
	  case LESS_OR_EQUAL:
	  case EQUAL:
	    if (!set_order_and_closure(orderset, a, i, LESS_OR_EQUAL))
	      return 0;
	    break;
	  }
	}
      break;
    }
    break;
#endif

  case GREATER:
    switch (old_order) {
    case GREATER:
      break;
    case UNTESTED:
#ifdef MAY_BE_UNDEFINED
    case GREATER_OR_EQUAL:
    case INDIFFERENT:
#endif
      set_order(orderset, a, b, GREATER);
      for (i = 0; i < n; i++)
	if (i != a && i != b) {
	  switch (get_order(orderset, b, i)) {
	  case GREATER:
#ifdef MAY_BE_EQUAL
	  case EQUAL:
#endif
	    if (!set_order_and_closure(orderset, a, i, GREATER))
	      return 0;
	    break;
	  }
	  switch (get_order(orderset, a, i)) {
	  case LESS:
#ifdef MAY_BE_EQUAL
	  case EQUAL:
#endif
	    if (!set_order_and_closure(orderset, b, i, LESS))
	      return 0;
	    break;
	  }
	}
      break;
    default:
      return 0;
      break;
    }
    break;
  }

  return 1;
}

/* The orderset must have been closured before calling the following two
   functions. */
static int orderset_is_complete(orderset_t *orderset)
{
  int a, b;

  /* No point in calling this for subordersets. */
  assert(orderset->n == N);
  assert(orderset->i == N);

  for (a = 0; a < N - 1; a++)
    for (b = a + 1; b < N; b++)
      if (get_order(orderset, a, b) == UNTESTED)
	return 0;
  return 1;
}

static int orderset_selects_ith(orderset_t *orderset, int i, 
				unsigned char *varp)
{
  int a, b, n = orderset->n, n_orders[N_ORDERS], j, slop;

  for (a = 0; a < N; a++) {
    for (j = 0; j < N_ORDERS; j++)
      n_orders[j] = 0;

    for (b = 0; b < N; b++)
      if (a != b)
	n_orders[get_order(orderset, b, a)]++;

    slop = 0;
#ifdef MAY_BE_EQUAL
    slop += n_orders[EQUAL];
#endif
#ifdef MAY_BE_UNDEFINED
    slop += n_orders[INDIFFERENT] + n_orders[GREATER_OR_EQUAL];
#endif
    if (n_orders[GREATER] + n_orders[UNTESTED] <= i
	&& i + n_orders[UNTESTED] <= n_orders[GREATER] + slop) {
      if (varp != NULL)
	*varp = a;
      return 1;
    }
  }
  return 0;
}


/* min_n_comparisons[n][i] contains the lowest number of comparisons
   required to solve the corresponding selection problem from the
   beginning.  Contains zero if no lower bound known. */
static unsigned char min_n_comparisons[1 << BITS_IN_N][1 << BITS_IN_N] = {
         /* i=1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15, 16 */
/* n= 0 */ { },
/* n= 1 */ { },
/* n= 2 */ {  1,  1 },
/* n= 3 */ {  2,  3,  2 },
/* n= 4 */ {  3,  4,  4,  3 },
/* n= 5 */ {  4,  6,  6,  6,  4 },
/* n= 6 */ {  5,  7,  8,  8,  7,  5 },
/* n= 7 */ {  6,  8, 10, 10, 10,  8,  6 },
/* n= 8 */ {  7,  9, 11, 12, 12, 11,  9,  7 },
/* n= 9 */ {  8, 11, 12, 14, 14, 14, 12, 11, 8 },
/* n=10 */ {  9, 12, 14, 15, 16, 16, 15, 14, 12,  9 },
/* n=11 */ { 10, 13, 15, 17, 18, 18, 18, 17, 15, 13, 10 },
/* n=12 */ { 11, 14, 17, 18, 19, 21, 21, 19, 18, 17, 14, 11 },
#if 0
/* n=13 */ { 12, 15, 18, 20, 21, 22, 22, 22, 21, 20, 18, 15, 12 },
                              /* ^^^^^^^^^^^ From theory */
/* n=14 */ { 13, 16, 19, 21, 22, 21, 22, 22, 21, 22, 21, 19, 16, 13 },
                          /* ^^^^^^^^^^^^^^^^^^^^^^ From theory */
/* n=15 */ { 14, 17, 20, 22, 22, 23, 23, 24, 23, 23, 22, 22, 20, 17, 14 },
                      /* ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ From theory */
#endif
};


orderset_t *hash_table = NULL;
uint32_t hash_table_size;

unsigned long long n_hits = 0, n_misses = 0;


static inline unsigned int cache_value(unsigned int n, unsigned int i)
{
#if 1
  int shmt = min_n_comparisons[n][i];

  if (shmt > current_search_cost)
    shmt = current_search_cost;

  return shmt;			/* 48.66s */
#endif

#if 0
  unsigned int mid = n / 2;

#if 1
  int shmt = min_n_comparisons[n][i];

  if (shmt > current_search_cost)
    shmt = current_search_cost;

  return shmt;			/* 48.66s */
  return shmt << 2;		/* 79.22s */
  
  shmt >>= 1;

  if (i <= mid)			/* =>>0: 92.56s, =>>1: 47.43s, =>>2: 67.07s,
				   =>>3: 82.86s, =>>4: 51.01s, =>>5: 53.59s */
    return n + (i << shmt);
  else
    return n + ((n - i - 1) << shmt);
#else
  if (i <= mid)			/* 63.52s */
    return i << (n + i / 4);
  else
    return (n - i - 1) << (n + (n - i - 1) / 4);
#endif
#endif

#if 0
  return n;			/* 53.70s */
  return 1;			/* 57.48s */
#endif
}


static inline uint32_t orderset_hash(orderset_t *orderset)
{
  uint32_t h = (orderset->n << 8) | orderset->i;
  int i;

  for (i = 0; i < N_CMPS; i++) {
    h += orderset->order[i] >> 20;
    h += h << 10;
    h ^= h >> 7;
    h += orderset->order[i] >> 9;
    h += h << 10;
    h ^= h >> 7;
    h += orderset->order[i];
    h += h << 10;
    h ^= h >> 7;
  }
  h += h << 3;
  h ^= h >> 11;
  h += h << 15;
  return h;
}


static orderset_t *probe_orderset_cache(orderset_t *orderset, 
					orderset_t **alts)
{
  orderset_t *alts_reserve[N_PROBES];
  orderset_t *p;
  int i, j;
  uint32_t h;
  /* Some random data to prevent possible infinite loops, taken from
     `cat /dev/random | od -x' */
#define N_RNDS  16
  static uint32_t rnd[N_RNDS] = {
    0x33432BD5, 0xD9DA2857, 0xC16CA349, 0xB48E786F,
    0xC280E04C, 0xB6419EF7, 0x35E68035, 0x7327028D,
    0x1618C293, 0x9E0A336E, 0x1709F35C, 0x5102EB06,
    0x2B02AD5B, 0x8E4D16D4, 0x2DEA4A71, 0x2A3DDDC0
  };
  int rnd_ix = 0;

  if (hash_table == NULL) {
    hash_table_size = MAX_N_BYTES / sizeof(orderset_t);
    hash_table = calloc(hash_table_size, sizeof(orderset_t));
    if (hash_table == NULL) {
      fprintf(stderr,
	      "Malloc failed when allocating the %u-entry hash table.  "
	      "Sorry.\n",
	      hash_table_size);
      exit(1);
    }
  }

  h = orderset_hash(orderset);

  if (alts == NULL)
    alts = alts_reserve;
  for (i = 0; i < N_PROBES; i++)
    alts[i] = NULL;
  for (i = 0; i < N_PROBES; i++) {
    p = &hash_table[h % hash_table_size];
    if (orderset_is_equal(p, orderset)) {
      /* Hit!  Increment priority and return. */
      unsigned long v = cache_value(p->n, p->i);
      if (p->priority <= MAX_PRIORITY - v)
	p->priority += v;
      n_hits++;
      return p;
    } else if (!p->locked) {
      for (j = 0; j < i; j++)
	if (alts[j] == p) {
	  /* We don't want to identical pointers in `alts'.  Stir up
	     `h' and pick another slot in the hash table. */
	  h ^= rnd[rnd_ix++];
	  if (rnd_ix == N_RNDS)
	    rnd_ix = 0;
	  i--;
	  goto next_probe;
	}
      alts[i] = p;
    }
    h += h << 3;
    h ^= h >> 11;
    h += h << 15;
  next_probe:
    ;
  }

  /* Miss. */
  n_misses++;
  return NULL;
}

static inline void store_orderset_cache(orderset_t *orderset,
					orderset_t **alts)
{
  int i, j;

  for (i = j = 0; i < N_PROBES; i++) {
    if (alts[i] == NULL) {
      if (i == j)
	j++;
      continue;
    }
    if (i == j || alts[j]->priority > alts[i]->priority)
      j = i;
  }
  if (j < N_PROBES && alts[j] != NULL) {
    copy_orderset(alts[j], orderset);
    alts[j]->priority = cache_value(orderset->n, orderset->i);
  }

  /* Decrease weight of all other alternatives.
   */
  for (i = 0; i < N_PROBES; i++)
    if (i != j && alts[i] != NULL && alts[i]->priority > 1)
      alts[i]->priority--;
}

static void report_orderset_cache(void)
{
  unsigned long long priority_sum = 0, cost_sum = 0;
  unsigned int i, n_solved = 0, n_unsolved = 0;
  orderset_t *p;

  for (i = 0; i < hash_table_size; i++) {
    p = &hash_table[i];
    if (p->cost == 0)
      /* Empty. */
      continue;
    if (p->solved)
      n_solved++;
    else
      n_unsolved++;
    priority_sum += p->priority;
    cost_sum += p->cost;
  }
  printf("# hash_table_size = %u\n", hash_table_size);
  printf("# n_solved = %u\n", n_solved);
  printf("# n_unsolved = %u\n", n_unsolved);
  printf("# n_hits = %llu\n", n_hits);
  printf("# n_misses = %llu\n", n_misses);
  printf("# avg_priority = %.3f\n", 
	 priority_sum / (double) (n_solved + n_unsolved));
  printf("# avg_cost = %.3f\n", 
	 cost_sum / (double) (n_solved + n_unsolved));
}


/* Perform various simplifications and canonifications in the
   orderset, and detects whether the orderset has become solved. */
static inline void canonify_orderset(orderset_t *orderset, 
				     unsigned char *new_a)
{
  unsigned char dropped[N], new_a_reserve[N], n_orders[N][N_ORDERS];
  unsigned int lessness[N], n_topo_iterations;
  order_t order;
  uint32_t topo_hash_old[N], topo_hash_new[N], h;
  int n = orderset->n, new_n, n_less_dropped, a, b, c, j;
  int have_dropped, n_cmps;
  orderset_t new_orderset;

  if (new_a == NULL)
    new_a = new_a_reserve;

  /* Compute the n_orders array.  Given some order, say `GREATER', and
     some variable `a', then `n_orders[a][GREATER]' is computed below
     to tell how many other variables are known to be greater than `a'. */
  memset(n_orders, 0, sizeof(n_orders));
  for (a = 0; a < n - 1; a++)
    for (b = a + 1; b < n; b++) {
      order_t order = get_order(orderset, b, a);
      n_orders[a][order]++;
      n_orders[b][opposite[order]]++;
    }

  /* Mark into `dropped' each variable which is either greater that
     `i' other variables or less than `n-i' other variables. */
  memset(dropped, 0, sizeof(dropped));
  for (n_less_dropped = a = 0; a < n; a++)
    if (n_orders[a][GREATER] > orderset->i)
      dropped[a] = 1;
    else if (n_orders[a][LESS] >= n - orderset->i) {
      dropped[a] = 1;
      n_less_dropped++;
    }

  /* Compute into `new_n' the number of variables not dropped and let
     `new_a[a]' be the new name (number) of variable `a'.  The `new_a'
     is an indirection that will be worked on further. */
  for (new_n = a = 0, b = n - 1; a < n; a++)
    if (!dropped[a])
      new_a[new_n++] = a;
    else
      new_a[b--] = a;

  if (new_n == n)
    have_dropped = 0;
  else {
    have_dropped = 1;
    n = new_n;			/* `new_n' is a cumbersome name... */
    /* We have dropped some variables, therefore recompute the
       `n_orders'-array.  Since it is used later in the orderset
       isomorphism/canonifying code, we might otherwise fail to detect
       the isomorphism of two ordersets, one of which was constructed
       by dropping a variable. */
    memset(n_orders, 0, sizeof(n_orders));
    for (a = 0; a < n - 1; a++)
      for (b = a + 1; b < n; b++) {
	order_t order = get_order(orderset, new_a[b], new_a[a]);
	n_orders[new_a[a]][order]++;
	n_orders[new_a[b]][opposite[order]]++;
      }
  }

  /* Sort the variables into an as canonical order as possible
     according to a number of characteristics:
      - The variable's "lessness" based on already performed
        comparisons (and their transitive closure).
      - Hash values based on the lessness of the variable (`new_a[a]')
        and the relative order and lessness of the other variables
        (`new_a[b]') to which the first variable (`new_a[a]') has an
        established order.
      - Hash values based on the previously computed hash value of the
        variable (`new_a[a]') and the relative order and previously
        computed hash values of the other variables (`new_a[b]') to
        which the first variable (`new_a[a]') has an established
        order.
      - The hash values are recomputed a total of `N_TOPO_ITERATIONS'
        times, where each iteration propagates the topology of the
        graph to the variables.
     After computing the lessnesses and hash values of variables, we
     sort the variables according to increasing lessness and hash
     value.  But this still leaves one significant kind of ordering
     unsolved.  Consider the case of `a>b,c>d'.  The sorting can
     produce either the order `abcd' or `abdc' (`bacd' and `badc' will
     become either one in the later variable renaming).  Therefore, in
     the last pass we do the following:
       - if two or more variables have the same lessness and hash
         values, and if so, we pin their relative order, and use their
         relative orders to rehash variables which have not yet been
         pinned.

     It is still possible that some graph (orderset_t) isomorphishms
     go undetected:
       - hash values are only 32-bit and they can always collide,
         particularly since we can not use arbitrary hash functions,
         but have to choose commutative ones.
       - the last pass performs only one recomputation of the hash
         values, therefore it is possible that isomorphic "zig-zag" or
         "fence-like" orders (`a>b,a>d,c>b,c>d'+same again) do
         not become fully canonified.
     But I hope they would be so infrequent that they cause little
     excess computation. */

  for (a = 0; a < n; a++)
    topo_hash_old[new_a[a]]
      = lessness[new_a[a]]
      = N*N
        - (n_orders[new_a[a]][GREATER] << BITS_IN_N)
        - n_orders[new_a[a]][LESS];
  
  for (n_topo_iterations = 0;
       n_topo_iterations < N_TOPO_ITERATIONS;
       n_topo_iterations++) {

    /* Compute new hash values based on the old ones. */
    for (a = 0; a < n; a++) {
      h = topo_hash_old[new_a[a]];
      h += h << 10;
      for (b = 0; b < n; b++)
	if (a != b
	    && (order = get_order(orderset, new_a[a], new_a[b])) != UNTESTED)
	  h += (topo_hash_old[new_a[b]] << 4) + order;
	  /* NOTE: This hash function must be commutative w.r.t. all
	     other compared variables `new_a[b]'.  Therefore we can
	     *not* issue the typical `h += h << 10; h ^= h >> 7;' here. */
      topo_hash_new[new_a[a]] = h;
    }

#if 0
    /* This was useful for testing. */
    for (a = 0; a < n - 1; a++)
      for (b = a + 1; b < n; b++)
	if (topo_hash_old[new_a[a]] != topo_hash_old[new_a[b]]
	    && topo_hash_new[new_a[a]] == topo_hash_new[new_a[b]]) {
	  /* print_orderset uses new_a differently now. */
	  print_orderset(orderset, n, new_a);
	  printf("n_topo_iterations = %d:\nold:\n", n_topo_iterations);
	  for (a = 0; a < n; a++)
	    printf("%c:%d-%08X ", VAR_NAME(new_a[a]), 
		   lessness[new_a[a]], topo_hash_old[new_a[a]]);
	  printf("\nnew:\n");
	  for (a = 0; a < n; a++)
	    printf("%c:%d-%08X ", VAR_NAME(new_a[a]),
		   lessness[new_a[a]], topo_hash_new[new_a[a]]);
	  printf("\n");
	  goto foo;
	}
  foo:
#endif

    /* Propagate new hash values to become the old ones in the next
       iteration. */
    for (a = 0; a < n; a++)
      topo_hash_old[new_a[a]] = topo_hash_new[new_a[a]];
  }

  /* A simple O(n^2) sort based on the lessness and hash values. */
  for (a = 0; a < n - 1; a++)
    for (b = a + 1; b < n; b++)
      if (lessness[new_a[a]] < lessness[new_a[b]]
	  || (lessness[new_a[a]] == lessness[new_a[b]]
	      && topo_hash_old[new_a[a]] < topo_hash_old[new_a[b]])) {
	j = new_a[a];
	new_a[a] = new_a[b];
	new_a[b] = j;
      }

  /* The final pass. */
  for (a = 1; a < n; a++)
    if (lessness[new_a[a]] == lessness[new_a[a - 1]]
	&& topo_hash_old[new_a[a]] == topo_hash_old[new_a[a - 1]]) {
      /* Skip over the equivalent variables. */
      for (a++; 
	   a < n
	     && lessness[new_a[a]] == lessness[new_a[a - 1]]
	     && topo_hash_old[new_a[a]] == topo_hash_old[new_a[a - 1]];
	   a++)
	;
      if (a == n)
	continue;
      for (n_topo_iterations = 0;
	   n_topo_iterations < N_TOPO_ITERATIONS2;
	   n_topo_iterations++) {
	/* Recompute the hash values. */
	for (c = a; c < n; c++) {
	  h = topo_hash_old[new_a[c]];
	  h += h << 10;
	  for (b = 0; b < a; b++)
	    if ((order = get_order(orderset, new_a[c], new_a[b]))
		!= UNTESTED)
	      h += (topo_hash_old[new_a[b]] << (4 + BITS_IN_N))
		- (order << BITS_IN_N) + b;
	  topo_hash_new[new_a[c]] = h;
	}
	/* Propagate hash values in case we should hash again. */	
	for (c = a; c < n; c++)
	  topo_hash_old[new_a[c]] = topo_hash_new[new_a[c]];
      }
      /* Re-sort the variables below the equivalent ones we just
	 skipped over. */
      for (c = a; c < n - 1; c++)
	for (b = c + 1; b < n; b++)
	  if (lessness[new_a[c]] < lessness[new_a[b]]
	      || (lessness[new_a[c]] == lessness[new_a[b]]
		  && topo_hash_old[new_a[c]] < topo_hash_old[new_a[b]])) {
	    j = new_a[c];
	    new_a[c] = new_a[b];
	    new_a[b] = j;
	  }
      }

  /* Construct a new orderset based on `new_a' and `n'. */
  clear_orderset(&new_orderset);
  new_orderset.n = n;
  new_orderset.i = orderset->i - n_less_dropped;
  for (a = 0; a < n - 1; a++)
    for (b = a + 1; b < n; b++)
      set_order(&new_orderset, a, b,
		get_order(orderset, new_a[a], new_a[b]));
  copy_orderset(orderset, &new_orderset);

  /* Detect if the problem became solved, and feed the killer
     heuristic with a guesstimate of how difficult a problem we have
     left. */
  if (n == 1)
    orderset->solved = 1;
}


static unsigned int inline highest_bit(uint32_t x)
{
  unsigned int i;

  if (x-- == 0)
    return 0;
  for (i = 0; x != 0; i++)
    x >>= 1;
  return i;
}


typedef int n_orders_t[N][N_ORDERS];

typedef enum {
  SOLVED, IMPOSSIBLE, UNCLEAR
} solvability_t;

/* Return non-zero if the given orderset might be solvable in
   `cost_limit' comparisons.  Returns zero only if it is completely
   certain that a solution can not be found in the given number of
   comparisons. */

static inline int estimate_hardness(orderset_t *orderset,
				    int *hardness,
				    int cost_limit,
				    int changed)
{
  int n_orders[N][N_ORDERS];
  int n = orderset->n, a, b, c;
  orderset_t os;
  cost_t cost;

  /* Compute the n_orders array.  Given some order, say `GREATER', and
     some variable `a', then `n_orders[a][GREATER]' is computed below
     to tell how many other variables are known to be greater than `a'. */
  memset(n_orders, 0, sizeof(n_orders));
  for (a = 0; a < n - 1; a++)
    for (b = a + 1; b < n; b++) {
      order_t order = get_order(orderset, b, a);
      n_orders[a][order]++;
      n_orders[b][opposite[order]]++;
    }

  if (hardness != NULL) {
    *hardness = 0;
    for (a = 0; a < n; a++) {
      int d = n_orders[a][GREATER] - n_orders[a][LESS];
      int u = n_orders[a][UNTESTED];
      if (d < 0) d = - d;
      *hardness -= d + 2 * u;
    }
  }


  if (orderset->i == 0 || orderset->i == n - 1)
    return cost_limit >= n - 1;
  /* The following two estimates are based on a lower bound given in
     TAOCP, Volume 3, Section 5.3.3, Exercise 6. */
  else if (orderset->i == 1) {
    uint32_t n_groups = 0, s = 0;
    for (a = 0; a < n; a++)
      if (n_orders[a][GREATER] == 0) {
	n_groups++;
	s += 1 << n_orders[a][LESS];
      }
    return cost_limit >= n_groups - 2 + highest_bit(s);
  } else if (orderset->i == n - 2) {
    uint32_t n_groups = 0, s = 0;
    for (a = 0; a < n; a++)
      if (n_orders[a][LESS] == 0) {
	n_groups++;
	s += 1 << n_orders[a][GREATER];
      }
    return cost_limit >= n_groups - 2 + highest_bit(s);
  } else {
#if 1
    int n_cmps = min_n_comparisons[n][orderset->i];

    /* Subtract from `n_cmps' every order which is not deducible from
       some other order.  Try first the most easily computed ones. */
    for (a = 0; a < n; a++)
      if (n_orders[a][LESS] == 1) {
	n_cmps--;
	if (n_cmps <= cost_limit)
	  goto out;
      }
    for (a = 0; a < n - 1; a++)
      if (n_orders[a][LESS] >= 2)
	for (b = a + 1; b < n; b++) {
	  if (get_order(orderset, b, a) == LESS)
	    if (n_orders[b][GREATER] == 1) {
	      n_cmps--;
	      if (n_cmps <= cost_limit)
		goto out;
	    } else {
	      for (c = 0; c < n; c++)
		if (a != c
		    && b != c
		    && get_order(orderset, b, c) == LESS
		    && get_order(orderset, c, a) == LESS)
		  goto next_b;
	      n_cmps--;
	      if (n_cmps <= cost_limit)
		goto out;
	    next_b:
	      ;
	    }
	}
  out:
    if (n_cmps > cost_limit)
      return 0;
#endif

#if 0
    /* XXX THIS IS INCORRECT! */

    /* Without this heuristic: 697s, with it 330s */
    for (a = 0; a < n; a++) {
      int n_gt, n_lt, n_both;

      if (n - n_orders[a][LESS] - n_orders[a][GREATER] - 1 <= cost_limit)
	/* A quick pre-test. */
	continue;

      n_gt = n_lt = n_both = 0;
      for (b = 0; b < n; b++)
	if (a != b
	    && get_order(orderset, a, b) == UNTESTED) {
	  if (n_orders[b][LESS] == 0)
	    if (n_orders[b][GREATER] == 0)
	      n_both++;
	    else
	      n_gt++;
	  else if (n_orders[b][GREATER] == 0)
	    n_lt++;
	}
      while (n_lt < orderset->i - n_orders[a][LESS] && n_both > 0) {
	n_lt++;
	n_both--;
      }
      while (n_gt < n - orderset->i - 1 - n_orders[a][GREATER] && n_both > 0) {
	n_gt++;
	n_both--;
      }
      if (n_lt + n_gt > cost_limit)
	return 0;
    }
#endif

#if 0
    if (n >= 5 && n <= 8 && changed) {
      copy_orderset(&os, orderset);
      
      /* Remove from `os' all comparisons whose utility is one (or
	 more). */
      for (n_cmps = a = 0; a < n; a++)
	if (n_orders[a][LESS] == 1)
	  for (b = 0; b < n; b++)
	    if (a != b
		&& n_orders[b][GREATER] == 1
		&& get_order(&os, a, b) == GREATER) {
	      set_order(&os, a, b, UNTESTED);
	      n_cmps++;
	      break;
	    }
      canonify_orderset(&os, NULL);
      cost = search(&os, cost_limit + n_cmps);
      return cost <= cost_limit + n_cmps;
    }
#endif

#if 0
    if (n >= 8 && changed) {
      int c;

      copy_orderset(&os, orderset);
      
      /* Add to `os' comparisons that are most probably pretty
	 useless. */
      for (a = 0; a < n; a++)
	if (n_orders[a][LESS] == 0
	    && n_orders[a][GREATER] >= 2) {
	  for (c = 0; c < n; c++)
	    if (a != c 
		&& n_orders[c][LESS] >= 1
		&& n_orders[c][GREATER] >= 1
		&& get_order(orderset, a, c) == LESS) {
	      for (b = 0; b < n; b++)
		if (a != b
		    && n_orders[b][GREATER] == 0
		    && n_orders[b][LESS] >= 2
		    && get_order(orderset, a, b) == UNTESTED) {
		  for (c = 0; c < n; c++)
		    if (b != c
			&& n_orders[c][GREATER] >= 1
			&& n_orders[c][LESS] >= 1
			&& get_order(orderset, b, c) == GREATER) {
		      set_order(&os, a, b, LESS);
		      goto gout1;
		    }
		gout1:
		  ;
		}
	      goto gout2;
	    }
	gout2:
	  ;
	}
	      
      canonify_orderset(&os, NULL);
      cost = search(&os, cost_limit);
      if (cost > cost_limit)
	return 0;
    }
#endif
  }

  return 1;
}


typedef struct {
  unsigned long hash : 28;
  unsigned int n_hits : 4;
} fw_cache_entry_t;

#define N_FW_CACHE_ENTRIES  (1024*1024)

static fw_cache_entry_t fw_cache[N_FW_CACHE_ENTRIES];


static inline solvability_t fw_search(orderset_t *orderset,
				      n_orders_t n_orders,
				      int initial_a, int initial_b,
				      int cost_limit,
				      int depth)
{
  int a, b, d, n = orderset->n;
  orderset_t os, *cached_os;
  solvability_t s;

  copy_orderset(&os, orderset);
  if (initial_a != 0 || initial_b != 0) {
    canonify_orderset(&os, NULL);
    if (!estimate_hardness(&os, NULL, cost_limit, 0))
      return IMPOSSIBLE;
    cached_os = probe_orderset_cache(&os, NULL);
    if (cached_os != NULL)
      if (cached_os->solved)
	if (cached_os->cost <= cost_limit)
	  return SOLVED;
	else
	  return IMPOSSIBLE;
      else
	if (cached_os->cost >= cost_limit)
	  return IMPOSSIBLE;
	else
	  goto unclear;
  }

  /* Experiments showed there's little benefit from depth-limiting the
     loop below. */
  for (a = initial_a; a < n; a++)
    if (n_orders[a][LESS] == 0 && n_orders[a][GREATER] >= 2)
      for (b = (a == initial_a ? initial_b : 0); b < n; b++)
	if (a != b
	    && n_orders[b][GREATER] == 0
	    && n_orders[b][LESS] >= 2
	    /* && (d = n_orders[a][GREATER] + n_orders[b][LESS]) >= 5 */
	    && get_order(orderset, a, b) == UNTESTED) {
	  set_order(orderset, a, b, LESS);
	  s = fw_search(orderset, n_orders, a, b + 1, cost_limit, depth + 1);
	  set_order(orderset, a, b, UNTESTED);
	  if (s == IMPOSSIBLE)
	    return IMPOSSIBLE;
	}

 unclear:
  if (initial_a != 0 || initial_b != 0) {
    uint32_t h = orderset_hash(&os);
    uint32_t i = h % N_FW_CACHE_ENTRIES;

    if (fw_cache[i].hash == (h >> 4)) {
      if (fw_cache[i].n_hits >= 6 && depth <= 4) {
	int cost = search(&os, cost_limit);
	if (cost > cost_limit)
	  return IMPOSSIBLE;
      } else if (fw_cache[i].n_hits < 15)
	fw_cache[i].n_hits++;
    } else {
      fw_cache[i].hash = h >> 4;
      fw_cache[i].n_hits = 1;
    }
  }

  return UNCLEAR;
}


static unsigned long long n_nodes = 0;
static unsigned long nth_orderset = 0;

static cost_t search(orderset_t *parent, cost_t cost_limit)
{
  orderset_t *alts[N_PROBES], *cached_parent, child[N_ORDERS];
  cost_t cost, child_cost;
  order_t order, killer_order;
  int a, b, c, d, hardness, worst_hardness, n, new_n, delta = 0;

  if (parent->solved)
    return parent->cost;
  if (cost_limit <= 0)
    return COST_INFINITE;
  cached_parent = probe_orderset_cache(parent, alts);
  if (cached_parent != NULL) {
    if (cached_parent->solved)
      return cached_parent->cost;
    if (cached_parent->cost >= cost_limit)
      return COST_INFINITE;
    cached_parent->locked = 1;
  }

  n = parent->n;

  {
    n_orders_t n_orders;
    
    memset(n_orders, 0, sizeof(n_orders));
    for (a = 0; a < n - 1; a++)
      for (b = a + 1; b < n; b++) {
	order_t order = get_order(parent, b, a);
	n_orders[a][order]++;
	n_orders[b][opposite[order]]++;
      }
    if (fw_search(parent, n_orders, 0, 0, cost_limit, 0) == IMPOSSIBLE)
      return COST_INFINITE;
  }

  if (cached_parent != NULL)
    parent = cached_parent;

#if 1
  if (nth_orderset++ % 1024 == 0) {
    printf("limit=%d, ", current_search_cost);
    print_orderset(parent, 0, NULL);
  }
  if (nth_orderset % 65536 == 0)
    report_orderset_cache();
#endif

  for (a = 0; a < n - 1; a++)
    for (b = a + 1; b < n; b++)
      if (get_order(parent, a, b) == UNTESTED) {

	worst_hardness = -1000000;
	killer_order = GREATER;
	for (order = GREATER; order <= LESS; order++) {
	  copy_orderset(&child[order], parent);
	  set_order_and_closure(&child[order], a, b, order);
	  canonify_orderset(&child[order], NULL);
	  if (!estimate_hardness(&child[order],
				 &hardness,
				 cost_limit - 1 - delta,
				 n != child[order].n))
	    goto next_comparison;
	  {
	    orderset_t *cached_child = 
	      probe_orderset_cache(&child[order], NULL);
	    if (cached_child != NULL) {
	      if (!cached_child->solved
		  && cached_child->cost >= cost_limit - 1 - delta)
		goto next_comparison;
	    }
	  }
#if 1
	  if (hardness > worst_hardness) {
	    worst_hardness = hardness;
	    killer_order = order;
	  }
#endif
	}

	cost = 0;
	for (order = UNTESTED; order <= LESS; order++) {
	  if (order == UNTESTED)
	    child_cost = search(&child[killer_order], cost_limit - 1 - delta);
	  else if (order == killer_order)
	    continue;
	  else
	    child_cost = search(&child[order], cost_limit - 1 - delta);
	  if (child_cost > cost_limit - 1 - delta)
	    /* This test is equivalent to an alpha-beta cutoff. */
	    goto next_comparison;
	  child_cost++;
	  if (child_cost > cost)
	    cost = child_cost;
	}
	if (cost <= cost_limit) {
	  /* The `delta' is a little trick to cause the comparison to
	     most preferably occur on the first variables, thereby
	     slightly improving readability of the resulting
	     algorithms.  This also corresponds to alpha-beta
	     windowing. */
	  parent->solved = 1;
	  parent->cost = cost;
	  parent->a = a;
	  parent->b = b;
	  delta++;
	}
      next_comparison:
	;
      }

  n_nodes++;

  if (!parent->solved)
    parent->cost = cost_limit;
  if (cached_parent == NULL)
    store_orderset_cache(parent, alts);
  else
    parent->locked = 0;
  if (parent->solved)
    return parent->cost;
  else
    return COST_INFINITE;
}


static unsigned int number = 1;

static void research(orderset_t *parent, int cost_limit)
{
  orderset_t *alts[N_PROBES], *cached_parent, child, *cached_child;
  unsigned char new_a[N];
  cost_t cost;
  order_t order;
  int a, b, i, n, greater_done = 1, less_done = 1;

  n = parent->n;
  cached_parent = probe_orderset_cache(parent, alts);
  if (cached_parent == NULL) {
    cost = search(parent, cost_limit);
    cached_parent = probe_orderset_cache(parent, alts);
  }
  if (cached_parent->number == 0)
    cached_parent->number = number++;
  a = cached_parent->a;
  b = cached_parent->b;

#ifdef PRODUCE_DOT
  print_orderset(cached_parent, 0, NULL);
#else
#ifdef PRODUCE_C
  printf("/*\n");
#else
  printf("# ");
#endif
  print_orderset(cached_parent, 0, NULL);
#ifdef PRODUCE_C
  printf(" */\n");
  printf("int find_%d(", cached_parent->number);
#else
  printf("find_%d(", cached_parent->number);
#endif
  for (i = 0; i < n; i++) {
#ifdef PRODUCE_C
    printf("int %c", VAR_NAME(i));
    if (i < n-1)
      printf(", ");
#else
    putchar(VAR_NAME(i));
    if (i < n-1)
      putchar(',');
#endif
  }
#ifdef PRODUCE_C
  printf(")\n{\n  return %c > %c\n    ? ", VAR_NAME(a), VAR_NAME(b));
#else
  printf(") =\n  if %c > %c\n  then ", VAR_NAME(a), VAR_NAME(b));
#endif
#endif /* !PRODUCE_DOT */

  copy_orderset(&child, parent);
  set_order_and_closure(&child, a, b, GREATER);
  canonify_orderset(&child, new_a);
  if (child.solved)
#ifdef PRODUCE_DOT
    ;
#else
    putchar(VAR_NAME(new_a[0]));
#endif
  else {
    search(&child, cost_limit - 1);
    cached_child = probe_orderset_cache(&child, alts);
    if (cached_child->number == 0) {
      greater_done = 0;
      cached_child->number = number++;
    }
#ifdef PRODUCE_DOT
    printf("  %c%d -> %c%d [ltail = cluster_find%d, lhead = cluster_find%d, "
	   "label=\"%c>%c\"];\n",
	   VAR_NAME(0), cached_parent->number,
	   VAR_NAME(0), cached_child->number,
	   cached_parent->number,
	   cached_child->number,
	   VAR_NAME(a), VAR_NAME(b));
#else
    n = child.n;
    printf("find_%d(", cached_child->number);
    for (i = 0; i < n; i++) {
      putchar(VAR_NAME(new_a[i]));
      if (i < n-1)
	putchar(',');
    }
    putchar(')');
#endif /* !PRODUCE_DOT */
  }
#ifndef PRODUCE_DOT
#ifdef PRODUCE_C
  printf("\n    : ");
#else
  printf("\n  else ");
#endif
#endif

  copy_orderset(&child, parent);
  set_order_and_closure(&child, a, b, LESS);
  canonify_orderset(&child, new_a);
  if (child.solved)
#ifdef PRODUCE_DOT
    ;
#else
    putchar(VAR_NAME(new_a[0]));
#endif
  else {
    search(&child, cost_limit - 1);
    cached_child = probe_orderset_cache(&child, alts);
    if (cached_child->number == 0) {
      less_done = 0;
      cached_child->number = number++;
    }
#ifdef PRODUCE_DOT
    printf("  %c%d -> %c%d [ltail = cluster_find%d, lhead = cluster_find%d, "
	   "label=\"%c<%c\"];\n",
	   VAR_NAME(0), cached_parent->number,
	   VAR_NAME(0), cached_child->number,
	   cached_parent->number, cached_child->number,
	   VAR_NAME(a), VAR_NAME(b));
#else
    n = child.n;
    printf("find_%d(", cached_child->number);
    for (i = 0; i < n; i++) {
      putchar(VAR_NAME(new_a[i]));
      if (i < n-1)
	putchar(',');
    }
    putchar(')');
#endif /* !PRODUCE_DOT */
  }
#ifndef PRODUCE_DOT
#ifdef PRODUCE_C
  printf(";\n}\n\n");
#else
  puts("");
#endif
#endif /* !PRODUCE_DOT */

  if (!less_done) {
    copy_orderset(&child, parent);
    set_order_and_closure(&child, a, b, LESS);
    canonify_orderset(&child, NULL);
    research(&child, cost_limit - 1);
  }

  if (!greater_done) {
    copy_orderset(&child, parent);
    set_order_and_closure(&child, a, b, GREATER);
    canonify_orderset(&child, NULL);
    research(&child, cost_limit - 1);
  }
}


/* Returns wall clock time in seconds since the beginning of the
   program.  Typical use involves two calls; one before and one after
   the benchmark, and the consumed time is the difference of these two
   times. */

static double give_time(void)
{
  struct tms tms;
  long ticks_per_second;
  long ticks;

  ticks = times(&tms);
  if (ticks == -1) {
    fprintf(stderr, "'times' failed\n");
    exit(1);
  }
  ticks_per_second = sysconf(_SC_CLK_TCK);
  if (ticks_per_second == -1) {
    fprintf(stderr, "'sysconf(_SC_CLK_TCK)' failed.\n");
    exit(1);
  }
  return ticks / (double) ticks_per_second;
}


/* An interactive decision tree studying routine.  Returns non-zero if
   full exit not requested. */

static int study(orderset_t *orderset, unsigned char *new_a)
{
  orderset_t *cached_orderset, os;
  char *cmd, old_a[N], newing_a[N], newer_a[N];
  cost_t cost, max_cost;
  int a, b;
  order_t order;

  for (a = 0; a < N; a++) {
    /* printf("new_a[%d] = %d\n", a, new_a[a]); */
    old_a[new_a[a]] = a;
  }

  while (1) {
    cached_orderset = probe_orderset_cache(orderset, NULL);
    if (cached_orderset != NULL)
      orderset = cached_orderset;
    print_orderset(orderset, N, new_a);
    fflush(stdout);
    cmd = readline("# ");
    
    if (cmd == NULL)
      return 0;
    if (cmd[0] == '-' && cmd[1] == '\0')
      /* Go one step up towards to root of the decision tree. */
      return 1;
    else if (cmd[0] == '!' && cmd[1] == '\0') {
      printf("   ");
      for (b = 1; b < N; b++)
	printf("  %c", VAR_NAME(b));
      for (a = 0; a < N - 1; a++) {
	puts("");
	if (a > 0)
	  printf("%*c", 3*a, ' ');
	printf("%c ?", VAR_NAME(a));
	for (b = a + 1; b < N; b++)
	  if (get_order(orderset, old_a[a], old_a[b]) != UNTESTED)
	    printf("   ");
	  else {
	    fflush(stdout);
	    current_search_cost = 0;
	    do {
	      copy_orderset(&os, orderset);
	      set_order_and_closure(&os, old_a[a], old_a[b], LESS);
	      canonify_orderset(&os, NULL);
	      cost = search(&os, current_search_cost);
	    } while (cost > current_search_cost++);
	    max_cost = cost;
	    current_search_cost = 0;
	    do {
	      copy_orderset(&os, orderset);
	      set_order_and_closure(&os, old_a[a], old_a[b], GREATER);
	      canonify_orderset(&os, NULL);
	      cost = search(&os, current_search_cost);
	    } while (cost > current_search_cost++);
	    if (cost > max_cost)
	      max_cost = cost;
	    printf("%3d", max_cost);
	  }
      }
      puts("");
    } else if (cmd[0] == '?' && cmd[1] == '\0') {
      printf("   ");
      for (b = 0; b < N; b++)
	printf("  %c", VAR_NAME(b));
      for (a = 0; a < N; a++) {
	printf("\n%c <", VAR_NAME(a));
	for (b = 0; b < N; b++)
	  if (get_order(orderset, old_a[a], old_a[b]) != UNTESTED)
	    printf("   ");
	  else {
	    fflush(stdout);
	    current_search_cost = 0;
	    do {
	      copy_orderset(&os, orderset);
	      set_order_and_closure(&os, old_a[a], old_a[b], LESS);
	      canonify_orderset(&os, NULL);
	      cost = search(&os, current_search_cost);
	    } while (cost > current_search_cost++);
	    printf("%3d", cost);
	  }
      }
      puts("");
    } else if (cmd[0] >= 'a' 
	       && cmd[0] < 'a' + N 
	       && (cmd[1] == '<' || cmd[1] == '>')
	       && cmd[2] >= 'a'
	       && cmd[2] < 'a' + N
	       && cmd[3] == '\0') {
      a = cmd[0] - 'a';
      b = cmd[2] - 'a';
      order = cmd[1] == '<' ? LESS : GREATER;
      if (get_order(orderset, old_a[a], old_a[b]) != UNTESTED)
	printf("The relative order of %c and %c is already known.\n",
	       VAR_NAME(a), VAR_NAME(b));
      else {
	copy_orderset(&os, orderset);
	set_order_and_closure(&os, old_a[a], old_a[b], order);
	canonify_orderset(&os, newing_a);
	for (a = 0; a < N; a++) {
	  newer_a[a] = new_a[newing_a[a]];
	  /* printf("a=%d, new=%d, newing=%d, newer=%d\n",
	     a, new_a[a], newing_a[a], newer_a[a]); */
	}
	if (!study(&os, newer_a))
	  return 0;
      }
    } else
      printf("Unrecognized command.\n");
  }
}


int main(int argc, char **argv)
{
  orderset_t initial;
  cost_t found_cost;
  double t_start, t_end;
  unsigned char new_a[N];
  int a;

  init_offsets();

  t_start = give_time();
  clear_orderset(&initial);
  initial.n = N;
  initial.i = I - 1;
#ifdef ASSUME_INITIAL_PAIRWISE
  for (a = 0; a < N - 1; a += 2)
    set_order(&initial, a, a + 1, GREATER);
#endif

#ifdef PRINT_COST
  set_order_and_closure(&initial, 0, 1, GREATER);
  set_order_and_closure(&initial, 0, 2, GREATER);
  set_order_and_closure(&initial, 2, 3, GREATER);
  set_order_and_closure(&initial, 3, 4, GREATER);
#endif

  canonify_orderset(&initial, NULL);
  if (initial.solved)
    found_cost = 0;
  else {
    current_search_cost = 1;
    do {
#ifndef PRINT_COST
      fprintf(stderr, "searching V(%d,%d) with maximum cost %d\n", 
	      N, I, current_search_cost);
#endif
      /* n_nodes = n_hits = n_misses = 0; */
      found_cost = search(&initial, current_search_cost);
    } while (found_cost > current_search_cost++);
  }

#ifdef PRINT_COST
  printf("%3d", min_n_comparisons[N][I - 1] - found_cost);
  return 0;
#endif

  t_end = give_time();
  fprintf(stderr, "solved V(%d,%d) = %d\n", N, I, found_cost);

#ifdef PRODUCE_DOT
  printf("digraph V_%d_%d {\n", N, I);
  puts("  compound=true;");
  puts("  size=\"8.4,11.9\";");
#else
#ifdef PRODUCE_C
  puts("/*");
#endif
#ifdef ASSUME_INITIAL_PAIRWISE
  puts("# NOTE: This code has been generated using the assumption that we");
  puts("# first compare pairwise all variables, which in this case requires");
  printf("# performing %d comparisons.  Gasarch et al. conjecture that this\n",
	 N / 2);
  puts("# should not lead to suboptimal selection algorithms.  In this");
  printf("# particular case (N=%d, I=%d) the found algorithm's complexity\n",
	 N, I);
  puts("# coincides with the best known theoretical result, and we can hence");
  puts("# deduce that this algorithm is optimal.\n");
#endif

  printf("# cost = %d\n", (int) found_cost);
  printf("# n_nodes = %llu\n", n_nodes);
  printf("# version = " VERSION "\n");
  printf("# time = %.3f\n", t_end - t_start);
  report_orderset_cache();
#ifdef PRODUCE_C
  puts("*/");
#else
  puts("");
#endif
#endif /* PRODUCE_DOT */
  fflush(stdout);

  research(&initial, found_cost);

#ifdef PRODUCE_DOT
  puts("}");
#endif

#ifdef STUDY
  for (a = 0; a < N; a++)
    new_a[a] = a;
  study(&initial, new_a);
#endif

  return 0;
}