// BEGIN mycpp output

#include "mycpp/runtime.h"

GLOBAL_STR(str0, "ab");
GLOBAL_STR(str1, "--");
GLOBAL_STR(str2, "ab");
GLOBAL_STR(str3, "-|_");
GLOBAL_STR(str4, "ABC");
GLOBAL_STR(str5, "ab");
GLOBAL_STR(str6, "-|_");
GLOBAL_STR(str7, "ABC");

namespace cartesian {  // forward declare


}  // forward declare namespace cartesian

namespace cartesian {  // declare

void Cartesian(List<BigStr*>* dims, List<BigStr*>* out);
void run_tests();
void run_benchmarks();

}  // declare namespace cartesian

namespace cartesian {  // define


void Cartesian(List<BigStr*>* dims, List<BigStr*>* out) {
  List<BigStr*>* rest = nullptr;
  if (len(dims) == 1) {
    for (StrIter it(dims->at(0)); !it.Done(); it.Next()) {
      BigStr* ch = it.Value();
      out->append(ch);
    }
  }
  else {
    rest = Alloc<List<BigStr*>>();
    Cartesian(dims->slice(1), rest);
    for (StrIter it(dims->at(0)); !it.Done(); it.Next()) {
      BigStr* ch = it.Value();
      for (ListIter<BigStr*> it(rest); !it.Done(); it.Next()) {
        BigStr* r = it.Value();
        out->append(str_concat(ch, r));
      }
    }
  }
}

void run_tests() {
  List<BigStr*>* out = nullptr;
  List<BigStr*>* tmp = nullptr;
  List<BigStr*>* tmp2 = nullptr;
  out = Alloc<List<BigStr*>>();
  tmp = NewList<BigStr*>(std::initializer_list<BigStr*>{str0});
  Cartesian(tmp, out);
  for (ListIter<BigStr*> it(out); !it.Done(); it.Next()) {
    BigStr* s = it.Value();
    print(s);
  }
  print(str1);
  out = Alloc<List<BigStr*>>();
  tmp2 = NewList<BigStr*>(std::initializer_list<BigStr*>{str2, str3, str4});
  Cartesian(tmp2, out);
  for (ListIter<BigStr*> it(out); !it.Done(); it.Next()) {
    BigStr* s = it.Value();
    print(s);
  }
}

void run_benchmarks() {
  int i;
  int n;
  List<BigStr*>* out = nullptr;
  i = 0;
  n = 100000;
  while (i < n) {
    out = Alloc<List<BigStr*>>();
    Cartesian(NewList<BigStr*>(std::initializer_list<BigStr*>{str5, str6, str7}), out);
    i = (i + 1);
    mylib::MaybeCollect();
  }
}

}  // define namespace cartesian