sortings

---/sorts.h/---
#ifndef COURSEWORK_H
#define COURSEWORK_H

#include <gtk/gtk.h>

// координаты левого верхнего угла прямоугольника,в котором будет нарисовано дерево
#define TREEOFFSETX 10
#define TREEOFFSETY 70

// координаты левого верхнего угла прямоугольника, в котором будет нарисован массив
#define LINEOFFSETX 20
#define LINEOFFSETY 300
// на сколько вверх и вниз будут выдвигаться элементы массива при обменах
#define RISE 30

// сколько должно быть точек в пути при горизонтальном и вертикальном перемещении объекта
#define VCOUNT 10
#define HCOUNT 20

// отступ относительно верха окна для текста о текущем действии
#define CENTERTEXTOFFSETY 20
#define CENTERTEXTHEADER "Текущее действие:"
// на каком расстоянии от текста нужно рисовать тень
#define SHADOWOFFSET -1

// настройки для рисования легенды:
// отступ, на котором будет рисоватся легенда, относительно правого края
#define LEGENDOFFSETX 5
// положение легенды относительно верха окна
#define LEGENDY 60
// координаты левого верхнего угла прямоугольника, в котором будет рисоваться легенда
#define LEGENDINNEROFFSETX 10
#define LEGENDINNEROFFSETY 10
// ширина легенды
#define LEGENDWIDTH 290
// высота, которая отводится под заголовок в легенде
#define LEGENDHEADERHEIGHT 20
#define LEGENDHEADER "Легенда"

// радиус окружности / половина ширины прямоугольника элемента массива и дерева
#define RAD 14
// расстояние между элементами в массиве и на последнем уровне дерева
#define GAP 0

// количество элементов в массивах
#define N 26
// массив будет заполнятся случайными значениями из диапазона 0..MOD-1
#define MOD 100

// количество состояний, в которых может находится каждый элемент
#define STATECNT 9

// задержки между событиями:
// между перемещениями элементов
#define MOVEDELAY 10
// после отрисовки объектов
#define REDRAWDELAY 300
// промежутки между вызовом визуализатора и некоторыми фазами сортировки
#define SORTDELAY 400

// ширина и высота окна
#define WIDTH 800
#define HEIGHT 360

typedef struct elpath elpath;
typedef struct element element;
typedef struct action action;
typedef enum elstate elstate;
typedef enum actiontype actiontype;
typedef union actionparameter actionparameter;

// возможные состояния вершин
enum elstate
{
    normal,
    inplace,
    inheap,
    processed,
    active,
    activeinplace,
    activeinheap,
    activeproc,
    activeinterval
};

// варианты действий для визуализатора: подождать, обменять два элемента, поменять состояние элемента и сменить название фазы сортировки
enum actiontype
{
    acsleep,
    acswap,
    acchangestate,
    acchangephase
};

// параметры для каждого из действий: сколько ждать, какие элементы менять, какое состояние какому элементу установить и номер фазы
union actionparameter
{
    int time;
    struct
    {
        int id1,id2;
    } swap;
    struct
    {
        int id;
        elstate state;
    } chgst;
    int phase;
};

// структура, содержащая информацию о номере элемента, который нужно перемещать и по какой траектории двигать его в массиве и в дереве
struct elpath
{
    GList *linecurve,*treecurve;
    int elnum;
};

// элемент это совокупность точки в дереве и массиве, значения, по которому идёт сортировка и состояния, в котором он находится
struct element
{
    GdkPoint linecoord,treecoord;
    int value;
    elstate state;
};

// структура, описывающая действия для визуализатора
struct action
{
    actiontype type;
    actionparameter param;
};

void init_gc();
void init_sort();
void init_legend();
void draw_element(GtkWidget *w,GdkDrawable *d, element *e);
void draw_text_in_center(gchar * text, GtkWidget *w, GdkDrawable *d, GdkGC *gc, gint xc, gint yc);
void draw_text_in_center_y(gchar * text, GtkWidget *w, GdkDrawable *d, GdkGC *gc, gint x, gint yc);
void draw_legend();
void startmoving(elpath *p1,elpath *p2);
void swap(int idx1,int idx2);
void swapvis(int idx1,int idx2);
void displayphasetxt();
void genline(GdkPoint s, GdkPoint t,int cnt,GList ** l);
void insertswap(int idx1,int idx2);
void insertchangestate(int idx,elstate newstate);
void insertsleep(int t);
void insertchangephase(int np);
void sort(int *array);
void quicksort(int n,int *a,int offset);
GdkPoint getlinecoord(int n);
GdkPoint gettreecoord(int n,int maxh);
elpath makepath(gint idx,GdkPoint listb,GdkPoint liste, gint dy, gint listc1, gint listc2,gint listc3,GdkPoint treep1,GdkPoint treep2, gint treec);
gboolean move(elpath* p);
gboolean expose_event(GtkWidget *w,GdkEvent *e, gpointer data);
gboolean delete_event(GtkWidget *w,GdkEvent *e, gpointer data);
gboolean visualize(gpointer data);


