/*
	1.1 fake ALLOC (fake memory management)
		where it is not possible to use malloc
		where multiple memory allocation is a speed issue
		where u want to keep ure program within a memory limit
	2.1 rotational LIST (dual-linked node array)
		2.1.0	STRUCT	they always refer to the sentinel
		2.1.1	CREATE	fast node insertion
		2.1.2	DESTROY	fast removal thank to dual linked property
		2.1.3	SWAP	fast swaping , return pack of the next node, 
				usable as rotational loop by swapping sentinel
		2.1.4	FIND	loop entire list until find the given pack
				else return 0 , simple [item in list] fonction
		2.1.5	SORT	will sort list but it need a given comparator function
				while (void*) can be anything , u must specify it
	2.3 sequential CALLBACK
		2.3.0	STRUCT	use the node above and hook a new structure to it
		2.3.1	SCHEDULE	with a given function and interval it will put in todo list
		2.3.2	RESCHEDULE	you can change the interval associated with a task anytime
		2.3.3	CANCEL		you can cancel task , it will return a pointer that include both
		2.3.4	DO	with a given time , it will loop the list until it find one ready to run,
				and will return, next run it will start its scan after the last runned
				if looped entire list and still none to run , it return the difference
				from the nearest from now . I use it as sleep(void_do(timer()))
	3.1 BINARY TREE
		3.1.0	STRUCT use the same node as dual-linked list
		3.1.1	LEAF
		3.1.2	CUT
		3.1.3	ROTATE
		3.1.4	TRAVERSE
	FUTURE	
		balanced tree
		red-black tree
		A* pathfinding
			fast using LIST and given allocation function
			appliable to all struct using given neighbor and cost function
			as for 2d array or binary tree or neural net
*/		


//===========================================================================================
//===================================== 1.1 ALLOC =========================================
//===========================================================================================

// 1.1.0 STRUCT
#define NULE 0
#define MULE 8888

typedef struct void_memory{
	int id;
	int size;
	struct void_memory * last;
	struct void_memory * next;
} void_memory;

