/*
    ChemCon - molecular mechanics and molecular graphics
    Copyright (C) 1998-2002  Alexei Nikitin

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
*/
#ifndef MM_HASH_H
#define MM_HASH_H

#ifndef ARRAY_H
#include "Array.h"
#endif

#ifndef DEFS_H
#include "Defs.h"
#endif

#ifndef MOT_H
#include "MOT.h"
#endif

#ifdef TEST_HI
//  #ifndef INCLUDED_iostream
    #include <iostream>
//    #define INCLUDED_iostream
//  #endif
#endif

#ifndef USER_H
#include "User.h"
#endif

//#include "Log.h"

namespace MM
{

template< class Data >
class MM_Hash_table
  {
    private:

      int                         hash_code;
      int                         counter, collision_counter;
      int                         size;

      Array< Array< int > >       key;
      Array< Data >             data;
      Array< int >                is_empty;

      int                         hash( unsigned int );
      int                         hash2();

      int                         is_equal( Array< int >, Array< int > ) const;

      MM_Hash_table( const MM_Hash_table & r );
      const MM_Hash_table &     operator = ( const MM_Hash_table & r );

    public:

      const Data *                get( const Array< int > & Key );
      void                        set( const Array< int > & Key, const Data & data );
      void                        add( const Array< int > & Key, const Data & data );

      int                         get_counter()             { return counter; }
      int                         get_collision_counter()   { return collision_counter; }
      void                        test(); 

      ~MM_Hash_table();
      MM_Hash_table( int Size );
  };

template< class Data >
inline int  MM_Hash_table< Data >::
hash( unsigned int code )
  {
    return hash_code = code % size;
  }

template< class Data >
inline int  MM_Hash_table< Data >::
hash2()
  {
     return ( hash_code != 0 ) ? size - hash_code : 1;
    //return ( hash_code != 0 ) ? hash_code-1 : size-1;
  }

template< class Data >
inline int  MM_Hash_table< Data >::
is_equal( Array< int > key1, Array< int > key2 ) const
  {
    int result = 1;
    for( int i=0;  i<key1.size();  i++ )  result &= key1[i] == key2[i];
    return  result; 
  }

template< class Data >
inline const Data *  MM_Hash_table< Data >::
get( const Array< int > & Key )
  {
    int i;
    unsigned int code = 0;
    for( i=0;  i<Key.size();  i++ ) code += Key[i] << ( 8 * i );
                                                               
    i = hash( code );
    
    for(;;)
      {
        if( is_empty[i] )                   return NULL;
        else if( is_equal( key[i], Key ) )  return &data[i];
        else
          {
            i -= hash2();
            if( i < 0 )  i += size;
          }
      }
  }

template< class Data >
inline void MM_Hash_table< Data >::
set( const Array< int > & the_key, const Data & the_data )
  {
    if( counter >= size - 1 )           to_user().error("Hash_table::set\nOverflow");
    else if( counter >= ( size >> 1 ) ) to_user().warning("Hash_table::set\nOverflow");

    int i;
    unsigned int code = 0;
    for( i=0;  i<the_key.size();  i++ ) 
    {
        int current_key = key[i];
        code += current_key << (8 * i);
    }
                                                               
    i = hash( code );
    
    for(;;)
      {
        if( is_empty[i] ) 
          {
            is_empty[i] = 0;
            key[i]  = the_key; 
            data[i] = the_data;
            counter++;
            break;
          }
        else 
            if( is_equal( key[i], the_key ) )  
                to_user().error("Hash_table::set\nKey already exist.");
        else
          {
            i -= hash2();
            if( i < 0 )  i += size;
            collision_counter++;
          }
      }
  }

template< class Data >
inline void MM_Hash_table< Data >::
add( const Array< int > & the_key, const Data & the_data )
  {
    if( counter >= size - 1 )           to_user().error("Hash_table::set\nOverflow");
    else if( counter >= ( size >> 1 ) ) to_user().warning("Hash_table::set\nOverflow");

    int i;
    unsigned int code = 0;
    for( i=0;  i<the_key.size();  i++ ) code += the_key[i] << ( 8 * i );
                                                               
    i = hash( code );
    
    for(;;)
      {
        if( is_empty[i] ) 
          {
            is_empty[i] = 0;
            key[i]  = the_key; 
            data[i] = the_data;
            counter++;
            break;
          }
        else if( is_equal( key[i], the_key ) )
          {
            data[i] += the_data;
//            Data tmp = data[i];             
//            data[i] = tmp + Data;

            break;
          }
        else
          {
            i -= hash2();
            if( i < 0 )  i += size;
            collision_counter++;
          }
      }
  }

#ifdef TESHI

template< class Data >
void  MM_Hash_table< Data >::
test()
  {
    cout << endl
      << "Hash table test" << endl
      << "Size " << size   << endl;

    for( int i=0;  i<size;  i++ )
      {
        cout << i << "   \tKey ";

        for( int j=0;  j<key[i].size();  j++ ) cout << key[i][j] << " ";

        cout
          << "   \tEmpty " << is_empty[i]
          << "   \tData " << data[i]
          << endl;
      }
  }
#endif

template< class Data >
MM_Hash_table< Data >::
MM_Hash_table( int Size )
  : hash_code( 0 ), counter( 0 ), collision_counter( 0 ), size( 0 )
  {
    const int prime_numbers[] =
      { 7, 11, 13,
        101, 211, 307, 401, 503, 701, 1009,
        2003, 3001, 4001, 5003, 0 };
    int i;

    size = ( Size >> 1 ) * 2 + 1;
    for( i=0;  prime_numbers[i] != 0;  i++ )
      {
        if( prime_numbers[i] >= size )
          {
            size = prime_numbers[i];
            break;
          }
      }
    //key.add_by_default( size );
    //data.add_by_default( size );
    //is_empty.add_by_default( size );

    for( i=0;  i<size;  i++ ) is_empty[i] = 1;
  }//*/

template< class Data >
MM_Hash_table< Data >::
~MM_Hash_table()
  {
    hash_code         = 0;
    counter           = 0;
    collision_counter = 0;
    size              = 0;
    for( int i=0;  i<size;  i++ ) is_empty[i] = 1;
  }

//================================================================================================

template< class Data >
class Angle_Hash_table
  {
    private:

