gd20-03.cpp

游戏开发数据结构-Data.Structures.for.Game.Programmers

// ============================================================================
//  GD20-03.cpp
//  Quick Sort Demo
// ============================================================================
#include "SDLGUI.h"
#include "Queue.h"
#include <stdlib.h>
#include <time.h>



// ============================================================================
//  Global Constants
// ============================================================================
const char PROGRAM_NAME[]   = "Quick Sort Graphical Demonstration";
const int WIDTH             = 640;
const int HEIGHT            = 480;
const int ITEMS             = 32;
const int ARIAL             = 0;
const int ARRAYSIZE         = 128;



// holds the indexes of two items that are to be swapped.
class Swap
{
public:
    int a;
    int b;
};

// ============================================================================
//  Global Variables
// ============================================================================
SDLGUI* g_gui;

int g_array[ARRAYSIZE];
int g_temparray[ARRAYSIZE];

SDL_Color g_colors[ARRAYSIZE];

LQueue<Swap> g_queue;

int g_timer;

bool g_sorting = false;

// ============================================================================
//  Draw Algorithm
// ============================================================================
void Draw()
{
    int i;

    for( i = 0; i < ARRAYSIZE; i++ )
    {
        g_gui->Box( i * 5, HEIGHT - (g_array[i] * 2), 
                    5, g_array[i] * 2, BLACK );
        g_gui->Box( i * 5 + 1, HEIGHT - (g_array[i] * 2) + 1, 
                    3, (g_array[i] * 2) - 2, g_colors[g_array[i]] );
    }
}


// ============================================================================
//  Other Algorithms
// ============================================================================
void InitColors()
{
    SDL_Color c;
    int i;

    for( i = 0; i < ARRAYSIZE; i++ )
    {
        c.r = rand() % 255;
        c.g = rand() % 255;
        c.b = rand() % 255;

        g_colors[i] = c;
    }
}



int FindMedianOfThree( int* p_array, int p_first, int p_size )
{
    // calculate the mid and last indexes
    int last = p_first + p_size - 1;
    int mid = p_first + (p_size / 2);

    // determine which index is the median value
    if( p_array[p_first] < p_array[mid] && p_array[p_first] < p_array[last] ) 
    {
        if( p_array[mid] < p_array[last] )
            return mid;
        else
            return last;
    }

    if( p_array[mid] < p_array[p_first] && p_array[mid] < p_array[last] ) 
    {
        if( p_array[p_first] < p_array[last] ) 
            return p_first;
        else
            return last;
    }

    if( p_array[mid] < p_array[p_first] )
        return mid;
    else
        return p_first;
}


void QuickSort( int* p_array, int p_first, int p_size )
{
    int pivot;
    int last = p_first + p_size - 1;
    int lower = p_first;
    int higher = last;
    int mid;
    int temp;
    
    Swap s;

    if( p_size > 1 )
    {
        // get the median point.
        mid = FindMedianOfThree( p_array, p_first, p_size );
        pivot = p_array[mid];

        // swap the pivot into the first index.
        s.a = mid;
        s.b = p_first;
        g_queue.Enqueue( s );
        temp = p_array[mid];
        p_array[mid] = p_array[p_first];
        p_array[p_first] = temp;
        
        while( lower < higher )
        {
            // iterate downwards until you find a value that is lower
            // than the pivot.
            while( pivot < p_array[higher] && lower < higher )
                higher--;
            if( higher != lower ) 
            {
                // swap lower value into the empty index.
                s.a = lower;
                s.b = higher;
                g_queue.Enqueue( s );
                p_array[lower] = p_array[higher];
                lower++;
            }

            // iterate upwards until you find a value greater than the pivot
            while( pivot > p_array[lower] && lower < higher )
                lower++;
            if( higher != lower ) 
            {
                // swap the higher value into the empty index.
                s.a = lower;
                s.b = higher;
                g_queue.Enqueue( s );
                p_array[higher] = p_array[lower];
                higher--;
            }
        }
        p_array[lower] = pivot;
        QuickSort( p_array, p_first, lower - p_first );
        QuickSort( p_array, lower + 1, last - lower );
    }
}





// ============================================================================
//  Button Callbacks
// ============================================================================
void RandomizeArray()
{
    // do nothing if array is sorting.
    if( g_sorting != false )
        return;

    int i;
    for( i = 0; i < ARRAYSIZE; i++ )
    {
        g_array[i] = rand() % 128;
        g_temparray[i] = g_array[i];
    }
}


void SortArray()
{
    QuickSort( g_temparray, 0, ARRAYSIZE );
    g_sorting = true;
    g_timer = SDL_GetTicks();
}


// ============================================================================
//  Main
// ============================================================================
int main( int argc, char* argv[] )
{
    int x;
    int y;


    srand( time(0) );

    InitColors();
    RandomizeArray();
    
    //initialize systems
    SDL_Init( SDL_INIT_VIDEO | SDL_INIT_TIMER );
    SDL_WM_SetCaption( PROGRAM_NAME, 0); 
    TTF_Init();
    g_gui = new SDLGUI( WIDTH, HEIGHT, ITEMS, WHITE );
    g_gui->SetFont( "arial.ttf", ARIAL, 18, TTF_STYLE_NORMAL );



    // add the items to the g_gui
    g_gui->AddButton( 0, 0, "gbup.bmp", "gbdown.bmp", "Randomize", ARIAL, 
                      BLACK, WHITE, RandomizeArray );
    g_gui->AddButton( 128, 0, "gbup.bmp", "gbdown.bmp", "Sort", ARIAL, 
                      BLACK, WHITE, SortArray );

    // set our at exit function
    atexit( SDL_Quit ) ;

    // declare event variable
    SDL_Event event;

    g_gui->Draw();
    g_gui->Update();

    // loop until we get a quit message.
    while( 1 )
    {
        //look for an event
        if( SDL_PollEvent( &event ) )
        {
            //an event was found
            if( event.type == SDL_QUIT ) 
                break;

            // mouse button was pressed
            if( event.type == SDL_MOUSEBUTTONDOWN ) 
            {
                // get the mouse g_state.
                SDL_GetMouseState( &x, &y );

                // tell the GUI that a button has been pressed
                g_gui->MouseDown( x, y );

            }

            // mouse button was released
            if( event.type == SDL_MOUSEBUTTONUP ) 
            {
                // get the mouse state.
                SDL_GetMouseState( &x, &y );

                // tell the GUI that a button has been released
                g_gui->MouseUp( x, y );
            }

            if( event.type == SDL_KEYDOWN )
            {
                // a key was pressed.
                if( event.key.keysym.sym == SDLK_ESCAPE )
                {
                    // if ESC was pressed, quit the program.
                    SDL_Event quit;
                    quit.type = SDL_QUIT;
                    SDL_PushEvent( &quit );
                }

                // tell the GUI that a key was pressed.
                g_gui->KeyDown( event.key.keysym.sym, 
                                event.key.keysym.mod,
                                event.key.keysym.unicode );
            }
        }

        // draw the g_gui at the end of each loop.
        g_gui->Draw();

        if( g_queue.Count() == 0 )
            g_sorting = false;
        
        if( g_sorting == true && SDL_GetTicks() - g_timer >= 15 )
        {
            x = g_array[g_queue.Front().a];
            g_array[g_queue.Front().a] = g_array[g_queue.Front().b];
            g_array[g_queue.Front().b] = x;
            g_timer = SDL_GetTicks();
            g_queue.Dequeue();

        }

        Draw();

        g_gui->Update();
    }

    return 0;
}