int c;
bool gres[2];
int *list;

bool lesseq(int a, int b);

int fact(int a, int recursion) {
  if (recursion > 0) {
    if (lesseq(a,1)) {
      return 1;
    } else {
      return a * fact(a - 1, recursion - 1);
    }
  } else {
    int res;
    res = 1;
    while (a >= 2) {
      res *= a;
      a -= 1;
    }
    return res;
  }
}

void calcFact() {
  cout << fact(6, 3);
  cout << "\n";
  cout << fact(7, 2);
  cout << "\n";
  fact(3, 2);
}

bool lesseq(int a, int b) {
  if (a <= b) {
    return true;
  } else {
    return false;
  }
}


void swap(int *a, int *b) {
  int temp;
  temp = *a;
  *a = *b;
  *b = temp;
}

void quickSort(int *list, int start, int end) {
  int lower;
  int upper;
  lower = start + 1;
  upper = end;
  swap(list + start, list + (start + end) / 2);

  while (lower <= upper) {
    while (list[lower] < list[start]) {
      lower += 1;
    }
    while (list[start] < list[upper]) {
      upper -= 1;
    }
    if (lower < upper) {
      swap(list + lower, list + upper);
      lower += 1;
      upper += 1;
    } else {
      lower += 1;
    }
  }
  swap(list + upper, &list[start]);
  if (start < upper - 1) {
    quickSort(list, start, upper - 1);
  }
  if (upper + 1 < end) {
    quickSort(list, upper + 1, end);
  }
}

void testStructures();

void main() {
  int a;
  int b;
  bool res[5];
  int i;
  int j;

  int a_in[5];
  int b_in[5];
  int c_in[5];
  a_in[0] = 0;
  b_in[0] = 0;
  c_in[0] = 0;
  a_in[1] = 14;
  b_in[1] = 0;
  c_in[1] = 0;
  a_in[2] = 0;
  b_in[2] = 13;
  c_in[2] = -3;
  a_in[3] = 3;
  b_in[3] = -5;
  c_in[3] = -7;
  a_in[4] = -14;
  b_in[4] = -2;
  c_in[4] = -6;

  //can test all combinations of these things
  //by specifing different values for a
  //cont = true;
  //while (cont) {
  for (j = 0; j < 5; j += 1) {
  //  cout << "Enter 3 numbers:\n";
  //  cin >> a;
  //  cin >> b;
  //  cin >> c;
   a = a_in[j];
   b = b_in[j];
   c = c_in[j];
    
    if ((a < 0 || a > 0) && b == 0) {
      cout << "a\n";
    } else {
      cout << "b\n";
    }
    if (a == 0 || b == 0) {
      cout << "c\n";
    } else {
      cout << "d\n";
    }
    res[0] = (c < 0) && (a != 0);
    res[1] = a == 0 || b == 0;
    res[2] = b == 0 || a == 0;
    res[3] = a > 0 && b < 0;
    res[4] = a <= 0;
    gres[0] = a >= 0;
    gres[1] = !gres[0];
    for (i = 0; i <= 4; i = i + 1) {
      cout << res[i];
    }
    cout << gres[0];
    cout << gres[1];
    //cout << "\nContinue? ";
    //cin >> cont;
    cout << "\n";
  }


  // test poping return value off the stack
  calcFact();
  cout << a;
  cout << "\n";
  testStructures();
}

int randSeed;
int randA;
int randC;
int randM;

int rand() {
  randSeed = (randSeed * randA + randC) % randM;
  return randSeed;
}

struct foo {
  int a;
  int arr[15];
  int *arr2[15];
  int *c;
};

void print(struct foo *f) {
  int i;
  int j;
  for (j = 0; j < 15; j += 1) {
    cout << *f->arr2[j];
    cout << "\n";
  }
}

void testStructures() {
  struct foo *f;
  struct foo foo_stack;
  int i;
  int j;
  struct foo *foop_arr[3];
  struct foo foo_arr[3];

  randA = 151;
  randC = 233;
  randM = 179;
  randSeed = 139;
  
  for (i = 0; i < 3; i += 1) {
    foop_arr[i] = sbrk(sizeof(foo));
    foop_arr[i]->a = i;
    for (j = 0; j < 14; j += 1) {
      foop_arr[i]->arr[j] = rand();
      foop_arr[i]->arr2[j] = &(foop_arr[i]->arr[j]);
    }
    *(foop_arr[i]->arr + 14) = randM + 1;
    *(14 + foop_arr[i]->arr2) = j + foop_arr[i]->arr;
  }

  for (i = 0; i < 3; i += 1) {
    cout << foop_arr[i]->a;
    cout << "\n";
    for (j = 0; j < 15; j += 1) {
      cout << *foop_arr[i]->arr2[j];
      cout << "\n";
    }
    
    quickSort(foop_arr[i]->arr, 0, 13);
    cout << "Sorted\n";

    for (j = 0; j < 15; j += 1) {
      cout << **(foop_arr[i]->arr2 + j);
      cout << "\n";
    }
  }

  // Check worst case sorting for quicksort
  cout << "\n\n\nReverse Sorting";
  for (i = 0; i < 3; i += 1) {
    foo_arr[i].a = i * 100;
    for (j = 0; j < 14; j += 1) {
      foo_arr[i].arr[j] = *foop_arr[i]->arr2[13 - j];
      (foo_arr + i)->arr2[j] = &(foo_arr[i].arr[j]);
    }
    foo_arr[i].arr[14] = *foop_arr[i]->arr2[14];
    (i + foo_arr)->arr2[j] = &(foo_arr[i].arr[j]);
    cout << "\nSorting from reverse order\n";
    print(&foo_arr[i]);
    quickSort(foo_arr[i].arr, 0, 13);
    cout << "\nSorted\n";
    f = &foo_arr[2] - (2 - i);
    print(f);
  }

  cout << "\n\nStatic\n";
  for (i = 0; i < 14; i += 1) {
    foo_stack.arr[i] = rand();
  }
  foo_stack.arr[14] = randM + 1;
  f = &foo_stack;
  
  // pointers are mapped in reverse order so list will
  // be printed out high to low
  for (i = 0; i < 15; i += 1) {
    f->arr2[i] = &(f->arr[14]) - i;
  }
  print(&foo_stack);
  quickSort(f->arr, 0, 13);
  cout << "\nSorted High to Low\n";
  print(f);

  // test pointer arithmatic
  cout << "Length: ";
  cout << f->arr2[12] - f->arr2[3];
  cout << " ";
  cout << &foo_arr[3] - &foo_arr[1];
  cout << "\n";
}