# select.py
# Copyright (C) 2006, 2007 Martin Jansche
#
# Permission is hereby granted, free of charge, to any person obtaining
# a copy of this software and associated documentation files (the
# "Software"), to deal in the Software without restriction, including
# without limitation the rights to use, copy, modify, merge, publish,
# distribute, distribute with modifications, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the Software is
# furnished to do so, subject to the following conditions:
#
# The above copyright notice and this permission notice shall be
# included in all copies or substantial portions of the Software.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
# IN NO EVENT SHALL THE ABOVE COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
# DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
# OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR
# THE USE OR OTHER DEALINGS IN THE SOFTWARE.
#
# Except as contained in this notice, the name(s) of the above copyright
# holders shall not be used in advertising or otherwise to promote the
# sale, use or other dealings in this Software without prior written
# authorization.

"""
Fast (expected linear time) selection, based on Section 3.7 of "The
Design and Analysis of Computer Algorithms" by Aho, Hopcroft and
Ullman.  Also contains a simple implementation of quicksort, which is
based on the same idea.
"""

import random as _random

_rng = _random.Random()

def select(k, S, comparator=cmp):
    """Select the k-th smallest element from S.  Let x be the k-th
    smallest element of S.  Then this function returns x and
    furthermore rearranges the elements of S in such a way that
    S[k] == x; for all y in S[:k], y <= x; and for all z in S[k+1:],
    x <= z."""
    assert 0 <= k and k < len(S)
    return _randSelect(S, comparator, 0, len(S)-1, k)

def _randSelect(A, comparator, p, r, i):
    assert 0 <= p and p < len(A)
    assert p <= r and r < len(A)
    assert 0 <= i and i < len(A)
    if p == r:
        return A[p]
    q = _randPartition(A, comparator, p, r)
    k = q - p
    if i == k:
        return A[q]
    elif i < k:
        return _randSelect(A, comparator, p, q-1, i)
    else:
        assert i > k
        return _randSelect(A, comparator, q+1, r, i-k-1)

def _swap(A, i, j):
    if i == j:
        return
    assert 0 <= i and i < len(A)
    assert 0 <= j and j < len(A)
    tmp = A[i]
    A[i] = A[j]
    A[j] = tmp
    return

def _randPartition(A, comparator, p, r):
    assert 0 <= p and p < len(A)
    assert p <= r and r < len(A)
    i = p + _rng.randint(0, r - p)
    assert p <= i and i <= r
    _swap(A, r, i)
    return _partition(A, comparator, p, r)

def _partition(A, comparator, p, r):
    assert 0 <= p and p < len(A)
    assert p <= r and r < len(A)
    x = A[r]
    i = p - 1
    for j in xrange(p, r):
        if comparator(A[j], x) <= 0:
            i += 1
            _swap(A, i, j)
    i += 1
    assert p <= i and i <= r
    _swap(A, i, r)
    return i

def quicksort(A, comparator=cmp):
    """Sort the array (or array-like object) A in place."""
    _quicksort(A, comparator, 0, len(A)-1)
    return

def _quicksort(A, comparator, p, r):
    if p >= r:
        return
    assert 0 <= p and p < len(A)
    assert 0 <= r and r < len(A)
    q = _randPartition(A, comparator, p, r)
    _quicksort(A, comparator, p, q-1)
    _quicksort(A, comparator, q+1, r)
    return

# eof