gjc@3408: # Copyright (c) 2007 RADLogic
gjc@3408: # 
gjc@3408: # Permission is hereby granted, free of charge, to any person obtaining a copy
gjc@3408: # of this software and associated documentation files (the "Software"), to deal
gjc@3408: # in the Software without restriction, including without limitation the rights
gjc@3408: # to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
gjc@3408: # copies of the Software, and to permit persons to whom the Software is
gjc@3408: # furnished to do so, subject to the following conditions:
gjc@3408: # 
gjc@3408: # The above copyright notice and this permission notice shall be included in
gjc@3408: # all copies or substantial portions of the Software.
gjc@3408: # 
gjc@3408: # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
gjc@3408: # IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
gjc@3408: # FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
gjc@3408: # AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
gjc@3408: # LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
gjc@3408: # OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
gjc@3408: # THE SOFTWARE.
gjc@3408: """Provide various handy Python functions.
gjc@3408: 
gjc@3408: Running this script directly will execute the doctests.
gjc@3408: 
gjc@3408: Functions:
gjc@3408: int2bin(i, n) -- Convert integer to binary string.
gjc@3408: bin2int(bin_string) -- Convert binary string to integer.
gjc@3408: reverse(input_string) -- Reverse a string.
gjc@3408: transpose(matrix) -- Transpose a list of lists.
gjc@3408: polygon_area(points_list) -- Calculate the area of an arbitrary polygon.
gjc@3408: timestamp() -- Return string containing current time stamp.
gjc@3408: pt2str(point) -- Return prettier string version of point tuple.
gjc@3408: gcf(a, b) -- Return the greatest common factor of two numbers.
gjc@3408: lcm(a, b) -- Return the least common multiple of two numbers.
gjc@3408: permutations(input_list) -- Generate all permutations of a list of items.
gjc@3408: reduce_fraction(fraction) -- Reduce fraction (num, denom) to simplest form.
gjc@3408: quantile(l, p) -- Return p quantile of list l. E.g. p=0.25 for q1.
gjc@3408: trim(l) -- Discard values in list more than 1.5*IQR outside IQR.
gjc@3408: nice_units(value) -- Return value converted to human readable units.
gjc@3408: uniquify(seq) -- Return sequence with duplicate items in sequence seq removed.
gjc@3408: reverse_dict(d) -- Return the dictionary with the items as keys and vice-versa.
gjc@3408: lsb(x, n) -- Return the n least significant bits of x.
gjc@3408: gray_encode(i) -- Gray encode the given integer.
gjc@3408: random_vec(bits, max_value=None) -- Return a random binary vector.
gjc@3408: binary_range(bits) -- Return list of all possible binary numbers width=bits.
gjc@3408: float_range([start], stop, [step]) -- Return range of floats.
gjc@3408: find_common_fixes(s1, s2) -- Find common (prefix, suffix) of two strings.
gjc@3408: is_rotated(seq1, seq2) -- Return true if the list is a rotation of other list.
gjc@3408: getmodule(obj) -- Return the module that contains the object definition of obj.
gjc@3408:                   (use inspect.getmodule instead, though)
gjc@3408: get_args(argv) -- Store command-line args in a dictionary.
gjc@3408: 
gjc@3408: This module requires Python >= 2.2
gjc@3408: 
gjc@3408: """
gjc@3408: __author__ = 'Tim Wegener <twegener@radlogic.com.au>'
gjc@3408: __date__ = '$Date: 2007/03/27 03:15:06 $'
gjc@3408: __version__ = '$Revision: 0.45 $'
gjc@3408: __credits__ = """
gjc@3408:               David Chandler, for polygon area algorithm.
gjc@3408:                (http://www.davidchandler.com/AreaOfAGeneralPolygon.pdf)
gjc@3408:               """
gjc@3408: 
gjc@3408: import re
gjc@3408: import sys
gjc@3408: import time
gjc@3408: import random
gjc@3408: 
gjc@3408: try:
gjc@3408:     True, False
gjc@3408: except NameError:
gjc@3408:     True, False = (1==1, 0==1)
gjc@3408: 
gjc@3408: 
gjc@3408: def int2bin(i, n):
gjc@3408:     """Convert decimal integer i to n-bit binary number (string).
gjc@3408: 
gjc@3408:     >>> int2bin(0, 8)
gjc@3408:     '00000000'
gjc@3408: 
gjc@3408:     >>> int2bin(123, 8)
gjc@3408:     '01111011'
gjc@3408: 
gjc@3408:     >>> int2bin(123L, 8)
gjc@3408:     '01111011'
gjc@3408: 
gjc@3408:     >>> int2bin(15, 2)
gjc@3408:     Traceback (most recent call last):
gjc@3408:     ValueError: Value too large for given number of bits.
gjc@3408: 
gjc@3408:     """
gjc@3408:     hex2bin = {'0': '0000', '1': '0001', '2': '0010', '3': '0011',
gjc@3408:                '4': '0100', '5': '0101', '6': '0110', '7': '0111',
gjc@3408:                '8': '1000', '9': '1001', 'a': '1010', 'b': '1011',
gjc@3408:                'c': '1100', 'd': '1101', 'e': '1110', 'f': '1111'}
gjc@3408:     # Convert to hex then map each hex digit to binary equivalent.
gjc@3408:     result = ''.join([hex2bin[x] for x in hex(i).lower().replace('l','')[2:]])
gjc@3408:                       
gjc@3408:     # Shrink result to appropriate length.
gjc@3408:     # Raise an error if the value is changed by the truncation.
gjc@3408:     if '1' in result[:-n]:
gjc@3408:         raise ValueError("Value too large for given number of bits.")
gjc@3408:     result = result[-n:]
gjc@3408:     # Zero-pad if length longer than mapped result.
gjc@3408:     result = '0'*(n-len(result)) + result
gjc@3408:     return result
gjc@3408: 
gjc@3408: 
gjc@3408: def bin2int(bin_string):
gjc@3408:     """Convert binary number string to decimal integer.
gjc@3408:     
gjc@3408:     Note: Python > v2 has int(bin_string, 2)
gjc@3408: 
gjc@3408:     >>> bin2int('1111')
gjc@3408:     15
gjc@3408: 
gjc@3408:     >>> bin2int('0101')
gjc@3408:     5
gjc@3408: 
gjc@3408:     """
gjc@3408: ##     result = 0
gjc@3408: ##     bin_list = list(bin_string)
gjc@3408: ##     if len(filter(lambda x: x in ('1','0'), bin_list)) < len(bin_list):
gjc@3408: ##         raise Exception ("bin2int: Error - not a binary number: %s"
gjc@3408: ##                          % bin_string)
gjc@3408: ##     bit_list = map(int, bin_list)
gjc@3408: ##     bit_list.reverse()  # Make most significant bit have highest index.
gjc@3408: ##     for bit_place in range(len(bit_list)):
gjc@3408: ##         result = result + ((2**bit_place) * bit_list[bit_place])
gjc@3408: ##     return result
gjc@3408:     return int(bin_string, 2)
gjc@3408: 
gjc@3408: 
gjc@3408: def reverse(input_string):
gjc@3408:     """Reverse a string. Useful for strings of binary numbers.
gjc@3408: 
gjc@3408:     >>> reverse('abc')
gjc@3408:     'cba'
gjc@3408: 
gjc@3408:     """
gjc@3408:     str_list = list(input_string)
gjc@3408:     str_list.reverse()
gjc@3408:     return ''.join(str_list)
gjc@3408: 
gjc@3408: 
gjc@3408: def transpose(matrix):
gjc@3408:     """Transpose a list of lists.
gjc@3408: 
gjc@3408:     >>> transpose([['a', 'b', 'c'], ['d', 'e', 'f'], ['g', 'h', 'i']])
gjc@3408:     [['a', 'd', 'g'], ['b', 'e', 'h'], ['c', 'f', 'i']]
gjc@3408: 
gjc@3408:     >>> transpose([['a', 'b', 'c'], ['d', 'e', 'f']])
gjc@3408:     [['a', 'd'], ['b', 'e'], ['c', 'f']]
gjc@3408: 
gjc@3408:     >>> transpose([['a', 'b'], ['d', 'e'], ['g', 'h']])
gjc@3408:     [['a', 'd', 'g'], ['b', 'e', 'h']]
gjc@3408: 
gjc@3408:     """
gjc@3408:     result = zip(*matrix)
gjc@3408:     # Convert list of tuples to list of lists.
gjc@3408:     # map is faster than a list comprehension since it is being used with
gjc@3408:     # a built-in function as an argument.
gjc@3408:     result = map(list, result)
gjc@3408:     return result
gjc@3408: 
gjc@3408: 
gjc@3408: def polygon_area(points_list, precision=100):
gjc@3408:     """Calculate area of an arbitrary polygon using an algorithm from the web.
gjc@3408: 
gjc@3408:     Return the area of the polygon as a positive float. 
gjc@3408: 
gjc@3408:     Arguments:
gjc@3408:     points_list -- list of point tuples [(x0, y0), (x1, y1), (x2, y2), ...]
gjc@3408:                    (Unclosed polygons will be closed automatically.
gjc@3408:     precision -- Internal arithmetic precision (integer arithmetic).
gjc@3408: 
gjc@3408:     >>> polygon_area([(0, 0), (0, 1), (1, 1), (1, 2), (2, 2), (2, 0), (0, 0)])
gjc@3408:     3.0
gjc@3408: 
gjc@3408:     Credits:
gjc@3408:     Area of a General Polygon by David Chandler
gjc@3408:     http://www.davidchandler.com/AreaOfAGeneralPolygon.pdf
gjc@3408:     
gjc@3408:     """
gjc@3408:     # Scale up co-ordinates and convert them to integers.
gjc@3408:     for i in range(len(points_list)):
gjc@3408:         points_list[i] = (int(points_list[i][0] * precision),
gjc@3408:                           int(points_list[i][1] * precision))
gjc@3408:     # Close polygon if not closed.
gjc@3408:     if points_list[-1] != points_list[0]:
gjc@3408:         points_list.append(points_list[0])
gjc@3408:     # Calculate area.
gjc@3408:     area = 0
gjc@3408:     for i in range(len(points_list)-1):
gjc@3408:         (x_i, y_i) = points_list[i]
gjc@3408:         (x_i_plus_1, y_i_plus_1) = points_list[i+1]
gjc@3408:         area = area + (x_i_plus_1 * y_i) - (y_i_plus_1 * x_i)
gjc@3408:     area = abs(area / 2)
gjc@3408:     # Unscale area.
gjc@3408:     area = float(area)/(precision**2)
gjc@3408:     return area
gjc@3408: 
gjc@3408: 
gjc@3408: def timestamp():
gjc@3408:     """Return string containing current time stamp.
gjc@3408: 
gjc@3408:     Note: In Python 2 onwards can use time.asctime() with no arguments.
gjc@3408: 
gjc@3408:     """
gjc@3408: 
gjc@3408:     return time.asctime()
gjc@3408: 
gjc@3408: 
gjc@3408: def pt2str(point):
gjc@3408:     """Return prettier string version of point tuple.
gjc@3408: 
gjc@3408:     >>> pt2str((1.8, 1.9))
gjc@3408:     '(1.8, 1.9)'
gjc@3408: 
gjc@3408:     """
gjc@3408:     return "(%s, %s)" % (str(point[0]), str(point[1]))
gjc@3408: 
gjc@3408: 
gjc@3408: def gcf(a, b, epsilon=1e-16):
gjc@3408:     """Return the greatest common factor of a and b, using Euclidean algorithm.
gjc@3408: 
gjc@3408:     Arguments:
gjc@3408:     a, b -- two numbers
gjc@3408:             If both numbers are integers return an integer result, 
gjc@3408:             otherwise return a float result.
gjc@3408:     epsilon -- floats less than this magnitude are considered to be zero
gjc@3408:                (default: 1e-16)
gjc@3408: 
gjc@3408:     Examples:
gjc@3408: 
gjc@3408:     >>> gcf(12, 34)
gjc@3408:     2
gjc@3408: 
gjc@3408:     >>> gcf(13.5, 4)
gjc@3408:     0.5
gjc@3408: 
gjc@3408:     >>> gcf(-2, 4)
gjc@3408:     2
gjc@3408: 
gjc@3408:     >>> gcf(5, 0)
gjc@3408:     5
gjc@3408: 
gjc@3408:     By (a convenient) definition:
gjc@3408:     >>> gcf(0, 0)
gjc@3408:     0
gjc@3408: 
gjc@3408:     """
gjc@3408:     result = max(a, b)
gjc@3408:     remainder = min(a, b)
gjc@3408:     while remainder and abs(remainder) > epsilon:
gjc@3408:         new_remainder = result % remainder
gjc@3408:         result = remainder
gjc@3408:         remainder = new_remainder
gjc@3408:     return abs(result)
gjc@3408: 
gjc@3408: def lcm(a, b, precision=None):
gjc@3408:     """Return the least common multiple of a and b, using the gcf function.
gjc@3408: 
gjc@3408:     Arguments:
gjc@3408:     a, b -- two numbers. If both are integers return an integer result, 
gjc@3408:             otherwise a return a float result.
gjc@3408:     precision -- scaling factor if a and/or b are floats.
gjc@3408: 
gjc@3408:     >>> lcm(21, 6)
gjc@3408:     42
gjc@3408: 
gjc@3408:     >>> lcm(2.5, 3.5)
gjc@3408:     17.5
gjc@3408: 
gjc@3408:     >>> str(lcm(1.5e-8, 2.5e-8, precision=1e9))
gjc@3408:     '7.5e-08'
gjc@3408: 
gjc@3408:     By (an arbitary) definition:
gjc@3408:     >>> lcm(0, 0)
gjc@3408:     0
gjc@3408: 
gjc@3408:     """
gjc@3408:     # Note: Dummy precision argument is for backwards compatibility.
gjc@3408:     # Do the division first.
gjc@3408:     # (See http://en.wikipedia.org/wiki/Least_common_multiple )
gjc@3408:     denom = gcf(a, b)
gjc@3408:     if denom == 0:
gjc@3408:         result = 0
gjc@3408:     else:
gjc@3408:         result = a * (b / denom)
gjc@3408:     return result
gjc@3408: 
gjc@3408: 
gjc@3408: def permutations(input_list):
gjc@3408:     """Return a list containing all permutations of the input list.
gjc@3408: 
gjc@3408:     Note: This is a recursive function.
gjc@3408: 
gjc@3408:     >>> perms = permutations(['a', 'b', 'c'])
gjc@3408:     >>> perms.sort()
gjc@3408:     >>> for perm in perms:
gjc@3408:     ...     print perm
gjc@3408:     ['a', 'b', 'c']
gjc@3408:     ['a', 'c', 'b']
gjc@3408:     ['b', 'a', 'c']
gjc@3408:     ['b', 'c', 'a']
gjc@3408:     ['c', 'a', 'b']
gjc@3408:     ['c', 'b', 'a']
gjc@3408: 
gjc@3408:     """
gjc@3408:     out_lists = []
gjc@3408:     if len(input_list) > 1:
gjc@3408:         # Extract first item in list.
gjc@3408:         item = input_list[0]
gjc@3408:         # Find all permutations of remainder of list. (Recursive call.)
gjc@3408:         sub_lists = permutations(input_list[1:])
gjc@3408:         # For every permutation of the sub list...
gjc@3408:         for sub_list in sub_lists:
gjc@3408:             # Insert the extracted first item at every position of the list.
gjc@3408:             for i in range(len(input_list)):
gjc@3408:                 new_list = sub_list[:]
gjc@3408:                 new_list.insert(i, item)
gjc@3408:                 out_lists.append(new_list)
gjc@3408:     else:
gjc@3408:         # Termination condition: only one item in input list.
gjc@3408:         out_lists = [input_list]
gjc@3408:     return out_lists
gjc@3408: 
gjc@3408: 
gjc@3408: def reduce_fraction(fraction):
gjc@3408:     """Reduce fraction tuple to simplest form. fraction=(num, denom)
gjc@3408:     
gjc@3408:     >>> reduce_fraction((14, 7))
gjc@3408:     (2, 1)
gjc@3408: 
gjc@3408:     >>> reduce_fraction((-2, 4))
gjc@3408:     (-1, 2)
gjc@3408: 
gjc@3408:     >>> reduce_fraction((0, 4))
gjc@3408:     (0, 1)
gjc@3408: 
gjc@3408:     >>> reduce_fraction((4, 0))
gjc@3408:     (1, 0)
gjc@3408:     
gjc@3408:     """
gjc@3408:     (numerator, denominator) = fraction
gjc@3408:     common_factor = abs(gcf(numerator, denominator))
gjc@3408:     result = (numerator/common_factor, denominator/common_factor)
gjc@3408:     return result
gjc@3408: 
gjc@3408: 
gjc@3408: def quantile(l, p):
gjc@3408:     """Return p quantile of list l. E.g. p=0.25 for q1.
gjc@3408: 
gjc@3408:     See:
gjc@3408:     http://rweb.stat.umn.edu/R/library/base/html/quantile.html
gjc@3408: 
gjc@3408:     """
gjc@3408:     l_sort = l[:]
gjc@3408:     l_sort.sort()
gjc@3408:     n = len(l)
gjc@3408:     r = 1 + ((n - 1) * p)
gjc@3408:     i = int(r)
gjc@3408:     f = r - i
gjc@3408:     if i < n:
gjc@3408:         result =  (1-f)*l_sort[i-1] + f*l_sort[i]
gjc@3408:     else:
gjc@3408:         result = l_sort[i-1]
gjc@3408:     return result
gjc@3408: 
gjc@3408: 
gjc@3408: def trim(l):
gjc@3408:     """Discard values in list more than 1.5*IQR outside IQR.
gjc@3408: 
gjc@3408:     (IQR is inter-quartile-range)
gjc@3408: 
gjc@3408:     This function uses rad_util.quantile
gjc@3408: 
gjc@3408:     1.5*IQR -- mild outlier
gjc@3408:     3*IQR -- extreme outlier
gjc@3408: 
gjc@3408:     See:
gjc@3408:     http://wind.cc.whecn.edu/~pwildman/statnew/section_7_-_exploratory_data_analysis.htm
gjc@3408: 
gjc@3408:     """
gjc@3408:     l_sort = l[:]
gjc@3408:     l_sort.sort()
gjc@3408:     # Calculate medianscore  (based on stats.py lmedianscore by Gary Strangman)
gjc@3408:     if len(l_sort) % 2 == 0:
gjc@3408:         # If even number of scores, average middle 2.
gjc@3408:         index = int(len(l_sort) / 2)  # Integer division correct
gjc@3408:         median = float(l_sort[index] + l_sort[index-1]) / 2
gjc@3408:     else:
gjc@3408:         # int divsion gives mid value when count from 0
gjc@3408:         index = int(len(l_sort) / 2)
gjc@3408:         median = l_sort[index]
gjc@3408:     # Calculate IQR.
gjc@3408:     q1 = quantile(l_sort, 0.25)
gjc@3408:     q3 = quantile(l_sort, 0.75)
gjc@3408:     iqr = q3 - q1
gjc@3408:     iqr_extra = iqr * 1.5
gjc@3408:     def in_interval(x, i=iqr_extra, q1=q1, q3=q3):
gjc@3408:         return (x >= q1-i and x <= q3+i)
gjc@3408:     l_trimmed = [x for x in l_sort if in_interval(x)]
gjc@3408:     return l_trimmed
gjc@3408: 
gjc@3408: 
gjc@3408: def nice_units(value, dp=0, sigfigs=None, suffix='', space=' ',
gjc@3408:                use_extra_prefixes=False, use_full_name=False, mode='si'):
gjc@3408:     """Return value converted to human readable units eg milli, micro, etc.
gjc@3408: 
gjc@3408:     Arguments:
gjc@3408:     value -- number in base units
gjc@3408:     dp -- number of decimal places to display (rounded)
gjc@3408:     sigfigs -- number of significant figures to display (rounded)
gjc@3408:                This overrides dp if set.
gjc@3408:     suffix -- optional unit suffix to append to unit multiplier
gjc@3408:     space -- seperator between value and unit multiplier (default: ' ')
gjc@3408:     use_extra_prefixes -- use hecto, deka, deci and centi as well if set.
gjc@3408:                           (default: False)
gjc@3408:     use_full_name -- use full name for multiplier symbol,
gjc@3408:                      e.g. milli instead of m
gjc@3408:                      (default: False)
gjc@3408:     mode -- 'si' for SI prefixes, 'bin' for binary multipliers (1024, etc.)
gjc@3408:             (Default: 'si')
gjc@3408: 
gjc@3408:     SI prefixes from:
gjc@3408:     http://physics.nist.gov/cuu/Units/prefixes.html
gjc@3408:     (Greek mu changed to u.)
gjc@3408:     Binary prefixes based on:
gjc@3408:     http://physics.nist.gov/cuu/Units/binary.html
gjc@3408: 
gjc@3408:     >>> nice_units(2e-11)
gjc@3408:     '20 p'
gjc@3408: 
gjc@3408:     >>> nice_units(2e-11, space='')
gjc@3408:     '20p'
gjc@3408: 
gjc@3408:     """
gjc@3408:     si_prefixes = {1e24:  ('Y', 'yotta'),
gjc@3408:                    1e21:  ('Z', 'zetta'),
gjc@3408:                    1e18:  ('E', 'exa'),
gjc@3408:                    1e15:  ('P', 'peta'),
gjc@3408:                    1e12:  ('T', 'tera'),
gjc@3408:                    1e9:   ('G', 'giga'),
gjc@3408:                    1e6:   ('M', 'mega'),
gjc@3408:                    1e3:   ('k', 'kilo'),
gjc@3408:                    1e-3:  ('m', 'milli'),
gjc@3408:                    1e-6:  ('u', 'micro'),
gjc@3408:                    1e-9:  ('n', 'nano'),
gjc@3408:                    1e-12: ('p', 'pico'),
gjc@3408:                    1e-15: ('f', 'femto'),
gjc@3408:                    1e-18: ('a', 'atto'),
gjc@3408:                    1e-21: ('z', 'zepto'),
gjc@3408:                    1e-24: ('y', 'yocto')
gjc@3408:                    }
gjc@3408:     if use_extra_prefixes:
gjc@3408:         si_prefixes.update({1e2:  ('h', 'hecto'),
gjc@3408:                             1e1:  ('da', 'deka'),
gjc@3408:                             1e-1: ('d', 'deci'),
gjc@3408:                             1e-2: ('c', 'centi')
gjc@3408:                             })
gjc@3408:     bin_prefixes = {2**10: ('K', 'kilo'),
gjc@3408:                     2**20: ('M', 'mega'),
gjc@3408:                     2**30: ('G', 'mega'),
gjc@3408:                     2**40: ('T', 'tera'),
gjc@3408:                     2**50: ('P', 'peta'),
gjc@3408:                     2**60: ('E', 'exa')
gjc@3408:                     }
gjc@3408:     if mode == 'bin':
gjc@3408:         prefixes = bin_prefixes
gjc@3408:     else:
gjc@3408:         prefixes = si_prefixes
gjc@3408:     prefixes[1] = ('', '')  # Unity.
gjc@3408:     # Determine appropriate multiplier.
gjc@3408:     multipliers = prefixes.keys()
gjc@3408:     multipliers.sort()
gjc@3408:     mult = None
gjc@3408:     for i in range(len(multipliers) - 1):
gjc@3408:         lower_mult = multipliers[i]
gjc@3408:         upper_mult = multipliers[i+1]
gjc@3408:         if lower_mult <= value < upper_mult:
gjc@3408:             mult_i = i
gjc@3408:             break
gjc@3408:     if mult is None:
gjc@3408:         if value < multipliers[0]:
gjc@3408:             mult_i = 0
gjc@3408:         elif value >= multipliers[-1]:
gjc@3408:             mult_i = len(multipliers) - 1
gjc@3408:     mult = multipliers[mult_i]
gjc@3408:     # Convert value for this multiplier.
gjc@3408:     new_value = value / mult
gjc@3408:     # Deal with special case due to rounding.
gjc@3408:     if sigfigs is None:
gjc@3408:         if mult_i < (len(multipliers) - 1) and \
gjc@3408:                round(new_value, dp) == \
gjc@3408:                round((multipliers[mult_i+1] / mult), dp):
gjc@3408:             mult = multipliers[mult_i + 1]
gjc@3408:             new_value = value / mult
gjc@3408:     # Concatenate multiplier symbol.
gjc@3408:     if use_full_name:
gjc@3408:         label_type = 1
gjc@3408:     else:
gjc@3408:         label_type = 0
gjc@3408:     # Round and truncate to appropriate precision.
gjc@3408:     if sigfigs is None:
gjc@3408:         str_value = eval('"%.'+str(dp)+'f" % new_value', locals(), {})
gjc@3408:     else:
gjc@3408:         str_value = eval('"%.'+str(sigfigs)+'g" % new_value', locals(), {})
gjc@3408:     return str_value + space + prefixes[mult][label_type] + suffix
gjc@3408: 
gjc@3408: 
gjc@3408: def uniquify(seq, preserve_order=False):
gjc@3408:     """Return sequence with duplicate items in sequence seq removed.
gjc@3408: 
gjc@3408:     The code is based on usenet post by Tim Peters.
gjc@3408: 
gjc@3408:     This code is O(N) if the sequence items are hashable, O(N**2) if not.
gjc@3408:     
gjc@3408:     Peter Bengtsson has a blog post with an empirical comparison of other
gjc@3408:     approaches:
gjc@3408:     http://www.peterbe.com/plog/uniqifiers-benchmark
gjc@3408: 
gjc@3408:     If order is not important and the sequence items are hashable then
gjc@3408:     list(set(seq)) is readable and efficient.
gjc@3408: 
gjc@3408:     If order is important and the sequence items are hashable generator
gjc@3408:     expressions can be used (in py >= 2.4) (useful for large sequences):
gjc@3408:     seen = set()
gjc@3408:     do_something(x for x in seq if x not in seen or seen.add(x))
gjc@3408: 
gjc@3408:     Arguments:
gjc@3408:     seq -- sequence
gjc@3408:     preserve_order -- if not set the order will be arbitrary
gjc@3408:                       Using this option will incur a speed penalty.
gjc@3408:                       (default: False)
gjc@3408: 
gjc@3408:     Example showing order preservation:
gjc@3408: 
gjc@3408:     >>> uniquify(['a', 'aa', 'b', 'b', 'ccc', 'ccc', 'd'], preserve_order=True)
gjc@3408:     ['a', 'aa', 'b', 'ccc', 'd']
gjc@3408: 
gjc@3408:     Example using a sequence of un-hashable items:
gjc@3408: 
gjc@3408:     >>> uniquify([['z'], ['x'], ['y'], ['z']], preserve_order=True)
gjc@3408:     [['z'], ['x'], ['y']]
gjc@3408: 
gjc@3408:     The sorted output or the non-order-preserving approach should equal
gjc@3408:     that of the sorted order-preserving approach output:
gjc@3408:     
gjc@3408:     >>> unordered = uniquify([3, 3, 1, 2], preserve_order=False)
gjc@3408:     >>> unordered.sort()
gjc@3408:     >>> ordered = uniquify([3, 3, 1, 2], preserve_order=True)
gjc@3408:     >>> ordered.sort()
gjc@3408:     >>> ordered
gjc@3408:     [1, 2, 3]
gjc@3408:     >>> int(ordered == unordered)
gjc@3408:     1
gjc@3408: 
gjc@3408:     """
gjc@3408:     try:
gjc@3408:         # Attempt fast algorithm.
gjc@3408:         d = {}
gjc@3408:         if preserve_order:
gjc@3408:             # This is based on Dave Kirby's method (f8) noted in the post:
gjc@3408:             # http://www.peterbe.com/plog/uniqifiers-benchmark
gjc@3408:             return [x for x in seq if (x not in d) and not d.__setitem__(x, 0)]
gjc@3408:         else:
gjc@3408:             for x in seq:
gjc@3408:                 d[x] = 0
gjc@3408:             return d.keys()
gjc@3408:     except TypeError:
gjc@3408:         # Have an unhashable object, so use slow algorithm.
gjc@3408:         result = []
gjc@3408:         app = result.append
gjc@3408:         for x in seq:
gjc@3408:             if x not in result:
gjc@3408:                 app(x)
gjc@3408:         return result
gjc@3408: 
gjc@3408: # Alias to noun form for backward compatibility.
gjc@3408: unique = uniquify
gjc@3408: 
gjc@3408: 
gjc@3408: def reverse_dict(d):
gjc@3408:     """Reverse a dictionary so the items become the keys and vice-versa.
gjc@3408: 
gjc@3408:     Note: The results will be arbitrary if the items are not unique.
gjc@3408: 
gjc@3408:     >>> d = reverse_dict({'a': 1, 'b': 2})
gjc@3408:     >>> d_items = d.items()
gjc@3408:     >>> d_items.sort()
gjc@3408:     >>> d_items
gjc@3408:     [(1, 'a'), (2, 'b')]
gjc@3408: 
gjc@3408:     """
gjc@3408:     result = {}
gjc@3408:     for key, value in d.items():
gjc@3408:         result[value] = key
gjc@3408:     return result
gjc@3408: 
gjc@3408:     
gjc@3408: def lsb(x, n):
gjc@3408:     """Return the n least significant bits of x.
gjc@3408: 
gjc@3408:     >>> lsb(13, 3)
gjc@3408:     5
gjc@3408: 
gjc@3408:     """
gjc@3408:     return x & ((2 ** n) - 1)
gjc@3408: 
gjc@3408: 
gjc@3408: def gray_encode(i):
gjc@3408:     """Gray encode the given integer."""
gjc@3408: 
gjc@3408:     return i ^ (i >> 1)
gjc@3408: 
gjc@3408: 
gjc@3408: def random_vec(bits, max_value=None):
gjc@3408:     """Generate a random binary vector of length bits and given max value."""
gjc@3408: 
gjc@3408:     vector = ""
gjc@3408:     for _ in range(int(bits / 10) + 1):
gjc@3408:         i = int((2**10) * random.random())
gjc@3408:         vector += int2bin(i, 10)
gjc@3408: 
gjc@3408:     if max_value and (max_value < 2 ** bits - 1):
gjc@3408:         vector = int2bin((int(vector, 2) / (2 ** bits - 1)) * max_value, bits)
gjc@3408:     
gjc@3408:     return vector[0:bits]
gjc@3408: 
gjc@3408: 
gjc@3408: def binary_range(bits):
gjc@3408:     """Return a list of all possible binary numbers in order with width=bits. 
gjc@3408:     
gjc@3408:     It would be nice to extend it to match the
gjc@3408:     functionality of python's range() built-in function.
gjc@3408:     
gjc@3408:     """
gjc@3408:     l = []
gjc@3408:     v = ['0'] * bits
gjc@3408: 
gjc@3408:     toggle = [1] + [0] * bits
gjc@3408:     
gjc@3408:     while toggle[bits] != 1:
gjc@3408:         v_copy = v[:]
gjc@3408:         v_copy.reverse()
gjc@3408:         l.append(''.join(v_copy))
gjc@3408:         
gjc@3408:         toggle = [1] + [0]*bits
gjc@3408:         i = 0
gjc@3408:         while i < bits and toggle[i] == 1:
gjc@3408:             if toggle[i]:
gjc@3408:                 if v[i] == '0':
gjc@3408:                     v[i] = '1'
gjc@3408:                     toggle[i+1] = 0
gjc@3408:                 else:
gjc@3408:                     v[i] = '0'
gjc@3408:                     toggle[i+1] = 1
gjc@3408:             i += 1
gjc@3408:     return l
gjc@3408: 
gjc@3408: 
gjc@3408: def float_range(start, stop=None, step=None):
gjc@3408:     """Return a list containing an arithmetic progression of floats.
gjc@3408: 
gjc@3408:     Return a list of floats between 0.0 (or start) and stop with an
gjc@3408:     increment of step. 
gjc@3408: 
gjc@3408:     This is in functionality to python's range() built-in function 
gjc@3408:     but can accept float increments.
gjc@3408: 
gjc@3408:     As with range(), stop is omitted from the list.
gjc@3408: 
gjc@3408:     """
gjc@3408:     if stop is None:
gjc@3408:         stop = float(start)
gjc@3408:         start = 0.0
gjc@3408: 
gjc@3408:     if step is None:
gjc@3408:         step = 1.0
gjc@3408: 
gjc@3408:     cur = float(start)
gjc@3408:     l = []
gjc@3408:     while cur < stop:
gjc@3408:         l.append(cur)
gjc@3408:         cur += step
gjc@3408: 
gjc@3408:     return l
gjc@3408: 
gjc@3408: 
gjc@3408: def find_common_fixes(s1, s2):
gjc@3408:     """Find common (prefix, suffix) of two strings.
gjc@3408: 
gjc@3408:     >>> find_common_fixes('abc', 'def')
gjc@3408:     ('', '')
gjc@3408: 
gjc@3408:     >>> find_common_fixes('abcelephantdef', 'abccowdef')
gjc@3408:     ('abc', 'def')
gjc@3408: 
gjc@3408:     >>> find_common_fixes('abcelephantdef', 'abccow')
gjc@3408:     ('abc', '')
gjc@3408: 
gjc@3408:     >>> find_common_fixes('elephantdef', 'abccowdef')
gjc@3408:     ('', 'def')
gjc@3408: 
gjc@3408:     """
gjc@3408:     prefix = []
gjc@3408:     suffix = []
gjc@3408: 
gjc@3408:     i = 0
gjc@3408:     common_len = min(len(s1), len(s2))
gjc@3408:     while i < common_len:
gjc@3408:         if s1[i] != s2[i]:
gjc@3408:             break
gjc@3408: 
gjc@3408:         prefix.append(s1[i])
gjc@3408:         i += 1
gjc@3408: 
gjc@3408:     i = 1
gjc@3408:     while i < (common_len + 1):
gjc@3408:         if s1[-i] != s2[-i]:
gjc@3408:             break
gjc@3408:         
gjc@3408:         suffix.append(s1[-i])
gjc@3408:         i += 1
gjc@3408: 
gjc@3408:     suffix.reverse()
gjc@3408: 
gjc@3408:     prefix = ''.join(prefix)
gjc@3408:     suffix = ''.join(suffix)
gjc@3408:         
gjc@3408:     return (prefix, suffix)
gjc@3408: 
gjc@3408: 
gjc@3408: def is_rotated(seq1, seq2):
gjc@3408:     """Return true if the first sequence is a rotation of the second sequence.
gjc@3408: 
gjc@3408:     >>> seq1 = ['A', 'B', 'C', 'D']
gjc@3408:     >>> seq2 = ['C', 'D', 'A', 'B']
gjc@3408:     >>> int(is_rotated(seq1, seq2))
gjc@3408:     1
gjc@3408: 
gjc@3408:     >>> seq2 = ['C', 'D', 'B', 'A']
gjc@3408:     >>> int(is_rotated(seq1, seq2))
gjc@3408:     0
gjc@3408: 
gjc@3408:     >>> seq1 = ['A', 'B', 'C', 'A']
gjc@3408:     >>> seq2 = ['A', 'A', 'B', 'C']
gjc@3408:     >>> int(is_rotated(seq1, seq2))
gjc@3408:     1
gjc@3408: 
gjc@3408:     >>> seq2 = ['A', 'B', 'C', 'A']
gjc@3408:     >>> int(is_rotated(seq1, seq2))
gjc@3408:     1
gjc@3408: 
gjc@3408:     >>> seq2 = ['A', 'A', 'C', 'B']
gjc@3408:     >>> int(is_rotated(seq1, seq2))
gjc@3408:     0
gjc@3408: 
gjc@3408:     """
gjc@3408:     # Do a sanity check.
gjc@3408:     if len(seq1) != len(seq2):
gjc@3408:         return False
gjc@3408:     # Look for occurrences of second sequence head item in first sequence.
gjc@3408:     start_indexes = []
gjc@3408:     head_item = seq2[0]
gjc@3408:     for index1 in range(len(seq1)):
gjc@3408:         if seq1[index1] == head_item:
gjc@3408:             start_indexes.append(index1)
gjc@3408:     # Check that wrapped sequence matches.
gjc@3408:     double_seq1 = seq1 + seq1
gjc@3408:     for index1 in start_indexes:
gjc@3408:         if double_seq1[index1:index1+len(seq1)] == seq2:
gjc@3408:             return True
gjc@3408:     return False
gjc@3408: 
gjc@3408: def getmodule(obj):
gjc@3408:     """Return the module that contains the object definition of obj.
gjc@3408: 
gjc@3408:     Note: Use inspect.getmodule instead.
gjc@3408: 
gjc@3408:     Arguments:
gjc@3408:     obj -- python obj, generally a class or a function
gjc@3408: 
gjc@3408:     Examples:
gjc@3408:     
gjc@3408:     A function:
gjc@3408:     >>> module = getmodule(random.choice)
gjc@3408:     >>> module.__name__
gjc@3408:     'random'
gjc@3408:     >>> module is random
gjc@3408:     1
gjc@3408: 
gjc@3408:     A class:
gjc@3408:     >>> module = getmodule(random.Random)
gjc@3408:     >>> module.__name__
gjc@3408:     'random'
gjc@3408:     >>> module is random
gjc@3408:     1
gjc@3408: 
gjc@3408:     A class inheriting from a class in another module:
gjc@3408:     (note: The inheriting class must define at least one function.)
gjc@3408:     >>> class MyRandom(random.Random):
gjc@3408:     ...     def play(self):
gjc@3408:     ...         pass
gjc@3408:     >>> module = getmodule(MyRandom)
gjc@3408:     >>> if __name__ == '__main__':
gjc@3408:     ...     name = 'rad_util'
gjc@3408:     ... else:
gjc@3408:     ...     name = module.__name__
gjc@3408:     >>> name
gjc@3408:     'rad_util'
gjc@3408:     >>> module is sys.modules[__name__]
gjc@3408:     1
gjc@3408: 
gjc@3408:     Discussion:
gjc@3408:     This approach is slightly hackish, and won't work in various situations.
gjc@3408:     However, this was the approach recommended by GvR, so it's as good as
gjc@3408:     you'll get.
gjc@3408: 
gjc@3408:     See GvR's post in this thread:
gjc@3408:     http://groups.google.com.au/group/comp.lang.python/browse_thread/thread/966a7bdee07e3b34/c3cab3f41ea84236?lnk=st&q=python+determine+class+module&rnum=4&hl=en#c3cab3f41ea84236
gjc@3408:     
gjc@3408:     """
gjc@3408:     if hasattr(obj, 'func_globals'):
gjc@3408:         func = obj
gjc@3408:     else:
gjc@3408:         # Handle classes.
gjc@3408:         func = None
gjc@3408:         for item in obj.__dict__.values():
gjc@3408:             if hasattr(item, 'func_globals'):
gjc@3408:                 func = item
gjc@3408:                 break
gjc@3408:         if func is None:
gjc@3408:             raise ValueError("No functions attached to object: %r" % obj)
gjc@3408:     module_name = func.func_globals['__name__']
gjc@3408:     # Get module.
gjc@3408:     module = sys.modules[module_name]
gjc@3408:     return module
gjc@3408: 
gjc@3408: 
gjc@3408: def round_grid(value, grid, mode=0):
gjc@3408:     """Round off the given value to the given grid size.
gjc@3408: 
gjc@3408:     Arguments:
gjc@3408:     value -- value to be roudne
gjc@3408:     grid -- result must be a multiple of this
gjc@3408:     mode -- 0 nearest, 1 up, -1 down
gjc@3408: 
gjc@3408:     Examples:
gjc@3408:     
gjc@3408:     >>> round_grid(7.5, 5)
gjc@3408:     10
gjc@3408: 
gjc@3408:     >>> round_grid(7.5, 5, mode=-1)
gjc@3408:     5
gjc@3408: 
gjc@3408:     >>> round_grid(7.3, 5, mode=1)
gjc@3408:     10
gjc@3408: 
gjc@3408:     >>> round_grid(7.3, 5.0, mode=1)
gjc@3408:     10.0
gjc@3408: 
gjc@3408:     """
gjc@3408:     off_grid = value % grid
gjc@3408:     if mode == 0:
gjc@3408:         add_one = int(off_grid >= (grid / 2.0))
gjc@3408:     elif mode == 1 and off_grid:
gjc@3408:         add_one = 1
gjc@3408:     elif mode == -1 and off_grid:
gjc@3408:         add_one = 0
gjc@3408:     result = ((int(value / grid) + add_one) * grid)
gjc@3408:     return result
gjc@3408: 
gjc@3408: 
gjc@3408: def get_args(argv):
gjc@3408:     """Store command-line args in a dictionary.
gjc@3408:     
gjc@3408:     -, -- prefixes are removed
gjc@3408:     Items not prefixed with - or -- are stored as a list, indexed by 'args'
gjc@3408: 
gjc@3408:     For options that take a value use --option=value
gjc@3408: 
gjc@3408:     Consider using optparse or getopt (in Python standard library) instead.
gjc@3408: 
gjc@3408:     """
gjc@3408:     d = {}
gjc@3408:     args = []
gjc@3408:     
gjc@3408:     for arg in argv:
gjc@3408:             
gjc@3408:         if arg.startswith('-'):
gjc@3408:             parts = re.sub(r'^-+', '', arg).split('=')
gjc@3408:             if len(parts) == 2:
gjc@3408:                 d[parts[0]] = parts[1]
gjc@3408:             else:
gjc@3408:                 d[parts[0]] = None
gjc@3408:         else:
gjc@3408:             args.append(arg)
gjc@3408: 
gjc@3408:     d['args'] = args
gjc@3408:     
gjc@3408:     return d
gjc@3408: 
gjc@3408: 
gjc@3408: if __name__ == '__main__':
gjc@3408:     import doctest
gjc@3408:     doctest.testmod(sys.modules['__main__'])
gjc@3408: