/********************************************************************
 *
 * 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_nonadaptive.c,v 1.4 1995/04/15 04:11:26 dmarg Exp $
 *
 ********************************************************************/

#include "includes.h"

unsigned q;              /* The alphabet size. */
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. */

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

unsigned do_exper()
{
unsigned len, stages;
int proposedstrings;
#ifdef DEBUG
#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 = 1;
    stages = 0;
    do {

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

        if (sequence_len - 1 - len < 2 * len) {
            proposedstrings = stree_count_strings(sequence_len - 1 - len,
                                                 len, STREE_COUNT_INFINITY);
            stages += (unsigned)
                ceil((double) proposedstrings / (sequence_len - 1));
            break;
        } else {
            proposedstrings = stree_count_strings(2 * len, len,
                                                   STREE_COUNT_INFINITY);
            stages += (unsigned)
                ceil((double) proposedstrings / (sequence_len - 1));
            len += 2 * len;
        }
    } while (TRUE);

#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 != 5) {
        fprintf(stderr, "Usage: %s ", argv[0]);
        fprintf(stderr, "-a <alphabet-size> ");
        fprintf(stderr, "{ -p <power> | -u <unknown-string> }\n");
        exit(1);
    }

    while ((c = getopt(argc, argv, "p:u:a:")) != -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> }\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> }\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;
          default:
            fprintf(stderr, "Usage: %s ", argv[0]);
            fprintf(stderr, "-a <alphabet-size> ");
            fprintf(stderr, "{ -p <power> | -u <unknown-string> }\n");
            exit(1);
        }
    }

    if ( ! (pu_flag && a_flag) ) {
        fprintf(stderr, "Usage: %s ", argv[0]);
        fprintf(stderr, "-a <alphabet-size> ");
        fprintf(stderr, "{ -p <power> | -u <unknown-string> }\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));
#endif

    stages = do_exper();

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

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

    exit(0);

}

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