#endif
---/sorts.c/---
// По умолчанию компилируется визуализатор QuickSort.
// Чтобы скомпилировать другие визуализаторы, нужно определить один из следующих идентификаторов:
// HEAPSORTA - пирамидальная сортировка, первая фаза которой заключается в проходе по массиву от начала к концу и просеивании элемента вверх
// HEAPSORTB - пирамидальная сортировка, первая фаза которой заключается в проходе по массиву от конца к началу и просеивании элемента вниз
// SHELLSORT - сортировка шелла
// BUBBLESORT - пузырьковая сортировка

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <gtk/gtk.h>
#include "sorts.h"

GtkWidget *window;
// буффер, в котором будет хранится уже нарисованная легенда
GdkPixmap *legend;
// настройки цветов для рисования фона и переднего плана
GdkGC *gcbg[STATECNT],*gcfg[STATECNT];
// очередь, в которую будут добавляться действия, которые будет необходимо визуализировать; заполняется по мере обычной сортировки массива
GSList *actionqueue=NULL;
// массивы элементов и чисел, которые будут упорядочиваться
element el[N];
int arrv[N];

// в зависимости от того, какую сортировку будет визуализировать нам необходимо выводить описания фаз
#if HEAPSORTA || HEAPSORTB
char phasetxt[4][100]={"Построение кучи","Исключение наибольшего элемента","Восстановление кучи","Сортировка окончена"};
#else
char phasetxt[4][100]={"Сортировка","","","Сортировка окончена"};
#endif
// какие типы элементов будут показываться в легенде
#if HEAPSORTA
gboolean legendshow[STATECNT]={TRUE,TRUE,TRUE,FALSE,TRUE,TRUE,FALSE,FALSE,FALSE};
#elif HEAPSORTB
gboolean legendshow[STATECNT]={TRUE,TRUE,FALSE,TRUE,TRUE,TRUE,FALSE,FALSE,FALSE};
#elif SHELLSORT
gboolean legendshow[STATECNT]={TRUE,FALSE,FALSE,TRUE,TRUE,FALSE,FALSE,FALSE,FALSE};
#elif BUBBLESORT
gboolean legendshow[STATECNT]={TRUE,TRUE,FALSE,TRUE,TRUE,FALSE,FALSE,FALSE,FALSE};
#else
gboolean legendshow[STATECNT]={TRUE,FALSE,FALSE,TRUE,TRUE,FALSE,FALSE,FALSE,TRUE};
#endif

// высота легенды с учётом заголовка и описания элементов
int legendheight;
// описание состояний в легенде
char legendtext[STATECNT][100]={"Обычный","На своём месте","В куче","Обрабатывается","Перемещается","Перемещается на своё место","","","Текущий интервал"};
// номер текущей фазы
int phase;
// сколько элементов ещё нужно переместить
int finished;
// координаты левого верхнего угла легенды
int legx,legy;

int main(int argc,char * argv[])
{
    int i;
    int maxh;

    gtk_init(&argc,&argv);
    // создаём окно и задаём его размер
    window=gtk_window_new(GTK_WINDOW_TOPLEVEL);
    gtk_widget_set_size_request(window,WIDTH,HEIGHT);

    srand(time(0));
    // считаем высоту дерева
    for(maxh=0;(1<<maxh)<=N;maxh++);
    // генерируем массив элементов
    for(i=0;i<N;i++)
    {
        el[i].linecoord=getlinecoord(i);
        el[i].treecoord=gettreecoord(i,maxh);
        arrv[i]=el[i].value=rand()%MOD;
        el[i].state=normal;
    }

    gtk_widget_show(window);

    // подготавливаем программу к визуализации
    init_gc();
    init_sort();
    init_legend();
    g_signal_connect(G_OBJECT(window),"delete-event",G_CALLBACK(delete_event),NULL);
    g_signal_connect(G_OBJECT(window),"expose-event",G_CALLBACK(expose_event),NULL);

    // прорисовываем содержимое окна
    expose_event(window,NULL,NULL);

    // запускаем бесконечный цикл
    gtk_main();
    return 0;
}


