Test program for binary search algorithm

binsearch.pl

#!/usr/bin/perl

use strict;

use integer;
use Data::Dumper;

my @data = ();
my @order = ();
my $n = 0;
my $free = 0;

sub search($) {
	my ($s) = @_;
	my $delete = 0;

	if (substr($s, 0, 1) eq '-') {
		$delete = 1;
		$s = substr($s, 1);
		print "Deleting $s\n";
	} else {
		print "Searching for $s\n";
	}

	my $l = 0;
	my $r = $n;
	my ($i, $t, $new);

	while ($r > $l) {
		$t = ($r + $l) / 2;
		print "l = $l, t = $t, r = $r\n";

		if ($data[$order[$t]]->{str} eq $s) {
			print "found $s at $t\n";
			if ($delete) {

				# print Data::Dumper->Dump([\@order], [qw(*order)]);

				my $x = $order[$t];
				$data[$x]->{str} = "*free*";
				$n--;
				for ($i = $t; $i < $n; $i++) {
					my $j = $i+1;
					print "copy order[$j] to order[$i]\n";
					$order[$i] = $order[$j];
				}
				$order[$i] = $x;

				# print Data::Dumper->Dump([\@order], [qw(*order)]);
				print "n = $n, free = $free\n";
				print "data = ".join(', ', map { $_->{str} } @data)."\n";
				print "order = ".join(', ', @order)."\n";
				print "sorted = ".join(', ', map { $data[$_]->{str} } @order)."\n";
			}
			return;
		} elsif ($data[$order[$t]]->{str} gt $s) {
			$r = $t;
		} else {
			$l = $t+1;
		}
	}
	print "not found, l = $l, r = $r, n = $n, free = $free\n";

	return if $delete;

	# need to create - see if we already have a free one

	if ($free > $n) {
		$new = $order[$n++];
	} else {
		$new = $n++;
		$free = $n;
	}
	$data[$new] = { str => $s };

	# print Data::Dumper->Dump([\@order], [qw(*order)]);

	for ($t = $n-1 ; $t > $r;) {
		my $j = $t--;
		print "copy order[$t] to order[$j]\n";

		$order[$j] = $order[$t];
	}

	# print Data::Dumper->Dump([\@order], [qw(*order)]);

	$order[$t] = $new;
	print "inserted $s at $t\n";

	# print Data::Dumper->Dump([\@order], [qw(*order)]);

	print "n = $n, free = $free\n";
	print "data = ".join(', ', map { $_->{str} } @data)."\n";
	print "order = ".join(', ', @order)."\n";
	print "sorted = ".join(', ', map { $data[$_]->{str} } @order)."\n";
}

while (<>) {
	chomp;
	search($_);
}