# Copyright (c) 2007 RADLogic
#
# 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, 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
# AUTHORS OR 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.
"""Provide various handy Python functions.

Running this script directly will execute the doctests.

Functions:
int2bin(i, n) -- Convert integer to binary string.
bin2int(bin_string) -- Convert binary string to integer.
reverse(input_string) -- Reverse a string.
transpose(matrix) -- Transpose a list of lists.
polygon_area(points_list) -- Calculate the area of an arbitrary polygon.
timestamp() -- Return string containing current time stamp.
pt2str(point) -- Return prettier string version of point tuple.
gcf(a, b) -- Return the greatest common factor of two numbers.
lcm(a, b) -- Return the least common multiple of two numbers.
permutations(input_list) -- Generate all permutations of a list of items.
reduce_fraction(fraction) -- Reduce fraction (num, denom) to simplest form.
quantile(l, p) -- Return p quantile of list l. E.g. p=0.25 for q1.
trim(l) -- Discard values in list more than 1.5*IQR outside IQR.
nice_units(value) -- Return value converted to human readable units.
uniquify(seq) -- Return sequence with duplicate items in sequence seq removed.
reverse_dict(d) -- Return the dictionary with the items as keys and vice-versa.
lsb(x, n) -- Return the n least significant bits of x.
gray_encode(i) -- Gray encode the given integer.
random_vec(bits, max_value=None) -- Return a random binary vector.
binary_range(bits) -- Return list of all possible binary numbers width=bits.
float_range([start], stop, [step]) -- Return range of floats.
find_common_fixes(s1, s2) -- Find common (prefix, suffix) of two strings.
is_rotated(seq1, seq2) -- Return true if the list is a rotation of other list.
getmodule(obj) -- Return the module that contains the object definition of obj.
                  (use inspect.getmodule instead, though)
get_args(argv) -- Store command-line args in a dictionary.

This module requires Python >= 2.2

"""
__author__ = 'Tim Wegener <twegener@radlogic.com.au>'
__date__ = '$Date: 2007/03/27 03:15:06 $'
__version__ = '$Revision: 0.45 $'
__credits__ = """
              David Chandler, for polygon area algorithm.
               (http://www.davidchandler.com/AreaOfAGeneralPolygon.pdf)
              """

import re
import sys
import time
import random

try:
    True, False
except NameError:
    True, False = (1==1, 0==1)


def int2bin(i, n):
    """Convert decimal integer i to n-bit binary number (string).

    >>> int2bin(0, 8)
    '00000000'

    >>> int2bin(123, 8)
    '01111011'

    >>> int2bin(123L, 8)
    '01111011'

    >>> int2bin(15, 2)
    Traceback (most recent call last):
    ValueError: Value too large for given number of bits.

    """
    hex2bin = {'0': '0000', '1': '0001', '2': '0010', '3': '0011',
               '4': '0100', '5': '0101', '6': '0110', '7': '0111',
               '8': '1000', '9': '1001', 'a': '1010', 'b': '1011',
               'c': '1100', 'd': '1101', 'e': '1110', 'f': '1111'}
    # Convert to hex then map each hex digit to binary equivalent.
    result = ''.join([hex2bin[x] for x in hex(i).lower().replace('l','')[2:]])

    # Shrink result to appropriate length.
    # Raise an error if the value is changed by the truncation.
    if '1' in result[:-n]:
        raise ValueError("Value too large for given number of bits.")
    result = result[-n:]
    # Zero-pad if length longer than mapped result.
    result = '0'*(n-len(result)) + result
    return result


def bin2int(bin_string):
    """Convert binary number string to decimal integer.

    Note: Python > v2 has int(bin_string, 2)

    >>> bin2int('1111')
    15

    >>> bin2int('0101')
    5

    """
    ##     result = 0
    ##     bin_list = list(bin_string)
    ##     if len(filter(lambda x: x in ('1','0'), bin_list)) < len(bin_list):
    ##         raise Exception ("bin2int: Error - not a binary number: %s"
    ##                          % bin_string)
    ##     bit_list = map(int, bin_list)
    ##     bit_list.reverse()  # Make most significant bit have highest index.
    ##     for bit_place in range(len(bit_list)):
    ##         result = result + ((2**bit_place) * bit_list[bit_place])
    ##     return result
    return int(bin_string, 2)


def reverse(input_string):
    """Reverse a string. Useful for strings of binary numbers.

    >>> reverse('abc')
    'cba'

    """
    str_list = list(input_string)
    str_list.reverse()
    return ''.join(str_list)


def transpose(matrix):
    """Transpose a list of lists.

    >>> transpose([['a', 'b', 'c'], ['d', 'e', 'f'], ['g', 'h', 'i']])
    [['a', 'd', 'g'], ['b', 'e', 'h'], ['c', 'f', 'i']]

    >>> transpose([['a', 'b', 'c'], ['d', 'e', 'f']])
    [['a', 'd'], ['b', 'e'], ['c', 'f']]

    >>> transpose([['a', 'b'], ['d', 'e'], ['g', 'h']])
    [['a', 'd', 'g'], ['b', 'e', 'h']]

    """
    result = zip(*matrix)
    # Convert list of tuples to list of lists.
    # map is faster than a list comprehension since it is being used with
    # a built-in function as an argument.
    result = map(list, result)
    return result


def polygon_area(points_list, precision=100):
    """Calculate area of an arbitrary polygon using an algorithm from the web.

    Return the area of the polygon as a positive float.

    Arguments:

    points_list -- list of point tuples [(x0, y0), (x1, y1), (x2, y2), ...]
                   (Unclosed polygons will be closed automatically.
    preci
sion -- Internal arithmetic precision (integer arithmetic).

    >>> polygon_area([(0, 0), (0, 1), (1, 1), (1, 2), (2, 2), (2, 0), (0, 0)])
    3.0

    Credits:
    Area of a General Polygon by David Chandler
    http://www.davidchandler.com/AreaOfAGeneralPolygon.pdf

    """
    # Scale up co-ordinates and convert them to integers.
    for i in range(len(points_list)):
        points_list[i] = (int(points_list[i][0] * precision),
                          int(points_list[i][1] * precision))
        # Close polygon if not closed.
    if points_list[-1] != points_list[0]:
        points_list.append(points_list[0])
        # Calculate area.
    area = 0
    for i in range(len(points_list)-1):
        (x_i, y_i) = points_list[i]
        (x_i_plus_1, y_i_plus_1) = points_list[i+1]
        area = area + (x_i_plus_1 * y_i) - (y_i_plus_1 * x_i)
    area = abs(area / 2)
    # Unscale area.
    area = float(area)/(precision**2)
    return area


def timestamp():
    """Return string containing current time stamp.

    Note: In Python 2 onwards can use time.asctime() with no arguments.

    """

    return time.asctime()


def pt2str(point):
    """Return prettier string version of point tuple.

    >>> pt2str((1.8, 1.9))
    '(1.8, 1.9)'

    """
    return "(%s, %s)" % (str(point[0]), str(point[1]))


def gcf(a, b, epsilon=1e-16):
    """Return the greatest common factor of a and b, using Euclidean algorithm.

    Arguments:
    a, b -- two numbers
            If both numbers are integers return an integer result,
            otherwise 