#include <iostream.h>

class ARENA
{
public:
  ARENA(int ss,int a) { 
    arena = NULL; 
    last_segment = -1; 
    segment_size = ss;       //arena segment size
    align = a;               //memory alignment boundary
  }

  ~ARENA() {
    for(int i = 0; i <= last_segment; i++)
     delete[] arena[i];
    delete[] arena;
  }

  ARENA& operator= (const ARENA& ar) {
    int i, j;

    for(i = 0; i <= last_segment; i++)  // destroy old data
      delete[] arena[i];
    delete[] arena;
    arena = NULL;

    segment_size = ar.segment_size;       // copy new data
    next_ind = ar.next_ind;
    last_segment = ar.last_segment;
    align = ar.align;

    arena = new char* [last_segment+1];
    for(i = 0; i <= last_segment; i++) {
      arena[i] = new char[segment_size];
      for(j = 0; j < segment_size; j++)
        arena[i][j] = ar.arena[i][j];
    }
    return *this;
  }

  void* Alloc(size_t s) {  //alloc. memory of size s from its segment
    char** a;              //obtains a new segment if need be
    int i;
    void* ret;

    if (arena == NULL) {                       //alloc 1st segment
      arena = new char*[1];
      last_segment = 0;
      arena[0] = new char[segment_size];
      last_segment = 0;
      next_ind = 0;
    }else if (s > (size_t) segment_size-next_ind) { 
      last_segment++;
      a = new char*[last_segment+1];
      for(i = 0; i < last_segment; i++)
        a[i] = arena[i];
      delete[] arena;
      arena = a;
      arena[last_segment] = new char[segment_size];
      next_ind = 0;
    }
    ret = (void*) &arena[last_segment][next_ind];
    next_ind += s;
    // align next_ind for future use
    while(((long)&arena[last_segment][next_ind]%align) != 0)
      if (next_ind >= segment_size) break;

    // if next_ind runs to the end of the segment, no problem
    // on next Alloc() a new segment will be enforced
    return ret;
  }

void* Relativize(void* s) {     //relativizes address s with respect
    short segment, offset, *ip; //to the segment that s belongs to
    void* res;

    if (s == NULL) return NULL;

    for(segment = 0; segment <= last_segment; segment++) {
      if (s < arena[segment]) 
        continue;
      if (s >= arena[segment]+segment_size) 
        continue;
      // so we have the right segment
      offset = (short) ((long)s - (long)arena[segment]);
      segment++;        // shift segment by 1 so the beginning does
      ip = (short*)&res;  // not get relativized to NULL
      *ip++ = segment;
      *ip = offset;
      return res;
    }
    return NULL;
  }

void* Absolutize(void* s) {  //absolutize relative address s
    short *ip, segment, offset;
    void* r;

    if (s == NULL) return NULL;
    r = s;
    ip = (short*) &r;
    segment = *ip++;
    segment--;            // undo the shift
    offset = *ip;
    return (void*)&arena[segment][offset];
  }

protected:
  char** arena;
  short last_segment;
  short segment_size;
  short next_ind;
  short align;

};//end class ARENA


class TREE;

class NODE
{
  friend class TREE;
public:

  NODE() { value = 0; lch = rch = NULL; }
  NODE(char c) { value = c; lch = rch = NULL;  } 


protected:
  char value;
  NODE *lch, *rch;
  static ARENA *arena;

  //the following methods are only for arena allocation
  static void* operator new(size_t s) { return arena->Alloc(s); }

  // we will deallocate the whole arena instead
  static void operator delete(void* s) { return; }

  static void SetArena(ARENA* a) { //set the arena for NODE object
    static int first = 1;
    if (first) {
      arena = a;
      first = 0;
    }
  }
};//end class NODE

ARENA* NODE::arena = NULL;


class TREE
{
public:
  TREE() { root = NULL; }

  void Insert(char c) {   //start recursive insertion
    NODE* p;
    p = new NODE(c);
    p->lch = NULL;
    p->rch = NULL;
    if (root == NULL) {
      root = p;
      return;
    }else
      Insert1(root,p);
  }
  void Show() {
    if (root == NULL) return;
    Show1(root);
    cout << '\n' << flush;
  }
  void SetRoot(NODE* r) { root = r; }
  NODE* GetRoot() { return root; }

  static void SetArena(ARENA* a) {  //set arena for TREE object
    static int first = 1;
    if (first) {
      arena = a;
      NODE::SetArena(a);
      first = 0;
    }
  }

  void Relativize() {         //start recursive relativization of the
    Relativize1(root);        //at the root
    root = (NODE*)arena->Relativize(root);  
  }

  void Absolutize() {        //start recursive absolutization of the
                             //at the root
    root = (NODE*)arena->Absolutize((void*)root);
    Absolutize1(root);
  }

protected:
  NODE* root;
  static ARENA* arena;

void Insert1(NODE* n,NODE* p) { //continue recursive insertion
    if (p->value < n->value)
      if (n->lch == NULL)
        n->lch = p;
      else
        Insert1(n->lch,p);
    else
      if (n->rch == NULL)
        n->rch = p;
      else
        Insert1(n->rch,p);
  }

  void Show1(NODE* p) {
    if (p == NULL) return;
    Show1(p->lch);
    cout << ' ' << p->value;
    Show1(p->rch);
  }

  void Relativize1(NODE* n) {  //continue recursive relativization
    if (n == NULL) return;
    Relativize1(n->lch);  
    Relativize1(n->rch);  
    n->lch = (NODE*)arena->Relativize((void*)n->lch);
    n->rch = (NODE*)arena->Relativize((void*)n->rch);
  }

  void Absolutize1(NODE* n) {   //continue recursive absolutization
    if (n == NULL) return;
    n->lch = (NODE*)arena->Absolutize(n->lch);
    n->rch = (NODE*)arena->Absolutize(n->rch);
    Absolutize1(n->lch);
    Absolutize1(n->rch);
  }
};//end class TREE

ARENA* TREE::arena = NULL;




// function main -----------------------------------------------
int main()
{

  ARENA arena(24,4), b(0,0);
  TREE t, t1;
  
  t.SetArena(&arena);
  t.Insert('d');
  t.Insert('c');
  t.Insert('e');
  t.Insert('a');
  t.Insert('b');
  t.Show();
  t.Relativize();

  b = arena;
  t1.SetArena(&b);
  t1.SetRoot(t.GetRoot());
  t1.Absolutize();
  t1.Show();

  return 0;
}//end main