gd21-02.cpp

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

// ============================================================================
//  GD21-02.cpp
//  Huffman Tree Graphical Demonstration.
// ============================================================================
#include "SDLGUI.h"
#include "Array.h"
#include "DLinkedList.h"
#include "BinaryTree.h"
#include <stdlib.h>
#include <time.h>
#include <string.h>



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


// ============================================================================
//  Classes
// ============================================================================
class Character
{
public:
    char c;
    int weight;
    int t;


    Character()
    {
        c = 0;
        weight = 0;
        t = 0;
    }
};


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

bool g_calculating = false;
int g_iteratestate = 0;

typedef BinaryTree<Character> charnode;
DLinkedList<charnode*> g_queue;

int g_numberofnewnodes = 0;

charnode* g_left;
charnode* g_right;
charnode* g_parent;

char g_string[80] = "hello!";

int g_frequencyarray[256];

// Circles
SDL_Surface* g_blackcircle;


// ============================================================================
//  Functions
// ============================================================================
int GetDepth( charnode* p_tree )
{
    int left = -1;
    int right = -1;

    if( p_tree->m_left != 0 )
        left = GetDepth( p_tree->m_left );
    if( p_tree->m_right != 0 )
        right = GetDepth( p_tree->m_right );

    return ( left > right ? left : right ) + 1;
}


void GetFrequency()
{
    int i;
    int length;

    // clear the frequency table
    for( i = 0; i < 256; i++ )
    {
        g_frequencyarray[i] = 0;
    }

    // calculate the frequencies
    length = strlen( g_string );
    for( i = 0; i < length; i++ )
    {
        g_frequencyarray[ g_string[i] ]++;
    }
}


void AddNode( charnode* p_node )
{
    DListIterator<charnode*> itr = g_queue.GetIterator();

    // find the right place in the queue to add the node
    while( itr.Valid() )
    {
        if( itr.Item()->m_data.weight <= p_node->m_data.weight )
        {
            itr.Forth();
        }
        else
            break;
    }

    if( itr.Valid() )
    {
        g_queue.InsertBefore( itr, p_node );
    }
    else
    {
        g_queue.Append( p_node );
    }
}


void InitQueue()
{
    charnode* node = 0;
    int i;

    // clear the queue
    while( g_queue.m_count != 0 )
    {
        delete g_queue.m_head->m_data;
        g_queue.RemoveHead();
    }

    for( i = 0; i < 256; i++ )
    {
        // add a new node if it has letter occurences.
        // no need to add nodes that don't exist in the tree.
        if( g_frequencyarray[i] != 0 )
        {
            node = new charnode;
            node->m_data.c = (char)i;
            node->m_data.weight = g_frequencyarray[i];
            AddNode( node );
        }
    }

}