void init_gc() // создаём цвета, которыми мы будем рисовать элементы в различных состояниях
{
    GdkColor c;
    gcbg[normal]=gdk_gc_new(window->window);
    gcfg[normal]=gdk_gc_new(window->window);
    gcbg[active]=gdk_gc_new(window->window);
    gcfg[active]=gdk_gc_new(window->window);
    gcbg[inplace]=gdk_gc_new(window->window);
    gcfg[inplace]=gdk_gc_new(window->window);
    gcbg[activeinheap]=gcbg[active];
    gcfg[activeinheap]=gcfg[active];
    gcbg[inheap]=gdk_gc_new(window->window);
    gcfg[inheap]=gdk_gc_new(window->window);
    gcbg[activeinplace]=gdk_gc_new(window->window);
    gcfg[activeinplace]=gdk_gc_new(window->window);
    gcbg[inheap]=gdk_gc_new(window->window);
    gcfg[inheap]=gdk_gc_new(window->window);
    gcbg[activeinplace]=gdk_gc_new(window->window);
    gcfg[activeinplace]=gdk_gc_new(window->window);
    gcbg[processed]=gdk_gc_new(window->window);
    gcfg[processed]=gdk_gc_new(window->window);
    gcbg[activeproc]=gcbg[active];
    gcfg[activeproc]=gcfg[active];
    gcbg[activeinterval]=gcbg[inplace];
    gcfg[activeinterval]=gcfg[inplace];

    c.red=255*257;
    c.green=250*257;
    c.blue=173*257;
    gdk_gc_set_rgb_fg_color(gcbg[normal],&c);

    c.red=97*257;
    c.green=78*257;
    c.blue=0*257;
    gdk_gc_set_rgb_fg_color(gcfg[normal],&c);

    c.red=255*257;
    c.green=255*257;
    c.blue=255*257;
    gdk_gc_set_rgb_fg_color(gcbg[active],&c);

    c.red=118*257;
    c.green=0*257;
    c.blue=0*257;
    gdk_gc_set_rgb_fg_color(gcfg[active],&c);

    c.red=205*257;
    c.green=188*257;
    c.blue=0*257;
    gdk_gc_set_rgb_fg_color(gcbg[inplace],&c);

    c.red=0*257;
    c.green=0*257;
    c.blue=0*257;
    gdk_gc_set_rgb_fg_color(gcfg[inplace],&c);

    c.red=246*255;
    c.green=197*255;
    c.blue=0*255;
    gdk_gc_set_rgb_fg_color(gcbg[inheap],&c);

    c.red=97*257;
    c.green=78*257;
    c.blue=0*257;
    gdk_gc_set_rgb_fg_color(gcfg[inheap],&c);

    c.red=255*257;
    c.green=255*257;
    c.blue=255*257;
    gdk_gc_set_rgb_fg_color(gcbg[activeinplace],&c);

    c.red=97*257;
    c.green=78*257;
    c.blue=0*257;
    gdk_gc_set_rgb_fg_color(gcfg[activeinplace],&c);

    c.red=169*257;
    c.green=255*257;
    c.blue=142*257;
    gdk_gc_set_rgb_fg_color(gcbg[processed],&c);

    c.red=0*257;
    c.green=0*257;
    c.blue=0*257;
    gdk_gc_set_rgb_fg_color(gcfg[processed],&c);

}

void init_sort() // подготавливаем визуализатор к работе
{
    // устанавливаем в качестве текущей фазы нулевую
    phase=0;
    // говорим, что все элементы перемещены
    finished=0;
    // сортируем массив arrv, чтобы заполнить очередь событий задержками, обменами и т.д.
    sort(arrv);
    // визуализируем очередь
    g_timeout_add(SORTDELAY,(GSourceFunc) visualize,NULL);
}

// создаёт легенду в буфере GdkPixmap* legend, инициализируем положение легенды
// и рассчитываем высоту легенды
void init_legend()
{
    int i;
    int legendshowcnt;
    element e;
    legx=-1;
    legy=-1;
    legendshowcnt=0;
    for(i=0;i<STATECNT;i++)
        if(legendshow[i]) legendshowcnt++;
    legendheight=LEGENDINNEROFFSETY+2*RAD*legendshowcnt+GAP*(legendshowcnt-1)+LEGENDINNEROFFSETY+LEGENDHEADERHEIGHT;
    legend=gdk_pixmap_new(window->window,LEGENDWIDTH+2,legendheight+2,-1);
    gdk_draw_rectangle(legend,window->style->bg_gc[GTK_WIDGET_STATE(window)],TRUE,0,0,LEGENDWIDTH+2,legendheight+2);

    draw_text_in_center(LEGENDHEADER,window,legend,window->style->black_gc,LEGENDWIDTH/2,LEGENDHEADERHEIGHT/2);
    gdk_draw_rectangle(legend,window->style->white_gc,FALSE,1,LEGENDHEADERHEIGHT,LEGENDWIDTH-1,legendheight-LEGENDHEADERHEIGHT-1);
    gdk_draw_rectangle(legend,window->style->black_gc,FALSE,2,LEGENDHEADERHEIGHT+1,LEGENDWIDTH-1,legendheight-LEGENDHEADERHEIGHT-1);
    e.linecoord.x=LEGENDINNEROFFSETX;
    e.linecoord.y=LEGENDINNEROFFSETY+LEGENDHEADERHEIGHT;
    e.treecoord.x=LEGENDINNEROFFSETX+2*RAD+5;
    e.treecoord.y=LEGENDINNEROFFSETY+LEGENDHEADERHEIGHT;
    e.value=00;

    for(i=0;i<STATECNT;i++)
    {
        if(!legendshow[i]) continue;
        e.state=i;
        draw_element(window,legend,&e);
        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);
        e.linecoord.y+=2*RAD+GAP;
        e.treecoord.y+=2*RAD+GAP;
    }
}

