include/acdp/actree.h

#ifndef ACTREE_HPP
#define ACTREE_HPP

#include "acdp.h"

typedef int  (*fcmp) (void *, void *);   // funcao de comparacao
typedef void (*fprt) (FILE *, void *);   // funcao de impressao

// definicao de uma classe para representar o no' da arvore generica
class acNodeTree
    {
    friend class acTree;

    private:
        acNodeTree *l, *r;   // pointer para os filhos
        void *dados;         // pointer para os dados
    public:
        acNodeTree *GetLeft()  { return(l); }
        acNodeTree *GetRight() { return(r); }
        void *GetData()        { return(dados); }
    };


class acTree
    {
    private:
        acNodeTree *head;    // inicio da arvore
        int        sizedados;      // numero de bytes dos dados
        fcmp       cmp;           // funcao de comparacao
        fprt       prt;           // funcao de impressao
        int        size_tree(acNodeTree *);
        void       Print(FILE *fp, acNodeTree *);
        void       cnivel(long nivel, acNodeTree *);
        void       setniv(long nivel, acNodeTree *);
        long       NumNiveis;     // numero de niveis
        long       *vecniv;  // vetor com niveis
        void       setvec (void **v, long &i, acNodeTree *t);
//        void       setvec (void huge * huge *v, long &i, acNodeTree *t);
//        acNodeTree *Rebuild (void huge * huge *v, long n);
        acNodeTree *Rebuild (void **v, long n);
        acNodeTree *resttree(long, FILE *);
        void       savetree(FILE *, acNodeTree *);
        void       errorcmp();    // erro de comparacao
        void       erroralloc();  // erro de alocacao
        void       errorinit();   // erro de inicializacao
        void       errorprt();    // erro de impressao


    public:

        // Funcao para retornar o inicio da arvore
        acNodeTree *GetHead() { return(head); }


        /*********************************************
        * Construtor e destrutor da arvore generica *
        *********************************************/

        /*
        ** Construtores
        **
        ** Formas de uso:
        **
        **      acTree tree(sizeof(tipo), func_comp);
        **              Cria tree e armazena tamanho dos dados e
        **              a funcao de comparacao para pesquisa e
        **              e insercao ordenada.
        **
        **      acTree tree(sizeof(tipo), func_comp, func_prt);
        **              Cria tree e armazena tamanho dos dados,
        **              da funcao de comparacao para pesquisa e
        **              e insercao ordenada e funcao de impressao/gravacao.
        */
        acTree()
            {
            head = 0;
            sizedados = 0;
            cmp = 0;
            prt = 0;
            }

        acTree(int s, fcmp c)
            {
            head = 0;
            sizedados = s;
            cmp = c;
            prt = 0;
            }

         acTree(int s, fcmp c, fprt p)
            {
            head = 0;
            sizedados = s;
            cmp = c;
            prt = p;
            }

        // Coloca dados em uma arvore criada sem argumentos
        void SetTreeData(int s, fcmp c)
            {
            head = 0;
            sizedados = s;
            cmp = c;
            prt = 0;
            }

        // Funcao para deletar todos os nos de uma arvore
        void Clear(acNodeTree *n = 0, int first = 1);

        // Funcao para deletar um no' a partir de uma chave
        // Se deletar retorna 1 e em caso contrario retorna 0
        int DelNode(void *);

        // Funcao para inserir um dado na arvore
        // Se inserir, retorna 1 e em caso contrario retorna 0
        // -1 -> erro
        int Insert(void *val);

        // funcao para inserir um dado na arvore
        // Se inserir, retorna o ponteiro para o no' criado
        // e em caso contrario, retorna NULL
        void *InsRet(void *val);

        // Funcao para inserir ou deletar um dado na arvore
        // Se inserir, retorna 1 e se deletar retorna 0
        // -1 -> erro
        int InsDel(void *val);

        // Funcao para retornar o tamanho de uma arvore
        int Size();

        // Funcao que retorna um pointer para um no'
        // se nao achar, retorna NULL
        void *Search(void *x);

        // grava ou imprime a arvore
        void Print(FILE *fp) { if (prt) Print(fp, head); }

        // grava arvore
        void Save(FILE *fp);

        // recurepa uma arvore
        void Restore(long n, FILE *fp);

        // imprime numero de niveis da arvore
        int PrintNivels(FILE *);

        // Rebalancea arvore
        void Balance();

        // Reordena arvore
        void Reorder();

        };


#endif // ACTREE_HPP