"""Show that selection sort is not a stable sort.

Run with ``pytest hypostable.py``.

I asserted to my wife that selection sort is not a stable sort, and so
is not suitable for getting a list sorted by a compound key by sorting
it with two simple keys.  But I had a hard time coming up with a
minimal counterexample.

But you know what's fantastic at coming up with minimal
counterexamples to hypotheses about program behavior?  DRMacIver's
Hypothesis.

Python ``.sort()`` and ``sorted()`` are happy to sort things by a
compound key by default, which makes the test easy to write.

This finds the counterexamples
[(-1, 1), (0, 1), (0, 0)] and 
[( 0, 2), (1, 1), (1, 0)].

"""
from hypothesis import given
from hypothesis.strategies import lists, tuples, integers


def selection_sort(seq, less_than):
    for i in range(len(seq)-1):
        min_idx = i
        for j in range(i+1, len(seq)):
            if less_than(seq[j], seq[min_idx]):
                min_idx = j

        seq[i], seq[min_idx] = seq[min_idx], seq[i]


def insertion_sort(seq, less_than):
    for i in range(1, len(seq)):
        j = i
        while j > 0:
            if less_than(seq[j], seq[j-1]):
                seq[j], seq[j-1] = seq[j-1], seq[j]
                j -= 1
            else:
                break
    

@given(lists(tuples(integers(), integers())))
def test_selection_sort_stability(xys):
    check_stability(selection_sort, xys)

    
@given(lists(tuples(integers(), integers())))
def test_insertion_stability(xys):
    check_stability(insertion_sort, xys)


def check_stability(sort_function, xys):
    xys = xys[:]
    correct = sorted(xys)
    sort_function(xys, lambda a, b: a[1] < b[1])
    sort_function(xys, lambda a, b: a[0] < b[0])
    assert xys == correct