// BEGIN mycpp output

#include "gc_heap.h"

using gc_heap::Alloc;
using gc_heap::kZeroMask;
using gc_heap::StackRoots;
#include "my_runtime.h"
#include "mylib2.h"

using gc_heap::NewStr;
using gc_heap::NewList;
using gc_heap::NewDict;
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<Str*>* dims, List<Str*>* out);
void run_tests();
void run_benchmarks();

}  // declare namespace cartesian

namespace cartesian {  // define

void Cartesian(List<Str*>* dims, List<Str*>* out) {
  List<Str*>* rest = nullptr;
  StackRoots _roots({&dims, &out, &rest});

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

void run_tests() {
  List<Str*>* out = nullptr;
  List<Str*>* tmp = nullptr;
  List<Str*>* tmp2 = nullptr;
  StackRoots _roots({&out, &tmp, &tmp2});

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

void run_benchmarks() {
  int i;
  int n;
  List<Str*>* out = nullptr;
  StackRoots _roots({&out});

  i = 0;
  n = 200000;
  while (i < n) {
    out = Alloc<List<Str*>>();
    Cartesian(NewList<Str*>(std::initializer_list<Str*>{str5, str6, str7}), out);
    i = (i + 1);
  }
}

}  // define namespace cartesian