/**
  * 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 "BitString.h"

typedef BitString Key;
typedef long int Attr;   /* or something else */

typedef enum {Empty, Leaf, Fork} TreeKind;

typedef struct Node * Tree;

struct Node {
  TreeKind Kind;
  union {
    /* data for leaf nodes */
    struct {
      Key k;
      Attr a;
    } leaf;

    /* data for inner nodes */
    struct {
      Prefix p;
      Mask m;
      Tree l;
      Tree r;
    } fork;

    /* data for empty tree */
    /* not there */

  } data;
};

typedef Tree IntMap;

typedef void (*ProcessKeyAttr)(Key k, Attr a);

extern Tree empty;

extern int  isInMap(Key k, Tree t, Attr * res);
extern Tree insert(Key k, Attr a, Tree t);
extern Tree remov(Key k, Tree t);    /* remove is in stdio.h */
extern void foreach(ProcessKeyAttr p, Tree t);

extern void showTree(Tree t);
extern void showTree0(char * txt, Tree t);

#if TRACE
#define trace(x) x
#else
#define trace(x)
#endif