/*++++++++++++++
.IDENTIFICATION tree.c
.LANGUAGE       C
.AUTHOR         Francois Ochsenbein [CDS]
.ENVIRONMENT    Btrees
.KEYWORDS       CDS Catalogue Server
.VERSION  1.0   07-Dec-2002: Tests for B-tree
.COMMENTS       Btrees
---------------*/

#include <stdio.h>
#include <stdlib.h>	/* Malloc   */
#include <string.h>
#include <ctype.h>
#include <math.h>

#define ITEMS(a)	(sizeof(a)/sizeof(a[0]))
#define MIN(a,b)	((a)<(b) ? (a) : (b))
#define MAX(a,b)	((a)>(b) ? (a) : (b))

typedef int RECORD;
/* Linked records, to sort them...	*/
typedef struct linked_RECORD {
    struct linked_RECORD *lt ;
    struct linked_RECORD *ge ;
    RECORD rec ;
} LRECORD ;
static RECORD rec0;		/* NULL Record	*/
static int compare_calls;
static int tree_depth;
static int mrec = 20 ;
static int irec, truncated ;
static int input_id ;		/* ID(1) Zone (2)  */
static char whole_usnob ;	/* -whole option   */
LRECORD *last, *arec, *root, *just_added;

/*  Definitions related to Center of Field */
static double radius = 0 ;
static double boxy[2] ;
static int (*digest_routine)() ;
static double localR[3][3] ;	/* Matrix, [0] = dir.cos. of center */
static double du2max = -1 ;
static char optE;

/* Other options */
static int opted = 'n';	/* 'o' ==> all */


/*==================================================================
		Comparison routines
 *==================================================================*/

static int compare(RECORD *a, RECORD *b)
/*++++++++++++++++
.PURPOSE  Compare two records according to the sort options
.RETURNS  Difference (a-b)
-----------------*/
{
    compare_calls++;
    return(*a - *b);
}

static void print_nodes(LRECORD *node)
/*++++++++++++++++
.PURPOSE  Print all nodes in order
.RETURNS  ---
.REMARKS  Recursivity = simplicity !!
-----------------*/
{
  static int depth = 0;
    if (node->lt) depth++, print_nodes(node->lt), depth--;
    printf("%10d:%-5d", node->rec, depth);
    if (node->ge) depth++, print_nodes(node->ge), depth--;
    /* if (depth==0) putchar('\n'); */
}

/*==================================================================
		Sorting the Records
 *==================================================================*/

static int add_rec(RECORD *new)
/*++++++++++++++++
.PURPOSE  Add a new record, link it.
.RETURNS  0 (not kept) / 1
-----------------*/
{
  LRECORD *node, *prev, *n;
  int diff, comp1, depth;

    comp1 = compare_calls; 

    /* (0) Check if the new record has any use... */
    if ((irec == mrec) && last) {
	diff = compare(new, &(last->rec));
	if (diff >= 0) { truncated++; return(0); }
    }

    /* (1) Find where in the list we've to insert the new record */
    node = root;
    prev = (LRECORD *)0;
    depth = 0;
    while(node) {
	diff = compare(new, &(node->rec));
	/* if (diff == 0) break; */
	prev = node;
	node = diff < 0 ? node->lt : node->ge ;
	depth++;
    }
    if (depth > tree_depth) tree_depth = depth;

    /* (2) If max attained, put the new in place of last */
    if (irec == mrec) {
	if(opted=='o') { putchar('\n'); print_nodes(root); putchar('\n'); }
	truncated++ ;
	for (n=(LRECORD *)0, last=root; last->ge; last=last->ge) n = last; 
	node = last ;	/* Where to store the new record */
	if (!n) {	/* Happens when root == last !   */
	    root = root->lt;
	    for (n=root; n->ge; n=n->ge) ;
	    node->lt = (LRECORD *)0;
	}
	last = n;	/* What's now the LAST record... */
	last->ge = node->lt;
	while(last->ge) last = last->ge;
    }
    else node = arec + irec++ ;

    /* (3) Insert the new record, and set the links */
    *(&(node->rec)) = *new ;
    node->lt = node->ge = (LRECORD *)0;
    if (prev) {
	if (diff < 0) prev->lt = node;
	else node->ge = prev->ge, prev->ge = node;
    }
    else node->ge = root, root = node;
    
#if 1
    printf("\n....Adding#%d: comparisons=%d ", 
	irec, compare_calls-comp1);
#endif

    return(1) ;
}

/*==================================================================
		Main Program
 *==================================================================*/

main (argc, argv) int argc; char **argv;
{
  RECORD rec;
  int n;

    arec = (LRECORD *)malloc(mrec*sizeof(LRECORD));

    while (1) {
	printf("....Random list: "); n = getchar();
	if (n<0) break;
        irec = 0; compare_calls = 0; root = (LRECORD *)0; tree_depth = 0;
        for (n=0; n<100; n++){ rec = rand()%100; add_rec(&rec); }
        printf("%d total comparisons, depth=%d", compare_calls, tree_depth); 
	n = getchar(); 
	print_nodes(root); putchar('\n');
    }

    /* Generate one up, one down, random */
    irec = 0; compare_calls = 0; root = (LRECORD *)0; tree_depth = 0;
    printf("----Adding  ascending list: ");  n = getchar();
    for (n=0; n<1000; n++){ rec = n; add_rec(&rec); }
    printf("%d total comparisons, depth=%d", compare_calls, tree_depth); 
    n = getchar(); 
    print_nodes(root); putchar('\n');

    irec = 0; compare_calls = 0; root = (LRECORD *)0; tree_depth = 0;
    printf("----Adding descending list: ");  n = getchar();
    for (n=30; --n>=0 ;){ rec = n; add_rec(&rec); }
    printf("%d total comparisons, depth=%d", compare_calls, tree_depth); 
    n = getchar(); 
    print_nodes(root); putchar('\n');

    exit(0);
}