/*
 * Copyright (c) 2007 Vojtech Mencl
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * - Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 * - Redistributions in binary form must reproduce the above copyright
 *   notice, this list of conditions and the following disclaimer in the
 *   documentation and/or other materials provided with the distribution.
 * - The name of the author may not be used to endorse or promote products
 *   derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#include <test.h>
#include <print.h>
#include <adt/extavl.h>
#include <debug.h>

#include <panic.h>


#define NODE_COUNT 100

/*
 * wrapper structure with a pointer to extended avl tree root
 */
static extavltree_t exttree;

/*
 * extavltree nodes in array for faster allocating
 */
static extavltree_node_t extavltree_nodes[NODE_COUNT];

/* 
 * head of free nodes' list:
 */
static extavltree_node_t *first_free_node = NULL;



static int exttree_test_height(extavltree_node_t *node,bool timeout);
static extavltree_node_t *exttree_test_parents(extavltree_node_t *node);
static void print_exttree_structure_flat (extavltree_node_t *node, int level);
static bool exttree_test_link(int node_count);
static void print_exttree_link(void);
static extavltree_node_t *alloc_extavltree_node(void);



//vraci hloubku stromu
static int exttree_test_height(extavltree_node_t *node,bool timeout)
{
	int h1, h2;

	if (!node) return -1;

	h1 = exttree_test_height(node->lft,timeout) + 1;
	if (!timeout && node->lft_height != h1) {
		printf("Bad height: %d of LEFT subtree in node: %d with address: %p\n",h1,node->key,node);
	}
	h2 = exttree_test_height(node->rgt,0) + 1;
	if (node->rgt_height != h2) {
		printf("Bad height: %d of RIGHT subtree in node: %d with address: %p\n",h2,node->key,node);
	}
	if (!timeout && (((h1-h2)>0?h1-h2:h2-h1) > 1)) {
		printf("Bad height: error in definition of avltree: %d with address: %p\n",node->key,node);
	}

	return (node->lft_height > node->rgt_height? node->lft_height: node->rgt_height);
}


/** Tests par atribute of every tree node
 *
 */
static extavltree_node_t *exttree_test_parents(extavltree_node_t *node)
{
	extavltree_node_t *tmp;
	
	if (!node) return NULL;

	if (node->lft) {
		tmp = exttree_test_parents(node->lft);
		if (tmp != node) {
			printf("Bad parent pointer at node with key: %d, address: %p\n",tmp->key,node->lft);
		}
	}
	if (node->rgt) {
		tmp = exttree_test_parents(node->rgt);
		if (tmp != node) {
			printf("Bad parent pointer at node with key: %d, address: %p\n",tmp->key,node->rgt);
		}
	}
	return node->par;
}

/** Checks list of nodes
 *
 */
static bool exttree_test_link(int node_count)
{
	extavltree_node_t *node;
	int i;
	bool test_link = true;

	for (i = 0,node = exttree.head.next; node != &(exttree.head); i++,node = node->next) {
		if ((node->next != &(exttree.head)) && (node->key > node->next->key)) {
			printf("\nList is not sorted (forward direction) at key: %d\n",node->key);
			test_link = false;
		}
	}
	if (i != node_count) {
		printf("\nBad node count!!! Counted: %d, right number: %d", i, node_count);
		test_link = false;
	}
	for (i = 0,node = exttree.head.prev; node != &(exttree.head); i++,node = node->prev) {
		if ((node->prev != &(exttree.head)) && (node->key < node->prev->key)) {
			printf("\nList is not sorted (backward direction) at key: %d\n",node->key);
			test_link = false;
		}
	}
	if (i != node_count) {
		printf("\nBad node count!!! Counted: %d, right number: %d", i, node_count);
		test_link = false;
	}
	return test_link;
}

/** Prints the structure of node, which is level levels from the top of the tree. 
 * 
 */
