#include "stdio.h"
#include "stdlib.h"
#include "assert.h"

long max_cons = 16;
long cons_so_far = 0;
long* fromspace;
long* tospace;
long* val_stack;
long* registers;
long* B;
long* S;
long* T;
long* rbp;
long* rsp;
long maskCAR = ~0xF;
long maskCONS = ~0x2;
long NIL = 0x1;
//function headers
long convert_cINT_toLisp(long x);
long my_CONS(long x, long y);
void print_tree_inorder(long x);
void print_tree(int x);
void print_vs();
void print_reg();
void print_mem();
long my_app(long x, long y);
long APP();
long CONS();
long CAR(long p);
long CDR(long p);
void vs_CAR();
void vs_CDR();
void vs_rplacd();
void vs_rplaca();
void vs_eq();
void vs_equal();
long my_cons_copy(long x);
void cons_copy();
int my_cons_count(long x);
void cons_count();
long my_rev(long x);
void rev();
long my_make_lst(long n);
void make_lst();
long move(long x);
int isPointer(long x);
void flip();
int is_tospace(long x);
int is_fromspace(long x);
void RPLACA(long p, long a);
void RPLACD(long x, long b);
int EQ(long r, long s);
int EQUAL(long x, long y);
int ATOM(long k);

/*
DONUT FORGET: CONS RETURN A POINTER TO THE CDR!! NOT THE CAR!!!!!!!!!
*/

void vs_push(long x) {
	*rsp = x;
	rsp++;
}
void vs_push_integer(int x) { //takes a C int
     vs_push(x<<4);
}

void vs_push_register(int x) {
     vs_push(registers[x]);
}

void vs_push_nil() {
	vs_push(NIL);
}

void vs_push_t() {
	vs_push(1<<4);
}

long vs_pop(){
	long ret = *(rsp-1);
	rsp--;
	return ret;
}

void vs_assign(int x) {
	registers[x] = vs_pop();
}

void vs_CAR() {
	long ptr = vs_pop();
	if(isPointer(ptr))
		vs_push(CAR(ptr));
}

void vs_CDR() {
	long ptr = vs_pop();
	if(isPointer(ptr))
		vs_push(CDR(ptr));
}

void vs_rplacd() {
	long to_replace = vs_pop();
	long val = vs_pop();
	RPLACD(to_replace, val);
}

void vs_rplaca() {
	long to_replace = vs_pop();
	long val = vs_pop();
	RPLACA(to_replace, val);
}

void vs_eq() {
	long x = vs_pop();
	long y = vs_pop();
	if(EQ(x, y)) {
		vs_push(1<<4);
	}
	else {
		vs_push(NIL);
	}
}

void vs_equal() {
	long x = vs_pop();
	long y = vs_pop();
	if(EQUAL(x, y))
		vs_push(1<<4);
	else
		vs_push(NIL);
}


void print_vs_top() {
	long *ret = rsp-1;
	if(isPointer(*ret))
		printf("PTR %ld\n", *ret);
	else if(ATOM(*ret)) {
		printf("INT %ld\n", *ret >> 4);
	}
	else if(*ret == NIL) {
		printf("NIL\n");
	}
	printf("neither\n");
}

void print_tree(int x){
	print_tree_inorder(registers[x]);
	printf("\n");
}

void print_tree_inorder(long x) {
	if(ATOM(x)) {
		if(x == NIL)
			printf("NIL ");
		else
			printf("%ld ", x >> 4);
	}
	else {
		//printf("\n");
		print_tree_inorder(CAR(x));
		print_tree_inorder(CDR(x));
		//printf("\n");
	}
}



void print_mem() {
    long address = (long)tospace;
    printf("TO SPACE:\n");
    printf("+----------------------+ %ld\n", (long)address);
    for (int i = 0; i < max_cons*2; i++) {
        printf("| %ld\t\t\t|\n", (ATOM(tospace[i])) ? tospace[i] >> 4 : tospace[i]);
        printf("+----------------------+ %ld\n", (long)(address += 8));
    }
    address = (long)fromspace;
    printf("\nFROM SPACE:\n");
    printf("+----------------------+ %ld\n", (long)address);
    for (int i = 0; i < max_cons*2; i++) {
        printf("| %ld\t\t\t|\n", (ATOM(fromspace[i])) ? fromspace[i] >> 4 : fromspace[i]);
        printf("+----------------------+ %ld\n", (long)(address += 8));
    }
}

void print_vs() {
	long address = (long)rbp;
	printf("VALUE STACK:\n");
	printf("+----------------------+ %ld\n", (long)(address));
	for (int i = 0; i < (rsp - rbp); i++) {
		printf("| %ld\t\t\t|\n", (ATOM(rbp[i])) ? rbp[i] >> 4 : rbp[i]);
		printf("+----------------------+ %ld\n", (long)(address += 8));
	}
}