// визуализируем очередь actionqueue, последовательно доставая элементы из неё и обробатывая их
gboolean visualize(gpointer data)
{
    action cur;
    while(actionqueue) // пока очередь действий не пустая
    {
        cur=*((action*) actionqueue->data); //получаем действие из головы очереди
        free(actionqueue->data); // освобождаем память выделенную под действие
        actionqueue=g_slist_remove(actionqueue,actionqueue->data); //удаляем первый элемент списка
        switch(cur.type)
        {
        case acsleep:
            //если текущее действие - ждать, то мы добавляем ожидание и прекращаем выполнение этой функции
            g_timeout_add(cur.param.time,(GSourceFunc) visualize,actionqueue);
            return FALSE;
        case acswap:
            //если текущее действие - обмен, мы активируем функцию обмена двух элементов и прекращаем выполнение этой функции
            swapvis(cur.param.swap.id1,cur.param.swap.id2);
            return FALSE;
        case acchangestate:
            //если текущее действие - смена статуса, мы меняем его и перерисовываем элемент
            el[cur.param.chgst.id].state=cur.param.chgst.state;
            draw_element(window,window->window,&(el[cur.param.chgst.id]));
            break;
        case acchangephase:
            //если текущее действие - смена фазы, мы меняем номер текущей фазы и отображаем новый текст
            phase=cur.param.phase;
            displayphasetxt();
            break;
        }
    }
    return FALSE;
}

gboolean expose_event(GtkWidget *w, GdkEvent *e, gpointer data) // если необходима перересовка, то перерисуем всё
{
    int i;
    displayphasetxt();
    draw_legend();
    for(i=0;i<N;i++)
    {
        draw_element(w,w->window,&el[i]);
    }
    return TRUE;
}

// получаем координаты вершины в дереве
GdkPoint gettreecoord(int n,int maxh)
{
    GdkPoint res;
    int h;
    // определяем слой, в котором находится вершина
    for(h=0;(1<<h)<=n+1;h++);
    // высчитываем по формуле координаты вершины
    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);
    res.y=TREEOFFSETY+(h-1)*(2*RAD+GAP);
    return res;
}

// получаем координаты вершины в массиве
GdkPoint getlinecoord(int n)
{
    GdkPoint res;
    res.x=LINEOFFSETX+(2*RAD+GAP)*n;
    res.y=LINEOFFSETY;
    return res;
}

// отрисовка элемента e в d, используя w для получения PangoContext в draw_text_in_center
void draw_element(GtkWidget *w,GdkDrawable *d, element *e)
{
    // печатаем число в массив s
    char s[10];
    sprintf(s,"%.2d",e->value);

    // рисуем элемент массива в виде прямоугольник с рамкой и текстом s
    gdk_draw_rectangle(d,gcbg[e->state],TRUE,e->linecoord.x,e->linecoord.y,2*RAD,2*RAD);
    gdk_draw_rectangle(d,gcfg[e->state],FALSE,e->linecoord.x,e->linecoord.y,2*RAD,2*RAD);
    draw_text_in_center(s,w,d,gcfg[e->state],e->linecoord.x+RAD,e->linecoord.y+RAD);
#if HEAPSORTA || HEAPSORTB
    // если происходит отрисовка дерева, то мы рисуем элемент дерева в виде окружности с рамкой и текстом s
    gdk_draw_arc(d,gcbg[e->state],TRUE,e->treecoord.x,e->treecoord.y,2*RAD,2*RAD,0,64*360);
    gdk_draw_arc(d,gcfg[e->state],FALSE,e->treecoord.x,e->treecoord.y,2*RAD,2*RAD,0,64*360);
    draw_text_in_center(s,w,d,gcfg[e->state],e->treecoord.x+RAD,e->treecoord.y+RAD);
#endif
}

// рисуем текст text в d при помощи графического контекста gc с центром в (xc,yc) используя w для получения PangoContext
void draw_text_in_center(gchar * text, GtkWidget *w, GdkDrawable *d, GdkGC *gc, gint xc, gint yc)
{
    PangoContext *context=gtk_widget_create_pango_context(w);
    PangoLayout *layout= pango_layout_new(context);
    gint width,height;
    pango_layout_set_text(layout,text,-1);
    pango_layout_get_pixel_size(layout,&width,&height);
    gdk_draw_layout (d,gc,xc-width/2,yc-height/2,layout);
    g_object_unref(context); g_object_unref(layout);
}

