package BSTree;
use strict;
use BSTNode;

sub new {
	my $class = shift;
	my $root = BSTNode->new;
	my $self = \$root;
	bless ($self, $class);
	return $self;
}

sub insert {
	my $self = shift;
	my $newval = shift;
	my $rootval = $$self->val;
#	defined($rootval) and print "Rootval: " . $rootval . "\n";
#	if (defined($$self->val)) {
	if (defined($rootval)) {
		my $current = $$self;
#		print $current . "\n";
		my $next = undef;
		do {
			if ($newval < $current->val) {
				$next = $current->left;
			} elsif ($newval > $current->val) {
				$next = $current->right;
			} elsif ($newval == $current->val) {
				$current = undef;
				$next = undef;
			}
			if (defined($next)) {$current = $next}
		} while (defined $next);
		if (defined($current)) {
			my $newnode = BSTNode->new;
			$newnode->val($newval);
			if ($newval < $current->val) { $current->left($newnode) }
			else { $current->right($newnode) }
			return 1;
		}
	} else { #We need a new root
#		print "Making new root...\n";
		my $root = $$self;
		$root->val($newval);
#		$self = \$root; #Useless, since $self is lexically scoped. Curses!
#		print $self->{'ROOT'} . "\n";
#		$rootval = $$self->val;
#		print "New root value: " . $rootval . "\n";
		return 1;
	}
	return 0;
}

sub find {
	my $self = shift;
	my $val = shift;
	my $current = $$self;
	my $cv = $current->val;
#	print $current . " Val: " . $cv;
	do {
		if ($current->val == $val) { return $current }
		elsif ($val < $current->val) { $current = $current->left }
		elsif ($val > $current->val) { $current = $current->right }
	} while (defined $current);
	return undef;
}

sub findWithParent {
	my $self = shift;
	my $val = shift;
	my $current = $$self;
	my $parent = undef;
#	my $cv = $current->val;
#	print $current . " Val: " . $cv;
	do {
#		print "Current node value: " . $current->val . "\n";
		if ($current->val == $val) { return ($current, $parent) }
		elsif ($val < $current->val) { $parent = $current; $current = $current->left }
		elsif ($val > $current->val) { $parent = $current; $current = $current->right }
	} while (defined $current);
	return undef;
}

sub remove {
	my $self = shift;
	my $val = shift;
	my ($node, $parent) = $self->findWithParent($val);
#	print "Removing " . $node->val . " with parent " . (defined($parent) ? $parent->val : "undef") . ".\n";
	if (defined($node)) {
		if (defined($node->left) and defined($node->right)) { #Two children; patch in a minimum
			my $replacement = $node->minBelow;
			$self->remove($replacement->val);
			$self->replace($node, $replacement, $parent);
		} elsif (defined($node->left)) { #One child; splice it upward
			if ($parent->val > $node->val && $parent->left == $node) { $parent->left($node->left) }
			elsif ($parent->val < $node->val && $parent->right == $node) { $parent->right($node->left) }
		} elsif (defined($node->right)) {
			if ($parent->val > $node->val && $parent->left == $node) { $parent->left($node->right) }
			elsif ($parent->val < $node->val && $parent->right == $node) { $parent->right($node->right) }
		} else { #No children; nobody will miss it
			if (defined $parent) { $self->orphan($node, $parent) }
		}
	}
}

#Breaks the link from a node's parent
# orphan(BSTNode node, BSTNode parent)
sub orphan {
	my $self = shift;
	my $node = shift;
	my $parent = shift;
	if ($parent->val > $node->val and $parent->left == $node) { $parent->left(undef); return 1 }
	elsif ($parent->val < $node->val and $parent->right == $node) { $parent->right(undef); return 1 }
	return 0;
}

#Moves a node to the place occupied by the old node
# replace(BSTNode oldNode, BSTNode replacementNode, BSTNode oldNodeParent)
sub replace {
	my $self = shift;
	my $node = shift;
	my $replacement = shift;
	my $parent = undef;
	if (@_) { $parent = shift; }
	if (defined $parent) {
		if ($parent->val > $node->val && $parent->left == $node) { $parent->left($replacement) }
		elsif ($parent->val < $node->val && $parent->right == $node) { $parent->right($replacement) }
	} else { #We're replacing the root
		$self->root($replacement);
		#Changing $self is pointless, since it is lexically scoped.
		#Redefine the reference it points to.
	}
	$replacement->left($node->left);
	$replacement->right($node->right);
	1;
}

#Initiates a recursive printing of all nodes and their children
sub traverse {
	my $self = shift;
	print "Here comes the tree...\n";
	$self->dive($$self);
}

sub dive {
	my $self = shift;
	my $node = shift;
	my $left = $node->left;
	my $right = $node->right;
	print ("Node: " . $node->val . (defined($left) ? " L: " . $left->val : "") . (defined($right) ? " R: " . $right->val : "") . "\n");
	if (defined($node->left)) { $self->dive($node->left) }
	if (defined($node->right)) { $self->dive($node->right) }
}

# root() Returns the tree's root
# root(BSTNode newRoot) Re-roots the tree with newRoot (not normally needed)
sub root {
	my $self = shift;
	if (@_) {$$self = shift};
	return $$self;
}

1;