#!/usr/bin/python3
"""Hypothesis makes test-first development more efficient.

The following broken quicksort was developed with the following tests:

    quicksort([]) # prove it exists
    assert quicksort([]) == []
    assert quicksort([1]) == [1]
    assert quicksort([2, 1]) == [1, 2]
    assert quicksort([1, 2]) == [1, 2]
    assert quicksort([1, 2, 1]) == [1, 1, 2]
    assert quicksort([2, 3, 1]) == [1, 2, 3]

Hypothesis finds the counterexample [0, 2, 1]:

    $ pytest-3 ./testsort.py
    (...)
    seq = [0, 2, 1]

        @given(lists(integers()))
        def test_quicksort(seq):
            results = quicksort(seq[:])
            # results should be a permutation of the input
            assert Counter(seq) == Counter(results)
            # results should be sorted
            for i, ri in enumerate(results[1:]):
    >           assert ri >= results[i]
    E           assert 1 >= 2

    testsort.py:25: AssertionError

"""

from collections import Counter
from hypothesis import given
from hypothesis.strategies import lists, integers


def quicksort(l):
    # Incorrect!  Example due to jcowan.
    if not l:
        return []
    out = [l[0]]
    for i in l[1:]:
        if i <= out[0]:
            out = [i] + out
        else:
            out.append(i)
    return out

# Just to verify that the test works, here’s a correct
# quasi-quicksort.  It’s not in-place, though, and has no recursion
# limit.
def ok_quicksort(l):
    if len(l) < 2:
        return l

    pivot = l[0]
    pre = [x for x in l[1:] if x < pivot]
    post = [x for x in l[1:] if x >= pivot]
    return ok_quicksort(pre) + [pivot] + ok_quicksort(post)

@given(lists(integers()))
def test_quicksort(seq):
    results = quicksort(seq[:])
    # results should be a permutation of the input
    assert Counter(seq) == Counter(results)
    # results should be sorted
    for i, ri in enumerate(results[1:]):
        assert ri >= results[i]