huffman.h

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

            {
                value = (1 << codeindex) & code;
                m_compressedData.Set( vectorindex, value );
                vectorindex++;
            }
        }

        // record the size of the data in the bitvector
        m_compressedLength = vectorindex;
        m_dataLength = p_array.Size();
    }


// ----------------------------------------------------------------
//  Name:           Decompress
//  Description:    This decompresses the data in the bitvector
//                  into p_array.
//  Arguments:      p_array
//  Return Value:   None
// ----------------------------------------------------------------
    void Decompress( Array<DataType>& p_array )
    {
        int vectorindex;
        int arrayindex = 0;
        int treeindex = 1;
        int value;

        // resize the array to make room
        if( p_array.Size() < m_dataLength )
            p_array.Resize( m_dataLength );

        // go through each bit in the vector
        for( vectorindex = 0; vectorindex < m_compressedLength; vectorindex++ )
        {
            // calculate the value of the current bit, then
            // travel down the tree.
            value = m_compressedData[vectorindex];
            treeindex = treeindex * 2 + value;

            // if the node's current code length is not zero, then you've
            // found a leaf node
            if( m_huffmanTree[treeindex-1].m_codeLength != 0 )
            {
                // we found a leaf node, so copy it into the array
                p_array[arrayindex] = m_huffmanTree[treeindex-1].m_data;

                // increment the array index
                arrayindex++;

                // reset the tree index.
                treeindex = 1;
            }
        }
    }


// ----------------------------------------------------------------
//  Name:           SaveTree
//  Description:    This saves the tree to disk
//  Arguments:      p_name: the name of the file.
//  Return Value:   None
// ----------------------------------------------------------------
    void SaveTree( char* p_name )
    {
        // open the file
        FILE* file = fopen( p_name, "wb" );

        // write the tree.
        fwrite( &m_maxEntry, sizeof(int), 1, file );
        fwrite( m_huffmanTree.m_array, sizeof(Node), m_maxEntry, file );

        fclose( file );
    }


// ----------------------------------------------------------------
//  Name:           LoadTree
//  Description:    Loads a tree from disk.
//  Arguments:      p_name: name of the file.
//  Return Value:   None
// ----------------------------------------------------------------
    void LoadTree( char* p_name )
    {
        FILE* file = fopen( p_name, "rb" );

        // read the tree size
        fread( &m_maxEntry, sizeof(int), 1, file );

        // resize the array to hold the tree
        m_huffmanTree.Resize( m_maxEntry );

        // read the tree
        fread( m_huffmanTree.m_array, sizeof(Node), m_maxEntry, file );

        fclose( file );

        CreateLookupTable();
    }


// ----------------------------------------------------------------
//  Name:           SaveData
//  Description:    Saves the compressed data to disk
//  Arguments:      p_name: name of the file
//  Return Value:   None
// ----------------------------------------------------------------
    void SaveData( char* p_name )
    {
        FILE* file = fopen( p_name, "wb" );

        // write the size of the data stored
        fwrite( &m_dataLength, sizeof(int), 1, file );

        // write the size of the binary data stored
        fwrite( &m_compressedLength, sizeof(int), 1, file );

        // write the actual compressed data
        fwrite( m_compressedData.m_array, 
                sizeof(unsigned long int),
                (m_compressedLength / 32) + 1,
                file );

        fclose( file );
    }



// ----------------------------------------------------------------
//  Name:           LoadData
//  Description:    Loads compressed data from disk
//  Arguments:      p_name: name of the file
//  Return Value:   None
// ----------------------------------------------------------------
    void LoadData( char* p_name )
    {
        FILE* file = fopen( p_name, "rb" );

        // read the size of the data stored
        fread( &m_dataLength, sizeof(int), 1, file );

        // read the size of the binary data stored
        fread( &m_compressedLength, sizeof(int), 1, file );

        // resize the bitvector to store the data
        m_compressedData.Resize( m_compressedLength );

        // read the actual compressed data
        fread( m_compressedData.m_array, 
               sizeof(unsigned long int),
               m_compressedData.m_size,
               file );

        fclose( file );
    }


// ----------------------------------------------------------------
//  Name:           ConvertTreeToArray
//  Description:    This converts the linked tree produced by
//                  the huffman algorithm into an arrayed tree.
//  Arguments:      p_tree: the root of the linked tree.
//  Return Value:   None
// ----------------------------------------------------------------
    void ConvertTreeToArray( TreeNode* p_tree )
    {
        int index;

        // resize the tree to hold the right amount of nodes
        index = ( 2 << GetDepth( p_tree ) ) - 1;

        if( m_huffmanTree.Size() < index )
            m_huffmanTree.Resize( index );

        // clear the existing tree
        m_maxEntry = 0;
        for( index = 0; index < m_huffmanTree.Size(); index++ )
        {
            m_huffmanTree[index].m_code = 0;
            m_huffmanTree[index].m_codeLength = 0;
        }

        Convert( p_tree, 1, 0, 0 );

    }


    
// ----------------------------------------------------------------
//  Name:           Convert
//  Description:    This is a recursive helper function that
//                  does the actual tree->array converting.
//  Arguments:      p_tree: the current node to convert
//                  p_index: the index of the node in the array
//                  p_length: the length of the node's code
//                  p_code: the code for the node.
//  Return Value:   None
// ----------------------------------------------------------------
    void Convert( TreeNode* p_tree, 
                  int p_index, 
                  int p_length, 
                  unsigned long int p_code )
    {
        // chack to see if the node is a leaf or not.
        if( p_tree->m_left == 0 && p_tree->m_right == 0 )
        {
            // if this node is higher than the max entry, set
            // a new max entry.
            if( p_index > m_maxEntry )
                m_maxEntry = p_index;

            // set up the entry
            m_huffmanTree[p_index-1].m_data = p_tree->m_data.m_data;
            m_huffmanTree[p_index-1].m_code = p_code;
            m_huffmanTree[p_index-1].m_codeLength = p_length;
        }
        else
        {
            // else, recurse down the left and right children until
            // a leaf is found.
            if( p_tree->m_left != 0 )
            {
                Convert( p_tree->m_left, 
                         p_index * 2, 
                         p_length + 1, 
                         p_code );
            }
            if( p_tree->m_right != 0 )
            {
                Convert( p_tree->m_right, 
                         p_index * 2 + 1, 
                         p_length + 1, 
                         p_code | (1 << p_length) );
            }
        }
    }


// ----------------------------------------------------------------
//  Name:           CreateLookupTable
//  Description:    This creates the lookup table of nodes.
//  Arguments:      None
//  Return Value:   None
// ----------------------------------------------------------------
    void CreateLookupTable()
    {
        int index;

        // loop through each tree entry
        for( index = 0; index < m_maxEntry; index++ )
        {
            // if the tree entry is valid, 
            if( m_huffmanTree[index].m_codeLength != 0 )
            {
                // store the entry into the lookuptable
                m_lookupTable[ m_huffmanTree[index].m_data ] = 
                    m_huffmanTree[index];
            }
        }
    }
};


#endif