# author: bliako
# date:   25/02/2020
# for:    https://perlmonks.org/?node_id=11113388

use strict;
use warnings;

use AVLTree;

# create a binary tree with custom string comparator
# if cmp < 0, word goes to the left of current node
# if cmp > 0, word goes to the right
# if cmp == 0, word is identical to the current node
my $tree = AVLTree->new(sub { $_[0] cmp $_[1] });

open(my $IN, '<', '/usr/share/dict/words');

my $tstart = time;
my $numwords = 0;
while( my $aword=<$IN> ){
	chomp $aword;
	$tree->insert($aword);
	$numwords++;
}
close($IN);
print "$0 : tree size: ".$tree->size()." (same as $numwords in file).\n";
print "$0 : inserted $numwords words in ".(time-$tstart)." seconds.\n";

open($IN, '<', '/usr/share/dict/words'); 
$numwords = 0;
$tstart = time;
while( my $astopword=<$IN> ){
	chomp $astopword;
	next if rand>0.05;
	if( ! $tree->find($astopword) ){ print STDERR "$0 : error, did not find the word '$astopword', that's not right\n"; exit(1); }
	$numwords++;
}
close($IN); # edit: forgot that!
print "search $numwords words in ".(time-$tstart)." seconds.\n";