#/*
# *  Copyright 2007-2008 hkrn <hikarin@users.sourceforge.jp>
# *
# *  Licensed under the Apache License, Version 2.0 (the "License");
# *  you may not use this file except in compliance with the License.
# *  You may obtain a copy of the License at
# *
# *      http://www.apache.org/licenses/LICENSE-2.0
# *
# *  Unless required by applicable law or agreed to in writing, software
# *  distributed under the License is distributed on an "AS IS" BASIS,
# *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# *  See the License for the specific language governing permissions and
# *  limitations under the License.
# */
#
# $Id: Trie.pm 1645 2008-02-06 15:40:18Z hikarin $
#

package Img0ch::Util::Trie;

# import from Regexp::Trie by dan kogai
# for backward compatiblity

use strict;

sub new { bless {}, __PACKAGE__ }

sub add {
    my ( $this, $str ) = @_;
    my $ref = $this;
    for my $char ( split //, $str ) {
        $ref->{$char} ||= {};
        $ref = $ref->{$char};
    }
    $ref->{''} = 1;    # { '' => 1 } as terminator
    $this;
}

sub _regexp {
    my ($this) = @_;
    $this->{''} and scalar keys %$this == 1 and return;    # terminator

    my ( @alt, @cc );
    my $q = 0;
    for my $char ( sort keys %$this ) {
        my $qchar = quotemeta $char;
        if ( ref $this->{$char} ) {
            if ( defined( my $recurse = _regexp( $this->{$char} ) ) ) {
                push @alt, $qchar . $recurse;
            }
            else {
                push @cc, $qchar;
            }
        }
        else {
            $q = 1;
        }
    }

    my $cconly = !@alt;
    @cc and push @alt, @cc == 1 ? $cc[0] : '[' . join( '', @cc ) . ']';
    my $result = @alt == 1 ? $alt[0] : '(?:' . join( '|', @alt ) . ')';
    $q and $result = $cconly ? "$result?" : "(?:$result)?";

    return $result;
}

sub regexp { my $str = shift->_regexp(); return qr/$str/ }

1;
__END__
