#if defined IMPL_STL_NA_NA
  #define IMPL_STL
#endif

#if defined IMPL_BUHR94_NA_NA
  #define IMPL_BUHR94
#endif

#if defined IMPL_STL
  #include <string>
  #include <iostream>
  #include <cstdio>
  using namespace std;
  #define IMPL_CXX

#elif defined IMPL_CFA_HL_SHARE
  #define IMPL_CFA_HL
  #define IMPL_CFA

#elif defined IMPL_CFA_LL_SHARE
  #define IMPL_CFA_LL
  #define IMPL_CFA

#elif defined IMPL_CFA_HL_NOSHARE
  #define IMPL_CFA_HL
  #define CFA_NOSHARE
  #define IMPL_CFA

#elif defined IMPL_CFA_LL_NOSHARE
  #define IMPL_CFA_LL
  #define CFA_NOSHARE
  #define IMPL_CFA

#elif defined IMPL_BUHR94
  #include <iostream>
  #include <cstdio>
  #include "/u0/mlbrooks/usys1/sm/string/StringSharing/src/string.h"
  #define IMPL_CXX

#else
  #error Bad IMPL_
#endif


#if defined IMPL_CFA_HL
  #include <string.hfa>
  extern void TUNING_set_string_heap_liveness_threshold(double);  // in string_res.hfa
#elif defined IMPL_CFA_LL
  #include <string_res.hfa>
#endif

#if defined CFA_NOSHARE
  #include <string_sharectx.hfa>
  #define STRING_SHARING_CONTROL \
    string_sharectx c = { NO_SHARING };
#else 
  #define STRING_SHARING_CONTROL
#endif

#if defined IMPL_CFA
  #include <math.hfa>
  extern "C" {
    void malloc_stats( void );
  }
#elif defined IMPL_CXX
  #include <algorithm>
  using std::min;
  #include <malloc.h>
#endif

#include <time.h>
#include <stdlib.h> // atoi
#include <string.h> // strlen, only during setup

#if defined IMPL_STL || defined IMPL_BUHR94
    #define PRINT(s) std::cout << s << std::endl
#elif defined IMPL_CFA_HL || defined IMPL_CFA_LL
    #define PRINT(s) sout | s;
#else
    #error Unhandled print case
#endif

#if defined IMPL_CFA_LL
    #define STRING_T string_res
    #define ASSIGN_CHAR(str, idx, val) assignAt(str, idx, val)
#else
    #define STRING_T string
    #define ASSIGN_CHAR(str, idx, val) str[idx] = val
#endif

double meanLen(int N, char ** strings) {
    int totalLen = 0;
    for (int i = 0 ; i < N; i ++) {
        totalLen += strlen(strings[i]);
    }
    return (double)totalLen / (double)N;
}

volatile int checkthis = 0;
#define MAYBE( op ) if (checkthis) { op; }

int corpuslen = 0;
char ** corpus = (char**) 0;
size_t corpus_next_pos = 0;

double repsPerLevel;
double repBalance = 0.0000001;

clock_t start, endTarget, end_actual;
size_t allocationCountTarget = 0;

size_t allocationCountActual = 0;
//size_t allocationBytesActual = 0;

void helper( int depth ) {

    if (depth == 0) return;

    corpus_next_pos += 1;
    corpus_next_pos %= corpuslen;

    STRING_T q = corpus[corpus_next_pos];
//    ASSIGN_CHAR(q, 0, '@');    // Turns out my implementation is slow at this step.  A separate test could work it.  It's inessential to the allocation test, given the assumption that both string reps allocate eagerly in their heaps from a constant.  In the STL, that assumption is upheld by my observation that commenting out this line didn't speed it up.  In CFA-share, I know it to be true of the implementation.

    allocationCountActual += 1;
//    allocationBytesActual += q`len;

//    if (depth > 0) {

        repBalance += repsPerLevel;
        int curRepLimit = repBalance;
        repBalance -= curRepLimit;

        for ( int i = 0 ;  i < curRepLimit;  i++ ) {
            if ((allocationCountActual+1) % allocationCountTarget == 0 && clock() > endTarget) return;
            helper(depth-1);
        }
//    }

    MAYBE(PRINT(q));
}

int main( int argc, char ** argv ) {

    STRING_SHARING_CONTROL


    const char * usage_args[] = {"Depth RepsPerLevel ExpansionThreshold    ExecTimeSecs   Corpus...",
                                 "Depth RepsPerLevel ExpansionThreshold -w WorkAllocCount Corpus..."};
    const int static_arg_posns = 5;
    int used_arg_posns = static_arg_posns;

    int launchDepth = -1;
    double expansionThreshold = -1.0;
    int execTimeSecs = -1;

    switch (min(argc, static_arg_posns)) {
      case 5: if ( strcmp(argv[4], "-w") == 0 ) {
                used_arg_posns ++;
                allocationCountTarget = atoi(argv[5]);
              } else {
                execTimeSecs = atoi(argv[4]);
              }
      case 4: expansionThreshold = atof(argv[3]);
      case 3: repsPerLevel = atof(argv[2]);
      case 2: launchDepth = atoi(argv[1]);
    }

    corpuslen = argc - used_arg_posns;
    corpus = argv + used_arg_posns;

    if (launchDepth < 1 || repsPerLevel < 1.0 || (execTimeSecs < 1 && allocationCountTarget < 1) || corpuslen < 1 ||
        (expansionThreshold != -1.0 && (expansionThreshold <= 0.0 || expansionThreshold >= 1.0))) {
      for (int u = 0; u < sizeof(usage_args) / sizeof(*usage_args); u++) {
        printf("usage: %s %s\n", argv[0], usage_args[u]);
      }
      printf("output:\nxxx,corpusItemCount,corpusMeanLenChars,allocationCountActual,execTimeActualSec,topIters\n");
      exit(1);
    }

    if (expansionThreshold != -1.0 ) {
      #if defined IMPL_CFA
      TUNING_set_string_heap_liveness_threshold(expansionThreshold);
      #else
      printf("cannot set expansion threshold on non-CFA implementation");
      exit(1);
      #endif
    }

    double meanCorpusLen = meanLen(corpuslen, corpus);

    // time driven experiment: re-check time every 10000 allocations
    if (execTimeSecs > 0) allocationCountTarget = 10000;

    start = clock();
    endTarget = start + CLOCKS_PER_SEC * max(0, execTimeSecs);

    size_t top_iters = 0;

    for(;;) {
            #if defined OP_PALL
                helper( launchDepth );
            #else
                #error Bad OP_
            #endif

            top_iters++;

            if ((allocationCountActual+1) % allocationCountTarget == 0 && clock() > endTarget) break;
    }
    end_actual = clock();
    double elapsed = ((double) (end_actual - start)) / CLOCKS_PER_SEC;
    printf("xxx,%d,%f,%ld,%f,%ld\n", corpuslen, meanCorpusLen, allocationCountActual, elapsed, top_iters);

    // malloc_stats();

    return 0;
}