void print_reg() {
	long address = (long)registers;
	printf("REGISTERS:\n");
	printf("+----------------------+ %ld\n", (long)(address));
	for (int i = 0; i < 5; i++) {
		printf("| %ld\t\t\t|\n", (ATOM(registers[i])) ? registers[i] >> 4 : registers[i]);
		printf("+----------------------+ %ld\n", (long)(address += 8));
	}
}

int isPointer(long x) {
     return (x & 0xF) == 0x8;
}
long convert_cINT_toLisp(long x) {
     return (x << 4);
}



long CONS() {
	long car = vs_pop();
	long cdr = vs_pop();
	long ret = my_CONS(car, cdr);
	vs_push(ret);
	return ret;
}

long my_CONS(long x, long y) {
     if((long)B == (long)T) { //START GARBAGE COLLECTION
          printf("\n\n\nGARBAGE COLLECTION!!!\n\n");
          flip(); //flip tospace and fromspace
          for(int i = 0; i < max_cons; i++) {
               //printf("register %d\n", i);
               registers[i] = move(registers[i]);
          }
          for(int i = 0; i < (rsp - rbp)/8; i++) {
          	if(isPointer(val_stack[i])) {
          		if(!is_tospace(CDR(val_stack[i])))
          			val_stack[i] = move(val_stack[i]);
          		else
          			val_stack[i] = CDR(val_stack[i]);
          	}
          }
          x = move(x);
          y = move(y);
          while(S < B) {
               //printf("here\n");
               S[0] = move(S[0]);
               S[1] = move(S[1]);
               S += 2;
          }
     }
     //just allocate
      if(B >= T) {
      	//print_mem();
      	printf("out of memory\n");
      	exit(-1);
      }
      B[0] = x;
      B[1] = y;
      long p = (long)(B + 1); //the CDR of the new Cons
      B += 2;
      return p;

}

//assume for our purposes that these will always be in our world, x and y will be our type
long CAR(long p) {
     long* pointer = (long*) (p & maskCAR);
     return *(pointer);
}

long CDR(long p) {
     long* pointer = (long*) p;
     return *pointer;
     //return right
}

long copy(long x) {
     //x is always going to be a pointer to a CDR
     //printf("in copy\n");
     if(B >= T) {
     	printf("error in cons\n");
     	exit(0);
     }
     B[0] = CAR(x);
     B[1] = CDR(x);
     long temp = (long)(B + 1);
     B += 2;
     return temp;
}

long move(long x) {
     //printf("in move %ld\n", x);
     if(!is_fromspace(x)) //not in fromspace, would be a number that hasnt been allocated yet!
          return x;
     else {
          if(!is_tospace(CDR(x))) {
               RPLACD(x, copy(x));
               return CDR(x);
          }
     }
     return CDR(x);
}

void flip() {
     long* temp = tospace;
     tospace = fromspace;
     fromspace = temp;
     B = tospace;
     S = tospace;
     T = tospace + max_cons*2;
}

int is_tospace(long x) {
	if(!isPointer(x))
		return 0;
     long* bot = tospace;
     long* top = tospace + max_cons*2;
     if((long)bot < x && x <= (long)top)
          return 1;
     return 0;
}

int is_fromspace(long x) {
     //check if its an ATOM
     if(!isPointer(x))
          return 0;
     // long bot = (long)fromspace;
     // long top = ((long)fromspace) + max_cons*2;

     long* bot = fromspace;
     long* top = fromspace + max_cons*2;
     if((long)bot < x && x <= (long)top)
          return 1;
     return 0;
}



void RPLACA(long p, long a){
     long* toreplace = (long*)(maskCAR & p);
     *toreplace = a;
     // Replace x of pair x, y, with a
}

void RPLACD(long x, long b) {
     long* pointer = (long*) x;
     *pointer = b;
     // Replace x of pair x, y, with b
}

int EQ(long r, long s) {
     return r == s;
     //do r and s reference the same object
}

int EQUAL(long x, long y) {
	if(ATOM(x) && ATOM(y))
		return x == y;
	else if(ATOM(x) || ATOM(y))
		return 0;

	if(EQUAL(CAR(x), CAR(y)) && EQUAL(CDR(x), CDR(y)))
		return 1;
	else
		return 0;

}


int ATOM(long k) {
     return !(k & 0x8);
     // does k reference a non-pair
}

long APP() {
	long x = vs_pop();
	long y = vs_pop();
	long ret = my_app(x, y);
	vs_push(ret);
}

long my_app(long x, long y) {
	if(ATOM(x))
		return y;
	vs_push(my_app(CDR(x), y));
	vs_push(CAR(x));
	long ret = CONS();
	vs_pop();
	return ret;
}

void rev() {
	long ptr = vs_pop();
	if(!isPointer(ptr)) {
		printf("error in rev\n");
		exit(-1);
	}
	else {
		//long x = vs_pop();
		vs_push(my_rev(ptr));
	}
}

