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

#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 *eq ;
    struct linked_RECORD *gt ;
    RECORD rec ;
} LRECORD ;
static int compare_calls;
static int tree_depth;
static int mrec = 20 ;
static int irec, truncated ;
static LRECORD *last, *arec, *root;

/*  Definitions related to Center of Field */
static int (*digest_routine)() ;

/* Other options */
static int opted = 'o';	/* '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;
  LRECORD *n;
    if (node->lt) depth++, print_nodes(node->lt), depth--;
    for (n=node; n; n=n->eq)
        printf("%10d:%-5d", n->rec, depth);
    if (node->gt) depth++, print_nodes(node->gt), 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, *prev1, *n;
  int diff, comp1, depth;

    comp1 = compare_calls; 

    /* (0) Check if the new record has any use... */
    n = (LRECORD *)0;		/* n -> last */
    if (irec == mrec) {
	if (!last) for (last=root; last->gt; last=last->gt) n = 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 = prev1 = (LRECORD *)0;
    depth = 0;
    while(node) {
	diff = compare(new, &(node->rec));
	prev1 = prev; prev = node;
	if (diff == 0) break;
	node = diff < 0 ? node->lt : node->gt ;
	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') { 
	    printf(" new=%d\n", *new); print_nodes(root); putchar('\n'); 
	}
	truncated++ ;
	node = last ;	/* Where to store new record 	*/
	if (last->eq) {	/* Several last records...	*/
	    node = last->eq;
	    last->eq = node->eq ;
	}
	else {		/* Set n->gt gives last */
	    if (!n) for (last=root; last->gt; last=last->gt) n = last;
	    if (!n) {	/* Happens when root == last !	*/
	        root = root->lt;
		last = root;
	    }
	    else {
		last = n;
		last->gt = node->lt;
	    }
	}
	while(last->gt) last = last->gt;
    }
    else node = arec + irec++ ;

    /* (3) Insert the new record, and set the links */
    *(&(node->rec)) = *new ;
    node->lt = node->gt = node->eq = (LRECORD *)0;
    if (!prev) root = node;
    else {
        if (diff < 0) 
	    prev->lt = node;
        else if (diff > 0) {	/* I may have changed the last */
	    prev->gt = node;
	    if (last) while(last->gt) last = last->gt;
	}
        else { node->eq = prev->eq; prev->eq = node; }
    }
    
#if 1
    printf("\n....Added#%d = %d: comparisons=%d ", 
	irec, *new, compare_calls-comp1);
    putchar('\n'); print_nodes(root); putchar('\n');
#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 = last = (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 = last = (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 = last = (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);
}