// рисуем текст text в d при помощи графического контекста gc с центром по y в yc и координатой по x x
// используя w для получения PangoContext
void draw_text_in_center_y(gchar * text, GtkWidget *w, GdkDrawable *d, GdkGC *gc, gint x, gint yc)
{
    PangoContext *context=gtk_widget_create_pango_context(w);
    PangoLayout *layout= pango_layout_new(context);
    gint width,height;
    pango_layout_set_text(layout,text,-1);
    pango_layout_get_pixel_size(layout,&width,&height);
    gdk_draw_layout (d,gc,x,yc-height/2,layout);
    g_object_unref(context); g_object_unref(layout);
}


// отрисовать легенду
void draw_legend()
{
    // если легенда уже была нарисована, то очищаем её предыдущее местонахождение
    if(legx>0&&legy>0)
        gdk_window_clear_area(window->window,legx,legy,legx+LEGENDWIDTH,legy+legendheight);
    // устанавливаем новое положение легенды
    legx=window->allocation.width-LEGENDOFFSETX-LEGENDWIDTH;
    legy=LEGENDY;
    // отрисовываем легенду из GdkPixmap *legend по новым координатам
    gdk_draw_drawable(window->window,window->style->fg_gc[GTK_WIDGET_STATE(window)],legend,0,0,legx,legy,-1,-1);
}

// отрисовываем описание фазы
void displayphasetxt()
{
    // очищаем верхнюю часть окна
    gdk_window_clear_area(window->window,0,0,window->allocation.width,2*CENTERTEXTOFFSETY+2);
    // рисуем описание фазы с тенью
    draw_text_in_center(phasetxt[phase],window,window->window,window->style->white_gc,window->allocation.width/2+SHADOWOFFSET,CENTERTEXTOFFSETY+SHADOWOFFSET);
    draw_text_in_center(phasetxt[phase],window,window->window,window->style->black_gc,window->allocation.width/2,CENTERTEXTOFFSETY);
    // пишем CENTERTEXTHEADER в той же строке, что и описание фазы, но только слева, а не по центру
    draw_text_in_center_y(CENTERTEXTHEADER,window,window->window,window->style->black_gc,10,CENTERTEXTOFFSETY);
}

// начинаем перемещение элементов по путям p1 и p2 ( в каждом пути также хранится номер элемента, который перемещается)
void startmoving(elpath *p1,elpath *p2)
{
    // говорим, что перемещаются ещё 2 элемента
    finished+=2;
    // добавляем два таймера, которые будут периодически вызывать функцию move. В качестве параметра будет передаваться адрес на путь,
    // чтобы его можно было изменять в процессе изменения
    g_timeout_add(MOVEDELAY,(GSourceFunc) move,(gpointer) p1);
    g_timeout_add(MOVEDELAY,(GSourceFunc) move,(gpointer) p2);
}

