/********************************************************************
 *
 * Implementation of adaptive algorithm for determining strings
 * from substrings by asking YES/NO substring questions.
 * Prefix tree version.
 *
 * (C) February - December 1994, Dimitris Margaritis, Steven Skiena
 *
 * $Id: exper.c,v 2.4 1995/04/17 15:17:48 dmarg Exp $
 *
 ********************************************************************/

#include "includes.h"

unsigned q;              /* The alphabet size. */
unsigned C;              /* # of length-N substages / stage. */
char *sequence;          /* The "unknown" string. */
unsigned sequence_len;   /* The length of the "unknown" string (i.e. N). */
NODE *root;              /* The root of the prefix tree. */
unsigned total_num_questions;  /* Total number of questions asked. */

/********************************************************************
 *
 * Execute the experiment.  q is the alphabet size and is expected
 * to fit in a char.
 *
 ********************************************************************/

unsigned do_exper()
{
int step;
unsigned len, new_len, stages, substages;
int howmany, proposedstrings;
#ifdef DEBUG
unsigned yes;
double ratio;
#endif

    root = create_suffix_tree(); /* Construct the full prefix tree. */

#ifdef DEBUG
    print_suffix_tree(root, 0);

/*    { int i, j;

    for (i = 2; i <= 2 * sequence_len; i++)
        for (j = 2; j <= i; j++)
            printf("stree_count_strings(%d, %d) = %u\n", i, j,
                    stree_count_strings(i, j, STREE_COUNT_INFINITY));

    }

    return; */
#endif

  /* ------ Start doing stages of experimentation and computation. */

    len = log((double) sequence_len - 1) / log((double) q);
    total_num_questions = (unsigned) pow((double) q, (double) len);
#ifdef DEBUG
    printf("\n");
    printf("*** Assuming all strings of length ");
    printf("log_base_%u(N) = %u\n", q, len);
    printf("*** are known from a single initial round of length ");
    printf("N = %u\n", sequence_len - 1);
    printf("*** Total number of questions so far is ");
    printf("%u\n\n", total_num_questions);
#endif
    stages = 1;
    do {

#ifdef DEBUG
        printf("Starting stage %u of experiment.\n", stages);
        printf("=================================\n");
#endif

  /*
   * Try increasing the length and see if it creates too
   * many new questions.  "Too many" here
   * means > C * (sequence_len - 1) ("- 1" for excluding the
   * end-of-string marker), where C is passed on the command line
   * (option 's') or, equivalently, more than one substages
   * are needed to actually find all the substrings of double the length.
   */

        new_len = len;
        for (step = 1;
                   (step = MIN(step, sequence_len - 1 - new_len)) >= 1; ) {
#ifdef DEBUG
            printf("Trying step = +%d...", step);
            fflush(stdout);
#endif
            if ((howmany = stree_count_strings(new_len + step,
                                       len, C * (sequence_len - 1))) != -1) {
                proposedstrings = howmany;
                new_len += step;
                step *= 2;                    /* Do doubling. */
#ifdef DEBUG
                printf("yup (proposedstrings = %d < ", proposedstrings);
                printf("C * n = %u) => ", C * (sequence_len - 1));
                printf("query-string length is %u\n", new_len);
                printf("(YES substrings = %u)\n",
                     stree_count_strings(new_len, (sequence_len - 1),
                                                       STREE_COUNT_INFINITY));

#endif
            } else {
                step /= 2;
#ifdef DEBUG
                printf("nope (proposedstrings > ");
                printf("C * n = %u)\n", C * (sequence_len - 1));
#endif
            }
        }

        if (howmany != -1)
            proposedstrings = howmany;

        if (len == new_len) {  /* Couldn't extend even by one, so */
                               /* use more than one substages. */
#ifdef DEBUG
            printf("Couldn't extend even by 1 char using ");
            printf("%u string slots per stage,\n", C * (sequence_len - 1));
            printf("using %u substages.\n", (unsigned)
                  ceil((double) proposedstrings / (sequence_len - 1)));
#endif
            proposedstrings = stree_count_strings(len + 1, len,
                                                    STREE_COUNT_INFINITY);
            len++;
        } else
            len = new_len;

        substages = (unsigned)
                     ceil((double) proposedstrings / (sequence_len - 1));

        total_num_questions += proposedstrings;

#ifdef DEBUG
        yes = stree_count_strings(new_len, (sequence_len - 1),
                                                   STREE_COUNT_INFINITY);

        ratio = (double) proposedstrings / (double) yes;
        printf("\n         # of proposed length-%u strings      ", len);
        printf("%d\n", proposedstrings);
        printf("Ratio = --------------------------------- = ");
        printf("--------------- = %.2lf.\n", ratio);
        printf("         # of YES length-%u strings           ", len);
        printf("%u\n\n", yes);

        printf ("# of length-N substages needed: %u\n", substages);

        printf("\nUtilization: ");
        printf("%f\n\n", (double) proposedstrings /
                                     (substages * (sequence_len - 1)));

        printf("Total number of questions so far is ");
        printf("%u\n\n", total_num_questions);

        printf("End of stage %u.\n", stages);
        printf("=================\n\n");
#endif

        if (proposedstrings > 1)
            stages += substages;

    } while ((proposedstrings > 1) && (len < sequence_len - 1));

    /* stree_destroy(root); */

#ifdef DEBUG
    printf("\n");
    printf("+-------------+\n");
    printf("|  FINISHED!  |\n");
    printf("+-------------+\n");
    printf("\n");
#endif

    return stages;
}

