package ValueTree;

use CLR::Tree::Binary;
@ISA = qw(CLR::Tree::Binary);

use strict;

# Redefinable functions. 
# First returns the info fields of the node, second the structure fields.
sub FIELDS () {qw /key value/;}
## sub CHILDS () {qw /left right/;}

# $status = $tree->insert (key, value);
sub insert ($$$) {
    my $self  = shift;
    my $key   = shift;
    my $value = shift;

    if ($self->is_empty ()) {
        $self->{key}   = $key;
        $self->{value} = $value;
        $self->{left}  = $self->new ();
        $self->{right} = $self->new ();
        return 1;
    }

    return 0 if $self->eq ($key);
    $self->{$self->lt ($key) ? "left" : "right"}->insert ($key, $value);
}

# Return the value corresponding to the given key.
sub fetch ($$) {
    my $self = shift;
    my $key  = shift;
    my $tree = $self->_tree_fetch($key);
    return $tree && $tree->{value};
}

# Replace the value corresponding to the given key.
sub replace ($$$) {
    my $self = shift;
    my $key  = shift;
    my $value = shift;

    my $node = $self->_tree_fetch($key);
    if ($node) {
	$node->{value} = $value;
    } else {
	$self->insert($key, $value);
    } 
    return $value;
} 

# Return the tree corresponding to the given key.
sub _tree_fetch ($$) {
    my $self = shift;
    my $key  = shift;

    return undef   if $self->is_empty ();
    return $self   if $self->eq ($key);

    $self->{$self->lt ($key) ? "left" : "right"}->_tree_fetch($key);
} 

1;