//добавляем в очередь actionqueue события:
//обмен двух элментов
void insertswap(int idx1,int idx2)
{
    action *n=(action*) malloc(sizeof(action));
    n->type=acswap;
    n->param.swap.id1=idx1;
    n->param.swap.id2=idx2;
    actionqueue=g_slist_append(actionqueue,n);
}
//смена состояния элемента
void insertchangestate(int idx,elstate newstate)
{
    action *n=(action*) malloc(sizeof(action));
    n->type=acchangestate;
    n->param.chgst.id=idx;
    n->param.chgst.state=newstate;
    actionqueue=g_slist_append(actionqueue,n);
}
//ожидание t милисекунд
void insertsleep(int t)
{
    action *n=(action*) malloc(sizeof(action));
    n->type=acsleep;
    n->param.time=t;
    actionqueue=g_slist_append(actionqueue,n);
}
//смена текущей фазы
void insertchangephase(int np)
{
    action *n=(action*) malloc(sizeof(action));
    n->type=acchangephase;
    n->param.phase=np;
    actionqueue=g_slist_append(actionqueue,n);
}
//перемещение элемента p->elnum по траектории, указанной в p->linecurve и p->treecurve
gboolean move(elpath* p)
{
    int i;
    GdkPoint lc,tc;
    // получчаем текущие координаты
    lc=el[p->elnum].linecoord;
    tc=el[p->elnum].treecoord;
    // очищаем окно в том месте, где находился элемент
    gdk_window_clear_area(window->window,el[p->elnum].linecoord.x,el[p->elnum].linecoord.y,2*RAD+1,2*RAD+1);
    gdk_window_clear_area(window->window,el[p->elnum].treecoord.x,el[p->elnum].treecoord.y,2*RAD+1,2*RAD+1);

    // если мы ещё не исчерпали очередь точек p->linecurve, которая является путём элемента в массиве,
    // то мы достаём из очереди координаты и удаляем первый элемент
    if(p->linecurve!=NULL)
    {
        el[p->elnum].linecoord=*((GdkPoint*) p->linecurve->data);
        free(p->linecurve->data);
        p->linecurve=g_list_remove(p->linecurve,p->linecurve->data);
    }
    // аналогично для элемента в дереве
    if(p->treecurve!=NULL)
    {
        el[p->elnum].treecoord=*((GdkPoint*) p->treecurve->data);
        free(p->treecurve->data);
        p->treecurve=g_list_remove(p->treecurve,p->treecurve->data);
    }
    //перерисовываем все те элементы, которые мы могли затронуть при обмене, кроме своего элемента
    for(i=0;i<N;i++)
    {
        if(i==p->elnum) continue;
        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)||
           (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))
        {
            draw_element(window,window->window,&el[i]);
        }
    }
    if(p->linecurve==NULL&&p->treecurve==NULL)
    {
        //если очередь закончилась, то тогда возвращаем элемент в его обычное состояние
        switch(el[p->elnum].state)
        {
            case activeinplace:
                el[p->elnum].state=inplace;
                break;
            case activeinheap:
                el[p->elnum].state=inheap;
                break;
            case activeproc:
                el[p->elnum].state=processed;
                break;
            default:
                el[p->elnum].state=normal;
        }
    }
    // рисуем текущий элемент
    draw_element(window,window->window,&el[p->elnum]);
    if(p->linecurve==NULL&&p->treecurve==NULL)
    {
        //если списки закончились, то тогда мы говорим, что перемещаются на один элемент меньше
        // и освобождаем память, которая была занята под путь
        finished--;
        free(p);
//      if(finished==0&&phase==1)
//          phase=2;
        // если мы закончили перемещать все элементы, вызываем визуализацию
        if(finished==0)
            g_timeout_add(SORTDELAY,(GSourceFunc) visualize,NULL);
        return FALSE;
    }
    return TRUE;
}

// обменивает два элемента массива arrv и сохраняем в очередь действий этот обмен
void swap(int idx1,int idx2)
{
    int t=arrv[idx1];
    arrv[idx1]=arrv[idx2];
    arrv[idx2]=t;
    insertswap(idx1,idx2);
}

// обменивает два элемента массива el, генерирует путь для перемещения элементов и запускает процесс перемещения
void swapvis(int idx1,int idx2)
{
    elpath *p1,*p2;
    int i;
    element t;
    t=el[idx1];
    el[idx1]=el[idx2];
    el[idx2]=t;
    // создаём два пути
    p1=(elpath*) malloc(sizeof(elpath));
    p2=(elpath*) malloc(sizeof(elpath));
    // генерируем путь для вершин idx1 и idx2 соответственно. для вершины idx1 и idx2 в массиве создадим путь вида
    //       ___idx2___
    //       |        /|\
    //      \|/        |
    //-------------------------
    //       |        /|\
    //      \|/        |
    //  ____idx1____
    //
    // и прямой обмен между вершинами в дереве
    *p1=makepath(idx1,el[idx1].linecoord,el[idx2].linecoord,-RISE,VCOUNT,HCOUNT,VCOUNT,el[idx1].treecoord,el[idx2].treecoord,2*VCOUNT+HCOUNT-2);
    *p2=makepath(idx2,el[idx2].linecoord,el[idx1].linecoord,+RISE,VCOUNT,HCOUNT,VCOUNT,el[idx2].treecoord,el[idx1].treecoord,2*VCOUNT+HCOUNT-2);
    switch(el[idx1].state)
    {
        case inplace:
            el[idx1].state=activeinplace;
            break;
        case inheap:
            el[idx1].state=activeinheap;
            break;
        case processed:
            el[idx1].state=activeproc;
            break;
        default:
            el[idx1].state=active;
    }
    switch(el[idx2].state)
    {
        case inplace:
            el[idx2].state=activeinplace;
            break;
        case inheap:
            el[idx2].state=activeinheap;
            break;
        case processed:
            el[idx2].state=activeproc;
            break;
        default:
            el[idx2].state=active;
    }

    // запускаем перемещение по путям p1 и p2 соответственно
    startmoving(p1,p2);
}

// возвращает в списке l очередь точек, начиная с точки s до t исключительно, разделённый на (cnt-1) вершин
void genline(GdkPoint s, GdkPoint t,int cnt,GList ** l)
{
    GdkPoint m,*c;
    int i;
    m=s;
    for(i=1;i<cnt;i++)
    {
        c=(GdkPoint*) malloc(sizeof(GdkPoint));
        *c=m;
        *l=g_list_append(*l,c);
        m.x=s.x+i*1.0*(t.x-s.x)/(cnt-1);
        m.y=s.y+i*1.0*(t.y-s.y)/(cnt-1);
    }
}