      mutable int                 hash_code;
      int                         counter, collision_counter;
      int                         size;

      Array< Array< int > >       key;
      Array< Data >               data;
      Array< int >                is_empty;

      int                         hash (unsigned int) const;
      int                         hash2() const;

      int                         is_equal( Array< int >, Array< int > ) const;

      Angle_Hash_table( const Angle_Hash_table & r );
      const Angle_Hash_table &     operator = ( const Angle_Hash_table & r );

    public:

      const Data *              get( const Array< int > & Key ) const;
      void                        set( const Array< int > & Key, const Data & data );
//      void                        add( const Array< int > & Key, const Data & data );

      int                         get_counter()             { return counter; }
      int                         get_collision_counter()   { return collision_counter; }
      void                        test(); 

      ~Angle_Hash_table();
      Angle_Hash_table( int Size );

    private:
        void                key_already_exist (Array <int> const & Key);
  };

template< class Data >
inline int  Angle_Hash_table< Data >::
hash( unsigned int code ) const
  {
    return hash_code = code % size;
  }

template< class Data >
inline int  Angle_Hash_table< Data >::
hash2() const
  {
     return ( hash_code != 0 ) ? size - hash_code : 1;
    //return ( hash_code != 0 ) ? hash_code-1 : size-1;
  }

template< class Data >
inline int  Angle_Hash_table< Data >::
is_equal( Array< int > key1, Array< int > key2 ) const
  {
    int result = 1;
    for( int i=0;  i<key1.size();  i++ )  result &= key1[i] == key2[i];
    return  result; 
  }

template <class Data>
inline const Data *  Angle_Hash_table <Data>::
get (const Array <int> & the_key) const
{
    int i;
    unsigned int code = 0;

    for( i=0;  i<the_key.size();  i++ ) 
        code += the_key[i] << ( 8 * i );
                                                               
    i = hash( code );
    
    /*for(;;)
      {
        if( is_empty[i] )                   return NULL;
        else if( is_equal( key[i], the_key ) )  return &data[i];
        else
          {
            i -= hash2();
            if( i < 0 )  i += size;
          }
      }//*/

    if (is_empty[i])
        return 0;

    if (is_equal (key[i], the_key))  
        return &data[i];

    int c = hash2 ();
    
    for (;;)
    {
        i -= c;
        if (i<0)
            i += size;

        if (is_empty[i])
            return 0;

        else if (is_equal (key[i], the_key))  
            return &data[i];
    }

    FLAW ("Should not be here.");
}

template< class Data >
inline void Angle_Hash_table< Data >::
set( const Array< int > & the_key, const Data & the_data )
  {
    if( counter >= size - 1 )           to_user().error("Hash_table::set\nOverflow");
    else if( counter >= ( size >> 1 ) ) to_user().warning("Hash_table::set\nOverflow");

    int i;
    unsigned int code = 0;
    for( i=0;  i<the_key.size();  i++ ) 
        code += the_key[i] << ( 8 * i );
    //MM::log () << "### " << Key[0] << " " 
    //  << Key[1] << " " << Key[2] << " ###\n";
                                                               
    i = hash (code);

    if (!is_empty[i]) 
    {
        if (is_equal (key[i], the_key))  
        {
            key_already_exist (the_key);
            return;
        }

        int c = hash2 ();
        
        for (;;)
        {
            i -= c;
            if (i<0)
                i += size;

            if (is_empty[i])
                break;
            else if (is_equal (key[i], the_key))  
            {
                key_already_exist (the_key);
                return;
            }
        }
    }

    is_empty[i] = 0;
    key [i] = the_key; 
    data[i] = the_data;
    counter++;

    
    /*for(;;)
      {
        if( is_empty[i] ) 
          {
            is_empty[i] = 0;
            key [i] = the_key; 
            data[i] = the_data;
            counter++;
            break;
          }
        else 
            if( is_equal( key[i], the_key ) )  
                to_user().error("Hash_table::set\nKey already exist.");
        else
          {
            i -= hash2();
            if( i < 0 )  i += size;
            collision_counter++;
          }
      }//*/
  }

template <class Data>
inline void Angle_Hash_table <Data>::
key_already_exist (Array <int> const & the_key)
{
    Text message;
    message += "Angle_Hash_table::set\nKey ";
    message += mot().itoa(the_key[0]);
    message += " ";
    message += mot().itoa(the_key[1]);
    message += " ";
    message += mot().itoa(the_key[2]);
    message += " ";
    message += " already exist.";
    to_user().error (message);
}

/*
template< class Data >
inline void MM_Hash_table< Data >::
add( const Array< int > & Key, const Data & Data )
  {
    if( counter >= size - 1 )           error("Hash_table::set\nOverflow");
    else if( counter >= ( size >> 1 ) ) warning("Hash_table::set\nOverflow");

    int i;
    unsigned int code = 0;
    for( i=0;  i<Key.size();  i++ ) code += Key[i] << ( 8 * i );
                                                               
    i = hash( code );
    
    for(;;)
      {
        if( is_empty[i] ) 
          {
            is_empty[i] = 0;
            key[i]  = Key; 
            data[i] = Data;
            counter++;
            break;
          }
        else if( is_equal( key[i], Key ) )
          {
            data[i] += Data;
//            Data tmp = data[i];             
//            data[i] = tmp + Data;

            break;
          }
        else
          {
            i -= hash2();
            if( i < 0 )  i += size;
            collision_counter++;
          }
      }
  }
*/

template< class Data >
Angle_Hash_table< Data >::
Angle_Hash_table( int Size )
  : hash_code( 0 ), counter( 0 ), collision_counter( 0 ), size( 0 )
  {
    const int prime_numbers[] =
      { 7, 11, 13,
        101, 211, 307, 401, 503, 701, 1009,
        2003, 3001, 4001, 5003, 0 };
    int i;

    size = ( Size >> 1 ) * 2 + 1;
    for( i=0;  prime_numbers[i] != 0;  i++ )
      {
        if( prime_numbers[i] >= size )
          {
            size = prime_numbers[i];
            break;
          }
      }
    //key.add_by_default( size );
    //data.add_by_default( size );
    //is_empty.add_by_default( size );
    for( int k=0;  k<size;  ++k ) //fix
    {
        key.push_back( Array< int >() );
        data.push_back( Data() );
        is_empty.push_back( int() );
    }

    for( i=0;  i<size;  i++ ) is_empty[i] = 1;
  }

template< class Data >
Angle_Hash_table< Data >::
~Angle_Hash_table()
  {
    hash_code         = 0;
    counter           = 0;
    collision_counter = 0;
    size              = 0;
    for( int i=0;  i<size;  i++ ) is_empty[i] = 1;
  }

//================================================================================================

template< class Data >
class Torsion_Hash_table
  {
    private:

