#!/bin/bash

set -eu

unique_inorder_values=$(seq 100)

unique_first_10=$(echo "$unique_inorder_values" | head -10)
unique_last_10=$(echo "$unique_inorder_values" | tail -10 | tac)

dup_out_of_order_values=$(seq 100; seq 100)
dup_inorder_values=$(echo "$dup_out_of_order_values" | sort -n)

dup_first_10=$(echo "$dup_inorder_values" | head -10)
dup_last_10=$(echo "$dup_inorder_values" | tail -10 | tac)

rnd_values=$(echo "$dup_inorder_values" | sort -R)

fail=False

function compare
{
	fn="$1"
	echo "Checking $fn" 1>&2
	input="$2"
	expected_output="$3"
	actual_output=$(echo "$input" | eval "$fn" 2>&1)
	if [ "$expected_output" != "$actual_output" ]
	then
		echo "$fn failed:" 1>&2
		echo "Expected: $expected_output" 1>&2
		echo "Got: $actual_output" 1>&2
		fail=True
	else
		fail=False
	fi
}

for kind in '--use-bisect' '--use-treap' '--use-heap' '--use-rbtree' '--use-fibonacci-heap'
do
	for input in "$dup_inorder_values" "$rnd_values"
	do
		compare "./highest -n 10 $kind" "$input" "$dup_last_10"
		compare "./highest -n 10 -r $kind" "$input" "$dup_first_10"
		case "$kind" in
            "--use-heap") ;;
            '--use-fibonacci-heap') ;;
            *)
                compare "./highest -n 10 --disallow-duplicates $kind" "$input" "$unique_last_10"
                compare "./highest -n 10 --disallow-duplicates -r $kind" "$input" "$unique_first_10"
                ;;
        esac
	done
done

if [ "$fail" = True ]
then
	exit 1
else
	exit 0
fi