Pannyx

devel

Request #09 


~/devel/sleek
% cda
~/devel/proto/aej
% pp tree_int.c tree_int.h
#define TREE_INT_C
#include <tree_int.h>

static void delete_node (tree_int_node_t *);
static void insert_left (tree_int_node_t, int_t, int_t *);
static void insert_right (tree_int_node_t, int_t, int_t *);
static void traverse_node (tree_int_node_t);

tree_int_t
new_int_tree (void) { tree_int_t t;
      if (( t = malloc(sizeof (tree_int_st))) == NULL) { ouch(); return NULL; }
      t->n_items = 0; t->root = NULL;
      return t; }

void
delete_int_tree (tree_int_t * t) { if (* t == NULL || (* t)->root == NULL) { ouch(); return; }
      delete_node(& (* t)->root);
      free(* t); * t = NULL; return; }

static void
delete_node (tree_int_node_t * v)
{

   if (!( (* v)->left == NULL)) { delete_node(& ((* v)->left)); }
   if (!( (* v)->right == NULL)) { delete_node(& ((* v)->right)); }
   free(* v); * v = NULL;
   return;

}

static int_t m_depth;
static bool_t pending;

void
int_tree_insert (tree_int_t t, int_t j)
{
   int_t l;

   if (t == NULL) { ouch(); return; }

   if (t->n_items == 0) {
      if (( t->root = malloc(sizeof (tree_int_node_st))) == NULL) { ouch(); return; }

      t->n_items = 1; t->root->item = j; t->root->left = NULL; t->root->right = NULL;
      return;
   }
   t->n_items += 1;
   m_depth = 0; l = 2; while (!( t->n_items < l)) { m_depth += 1; l *= 2; }
   pending = true;
   l = j;
   if (j < t->root->item) {
      insert_left(t->root, 0, & l); if (error_flag) { goto L1; }
// assert(! pending);
      return;
   }
   if (t->root->item < j) {
      insert_right(t->root, 0, & l); if (error_flag) { goto L1; }
// assert(! pending);
      return;
   }
   ouch();
L1:
   t->n_items -= 1;
   return;

}


static void
insert_left (tree_int_node_t v, int_t d, int_t * r)
{
   int_t j;

   j = * r;
   if (d < m_depth - 1) {
      if (j == v->item) {
         ouch(); pending = false; return;
      }
      if (v->item < j) {
         insert_right(v->right, d + 1, r); if (error_flag) { pending = false; return; }
         if (pending) {
            int_swap(r, & v->item);
// assert(* r < v->item);
         }
         else {
            return;
         }
      }
   // * r < v->item
      insert_left(v->left, d + 1, r); if (error_flag) { pending = false; return; }
      if (pending) {
         int_swap(& v->item, r);
// assert(v->item < * r);
         insert_left(v->right, d + 1, r); if (error_flag) { pending = false; return; }
// assert(v->item < * r);
      }
      return;
   }
   if (j < v->item) {
      if (v->left == NULL) {
         if (( v->left = malloc(sizeof (tree_int_node_st))) == NULL) { ouch();
   ↪  pending = false; return; }

         v->left->item = j; v->left->left = NULL; v->left->right = NULL;
         pending = false;
         return;
      }
      if (v->right == NULL) {
         if (j < v->left->item) {
            int_ror_3(& v->left->item, & v->item, r);
         }
         else {
            int_swap(& v->item, r);
         }
         if (( v->right = malloc(sizeof (tree_int_node_st))) == NULL) { ouch();
   ↪  pending = false; return; }

         v->right->item = * r; v->right->left = NULL; v->right->right = NULL;
// assert(v->left->item < v->item && v->item < v->right->item);
         pending = false;
         return;
      }
      if (j < v->left->item) {
         int_ror_4(& v->left->item, & v->item, & v->right->item, r);
// assert(v->left->item < v->item && v->item < v->right->item);
      }
      else {
         int_ror_3(& v->item, & v->right->item, r);
// assert(v->left->item < v->item && v->item < v->right->item);
      }
      return;
   }
   if (v->item < j) {
      if (v->right == NULL) {
         if (( v->right = malloc(sizeof (tree_int_node_st))) == NULL) { ouch();
   ↪  pending = false; return; }

         v->right->item = j; v->right->left = NULL; v->right->right = NULL;
         pending = false;
         return;
      }
      if (v->left == NULL) {
         if (v->right->item < j) {
            int_rol_3(r, & v->item, & v->right->item);
         }
         else {
            int_swap(r, & v->item);
         }
         if (( v->left = malloc(sizeof (tree_int_node_st))) == NULL) { ouch();
   ↪  pending = false; return; }

         v->left->item = * r; v->left->left = NULL; v->left->right = NULL;
// assert(v->left->item < v->item && v->item < v->right->item);
         pending = false;
         return;
      }
      if (j < v->right->item) {
         int_swap(& v->right->item, r);
      }
// assert(v->left->item < v->item && v->item < v->right->item && v->right->item <
   ↪ * r);
      return;
   }
   ouch(); pending = false;
   return;

}