/********************************************************************
 *
 * Main program.
 *
 ********************************************************************/

void main(int argc, char *argv[])
{
int i, c;
extern char *optarg;
BOOL pu_flag = FALSE, a_flag = FALSE, s_flag = FALSE;
unsigned stages;

    if (argc != 7) {
        fprintf(stderr, "Usage: %s ", argv[0]);
        fprintf(stderr, "-a <alphabet-size> ");
        fprintf(stderr, "{ -p <power> | -u <unknown-string> } ");
        fprintf(stderr, "-s <max # of length-N substages / stage>\n");
        exit(1);
    }

    while ((c = getopt(argc, argv, "p:u:a:s:")) != -1) {
        switch (c) {
          case 'p':
            if (pu_flag || !a_flag) {
                if (!a_flag) {
                    fprintf(stderr, "%s: Option 'a' must precede ", argv[0]);
                    fprintf(stderr, "option 'p'\n");
                }
                fprintf(stderr, "Usage: %s ", argv[0]);
                fprintf(stderr, "-a <alphabet-size> ");
                fprintf(stderr, "{ -p <power> | -u <unknown-string> } ");
                fprintf(stderr, "-s <max # of length-N substages / stage>\n");
                exit(1);
            }
            sequence_len = (unsigned) pow(2.0, atof(optarg)) + 1;
            sequence = getmem((sequence_len + 1) * sizeof(char));
            for (i = 0; i < sequence_len - 1; i++)
                sequence[i] = '0' + (char) random_num(q);
            sequence[i++] = '0' + q;  /* String ending marker. */
            sequence[i] = '\0';
            pu_flag = TRUE;
            break;
          case 'u':
            if (pu_flag) {
                fprintf(stderr, "Usage: %s ", argv[0]);
                fprintf(stderr, "-a <alphabet-size> ");
                fprintf(stderr, "{ -p <power> | -u <unknown-string> } ");
                fprintf(stderr, "-s <max # of length-N substages / stage>\n");
                exit(1);
            }
            sequence = optarg;
            sequence_len = strlen(sequence);
            pu_flag = TRUE;
            break;
          case 'a':
            q = atoi(optarg);  /* The alphabet size. */
            a_flag = TRUE;
            break;
          case 's':
            C = atoi(optarg);
            s_flag = TRUE;
            break;
          default:
            fprintf(stderr, "Usage: %s ", argv[0]);
            fprintf(stderr, "-a <alphabet-size> ");
            fprintf(stderr, "{ -p <power> | -u <unknown-string> } ");
            fprintf(stderr, "-s <max # of length-N substages / stage>\n");
            exit(1);
        }
    }

    if ( ! (pu_flag && a_flag && s_flag) ) {
        fprintf(stderr, "Usage: %s ", argv[0]);
        fprintf(stderr, "-a <alphabet-size> ");
        fprintf(stderr, "{ -p <power> | -u <unknown-string> } ");
        fprintf(stderr, "-s <max # of length-N substages / stage>\n");
        exit(1);
    }

#ifdef DEBUG
    printf("Alphabet size = %u.\n", q);
    printf("Unknown string = %s.\n", sequence);
    printf("Unknown string length = %u.\n", (sequence_len - 1));
    printf("Max # of length-N substages / stage = %u\n", C);
#endif

    stages = do_exper();

    printf("%u\t%u\t%u\n", (sequence_len - 1), stages, total_num_questions);

#ifdef DEBUG
    printf("Experiment complete.\n\n");
#endif

    exit(0);

}

/********************************************************************/