// cAVLTree.h: interface for the cAVLTree class.
//
//////////////////////////////////////////////////////////////////////

#ifndef cAVLTree_H
#define cAVLTree_H

#include "cAVLNode.h"

template <class Type>
class cAVLTree{
protected:
	cAVLNode<Type> *pRoot;
	
public:
	cAVLTree();
	virtual ~cAVLTree();



};

#endif 

    void    DestroySymbol(TSymbol *);
    TSymbol *RecurSearchSymbol(TSymbol *,char *);
    
    int     InsertSymbol(char *,long);
    TSymbol *SearchSymbol(char *);
    void    Write(FILE *);
    void    DestroyTable();
};

#endif














#include  <malloc.h>
#include  <string.h>
#include  <stdio.h>
#include  "Symbol.h"

TSymbol::TSymbol(char *sym,long val) {
  Symbol=0;
  Value=0;
  LeftS=RightS=0;
  Balance=0;
  SetSymbol(sym,val);
}

TSymbol::TSymbol() {
  Symbol=0;
  Value=0;
  LeftS=RightS=0;
  Balance=0;
}

TSymbol::~TSymbol() {
  if(Symbol!=0) free(Symbol);
}

int TSymbol::SetSymbol(char *sym,long val) {
  if(Symbol!=0) free(Symbol);
  Symbol=(char *)malloc(strlen(sym)+1);
  if(Symbol!=0) {
    strcpy(Symbol,sym);
    Value=val;
    return 1;
  }
  return 0;
}

void TSymbol::Write(FILE *f) {
  fprintf(f,"Name:%s, Value: %ld\n",Symbol,Value);
}

SymTable.cc - TSymTable class implementation

#include  <string.h>
#include  "SymTable.h"
#include  "Symbol.h"

TSymTable::TSymTable() {
  RootS=0;
}

TSymTable::~TSymTable() {
  DestroyTable();
}

void TSymTable::WriteSymbol(FILE *f,TSymbol *sym) {
  if(sym!=0) {
    WriteSymbol(f,sym->GetLeft());
    sym->Write(f);
    WriteSymbol(f,sym->GetRight());
  }
}

TSymbol *TSymTable::RecurSearchSymbol(TSymbol *sym,char *s) {
int res;
  if(sym==0) return 0;
  res=strcmp(s,sym->GetSymbol());
  if(res==0) return sym;
  else if(res>0) return RecurSearchSymbol(sym->GetRight(),s);
  else return RecurSearchSymbol(sym->GetLeft(),s);
}

void TSymTable::DestroySymbol(TSymbol *sym) {
  if(sym!=0) {
    DestroySymbol(sym->GetLeft());
    DestroySymbol(sym->GetRight());
    delete sym;
  }
}

int TSymTable::InsertSymbol(char *sym,long val) {
TSymbol *a,*b,*c,*f,*p,*q,*y;
int     cmpRes,d;
  if(RootS==0) {
    y=new TSymbol(sym,val);
    if(y==0) return 0;
    if(y->IsValid()==0) return 0;
    RootS=y;
    return 1;
  }
  f=0;
  a=RootS;
  p=RootS;
  q=0;
  while(p!=0) {
    if(p->GetBalance()!=0) {
      a=p;
      f=q;
    }
    cmpRes=strcmp(sym,p->GetSymbol());
    if(cmpRes<0) {
      q=p;
      p=p->GetLeft();
    }
    else if(cmpRes>0) {
      q=p;
      p=p->GetRight();
    }
    else return 2;
  }
  y=new TSymbol(sym,val);
  if(y==0) return 0;
  if(y->IsValid()==0) return 0;
  if(strcmp(sym,q->GetSymbol())<0) q->SetLeft(y);
  else q->SetRight(y);
  if(strcmp(sym,a->GetSymbol())>0) {
    p=a->GetRight();
    b=p;
    d=-1;
  }
  else {
    p=a->GetLeft();
    b=p;
    d=1;
  }
  while(p!=y) {
    if(strcmp(sym,p->GetSymbol())>0) {
      p->SetBalance(-1);
      p=p->GetRight();
    }
    else {
      p->SetBalance(1);
      p=p->GetLeft();
    }
  }
  if((a->GetBalance()==0)||((a->GetBalance()+d)==0)) {
    a->SetBalance(a->GetBalance()+d);
    return 1;
  }
  if(d==1) {
    if(b->GetBalance()==1) {
      a->SetLeft(b->GetRight());
      b->SetRight(a);
      a->SetBalance(0);
      b->SetBalance(0);
    }
    else {
      c=b->GetRight();
      b->SetRight(c->GetLeft());
      a->SetLeft(c->GetRight());
      c->SetLeft(b);
      c->SetRight(a);
      switch(c->GetBalance()) {
        case 1:
          a->SetBalance(-1);
          b->SetBalance(0);
          break;
        case -1:
          b->SetBalance(1);
          a->SetBalance(0);
          break;
        case 0:
          b->SetBalance(0);
          a->SetBalance(0);
          break;
      }
      c->SetBalance(0);
      b=c;
    }
  }
  else {
    if(b->GetBalance()==-1) {
      a->SetRight(b->GetLeft());
      b->SetLeft(a);
      a->SetBalance(0);
      b->SetBalance(0);
    }
    else {
      c=b->GetLeft();
      b->SetLeft(c->GetRight());
      a->SetRight(c->GetLeft());
      c->SetRight(b);
      c->SetLeft(a);
      switch(c->GetBalance()) {
        case 1:
          a->SetBalance(0);
          b->SetBalance(1);
          break;
        case -1:
          b->SetBalance(0);
          a->SetBalance(-1);
          break;
        case 0:
          b->SetBalance(0);
          a->SetBalance(0);
          break;
      }
      c->SetBalance(0);
      b=c;
    }
  }
  if(f==0) RootS=b;
  else if(a==f->GetLeft()) f->SetLeft(b);
  else if(a==f->GetRight()) f->SetRight(b);
  return 1;
}

TSymbol *TSymTable::SearchSymbol(char *sym) {
  return RecurSearchSymbol(RootS,sym);
}

void TSymTable::Write(FILE *f) {
  fprintf(f,"\n*** Symbol Table ***\n");
  WriteSymbol(f,RootS);
}

void TSymTable::DestroyTable() {
  DestroySymbol(RootS);
}

