class Hash : precompile {
  use Hash::Entry;
  use Fn;

  has bucket_count : int;
  has count : ro int;
  has entries : Hash::Entry[];

  private enum {
    _DEFALUT_HASH_TABLE_LENGTH = 16,
  }
  private static method _MAX_LOAD_FACTOR : double () { return 0.75; }

  static method new : Hash ($key_values : object[]) {
    my $self = new Hash;
    
    my $default_capacity = 32;
    $self->{bucket_count} = Hash->_DEFALUT_HASH_TABLE_LENGTH();
    $self->{entries} = new Hash::Entry[Hash->_DEFALUT_HASH_TABLE_LENGTH()];
    $self->{count} = 0;
    
    my $length : int;
    if ($key_values) {
      $length = @$key_values;
    }
    else {
      $length = 0;
    }
    
    if ($length % 2 != 0) {
      die "Odd number array is invalid";
    }
    
    if ($key_values) {
      for (my $i = 0; $i < @$key_values; $i += 2) {
        my $key = (string)$key_values->[$i];
        my $value = $key_values->[$i + 1];
        unless ($key isa string) {
          die "Key must be string";
        }

        $self->set($key => $value);
      }
    }
    
    return $self;
  }

  method set : void ($key : string, $val : object) {
    unless ($key) {
      die "key must not be undef";
    }
    # Rehash
    if (((double)$self->{count} / $self->{bucket_count}) > Hash->_MAX_LOAD_FACTOR()) {
      $self->_rehash;
    }
    my $count = $self->{count};
    Hash->_set_to_container($self->{entries}, $self->{bucket_count}, \$count, $key, $val);
    $self->{count} = $count;
  }

  method get : object ($key : string) {
    my $index = Hash->_index_by_key($key, $self->{bucket_count});
    my $ref = $self->{entries}->[$index];
    unless ($ref) {
      return undef;
    }
    while (1) {
      if ($ref->{key} eq $key) {
        return $ref->{val};
      }
      unless ($ref->{next_entry}) {
        return undef;
      }
      $ref = $ref->{next_entry};
    }
  }

  method exists : int ($key : string) {
    my $index = Hash->_index_by_key($key, $self->{bucket_count});
    my $ref = $self->{entries}->[$index];

    unless ($ref) {
      return 0;
    }
    while (1) {
      if ($ref->{key} eq $key) {
        return 1;
      }
      unless ($ref->{next_entry}) {
        return 0;
      }
      $ref = $ref->{next_entry};
    }
  }

  method delete : object ($key : string) {
    my $index = Hash->_index_by_key($key, $self->{bucket_count});
    my $ref = $self->{entries}->[$index];
    my $prev : Hash::Entry = undef;
    unless ($ref) {
      return undef;
    }
    while (1) {
      if ($ref->{key} eq $key) {
        my $ret = $ref->{val};
        if ($prev) {
          $prev->{next_entry} = $ref->{next_entry};
        }
        else {
          $self->{entries}->[$index] = $ref->{next_entry};
        }
        $self->{count}--;
        return $ret;
      }
      unless ($ref->{next_entry}) {
        return undef;
      }
      $prev = $ref;
      $ref = $ref->{next_entry};
    }
  }

  method keys : string[] () {
    my $keys = new string[$self->{count}];
    # iterate entries
    my $count = 0;
    for (my $i = 0; $i < $self->{bucket_count}; ++$i) {
      my $ref = $self->{entries}->[$i];
      while ($ref) {
        $keys->[$count++] = $ref->{key};
        $ref = $ref->{next_entry};
      }
    }
    return $keys;
  }

  method values : object[] () {
    my $retval = new object[$self->{count}];
    # iterate entries
    my $count = 0;
    for (my $i = 0; $i < $self->{bucket_count}; ++$i) {
      my $ref = $self->{entries}->[$i];
      while ($ref) {
        $retval->[$count++] = $ref->{val};
        $ref = $ref->{next_entry};
      }
    }
    return $retval;
  }

