#!/usr/bin/perl

package Trie;

sub new {
  my $class = shift;
  bless [], $class;
}

sub insert {
  my $self = shift;
  my ($key) = @_;
  if ($key eq "") {
   $self->[0] = 1;
   return;
 }
  my ($car, $cdr) = ($key =~ /(.)(.*)/);
  my $i = (ord $car) - (ord 'A') + 1;
  $self->[$i] = Trie->new() unless ref $self->[$i];
  insert($self->[$i], $cdr);
}

{
  my $pos;

  sub write {
	my $self = shift;
	my ($fh) = @_;
	$pos = 0;
	$self->_write($fh, 0);
  }

  sub _write {
	my $self = shift;
	my ($fh, $where) = @_;
	my (@kids) = grep {$self->[$_]} (1..26);

	seek $fh, $where, 0;
	print $fh (pack("c", @kids * ($self->[0] ? 1 : -1))); # The '$' pseudo-entry.

	$pos += 4 * @kids + 1;
	foreach (0..$#kids) {
	  if ($self->[$kids[$_]]) {
		seek $fh, $where + 1 + 4 * $_, 0;
		print $fh substr((pack "cl", $kids[$_], $pos), 0, 4);
		$self->[$kids[$_]]->_write($fh, $pos);
	  }
	}
  }
}

package main;
 
$|=1;
print "Loading dictionary...";

$trie = Trie->new();
open(IN, "/usr/share/dict/words") or die $!;
for(<IN>) {
  chomp;
  next if /^[A-Z]/;
  next if /[^a-zA-Z]/;
  next if length == 2;
	$s = uc $_;
  $trie->insert($s);
  $foo++;
  print "." unless ($foo % 5000);
}
print "\n";
print "Writing dictionary...\n";
open(OUT, ">ptkboggle.dict") or die $!;
$trie->write(\*OUT);
close(OUT);
print "Done.\n";