view release on metacpan or  search on metacpan

lib/Tree/BPTree.pm  view on Meta::CPAN

sub split {
	my ($self, $n, $cmp, $key) = @_;

	# find the node we're going to insert to; split that node; if it splits
	# either incorporate the split in ourselves or split ourselves if we are
	# full
	my $v = $self->find($cmp, $key);
	my $result = $self->[($v) * 2]->split($n, $cmp, $key);
	if ((@$self + 1) / 2 == $n && defined $result) {
		# We're full and they split, we must split too. The way the split must
		# be handled will depend upon whether this is a Left, Center, or Right
		# split. That is, is the sub-split node pointer on the left side, the
		# middle, or the right. But first, let's go ahead and split the node in
		# half.
		#
		# The way a node can be split depends on the oddness of n. If n is odd
		# (normal looking node split), then we split at index n-1 and give the
		# new node n elements. If n is even, we split at index n and give the
		# new node n-1 elements. The combinatorics of this solution are kind of
		# interesting. In any case, we create the new node complete while