/**
  * Copyright (c): Uwe Schmidt, FH Wedel
  *
  * You may study, modify and distribute this source code
  * FOR NON-COMMERCIAL PURPOSES ONLY.
  * This copyright message has to remain unchanged.
  *
  * Note that this document is provided 'as is',
  * WITHOUT WARRANTY of any kind either expressed or implied.
  */

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#include "IntMap.h"

static struct Node emptyNode = {Empty};

Tree empty = & emptyNode;

/* selector macros */

#define kind(t)    ((t)->Kind)
#define isEmpty(t) (kind(t) == Empty)
#define isLeaf(t)  (kind(t) == Leaf)
#define isFork(t)  (kind(t) == Fork)

#define key(t)     ((t)->data.leaf.k)
#define attr(t)    ((t)->data.leaf.a)
#define prefix(t)  ((t)->data.fork.p)
#define mask(t)    ((t)->data.fork.m)
#define left(t)    ((t)->data.fork.l)
#define right(t)   ((t)->data.fork.r)

/*----------------------------------------*/
/* constructors */

static
Tree mkLeaf(Key k, Attr a) {
  Tree res = malloc(sizeof(* res));
  if (! res) {
    perror("mkLeaf: heap overflow");
    exit(1);
  }
  kind(res) = Leaf;
  key (res) = k;
  attr(res) = a;

  trace(showTree0("mkLeaf", res));

  return res;
}

static
Tree mkFork(Prefix p, Mask m, Tree l, Tree r) {
  Tree res = malloc(sizeof(* res));
  if (! res) {
    perror("mkFork: heap overflow");
    exit(1);
  }
  kind  (res) = Fork;
  prefix(res) = p;
  mask  (res) = m;
  left  (res) = l;
  right (res) = r;

  trace(showTree0("mkFork", res));

  return res;
}

/*----------------------------------------------*/
/* destructors                                  */
/* helper for profiling and counting free calls */

static
void freeFork(Tree t) {
  assert(isFork(t));
  free(t);
}

static
void freeLeaf(Tree t) {
  assert(isLeaf(t));
  free(t);
}

/*----------------------------------------*/

int isInMap(Key k, Tree t, Attr * res) {
  switch ( kind(t) ) {
  case Empty:
    return 0;

  case Leaf:
    { int found = key(t) == k;
      if (found)
	*res = attr(t);
      return found;
    }

  case Fork:
    { Tree t1;
      if (! matchPrefix(k, prefix(t), mask(t)))
	return 0;

      t1 = (k & mask(t)) ? right(t) : left(t);

      return isInMap(k, t1, res);
    }

  default:
    assert(0);
    return 0;
  }
}

/* join 2 none empty trees together */
/* intervall of elements don't overlap */

static
Tree join(Prefix p1, Tree t1,
	  Prefix p2, Tree t2) {

  Mask   m = commonPrefixMask(p1, p2);
  Prefix p = getPrefix(p1, m);

  trace(showTree0("join t1", t1));
  trace(showTree0("join t2", t2));

  if (p1 & m) {
    return
      mkFork(p, m, t2, t1);
  } else {
    return
      mkFork(p, m, t1, t2);
  }
}

Tree insert(Key k, Attr a, Tree t) {
  trace(printf("insert %ld %ld\n", k, a));
  trace(showTree0("insert", t));

  switch ( kind(t) ) {
  case Empty:
    return
      mkLeaf(k, a);

  case Leaf:
    { Key k1 = key(t);

      if (k == k1) {
	/* destructive update */
	attr(t) = a;
	return t;
      } else {
	return
	  join(k,  mkLeaf(k, a),
	       k1, t);
      }
    }

  case Fork:
    { Prefix p = prefix(t);
      Mask m   = mask(t);

      if (! matchPrefix(k, p, m)) {
	return join(k, mkLeaf(k, a),
		    p, t);
      }

      /* destructive updates */
      if (k & m) {
	right(t) = insert(k, a, right(t));
      } else {
	left(t)  = insert(k, a,  left(t));
      }
      trace(showTree0("insert: Fork return", t));
      return t;
    }

  default:
    assert(0);
    return 0;
  }
}

Tree remov(Key k, Tree t) {
  switch ( kind(t) ) {
  case Empty:
    return t;

  case Leaf:
    { Key k1 = key(t);

      if (k == k1) {
	freeLeaf(t);
	return empty;
      } else {
	return t;
      }
    }

  case Fork:
    { Prefix p = prefix(t);
      Mask   m = mask(t);

      if (! matchPrefix(k, p, m)) {
	/* entry not there */

	return t;
      } else {
	if (k & m) {
	  /* remove entry in right subtree */

	  Tree r = remov(k, right(t));
	  if (isEmpty(r)) {
	    Tree res = left(t);
	    freeFork(t);
	    return res;
	  } else {
	    right(t) = r;
	    return t;
	  }
	} else {
	  /* remove entry in left subtree */

	  Tree l = remov(k, left(t));
	  if (isEmpty(l)) {
	    Tree res = right(t);
	    freeFork(t);
	    return res;
	  } else {
	    left(t) = l;
	    return t;
	  }
	}
	return t;
      }
    }

  default:
    assert(0);
    return 0;
  }
}


void foreach(ProcessKeyAttr p, Tree t) {
 switch ( kind(t) ) {
 case Empty:
   break;
 case Leaf:
   p(key(t), attr(t));
   break;
 case Fork:
   foreach(p, left(t));
   foreach(p, right(t));
   break;
 }
}

static
void indent(int level) {
  int i;
  for (i = 0; i < level; ++i)
    printf(" ");
}

static
void showTree1(int level, Tree t) {
  indent(level);
  switch ( kind(t) ) {
  case Empty:
    printf("Empty\n");
    break;
  case Leaf:
    printf("\"");
    printBitString(key(t));
    printf("\"\t%ld\n", attr(t));
    break;
  case Fork:
    /* printf("%lu,%lu,",prefix(t),mask(t)); */
    printf("\"");
    printPrefix(prefix(t), mask(t));
    printf("\"\n");
    showTree1(level + 2,  left(t));
    showTree1(level + 2, right(t));
    break;
  }
  return;
}

void showTree(Tree t) {
  showTree0("", t);
}

void showTree0(char * txt, Tree t) {
  printf("%s\t%p\n", txt, (void *)t);
  showTree1(0, t);
  printf("\n");
}