gd20-05.cpp

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

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



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



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

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

SDL_Color g_colors[ARRAYSIZE];

LQueue<int> g_queue;

int g_timer;

bool g_sorting = false;


int g_index;

// ============================================================================
//  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 RadixSort2( int* p_array )
{
    int bins[2][ARRAYSIZE];
    int bincount[2];

    int radix = 1;
    int shift = 0;
    int index;
    int binindex;
    int currentbin;

    while( radix <= 0x80 )
    {
        // clear the bin counts
        bincount[0] = bincount[1] = 0;
        
        // place the items in the bins
        for( index = 0; index < ARRAYSIZE; index++ )
        {
            binindex = (p_array[index] & radix) >> shift;
            bins[binindex][bincount[binindex]] = p_array[index];
            bincount[binindex]++;
        }

        // put the items back in the array
        index = 0;

        for( currentbin = 0; currentbin < 2; currentbin++ )
        {
            binindex = 0;
            while( bincount[currentbin] > 0 )
            {
                p_array[index] = bins[currentbin][binindex];
                binindex++;
                bincount[currentbin]--;

                g_queue.Enqueue( p_array[index] );
                index++;
            }
        }

        radix <<= 1;
        shift += 1;
    }
}


void RadixSort4( int* p_array )
{
    int bins[4][ARRAYSIZE];
    int bincount[4];

    int radix = 3;
    int shift = 0;
    int index;
    int binindex;
    int currentbin;

    while( radix <= 0x100 )
    {
        // clear the bin counts
        bincount[0] = bincount[1] = bincount[2] = bincount[3] = 0;
        
        // place the items in the bins
        for( index = 0; index < ARRAYSIZE; index++ )
        {
            binindex = (p_array[index] & radix) >> shift;
            bins[binindex][bincount[binindex]] = p_array[index];
            bincount[binindex]++;
        }

        // put the items back in the array
        index = 0;

        for( currentbin = 0; currentbin < 4; currentbin++ )
        {
            binindex = 0;
            while( bincount[currentbin] > 0 )
            {
                p_array[index] = bins[currentbin][binindex];
                binindex++;
                bincount[currentbin]--;

                g_queue.Enqueue( p_array[index] );
                index++;
            }
        }

        radix <<= 2;
        shift += 2;
    }
}


void RadixSort8( int* p_array )
{
    int bins[8][ARRAYSIZE];
    int bincount[8];

    int radix = 7;
    int shift = 0;
    int index;
    int binindex;
    int currentbin;

    while( radix <= 0x200 )
    {
        // clear the bin counts
        bincount[0] = bincount[1] = bincount[2] = bincount[3] = 0;
        bincount[4] = bincount[5] = bincount[6] = bincount[7] = 0;
        
        // place the items in the bins
        for( index = 0; index < ARRAYSIZE; index++ )
        {
            binindex = (p_array[index] & radix) >> shift;
            bins[binindex][bincount[binindex]] = p_array[index];
            bincount[binindex]++;
        }

        // put the items back in the array
        index = 0;

        for( currentbin = 0; currentbin < 8; currentbin++ )
        {
            binindex = 0;
            while( bincount[currentbin] > 0 )
            {
                p_array[index] = bins[currentbin][binindex];
                binindex++;
                bincount[currentbin]--;

                g_queue.Enqueue( p_array[index] );
                index++;
            }
        }

        radix <<= 3;
        shift += 3;
    }
}


// ============================================================================
//  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 SortArray2()
{
    // do nothing if array is sorting.
    if( g_sorting != false )
        return;

    RadixSort2( g_temparray );
    g_sorting = true;
    g_timer = SDL_GetTicks();
    g_index = 0;
}

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

    RadixSort4( g_temparray );
    g_sorting = true;
    g_timer = SDL_GetTicks();
    g_index = 0;
}

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

    RadixSort8( g_temparray );
    g_sorting = true;
    g_timer = SDL_GetTicks();
    g_index = 0;
}

// ============================================================================
//  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-2", ARIAL, 
                      BLACK, WHITE, SortArray2 );
    g_gui->AddButton( 256, 0, "gbup.bmp", "gbdown.bmp", "Sort-4", ARIAL, 
                      BLACK, WHITE, SortArray4 );
    g_gui->AddButton( 384, 0, "gbup.bmp", "gbdown.bmp", "Sort-8", ARIAL, 
                      BLACK, WHITE, SortArray8 );

    // 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 )
        {
            g_array[g_index] = g_queue.Front();
            g_index = (g_index + 1) % ARRAYSIZE;
            g_timer = SDL_GetTicks();
            g_queue.Dequeue();
        }

        Draw();

        g_gui->Update();
    }

    return 0;
}