static void print_exttree_structure_flat (extavltree_node_t *node, int level)
{
	extavltree_node_t *tmp;
	int i;

	if (level > 16)
	{
		printf ("[...]");
		return;
	}

	if (node == NULL)
		return;
	
	for (tmp = node,i = 0; tmp->key == node->key; tmp = tmp->next,i++)
		;

	printf ("%d[%d,%d,(%d)]", node->key,node->lft_height,node->rgt_height,i);
	if (node->lft != NULL || node->rgt != NULL)
	{
		printf("(");

		print_exttree_structure_flat (node->lft, level + 1);
		if (node->rgt != NULL)
		{
			printf(",");
			print_exttree_structure_flat (node->rgt, level + 1);
		}

		printf(")");
	}
}

/** Prints list of nodes
 *
 */
static void print_exttree_link(void)
{
	extavltree_node_t *node;
	printf("\n");
	for (node = exttree.head.next; node != &(exttree.head); node = node->next) {
		printf(" %d,",node->key);
	}
	for (node = exttree.head.prev; node != &(exttree.head); node = node->prev) {
		printf(" %d,",node->key);
	}
}

//****************************************************************
static void alloc_extavltree_node_prepare(void)
{
	int i;

	for (i = 0; i < NODE_COUNT - 1; i++) {
		extavltree_nodes[i].next = &(extavltree_nodes[i+1]);
	}
	/*
	 * Node keys which will be used for insertion. Up to NODE_COUNT size of array.
	 */

	// First tree node and same key
	extavltree_nodes[0].key = 60;
	extavltree_nodes[1].key = 60;
	extavltree_nodes[2].key = 60;
	//LL rotation
	extavltree_nodes[3].key = 50;
	extavltree_nodes[4].key = 40;
	extavltree_nodes[5].key = 30;
	//LR rotation
	extavltree_nodes[6].key = 20;
	extavltree_nodes[7].key = 20;
	extavltree_nodes[8].key = 25;
	extavltree_nodes[9].key = 25;
	//LL rotation in lower floor
	extavltree_nodes[10].key = 35;
	//RR rotation
	extavltree_nodes[11].key = 70;
	extavltree_nodes[12].key = 80;
	//RL rotation
	extavltree_nodes[13].key = 90;
	extavltree_nodes[14].key = 85;
	extavltree_nodes[15].key = 100;
	extavltree_nodes[16].key = 200;
	extavltree_nodes[17].key = 300;
	extavltree_nodes[18].key = 400;
	extavltree_nodes[19].key = 500;
	extavltree_nodes[20].key = 600;

	for (i = 21; i < NODE_COUNT; i++)
		extavltree_nodes[i].key = i * 3;
	
	extavltree_nodes[i].next = NULL;
	first_free_node = &(extavltree_nodes[0]);
}

static extavltree_node_t *alloc_extavltree_node(void)
{
	extavltree_node_t *node;

	node = first_free_node;
	first_free_node = first_free_node->next;

	return node;
}
//****************************************************************

static void test_exttree_insert(extavltree_t *tree, unsigned int node_count, int quiet) 
{
	unsigned int i;
	extavltree_node_t *newnode;

	/*
	 * Initialize tree before using.
	 */
	extavltree_create(tree);
	
	if (!quiet) printf("\nInserting %d nodes ...\n", node_count);

	for (i = 0; i < node_count; i++) {
		newnode = alloc_extavltree_node();
		//if (!quiet) printf("[[[%d]]]\n",newnode->key);
		
		extavltree_insert(tree, newnode);
		if (!quiet) {
			if (!exttree_test_link(i+1)) {
				print_exttree_link();
				printf("\n");
			}
			exttree_test_parents(tree->root);
			exttree_test_height(tree->root,1);
		}
	}
		
	if (!quiet) printf("Inserting was finished\n");
}

/*
static extavltree_node_t *exttree_random_delete_node(extavltree_t *tree, int node_count, int r, bool quiet)
{
	extavltree_node_t *delnode;
	int i;

	for (i = 0,delnode = tree->head.next; i < (r-1); i++)
		delnode = delnode->next;
	
	if (delnode == &tree->head) {
		if (!quiet) printf("Try to delete head! Node count: %d, number of deleted node: %d\n",node_count,r);
		return NULL;
	}

	extavltree_delete(tree, delnode);

	return delnode;
}
*/

