TAPsHashTableBySTLVector.cpp

Go to the documentation of this file.

/******************************************************************************
TAPsHashTableBySTLVector.cpp

Class TAPsHashTableBySTLVector is a hash table created from STL vector class.

SUKITTI PUNAK   (04/08/2005)
UPDATE          (04/15/2005)
******************************************************************************/
#include "TAPsHashTableBySTLVector.hpp"
// Using Inclusion Model (i.e. definitions are included in declarations)
//                       (this name.cpp is included in name.hpp)
// Each friend is defined directly inside its declaration.

BEGIN_NAMESPACE_TAPs__DS
//=============================================================================
// Constructor and Destructor
//-----------------------------------------------------------------------------
template <typename T>
HashTableBySTLVector<T>::HashTableBySTLVector ( int numberOfBuckets )
    : m_iNoOfBuckets( numberOfBuckets )
{   
    m_pvBucketNo = new std::vector<T>[m_iNoOfBuckets];
}
//-----------------------------------------------------------------------------
template <typename T>
HashTableBySTLVector<T>::~HashTableBySTLVector ()
{   
    if ( m_pvBucketNo != NULL ) {
        delete [] m_pvBucketNo;
    }
    m_pvBucketNo = NULL;
}
//-----------------------------------------------------------------------------
//=============================================================================
// Operation(s) Unsorted Elements
//-----------------------------------------------------------------------------
// Insert in into bucket#
// All values, assume numbers, in bucket will not be sorted.
// Return the inserted index
template <typename T>
int HashTableBySTLVector<T>::Insert ( T in, int bucketNo  )
{
    m_pvBucketNo[ bucketNo ].push_back( in );
    return static_cast<int>( m_pvBucketNo[ bucketNo ].size() - 1 );
}
//-----------------------------------------------------------------------------
// Search key in bucket# with unsorted values
// Return the first index that contains the key, else return -1
template <typename T>
int HashTableBySTLVector<T>::Search ( T key, int bucketNo )
{
    if ( !m_pvBucketNo[ bucketNo ].empty() ) {
        for ( int i = 0; i < m_pvBucketNo[ bucketNo ].size(); ++i ) {
            if ( key == m_pvBucketNo[ bucketNo ][ i ] ) {
                return i;
            }
        }
    }
    return -1;  // empty bucket or not found
}
//=============================================================================
// Operation(s) Sorted Elements
//-----------------------------------------------------------------------------
// Insert in into bucket#
// All values, assume numbers, in bucket will not be sorted.
// Return the inserted index
template <typename T>
int HashTableBySTLVector<T>::InsertSort ( T in, int bucketNo  )
{
    if ( !m_pvBucketNo[ bucketNo ].empty() ) {
        std::vector<T>::iterator pos = m_pvBucketNo[ bucketNo ].begin();
        for ( int i = 0; i < static_cast<int>( m_pvBucketNo[ bucketNo ].size() ); ++i, ++pos ) {
            if ( in < m_pvBucketNo[ bucketNo ][ i ] ) {
                m_pvBucketNo[ bucketNo ].insert( pos, in );
                return i;
            }
        }
    }
    m_pvBucketNo[ bucketNo ].push_back( in );
    return static_cast<int>( m_pvBucketNo[ bucketNo ].size() - 1 );
}
//-----------------------------------------------------------------------------
// Search key in bucket# with sorted values
// Return the first index that contains the key, else return -1
template <typename T>
int HashTableBySTLVector<T>::SearchSort ( T key, int bucketNo )
{
    if ( !m_pvBucketNo[ bucketNo ].empty() ) {
        for ( int i = 0; i < m_pvBucketNo[ bucketNo ].size(); ++i ) {
            if ( key >= m_pvBucketNo[ bucketNo ][ i ] ) {
                if ( key == m_pvBucketNo[ bucketNo ][ i ] ) return i;
                else                                        return -1;
            }
        }
    }
    return -1;  // empty bucket or not found
}
//-----------------------------------------------------------------------------
//=============================================================================
END_NAMESPACE_TAPs__DS
//345678901234567890123456789012345678901234567890123456789012345678901234567890
//--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8