use strict;

use Carp;

package Anagram;

@Anagram::EXPORT = qw(anagram is_word starts_word);

BEGIN {
    $Anagram::version = "1.0";
    $Anagram::dict = {};

    open DICT, "</usr/dict/words" or croak("Could not open dictionary: $!");
    foreach (<DICT>) {
        s/\W//g;
        my @letters = split //, lc;

        # Insert word into sorted dictionary tree
        my $sub_table = $Anagram::dict;
        foreach (@letters) {
            # Create sub-table if it's missing and then recurse
            $sub_table->{$_} = {} if ref($sub_table->{$_}) ne 'HASH';
            $sub_table = $sub_table->{$_};
        }

        # Flag this entry as a valid word
        $sub_table->{word} = 1;
    }
    close DICT;
}

sub version {
    my $version = shift;

    warn "Version $version is later than $Anagram::version."
      if defined($version) && ($version > $Anagram::version);

    return $Anagram::version;
}

sub anagram {
    my $word = shift;

    # Create table of letters.  This is better than a pure table
    # because we avoid extra work for duplicated letters-- we can
    # anagram "aaaaa" in one cycle instead of 5! = 120 cycles.
    my $letters = {};
    foreach (split //, $word) {
        $letters->{$_}++;
    }

    return permute_recurse($letters, "");
}

sub permute_recurse {
    my ($letters, $prefix) = @_;

    my @words = ();
    foreach (keys %$letters) {
        # Test if any words start with this new prefix
        my $sub_prefix = $prefix.$_;
        my $sub_table = starts_word($sub_prefix);
        next unless $sub_table;

        # Use this letter
        if ($letters->{$_} <= 1) {
            delete $letters->{$_};
        } else {
            $letters->{$_}--;
        }

        # Test for recurse case
        if (scalar keys %$letters) {
            push @words, permute_recurse($letters, $sub_prefix);
        }
        # Test for base case
        elsif ($sub_table->{word}) {
            push @words, $sub_prefix;
        }

        # Restore letter
        $letters->{$_}++;
    }

    return @words;
}

sub is_word {
    my $sub_table = walk_dict(@_) or return undef;
    return $sub_table->{word};
}

# Returns a sub-table entry on true and undef on failutre
sub starts_word {
    my ($word) = @_;

    my $sub_table = $Anagram::dict;
    foreach (split //, $word) {
        $sub_table = $sub_table->{$_};
        return undef unless ref($sub_table) eq 'HASH';
    }

    return $sub_table;
}

1;