// ============================================================================
//  Draw Algorithms
// ============================================================================
void DrawNode( BinaryTree<Character>* p_node, int p_x, int p_y )
{
    static SDL_Surface* text;
    static char letter[16] = "";

    // draw the contents of the circle.
    sprintf( letter, "%c", p_node->m_data.c );
    if( letter[0] == ' ' )
        strcpy( letter, "SP" );
    if( p_node->m_data.t != 0 )
    {
        sprintf( letter, "T%d", p_node->m_data.t );
    }
    
    text = TTF_RenderText_Shaded( g_gui->GetFont(ARIAL), letter, 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
    g_gui->Blit( g_blackcircle, p_x, p_y );
}


void DrawTree( BinaryTree<Character>* p_tree, int p_x, int p_y, int p_width )
{
    if( p_tree != 0 )
    {
        DrawNode( p_tree, p_x + (p_width / 2) - 24, p_y);

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

        if( p_tree->m_left )
        {
            DrawTree( p_tree->m_left, p_x, p_y + 128, w );
            g_gui->ArrowLine( p_x + (p_width / 2), p_y + 24, 
                              p_x + w2, p_y + 152, 24, 24, false, true, BLACK );
        }
        if( p_tree->m_right )
        {
            DrawTree( p_tree->m_right, p_x + w, p_y + 128, w );
            g_gui->ArrowLine( p_x + (p_width / 2), p_y + 24, 
                              p_x + w2 + w, p_y + 152, 24, 24, false, true, BLACK );
        }
    }
}



void DrawQueue()
{
    // quit out if queue is empty
    if( g_queue.m_count == 0 )
        return;

    int width = WIDTH / g_queue.m_count;
    DListIterator<charnode*> itr = g_queue.GetIterator();
    int x = 0;
    

    for( itr.Start(); itr.Valid(); itr.Forth() )
    {
        DrawTree( itr.Item(), x, 
                  HEIGHT - (128 * GetDepth( itr.Item() )) - 48,
                  width );
        x += width;
    }
}


void DrawIterateState()
{
    switch( g_iteratestate )
    {
    case 0:
        break;
    case 1:
        DrawTree( g_left, 0, 128, WIDTH / 2 );
        break;
    case 2:
        DrawTree( g_left, 0, 128, WIDTH / 2 );
        DrawTree( g_right, WIDTH/2, 128, WIDTH / 2 );
        break;
    case 3:
        DrawTree( g_parent, 0, 0, WIDTH );
        break;
    }
}


// ============================================================================
//  Button Callbacks
// ============================================================================
void Calculate()
{
    if( g_calculating == true )
        return;

    // calculate the frequency table
    GetFrequency();

    // insert all the letters into the queue.
    InitQueue();

    g_calculating = true;
    g_numberofnewnodes = 0;
    g_gui->GetItem( 1 )->SetVisibility( false );
    g_gui->GetItem( 2 )->SetVisibility( true );
}


void Iterate()
{

    if( g_calculating == false )
        return;

    switch( g_iteratestate )
    {
    case 0:
        g_left = g_queue.m_head->m_data;
        g_iteratestate = 1;
        g_gui->GetItem( 6 )->SetVisibility( false );
        g_gui->GetItem( 3 )->SetVisibility( true );
        g_queue.RemoveHead();
        break;
    case 1:
        g_right = g_queue.m_head->m_data;
        g_iteratestate = 2;
        g_gui->GetItem( 3 )->SetVisibility( false );
        g_gui->GetItem( 4 )->SetVisibility( true );
        g_queue.RemoveHead();
        break;
    case 2:
        g_parent = new charnode;
        g_parent->m_left = g_left;
        g_parent->m_right = g_right;
        g_numberofnewnodes++;
        g_parent->m_data.t = g_numberofnewnodes;
        g_parent->m_data.c = 0;
        g_parent->m_data.weight = g_left->m_data.weight + 
                                  g_right->m_data.weight;
        g_iteratestate = 3;
        g_gui->GetItem( 4 )->SetVisibility( false );
        g_gui->GetItem( 5 )->SetVisibility( true );
        break;
    case 3:
        AddNode( g_parent );
        g_iteratestate = 0;
        g_gui->GetItem( 5 )->SetVisibility( false );
        g_gui->GetItem( 6 )->SetVisibility( true );
        if( g_queue.m_count == 1 )
        {
            g_calculating = false;
            g_gui->GetItem( 6 )->SetVisibility( false );
            g_gui->GetItem( 2 )->SetVisibility( false );
            g_gui->GetItem( 1 )->SetVisibility( true );
        }
        break;
    }
}


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


    //initialize systems
    SDL_Init( SDL_INIT_VIDEO | SDL_INIT_TIMER );
    SDL_WM_SetCaption( PROGRAM_NAME, 0); 
    TTF_Init();
    SDL_EnableUNICODE( true );
    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" );

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

    // add the items to the g_gui
    g_gui->AddTextBox( 0, 0, 256, 32, g_string, 64, ARIAL, BLACK, 
                       WHITE, true, Calculate );
    g_gui->AddButton( 0, 33, "gbup.bmp", "gbdown.bmp", "Calculate", ARIAL,
                      BLACK, WHITE, Calculate );
    g_gui->AddButton( 0, 97, "gbup.bmp", "gbdown.bmp", "Iterate", ARIAL,
                      BLACK, WHITE, Iterate );
    g_gui->AddLabel( 0, 33, "Pull off the first node.", ARIAL, BLACK, WHITE );
    g_gui->AddLabel( 0, 33, "Pull off another node.", ARIAL, BLACK, WHITE );
    g_gui->AddLabel( 0, 33, "Create a new node.", ARIAL, BLACK, WHITE );
    g_gui->AddLabel( 0, 33, "Put it into the queue.", ARIAL, BLACK, WHITE );

    g_gui->GetItem( 2 )->SetVisibility( false );
    g_gui->GetItem( 3 )->SetVisibility( false );
    g_gui->GetItem( 4 )->SetVisibility( false );
    g_gui->GetItem( 5 )->SetVisibility( false );
    g_gui->GetItem( 6 )->SetVisibility( false );


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

        DrawQueue();
        DrawIterateState();
        g_gui->Update();
    }

    return 0;
}