package Patricia;


use English;
use Carp;

# use strict;
use integer;

$Patricia::MAXB = 9999999;

sub new {
    if (@ARG > 1) {
	confess  "usage: new Patricia";
    } 
    if (@ARG == 1) {
	my $self = shift;
	if ($self ne "Patricia" && ref $self ne "Patricia") { 
	    confess "invalid obref";
	}
    } 

    my $node = bless {};

    %$node = (
	"LEFT" 	=> $node,
	"RIGHT"	=> $node,
	"KEY" 	=> 0,
	"INFO" 	=> "",
	"BITS" 	=> $Patricia::MAXB,
    );

    return $node;

} 

sub search { my ($head,$v) = @ARG;

    if (@ARG != 2)               { confess "usage: search TREE KEY" } 
    if (ref $head ne "Patricia") { confess "invalid obref" }

    my $p = $head;
    my $x = $head->{"LEFT"};

    while ($p->{"BITS"} > $x->{"BITS"}) {
	$p = $x;
	$x = $x->{ bits($v, $x->{"BITS"}, 1) ? "RIGHT" : "LEFT" };
    } 
    if ($v == $x->{"KEY"}) {
	return $x->{"INFO"};
    } else {
	return undef;
    } 
} 

sub insert { my ($head, $v, $info) = @ARG;

    if (@ARG != 3) 		 { confess "usage: insert TREE KEY INFO" }
    if (ref $head ne "Patricia") { confess "invalid obref" }

    my ($p, $t, $x);

    my $i = $Patricia::MAXB;
    $p = $head;
    $t = $head->{"LEFT"};

    while ( $p->{"BITS"} > $t->{"BITS"} ) {
	$p = $t;
	$t = $t->{bits($v, $t->{"BITS"}, 1) ? "RIGHT" : "LEFT"};
    } 

    if ($v == $t->{"KEY"}) { return }

    while (bits($t->{"KEY"}, $i, 1) == bits($v, $i, 1)) { $i-- } 

    $p = $head;
    $x = $head->{"LEFT"};
    while ($p->{"BITS"} > $x->{"BITS"} && $x->{"BITS"} > $i) {
	$p = $x;
	$x = bits($v, $x->{"BITS"}, 1) ? $x->{"RIGHT"} : $x->{"LEFT"};
    } 

    $t = new();
    $t->{"KEY"} = $v; $t->{"INFO"} = $info; $t->{"BITS"} = $i;
    $t->{"LEFT"}  = (bits($v, $t->{"BITS"}, 1)) ? $x : $t;
    $t->{"RIGHT"} = (bits($v, $t->{"BITS"}, 1)) ? $t : $x;
    $p->{ bits($v, $p->{"BITS"}, 1) ? "RIGHT" : "LEFT" } = $t;
} 

sub bits {
    my($x, $k, $j) = @_;
    ($x >> $k) & ~(~0 << $j);
} 

sub print {	my($node) = @ARG;
    if (@ARG != 1) 		 { confess "usage: dump TREE" }
    if (ref $node ne "Patricia") { confess "invalid obref" }

    print <<EOF;
Node is $node
	BITS	$node->{"BITS"} 	
	KEY	$node->{"KEY"} 	
	INFO	$node->{"INFO"} 	
	LEFT	$node->{"LEFT"} 
	RIGHT	$node->{"RIGHT"} 	
EOF
} 

sub dtree {
    local %Patricia::seen;
    &Patricia::rdumpdree;
}

sub rdumpdree {
    my($node) = @ARG;
    $node->{"LEFT"}->rdumpdree()  unless $Patricia::seen{$node}++;
    $node->print();
    $node->{"RIGHT"}->rdumpdree() unless $Patricia::seen{$node}++;
}