long my_rev(long x) {
	if(ATOM(x))
		return NIL;
	vs_push(NIL);
	vs_push(CAR(x));
	//print_vs();
	CONS();
	vs_push(my_rev(CDR(x)));
	APP();
	long ret = vs_pop();
	return ret;
}

void cons_copy() {
	long ret = my_cons_copy(vs_pop());
	vs_push(ret);
}

long my_cons_copy(long x) {
	if(ATOM(x))
		return x;
	vs_push(my_cons_copy(CDR(x)));
	vs_push(my_cons_copy(CAR(x)));
	CONS();
	return vs_pop();
}

void cons_count() {
	int ret = my_cons_count(vs_pop());
	vs_push_integer(ret);
}

int my_cons_count(long x) {
	if(ATOM(x))
		return 0;
	return 1 + my_cons_count(CAR(x)) + my_cons_count(CDR(x));
}

void make_lst() {
	long ret = my_make_lst(vs_pop()>>4);
	vs_push(ret);
}

long my_make_lst(long n) {
	if(n <= 0)
		return NIL;
	else {
		vs_push(my_make_lst(n-1));
		vs_push_nil();
		CONS();
		long ret = vs_pop();
		return ret;
	}
}

int main(int argc, char* argv[], char** env) {
     max_cons = 2000000;
     fromspace = (long*)malloc((max_cons*2)*sizeof(long));
     tospace = (long*)malloc((max_cons*2)*sizeof(long));
     val_stack = (long*)malloc((max_cons*2)*sizeof(long));
     registers = (long*)malloc(max_cons*sizeof(long));
     rbp = val_stack;
     rsp = val_stack;
     B = tospace;
     S = tospace;
     T = tospace + max_cons*2;
     //printf("bfore\n");
     vs_push_integer(1000);
     //printf("%ld\n", vs_pop()>>4);
     make_lst();
     vs_assign(0);

	 vs_push_register(0);
	 //printf("%ld\n", vs_pop());
	 rev();
	 rev();
	 rev();
	 rev();
	 vs_assign(1);
	 vs_push_register(0);
	 vs_push_register(1);
	 vs_equal();
	 print_vs_top();
	// print_vs_top();
	// printf("what\n");
 //     vs_push_integer(1);
	// print_vs_top();

	// vs_push_integer(2);
	// print_vs_top();

	// //print_vs();

	// CONS();
	// print_vs_top();

	// // print_mem();
	// // print_vs();

	// vs_assign(0);
	// print_tree(0);

	// vs_push_integer(3);
	// print_vs_top();

	// vs_push_integer(4);
	// print_vs_top();

	// //print_vs();

	// CONS();
	// print_vs_top();

	// vs_assign(1);
	// print_tree(1);

	// vs_push_register(0);
	// vs_push_register(1);
	// APP();
	// vs_assign(2);
	// print_tree(2);

	// vs_push_register(2);
	// print_vs_top();
	// // if(isPointer(vs_pop()))
	// // 	printf("IS POINTER\n");
	// rev();
	// print_vs_top();
	// vs_assign(3);
	// print_tree(3);
	// vs_push_register(3);
	// cons_copy();
	// vs_assign(4);
	// print_tree(4);
	// vs_push_register(4);
	// cons_count();
	// print_vs_top();
	//  // vs_push_integer(1);
	 // print_vs_top();
	 // vs_push_integer(2);
	 // print_vs_top();
	 // CONS();
	 // print_vs_top();
	 // vs_assign(0);
	 // print_tree(0);
	 // vs_push_nil();
	 // vs_push_register(0);
	 // CONS();
	 // vs_assign(1);
	 // print_tree(1);
	 // vs_push_register(0);
	 // vs_push_register(1);
	 // APP();
	 // vs_assign(2);
	 // print_tree(2);
	//  print_mem();
	//  vs_push_register(2);
	//  vs_assign(3);
	//  print_tree(3);
	//  vs_push_register(2);
	//  vs_push_register(3);
	//  vs_equal();
	//  print_vs_top();
	//  vs_push_integer(3);
	// print_vs_top();

	// vs_push_integer(4);
	// print_vs_top();

	// print_vs();

	// CONS();
	// print_vs_top();

	// vs_assign(4);
	// print_tree(4);

	// vs_push_register(3);
	// vs_push_register(4);

	// vs_equal();

	// print_vs_top();
     //print_mem();
  //    long ptr = CONS(1 << 4, 2 << 4);
	 // registers[0] = ptr;
	 // registers[1] = CONS(ptr, 3 << 4);
	 // registers[2] = CONS(5 << 4, 6 << 4);
	 // registers[2] = 0;
	 // print_mem();
	 // registers[2] = CONS(7 << 4, 8 << 4);
	 // print_mem();
}










/*
From OH: basically need to wait for tests
CONS should only pull from the value val_stack
the first thing that happens is that you push an int (so make a push_int function that pushes things to the value stack)
push int does the conversion from ints to to our object ints
CONS pulls off of the value stack
so for cons, we basically just assume that its always in OUR WORLD(aka padded with the tag)

*/