Visualizza wikitesto di Algoritmi e strutture dati/Progetti/Rettangoli/Stesura I

   #include <stdio.h>
   #include <stdlib.h>
   
         /* definizione dei tipi */
   
   typedef enum{red, black} color;
   
   struct rbapple {
   int xx;
   int yy;
   color co;
   char touch;
   struct rbapple *left;
   struct rbapple *right;
   struct rbapple *parent;
   };			/* struttura di	ogni nodo dell'albero dei punti*/"
   
   typedef struct rbapple rbapple;
   
   struct rbalbero {
   rbapple *root;
   rbapple *nul;
   };	      /*struttura contenente i puntatori alla radice e alla sentinella"
   	       dell'albero dei punti*/"
   
   struct rbnode {
   color co ;
   int a;
   int b;
   int c;
   int d;
   char campo;
   struct rbnode *sinistra;
   struct rbnode *destra;
   struct rbnode *genitore;
   };			  /*struttura di ogni nodo dell'albero dei rettangoli*/"
   
   typedef struct rbnode rbnode;
   
   struct rbtree {
     rbnode *root;
     rbnode *nil;
   };		 /*struttura contenente	i puntatori alla radice e alla sentinella"
   	       dell'albero dei rettangoli*/"
   
   typedef struct rbalbero rbalbero;
   typedef struct rbtree rbtree;
   
   /*    variabili globali	   */"
     rbtree *spazio=NULL; /*puntatore all'albero dei rettangoli*/
     rbtree *blocco=NULL;/*puntatore all'albero contennte i rettangoli facenti
   			parte di un blocco*/"
     rbalbero *foglio=NULL;/*puntatore all'albero dei punti*/
     rbalbero *niubbio=NULL;/*puntatore all'albero contenente i punti che vanno
   			   rimossi*/"
     int   par1=0,
     par2=0,
     par3=0,
     par4=0,			  /* variabili di input*/"
     perimetro= 0,
     max_x=0,  /*dimensione massima dell'ascissa del piano*/
     max_y=0;  /*dimensione massima dell'ordinata del piano*/
   char com; /*parametro di scelta*/
   
   /*
   	       prototipi di FUNZIONI E PROCEDURE"
   */
   
   /*
   procedure principali
   */
   void procedura_perimetro(void);
   void procedura_blocco(void);
   
   void rbdelete(rbalbero *tree, rbapple *q);
   void scorri_albero_rettangoli (rbtree *perno, rbnode *buster, rbalbero *joshua , rbapple *corda,int x, int y,rbalbero *elimina);
   void elimina_interni_foglio(rbalbero *tree, rbapple *q,rbnode *helper, int x, int y ,rbalbero *elimina);
   void scorri_albero_punti(rbalbero *sanato, rbapple *helper, rbtree *f, rbnode *element, rbalbero *elimina);
   void ruotaadestra(rbalbero *andtrea , rbapple *giovanni);
   void inizializzacampo(rbnode *pino, rbnode *peppe);
   void fixup(rbalbero *tree, rbapple *x);
   void elimina_albero_supporto(rbalbero *sanato, rbapple *helper);
   void elimina_puntini(rbalbero *sanato, rbapple *helper, rbalbero *albero_punti);
   void inserisci_foglio(rbalbero *carmencita, int yukapan, int turu);
   void canc_albero(rbapple *plastica, rbapple *impertinente);
   void costruisci_foglio(rbnode *attacca, rbnode *lattina, rbalbero *the);
   void inserisci_blocco(rbtree *dd, int c, int z, int vv, int sc);
   void creablocco(rbnode *at, rbnode *ds, rbtree *pc, rbtree *os, int bin, int ffe, int cut, int fre);
   void ruotaasinistra(rbalbero *pat, rbapple *emilia);
   void inserisci_punto (rbalbero *carmen, int lardo, int palino);
   void elimina_tutto_l_albero(rbnode *uno, rbnode *due);
   void rightrotate(rbtree *ssa ,  rbnode *eew);
   void leftrotate(rbtree *gix, rbnode *giz);
   void inserisci_in_albero(rbtree *csi, int x , int y, int z, int u);
   void installarettangolo1(rbtree *doo, int you, int foo, int sedd, int degr);
   void search_block(rbnode *fab, rbnode *anna, rbtree *lobot, char drea,  int cse, int cpi);
   /*
   funzioni
   */
   int perimetroeblocco(rbalbero *foglio, int peri, char p_o_b);
   int ilpuntoeinterno(rbnode *p,int x, int y);
   rbapple *treesucc(rbalbero *tree, rbapple *q);
   rbapple *treemin(rbapple *p, rbalbero *tree);
   rbapple *minimo_foglio(rbapple *paolo, rbapple *piero);
   rbapple *trova_nodofoglio(rbalbero *eustachio, int adalberto , int paola);
   rbapple *crea_apple(rbalbero *lindo, int cccp, int ostro);
   rbapple *inserisci_apple(rbalbero *orin, int elio, int samaga);
   rbalbero *costruisci_blocco(rbtree *star, rbtree *stor,	 rbalbero *bull, int e, int f,char g);"
   rbalbero *crea_rbalbero(int gino);
   rbtree *crea_rbtree(void);
   rbtree *crea_spazio(rbtree *der, int ddr, int fviva);
   rbnode *cercanodino(rbtree *nonnot, int defr, int wwe, int t342, int dds);
   rbnode *assegna_rbnode(rbtree *eew, int, int, int, int);
   rbnode *metti_un_elemento(rbtree *lls, int d, int f, int r, int t);
   
   /*
   	 implementazione delle FUNZIONI	e PROCEDURE"
   */
   
   rbtree *crea_spazio(rbtree *spazio, int x, int y)
   /*
   questa procedura controlla che non sia già presente uno spazio e ne crea uno di
   dimensioni x y; nel caso in cui ci sia già uno spazio, lo cancella e, solo dopo
   crea quello richiesto.
   Nel primo caso il tempo è O(1), nel secondo dipende dalla funzione che elimina l'
   albero precedente.
   */
   {
     max_x=x;
     max_y=y;
     if(!spazio)
     {
      if (!(spazio = crea_rbtree()))
         exit(-2);
     }
     else
     {
       elimina_tutto_l_albero(spazio->root, spazio->nil);
       free(spazio);
      if (!(spazio = crea_rbtree()))
         exit(-2);
     }
     return spazio;
   }
   
   void procedura_blocco(void)
   /*
   questa procedura racchiude tutte le operazioni da compiere per calcolare e
   stampare a video la descrizione del contorno del blocco
   */
    {
    if(foglio != NULL)
   	       {"
   		  canc_albero(foglio->root, foglio->nul);"
   		  free(foglio);"
   		  foglio = NULL;"
   	       }"
   	       if(!(par1 >= 0 && par2 >= 0 && par1 <=max_x && par2<=max_y))"
   		    {"
   		    printf(""b -1"");"
   		    }"
   	       else"
   		   {"
   		   foglio = costruisci_blocco(spazio, blocco, foglio, par1, par2,'b');"
   		   if(foglio !=	NULL)"
   			     {"
   			     if	(!(niubbio=crea_rbalbero(1)))"
   				exit(-2);"
   			     scorri_albero_punti(foglio, foglio->root, spazio, spazio->root, niubbio);"
   			     elimina_puntini(niubbio, niubbio->root,foglio);"
   			     elimina_albero_supporto(niubbio, niubbio->root);"
   			     free(niubbio->nul);"
   			     free(niubbio);"
   			     perimetro = perimetroeblocco(foglio, perimetro, 'b');"
   			     }"
   		   }"
   }
   
   
   
   void elimina_tutto_l_albero(rbnode *ghigo, rbnode *nil)
   /*
   questa procedura elimina tutto l'albero passatole in input.
   tempo @(n), essendo n i nodi dell'albero da cancellare.
   */
   {
   	    if (ghigo->destra!=nil)"
   	       elimina_tutto_l_albero(ghigo->destra,nil);"
   	    if (ghigo->sinistra!=nil)"
   	       elimina_tutto_l_albero(ghigo->sinistra, nil);"
   	    ghigo->genitore = nil;"
   	    free (ghigo);"
   }
   
   
   rbtree *crea_rbtree(void)
   /*
   questa funzione crea e inizializza la radice e la sentinella di un albero e ne
   restituisce il puntatore.
   tempo @(1)
   */
   {
           rbtree *tree = malloc(sizeof(rbtree));
           if(!tree)
   	    return NULL;"
           if(!(tree->root = malloc(sizeof(rbnode))))
   	    return NULL;"
           tree->nil = tree->root;
           tree->nil->sinistra = tree->nil->destra = tree->nil->genitore = tree->nil;
           tree->nil->co = black;
           return tree;
   }
   
   void elimina_puntini(rbalbero *sanato, rbapple *helper, rbalbero *albero_punti)
   /*
   questa procedura elimina i punti interni del blocco, che abbiamo precedentemente
   inserito in un albero.
   tempo O(n), essendo n i nodi da cancellare. (va anlizzata a parte la procedura
   che effettivamente elimina i nodi)
   */
   	 {"
           rbapple *kiss;
           if (helper->left!=sanato->nul)
   	    elimina_puntini(sanato, helper->left, albero_punti);"
   
   
   		kiss = trova_nodofoglio(albero_punti, helper->xx, helper->yy);"
   
   		if (kiss)"
   			rbdelete(albero_punti, kiss);"
   
   
   
           if (helper->right!=sanato->nul)
   	   elimina_puntini(sanato,	helper->right,albero_punti);"
   }
   
   void elimina_albero_supporto(rbalbero *sanato, rbapple *helper)
   /*
   questa procedura distrugge completamente un albero di tipo rbalbero.
   tempo @(n), essendo n i nodi dell'albero.
   */
   {
           rbapple *kiss;
           if (helper->left!=sanato->nul)
   	    elimina_albero_supporto(sanato, helper->left);"
           if (helper->right!=sanato->nul)
   	   elimina_albero_supporto(sanato,	helper->right);"
   		free(helper);"
   }
   
   void installarettangolo1(rbtree *spazio, int a, int b, int c, int d)
   /*
   questa procedura inserisce un rettangolo nell'albero in input.
   tempo O(log n) dovuto alla ricerca nell'albero e all'insrimento
   */
   {
     rbnode *maya =NULL;
     if((a < c)&&(a >=0)&&(b < d)&&(b >= 0)&&(c <= max_x)&&(d <=max_y)&&(c >=0)&&(d>=0))
     {
       maya = cercanodino(spazio, a, b, c, d);
       if(maya == NULL)
       {
         inserisci_in_albero(spazio, a, b, c, d);
       }
     }
   }
   
   
   void inserisci_in_albero(rbtree* spazio, int a, int b, int c, int d)
   /*
   questa procedura inserisce un nodo in un'albero rb e ne ripristina le proprietà.
   tempo @(log n) dovuto alla ricerca dello spazio nell'albero
   */
   {
     rbnode *fatur	 = metti_un_elemento(spazio, a, b, c, d);"
     rbnode *iron = NULL;
     if (fatur != NULL){
     while(fatur != spazio->root && fatur->genitore->c == red)
     {
       if(fatur->genitore == fatur->genitore->genitore->sinistra)
       {
         iron = fatur->genitore->genitore->destra;
         if(iron->co == red)
         {
           fatur->genitore->co = black;
           iron->co = black;
           fatur->genitore->genitore->co = red;
           fatur= fatur->genitore->genitore;
         }
         else
         {
           if(fatur == fatur->genitore->destra)
           {
   	  fatur	= fatur->genitore;"
   	  leftrotate(spazio, fatur);"
           }
           fatur->genitore->co = black;
           fatur->genitore->genitore->co = red;
           rightrotate(spazio, fatur->genitore->genitore);
         }
       }
   
       else
       {
         iron = fatur->genitore->genitore->sinistra;
         if(iron->co == red)
         {
           fatur->genitore->co = black;
           iron->co = black;
           fatur->genitore->genitore->co = red;
           fatur = fatur->genitore->genitore;
         }
         else
         {
           if(fatur == fatur->genitore->sinistra)
           {
   	  fatur	= fatur->genitore;"
   	  rightrotate(spazio, fatur);"
           }
           fatur->genitore->co = black;
           fatur->genitore->genitore->co = red;
           leftrotate(spazio, fatur->genitore->genitore);
         }
       }
     }
     spazio->root->co = black;}
   }
   
   
   rbnode *metti_un_elemento(rbtree *spazio, int a, int b, int c, int d)
   /*
   questa procedura inserisce un elemento in un albero rb, come se si trattasse di
   un albero binario di ricerca.
   tempo @(log n) limitato superiormente dal fatto che l'albero è bilanciato, in
   quanto rb.
   */
   {
     char pink;
     rbnode *bruce = spazio->root;
     rbnode *purple = spazio->nil;
     while(bruce != spazio->nil)
     {
       purple = bruce;
       if(a == purple->a && b == purple->b && c == purple->c && d == purple->d)
       return NULL;
       else
       if(a >= purple->a && b >= purple->b && c <= purple->c && d <= purple->d)
       return NULL;
       else
       if (a < purple->a)
       pink = 'n';
       else
       if(a > purple->a)
       pink = 'y';
       else
       if(a == purple->a && b < purple->b)
       pink = 'n';
       else
       if(a == purple->a && b > purple->b)
       pink = 'y';
       else
       if(a == purple->a && b == purple->b && c < purple->c)
       pink = 'n';
       else
       if(a == purple->a && b == purple->b && c > purple->c)
       pink = 'y';
       else
       if(a == purple->a && b == purple->b && c == purple->c && d <= purple->d)
       pink= 'n';
       else
       pink = 'y';
       if (pink == 'n')
       bruce =purple->sinistra;
       else
       bruce=purple->destra;
     }
     bruce = assegna_rbnode(spazio, a, b, c, d);
     bruce->genitore = purple;
     if(purple == spazio->nil)
     spazio->root = bruce;
     else
     if(a < purple->a)
     purple->sinistra = bruce;
     else
     if(a > purple->a)
     purple->destra = bruce;
     else
     if(a == purple->a && b < purple->b)
     purple->sinistra = bruce;
     else
     if(a == purple->a && b > purple->b)
     purple->destra = bruce;
     else
     if(a == purple->a && b == purple->b && c < purple->c)
     purple->sinistra = bruce;
     else
     if(a == purple->a && b == purple->b && c > purple->c)
     purple->destra = bruce;
     else
     if(a == purple->a && b == purple->b && c == purple->c && d <= purple->d)
     purple->sinistra = bruce;
     else
     purple->destra = bruce;
     return bruce;
   }
   
   rbnode *assegna_rbnode(rbtree *spazio, int a, int b, int c, int d)
   /*
   questa procedura alloca spazio per un nodo di tipo rbtree. In caso no riuscisse
   ad allocare spazio in memoria esce dal programma e restituisce un codice di
   errore.
   tempo @(1)
   */
   {
     rbnode *figaro = NULL;
     if (!(figaro = malloc(sizeof(rbnode))))
        exit(-2);
     figaro->campo='n';
     figaro->co=red;
     figaro->a=a;
     figaro->b=b;
     figaro->c=c;
     figaro->d=d;
     figaro->destra = spazio->nil;
     figaro->sinistra = spazio->nil;
     figaro->genitore=spazio->nil;
     return figaro;
   }
   
   void leftrotate(rbtree* spazio, rbnode* indotto)
   /*
   questa procedura produce una rotazione necessaria al ripristino delle proprietà
   dell'alberorb.
   tempo @(1)
   */
   {
           rbnode *y = indotto->destra;
           indotto->destra = y->sinistra;
           if (y->sinistra != spazio->nil)
   	   y->sinistra->genitore = indotto;"
   	   y->genitore = indotto->genitore;"
           if (indotto->genitore==spazio->nil)
   	   spazio->root	= y;"
           else
   	    if (indotto==indotto->genitore->sinistra)"
   	    y->genitore->sinistra = y;"
   	    else"
   	    y->genitore->destra	= y;"
           y->sinistra = indotto;
           indotto->genitore = y;
   }
   
   void rightrotate(rbtree* perno, rbnode* ghigo)
   /*
   questa procedura produce una rotazione necessaria al ripristino delle proprietà
   dell'alberorb.
   tempo @(1)
   */
   {
           rbnode *mm = ghigo->sinistra;
           ghigo->sinistra = mm->destra;
           if (mm->destra!=perno->nil)
   		mm->destra->genitore = ghigo;"
           mm->genitore = ghigo->genitore;
           if (ghigo->genitore==perno->nil)
   		perno->root = mm;"
           else
   	    if (ghigo==ghigo->genitore->destra)"
   	    mm->genitore->destra = mm;"
   	    else"
   	    mm->genitore->sinistra = mm;"
           mm->destra = ghigo;
           ghigo->genitore = mm;
   }
   
   rbnode *cercanodino(rbtree *spazio, int a, int b, int c, int d)
   /*
   questa funzione cerca un nodo nell'albero e, in caso lo trovi, ne restituisce il
   puntatore; in caso contrario restituisce NULL.
   tempo @(log n)
   */
   {
     rbnode *buffer = NULL;
     char macaja;
     buffer = spazio->root;
     while(buffer != spazio->nil && (buffer->a != a || buffer->b != b || buffer->c != c || buffer->d != d))
     {
       if(a < buffer->a)
       macaja = 'y';
       else
       if(a > buffer->a)
       macaja = 'n';
       else
       if(a == buffer->a && b < buffer->b)
       macaja = 'y' ;
       else
       if(a == buffer->a && b > buffer->b)
       macaja = 'n';
       else
       if(a == buffer->a && b == buffer->b && c < buffer->c)
       macaja = 'y';
       else
       if(a == buffer->a && b == buffer->b && c > buffer->c)
       macaja = 'n';
       else
       if(a == buffer->a && b == buffer->b && c == buffer->c && d <= buffer->d)
       macaja = 'y';
       else
       macaja = 'n';
       if (macaja =='y')
          buffer = buffer->sinistra  ;
       else
           buffer=buffer->destra;
     }
     if(buffer == spazio->nil)
     return NULL;
     else
     return buffer;
   }
   
   rbalbero *crea_rbalbero(int a)
   /*
   questa procedura alloca spazio e inizializza la radice e la sentnella di un
   albero di tipo rbalbero.
   tempo @(1)
   */
   {
           rbalbero *tree = malloc(sizeof(rbalbero));
           if(!tree)
   	    return NULL;"
           if(!(tree->root = malloc(sizeof(rbapple))))
   	    return NULL;"
           tree->nul = tree->root;
           tree->nul->left = tree->nul->right = tree->nul->parent = tree->nul;
           tree->nul->co = black;
   		if (a==1)"
   		   {"
   		     if	(!(tree->nul=malloc(sizeof(rbapple))))"
   			exit(-2);"
   		     tree->root->left =	tree->root->right = tree->root->parent = tree->nul;"
   		   }"
           return tree;
   }
   
   
   rbapple *trova_nodofoglio(rbalbero *perno, int puntox, int puntoy)
   /*
   questa funzione si occupa di trovare un nodo, se esistente, e di restituirne il
   puntatore. Nel caso in cui il nodo non esista restituisce NULL.
   tempo @(log n)
   */
   
   {
      rbapple *giusto=perno->root;
      while (giusto!=perno->nul && (giusto->xx!=puntox || giusto->yy!=puntoy))
      {
        if (puntox<giusto->xx)
        giusto = giusto->left;
        else
        if (puntox>giusto->xx)
        giusto = giusto->right;
        else
        if (puntox == giusto->xx && puntoy < giusto->yy)
        giusto = giusto->left;
        else
        giusto = giusto->right;
       }
       if (giusto==perno->nul)
   	   return NULL;"
       else
   	   return giusto;"
   }
   
   void inserisci_punto(rbalbero* perno, int puntox, int puntoy)
   /*
   questa procedura inserisce un nodo in un'albero rb e ne ripristina le proprietà.
   tempo @(log n) dovuto alla ricerca dello spazio nell'albero
   */
   
   {
     rbapple *birba = inserisci_apple(perno, puntox, puntoy);
     rbapple *cesco;
     if (birba!=NULL){
     while (birba!=perno->root && birba->parent->co==red)
     {
       if (birba->parent==birba->parent->parent->left)
       {
          cesco = birba->parent->parent->right;
          if (cesco->co==red)
          {
   	  birba->parent->co  = black;"
   	  cesco->co = black;"
   	  birba->parent->parent->co = red;"
   	  birba	= birba->parent->parent;"
          }
         else
          {
           if (birba==birba->parent->right)
   	 {"
   	    birba = birba->parent;"
   	    ruotaasinistra(perno, birba);"
   	 }"
           birba->parent->co       = black;
           birba->parent->parent->co = red;
           ruotaadestra(perno, birba->parent->parent);
          }
        }
       else
        {
        cesco = birba->parent->parent->left;
        if (cesco->co==red)
        {
   	  birba->parent->co	= black;"
   	  cesco->co = black;"
   	  birba->parent->parent->co = red;"
   	  birba	= birba->parent->parent;"
        }

Per quanto riguarda la discussione del progetto fai riferimento a [http://www.dsy.it/forum/attachment.php?s=&postid=21256 questo file], che contiene anche il file C del progetto.

[[Categoria:Progetti]]