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 questo file, che contiene anche il file C del progetto.

[_pw9_]

nvnv