  method copy : Hash () {
    my $ret = Hash->new({});
    my $keys = $self->keys;
    for (my $i = 0; $i < @$keys; ++$i) {
      $ret->set($keys->[$i], $self->get($keys->[$i]));
    }
    return $ret;
  }

  native static method _murmur_hash : long ($string : string, $seed : int);

  method set_byte : void ($name : string, $value : byte) {
    $self->set($name => Byte->new($value));
  }
  method set_short : void ($name : string, $value : short) {
    $self->set($name => Short->new($value));
  }
  method set_int : void ($name : string, $value : int) {
    $self->set($name => Int->new($value));
  }
  method set_string : void ($name : string, $value : string) {
    $self->set($name => $value);
  }
  method set_long : void ($name : string, $value : long) {
    $self->set($name => Long->new($value));
  }
  method set_float : void ($name : string, $value : float) {
    $self->set($name => Float->new($value));
  }
  method set_double : void ($name : string, $value : double) {
    $self->set($name => Double->new($value));
  }

  method get_byte : byte ($name : string) {
    return (byte)$self->get($name);
  }
  method get_short : short ($name : string) {
    return (short)$self->get($name);
  }
  method get_int : int ($name : string) {
    return (int)$self->get($name);
  }
  method get_string : string ($name : string) {
    return (string)$self->get($name);
  }
  method get_long : long ($name : string) {
    return (long)$self->get($name);
  }
  method get_float : float ($name : string) {
    return (float)$self->get($name);
  }
  method get_double : double ($name : string) {
    return (double)$self->get($name);
  }

  method _bucket_count : int () {
    return $self->{bucket_count};
  }

  method _entries : Hash::Entry [] () {
    return $self->{entries};
  }

  static method _index_by_key : int ($key : string, $bucket_count : int) {
    my $default_seed = 123456789;
    return (int)(Hash->_murmur_hash($key, $default_seed) % $bucket_count);
  }

  static method _set_to_container : void (
    $entries : Hash::Entry[],
    $bucket_count : int,
    $count_ref : int*,
    $key : string,
    $val : object)
  {
    my $index = Hash->_index_by_key($key, $bucket_count);
    my $ref = $entries->[$index];
    unless ($ref) {
      $entries->[$index] = new Hash::Entry;
      my $new_key : string;
      if (is_read_only $key) {
        $new_key = $key;
      }
      else {
        $new_key = Fn->copy_string($key);
        make_read_only $new_key;
      }
      
      $entries->[$index]->{key} = $new_key;
      $entries->[$index]->{val} = $val;
      $entries->[$index]->{next_entry} = undef;
      ++$$count_ref;
      return;
    }
    while (1) {
      if ($ref->{key} eq $key) {
        $ref->{val} = $val;
        return;
      }
      unless ($ref->{next_entry}) {
        my $new_key : string;
        if (is_read_only $key) {
          $new_key = $key;
        }
        else {
          $new_key = Fn->copy_string($key);
          make_read_only $new_key;
        }

        $ref->{next_entry} = new Hash::Entry;
        $ref->{next_entry}->{key} = $new_key;
        $ref->{next_entry}->{val} = $val;
        $ref->{next_entry}->{next_entry} = undef;
        ++$$count_ref;
        return;
      }
      $ref = $ref->{next_entry};
    }
  }

  method _rehash : void () {
    my $new_bucket_count : int;
    $new_bucket_count = $self->{bucket_count} * 2;
    my $new_entries = new Hash::Entry [$new_bucket_count];
    my $new_count = 0;
    # iterate entries
    for (my $i = 0; $i < $self->{bucket_count}; ++$i) {
      my $ref = $self->{entries}->[$i];
      while ($ref) {
        Hash->_set_to_container($new_entries, $new_bucket_count, \$new_count, $ref->{key}, $ref->{val});
        $ref = $ref->{next_entry};
      }
    }
    $self->{bucket_count} = $new_bucket_count;
    $self->{entries} = $new_entries;
  }
}