# Copyright (c) 2023 Yuki Kimoto
# MIT License
class Hash {
use Hash::Entry;
use Fn;
use Array;
use Sort;
use Format;
# Interfaces
interface Cloneable;
# Fields
has keys_length : ro int;
# Private Fields
has entries : Hash::Entry[];
has seed : mutable string;
# Private Enumerations
private enum {
DEFALUT_ENTRIES_LENGTH = 1,
}
# Class Methods
precompile static method new : Hash ($key_values : object[] = undef) {
my $self = new Hash;
my $default_entries_length = &DEFALUT_ENTRIES_LENGTH();
$self->{entries} = new Hash::Entry[$default_entries_length];
$self->{keys_length} = 0;
my $seed_int32 = Fn->object_to_int($self);
$self->{seed} = (mutable string)new_string_len 16;
$self->build_seed($seed_int32, $self->{seed});
my $length : int;
if ($key_values) {
$length = @$key_values;
}
else {
$length = 0;
}
if ($length % 2 != 0) {
die "The length of the elements in the key-value pairs \$key_values must be an even number.";
}
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 "The key in the key-value pairs \$key_values must be string.";
}
$self->set($key => $value);
}
}
return $self;
}
# Private or Internal Class Methods
private native static method _siphash13 : long ($string : string, $seed : string);
private static method _MAX_LOAD_FACTOR : double () { return 0.75; }
native static method _murmur_hash : long ($string : string, $seed : int);
# Instance Methods
precompile 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;
}
method clone : Hash () {
return $self->copy;
}
method set : void ($key : string, $value : object) {
unless ($key) {
die "The key \$key must be defined.";
}
# Rehash
if (((double)$self->{keys_length} / @{$self->{entries}}) > Hash->_MAX_LOAD_FACTOR()) {
$self->_rehash;
}
my $keys_length = $self->{keys_length};
$self->_set_to_container($self->{entries}, @{$self->{entries}}, \$keys_length, $key, $value, 0);
$self->{keys_length} = $keys_length;
}
method get : object ($key : string) {
my $entry = $self->get_entry($key);
my $value = (object)undef;
if ($entry) {
$value = $entry->{value};
}
return $value;
}
method weaken : void ($key : string) {
my $entry = $self->get_entry($key);
if ($entry) {
weaken $entry->{value};
}
}
method unweaken : void ($key : string) {
my $entry = $self->get_entry($key);
if ($entry) {
unweaken $entry->{value};
}
}
method isweak : int ($key : string) {
my $entry = $self->get_entry($key);
my $isweak = 0;
if ($entry) {
$isweak = isweak $entry->{value};
}
return $isweak;
}
precompile private method get_entry : Hash::Entry ($key : string) {
unless ($key) {
die "The key \$key must be defined.";
}
my $index = $self->_index_by_key($key, @{$self->{entries}});
my $entry = $self->{entries}->[$index];
unless ($entry) {
return undef;
}
while (1) {
if ($entry->{key} eq $key) {
return $entry;
}
unless ($entry->{next_entry}) {
return undef;
}
$entry = $entry->{next_entry};
}
}
precompile method exists : int ($key : string) {
unless ($key) {
die "The key \$key must be defined.";
}
my $index = $self->_index_by_key($key, @{$self->{entries}});
my $entry = $self->{entries}->[$index];
unless ($entry) {
return 0;
}
while (1) {
if ($entry->{key} eq $key) {
return 1;
}
unless ($entry->{next_entry}) {
return 0;
}
$entry = $entry->{next_entry};
}
}
precompile method delete : object ($key : string) {
unless ($key) {
die "The key \$key must be defined.";
}
my $index = $self->_index_by_key($key, @{$self->{entries}});
my $entry = $self->{entries}->[$index];
my $prev : Hash::Entry = undef;
unless ($entry) {
return undef;
}
while (1) {
if ($entry->{key} eq $key) {
my $ret = $entry->{value};
if ($prev) {
$prev->{next_entry} = $entry->{next_entry};
}
else {
$self->{entries}->[$index] = $entry->{next_entry};
}
$self->{keys_length}--;
return $ret;
}
unless ($entry->{next_entry}) {
return undef;
}
$prev = $entry;
$entry = $entry->{next_entry};
}
}
precompile method keys : string[] () {
my $keys = new string[$self->{keys_length}];
# iterate entries
my $keys_length = 0;
my $entries_length = @{$self->{entries}};
for (my $i = 0; $i < $entries_length; ++$i) {
my $entry = $self->{entries}->[$i];
while ($entry) {
$keys->[$keys_length++] = $entry->{key};
$entry = $entry->{next_entry};
}
}
return $keys;
}
precompile method has_keys : int () {
my $has_keys = 0;
if ($self->{keys_length} > 0) {
$has_keys = 1;
}
return $has_keys;
}
precompile method values : object[] () {
my $retvalue = new object[$self->{keys_length}];
# iterate entries
my $keys_length = 0;
my $entries_length = @{$self->{entries}};
for (my $i = 0; $i < $entries_length; ++$i) {
my $entry = $self->{entries}->[$i];
while ($entry) {
$retvalue->[$keys_length++] = $entry->{value};
$entry = $entry->{next_entry};
}
}
return $retvalue;
}
precompile method to_array : object[] ($sort : int = 0) {
my $keys = $self->keys;
my $keys_length = @$keys;
if ($sort > 0) {
Sort->sort_string_asc($keys);
}
elsif ($sort < 0) {
Sort->sort_string_desc($keys);
}
my $array = new object[$keys_length * 2];
for (my $i = 0; $i < $keys_length; $i++) {
my $key = $keys->[$i];
$array->[$i * 2] = $key;
my $value = $self->get($key);
$array->[$i * 2 + 1] = $value;
}
return $array;
}
method set_byte : void ($key : string, $value : int) {
$self->set($key => Byte->new($value));
}
method set_short : void ($key : string, $value : int) {
$self->set($key => Short->new($value));
}
method set_int : void ($key : string, $value : int) {
$self->set($key => Int->new($value));
}
method set_string : void ($key : string, $value : string) {
$self->set($key => $value);
}
method set_long : void ($key : string, $value : long) {
$self->set($key => Long->new($value));
}
method set_float : void ($key : string, $value : float) {
$self->set($key => Float->new($value));
}
method set_double : void ($key : string, $value : double) {
$self->set($key => Double->new($value));
}
method get_byte : int ($key : string) {
my $object = $self->get($key);
unless ($object is_type Byte) {
die "The type of the value for the key \"$key\" must Byte type.";
}
return (int)(byte)$object;
}
method get_short : int ($key : string) {
my $object = $self->get($key);
my $value = 0;
if ($object is_type Byte) {
$value = (int)(byte)$object;
}
elsif ($object is_type Short) {
$value = (int)(short)$object;
}
else {
die "The type of the value for the key \"$key\" must Short type or Byte type.";
}
return $value;
}
method get_int : int ($key : string) {
my $object = $self->get($key);
my $value = 0;
if ($object is_type Byte) {
$value = (int)(byte)$object;
}
elsif ($object is_type Short) {
$value = (int)(short)$object;
}
elsif ($object is_type Int) {
$value = (int)$object;
}
else {
die "The type of the value for the key \"$key\" must Int type, Short type or Byte type.";
}
return $value;
}
method get_long : long ($key : string) {
my $object = $self->get($key);
my $value = 0L;
if ($object is_type Byte) {
$value = (long)(byte)$object;
}
elsif ($object is_type Short) {
$value = (long)(short)$object;
}
elsif ($object is_type Int) {
$value = (long)(int)$object;
}
elsif ($object is_type Long) {
$value = (long)$object;
}
else {
die "The type of the value for the key \"$key\" must Long type, Int type, Short type or Byte type.";
}
return $value;
}
method get_float : float ($key : string) {
my $object = $self->get($key);
unless ($object is_type Float) {
die "The type of the value for the key \"$key\" must Float type.";
}
return (float)$object;
}
method get_double : double ($key : string) {
my $object = $self->get($key);
unless ($object is_type Double) {
die "The type of the value for the key \"$key\" must Double type.";
}
return (double)$object;
}
method get_string : string ($key : string) {
my $object = $self->get($key);
unless (!$object || $object is_type string) {
die "The type of the value for the key \"$key\" must be string type.";
}
return (string)$object;
}
method get_or_default_byte : int ($key : string, $default : int) {
my $value = 0;
if ($self->exists($key)) {
$value = $self->get_byte($key);
}
else {
$value = $default;
}
return $value;
}
method get_or_default_short : int ($key : string, $default : int) {
my $value = 0;
if ($self->exists($key)) {
$value = $self->get_short($key);
}
else {
$value = $default;
}
return $value;
}
method get_or_default_int : int ($key : string, $default : int) {
my $value = 0;
if ($self->exists($key)) {
$value = $self->get_int($key);
}
else {
$value = $default;
}
return $value;
}
method get_or_default_long : long ($key : string, $default : long) {
my $value = 0L;
if ($self->exists($key)) {
$value = $self->get_long($key);
}
else {
$value = $default;
}
return $value;
}
method get_or_default_float : float ($key : string, $default : float) {
my $value = 0f;
if ($self->exists($key)) {
$value = $self->get_float($key);
}
else {
$value = $default;
}
return $value;
}
method get_or_default_double : double ($key : string, $default : double) {
my $value = 0.0;
if ($self->exists($key)) {
$value = $self->get_double($key);
}
else {
$value = $default;
}
return $value;
}
method get_or_default_string : string ($key : string, $default : string) {
my $value = (string)undef;
if ($self->exists($key)) {
$value = $self->get_string($key);
}
else {
$value = $default;
}
return $value;
}
method get_or_default : object ($key : string, $default : object) {
my $value = (object)undef;
if ($self->exists($key)) {
$value = $self->get($key);
}
else {
$value = $default;
}
return $value;
}
method delete_or_default_byte : int ($key : string, $default : int) {
my $value = 0;
if ($self->exists($key)) {
$value = $self->get_byte($key);
$self->delete($key);
}
else {
$value = $default;
}
return $value;
}
method delete_or_default_short : int ($key : string, $default : int) {
my $value = 0;
if ($self->exists($key)) {
$value = $self->get_short($key);
$self->delete($key);
}
else {
$value = $default;
}
return $value;
}
method delete_or_default_int : int ($key : string, $default : int) {
my $value = 0;
if ($self->exists($key)) {
$value = $self->get_int($key);
$self->delete($key);
}
else {
$value = $default;
}
return $value;
}
method delete_or_default_long : long ($key : string, $default : long) {
my $value = 0L;
if ($self->exists($key)) {
$value = $self->get_long($key);
$self->delete($key);
}
else {
$value = $default;
}
return $value;
}
method delete_or_default_float : float ($key : string, $default : float) {
my $value = 0f;
if ($self->exists($key)) {
$value = $self->get_float($key);
$self->delete($key);
}
else {
$value = $default;
}
return $value;
}
method delete_or_default_double : double ($key : string, $default : double) {
my $value = 0.0;
if ($self->exists($key)) {
$value = $self->get_double($key);
$self->delete($key);
}
else {
$value = $default;
}
return $value;
}
method delete_or_default_string : string ($key : string, $default : string) {
my $value = (string)undef;
if ($self->exists($key)) {
$value = $self->get_string($key);
$self->delete($key);
}
else {
$value = $default;
}
return $value;
}
method delete_or_default : object ($key : string, $default : object) {
my $value = (object)undef;
if ($self->exists($key)) {
$value = $self->get($key);
$self->delete($key);
}
else {
$value = $default;
}
return $value;
}
# Private or Internal Instance Methods
native private method build_seed : void ($seed_int32 : int, $seed : mutable string);
method _entries : Hash::Entry [] () {
return $self->{entries};
}
private method _index_by_key : int ($key : string, $entries_length : int) {
my $default_seed = $self->{seed};
my $hash = Hash->_siphash13($key, $default_seed);
my $index_by_key = (int)($hash mod_ulong (long)$entries_length);
return $index_by_key;
}
precompile private method _set_to_container : void (
$entries : Hash::Entry[],
$entries_length : int,
$keys_length_ref : int*,
$key : string,
$value : object,
$isweak : int)
{
my $index = $self->_index_by_key($key, $entries_length);
my $entry = $entries->[$index];
unless ($entry) {
$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]->{value} = $value;
if ($isweak) {
my $tmp = $entries->[$index];
weaken $tmp->{value};
}
$entries->[$index]->{next_entry} = undef;
++$$keys_length_ref;
return;
}
while (1) {
if ($entry->{key} eq $key) {
$entry->{value} = $value;
if ($isweak) {
weaken $entry->{value};
}
return;
}
unless ($entry->{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;
}
$entry->{next_entry} = new Hash::Entry;
$entry->{next_entry}->{key} = $new_key;
$entry->{next_entry}->{value} = $value;
if ($isweak) {
my $tmp = $entry->{next_entry};
weaken $tmp->{value};
}
$entry->{next_entry}->{next_entry} = undef;
++$$keys_length_ref;
return;
}
$entry = $entry->{next_entry};
}
}
precompile private method _rehash : void () {
my $new_entries_length : int;
my $entries_length = @{$self->{entries}};
$new_entries_length = @{$self->{entries}} * 2;
my $new_entries = new Hash::Entry [$new_entries_length];
my $new_keys_length = 0;
# iterate entries
for (my $i = 0; $i < $entries_length; ++$i) {
my $entry = $self->{entries}->[$i];
while ($entry) {
$self->_set_to_container($new_entries, $new_entries_length, \$new_keys_length, $entry->{key}, $entry->{value}, isweak $entry->{value});
$entry = $entry->{next_entry};
}
}
$self->{entries} = $new_entries;
}
}