typedef struct void_yromem{
	void_memory * space;
	int id;
} void_yromem;
// 1.1.1 INIT
void_memory * void_seg (void * v_array, int v_size){
	if ((v_size == 0)||(v_array == 0))	{
		return 0;
	}
	void_memory * v_header = (void_memory*)v_array;
	void_memory * v_new = (void_memory*)(v_array + sizeof(void_memory));
	void_yromem * v_ender = (void_yromem*)(v_array + v_size - sizeof(void_yromem));
	v_header->id = MULE;
	v_header->size = v_size;
	v_header->last = v_new;
	v_header->next = v_new;
	v_new->id = MULE;
	v_new->size = v_size - sizeof(void_memory);
	v_new->last = v_header;
	v_new->next = v_header;
	v_ender->space = v_header;
	v_ender->id = MULE;
	return v_header;
}
// 1.1.2 ALLOC
void * void_alloc (void_memory * v_segment, int v_size){
	if ((v_size == 0)||(v_segment == 0))	{
		return 0;
	}
	if (v_size < sizeof(void_memory)+sizeof(void_yromem))	{
		v_size = sizeof(void_memory)+sizeof(void_yromem);
	}
	void_memory * v_pivot = v_segment->next;
	void_memory * v_enogh;
	while (v_pivot != v_segment)	{
		if (v_pivot->size - sizeof(void_memory) > v_size + sizeof(int))	{
			v_enogh = v_pivot;
			v_pivot = v_segment->last;
		}
		v_pivot = v_pivot->next;
	}
	if (v_enogh != 0){
		void_memory * v_mov = (void_memory*)((void*)v_enogh + v_size + sizeof(int));
		void_yromem * v_set = (void_yromem*)((void*)v_enogh + v_enogh->size - sizeof(void_yromem));
		void * v_new = (void*) v_enogh;
		v_mov->id = v_enogh->id;
		v_mov->size = v_enogh->size - v_size - sizeof(int);
		v_mov->last = v_enogh->last;
		v_mov->next = v_enogh->next;
		v_mov->last->next = v_mov;
		v_mov->next->last = v_mov;
		v_set->space = v_mov;
		*(int*)v_new = v_size;
		v_new = v_new +sizeof(int);
		*(int*)v_new = 0;
		*(int*)(v_new + sizeof(int)) = 0;
		*(int*)(v_new + (sizeof(int) * 2)) = 0;
		return v_new;
	}
	return NULE;
}
// 1.1.3 FREE
void void_free (void_memory * v_segment, void * v_offset){
	if ((v_segment == 0)||(v_offset == 0))	{
		return ;
	} 
	int v_size = *(int*)(v_offset - sizeof(int));
	void_memory * v_new = (void_memory*) (v_offset - sizeof(int));
	void_yromem * v_end = (void_yromem*) (v_offset + v_size - sizeof(void_yromem));
	v_new->id = MULE;
	v_new->size = v_size + sizeof(int);
	v_new->last = v_segment;
	v_new->next = v_segment->next;
	v_new->last->next = v_new;
	v_new->next->last = v_new;
	v_end->id = MULE;
	v_end->space = v_new;
	if ((*(int*)(v_offset + v_size)) == MULE )	{
		void_memory * v_forward = (void_memory*)(v_offset + v_size);
		void_yromem * v_foreend = (void_yromem*)((void*)v_forward + v_forward->size - sizeof(void_yromem));
		v_new->size = v_new->size + v_forward->size;
		v_forward->next->last = v_forward->last;
		v_forward->last->next = v_forward->next;
		v_foreend->space = v_new;
		v_end = v_foreend;
	}
	if ((*(int*)(v_offset - (sizeof(int)*2))) == MULE )	{
		void_yromem * v_backend = (void_yromem*)(v_offset - (sizeof(int)*2) - sizeof(void*));
		void_memory * v_bacward = v_backend->space;
		v_bacward->size = v_bacward->size + v_new->size;
		v_new->next->last = v_new->last;
		v_new->last->next = v_new->next;
		v_end->space = v_bacward;
		v_new = v_bacward;
	}
}
//===========================================================================================
//================================= 2.1 LIST ==============================================
//===========================================================================================
// 2.1.0 STRUCT
typedef struct void_node{
	void * pack;
	struct void_node * sentinel;
	struct void_node * last;
	struct void_node * next;
} void_node;
// 2.1.1 CREATE
void_node * void_create (void_node * v_src, void * v_pack, void * v_ptr){
	if (v_ptr == 0)	{
		return 0;
	}
	void_node * v_nud = (void_node*) v_ptr;
	v_nud->pack = v_pack;
	if (v_src != 0)	{
		v_nud->sentinel = v_src->sentinel;
		v_nud->last = v_src;
		v_nud->next = v_src->next;
		v_nud->last->next = v_nud;
		v_nud->next->last = v_nud;
	}
	else{
		v_nud->sentinel = v_nud;
		v_nud->last = v_nud;
		v_nud->next = v_nud;
	}
	return v_nud;
}
// 2.1.2 DESTROY
void * void_destroy (void_node * v_nud){
	void_node * v_src = v_nud->sentinel;
	if ((v_src == 0)||(v_nud == 0))	{
		return;
	}
	if (v_src == v_nud){
		//you shouldnt destroy sentinel if array is not empty
		if (v_src != v_src->next){
			return;
		}
	}
	v_nud->last->next = v_nud->next;
	v_nud->next->last = v_nud->last;
	v_nud->pack = 0;
	v_nud->last = 0;
	v_nud->next = 0;
	return (void*) v_nud;	//return ptr in case of alloc/free
}
// 2.1.3 SWAP
void * void_swap_next (void_node * v_src){
	void_node * v_nud = v_src->next;
	v_src->last->next = v_src->next;
	v_src->next->last = v_src->last;
	v_nud->next->last = v_src;
	v_src->next = v_nud->next;
	v_nud->next = v_src;
	v_src->last = v_nud;
	return v_nud->pack;
}