static void
insert_right (tree_int_node_t v, int_t d, int_t * r)
{
   int_t j;

   j = * r;
   if (d < m_depth - 1) {
      if (j == v->item) {
         ouch(); pending = false; return;
      }
      if (j < v->item) {
         insert_left(v->left, d + 1, r); if (error_flag) { pending = false; return; }
         if (pending) {
            int_swap(& v->item, r);
// assert(v->item < * r);
         }
         else {
            return;
         }
      }
   // v->item < * r
      insert_right(v->right, d + 1, r); if (error_flag) { pending = false; return; }
      if (pending) {
         int_swap(r, & v->item);
// assert(* r < v->item);
         insert_right(v->left, d + 1, r); if (error_flag) { pending = false; return; }
// assert(* r < v->item);
      }
      return;
   }
   if (v->item < j) {
      if (v->right == NULL) {
         if (( v->right = malloc(sizeof (tree_int_node_st))) == NULL) { ouch();
   ↪  pending = false; return; }

         v->right->item = j; v->right->left = NULL; v->right->right = NULL;
         pending = false;
         return;
      }
      if (v->left == NULL) {
         if (v->right->item < j) {
            int_rol_3(r, & v->item, & v->right->item);
         }
         else {
            int_swap(r, & v->item);
         }
         if (( v->left = malloc(sizeof (tree_int_node_st))) == NULL) { ouch();
   ↪  pending = false; return; }

         v->left->item = * r; v->left->left = NULL; v->left->right = NULL;
         pending = false;
// assert(v->left->item < v->item && v->item < v->right->item);
         return;
      }
      if (v->right->item < j) {
         int_rol_4(r, & v->left->item, & v->item, & v->right->item);
// assert(v->left->item < v->item && v->item < v->right->item);
      }
      else {
         int_rol_3(r, & v->left->item, & v->item);
// assert(v->left->item < v->item && v->item < v->right->item);
      }
      return;
   }
   if (j < v->item) {
      if (v->left == NULL) {
         if (( v->left = malloc(sizeof (tree_int_node_st))) == NULL) { ouch();
   ↪  pending = false; return; }

         v->left->item = j; v->left->left = NULL; v->left->right = NULL;
         pending = false;
         return;
      }
      if (v->right == NULL) {
         if (j < v->left->item) {
            int_ror_3(& v->left->item, & v->item, r);
         }
         else {
            int_swap(& v->item, r);
         }
         if (( v->right = malloc(sizeof (tree_int_node_st))) == NULL) { ouch();
   ↪  pending = false; return; }

         v->right->item = * r; v->right->left = NULL; v->right->right = NULL;
         pending = false;
// assert(v->left->item < v->item && v->item < v->right->item);
         return;
      }
      if (v->left->item < j) {
         int_swap(r, & v->left->item);
      }
// assert(* r < v->left->item && v->left->item < v->item && v->item <
   ↪ v->right->item);
      return;
   }
   ouch(); pending = false;
   return;

}


static void (* traverse_proc) (int_t v);

void
int_tree_traverse (tree_int_t t, void (* proc) (int_t v)) { if (t == NULL || t->root == NULL) { ouch(); return; }
      traverse_proc = proc;
      traverse_node(t->root);
      return; }

static void
traverse_node (tree_int_node_t v)
{

   if (!( v->left == NULL)) { traverse_node(v->left); }
   traverse_proc(v->item);
   if (!( v->right == NULL)) { traverse_node(v->right); }
   return;

}

// tree_int.c
#ifndef TREE_INT_H
#define TREE_INT_H
#include <daejana.h>

struct tree_int_node_struct;
typedef struct tree_int_node_struct * tree_int_node_t;
typedef struct tree_int_node_struct {
   int_t item;
   tree_int_node_t left; tree_int_node_t right;
} tree_int_node_st;

typedef struct tree_int_struct {
   int_t n_items;
   tree_int_node_t root;
} tree_int_st, * tree_int_t;

#ifndef TREE_INT_C
#endif

tree_int_t new_int_tree (void);
void delete_int_tree (tree_int_t *);

void int_tree_insert (tree_int_t, int_t);

void int_tree_traverse (tree_int_t, void (*) (int_t v));

#endif
// tree_int.h
% cdm
~/devel/sleek
% pp tree_m.c
#include <shuffle.h>
#include <tree_int.h>

static int_t b;

void
print_int (int_t j) {
   // printf(" %2lld;", j);
      assert(!( j < b));
      b = j;
      return; }

int
main (int argc, char * argv [])
{
   int_t j; int_t k; int_t m; int_t n;
   tree_int_t t;
   int_t * v;

   error_flag = false;
   printf("\n");
   n = 31;
   open_shuffle(n, 500, & m);
   while (!( (v = take()) == NULL)) {
      if ( (t = new_int_tree()) == NULL) { goto L1; }

      b = -0x8000000000000000;
      printf("["); k = 0; while (k < m) { j = v[k] + 1; if (j < n) { printf(" %02lld,", j); int_tree_insert(t, j); if (error_flag) {
   ↪ delete_int_tree(& t); goto L1; } } k += 1; } printf(" ];\n");

   // printf("(");
      int_tree_traverse(t, print_int);
   // printf(" );\n\n");
      delete_int_tree(& t);
   }
L1:
   printf("\n");
   close_shuffle();
   if (error_flag) { exit(EXIT_FAILURE); }

   return EXIT_SUCCESS;

}

// tree_m.c
% cmr tree_m shuffle tree_int

[ 09, 01, 07, 04, 18, 05, 20, 06, 28, 24, 29, 10, 11, 03, 08, 30, 12, 26, 25, 21, 13, 27, 02, 16, 15, 14, 19, 17, 23, 22, ];
[ 05, 03, 20, 14, 24, 06, 12, 23, 28, 27, 09, 25, 01, 29, 11, 17, 30, 18, 04, 07, 10, 08, 02, 22, 16, 15, 26, 19, 21, 13, ];
[ 13, 11, 24, 07, 14, 15, 17, 22, 18, 16, 09, 19, 23, 21, 28, 27, 30, 29, 02, 03, 01, 06, 05, 12, 10, 25, 04, 08, 26, 20, ];
…
[ 04, 11, 14, 15, 12, 08, 10, 23, 13, 22, 17, 19, 24, 18, 28, 01, 20, 21, 02, 03, 29, 25, 27, 26, 05, 16, 30, 06, 09, 07, ];
[ 10, 11, 27, 05, 13, 02, 21, 04, 20, 19, 22, 18, 16, 08, 07, 06, 03, 28, 24, 14, 23, 09, 17, 01, 12, 25, 15, 29, 26, 30, ];
[ 28, 29, 22, 13, 21, 11, 15, 30, 05, 02, 17, 04, 12, 26, 03, 06, 07, 19, 14, 18, 20, 27, 01, 24, 10, 16, 09, 25, 08, 23, ];

%