API tools faq
paste
knightL

sorts

knightL
Dec 17th, 2010
284
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 20.66 KB | None | 0 0
raw download clone embed print report
  1. --coursework.h--
  2. #ifndef COURSEWORK_H
  3. #define COURSEWORK_H
  4.  
  5. #include <gtk/gtk.h>
  6.  
  7. #define TREEOFFSETX 10
  8. #define TREEOFFSETY 70
  9.  
  10. #define LINEOFFSETX 20
  11. #define LINEOFFSETY 300
  12. #define RISE 30
  13.  
  14. #define VCOUNT 10
  15. #define HCOUNT 20
  16.  
  17. #define CENTERTEXTOFFSETY 20
  18. #define CENTERTEXTHEADER "Текущее действие:"
  19. #define SHADOWOFFSET -1
  20.  
  21. #define LEGENDOFFSETX 5
  22. #define LEGENDY 60
  23. #define LEGENDINNEROFFSETX 10
  24. #define LEGENDINNEROFFSETY 10
  25. #define LEGENDWIDTH 290
  26. #define LEGENDHEADERHEIGHT 20
  27. #define LEGENDHEADER "Легенда"
  28.  
  29. #define RAD 14
  30. #define GAP 0
  31.  
  32. #define N 26
  33. #define MOD 100
  34. #define STATECNT 9
  35.  
  36. #define MOVEDELAY 10
  37. #define REDRAWDELAY 300
  38. #define SORTDELAY 400
  39.  
  40. #define WIDTH 800
  41. #define HEIGHT 360
  42.  
  43. typedef struct elpath elpath;
  44. typedef struct element element;
  45. typedef struct action action;
  46. typedef enum elstate elstate;
  47. typedef enum actiontype actiontype;
  48. typedef union actionparameter actionparameter;
  49.  
  50. enum elstate
  51. {
  52.     normal=0,
  53.     inplace=1,
  54.     inheap=2,
  55.     processed=3,
  56.     active=4,
  57.     activeinplace=5,
  58.     activeinheap=6,
  59.     activeproc=7,
  60.     activeinterval=8
  61. };
  62. enum actiontype
  63. {
  64.     acsleep,
  65.     acswap,
  66.     acchangestate,
  67.     acchangephase
  68. };
  69. union actionparameter
  70. {
  71.     struct
  72.     {
  73.         int id1,id2;
  74.     } swap;
  75.     int time;
  76.     struct
  77.     {
  78.         int id;
  79.         elstate state;
  80.     } chgst;
  81.     int phase;
  82. };
  83. struct elpath
  84. {
  85.     GList *linecurve,*treecurve;
  86.     int elnum;
  87. };
  88.  
  89. struct element
  90. {
  91.     GdkPoint linecoord,treecoord;
  92.     int value;
  93.     elstate state;
  94. };
  95. struct action
  96. {
  97.     actiontype type;
  98.     actionparameter param;
  99. };
  100.  
  101. void init_gc();
  102. void init_sort();
  103. void init_legend();
  104. void draw_element(GtkWidget *w,GdkDrawable *d, element *e);
  105. void draw_text_in_center(gchar * text, GtkWidget *w, GdkDrawable *d, GdkGC *gc, gint xc, gint yc);
  106. void draw_text_in_center_y(gchar * text, GtkWidget *w, GdkDrawable *d, GdkGC *gc, gint x, gint yc);
  107. void draw_legend();
  108. void startmoving(elpath *p1,elpath *p2);
  109. void swap(int idx1,int idx2);
  110. void swapvis(int idx1,int idx2);
  111. void displayphasetxt();
  112. void genline(GdkPoint s, GdkPoint t,int cnt,GList ** l);
  113. void insertswap(int idx1,int idx2);
  114. void insertchangestate(int idx,elstate newstate);
  115. void insertsleep(int t);
  116. void insertchangephase(int np);
  117. void heapsort(int *array);
  118. void quicksort(int n,int *a,int offset);
  119. GdkPoint getlinecoord(int n);
  120. GdkPoint gettreecoord(int n,int maxh);
  121. elpath makepath(gint idx,GdkPoint listb,GdkPoint liste, gint dy, gint listc1, gint listc2,gint listc3,GdkPoint treep1,GdkPoint treep2, gint treec);
  122. gboolean move(elpath* p);
  123. gboolean expose_event(GtkWidget *w,GdkEvent *e, gpointer data);
  124. gboolean delete_event(GtkWidget *w,GdkEvent *e, gpointer data);
  125. gboolean visualize(gpointer data);
  126.  
  127.  
  128. #endif
  129. --coursework.c--
  130. #include <stdio.h>
  131. #include <stdlib.h>
  132. #include <time.h>
  133. #include <gtk/gtk.h>
  134. #include "coursework.h"
  135.  
  136. GtkWidget *window;
  137. GdkPixmap *legend;
  138. GdkGC *gcbg[STATECNT],*gcfg[STATECNT];
  139. GSList *actionqueue=NULL;
  140. element el[N];
  141. int arrv[N];
  142. char phasetxt[4][100]={"Построение кучи","Исключение наибольшего элемента","Восстановление кучи","Сортировка окончена"};
  143. #if HEAPSORTA
  144. gboolean legendshow[STATECNT]={TRUE,TRUE,TRUE,FALSE,TRUE,TRUE,FALSE,FALSE,FALSE};
  145. #elif HEAPSORTB
  146. gboolean legendshow[STATECNT]={TRUE,TRUE,FALSE,TRUE,TRUE,TRUE,FALSE,FALSE,FALSE};
  147. #elif SHELLSORT
  148. gboolean legendshow[STATECNT]={TRUE,FALSE,FALSE,TRUE,TRUE,FALSE,FALSE,FALSE,FALSE};
  149. #elif BUBBLESORT
  150. gboolean legendshow[STATECNT]={TRUE,TRUE,FALSE,TRUE,TRUE,FALSE,FALSE,FALSE,FALSE};
  151. #elif QUICKSORT
  152. gboolean legendshow[STATECNT]={TRUE,FALSE,FALSE,TRUE,TRUE,FALSE,FALSE,FALSE,TRUE};
  153. #endif
  154. int legendshowcnt;
  155. int legendheight;
  156. char legendtext[STATECNT][100]={"Обычный","На своём месте","В куче","Обрабатывается","Перемещается","Перемещается на своё место","","","Текущий интервал"};
  157. int phase;
  158. int finished;
  159. int clrneed;
  160. int hi,hj;
  161. int legx,legy;
  162.  
  163. int main(int argc,char * argv[])
  164. {
  165.     int i;
  166.     int maxh;
  167.     gtk_init(&argc,&argv);
  168.     window=gtk_window_new(GTK_WINDOW_TOPLEVEL);
  169.    
  170.     gtk_widget_set_size_request(window,WIDTH,HEIGHT);
  171.  
  172.    
  173.     srand(time(0));
  174.     for(maxh=0;(1<<maxh)<=N;maxh++);
  175.     for(i=0;i<N;i++)
  176.     {
  177.         el[i].linecoord=getlinecoord(i);
  178.         el[i].treecoord=gettreecoord(i,maxh);
  179.         arrv[i]=el[i].value=rand()%MOD;
  180.         el[i].state=normal;
  181.     }
  182.     gtk_widget_show(window);
  183.     init_gc();
  184.     init_sort();
  185.     init_legend();
  186.     g_signal_connect(G_OBJECT(window),"delete-event",G_CALLBACK(delete_event),NULL);
  187.     g_signal_connect(G_OBJECT(window),"expose-event",G_CALLBACK(expose_event),NULL);
  188.     expose_event(window,NULL,NULL);
  189.     gtk_main();
  190.     return 0;
  191. }
  192.  
  193.  
  194. void init_gc()
  195. {
  196.     GdkColor c;
  197.     gcbg[normal]=gdk_gc_new(window->window);
  198.     gcfg[normal]=gdk_gc_new(window->window);
  199.     gcbg[active]=gdk_gc_new(window->window);
  200.     gcfg[active]=gdk_gc_new(window->window);
  201.     gcbg[inplace]=gdk_gc_new(window->window);
  202.     gcfg[inplace]=gdk_gc_new(window->window);
  203.     gcbg[activeinheap]=gcbg[active];
  204.     gcfg[activeinheap]=gcfg[active];
  205.     gcbg[inheap]=gdk_gc_new(window->window);
  206.     gcfg[inheap]=gdk_gc_new(window->window);
  207.     gcbg[activeinplace]=gdk_gc_new(window->window);
  208.     gcfg[activeinplace]=gdk_gc_new(window->window);
  209.     gcbg[inheap]=gdk_gc_new(window->window);
  210.     gcfg[inheap]=gdk_gc_new(window->window);
  211.     gcbg[activeinplace]=gdk_gc_new(window->window);
  212.     gcfg[activeinplace]=gdk_gc_new(window->window);
  213.     gcbg[processed]=gdk_gc_new(window->window);
  214.     gcfg[processed]=gdk_gc_new(window->window);
  215.     gcbg[activeproc]=gcbg[active];
  216.     gcfg[activeproc]=gcfg[active];
  217.     gcbg[activeinterval]=gcbg[inplace];
  218.     gcfg[activeinterval]=gcfg[inplace];
  219.    
  220.     c.red=255*257;
  221.     c.green=250*257;
  222.     c.blue=173*257;
  223.     gdk_gc_set_rgb_fg_color(gcbg[normal],&c);
  224.    
  225.     c.red=97*257;
  226.     c.green=78*257;
  227.     c.blue=0*257;
  228.     gdk_gc_set_rgb_fg_color(gcfg[normal],&c);
  229.    
  230.     c.red=255*257;
  231.     c.green=255*257;
  232.     c.blue=255*257;
  233.     gdk_gc_set_rgb_fg_color(gcbg[active],&c);  
  234.    
  235.     c.red=118*257;
  236.     c.green=0*257;
  237.     c.blue=0*257;  
  238.     gdk_gc_set_rgb_fg_color(gcfg[active],&c);
  239.        
  240.     c.red=205*257;
  241.     c.green=188*257;
  242.     c.blue=0*257;  
  243.     gdk_gc_set_rgb_fg_color(gcbg[inplace],&c);
  244.    
  245.     c.red=0*257;
  246.     c.green=0*257;
  247.     c.blue=0*257;  
  248.     gdk_gc_set_rgb_fg_color(gcfg[inplace],&c);
  249.    
  250.     c.red=246*255;
  251.     c.green=197*255;
  252.     c.blue=0*255;
  253.     gdk_gc_set_rgb_fg_color(gcbg[inheap],&c);
  254.    
  255.     c.red=97*257;
  256.     c.green=78*257;
  257.     c.blue=0*257;
  258.     gdk_gc_set_rgb_fg_color(gcfg[inheap],&c);
  259.  
  260.     c.red=255*257;
  261.     c.green=255*257;
  262.     c.blue=255*257;
  263.     gdk_gc_set_rgb_fg_color(gcbg[activeinplace],&c);   
  264.    
  265.     c.red=97*257;
  266.     c.green=78*257;
  267.     c.blue=0*257;
  268.     gdk_gc_set_rgb_fg_color(gcfg[activeinplace],&c);
  269.    
  270.     c.red=169*257;
  271.     c.green=255*257;
  272.     c.blue=142*257;
  273.     gdk_gc_set_rgb_fg_color(gcbg[processed],&c);   
  274.    
  275.     c.red=0*257;
  276.     c.green=0*257;
  277.     c.blue=0*257;
  278.     gdk_gc_set_rgb_fg_color(gcfg[processed],&c);
  279.    
  280. }
  281.  
  282. void init_sort()
  283. {
  284.     phase=0;
  285.     hi=1;
  286.     hj=1;
  287.     finished=2;
  288.     clrneed=1;
  289.     heapsort(arrv);
  290.     g_timeout_add(SORTDELAY,(GSourceFunc) visualize,actionqueue);
  291. }
  292.  
  293. void init_legend()
  294. {
  295.     int i;
  296.     element e;
  297.     legx=-1;
  298.     legy=-1;
  299.     legendshowcnt=0;
  300.     for(i=0;i<STATECNT;i++)
  301.         if(legendshow[i]) legendshowcnt++;
  302.     legendheight=LEGENDINNEROFFSETY+2*RAD*legendshowcnt+GAP*(legendshowcnt-1)+LEGENDINNEROFFSETY+LEGENDHEADERHEIGHT;
  303.     legend=gdk_pixmap_new(window->window,LEGENDWIDTH+2,legendheight+2,-1);
  304.     gdk_draw_rectangle(legend,window->style->bg_gc[GTK_WIDGET_STATE(window)],TRUE,0,0,LEGENDWIDTH+2,legendheight+2);
  305.  
  306.     draw_text_in_center(LEGENDHEADER,window,legend,window->style->black_gc,LEGENDWIDTH/2,LEGENDHEADERHEIGHT/2);
  307.     gdk_draw_rectangle(legend,window->style->white_gc,FALSE,1,LEGENDHEADERHEIGHT,LEGENDWIDTH-1,legendheight-LEGENDHEADERHEIGHT-1);
  308.     gdk_draw_rectangle(legend,window->style->black_gc,FALSE,2,LEGENDHEADERHEIGHT+1,LEGENDWIDTH-1,legendheight-LEGENDHEADERHEIGHT-1);
  309.     e.linecoord.x=LEGENDINNEROFFSETX;
  310.     e.linecoord.y=LEGENDINNEROFFSETY+LEGENDHEADERHEIGHT;
  311.     e.treecoord.x=LEGENDINNEROFFSETX+2*RAD+5;
  312.     e.treecoord.y=LEGENDINNEROFFSETY+LEGENDHEADERHEIGHT;
  313.     e.value=00;
  314.  
  315.     for(i=0;i<STATECNT;i++)
  316.     {
  317.         if(!legendshow[i]) continue;
  318.         e.state=i;
  319.         draw_element(window,legend,&e);
  320.         draw_text_in_center_y(legendtext[i],window,legend,window->style->black_gc,e.linecoord.x+4*RAD+2*GAP+LEGENDINNEROFFSETX,e.linecoord.y+RAD);
  321.         e.linecoord.y+=2*RAD+GAP;
  322.         e.treecoord.y+=2*RAD+GAP;
  323.     }
  324. }
  325.  
  326. gboolean visualize(gpointer data)
  327. {
  328.     action cur;
  329.     while(actionqueue)
  330.     {
  331.         cur=*((action*) actionqueue->data);
  332.         free(actionqueue->data);
  333.         actionqueue=g_slist_remove(actionqueue,actionqueue->data);
  334.         switch(cur.type)
  335.         {
  336.         case acsleep:
  337.             g_timeout_add(cur.param.time,(GSourceFunc) visualize,actionqueue);
  338.             return FALSE;
  339.         case acswap:
  340.             swapvis(cur.param.swap.id1,cur.param.swap.id2);
  341.             return FALSE;
  342.         case acchangestate:
  343.             el[cur.param.chgst.id].state=cur.param.chgst.state;
  344.             draw_element(window,window->window,&(el[cur.param.chgst.id]));
  345.             break;
  346.         case acchangephase:
  347.             phase=cur.param.phase;
  348.             displayphasetxt();
  349.             break;
  350.         }
  351.     }
  352.     return FALSE;
  353. }
  354.  
  355. gboolean expose_event(GtkWidget *w, GdkEvent *e, gpointer data)
  356. {
  357.     int i;
  358.     displayphasetxt();
  359.     draw_legend();
  360.     for(i=0;i<N;i++)
  361.     {
  362.         draw_element(w,w->window,&el[i]);
  363.     }
  364.     return TRUE;
  365. }
  366.  
  367. GdkPoint gettreecoord(int n,int maxh)
  368. {
  369.     GdkPoint res;
  370.     int h;
  371.     for(h=0;(1<<h)<=n+1;h++);
  372.     res.x=TREEOFFSETX+((1<<(maxh-h))-1)*(2*RAD+GAP)/2.0+( (1<<(maxh-h))*GAP+((1<<(maxh-h)))*2*RAD)*(n-(1<<(h-1))+1);
  373.     res.y=TREEOFFSETY+(h-1)*(2*RAD+GAP);
  374.     return res;
  375. }
  376.  
  377. GdkPoint getlinecoord(int n)
  378. {
  379.     GdkPoint res;
  380.     res.x=LINEOFFSETX+(2*RAD+GAP)*n;
  381.     res.y=LINEOFFSETY;
  382.     return res;
  383. }
  384.  
  385. void draw_element(GtkWidget *w,GdkDrawable *d, element *e)
  386. {
  387.     char s[10];
  388.     sprintf(s,"%.2d",e->value);
  389. //  gdk_draw_arc(d,gcbg[e->state],TRUE,e->linecoord.x,e->linecoord.y,2*RAD,2*RAD,0,64*360);
  390. //  gdk_draw_arc(d,gcfg[e->state],FALSE,e->linecoord.x,e->linecoord.y,2*RAD,2*RAD,0,64*360);
  391.     gdk_draw_rectangle(d,gcbg[e->state],TRUE,e->linecoord.x,e->linecoord.y,2*RAD,2*RAD);
  392.     gdk_draw_rectangle(d,gcfg[e->state],FALSE,e->linecoord.x,e->linecoord.y,2*RAD,2*RAD);
  393.     draw_text_in_center(s,w,d,gcfg[e->state],e->linecoord.x+RAD,e->linecoord.y+RAD);
  394. //  gdk_draw_rectangle(d,gcbg[e->state],TRUE,e->treecoord.x,e->treecoord.y,2*RAD,2*RAD);
  395. //  gdk_draw_rectangle(d,gcfg[e->state],FALSE,e->treecoord.x,e->treecoord.y,2*RAD,2*RAD);
  396. #if HEAPSORTA || HEAPSORTB
  397.     gdk_draw_arc(d,gcbg[e->state],TRUE,e->treecoord.x,e->treecoord.y,2*RAD,2*RAD,0,64*360);
  398.     gdk_draw_arc(d,gcfg[e->state],FALSE,e->treecoord.x,e->treecoord.y,2*RAD,2*RAD,0,64*360);
  399.     draw_text_in_center(s,w,d,gcfg[e->state],e->treecoord.x+RAD,e->treecoord.y+RAD);
  400. #endif
  401. }
  402.  
  403. void draw_text_in_center(gchar * text, GtkWidget *w, GdkDrawable *d, GdkGC *gc, gint xc, gint yc)
  404. {
  405.     PangoContext *context=gtk_widget_create_pango_context(w);
  406.     PangoLayout *layout= pango_layout_new(context);
  407.     gint width,height;
  408.     pango_layout_set_text(layout,text,-1);
  409.     pango_layout_get_pixel_size(layout,&width,&height);
  410.     gdk_draw_layout (d,gc,xc-width/2,yc-height/2,layout);
  411.     g_object_unref(context); g_object_unref(layout);
  412. }
  413.  
  414. void draw_text_in_center_y(gchar * text, GtkWidget *w, GdkDrawable *d, GdkGC *gc, gint x, gint yc)
  415. {
  416.     PangoContext *context=gtk_widget_create_pango_context(w);
  417.     PangoLayout *layout= pango_layout_new(context);
  418.     gint width,height;
  419.     pango_layout_set_text(layout,text,-1);
  420.     pango_layout_get_pixel_size(layout,&width,&height);
  421.     gdk_draw_layout (d,gc,x,yc-height/2,layout);
  422.     g_object_unref(context); g_object_unref(layout);
  423. }
  424.  
  425. void draw_legend()
  426. {
  427.     if(legx>0&&legy>0)
  428.         gdk_window_clear_area(window->window,legx,legy,legx+LEGENDWIDTH,legy+legendheight);
  429.     legx=window->allocation.width-LEGENDOFFSETX-LEGENDWIDTH;
  430.     legy=LEGENDY;
  431.     gdk_draw_drawable(window->window,window->style->fg_gc[GTK_WIDGET_STATE(window)],legend,0,0,legx,legy,-1,-1);
  432. }
  433.  
  434. void displayphasetxt()
  435. {
  436.     gdk_window_clear_area(window->window,0,0,window->allocation.width,2*CENTERTEXTOFFSETY+2);
  437.     draw_text_in_center(phasetxt[phase],window,window->window,window->style->white_gc,window->allocation.width/2+SHADOWOFFSET,CENTERTEXTOFFSETY+SHADOWOFFSET);
  438.     draw_text_in_center(phasetxt[phase],window,window->window,window->style->black_gc,window->allocation.width/2,CENTERTEXTOFFSETY);
  439.     draw_text_in_center_y(CENTERTEXTHEADER,window,window->window,window->style->black_gc,10,CENTERTEXTOFFSETY);
  440. }
  441.  
  442. void startmoving(elpath *p1,elpath *p2)
  443. {
  444.     finished=0;
  445.     g_timeout_add(MOVEDELAY,(GSourceFunc) move,(gpointer) p1);
  446.     g_timeout_add(MOVEDELAY,(GSourceFunc) move,(gpointer) p2);
  447. }
  448.  
  449. void insertswap(int idx1,int idx2)
  450. {
  451.     action *n=(action*) malloc(sizeof(action));
  452.     n->type=acswap;
  453.     n->param.swap.id1=idx1;
  454.     n->param.swap.id2=idx2;
  455.     actionqueue=g_slist_append(actionqueue,n);
  456. }
  457.  
  458. void insertchangestate(int idx,elstate newstate)
  459. {
  460.     action *n=(action*) malloc(sizeof(action));
  461.     n->type=acchangestate;
  462.     n->param.chgst.id=idx;
  463.     n->param.chgst.state=newstate;
  464.     actionqueue=g_slist_append(actionqueue,n);
  465. }
  466.  
  467. void insertsleep(int t)
  468. {
  469.     action *n=(action*) malloc(sizeof(action));
  470.     n->type=acsleep;
  471.     n->param.time=t;
  472.     actionqueue=g_slist_append(actionqueue,n);
  473. }
  474.  
  475. void insertchangephase(int np)
  476. {
  477.     action *n=(action*) malloc(sizeof(action));
  478.     n->type=acchangephase;
  479.     n->param.phase=np;
  480.     actionqueue=g_slist_append(actionqueue,n);
  481. }
  482.  
  483. gboolean move(elpath* p)
  484. {
  485.     int i;
  486.     GdkPoint lc,tc;
  487.     lc=el[p->elnum].linecoord;
  488.     tc=el[p->elnum].treecoord;
  489.     gdk_window_clear_area(window->window,el[p->elnum].linecoord.x,el[p->elnum].linecoord.y,2*RAD+1,2*RAD+1);
  490.     gdk_window_clear_area(window->window,el[p->elnum].treecoord.x,el[p->elnum].treecoord.y,2*RAD+1,2*RAD+1);
  491.     if(p->linecurve!=NULL)
  492.     {
  493.         el[p->elnum].linecoord=*((GdkPoint*) p->linecurve->data);
  494.         free(p->linecurve->data);
  495.         p->linecurve=g_list_remove(p->linecurve,p->linecurve->data);
  496.     }
  497.     if(p->treecurve!=NULL)
  498.     {
  499.         el[p->elnum].treecoord=*((GdkPoint*) p->treecurve->data);
  500.         free(p->treecurve->data);
  501.         p->treecurve=g_list_remove(p->treecurve,p->treecurve->data);
  502.     }
  503.     for(i=0;i<N;i++)
  504.     {
  505.         if(i==p->elnum) continue;
  506.         if((el[i].linecoord.x+2*RAD+1>=lc.x&&el[i].linecoord.x<=lc.x+2*RAD+1&&el[i].linecoord.y+2*RAD+1>=lc.y&&el[i].linecoord.y<=lc.y+2*RAD+1)||
  507.            (el[i].treecoord.x+2*RAD+1>=tc.x&&el[i].treecoord.x<=tc.x+2*RAD+1&&el[i].treecoord.y+2*RAD+1>=tc.y&&el[i].treecoord.y<=tc.y+2*RAD+1))
  508.         {
  509.             draw_element(window,window->window,&el[i]);
  510.         }
  511.     }
  512.     if(p->linecurve==NULL&&p->treecurve==NULL)
  513.     {
  514.         switch(el[p->elnum].state)
  515.         {
  516.             case activeinplace:
  517.                 el[p->elnum].state=inplace;
  518.                 break;
  519.             case activeinheap:
  520.                 el[p->elnum].state=inheap;
  521.                 break;
  522.             case activeproc:
  523.                 el[p->elnum].state=processed;
  524.                 break;
  525.             default:
  526.                 el[p->elnum].state=normal;
  527.         }
  528.     }
  529.     draw_element(window,window->window,&el[p->elnum]);
  530.     if(p->linecurve==NULL&&p->treecurve==NULL)
  531.     {
  532.         finished++;
  533.         free(p);
  534.         if(finished==2&&phase==1)
  535.             phase=2;
  536.         if(finished==2)
  537.             g_timeout_add(SORTDELAY,(GSourceFunc) visualize,NULL);
  538.         return FALSE;
  539.     }
  540.     return TRUE;
  541. }
  542.  
  543. void swap(int idx1,int idx2)
  544. {
  545.     int t=arrv[idx1];
  546.     arrv[idx1]=arrv[idx2];
  547.     arrv[idx2]=t;
  548.     insertswap(idx1,idx2);
  549. }
  550.  
  551. void swapvis(int idx1,int idx2)
  552. {
  553.     elpath *p1,*p2;
  554.     int i;
  555.     element t;
  556.     t=el[idx1];
  557.     el[idx1]=el[idx2];
  558.     el[idx2]=t;
  559.     p1=(elpath*) malloc(sizeof(elpath));
  560.     p2=(elpath*) malloc(sizeof(elpath));
  561.     *p1=makepath(idx1,el[idx1].linecoord,el[idx2].linecoord,-RISE,VCOUNT,HCOUNT,VCOUNT,el[idx1].treecoord,el[idx2].treecoord,2*VCOUNT+HCOUNT-2);
  562.     *p2=makepath(idx2,el[idx2].linecoord,el[idx1].linecoord,+RISE,VCOUNT,HCOUNT,VCOUNT,el[idx2].treecoord,el[idx1].treecoord,2*VCOUNT+HCOUNT-2);
  563.     switch(el[idx1].state)
  564.     {
  565.         case inplace:
  566.             el[idx1].state=activeinplace;
  567.             break;
  568.         case inheap:
  569.             el[idx1].state=activeinheap;
  570.             break;
  571.         case processed:
  572.             el[idx1].state=activeproc;
  573.             break;
  574.         default:
  575.             el[idx1].state=active;
  576.     }
  577.     switch(el[idx2].state)
  578.     {
  579.         case inplace:
  580.             el[idx2].state=activeinplace;
  581.             break;
  582.         case inheap:
  583.             el[idx2].state=activeinheap;
  584.             break;
  585.         case processed:
  586.             el[idx2].state=activeproc;
  587.             break;
  588.         default:
  589.             el[idx2].state=active;
  590.     }
  591.    
  592.     startmoving(p1,p2);
  593. }
  594.  
  595. void genline(GdkPoint s, GdkPoint t,int cnt,GList ** l)
  596. {
  597.     GdkPoint m,*c;
  598.     int i;
  599.     m=s;
  600.     for(i=1;i<cnt;i++)
  601.     {
  602.         c=(GdkPoint*) malloc(sizeof(GdkPoint));
  603.         *c=m;
  604.         *l=g_list_append(*l,c);
  605.         m.x=s.x+i*1.0*(t.x-s.x)/(cnt-1);
  606.         m.y=s.y+i*1.0*(t.y-s.y)/(cnt-1);
  607.     }
  608. }
  609.  
  610. elpath makepath(gint idx,GdkPoint listb,GdkPoint liste, gint dy, gint listc1, gint listc2,gint listc3,GdkPoint treep1,GdkPoint treep2, gint treec)
  611. {
  612.     GdkPoint s,t,*c;
  613.     elpath res;
  614.     double tx,ty;
  615.     GList *listl=NULL,*treel=NULL;
  616.     int i;
  617.     s=t=listb;
  618.     t.y+=dy;
  619.     genline(s,t,listc1,&listl);
  620.    
  621.     s=listb;
  622.     s.y+=dy;
  623.     t=liste;
  624.     t.y+=dy;
  625.     genline(s,t,listc2,&listl);
  626.    
  627.     s=liste;
  628.     s.y+=dy;
  629.     t=liste;
  630.     genline(s,t,listc3,&listl);
  631.    
  632.     c=(GdkPoint*) malloc(sizeof(GdkPoint));
  633.     *c=t;
  634.     listl=g_list_append(listl,c);
  635.    
  636.     genline(treep1,treep2,treec,&treel);
  637.    
  638.     c=(GdkPoint*) malloc(sizeof(GdkPoint));
  639.     *c=treep2;
  640.     treel=g_list_append(treel,c);
  641.    
  642.     res.linecurve=listl;
  643.     res.treecurve=treel;
  644.     res.elnum=idx;
  645.    
  646.     return res;
  647. }
  648.  
  649. void upHeap(int* array, int i)
  650. {
  651.     if(i>0)
  652.     {
  653.         if(array[i]>array[(i-1)/2])
  654.         {
  655.             swap(i,(i-1)/2);
  656.             upHeap(array,(i-1)/2);
  657.         }
  658.     }
  659. }
  660.  
  661. void downHeap(int* array, int i,int cnt)
  662. {
  663.     int child=i*2+1;
  664.     if(child<cnt)
  665.     {
  666.         if(child+1<cnt&&array[child]<array[child+1])
  667.             child++;
  668.         if(array[child]>array[i])
  669.         {
  670.             swap(child,i);
  671.             downHeap(array,child,cnt);
  672.         }
  673.     }
  674. }
  675.  
  676. void heapsort(int *array)
  677. {
  678.     int i;
  679. #ifdef HEAPSORTA
  680.     insertchangestate(0,inheap);
  681.     insertsleep(SORTDELAY);
  682.     for(i=1;i<N;i++)
  683.     {
  684.         insertchangestate(i,inheap);
  685.         insertsleep(REDRAWDELAY);
  686.         upHeap(array,i);
  687.         insertsleep(SORTDELAY);
  688.     }
  689.     for(i=0;i<N;i++)
  690.     {
  691.         insertchangestate(i,normal);
  692.     }
  693.     insertsleep(SORTDELAY);
  694.     for(i=N-1;i>0;i--)
  695.     {
  696.         insertchangephase(1);
  697.         insertchangestate(0,inplace);
  698.         swap(i,0);
  699.         insertchangephase(2);
  700.         insertsleep(REDRAWDELAY);
  701.         downHeap(array,0,i);
  702.         insertsleep(SORTDELAY);
  703.     }
  704.     insertchangestate(0,inplace);
  705.     insertchangephase(3);
  706. #elif HEAPSORTB
  707.     for(i=N-1;2*i+1>=N;i--)
  708.     {
  709.         insertchangestate(i,processed);
  710.     }
  711.     for(i=N/2-1;i>=0;i--)
  712.     {
  713.         insertchangestate(i,processed);
  714.         downHeap(array,i,N);
  715.         insertsleep(SORTDELAY);
  716.     }
  717.     for(i=0;i<N;i++)
  718.     {
  719.         insertchangestate(i,normal);
  720.     }
  721.     insertsleep(SORTDELAY);
  722.     for(i=N-1;i>0;i--)
  723.     {
  724.         insertchangephase(1);
  725.         insertchangestate(0,inplace);
  726.         swap(i,0);
  727.         insertchangephase(2);
  728.         insertsleep(REDRAWDELAY);
  729.         downHeap(array,0,i);
  730.         insertsleep(SORTDELAY);
  731.     }
  732.     insertchangestate(0,inplace);
  733.     insertchangephase(3);
  734. #elif SHELLSORT
  735. int h = 1;
  736. int prev;
  737.  
  738.    while ( h <= N / 9 )
  739.     h = 3 * h + 1;
  740.  
  741.    while ( h > 0 ) {
  742.      for ( i = h; i < N; i++ ) {
  743.      int k;
  744.         for(k=i;k>=0;k-=h)
  745.             insertchangestate(k,processed);
  746.         insertsleep(REDRAWDELAY);
  747.        int j, save = array[i];
  748.        prev=i;
  749.  
  750.        for ( j = i; j >= h && array[j - h] > save; j -= h )
  751.        {
  752.          swap(j,j-h);
  753.         }
  754.      for(k=i;k>=0;k-=h)
  755.             insertchangestate(k,normal);
  756.         insertsleep(REDRAWDELAY);
  757.      }
  758.  
  759.      h /= 3;
  760.    }
  761. #elif BUBBLESORT
  762. for(i=0;i<N;i++)
  763. {
  764.     int j;
  765.     for(j=0;j<N-i-1;j++)
  766.     {
  767.         insertchangestate(j,processed);
  768.         insertchangestate(j+1,processed);
  769.         insertsleep(REDRAWDELAY);
  770.         if(array[j]>array[j+1])
  771.         {
  772.             swap(j,j+1);
  773.         }
  774.         insertchangestate(j,normal);
  775.         insertchangestate(j+1,normal);
  776.         insertsleep(REDRAWDELAY);
  777.     }
  778.     insertchangestate(j,inplace);
  779.     insertsleep(REDRAWDELAY);
  780. }
  781. #elif QUICKSORT
  782. quicksort(N-1,array,0);
  783. #endif
  784. }
  785.  
  786. void quicksort(int n,int *a,int offset)
  787. {
  788.     int i=0,j=n,k;
  789.     int p=a[n>>1];
  790.     for(k=0;k<=n;k++)
  791.     {
  792.         insertchangestate(k+offset,activeinterval);
  793.     }
  794.     insertsleep(REDRAWDELAY);
  795.     insertchangestate(i+offset,processed);
  796.     insertchangestate(j+offset,processed);
  797.     do
  798.     {
  799.         while(a[i]<p)
  800.         {
  801.             insertchangestate(i+offset,activeinterval);
  802.             i++;
  803.             if(i<=j)insertchangestate(i+offset,processed);
  804.             insertsleep(REDRAWDELAY);
  805.         }
  806.         insertsleep(REDRAWDELAY);
  807.         while(a[j]>p)
  808.         {
  809.             insertchangestate(j+offset,activeinterval);
  810.             j--;
  811.             if(i<=j)insertchangestate(j+offset,processed);
  812.             insertsleep(REDRAWDELAY);
  813.         }
  814.         insertsleep(REDRAWDELAY);
  815.         if(i<=j)
  816.         {
  817.             swap(offset+i,offset+j);
  818.             insertchangestate(i+offset,activeinterval);
  819.             insertchangestate(j+offset,activeinterval);
  820.             i++;
  821.             j--;
  822.             if(i<=j)
  823.             {
  824.                 insertchangestate(i+offset,processed);
  825.                 insertchangestate(j+offset,processed);
  826.                 insertsleep(REDRAWDELAY);
  827.             }
  828.         }
  829.     }
  830.     while(i<=j);
  831.     for(k=0;k<=n;k++)
  832.     {
  833.         insertchangestate(k+offset,normal);
  834.     }  
  835.     if(j>0) quicksort(j,a,offset);
  836.     if(i<n) quicksort(n-i,a+i,offset+i);
  837. }
  838.  
  839. gboolean delete_event(GtkWidget *w,GdkEvent *e, gpointer data)
  840. {
  841.     gtk_main_quit();
  842.     return TRUE;
  843. }
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!