#include <time.h>
#include <ctype.h>
#include <stdio.h>
#include <stddef.h>
#include <stdlib.h>
#include <string.h>
 
void print_combinations_aux(char *s, size_t pos) {
  if(s[pos] == '\0') {
    puts(s);
  } else if(isalpha(s[pos])) {
    s[pos] = toupper(s[pos]);
    print_combinations_aux(s, pos + 1);
    s[pos] = tolower(s[pos]);
    print_combinations_aux(s, pos + 1);
  } else {
    print_combinations_aux(s, pos + 1);
  }
}
 
void print_combinations_inplace(char *s) {
  print_combinations_aux(s, 0);
}
 
void print_combinations(char const *s) {
  char *p = malloc(strlen(s) + 1);
  strcpy(p, s);
  print_combinations_inplace(p);
  free(p);
}
 
char *next_combination(char *s) {
  // upper -> 0, lower -> 1
  char *p;
 
  if(*s == '\0') { return NULL; }
 
  for(p = s; *p; ++p) {
    if(!isalpha(*p)) {
      continue;
    } else if(isupper(*p)) {
      *p = tolower(*p);
      return s;
    } else {
      *p = toupper(*p);
    }
  }
 
  return NULL;
}

void analyze(const char *c, unsigned *bitmask, unsigned *combos, char *togglecase)
{
  unsigned bit=1;
  int i;

  *bitmask = 0;
  *combos = 1;
  for (; *c; c++, bit<<=1)
    if (isalpha(*c))
      *combos <<= 1;
    else
      *bitmask |= bit;

  for (i=0; i<256; i++)
    togglecase[i] = isupper(i) ? tolower(i) : toupper(i);
}

void next_bit_combination(char *c, unsigned *pbitmask, unsigned startmask, const char *togglecase) {
  unsigned bitmask = *pbitmask;
  *pbitmask = bitmask + 1;
  unsigned diff = (bitmask ^ *pbitmask) & ~startmask;
  *pbitmask = *pbitmask | startmask;
  unsigned least_index;
  if (diff == 1)
    c[0] = togglecase[(unsigned char)c[0]];
  else
    do {
      least_index = __builtin_ctz(diff);
      c[least_index] = togglecase[(unsigned char)c[least_index]];
    } while ((diff -= 1u<<least_index));
}
 
int main() {
    
  clock_t start, end;
  //char buf[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZA";
  //char buf[] = "A B C D E F G H I J K L M N O P Q R S T U V W X Y Z !";

  // für ideone
  char buf[] = "A B C";
  
  start = clock();
 
  unsigned bitmask, combos, startmask;
  char table[256];
  analyze(buf, &bitmask, &combos, table);
  startmask = bitmask;
  for (; combos--; next_bit_combination(buf, &bitmask, startmask, table)) {
    puts(buf);
  }
 
  end = clock();
 
  fprintf(stderr, "bittig: %lf\n", (double) (end - start) / CLOCKS_PER_SEC);

  puts(buf);
  puts(buf);
  puts(buf);
  puts(buf);
 
  start = clock();
 
  do {
    puts(buf);
  } while(next_combination(buf));
 
  end = clock();
 
  fprintf(stderr, "iterativ: %lf\n", (double) (end - start) / CLOCKS_PER_SEC);
 
  start = clock();
 
  print_combinations_inplace(buf);
 
  end = clock();
 
  fprintf(stderr, "rekursiv: %lf\n", (double) (end - start) / CLOCKS_PER_SEC);
 
  return 0;
}