package Dict2;

use strict;
use warnings;

use Lib;
use L;

our $REPR;

sub dict {
	my $hash = {};
	tie %$hash, __PACKAGE__, @_;
	bless $hash, __PACKAGE__;
	return $hash;
}

sub home {
	my ($self) = @_;
	my $tied = tied %$self;
	delete $tied->{i};
	delete $tied->{j};
	delete $tied->{last_was};
}

sub TIEHASH {
	my ($class) = shift;
	my %hash;
	my $repr = {
		keys => odds(\@_),
		hash => \%hash,
	};
	pairs {push @{$hash{$a}}, $b } @_;
	bless $repr, $class;
	$REPR = $repr;
	return $repr;
}

sub FIRSTKEY {
	my ($self) = @_;
	$self->{i} = -1;   # key index
	$self->{j} = {};   # index within elements per key
	$self->{saw_undef} = 0;
	my $key = $self->next_key;
#	print "FIRSTKEY: $key\n";
#	print D $self;
	return $key;
}

sub next_key {
	my ($self) = @_;
	my $key;
	while (1) {
		++$self->{i};
		if ($self->{i} == @{$self->{keys}}) {
			delete $self->{i};
			delete $self->{j};
			delete $self->{last_was};
			undef $key;
			if ($self->{saw_undef}) {
				$self->clean;
			}
			last;
		}
		$key = $self->{keys}[$self->{i}];
		$self->{j}{$key} //= -1;
		my $j = ++$self->{j}{$key};
		if (defined $self->{hash}{$key}[$j]) {
			last;
		}
		$self->{saw_undef} = 1;
	}
	if (defined $key) {
		$self->{last_was}{$key} = "key";
	}
	return $key;
}

sub NEXTKEY {
	my ($self, $lastkey) = @_;
	my $key = $self->next_key;
#	print "NEXTKEY: @{[$key||'undef']} lastkey: $lastkey\n";
#	print D $self;
	return $key;
}

sub clean {
	my ($self) = @_;
	return unless $self->{saw_undef};
	$self->{saw_undef} = 0;
	my @keys_out;
	my $count = {};
	for my $k (@{$self->{keys}}) {
		$count->{$k} //= -1;
		my $j = ++$count->{$k};
		my $a = $self->{hash}{$k};
#		print "clean $k $j\n";
		if (defined $a->[$j]) {
			push @keys_out, $k;
		}
	}
	$self->{keys} = \@keys_out;
	while (my ($k, $v) = each %{$self->{hash}}) {
#		print "cleanarys $k @$v\n";
		@$v = grep {defined $_} @$v;
		if (@$v == 0) {
			delete $self->{hash}{$k};
		}
	}
#	say "clean";
}

sub FETCH {
	my ($self, $key) = @_;
#	print "FETCH: $key\n";
#	print D $self;
	my $val;
	my $j = $self->{j}{$key} // 0;
	if ($self->{last_was}{$key} and $self->{last_was}{$key} eq "fetch" || $self->{last_was}{$key} eq "store") {
		$j = $self->next_j($key, $j);
	}
	my $a = $self->{hash}{$key};
	$val = $a->[$j];
	$self->{last_was}{$key} = "fetch";
	return $val;
}

sub STORE {
	my ($self, $key, $val, $delete) = @_;
#	print "STORE: $key $val\n" if !$delete;
	my $j = $self->{j}{$key};
	if ($self->{last_was}{$key} and $self->{last_was}{$key} eq "store") {
		$j = $self->next_j($key, $j, 1);
	}
	my $a = $self->{hash}{$key} ||= [];
	if (!defined $j || $j == @$a) {
		$j = @$a;
		push @{$self->{keys}}, $key;
	}
	my $oldval = $a->[$j];
	$a->[$j] = $val;
	$self->{last_was}{$key} = "store";
	return $delete ? $oldval : $val;
}

sub next_j {
	my ($self, $key, $j, $store) = @_;
	my $a = $self->{hash}{$key};
	my $old_j = $j;
	++$j;
	if ($store && $j == @$a) {
		$self->{j}{$key} = $j;
		return $j;
	}
	while (!defined $a->[$j] && $j != $old_j) {
		if ($j < @$a) {
			++$j;
		} else {
			$j = 0;
		}
	}
	$self->{j}{$key} = $j;
#	warn "$key $j\n";
	return $j;
}

sub DELETE {
	my ($self, $key) = @_;
#	print "DELETE: $key\n";
	$self->{saw_undef} = 1;
	return $self->STORE($key, undef, 1);
}

sub EXISTS {
	my ($self, $key) = @_;
	# TODO use EXISTS to count number of key foo, step through them
	# should use reset first to check if any of that key exists
	return exists $self->{keys}{$key} && grep {defined $_} @{$self->{hash}{$key}};
}

sub CLEAR {
	my ($self) = @_;
	%$self = (keys => [], hash => {});
}

sub SCALAR {
	my ($self) = @_;
	$self->clean;
	return scalar(@{$self->{keys}});
}

sub UNTIE {
	my ($self, $count) = @_;
}

sub DESTROY {
	my ($self) = @_;
}

sub dict2str {
	my ($dict) = @_;
	my $str = join " ", map {"$_:$dict->{$_}"} keys %$dict;
	return $str;
}

sub test {
	my %hash;
	tie %hash, 'Dict2', a=>4, b=>2, c=>1, a=>3;
	say keys %hash;
	say keys %hash;
	say values %hash;
	say values %hash;
	while (my ($k, $v) = each %hash) {
		print "$k:$v ";
	}
	say;
	while (my $k = each %hash) {
		print "$k:$hash{$k} ";
	}
	say;
	while (my $k = each %hash) {
		++$hash{$k};
	}
	say dict2str(\%hash);
	while (my $k = each %hash) {
		$hash{$k} = $k;
	}
	say dict2str(\%hash);
	my $z = $hash{c};
	$hash{c} = 9;
	$hash{c} = 10;
	$z = $hash{a};
	$z = $hash{a};
	$hash{a} = 99;
	my @k = keys %hash;
	$hash{c} = 11;
	@k = keys %hash;
#	print D $REPR;
	say dict2str(\%hash);
	say values %hash;
#	print D $REPR;
	say $hash{a};
	say $hash{a};
	say $hash{a};
	say values %hash;
	say $hash{a};
	say $hash{b};
	my $a = delete $hash{b};
	print "$a\n";
#	print D $REPR;
	say dict2str(\%hash);
#	print D $REPR;
	while (my ($k, $v) = each %hash) {
		if ($v > 10) {
			delete $hash{$k};
		}
	}
	say dict2str(\%hash);
#	bless \%hash;
#	print \%hash;
#	print tied %hash;

	my $hash2 = {%hash};
	say dict2str $hash2;

	use Benchmark qw(:all) ;
	timethese(50000, {
		'hash' => sub { my @foo = keys %$hash2 },
		'dict' => sub { my @foo = keys %hash },
	});

	untie %hash;

	my $foo = dict a=>1, b=>2, a=>3, b=>4;
	say dict2str $foo;
	say $foo->{b};
	$foo->home;
	say $foo->{b};
	$foo->{c} = 1;
	$foo->{c} = 2;
	say dict2str $foo;
	$foo->{c}++;
	$foo->{c}++;
	say dict2str $foo;
}

1