      mutable int                 hash_code;
      int                         counter, collision_counter;
      int                         size;

      Array< Array< int > >       key;
      Array< Data >               data;
      Array< int >                is_empty;

      int                         hash( unsigned int ) const;
      int                         hash2() const;

      int                         is_equal( Array< int >, Array< int > ) const;

      Torsion_Hash_table( const Torsion_Hash_table & r );
      const Torsion_Hash_table &     operator = ( const Torsion_Hash_table & r );

    public:

      const Data *                get( const Array< int > & Key ) const;
      void                        set( const Array< int > & Key, const Data & data );
      void                        add( const Array< int > & Key, const Data & data );

      int                         get_counter()             { return counter; }
      int                         get_collision_counter()   { return collision_counter; }
      void                        test(); 

      ~Torsion_Hash_table();
      Torsion_Hash_table( int Size );
  };

template< class Data >
inline int  Torsion_Hash_table< Data >::
hash( unsigned  code ) const
  {
    return hash_code = code % size;
  }

template< class Data >
inline int  Torsion_Hash_table< Data >::
hash2() const
  {
     return ( hash_code != 0 ) ? size - hash_code : 1;
    //return ( hash_code != 0 ) ? hash_code-1 : size-1;
  }

template< class Data >
inline int  Torsion_Hash_table< Data >::
is_equal( Array< int > key1, Array< int > key2 ) const
  {
    int result = 1;
    for( int i=0;  i<key1.size();  i++ )  result &= key1[i] == key2[i];
    return  result; 
  }

template< class Data >
inline const Data *  Torsion_Hash_table< Data >::
get( const Array< int > & Key ) const
  {
    int i;
    unsigned int code = 0;
    for( i=0;  i<Key.size();  i++ ) code += Key[i] << ( 8 * i );
                                                               
    i = hash( code );
    
    for(;;)
      {
        if( is_empty[i] )                   return NULL;
        else if( is_equal( key[i], Key ) )  return &data[i];
        else
          {
            i -= hash2();
            if( i < 0 )  i += size;
          }
      }
  }

template< class Data >
inline void Torsion_Hash_table< Data >::
set( const Array< int > & the_key, const Data & the_data )
  {
    if( counter >= size - 1 )           to_user().error("Hash_table::set\nOverflow");
    else if( counter >= ( size >> 1 ) ) to_user().warning("Hash_table::set\nOverflow");

    int i;
    unsigned int code = 0;
    for( i=0;  i<the_key.size();  i++ ) code += the_key[i] << ( 8 * i );
                                                               
    i = hash( code );
    
    for(;;)
      {
        if( is_empty[i] ) 
          {
            is_empty[i] = 0;
            key[i]  = the_key; 
            data[i] = the_data;
            counter++;
            break;
          }
        else 
            if( is_equal( key[i], the_key ) )  
                to_user().error("Hash_table::set\nKey already exist.");
        else
          {
            i -= hash2();
            if( i < 0 )  i += size;
            collision_counter++;
          }
      }
  }

template< class Data >
inline void Torsion_Hash_table< Data >::
add( const Array< int > & the_key, const Data & the_data )
  {
    if( counter >= size - 1 )           to_user().error("Hash_table::set\nOverflow");
    else if( counter >= ( size >> 1 ) ) to_user().warning("Hash_table::set\nOverflow");

    int i;
    unsigned int code = 0;
    for( i=0;  i<the_key.size();  i++ ) 
        code += the_key[i] << ( 8 * i );
                                                               
    i = hash( code );
    
    for(;;)
      {
        if( is_empty[i] ) 
          {
            is_empty[i] = 0;
            key[i]  = the_key; 
            data[i] = the_data;
            counter++;
            break;
          }
        else if( is_equal( key[i], the_key ) )
          {
//fix            data[i] += the_data;
            data[i].insert(data[i].end(), the_data.begin(), the_data.end());
//            Data tmp = data[i];             
//            data[i] = tmp + Data;

            break;
          }
        else
          {
            i -= hash2();
            if( i < 0 )  i += size;
            collision_counter++;
          }
      }
  }

template< class Data >
Torsion_Hash_table< Data >::
Torsion_Hash_table( int Size )
  : hash_code( 0 ), counter( 0 ), collision_counter( 0 ), size( 0 )
  {
    const int prime_numbers[] =
      { 7, 11, 13,
        101, 211, 307, 401, 503, 701, 1009,
        2003, 3001, 4001, 5003, 0 };
    int i;

    size = ( Size >> 1 ) * 2 + 1;
    for( i=0;  prime_numbers[i] != 0;  i++ )
      {
        if( prime_numbers[i] >= size )
          {
            size = prime_numbers[i];
            break;
          }
      }
    //key.add_by_default( size );
    //data.add_by_default( size );
    //is_empty.add_by_default( size );
    for( int k=0;  k<size;  ++k ) //fix
    {
        key.push_back( Array< int >() );
        data.push_back( Data() );
        is_empty.push_back( int() );
    }

    for( i=0;  i<size;  i++ ) is_empty[i] = 1;
  }

template< class Data >
Torsion_Hash_table< Data >::
~Torsion_Hash_table()
  {
    hash_code         = 0;
    counter           = 0;
    collision_counter = 0;
    size              = 0;
    for( int i=0;  i<size;  i++ ) is_empty[i] = 1;
  }

}//MM

#endif//MM_HASH_H