static void test_exttree_delete(extavltree_t *tree, int node_count, int node_position, bool quiet) 
{
	extavltree_node_t *delnode;
	unsigned int i;
	
	//aktualni pocet tiku:
	if (!quiet) printf("Deleting tree...\n");

	switch(node_position) {
		case 0: //mazani vzdy korene
			if (!quiet) printf("\nDelete root nodes\n");
			i = node_count - 1;
			while(tree->root != NULL) {
				delnode = tree->root;
				extavltree_delete(tree,delnode);
				if (!quiet) {
					if (!exttree_test_link(i)) {
						print_exttree_link();
						printf("\n");
					}
					exttree_test_parents(tree->root);
					exttree_test_height(tree->root,1);
				}
				i--;
			} 
			
			break;
		case 1:
			if (!quiet) printf("\nDelete nodes according to their time of origin\n");
			for (i = 0; i < node_count; i++) {
				extavltree_delete(tree,&(extavltree_nodes[i]));
				if (!quiet) {
					if (!exttree_test_link(node_count-i-1)) {
						print_exttree_link();
						printf("\n");
					}
					exttree_test_parents(tree->root);
					exttree_test_height(tree->root,1);
				}
			}

			break;	
	}
	
	if (!quiet) printf("Deletion was finished\n");
}

static void timeout_exttree(extavltree_t *tree, int node_count, bool quiet)
{
	int i = node_count - 1;
	
	if (!quiet) printf("\nTimeout tree ...\n");
	
	while(tree->head.next != &(tree->head)) {
		extavltree_delete_min(tree);
		if (!quiet) {
			if (!exttree_test_link(i)) {
				print_exttree_link();
				printf("\n");
			}
			exttree_test_parents(tree->root);
			exttree_test_height(tree->root,1);
		}
		i--;
	}

	if (!quiet && (i != -1)) printf("Bad node count. Some nodes have been lost!\n");

	if (!quiet) printf("Timeout tree finished\n");
}

/*
void timeout_exttree_run(extavltree_t *tree, int operation_count, int verbal) 
{
	int i;
	extavltree_node_t *node;
	int r;
	int count;
	
	//inicializace stromu:
	extavltree_create(tree);
	
	for(i = 0, count = 0; i < operation_count; i++) {
		if (tree->count && ((rand() % NODE_COUNT) <= tree->count)) {
			if ((r = rand()) % DELETE_PROB == 1) { //mazu nahodne
				node = exttree_random_delete_node(tree,(r % tree->count));
				//printf("DELETE key: %d, number: %d,address: %p\n",node->key,r % (tree->count+1),node);
				node->next = first_free_node;
				first_free_node = node;
			} else {
				node = tree->head.next;
				extavltree_delete_min(tree);
				//printf("TIMEOUT key: %d, address: %p\n",node->key,node);
				node->next = first_free_node;
				first_free_node = node;
			}
        	} else {
            		node = alloc_extavltree_node_random();
			//printf("INSERT key: %d, address: %p\n",node->key + tree->basetime,node);
			extavltree_insert(tree, node);
        	}
		//test_exttree_height(tree->root,1);
		//exttree_test_parents(tree->root);		
		//print_exttree_link(tree->count);
		//print_exttree_structure_flat(tree->root,0); putchar('\n'); putchar('\n');
	}
}
*/

char * test_extavltree1(bool quiet)
{
	alloc_extavltree_node_prepare();
	test_exttree_insert(&exttree, NODE_COUNT, quiet);
	test_exttree_delete(&exttree, NODE_COUNT, 0, quiet);

	alloc_extavltree_node_prepare();
	test_exttree_insert(&exttree, NODE_COUNT, quiet);
	test_exttree_delete(&exttree, NODE_COUNT, 1, quiet);

	alloc_extavltree_node_prepare();
	test_exttree_insert(&exttree, NODE_COUNT, quiet);
	timeout_exttree(&exttree, NODE_COUNT, quiet);

	return NULL;
}