// создаёт путь для вершины idx путь в массиве начиная с точки listb до точки liste
// точка сначала поднимется на dy вверх, перемещается до liste.x и опускается на dy вниз.
// на каждом этапе будет соответственно listc1-1, listc2-1 и listc3-1 точки. Также в конце будет добавлена точка t
// для дерева будет создан отрезок из treep1 в treep2 исключительно длинной в treec-1 и добавлена вершина treep2
elpath makepath(gint idx,GdkPoint listb,GdkPoint liste, gint dy, gint listc1, gint listc2,gint listc3,GdkPoint treep1,GdkPoint treep2, gint treec)
{
    GdkPoint s,t,*c;
    elpath res;
    double tx,ty;
    GList *listl=NULL,*treel=NULL;
    int i;
    s=t=listb;
    t.y+=dy;
    genline(s,t,listc1,&listl);

    s=listb;
    s.y+=dy;
    t=liste;
    t.y+=dy;
    genline(s,t,listc2,&listl);

    s=liste;
    s.y+=dy;
    t=liste;
    genline(s,t,listc3,&listl);

    c=(GdkPoint*) malloc(sizeof(GdkPoint));
    *c=t;
    listl=g_list_append(listl,c);

    genline(treep1,treep2,treec,&treel);

    c=(GdkPoint*) malloc(sizeof(GdkPoint));
    *c=treep2;
    treel=g_list_append(treel,c);

    res.linecurve=listl;
    res.treecurve=treel;
    res.elnum=idx;

    return res;
}

// Один из этапов пирамидальной сортировки. Мы пытаемся поднять вершину наверх.
// Для этого мы сравниваем текущую вершину i  с вершиной (i-1)/2. Если он больше, то мы
// меняем элементы и поднимаемся наверх
void upHeap(int* array, int i)
{
    if(i>0)
    {
        if(array[i]>array[(i-1)/2])
        {
            swap(i,(i-1)/2);
            upHeap(array,(i-1)/2);
        }
    }
}

// Один из этапов пирамидальной сортировки. Мы пытаемся опустить вершину вниз.
// Для этого мы определяем наибольшую вершину среди детей i-той вершины и сравниваем. Если наш
// элемент меньше, то мы меняем их и спускаемся вниз
void downHeap(int* array, int i,int cnt)
{
    int child=i*2+1;
    if(child<cnt)
    {
        if(child+1<cnt&&array[child]<array[child+1])
            child++;
        if(array[child]>array[i])
        {
            swap(child,i);
            downHeap(array,child,cnt);
        }
    }
}

