#13

// itbl.h --- int table api.
struct itbl;
typedef struct itbl *itblp;
itblp itbl_new();                     // allocate new tbl
void itbl_put(itblp t, int k, int v); // store value
int itbl_get(itblp t, int k);         // obtain value
//void itbl_delete(itblp t, int k);     // delete key/value
void itbl_pr(itblp t);                // print contents

// bstree.c --- itbl impl with binary search tree.
#include <stdlib.h>
#include <stdio.h>
#include "itbl.h"
typedef struct ent *entp;
struct ent { int key, val; entp left, right; };
struct itbl { entp root; };
itblp itbl_new() {
  itblp p = (itblp)malloc(sizeof(struct itbl));
  p->root = NULL; return p;
}
static int get(entp p, int k) {
  if(p == NULL) { return -1; }
  if(k == p->key) { return p->val; }
  return get((k < p->key) ? p->left : p->right, k);
}
int itbl_get(itblp p, int k) { return get(p->root, k); }
static void put(entp *p, int k, int v) {
  if(*p == NULL) {
    entp q = *p = (entp)malloc(sizeof(struct ent));
    q->left = q->right = NULL; q->key = k; q->val = v;
  } else if(k == (*p)->key) {
    (*p)->val = v;
  } else {
    put((k < (*p)->key) ? &((*p)->left) : &((*p)->right), k, v);
  }
}
void itbl_put(itblp p, int k, int v) { put(&(p->root), k, v); }
static void pr(entp p) {
  if(p->left != NULL) { printf("("); pr(p->left); printf(") "); }
  printf("%d:%d", p->key, p->val);
  if(p->right != NULL) { printf(" ("); pr(p->right); printf(")"); }
}
void itbl_pr(itblp p) {
  if(p->root != NULL) { printf("("); pr(p->root); printf(")\n"); }
}

// treedemo.c --- demonstration of bstree operation
#include <stdlib.h>
#include <stdio.h>
#include "itbl.h"

int main(int argc, char *argv[]) {
  int n = atoi(argv[1]);
  itblp p = itbl_new();
  for(int i = 1; i < argc; ++i) {
    int v = atoi(argv[i]);
    if(v >= 0) { itbl_put(p, v, i); }
//  else       { itbl_delete(p, -v); }
    itbl_pr(p);
  }
  return 0;
}

// btree23.c --- itbl impl with 2-3 B-tree.
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include "itbl.h"
#define D 1
typedef struct ent *entp;
struct ent {
  bool leaf;
  int nkey, key[D*2+1], val[D*2+1];
  entp child[D*2+1];
};
struct itbl { entp root; };
itblp itbl_new() {
  itblp p = (itblp)malloc(sizeof(struct itbl));
  p->root = NULL; return p;
}
static int get(entp p, int k) {
  int i;
  for(i = 0; k >= p->key[i] && i < p->nkey; ++i) {
    if(k == p->key[i]) { return p->val[i]; }
  }
  return (p->leaf) ? -1 : get(p->child[i], k);
}
int itbl_get(itblp p, int k) {
  return (p->root == NULL) ? -1 : get(p->root, k);
}
static entp newent2(int k, int v, entp l, entp r) {
  entp p = (entp)malloc(sizeof(struct ent));
  p->leaf = false; p->nkey = 1; p->key[0] = k; p->val[0] = v;
  p->child[0] = l; p->child[1] = r; return p;
}
static entp newent(int k, int v) {
  entp q = newent2(k, v, NULL, NULL); q->leaf = true; return q;
}
static entp cpent2(entp p, int i, entp l, entp r) {
  entp q = newent2(p->key[i], p->val[i], l, r); return q;
}
static entp cpent(entp p, int i) {
  entp q = cpent2(p, i, NULL, NULL); q->leaf = true; return q;
}
static void shift(entp p, int i) {
  for(int j = ++p->nkey; j > i; --j) {
    p->key[j] = p->key[j-1]; p->val[j] = p->val[j-1];
    p->child[j] = p->child[j-1];
  }
}
static entp pleaf(entp p, int i, int k, int v) {
  if(p->nkey < D*2) { 
    shift(p, i); p->key[i] = k; p->val[i] = v; return NULL;
  } else if(i == 0) {
    return newent2(p->key[0], p->val[0], newent(k, v), cpent(p, 1));
  } else if(i == 1) {
    return newent2(k, v, cpent(p, 0), cpent(p, 1));
  } else {
    return newent2(p->key[1], p->val[1], cpent(p, 0), newent(k, v));
  }
}
static entp pnode(entp p, entp q, int i) {
  if(q == NULL) { return NULL; }
  entp r = NULL;
  if(p->nkey < D*2) {
    shift(p, i); p->key[i] = q->key[0]; p->val[i] = q->val[0];
    p->child[i] = q->child[0]; p->child[i+1] = q->child[1];
  } else if(i == 0) {
    r = newent2(p->key[0], p->val[0],
                newent2(q->key[0], q->val[0], q->child[0], q->child[1]),
                cpent2(p, 1, p->child[1], p->child[2]));
  } else if(i == 1) {
    r = newent2(q->key[0], q->val[0],
                cpent2(p, 0, p->child[0], q->child[0]),
                cpent2(p, 1, q->child[1], p->child[2]));
  } else {
    r = newent2(p->key[1], p->val[1],
                cpent2(p, 0, p->child[0], p->child[1]),
                newent2(q->key[0], q->val[0], q->child[0], q->child[1]));
  }
  free(q); return r;
}
static entp put(entp p, int k, int v) {
  int i;
  for(i = 0; k >= p->key[i] && i < p->nkey; ++i) {
    if(k == p->key[i]) { p->val[i] = v; return NULL; }
  }
  return p->leaf ? pleaf(p, i, k, v) : pnode(p, put(p->child[i], k, v), i);
}
void itbl_put(itblp p, int k, int v) {
  int k1, v1;
  if(p->root == NULL) { p->root = newent(k, v); return; }
  entp r = put(p->root, k, v);
  if(r != NULL) { free(p->root); p->root = r; }
}
static void pr(entp p) {
  int i;
  if(p == NULL) { printf("NULL"); return; }
  if(p->leaf) {
    if(p->nkey > 0) { printf("%d:%d", p->key[0], p->val[0]); }
    for(i = 1; i < p->nkey; ++i) {
      printf(" %d:%d", p->key[i], p->val[i]);
    }
  } else {
    for(i = 0; i < p->nkey; ++i) {
      printf("("); pr(p->child[i]);
      printf(") %d:%d ", p->key[i], p->val[i]);
    }
    printf("("); pr(p->child[i]); printf(")");
  }
}
void itbl_pr(itblp p) { printf("("); pr(p->root); printf(")\n"); }