gd20-04.cpp

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

// ============================================================================
//  GD20-04.cpp
//  Sorting Race Demo
// ============================================================================
#include "SDLGUI.h"
#include "Queue.h"
#include <stdlib.h>
#include <time.h>



// ============================================================================
//  Global Constants
// ============================================================================
const char PROGRAM_NAME[]   = "Sorting Race 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_arrayBS[ARRAYSIZE];
int g_temparrayBS[ARRAYSIZE];
int g_arrayHS[ARRAYSIZE];
int g_temparrayHS[ARRAYSIZE];
int g_arrayQS[ARRAYSIZE];
int g_temparrayQS[ARRAYSIZE];

SDL_Color g_colors[ARRAYSIZE];

LQueue<Swap> g_queueBS;
LQueue<Swap> g_queueHS;
LQueue<Swap> g_queueQS;

int g_timer;

bool g_sorting = false;

int g_heapSize;

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

    for( i = 0; i < ARRAYSIZE; i++ )
    {

        // Bubblesort
        g_gui->Box( i * 5, (HEIGHT - 256) - g_arrayBS[i], 
                    5, g_arrayBS[i], BLACK );
        if( g_arrayBS[i] > 1 )
        {
            g_gui->Box( i * 5 + 1, (HEIGHT - 256) - g_arrayBS[i] + 1, 
                        3, g_arrayBS[i] - 2, g_colors[g_arrayBS[i]] );
        }

        // Heapsort
        g_gui->Box( i * 5, (HEIGHT - 128) - g_arrayHS[i], 
                    5, g_arrayHS[i], BLACK );
        if( g_arrayHS[i] > 1 )
        {
            g_gui->Box( i * 5 + 1, (HEIGHT - 128) - g_arrayHS[i] + 1, 
                        3, g_arrayHS[i] - 2, g_colors[g_arrayHS[i]] );
        }

        // Quicksort
        g_gui->Box( i * 5, HEIGHT - g_arrayQS[i], 
                    5, g_arrayQS[i], BLACK );
        if( g_arrayQS[i] > 1 )
        {
            g_gui->Box( i * 5 + 1, HEIGHT - g_arrayQS[i] + 1, 
                        3, g_arrayQS[i] - 2, g_colors[g_arrayQS[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_queueQS.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_queueQS.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_queueQS.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 );
    }
}



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_queueHS.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_queueHS.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 );
    }
}

void BubbleSort( int* p_array )
{
    int top = ARRAYSIZE - 1;
    int index;
    int temp;
    Swap s;

    while( top != 0 )
    {
        for( index = 0; index < top; index++ )
        {
            if( p_array[index] > p_array[index + 1] )
            {
                s.a = index;
                s.b = index + 1;
                g_queueBS.Enqueue( s );

                temp = p_array[index];
                p_array[index] = p_array[index + 1];
                p_array[index + 1] = temp;
            }
        }
        top--;
    }
}


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

    int i;
    for( i = 0; i < ARRAYSIZE; i++ )
    {
        g_arrayBS[i] = rand() % 128;
        g_temparrayBS[i] = g_arrayBS[i];
        g_arrayHS[i] = g_arrayBS[i];
        g_temparrayHS[i] = g_arrayBS[i];
        g_arrayQS[i] = g_arrayBS[i];
        g_temparrayQS[i] = g_arrayBS[i];
    }
}


void SortArray()
{
    BubbleSort( g_temparrayBS );
    HeapSort( g_temparrayHS );
    QuickSort( g_temparrayQS, 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_queueBS.Count() == 0 && 
            g_queueHS.Count() == 0 &&
            g_queueQS.Count() == 0 )
            g_sorting = false;
        
        if( g_sorting == true && SDL_GetTicks() - g_timer >= 15 )
        {
            if( g_queueBS.Count() != 0 )
            {
                x = g_arrayBS[g_queueBS.Front().a];
                g_arrayBS[g_queueBS.Front().a] = g_arrayBS[g_queueBS.Front().b];
                g_arrayBS[g_queueBS.Front().b] = x;
                g_queueBS.Dequeue();
            }
            if( g_queueHS.Count() != 0 )
            {
                x = g_arrayHS[g_queueHS.Front().a];
                g_arrayHS[g_queueHS.Front().a] = g_arrayHS[g_queueHS.Front().b];
                g_arrayHS[g_queueHS.Front().b] = x;
                g_queueHS.Dequeue();
            }
            if( g_queueQS.Count() != 0 )
            {
                x = g_arrayQS[g_queueQS.Front().a];
                g_arrayQS[g_queueQS.Front().a] = g_arrayQS[g_queueQS.Front().b];
                g_arrayQS[g_queueQS.Front().b] = x;
                g_queueQS.Dequeue();
            }

            g_timer = SDL_GetTicks();
        }

        Draw();

        g_gui->Update();
    }

    return 0;
}