// упорядочиваем массив array, составляю очередь действий
void sort(int *array)
{
    int i;
#ifdef HEAPSORTA
    //добавляем в очередь смену состояния корня и добавляем задержку
    insertchangestate(0,inheap);
    insertsleep(SORTDELAY);
    for(i=1;i<N;i++)
    {
        //меняем состояние i-той вершины, добавляем задержку и пытаемся просеять эту вершину вверх
        insertchangestate(i,inheap);
        insertsleep(REDRAWDELAY);
        upHeap(array,i);
        insertsleep(SORTDELAY);
    }
    // очищаем состояния всех вершин
    for(i=0;i<N;i++)
    {
        insertchangestate(i,normal);
    }
    insertsleep(SORTDELAY);
    for(i=N-1;i>0;i--)
    {
        // меняем фазу на "Исключение наибольшего элемента", говорим, что первый элемент на месте и меняем его с последним элементом массива
        insertchangephase(1);
        insertchangestate(0,inplace);
        swap(i,0);
        insertchangephase(2);
        insertsleep(REDRAWDELAY);
        //просеиваем новый первый элемент вниз
        downHeap(array,0,i);
        insertsleep(SORTDELAY);
    }
    insertchangestate(0,inplace);
    insertchangephase(3);
#elif HEAPSORTB
    // говорим, что обработали последнюю половину элементов
    for(i=N-1;2*i+1>=N;i--)
    {
        insertchangestate(i,processed);
    }
    for(i=N/2-1;i>=0;i--)
    {
        //меняем состояние i-той вершины и пытаемся просеять её вниз
        insertchangestate(i,processed);
        downHeap(array,i,N);
        insertsleep(SORTDELAY);
    }
    // очищаем состояния всех вершин
    for(i=0;i<N;i++)
    {
        insertchangestate(i,normal);
    }
    insertsleep(SORTDELAY);
    for(i=N-1;i>0;i--)
    {
        // меняем фазу на "Исключение наибольшего элемента", говорим, что первый элемент на месте и меняем его с последним элементом массива
        insertchangephase(1);
        insertchangestate(0,inplace);
        swap(i,0);
        insertchangephase(2);
        insertsleep(REDRAWDELAY);
        //просеиваем новый первый элемент вниз
        downHeap(array,0,i);
        insertsleep(SORTDELAY);
    }
    insertchangestate(0,inplace);
    insertchangephase(3);
#elif SHELLSORT
    int h = 1;
    int prev;
    // в качестве последовательности шагов мы будем рассматривать последовательность 1, 4, 13, 40,...
    while ( h <= N / 9 )
        h = 3 * h + 1;

    while ( h > 0 ) {
        // сортируем массив какой-нибудь сортировкой. ниже реализован алгоритм, похожий на сортировку вставками
        for ( i = h; i < N; i++ ) {
            int k;
            // рассмотрим последовательность вершин, которые находятся раньше текущей и расположены на расстоянии h,2*h,3*h,... от ней
            // подсветим их все
            for(k=i;k>=0;k-=h)
                insertchangestate(k,processed);
            insertsleep(REDRAWDELAY);
            int j;
            prev=i;
            // так как эта последовательность отсортирована, то достаточно перемещать последний элемент массива влево, пока он меньше предыдущего
            for ( j = i; j >= h && array[j - h] > array[j]; j -= h )
            {
                swap(j,j-h);
            }
            // возвращаем всем вершинам нашей последовательности состояние normal
            for(k=i;k>=0;k-=h)
                insertchangestate(k,normal);
            insertsleep(REDRAWDELAY);
        }
        h /= 3;
    }
    insertchangephase(3);
#elif BUBBLESORT
    for(i=0;i<N;i++)
    {
        int j;
        for(j=0;j<N-i-1;j++)
        {
            // подсвечиваем j тый и j+1 ый элементы
            insertchangestate(j,processed);
            insertchangestate(j+1,processed);
            insertsleep(REDRAWDELAY);
            if(array[j]>array[j+1])
            {
                // если они неправильно стоят, меняем их местами
                swap(j,j+1);
            }
            //возвращаем нормальное состояние элементам
            insertchangestate(j,normal);
            insertchangestate(j+1,normal);
            insertsleep(REDRAWDELAY);
        }
        // говорим, что последний элемент на месте
        insertchangestate(j,inplace);
        insertsleep(REDRAWDELAY);
    }
    insertchangephase(3);
#else
    quicksort(N-1,array,0);
    insertchangephase(3);
#endif
}

// сортируем массив a, содержащий n элементов, который является массивом array с пропущенными offset первыми элементами
void quicksort(int n,int *a,int offset)
{
    int i=0,j=n,k;
    int p=a[n>>1];

    // подсвечиваем текущий интервал
    for(k=0;k<=n;k++)
    {
        insertchangestate(k+offset,activeinterval);
    }
    insertsleep(REDRAWDELAY);
    insertchangestate(i+offset,processed);
    insertchangestate(j+offset,processed);
    do
    {
        // находим первый элемент с начала массива, который не меньше p
        while(a[i]<p)
        {
            insertchangestate(i+offset,activeinterval);
            i++;
            if(i<=j)insertchangestate(i+offset,processed);
            insertsleep(REDRAWDELAY);
        }
        insertsleep(REDRAWDELAY);
        // находим первый элемент с конца массива, который не больше p
        while(a[j]>p)
        {
            insertchangestate(j+offset,activeinterval);
            j--;
            if(i<=j)insertchangestate(j+offset,processed);
            insertsleep(REDRAWDELAY);
        }
        insertsleep(REDRAWDELAY);
        // если индекс i, который пробегает массив с начала, больше, чем индекс j, который пробегает массив с конца,
        // то обменивать нечего, иначе
        if(i<=j)
        {
            // меняем эти два элемента и перемещаем указатели i и j
            swap(offset+i,offset+j);
            insertchangestate(i+offset,activeinterval);
            insertchangestate(j+offset,activeinterval);
            i++;
            j--;
            if(i<=j)
            {
                insertchangestate(i+offset,processed);
                insertchangestate(j+offset,processed);
                insertsleep(REDRAWDELAY);
            }
        }
    }
    while(i<=j);
    // убираем подсветку активного диапазона
    for(k=0;k<=n;k++)
    {
        insertchangestate(k+offset,normal);
    }
    // если интервал 0..j не состоит из одного элемента, то вызываем quicksort для него
    if(j>0) quicksort(j,a,offset);
    // если интервал i..n не состоит из одного элемента, то вызываем quicksort для него
    if(i<n) quicksort(n-i,a+i,offset+i);
}

//если окно было закрыто, завершаем работу
gboolean delete_event(GtkWidget *w,GdkEvent *e, gpointer data)
{
    gtk_main_quit();
    return TRUE;
}