gd20-02.cpp

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

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



// ============================================================================
//  Global Constants
// ============================================================================
const char PROGRAM_NAME[]   = "Heap 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;

int g_heapSize;


// ============================================================================
//  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;
    }
}


void HeapWalkDown( int* p_array, int p_index )
{
    int parent = p_index;
    int child = p_index * 2;
    int temp = p_array[parent - 1];

    Swap s;

    // loop through, walking node down heap until both children are
    // smaller than node.
    while( child <= g_heapSize )
    {
        // if left child is not the last node in the tree, then
        // find out which of the current node's children is largest.
        if( child < g_heapSize )
        {
            if( p_array[child - 1] < p_array[child] )
            {   // change the pointer to the right child, since it is larger.
                child++;
            }
        }
        // if the node to walk down is lower than the highest value child,
        // move the child up one level.
        if( temp < p_array[child - 1] )
        {
            s.a = parent - 1;
            s.b = child - 1;
            g_queue.Enqueue( s );

            p_array[parent - 1] = p_array[child - 1];
            parent = child;
            child *= 2;
        }
        else
            break;
    }
    p_array[parent - 1] = temp;
}


void Heapsort( int* p_array )
{
    int i;
    Swap s;
    int temp;
    g_heapSize = ARRAYSIZE;

    // walk everything down to transform it into a heap
    for( i = ARRAYSIZE/2; i > 0; i-- )
    {
        HeapWalkDown( p_array, i );
    }

    // remove the top, walk everything down.
    while( g_heapSize > 0 )
    {
        s.a = 0;
        s.b = g_heapSize - 1;
        g_queue.Enqueue( s );

        temp = p_array[0];
        p_array[0] = p_array[g_heapSize - 1];
        p_array[g_heapSize - 1] = temp;

        g_heapSize--;
        HeapWalkDown( p_array, 1 );
    }
}


// ============================================================================
//  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()
{
    Heapsort( g_temparray );
    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;
}