# Fig. 20.12: Hashtable.pm
# Simple hash table implementation.

use warnings;
use strict;

package Hashtable;

# Hashtable constructor
sub new 
{
   my $type = shift();
   my $class = ref( $type ) || $type;
   
   my $self = { table => [ ]};
   $self->{ size } = shift() || 23;  # 23 is default size
   $self->{ function } = 
      shift() || hashFunction( $self->{ size } );

   foreach ( 0 .. $self->{ size } - 1 ) {
      $self->{ table }->[ $_ ] = [ ];
   }
   
   bless( $self, $class );
   return $self;
}             

# inserts an element in the table
sub insert 
{
   my $self = shift();
   my $data = shift();
   
   my $index = $self->{ function }->( $data );
   push( @{ $self->{ table }[ $index ] }, $data );
   return $index;
}

# removes an element from the table
sub remove {
   my $self = shift();
   my $data = shift();
   
   my $index = $self->{ function }->( $data );

   foreach ( 0 .. $#{ $self->{ table }[ $index ] } ) {
      if ( $self->{ table }[ $index ][ $_ ] eq $data ) {
         print "Deleting $data\n";
         splice( @{ $self->{ table }[ $index ] }, 
                 $_, 1, @{ [] } );
         return 1;
      }
   }
   
   return 0;
}

# outputs the contents of the table
sub printTable 
{
   my $self = shift();
   
   for ( my $i = 0; $i < $self->{ size }; $i++ ) {
      print "Bucket $i: @{ $self->{ table }[ $i ] }\n";
   }
}

# calculates the location of a key in the table
sub hashFunction 
{
   my $size = shift();

   return sub 
   {
      my $string = shift();
      my $number;

      while ( $string ) {
         $number += ord( substr( $string, 0, 1, '' ) );
      }

      return $number % $size;
   }
}

return 1;

###########################################################################
#  (C) Copyright 2001 by Deitel & Associates, Inc. and Prentice Hall.     #
#  All Rights Reserved.                                                   #
#                                                                         #
#  DISCLAIMER: The authors and publisher of this book have used their     #
#  best efforts in preparing the book. These efforts include the          #
#  development, research, and testing of the theories and programs        #
#  to determine their effectiveness. The authors and publisher make       #
#  no warranty of any kind, expressed or implied, with regard to these    #
#  programs or to the documentation contained in these books. The authors #
#  and publisher shall not be liable in any event for incidental or       #
#  consequential damages in connection with, or arising out of, the       #
#  furnishing, performance, or use of these programs.                     #
###########################################################################