//------------------------------------------------------
// STAMP FOLDINGS, SEMI-MEANDERS, OPEN MEANDERS
// Research by:   Joe Sawada, Roy Li
// Programmed by: Joe Sawada 2008
//------------------------------------------------------
#include <stdio.h>		
#define MAX(a,b) ((a > b) ? a : b)
#define MAX_VAL 99
#define NULL -1 

typedef struct List {
	int head, tail;
} List;

typedef struct Interval {
	int left, right, prev, next, node_ptr, next_perm, prev_perm;
} Interval;

typedef struct Node {
	List L, R;
	int up_interval;
	char up_side;
} Node;

//--------------------------------------------------------------------------------
// GLOBAL VARIABLES
//--------------------------------------------------------------------------------
Interval interval[MAX_VAL];
List perm;
Node node[MAX_VAL];
int N, total=0, MEANDER=0, SEMI=0, STAMP=0, UNLABELED=0, SYM_SEMI=0;

//--------------------------------------------------------------------------------
void Input() {
int type;

    printf("\n  1.  Open meanders \n");               
    printf("  2.  Semi-meanders \n"); 
	printf("  3.  Stamp foldings     \n");            
    printf("  4.  Symmetric meanders   \n");                        
    printf("  5.  Symmetric semi-meanders   \n");                        
    printf("  6.  Unlabeled stamp foldings    \n");                     

    printf("\nENTER object #: ");    scanf("%d", &type);
	printf("ENTER order n: ");    scanf("%d", &N);
	printf("\n");
		
	if (type == 1) MEANDER = 1;				// SLOANE A005316
	if (type == 2) SEMI = 1;				// SLOANE A000682
	if (type == 3) STAMP = 1;				// SLOANE A000136
	if (type == 4) UNLABELED = MEANDER = 1;	// SLOANE A077055
	if (type == 5) SYM_SEMI = 1;			// SLOANE A000560
	if (type == 6) UNLABELED = STAMP = 1;	// SLOANE A001011
}
//--------------------------------------------------------------------------------
void Print() {
int i, j=0, one=0, a[MAX_VAL];

	i=perm.head;
	while(i != NULL) {
			a[++j] = interval[i].right;
			if (a[j] == 1) one = 1;
			else if (UNLABELED && a[j] == N && one == 0) return; 
			i = interval[i].next_perm;
	}
	for (j=1; j<=N; j++) {
		if (a[j] < N-a[N-j+1]+1) break;
		if (UNLABELED && a[j] > N-a[N-j+1]+1) return;
	}

	//for (j=1; j<=N; j++) printf("%d ", a[j]);
	//printf("\n");
	total++;
}
//--------------------------------------------------------------------------------
void InsertInterval(List *list, int t, int left, int right, int p, int n, int node_ptr) {

	if (p != NULL) interval[p].next = t;	
	else list->head = t;

	if (n != NULL) interval[n].prev = t;	
	else list->tail = t;

	interval[t].left = left;
	interval[t].right = right;
	interval[t].prev = p;
	interval[t].next = n;
	interval[t].node_ptr = node_ptr;
}

void RemoveInterval(List *list, int t) {

	if (interval[t].next == NULL) list->tail = interval[t].prev;
	else interval[interval[t].next].prev = NULL;

	if (interval[t].prev == NULL) list->head = interval[t].next;
	else interval[interval[t].prev].next = NULL;
}

void MoveInterval(int t, List *list1, List *list2, int p, int n, int node_ptr) {

	RemoveInterval(list1, t);
	InsertInterval(list2, t, interval[t].left, interval[t].right, p, n, node_ptr);
}
//--------------------------------------------------------------------------------
void SetNode(int t, int up_interval, int up_side) {

	node[t].up_interval = up_interval;
	node[t].up_side = up_side;
}

void SetNodeLists(int t, int left_head, int left_tail, int right_head, int right_tail) {

	if (left_head == NULL || left_tail == NULL) left_head = left_tail =  NULL; 
	if (right_head == NULL || right_tail == NULL) right_head = right_tail = NULL;
	
	node[t].L.head = left_head;
	node[t].L.tail = left_tail;
	node[t].R.head = right_head;
	node[t].R.tail=  right_tail;
}
//--------------------------------------------------------------------------------
void UpdatePerm(t, i) {
int p, n;
			
	p = interval[i].prev_perm;
	n = interval[i].next_perm;

	interval[2*t-1].prev_perm = p;
	interval[2*t-1].next_perm = 2*t;
	interval[2*t].prev_perm = 2*t-1;
	interval[2*t].next_perm = n;

	if (p != NULL) interval[p].next_perm = 2*t-1; 
	else perm.head = 2*t-1;
	if (n != NULL) interval[n].prev_perm = 2*t; 
}