void * void_swap_last (void_node * v_src){
	void_node * v_nud = v_src->last;
	v_src->next->last = v_src->last;
	v_src->last->next = v_src->next;
	v_nud->last->next = v_src;
	v_src->last = v_nud->last;
	v_nud->last = v_src;
	v_src->next = v_nud;
	return v_nud->pack;
}
// 2.1.4 FIND
void_node * void_find (void_node * v_nud,void * v_pack){
	if (v_nud != 0){
		void_node * v_tmp = v_nud->next;
		while (v_tmp != v_nud){
			if (v_tmp->pack == v_pack){
				return v_tmp;
			} else {
				v_tmp = v_tmp->next;
			}
		}
	}
	return 0;
}
// 2.1.5 SORT
//pseudo code for ordered int list
int void_cmp_int (void * first, void * second){
	if (*((int*)first) > *((int*)second)) { return 0; }
	return 1;
}

void void_sort (void_node * v_nud,int (*v_func) (void*,void*)){
	if (v_nud != 0){
		void_node * v_tmp = v_nud->next;
		while (v_tmp != v_nud){
			if ((v_tmp->last==v_nud)||(v_func(v_tmp->pack,v_tmp->last->pack)==1)){
				v_tmp = v_tmp->next;
			} else {
				void_swap_last(v_tmp);
			}
		}
	}
}
//===========================================================================================
//=========================== 2.3 CALLBACK ================================================
//===========================================================================================
// 2.3.0 STRUCT
typedef struct void_agenda{
	void_node * node;		//the node that list it
	signed long int wait;		//interval between call
	void (*func)(void);		//function to call
	signed long int till;		//wait till to execute
	signed long int idle;		//time left before execute
	signed long int loop;		//value that end loop
} void_agenda;
// 2.3.1 SCHEDULE
void_node * void_schedule (void_node * v_sentinel, void (*v_func)(void), signed long int v_wait ,void * v_ptr){
	if (v_sentinel != v_sentinel->sentinel)	{
		//v_sentinel = v_sentinel->sentinel;
	}
	void_agenda * v_now = (void_agenda*) v_ptr;
	void_node * v_node_now = void_create(v_sentinel,v_now,v_ptr + sizeof(void_agenda));
	v_now->node = v_node_now;
	v_now->func = v_func;
	v_now->wait = v_wait;
	return v_node_now;
}
// 2.3.2 RESCHEDULE
void_node * void_reschedule (void_node * v_what, signed long int v_wait){
	void_node * v_sentinel = v_what->sentinel;
	if ((v_sentinel == 0) || (v_what == 0))	{
		return 0;
	}
	void_agenda * v_today = (void_agenda*)v_sentinel->pack;
	void_agenda * v_now = (void_agenda*)v_what->pack;
	signed long int v_till = v_now->till - v_now->wait + v_wait;
	signed long int v_idle = v_now->till - v_now->idle + v_till;
	v_now->wait = v_wait;
	v_now->idle = v_idle;
	v_now->till = v_till;
	return v_what;
}
// 2.3.3 CANCEL
void * void_cancel (void_node * v_node_now){
	void_node * v_node_today = v_node_now->sentinel;
	void_agenda * v_now = v_node_now->pack;
	v_now->wait = 0;
	v_now->func = 0;
	v_now->idle = 0;
	v_now->till = 0;
	v_now->loop = 0;
	v_now->node = 0;
	v_node_now = void_destroy (v_node_now);
	return ((void*)v_now);
}
// 2.3.4 DO
signed long int void_do (void_node * v_sentinel, signed long int v_time){
	if (v_sentinel != v_sentinel->sentinel)	{
		v_sentinel = v_sentinel->sentinel;
	}
	void_agenda * v_today = (void_agenda*)v_sentinel->pack;
	void_agenda * v_now;
	v_today->loop += 1;
	v_today->idle = v_today->wait;
	int v_yet = 0;
	while (v_yet != 1){
		v_now = void_swap_next(v_sentinel);
		if (v_now->loop == v_today->loop){
			v_yet = 1;
		}
		if (v_now->till == 0){
			v_now->till = v_time + v_now->wait;
		}
		if (v_now->till <= v_time){
			v_now->till = v_time + v_now->wait;
			v_now->idle = 0;
			v_now->func();
			v_yet = 1;
		}
		else{
			v_now->idle = v_now->till - v_time;
			v_now->loop = v_today->loop;
		}
		if (v_now->idle < v_today->idle){
			v_today->idle = v_now->idle;
		}
	}
	return v_today->idle;
}
//===========================================================================================
//================================== 3.1 BINARY TREE ======================================
//===========================================================================================
// 3.1.0 STRUCT see 2.1.0 while it use the same node
// instead there some reusable primitive
int v_fromdirection(void_node * v_leaf){
	if (v_leaf->sentinel->next == v_leaf){
		return 1;
	}
	return 0;
}
// 3.1.1 LEAF
void_node * void_leaf(void_node * v_root, void * v_pack, int v_direction, void * v_ptr){
	if (v_ptr == 0) {
		return 0;
	}
	void_node * v_leaf = (void_node*) v_ptr;
	v_leaf->pack = v_pack;
	v_leaf->last = 0;
	v_leaf->next = 0;
	if (v_root != 0) {
		//left ?
		if (v_direction == 0) {
			if (v_root->last != 0) {
				return v_ptr;
			}
			v_root->last = v_leaf;
		}
		//right ?
		if (v_direction == 1) {
			if (v_root->next != 0) {
				return v_ptr;
			}
			v_root->next = v_leaf;
		}
		v_leaf->sentinel = v_root;
	}
	else {
		v_leaf->sentinel = v_leaf;
	}
	return v_leaf;
}
// 3.1.2 CUT
void * void_cut(void_node * v_leaf){
	if ((v_leaf == 0) || (v_leaf->last != 0) || (v_leaf->next != 0)) {
		return 0;
	}
	if (v_fromdirection(v_leaf) == 1){
		v_leaf->sentinel->next = 0;
	} else {
		v_leaf->sentinel->last = 0;
	}
	v_leaf->pack = 0;	//hope u taken care of the package
	v_leaf->sentinel = 0;
	v_leaf->last = 0;
	v_leaf->next = 0;
	return (void*) v_leaf;
}
// 3.1.3 ROTATE
void void_rotate(void_node * v_leaf,int v_direction){
	if ((v_leaf != 0)&&(v_leaf->sentinel != v_leaf)){
		if ((v_direction == 0) && (v_leaf->next != 0)){
			v_leaf->next->sentinel = v_leaf->sentinel;
			if (v_fromdirection(v_leaf) == 0){
				v_leaf->sentinel->last = v_leaf->next;
			} else {
				v_leaf->sentinel->next = v_leaf->next;
			}
			v_leaf->sentinel = v_leaf->next;
			v_leaf->next = v_leaf->sentinel->last;
			v_leaf->sentinel->last = v_leaf;
			return;
		}
		if ((v_direction == 1) && (v_leaf->last != 0)){
			v_leaf->last->sentinel = v_leaf->sentinel;
			if (v_fromdirection(v_leaf) == 0){
				v_leaf->sentinel->last = v_leaf->last;
			} else {
				v_leaf->sentinel->next = v_leaf->last;
			}
			v_leaf->sentinel = v_leaf->last;
			v_leaf->last = v_leaf->sentinel->next;
			v_leaf->sentinel->next = v_leaf;
			return;
		}
	}
}
// 3.1.4 TRAVERSE
/*order : 0 = preorder , 1 = inorder , 2 = postorder , 4 = none ..... return lenght*/
int void_traverse(void_node * v_root,int v_order,void (*v_func)(void*)){
	int v_len = 1;
	if (v_root != 0) {
		if (v_order == 0){	
			v_func(v_root->pack);
		}
		if (v_root->last != 0){
			v_len += void_traverse(v_root->last,v_order,v_func);
		}
		if (v_order == 1){	
			v_func(v_root->pack);
		}
		if (v_root->next != 0){
			v_len += void_traverse(v_root->next,v_order,v_func);
		}
		if (v_order == 2){	
			v_func(v_root->pack);
		}
	}
	return v_len;
}
//3.1.5 SIBLING
void * void_sibling(void_node * v_node){
	if (v_node->sentinel == 0){
		return 0;
		if (v_fromdirection(v_node) == 0){
			if (v_node->sentinel->next == 0){
				return 0;
			} else {
				return v_node->sentinel->next->pack;
			}
		} else {
			if (v_node->sentinel->last == 0){
				return 0;
			} else {
				return v_node->sentinel->last->pack;
			}
		}
	}
	return 0;
}

void void_degenerate_tree (void_node * v_root){
	
}