#ifndef AA_TREE_H__
#define AA_TREE_H__ 1

typedef struct aanode_ {
   int key;
   void *val;
   int lv;
   struct aanode_*l, *r;
} aanode;

typedef struct {
   aanode *root;
   aanode *nullnode;
   aanode *deleted;
   aanode *last;
   void(*valfree_fun)(void*);
   unsigned int num_entries;
} aatree;

// new empty AA tree
aatree* new_aatree(void(*valfree_fun)(void*));
// delete the AA tree(release all resources)
void  delete_aatree(aatree *t);

// the number of elements
unsigned aa_num_entries(const aatree *t);
// search an item in the tree by the key, and return the value
void* aa_search(const aatree *t, const int key);
// insert an item by key-value into the tree
void  aa_insert(aatree *t, const int key, void *val);
// remove an item from the tree by the key
void  aa_remove(aatree *t, const int key);
// a node of smallest key in the tree
aanode* aa_first(const aatree *t);
// a node of biggest key in the tree
aanode* aa_last(const aatree *t);

// foreach statement
typedef void (*AAForeach)(const aanode *, void *args);
void aa_foreach(const aatree *t, AAForeach callback, void *arg);
// map statement(previous data is released automatically)
typedef void*(*AAMap)(const aanode *);
void aa_map(const aatree *t, AAMap callback);

#endif