void RestorePerm(t, i) {
int p, n;
			
	p = interval[i].prev_perm;
	n = interval[i].next_perm;

	if (p != NULL) interval[p].next_perm = i; 
	else perm.head = i;
	if (n != NULL) interval[n].prev_perm = i; 
}
//--------------------------------------------------------------------------------
void Gen(int t, Node* X, int depth) {
Node *Y;
int i, up, j, n, p, old_up_side, old_up_interval, side, k;

	if (t > N) Print();
	else {	
		// VISIT LEFT LIST, THEN RIGHT LIST
		for (side=1; side<=2; side++) {
	
			if (SYM_SEMI && t == 2 && side == 2) return;

			up = 0;
			if (side == 1) i = X->L.head;
			else  i = X->R.head;
			
			// OPTIMIZATION FOR MEANDERS
			if (MEANDER && N-t <= depth) {                     
				i = X->up_interval;
				if (X->up_side == 'l')  side = 1;
				else side = 2;
			}
			
			// VISIT ALL INTERVALS IN LIST
			while (i != NULL) {
			
				n = interval[i].next;
				p = interval[i].prev;
				j = interval[i].node_ptr;
				Y = &node[j];
			
				old_up_interval = Y->up_interval;
				old_up_side = Y->up_side;
				
				SetNode(2*t-1, -1,-1);
				SetNode(2*t, -1,-1);
				
				// UPDATE NEXT NODE and CREATE 2 NEW NODES
				if (side == 1) {
					if (STAMP && depth == 0 && i == X->L.head) {
						up = 1;					
						if (Y->L.head != NULL) SetNodeLists(j, NULL, NULL, Y->L.head, Y->L.tail);						
						MoveInterval(X->R.tail, &X->R, &Y->R, Y->R.tail, NULL, 2*t-1);
					}
					else if (X->up_interval == i)  {
						up = 1;
						if ((MEANDER || SEMI) && depth == 0) SetNode(j, 2*t-1, 'l');
					}
					else if (up == 1 ||  X->up_side == 'r') {
					    SetNode(j, 2*t-1, 'l');
						SetNode(2*t-1, X->up_interval, X->up_side);
					}
					else {
						SetNode(j, 2*t, 'r');
						SetNode(2*t, X->up_interval, 'r');
					}
					SetNodeLists(2*t-1, X->L.head, p, X->R.head, X->R.tail);   
					SetNodeLists(2*t, NULL, NULL, n, X->L.tail);
				}
				else {
					if (STAMP && depth == 0 && i == X->R.tail)  {
						up = 1;
						if (Y->R.head != NULL) SetNodeLists(j, Y->R.head, Y->R.tail, NULL, NULL);							
						MoveInterval(X->L.head, &X->L, &Y->L, NULL, Y->L.head, 2*t);			
					}
					else if (X->up_interval == i)  {
						up = 1;
						if ((MEANDER || SEMI) && depth == 0) SetNode(j, 2*t, 'r');
					}
					else if (up == 1) {
						SetNode(j, 2*t-1, 'l');
						SetNode(2*t-1, X->up_interval, 'l');
					}
					else {
						SetNode(j, 2*t, 'r');
						SetNode(2*t, X->up_interval, X->up_side);
					}
					SetNodeLists(2*t-1, X->R.head, p, NULL, NULL);   
					SetNodeLists(2*t, X->L.head, X->L.tail, n, X->R.tail);
				}
	
				// INSERT NEW INTERVALS
				InsertInterval(&Y->L, 2*t-1, interval[i].left, t, Y->L.tail, NULL, 2*t-1);
				InsertInterval(&Y->R, 2*t, t, interval[i].right, NULL, Y->R.head, 2*t);
				
				// REMOVE CURRENT INTERVAL 
				if (n != NULL) interval[n].prev = NULL;
				if (p != NULL) interval[p].next = NULL;
			
				// UPDATE THE PERMUTATION 
				UpdatePerm(t,i);
	
				// MAKE RECURSIVE CALLS
				if (STAMP && depth == 0 && (i== X->R.tail || i == X->L.head)) Gen(t+1, Y, 0);
				else if (X->up_interval == i)  Gen(t+1, Y, MAX(0,depth-1));
				else Gen(t+1, Y, depth+1);

				// RESTORE DATA STRUCTURES
				RestorePerm(t,i);
	
				if (n != NULL) interval[n].prev = i;
				if (p != NULL) interval[p].next = i;
				
				RemoveInterval(&Y->L, 2*t-1);
				RemoveInterval(&Y->R, 2*t); 

				SetNode(j, old_up_interval, old_up_side);
				
				if (STAMP && depth == 0) {
					if (i == X->L.head) MoveInterval(Y->R.tail, &Y->R, &X->R, X->R.tail, NULL, j);
					if (i == X->R.tail) MoveInterval(Y->L.head, &Y->L, &X->L, NULL, X->L.head, j);
				}
				
				i = n;	// NEXT INTERVAL
				if (MEANDER && N-t <= depth) return; 
}	}	}	}
//--------------------------------------------------------------------------------
int main() {
int i,j;

	Input();
	
	// INITIALIZE NODES
	for (i=0; i<=2*N; i++) {
		node[i].L.head = node[i].L.tail = NULL;
		node[i].R.head = node[i].R.tail = NULL;
		node[i].up_interval = NULL;
		node[i].up_side = '-';
	}

	SetNode(0, 2, 'r');	
	InsertInterval(&node[0].L, 1, 0, 1, NULL, NULL, 2);
	InsertInterval(&node[0].R, 2, 1, MAX_VAL, NULL, NULL, 1);
	
	perm.head = 1;
	interval[1].prev_perm = NULL;
	interval[1].next_perm = 2;
	interval[2].prev_perm = 1;
	interval[2].next_perm = NULL;
		
	Gen(2, &node[0], 0);
	printf("Total = %d\n", total);
}