gd14-01.cpp

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

// ============================================================================
//  GD14-01.cpp
//  Heap Graphical Demonstration.
// ============================================================================
#include "SDLGUI.h"
#include "Queue.h"
#include "Heap.h"
#include <stdlib.h>
#include <time.h>
#include <string.h>



// ============================================================================
//  Global Constants
// ============================================================================
const char PROGRAM_NAME[]   = "Heap Graphical Demonstration";
const int WIDTH             = 800;
const int HEIGHT            = 600;
const int ITEMS             = 32;
const int ARIAL             = 0;



// ============================================================================
//  classes and enums
// ============================================================================
enum HEAPSTATE
{
    NOSTATE,
    WALKUP,
    WALKDOWN
};

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

int g_timer;

int CompInt( int l, int r )
{
    return l - r;
}

Heap<int> g_heap( 64, CompInt );

// the current node.
int g_current = 0;

// Circles
SDL_Surface* g_blackcircle;
SDL_Surface* g_redcircle;


HEAPSTATE g_state = NOSTATE;

char g_number[3] = "0";
int g_int = 0;

// ============================================================================
//  Draw Algorithms
// ============================================================================
void DrawNode( int p_node, int p_x, int p_y )
{
    static SDL_Surface* text;
    static char number[] = "00";

    // draw the contents of the circle.
    sprintf( number, "%d", g_heap[p_node] );
    text = TTF_RenderText_Shaded( g_gui->GetFont(ARIAL), number, BLACK, WHITE );

    g_gui->Blit( text, (g_blackcircle->w - text->w) / 2 + p_x, 
                       (g_blackcircle->h - text->h) / 2 + p_y );
    SDL_FreeSurface( text );


    // draw the circle
    if( g_current == p_node )
        g_gui->Blit( g_redcircle, p_x, p_y );
    else
        g_gui->Blit( g_blackcircle, p_x, p_y );
}


void DrawTree( int p_tree, int p_x, int p_y, int p_width )
{
    if( p_tree <= g_heap.m_count )
    {
        DrawNode( p_tree, p_x + (p_width / 2) - 24, p_y);

        int w = p_width / 2;
        int w2 = w / 2;

        if( (p_tree * 2) <= g_heap.m_count )
        {
            DrawTree( p_tree * 2, p_x, p_y + 96, w );
            g_gui->ArrowLine( p_x + (p_width / 2), p_y + 24, 
                              p_x + w2, p_y + 124, 24, 24, false, true, BLACK );
        }

        if( (p_tree * 2 + 1) <= g_heap.m_count )
        {
            DrawTree( p_tree * 2 + 1, p_x + w, p_y + 96, w );
            g_gui->ArrowLine( p_x + (p_width / 2), p_y + 24, 
                              p_x + w2 + w, p_y + 124, 24, 24, false, true, BLACK );
        }
    }
}



// ============================================================================
//  Button Callbacks
// ============================================================================
void Enqueue()
{
    if( g_state == NOSTATE )
    {
        // get the number to insert
        int n = atoi( g_number );

        g_heap.m_count++;

        // resize the heap if needed.
        if( g_heap.m_count >= g_heap.m_size )
            g_heap.Resize( g_heap.m_size * 2 );

        // place the new item at the bottom of the heap.
        g_heap[g_heap.m_count] = n;

        g_current = g_heap.m_count;

        g_state = WALKUP;
        g_timer = SDL_GetTicks();
    }
}


void Dequeue()
{
    if( g_state == NOSTATE && g_heap.m_count > 0 )
    {
        g_heap[1] = g_heap[g_heap.m_count];
        g_current = 1;
        g_heap.m_count--;

        g_state = WALKDOWN;
        g_timer = SDL_GetTicks();
    }
}

void Random()
{
    if( g_state == NOSTATE )
    {
        int i = rand() % 100;
        sprintf( g_number, "%d", i );
    }
}

// ============================================================================
//  Main
// ============================================================================

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

    DrawTree( 1, 0, 0, WIDTH );

    g_gui->Update();
}


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

    srand( time(0) );

    //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, 20, TTF_STYLE_NORMAL );


    // load the bmps
    g_blackcircle = SDL_LoadBMP( "circleblack.bmp" );
    g_redcircle =   SDL_LoadBMP( "circlered.bmp" );

    // set the color keys of the BMPs
    SDL_SetColorKey( g_blackcircle, SDL_SRCCOLORKEY, 
                     SDL_MapRGB( g_blackcircle->format, 255, 255, 255 ));
    SDL_SetColorKey( g_redcircle, SDL_SRCCOLORKEY, 
                     SDL_MapRGB( g_redcircle->format, 255, 255, 255 ));

    // add the items to the g_gui
    g_gui->AddButton( 0, 0, "gbup.bmp", "gbdown.bmp", "Enqueue", ARIAL,
                      BLACK, WHITE, Enqueue );
    g_gui->AddButton( 0, 64, "gbup.bmp", "gbdown.bmp", "Dequeue", ARIAL,
                      BLACK, WHITE, Dequeue );
    g_gui->AddButton( 0, 128, "gbup.bmp", "gbdown.bmp", "Random", ARIAL,
                      BLACK, WHITE, Random );


    // add the text box
    g_gui->AddTextBox( 128, 0, 128, 32, g_number, 2, 
                       ARIAL, BLACK, WHITE, true, 0 );

    // 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();
        }

        if( SDL_GetTicks() - g_timer > 700 && g_state != NOSTATE )
        {
            g_timer = SDL_GetTicks();

            // the walk-up algorithm
            if( g_state == WALKUP )
            {
                if( g_current > 1 )
                {
                    if( g_heap[g_current/2] < g_heap[g_current] )
                    {
                        // swap the nodes.
                        x = g_heap[g_current];
                        g_heap[g_current] = g_heap[g_current/2];
                        g_heap[g_current/2] = x;

                        g_current /= 2;
                    }
                    else
                    {
                        g_state = NOSTATE;
                    }
                }
                else
                {
                    g_state = NOSTATE;
                }
            }

            // the walk-down algorithm
            else
            {
                y = g_current * 2;
                if( y <= g_heap.m_count )
                {
                    // make y point to the largest of the two children
                    if( y + 1 <= g_heap.m_count )
                    {
                        if( g_heap[y] < g_heap[y+1] )
                            y++;
                    }

                    if( g_heap[g_current] < g_heap[y] )
                    {
                        // swap the nodes
                        x = g_heap[g_current];
                        g_heap[g_current] = g_heap[y];
                        g_heap[y] = x;
                        g_current = y;
                    }
                    else
                    {
                        g_state = NOSTATE;
                    }
                }
                else
                {
                    g_state = NOSTATE;
                }
            }
            Draw();
        }
    }

    return 0;
}