Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Username: Password: oppure
Bubble Sort Demo - bubble_sort_demo.c

bubble_sort_demo.c

 Caricato da: AldoBaldo
Scarica il programma completo

  1. #include "bubble_sort_demo.h"
  2. #include "offscreen.h"
  3.  
  4. /// ===> COSTANTI <=============================================================
  5.  
  6. static CONST INT kMaxOpzioniNCol = 8;
  7. static CONST INT kOpzioniCol[kMaxOpzioniNCol] = { 6,8,10,12,16,20,24,30 };
  8.  
  9. static CONST INT kMinCol   = 6;
  10. static CONST INT kMaxCol   = 30;
  11. static CONST INT kMargini  = 10;
  12. static CONST INT kHDati    = 20;
  13. static CONST INT kHMinCol  = 20;
  14. static CONST INT kHMaxCol  = kHFP - 3*kMargini - kHDati;
  15. static CONST INT kBordoCol = 2;
  16. static CONST INT kRitardo  = 200;
  17.  
  18. static CONST RECT kRDati   =
  19.     { kMargini, kMargini, kWFP-kMargini, kMargini+kHDati };
  20. static CONST RECT kRCol    =
  21.     { kMargini, 2*kMargini+kHDati, kWFP-kMargini, kHFP-kMargini };
  22.  
  23. static CONST COLORREF kColoreNeutro      = RGB(0xFF,0xFF,0xFF);
  24. static CONST COLORREF kColoreOrdinato    = RGB(0x00,0x99,0x00);
  25. static CONST COLORREF kColoreNonOrdinato = RGB(0xFF,0x00,0x00);
  26. static CONST COLORREF kColoreScambiato   = RGB(0x00,0x99,0xCC);
  27. static CONST COLORREF kColoreTestoValori = RGB(0x00,0x00,0x00);
  28.  
  29. /// ===> GLOBALI <==============================================================
  30.  
  31. static INT  gNCol = kOpzioniCol[4];
  32. static INT  gSerie[kMaxCol] = {0};
  33. static INT  gWCol;
  34. static RECT gRCol1;
  35.  
  36. VOID CalcolaDimensioniColonne( VOID ) {
  37.     gWCol = (kWFP-2*kMargini)/gNCol;
  38.     SetRect( &gRCol1,
  39.         kMargini+kBordoCol, 2*kMargini+kHDati,
  40.         kMargini+gWCol-kBordoCol, kHFP-kMargini );
  41. }
  42.  
  43. /*==============================================================================
  44. Aumenta la quantita' dei dati da ordinare (e di conseguenza la quantita' delle
  45. colonne nel grafico) secondo quanto stabilito nell'array di costanti kOpzioniCol
  46. ==============================================================================*/
  47.  
  48. VOID IngrandisciSerie( HWND hwnd ) {
  49.     INT i;
  50.  
  51.     if( gNCol == kMaxCol ) return;
  52.  
  53.     for( i=0; i<kMaxOpzioniNCol; ++i ) {
  54.         if( kOpzioniCol[i] > gNCol ) {
  55.             gNCol = kOpzioniCol[i];
  56.             break;
  57.         }
  58.     }
  59.  
  60.     CalcolaDimensioniColonne();
  61.     MostraInfo( hwnd );
  62. }
  63.  
  64. /*==============================================================================
  65. Riduce la quantita' dei dati da ordinare (e di conseguenza la quantita' delle
  66. colonne nel grafico) secondo quanto stabilito nell'array di costanti kOpzioniCol
  67. ==============================================================================*/
  68.  
  69. VOID RimpicciolisciSerie( HWND hwnd ) {
  70.     INT i;
  71.  
  72.     if( gNCol == kMinCol ) return;
  73.  
  74.     for( i=kMaxOpzioniNCol-1; i>=0; --i ) {
  75.         if( kOpzioniCol[i] < gNCol ) {
  76.             gNCol = kOpzioniCol[i];
  77.             break;
  78.         }
  79.     }
  80.  
  81.     CalcolaDimensioniColonne();
  82.     MostraInfo( hwnd );
  83. }
  84.  
  85. /*==============================================================================
  86. Calcola le dimensioni massime da attribuire a ciascuna colonna, quindi reimposta
  87. i valori nella variabile globale gSerie, estraendone a sorte la quantita'
  88. stabilita da gNCol e contenendoli tra kHMinCol e kHMaxCol.
  89. ==============================================================================*/
  90.  
  91. VOID InizializzaSerie( VOID ) {
  92.     INT i;
  93.  
  94.     CalcolaDimensioniColonne();
  95.  
  96.     for( i=0; i<gNCol; ++i )
  97.         gSerie[i] = (rand()%(kHMaxCol-kHMinCol))+kHMinCol;
  98. }
  99.  
  100. /*==============================================================================
  101. Notifica la quantita' dei passi gia' eseguiti, la quantita' degli scambi gia'
  102. eseguiti e la quantita' dei valori gia' definitivamente ordinati, trascrivendoli
  103. entro il rettangolo kRDati.
  104. ==============================================================================*/
  105.  
  106. VOID TracciaDati( HWND hwnd, INT passi, INT scambi, INT ordinati ) {
  107.     HDC hdc = OSW_Dc();
  108.     CHAR buff[32];
  109.     INT lTxt, exBkMode;
  110.     COLORREF exColore;
  111.     OSW_Cancella( &kRDati );
  112.  
  113.     exBkMode = SetBkMode( hdc, TRANSPARENT );
  114.  
  115.     exColore = SetTextColor( hdc, kColoreNeutro );
  116.     lTxt = wsprintf( buff, "passi: %d", passi );
  117.     TextOut( hdc, kRDati.left, kRDati.top, buff, lTxt );
  118.  
  119.     SetTextColor( hdc, kColoreScambiato );
  120.     lTxt = wsprintf( buff, "scambi: %d", scambi );
  121.     TextOut( hdc, kRDati.left+100, kRDati.top, buff, lTxt );
  122.  
  123.     SetTextColor( hdc, kColoreOrdinato );
  124.     lTxt = wsprintf( buff, "ordinati: %d/%d", ordinati, gNCol );
  125.     TextOut( hdc, kRDati.left+200, kRDati.top, buff, lTxt );
  126.  
  127.     OSW_FlipSuFinestra( hwnd, &kRDati );
  128.  
  129.     SetTextColor( hdc, exColore );
  130.     SetBkMode( hdc, exBkMode );
  131. }
  132.  
  133. /*==============================================================================
  134. Traccia alla base del RECT *r il valore v, centrato orizzontalmente.
  135. ==============================================================================*/
  136.  
  137. VOID TracciaValoreColonna( HDC hdc, CONST RECT *r, INT v ) {
  138.     COLORREF exColore;
  139.     CHAR buff[16];
  140.     INT exBkMode;
  141.  
  142.     exColore = SetTextColor( hdc, kColoreTestoValori );
  143.     exBkMode = SetBkMode( hdc, TRANSPARENT );
  144.  
  145.     wsprintf( buff, "%d", v );
  146.     DrawText( hdc, buff, -1, (RECT*)r, DT_SINGLELINE|DT_CENTER|DT_BOTTOM );
  147.  
  148.     SetTextColor( hdc, exColore );
  149.     SetBkMode( hdc, exBkMode );
  150. }
  151.  
  152. /*==============================================================================
  153. Traccia tutte le colonne del grafico, differenziando per colore quelle gia'
  154. riordinate e quelle ancora da riordinare.
  155. ==============================================================================*/
  156.  
  157. VOID TracciaColonne( HWND hwnd, INT ordinati ) {
  158.     HBRUSH pennelli[2];
  159.     HDC hdc;
  160.     RECT r;
  161.     INT i;
  162.  
  163.     pennelli[0] = CreateSolidBrush( kColoreNeutro );
  164.     if( pennelli[0] == NULL ) return;
  165.     pennelli[1] = CreateSolidBrush( kColoreOrdinato );
  166.     if( pennelli[1] == NULL ) { DeleteObject(pennelli[0]); return; }
  167.  
  168.     hdc = OSW_Dc();
  169.     r = gRCol1;
  170.  
  171.     OSW_Cancella( &kRCol );
  172.  
  173.     for( i=0; i<gNCol; ++i ) {
  174.         r.top = kHFP-kMargini - gSerie[i];
  175.         FillRect( hdc, &r, pennelli[i>=gNCol-ordinati] );
  176.         TracciaValoreColonna( hdc, &r, gSerie[i] );
  177.         OffsetRect( &r, gWCol, 0 );
  178.     }
  179.  
  180.     OSW_FlipSuFinestra( hwnd, &kRCol );
  181.  
  182.     DeleteObject( pennelli[0] );
  183.     DeleteObject( pennelli[1] );
  184. }
  185.  
  186. /*==============================================================================
  187. Traccia le colonne del grafico interessate da un confronto per determinare se i
  188. valori in elenco vanno o non vanno scambiati, differenziandole per colore a
  189. seconda della relazione quantitativa tra di esse.
  190. ==============================================================================*/
  191.  
  192. VOID TracciaColonneAttive( HWND hwnd, INT nc ) {
  193.     HBRUSH pennelli[3]; // neutro, scambiato, non ordinato
  194.     RECT u, r[3] = { gRCol1, gRCol1, gRCol1 };
  195.     INT i, c[3] = { nc-1, nc, nc+1 };
  196.     HDC hdc;
  197.  
  198.     pennelli[0] = CreateSolidBrush( kColoreNeutro );
  199.     if( pennelli[0] == NULL ) return;
  200.  
  201.     pennelli[1] = CreateSolidBrush( kColoreScambiato );
  202.     if( pennelli[1] == NULL ) { DeleteObject(pennelli[0]); return; }
  203.  
  204.     pennelli[2] = CreateSolidBrush( kColoreNonOrdinato );
  205.     if( pennelli[2] == NULL )
  206.         { DeleteObject(pennelli[0]); DeleteObject(pennelli[1]); return; }
  207.  
  208.     hdc = OSW_Dc();
  209.  
  210.     for( i=0; i<3; ++i ) {
  211.         if( i==0 && nc==0 ) continue;
  212.  
  213.         OffsetRect( &r[i], c[i]*gWCol, 0 );
  214.  
  215.         OSW_Cancella( &r[i] );
  216.  
  217.         r[i].top = kHFP-kMargini - gSerie[c[i]];
  218.  
  219.         if( i!=0 )
  220.             FillRect( hdc, &r[i], pennelli[1+(gSerie[c[1]]>gSerie[c[2]])] );
  221.         else FillRect( hdc, &r[i], pennelli[i] );
  222.  
  223.         TracciaValoreColonna( hdc, &r[i], gSerie[c[i]] );
  224.     }
  225.  
  226.     UnionRect( &u, &r[0], &r[1] );
  227.     UnionRect( &u, &u, &r[2] );
  228.     OSW_FlipSuFinestra( hwnd, &u );
  229.  
  230.     for( i=0; i<3; ++i ) DeleteObject( pennelli[i] );
  231. }
  232.  
  233. /*==============================================================================
  234. Esegue un ciclo eventi per introdurre una pausa in attesa della richiesta di
  235. procedere al passo successivo dell'ordinamento o di uscire dalla dimostrazione
  236. in corso.
  237. ==============================================================================*/
  238.  
  239. BOOL InterruzioneUtente(
  240.     HWND hwnd, INT passi, INT scambi, INT ordinati, INT rit=kRitardo ) {
  241.     MSG msg;
  242.  
  243.     while( TRUE ) {
  244.         if( PeekMessage(&msg,NULL,0,0,PM_REMOVE) ) {
  245.             if (msg.message == WM_QUIT) {
  246.                 PostQuitMessage( 0 );
  247.                 return TRUE;
  248.             }
  249.             else if( msg.message != WM_KEYDOWN && msg.message != WM_CHAR ) {
  250.                 TranslateMessage( &msg );
  251.                 DispatchMessage( &msg );
  252.             }
  253.         }
  254.         else {
  255.             if( KEYDOWN(VK_RIGHT) ) {
  256.                 Sleep( rit*(!KEYDOWN(VK_SHIFT)) );
  257.                 return FALSE;
  258.             }
  259.             else if( KEYDOWN(VK_ESCAPE) ) {
  260.                 MostraInfo( hwnd );
  261.                 return TRUE;
  262.             }
  263.             else if( KEYDOWN('i')||KEYDOWN('I') ) {
  264.                 Informazioni( hwnd );
  265.             }
  266.         }
  267.     }
  268. }
  269.  
  270. /*==============================================================================
  271. Avvia ed esegue passo per passo l'ordinamento della serie dei valori contenuti
  272. in gSerie, rappresentandola a schermo sotto forma di ortogramma.
  273. ==============================================================================*/
  274.  
  275. BOOL AvviaDemo( HWND hwnd ) {
  276.     INT i, j, t, scambiato;
  277.     INT passi, scambi, ordinati;
  278.  
  279.     InizializzaSerie();
  280.     passi = scambi = ordinati = 0;
  281.     TracciaDati( hwnd, passi, scambi, ordinati );
  282.     TracciaColonne( hwnd, ordinati );
  283.     if( InterruzioneUtente(hwnd,passi,scambi,ordinati) ) return TRUE;
  284.  
  285.     for( i=0; i<gNCol-1; ++i ) {
  286.         scambiato = 0;
  287.  
  288.         for( j=0; j<gNCol-1-i; ++j ) {
  289.             TracciaColonneAttive( hwnd, j );
  290.             TracciaDati( hwnd, ++passi, scambi, ordinati );
  291.             if( InterruzioneUtente(hwnd,passi,scambi,ordinati) ) return TRUE;
  292.  
  293.             if( gSerie[j] > gSerie[j+1] ) {
  294.                 t = gSerie[j];
  295.                 gSerie[j] = gSerie[j+1];
  296.                 gSerie[j+1] = t;
  297.                 scambiato = 1;
  298.                 TracciaColonneAttive( hwnd, j );
  299.                 TracciaDati( hwnd, passi, ++scambi, ordinati );
  300.                 if( InterruzioneUtente(hwnd,passi,scambi,ordinati) ) return TRUE;
  301.             }
  302.         }
  303.  
  304.         if( scambiato ) {
  305.             TracciaDati( hwnd, passi, scambi, ++ordinati );
  306.             TracciaColonne( hwnd, ordinati );
  307.             if( InterruzioneUtente(hwnd,passi,scambi,ordinati) ) return TRUE;
  308.         }
  309.         else {
  310.             break;
  311.         }
  312.     }
  313.  
  314.     TracciaDati( hwnd, passi, scambi, gNCol );
  315.     TracciaColonne( hwnd, gNCol );
  316.  
  317.     return FALSE;
  318. }
  319.  
  320. // LE INFORMAZIONI SULLA SCHERMATA INIZIALE
  321.  
  322. static CONST INT kNRigheInfo = 11;
  323. static CONST CHAR *kStrInfo[kNRigheInfo] = {
  324.     "01. I dati numerici rappresentati dalle colonne del grafico sono casuali.",
  325.     "02. L'altezza delle colonne del grafico è proporzionale al dato numerico in etichetta.",
  326.     "03. Usa i tasti + e - per regolare la quantità delle colonne nel grafico.",
  327.     "04. Usa la barra spaziatrice per avviare la dimostrazione.",
  328.     "05. Usa il tasto freccia destra per far avanzare d'un passo la procedura d'ordinamento.",
  329.     "(tieni premuto \"maiuscolo\" per un avanzamento più veloce)",
  330.     "06. Usa il tasto \"esc\" per interrompere l'ordinamento in corso.",
  331.     "07. Le barre del grafico sono bianche se devono essere ancora riordinate.",
  332.     "08. Le barre del grafico sono verdi se sono già state riordinate.",
  333.     "09. Le barre esaminate sono rosse se il loro ordine dev'essere invertito.",
  334.     "10. Le barre esaminate sono  azzurre se il loro ordine non dev'essere invertito."
  335. };
  336.  
  337. static CONST INT kNRigheCodice = 18;
  338. static CONST CHAR *kStrCodice[kNRigheCodice] = {
  339.     // il carattere iniziale fornisce la quantita' dei rientri
  340.     "\0void Ordina( int dati[], int dimDati ) {",
  341.     "\1int i, j, scambiato, aux;",
  342.     "\1",
  343.     "\1for( i=0; i<dimDati-1; ++i ) {",
  344.     "\2scambiato = 0;",
  345.     "\2",
  346.     "\2for( j=0; j<dimDati-1-i; ++j ) {",
  347.     "\3if( dati[j] > dati[j+1] ) {",
  348.     "\4aux = dati[j];",
  349.     "\4dati[j] = dati[j+1];",
  350.     "\4dati[j+1] = aux;",
  351.     "\4scambiato = 1;",
  352.     "\3}",
  353.     "\2}",
  354.     "\2",
  355.     "\2if( !scambiato ) break;",
  356.     "\1}",
  357.     "\0}"
  358. };
  359.  
  360. /*==============================================================================
  361. Mostra una schermata che contiene le istruzioni per l'uso del programma e una
  362. funzione in codice C che rappresenta il metodo di ordinamento impiegato nella
  363. dimostrazione.
  364. ==============================================================================*/
  365.  
  366. VOID MostraInfo( HWND hwnd ) {
  367.     CONST INT kDistanzaRighe = 31;
  368.     CONST INT kDistanzaRigheCodice = 20;
  369.     CONST INT kMargineCodice = 680;
  370.     CONST INT kRientroCodice = 32;
  371.     INT i, lTxt, xTxt = kRDati.left, yTxt = kRDati.top;
  372.     HDC hdc = OSW_Dc();
  373.     OSW_Cancella( NULL );
  374.     CHAR buff[128];
  375.     HPEN penna;
  376.  
  377.     INT exBkMode = SetBkMode( hdc, TRANSPARENT );
  378.  
  379.     COLORREF exColore = SetTextColor( hdc, kColoreNeutro );
  380.     lTxt = wsprintf( buff, "numero di colonne: %d", gNCol );
  381.     TextOut( hdc, xTxt, yTxt, buff, lTxt );
  382.  
  383.     xTxt += 2*kMargini;
  384.     yTxt = kRDati.bottom+kMargini;
  385.  
  386.     for( i=0; i<kNRigheInfo; ++i ) {
  387.         yTxt += kDistanzaRighe;
  388.         lTxt = wsprintf( buff, kStrInfo[i] );
  389.         if( i==5 ) { xTxt += 2*kMargini; yTxt -= kMargini; }
  390.         TextOut( hdc, xTxt, yTxt, buff, lTxt );
  391.         if( i==5 ) { xTxt -= 2*kMargini; }
  392.     }
  393.  
  394.     yTxt = kRDati.bottom+kMargini+5 - kDistanzaRigheCodice;
  395.  
  396.     for( i=0; i<kNRigheCodice; ++i ) {
  397.         xTxt = kMargineCodice + kRientroCodice*(*kStrCodice[i]);
  398.         yTxt += kDistanzaRigheCodice;
  399.         lTxt = wsprintf( buff, kStrCodice[i]+1 );
  400.         TextOut( hdc, xTxt, yTxt, buff, lTxt );
  401.     }
  402.  
  403.     if( (penna=CreatePen(PS_SOLID,2,kColoreNeutro)) != NULL ) {
  404.         HGDIOBJ exPenna = SelectObject( hdc, penna );
  405.         xTxt -= 4*kMargini;
  406.         yTxt = kRDati.bottom+kMargini;
  407.         MoveToEx( hdc, xTxt, yTxt, NULL );
  408.         LineTo( hdc, xTxt, kHFP-yTxt );
  409.         SelectObject( hdc, (HPEN)exPenna );
  410.         DeleteObject( penna );
  411.     }
  412.  
  413.     OSW_FlipSuFinestra( hwnd, NULL );
  414.  
  415.     SetTextColor( hdc, exColore );
  416.     SetBkMode( hdc, exBkMode );
  417. }
  418.  
  419. /*==============================================================================
  420. Restituisce una stringa che comprende il nome del programma e informazioni sulla
  421. sua versione, sottoversione ed eventuale revisione. Se il parametro buff e' NULL
  422. colloca la stringa in uno spazio di memoria statica e ne restituisce l'indirizzo
  423. ==============================================================================*/
  424.  
  425. const char *NomeCompletoProgramma( char *buff ) {
  426.     static char stBuff[kLungNomeProgramma+16];
  427.     if( buff == NULL ) buff = stBuff;
  428.     char *p = buff;
  429.  
  430.     p += wsprintf( p, "%s %d.%d", kStrNomeProgramma,
  431.                    kVersioneProgramma, kSottoversioneProgramma );
  432.  
  433.     if( kRevisioneProgramma != 0 )
  434.         p += wsprintf( p, ".%d", kRevisioneProgramma );
  435.  
  436.     return buff;
  437. }
  438.  
  439. /*==============================================================================
  440. Mostra alcune informazioni sul programma.
  441. ==============================================================================*/
  442.  
  443. void Informazioni( HWND genitrice ) {
  444.     CHAR buff[256];
  445.     CHAR *p;
  446.  
  447.     NomeCompletoProgramma( buff );
  448.     p = buff + lstrlen( buff );
  449.  
  450.     p += wsprintf( p, "%s%s%s",
  451.         "\n© 2016 di Aldo Carpanelli",
  452.         "\nFreeware",
  453.         "\n\nBuon divertimento! :o)" );
  454.  
  455.     MessageBox( genitrice, buff,
  456.         "Informazioni di copyright",
  457.         MB_OK | MB_ICONINFORMATION );
  458. }