bindings/python/rad_util.py
changeset 4654 2eaebe77d66b
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/bindings/python/rad_util.py	Sat Jul 04 08:15:48 2009 +0200
     1.3 @@ -0,0 +1,909 @@
     1.4 +# Copyright (c) 2007 RADLogic
     1.5 +# 
     1.6 +# Permission is hereby granted, free of charge, to any person obtaining a copy
     1.7 +# of this software and associated documentation files (the "Software"), to deal
     1.8 +# in the Software without restriction, including without limitation the rights
     1.9 +# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
    1.10 +# copies of the Software, and to permit persons to whom the Software is
    1.11 +# furnished to do so, subject to the following conditions:
    1.12 +# 
    1.13 +# The above copyright notice and this permission notice shall be included in
    1.14 +# all copies or substantial portions of the Software.
    1.15 +# 
    1.16 +# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
    1.17 +# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
    1.18 +# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
    1.19 +# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
    1.20 +# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
    1.21 +# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
    1.22 +# THE SOFTWARE.
    1.23 +"""Provide various handy Python functions.
    1.24 +
    1.25 +Running this script directly will execute the doctests.
    1.26 +
    1.27 +Functions:
    1.28 +int2bin(i, n) -- Convert integer to binary string.
    1.29 +bin2int(bin_string) -- Convert binary string to integer.
    1.30 +reverse(input_string) -- Reverse a string.
    1.31 +transpose(matrix) -- Transpose a list of lists.
    1.32 +polygon_area(points_list) -- Calculate the area of an arbitrary polygon.
    1.33 +timestamp() -- Return string containing current time stamp.
    1.34 +pt2str(point) -- Return prettier string version of point tuple.
    1.35 +gcf(a, b) -- Return the greatest common factor of two numbers.
    1.36 +lcm(a, b) -- Return the least common multiple of two numbers.
    1.37 +permutations(input_list) -- Generate all permutations of a list of items.
    1.38 +reduce_fraction(fraction) -- Reduce fraction (num, denom) to simplest form.
    1.39 +quantile(l, p) -- Return p quantile of list l. E.g. p=0.25 for q1.
    1.40 +trim(l) -- Discard values in list more than 1.5*IQR outside IQR.
    1.41 +nice_units(value) -- Return value converted to human readable units.
    1.42 +uniquify(seq) -- Return sequence with duplicate items in sequence seq removed.
    1.43 +reverse_dict(d) -- Return the dictionary with the items as keys and vice-versa.
    1.44 +lsb(x, n) -- Return the n least significant bits of x.
    1.45 +gray_encode(i) -- Gray encode the given integer.
    1.46 +random_vec(bits, max_value=None) -- Return a random binary vector.
    1.47 +binary_range(bits) -- Return list of all possible binary numbers width=bits.
    1.48 +float_range([start], stop, [step]) -- Return range of floats.
    1.49 +find_common_fixes(s1, s2) -- Find common (prefix, suffix) of two strings.
    1.50 +is_rotated(seq1, seq2) -- Return true if the list is a rotation of other list.
    1.51 +getmodule(obj) -- Return the module that contains the object definition of obj.
    1.52 +                  (use inspect.getmodule instead, though)
    1.53 +get_args(argv) -- Store command-line args in a dictionary.
    1.54 +
    1.55 +This module requires Python >= 2.2
    1.56 +
    1.57 +"""
    1.58 +__author__ = 'Tim Wegener <twegener@radlogic.com.au>'
    1.59 +__date__ = '$Date: 2007/03/27 03:15:06 $'
    1.60 +__version__ = '$Revision: 0.45 $'
    1.61 +__credits__ = """
    1.62 +              David Chandler, for polygon area algorithm.
    1.63 +               (http://www.davidchandler.com/AreaOfAGeneralPolygon.pdf)
    1.64 +              """
    1.65 +
    1.66 +import re
    1.67 +import sys
    1.68 +import time
    1.69 +import random
    1.70 +
    1.71 +try:
    1.72 +    True, False
    1.73 +except NameError:
    1.74 +    True, False = (1==1, 0==1)
    1.75 +
    1.76 +
    1.77 +def int2bin(i, n):
    1.78 +    """Convert decimal integer i to n-bit binary number (string).
    1.79 +
    1.80 +    >>> int2bin(0, 8)
    1.81 +    '00000000'
    1.82 +
    1.83 +    >>> int2bin(123, 8)
    1.84 +    '01111011'
    1.85 +
    1.86 +    >>> int2bin(123L, 8)
    1.87 +    '01111011'
    1.88 +
    1.89 +    >>> int2bin(15, 2)
    1.90 +    Traceback (most recent call last):
    1.91 +    ValueError: Value too large for given number of bits.
    1.92 +
    1.93 +    """
    1.94 +    hex2bin = {'0': '0000', '1': '0001', '2': '0010', '3': '0011',
    1.95 +               '4': '0100', '5': '0101', '6': '0110', '7': '0111',
    1.96 +               '8': '1000', '9': '1001', 'a': '1010', 'b': '1011',
    1.97 +               'c': '1100', 'd': '1101', 'e': '1110', 'f': '1111'}
    1.98 +    # Convert to hex then map each hex digit to binary equivalent.
    1.99 +    result = ''.join([hex2bin[x] for x in hex(i).lower().replace('l','')[2:]])
   1.100 +                      
   1.101 +    # Shrink result to appropriate length.
   1.102 +    # Raise an error if the value is changed by the truncation.
   1.103 +    if '1' in result[:-n]:
   1.104 +        raise ValueError("Value too large for given number of bits.")
   1.105 +    result = result[-n:]
   1.106 +    # Zero-pad if length longer than mapped result.
   1.107 +    result = '0'*(n-len(result)) + result
   1.108 +    return result
   1.109 +
   1.110 +
   1.111 +def bin2int(bin_string):
   1.112 +    """Convert binary number string to decimal integer.
   1.113 +    
   1.114 +    Note: Python > v2 has int(bin_string, 2)
   1.115 +
   1.116 +    >>> bin2int('1111')
   1.117 +    15
   1.118 +
   1.119 +    >>> bin2int('0101')
   1.120 +    5
   1.121 +
   1.122 +    """
   1.123 +##     result = 0
   1.124 +##     bin_list = list(bin_string)
   1.125 +##     if len(filter(lambda x: x in ('1','0'), bin_list)) < len(bin_list):
   1.126 +##         raise Exception ("bin2int: Error - not a binary number: %s"
   1.127 +##                          % bin_string)
   1.128 +##     bit_list = map(int, bin_list)
   1.129 +##     bit_list.reverse()  # Make most significant bit have highest index.
   1.130 +##     for bit_place in range(len(bit_list)):
   1.131 +##         result = result + ((2**bit_place) * bit_list[bit_place])
   1.132 +##     return result
   1.133 +    return int(bin_string, 2)
   1.134 +
   1.135 +
   1.136 +def reverse(input_string):
   1.137 +    """Reverse a string. Useful for strings of binary numbers.
   1.138 +
   1.139 +    >>> reverse('abc')
   1.140 +    'cba'
   1.141 +
   1.142 +    """
   1.143 +    str_list = list(input_string)
   1.144 +    str_list.reverse()
   1.145 +    return ''.join(str_list)
   1.146 +
   1.147 +
   1.148 +def transpose(matrix):
   1.149 +    """Transpose a list of lists.
   1.150 +
   1.151 +    >>> transpose([['a', 'b', 'c'], ['d', 'e', 'f'], ['g', 'h', 'i']])
   1.152 +    [['a', 'd', 'g'], ['b', 'e', 'h'], ['c', 'f', 'i']]
   1.153 +
   1.154 +    >>> transpose([['a', 'b', 'c'], ['d', 'e', 'f']])
   1.155 +    [['a', 'd'], ['b', 'e'], ['c', 'f']]
   1.156 +
   1.157 +    >>> transpose([['a', 'b'], ['d', 'e'], ['g', 'h']])
   1.158 +    [['a', 'd', 'g'], ['b', 'e', 'h']]
   1.159 +
   1.160 +    """
   1.161 +    result = zip(*matrix)
   1.162 +    # Convert list of tuples to list of lists.
   1.163 +    # map is faster than a list comprehension since it is being used with
   1.164 +    # a built-in function as an argument.
   1.165 +    result = map(list, result)
   1.166 +    return result
   1.167 +
   1.168 +
   1.169 +def polygon_area(points_list, precision=100):
   1.170 +    """Calculate area of an arbitrary polygon using an algorithm from the web.
   1.171 +
   1.172 +    Return the area of the polygon as a positive float. 
   1.173 +
   1.174 +    Arguments:
   1.175 +    points_list -- list of point tuples [(x0, y0), (x1, y1), (x2, y2), ...]
   1.176 +                   (Unclosed polygons will be closed automatically.
   1.177 +    precision -- Internal arithmetic precision (integer arithmetic).
   1.178 +
   1.179 +    >>> polygon_area([(0, 0), (0, 1), (1, 1), (1, 2), (2, 2), (2, 0), (0, 0)])
   1.180 +    3.0
   1.181 +
   1.182 +    Credits:
   1.183 +    Area of a General Polygon by David Chandler
   1.184 +    http://www.davidchandler.com/AreaOfAGeneralPolygon.pdf
   1.185 +    
   1.186 +    """
   1.187 +    # Scale up co-ordinates and convert them to integers.
   1.188 +    for i in range(len(points_list)):
   1.189 +        points_list[i] = (int(points_list[i][0] * precision),
   1.190 +                          int(points_list[i][1] * precision))
   1.191 +    # Close polygon if not closed.
   1.192 +    if points_list[-1] != points_list[0]:
   1.193 +        points_list.append(points_list[0])
   1.194 +    # Calculate area.
   1.195 +    area = 0
   1.196 +    for i in range(len(points_list)-1):
   1.197 +        (x_i, y_i) = points_list[i]
   1.198 +        (x_i_plus_1, y_i_plus_1) = points_list[i+1]
   1.199 +        area = area + (x_i_plus_1 * y_i) - (y_i_plus_1 * x_i)
   1.200 +    area = abs(area / 2)
   1.201 +    # Unscale area.
   1.202 +    area = float(area)/(precision**2)
   1.203 +    return area
   1.204 +
   1.205 +
   1.206 +def timestamp():
   1.207 +    """Return string containing current time stamp.
   1.208 +
   1.209 +    Note: In Python 2 onwards can use time.asctime() with no arguments.
   1.210 +
   1.211 +    """
   1.212 +
   1.213 +    return time.asctime()
   1.214 +
   1.215 +
   1.216 +def pt2str(point):
   1.217 +    """Return prettier string version of point tuple.
   1.218 +
   1.219 +    >>> pt2str((1.8, 1.9))
   1.220 +    '(1.8, 1.9)'
   1.221 +
   1.222 +    """
   1.223 +    return "(%s, %s)" % (str(point[0]), str(point[1]))
   1.224 +
   1.225 +
   1.226 +def gcf(a, b, epsilon=1e-16):
   1.227 +    """Return the greatest common factor of a and b, using Euclidean algorithm.
   1.228 +
   1.229 +    Arguments:
   1.230 +    a, b -- two numbers
   1.231 +            If both numbers are integers return an integer result, 
   1.232 +            otherwise return a float result.
   1.233 +    epsilon -- floats less than this magnitude are considered to be zero
   1.234 +               (default: 1e-16)
   1.235 +
   1.236 +    Examples:
   1.237 +
   1.238 +    >>> gcf(12, 34)
   1.239 +    2
   1.240 +
   1.241 +    >>> gcf(13.5, 4)
   1.242 +    0.5
   1.243 +
   1.244 +    >>> gcf(-2, 4)
   1.245 +    2
   1.246 +
   1.247 +    >>> gcf(5, 0)
   1.248 +    5
   1.249 +
   1.250 +    By (a convenient) definition:
   1.251 +    >>> gcf(0, 0)
   1.252 +    0
   1.253 +
   1.254 +    """
   1.255 +    result = max(a, b)
   1.256 +    remainder = min(a, b)
   1.257 +    while remainder and abs(remainder) > epsilon:
   1.258 +        new_remainder = result % remainder
   1.259 +        result = remainder
   1.260 +        remainder = new_remainder
   1.261 +    return abs(result)
   1.262 +
   1.263 +def lcm(a, b, precision=None):
   1.264 +    """Return the least common multiple of a and b, using the gcf function.
   1.265 +
   1.266 +    Arguments:
   1.267 +    a, b -- two numbers. If both are integers return an integer result, 
   1.268 +            otherwise a return a float result.
   1.269 +    precision -- scaling factor if a and/or b are floats.
   1.270 +
   1.271 +    >>> lcm(21, 6)
   1.272 +    42
   1.273 +
   1.274 +    >>> lcm(2.5, 3.5)
   1.275 +    17.5
   1.276 +
   1.277 +    >>> str(lcm(1.5e-8, 2.5e-8, precision=1e9))
   1.278 +    '7.5e-08'
   1.279 +
   1.280 +    By (an arbitary) definition:
   1.281 +    >>> lcm(0, 0)
   1.282 +    0
   1.283 +
   1.284 +    """
   1.285 +    # Note: Dummy precision argument is for backwards compatibility.
   1.286 +    # Do the division first.
   1.287 +    # (See http://en.wikipedia.org/wiki/Least_common_multiple )
   1.288 +    denom = gcf(a, b)
   1.289 +    if denom == 0:
   1.290 +        result = 0
   1.291 +    else:
   1.292 +        result = a * (b / denom)
   1.293 +    return result
   1.294 +
   1.295 +
   1.296 +def permutations(input_list):
   1.297 +    """Return a list containing all permutations of the input list.
   1.298 +
   1.299 +    Note: This is a recursive function.
   1.300 +
   1.301 +    >>> perms = permutations(['a', 'b', 'c'])
   1.302 +    >>> perms.sort()
   1.303 +    >>> for perm in perms:
   1.304 +    ...     print perm
   1.305 +    ['a', 'b', 'c']
   1.306 +    ['a', 'c', 'b']
   1.307 +    ['b', 'a', 'c']
   1.308 +    ['b', 'c', 'a']
   1.309 +    ['c', 'a', 'b']
   1.310 +    ['c', 'b', 'a']
   1.311 +
   1.312 +    """
   1.313 +    out_lists = []
   1.314 +    if len(input_list) > 1:
   1.315 +        # Extract first item in list.
   1.316 +        item = input_list[0]
   1.317 +        # Find all permutations of remainder of list. (Recursive call.)
   1.318 +        sub_lists = permutations(input_list[1:])
   1.319 +        # For every permutation of the sub list...
   1.320 +        for sub_list in sub_lists:
   1.321 +            # Insert the extracted first item at every position of the list.
   1.322 +            for i in range(len(input_list)):
   1.323 +                new_list = sub_list[:]
   1.324 +                new_list.insert(i, item)
   1.325 +                out_lists.append(new_list)
   1.326 +    else:
   1.327 +        # Termination condition: only one item in input list.
   1.328 +        out_lists = [input_list]
   1.329 +    return out_lists
   1.330 +
   1.331 +
   1.332 +def reduce_fraction(fraction):
   1.333 +    """Reduce fraction tuple to simplest form. fraction=(num, denom)
   1.334 +    
   1.335 +    >>> reduce_fraction((14, 7))
   1.336 +    (2, 1)
   1.337 +
   1.338 +    >>> reduce_fraction((-2, 4))
   1.339 +    (-1, 2)
   1.340 +
   1.341 +    >>> reduce_fraction((0, 4))
   1.342 +    (0, 1)
   1.343 +
   1.344 +    >>> reduce_fraction((4, 0))
   1.345 +    (1, 0)
   1.346 +    
   1.347 +    """
   1.348 +    (numerator, denominator) = fraction
   1.349 +    common_factor = abs(gcf(numerator, denominator))
   1.350 +    result = (numerator/common_factor, denominator/common_factor)
   1.351 +    return result
   1.352 +
   1.353 +
   1.354 +def quantile(l, p):
   1.355 +    """Return p quantile of list l. E.g. p=0.25 for q1.
   1.356 +
   1.357 +    See:
   1.358 +    http://rweb.stat.umn.edu/R/library/base/html/quantile.html
   1.359 +
   1.360 +    """
   1.361 +    l_sort = l[:]
   1.362 +    l_sort.sort()
   1.363 +    n = len(l)
   1.364 +    r = 1 + ((n - 1) * p)
   1.365 +    i = int(r)
   1.366 +    f = r - i
   1.367 +    if i < n:
   1.368 +        result =  (1-f)*l_sort[i-1] + f*l_sort[i]
   1.369 +    else:
   1.370 +        result = l_sort[i-1]
   1.371 +    return result
   1.372 +
   1.373 +
   1.374 +def trim(l):
   1.375 +    """Discard values in list more than 1.5*IQR outside IQR.
   1.376 +
   1.377 +    (IQR is inter-quartile-range)
   1.378 +
   1.379 +    This function uses rad_util.quantile
   1.380 +
   1.381 +    1.5*IQR -- mild outlier
   1.382 +    3*IQR -- extreme outlier
   1.383 +
   1.384 +    See:
   1.385 +    http://wind.cc.whecn.edu/~pwildman/statnew/section_7_-_exploratory_data_analysis.htm
   1.386 +
   1.387 +    """
   1.388 +    l_sort = l[:]
   1.389 +    l_sort.sort()
   1.390 +    # Calculate medianscore  (based on stats.py lmedianscore by Gary Strangman)
   1.391 +    if len(l_sort) % 2 == 0:
   1.392 +        # If even number of scores, average middle 2.
   1.393 +        index = int(len(l_sort) / 2)  # Integer division correct
   1.394 +        median = float(l_sort[index] + l_sort[index-1]) / 2
   1.395 +    else:
   1.396 +        # int divsion gives mid value when count from 0
   1.397 +        index = int(len(l_sort) / 2)
   1.398 +        median = l_sort[index]
   1.399 +    # Calculate IQR.
   1.400 +    q1 = quantile(l_sort, 0.25)
   1.401 +    q3 = quantile(l_sort, 0.75)
   1.402 +    iqr = q3 - q1
   1.403 +    iqr_extra = iqr * 1.5
   1.404 +    def in_interval(x, i=iqr_extra, q1=q1, q3=q3):
   1.405 +        return (x >= q1-i and x <= q3+i)
   1.406 +    l_trimmed = [x for x in l_sort if in_interval(x)]
   1.407 +    return l_trimmed
   1.408 +
   1.409 +
   1.410 +def nice_units(value, dp=0, sigfigs=None, suffix='', space=' ',
   1.411 +               use_extra_prefixes=False, use_full_name=False, mode='si'):
   1.412 +    """Return value converted to human readable units eg milli, micro, etc.
   1.413 +
   1.414 +    Arguments:
   1.415 +    value -- number in base units
   1.416 +    dp -- number of decimal places to display (rounded)
   1.417 +    sigfigs -- number of significant figures to display (rounded)
   1.418 +               This overrides dp if set.
   1.419 +    suffix -- optional unit suffix to append to unit multiplier
   1.420 +    space -- seperator between value and unit multiplier (default: ' ')
   1.421 +    use_extra_prefixes -- use hecto, deka, deci and centi as well if set.
   1.422 +                          (default: False)
   1.423 +    use_full_name -- use full name for multiplier symbol,
   1.424 +                     e.g. milli instead of m
   1.425 +                     (default: False)
   1.426 +    mode -- 'si' for SI prefixes, 'bin' for binary multipliers (1024, etc.)
   1.427 +            (Default: 'si')
   1.428 +
   1.429 +    SI prefixes from:
   1.430 +    http://physics.nist.gov/cuu/Units/prefixes.html
   1.431 +    (Greek mu changed to u.)
   1.432 +    Binary prefixes based on:
   1.433 +    http://physics.nist.gov/cuu/Units/binary.html
   1.434 +
   1.435 +    >>> nice_units(2e-11)
   1.436 +    '20 p'
   1.437 +
   1.438 +    >>> nice_units(2e-11, space='')
   1.439 +    '20p'
   1.440 +
   1.441 +    """
   1.442 +    si_prefixes = {1e24:  ('Y', 'yotta'),
   1.443 +                   1e21:  ('Z', 'zetta'),
   1.444 +                   1e18:  ('E', 'exa'),
   1.445 +                   1e15:  ('P', 'peta'),
   1.446 +                   1e12:  ('T', 'tera'),
   1.447 +                   1e9:   ('G', 'giga'),
   1.448 +                   1e6:   ('M', 'mega'),
   1.449 +                   1e3:   ('k', 'kilo'),
   1.450 +                   1e-3:  ('m', 'milli'),
   1.451 +                   1e-6:  ('u', 'micro'),
   1.452 +                   1e-9:  ('n', 'nano'),
   1.453 +                   1e-12: ('p', 'pico'),
   1.454 +                   1e-15: ('f', 'femto'),
   1.455 +                   1e-18: ('a', 'atto'),
   1.456 +                   1e-21: ('z', 'zepto'),
   1.457 +                   1e-24: ('y', 'yocto')
   1.458 +                   }
   1.459 +    if use_extra_prefixes:
   1.460 +        si_prefixes.update({1e2:  ('h', 'hecto'),
   1.461 +                            1e1:  ('da', 'deka'),
   1.462 +                            1e-1: ('d', 'deci'),
   1.463 +                            1e-2: ('c', 'centi')
   1.464 +                            })
   1.465 +    bin_prefixes = {2**10: ('K', 'kilo'),
   1.466 +                    2**20: ('M', 'mega'),
   1.467 +                    2**30: ('G', 'mega'),
   1.468 +                    2**40: ('T', 'tera'),
   1.469 +                    2**50: ('P', 'peta'),
   1.470 +                    2**60: ('E', 'exa')
   1.471 +                    }
   1.472 +    if mode == 'bin':
   1.473 +        prefixes = bin_prefixes
   1.474 +    else:
   1.475 +        prefixes = si_prefixes
   1.476 +    prefixes[1] = ('', '')  # Unity.
   1.477 +    # Determine appropriate multiplier.
   1.478 +    multipliers = prefixes.keys()
   1.479 +    multipliers.sort()
   1.480 +    mult = None
   1.481 +    for i in range(len(multipliers) - 1):
   1.482 +        lower_mult = multipliers[i]
   1.483 +        upper_mult = multipliers[i+1]
   1.484 +        if lower_mult <= value < upper_mult:
   1.485 +            mult_i = i
   1.486 +            break
   1.487 +    if mult is None:
   1.488 +        if value < multipliers[0]:
   1.489 +            mult_i = 0
   1.490 +        elif value >= multipliers[-1]:
   1.491 +            mult_i = len(multipliers) - 1
   1.492 +    mult = multipliers[mult_i]
   1.493 +    # Convert value for this multiplier.
   1.494 +    new_value = value / mult
   1.495 +    # Deal with special case due to rounding.
   1.496 +    if sigfigs is None:
   1.497 +        if mult_i < (len(multipliers) - 1) and \
   1.498 +               round(new_value, dp) == \
   1.499 +               round((multipliers[mult_i+1] / mult), dp):
   1.500 +            mult = multipliers[mult_i + 1]
   1.501 +            new_value = value / mult
   1.502 +    # Concatenate multiplier symbol.
   1.503 +    if use_full_name:
   1.504 +        label_type = 1
   1.505 +    else:
   1.506 +        label_type = 0
   1.507 +    # Round and truncate to appropriate precision.
   1.508 +    if sigfigs is None:
   1.509 +        str_value = eval('"%.'+str(dp)+'f" % new_value', locals(), {})
   1.510 +    else:
   1.511 +        str_value = eval('"%.'+str(sigfigs)+'g" % new_value', locals(), {})
   1.512 +    return str_value + space + prefixes[mult][label_type] + suffix
   1.513 +
   1.514 +
   1.515 +def uniquify(seq, preserve_order=False):
   1.516 +    """Return sequence with duplicate items in sequence seq removed.
   1.517 +
   1.518 +    The code is based on usenet post by Tim Peters.
   1.519 +
   1.520 +    This code is O(N) if the sequence items are hashable, O(N**2) if not.
   1.521 +    
   1.522 +    Peter Bengtsson has a blog post with an empirical comparison of other
   1.523 +    approaches:
   1.524 +    http://www.peterbe.com/plog/uniqifiers-benchmark
   1.525 +
   1.526 +    If order is not important and the sequence items are hashable then
   1.527 +    list(set(seq)) is readable and efficient.
   1.528 +
   1.529 +    If order is important and the sequence items are hashable generator
   1.530 +    expressions can be used (in py >= 2.4) (useful for large sequences):
   1.531 +    seen = set()
   1.532 +    do_something(x for x in seq if x not in seen or seen.add(x))
   1.533 +
   1.534 +    Arguments:
   1.535 +    seq -- sequence
   1.536 +    preserve_order -- if not set the order will be arbitrary
   1.537 +                      Using this option will incur a speed penalty.
   1.538 +                      (default: False)
   1.539 +
   1.540 +    Example showing order preservation:
   1.541 +
   1.542 +    >>> uniquify(['a', 'aa', 'b', 'b', 'ccc', 'ccc', 'd'], preserve_order=True)
   1.543 +    ['a', 'aa', 'b', 'ccc', 'd']
   1.544 +
   1.545 +    Example using a sequence of un-hashable items:
   1.546 +
   1.547 +    >>> uniquify([['z'], ['x'], ['y'], ['z']], preserve_order=True)
   1.548 +    [['z'], ['x'], ['y']]
   1.549 +
   1.550 +    The sorted output or the non-order-preserving approach should equal
   1.551 +    that of the sorted order-preserving approach output:
   1.552 +    
   1.553 +    >>> unordered = uniquify([3, 3, 1, 2], preserve_order=False)
   1.554 +    >>> unordered.sort()
   1.555 +    >>> ordered = uniquify([3, 3, 1, 2], preserve_order=True)
   1.556 +    >>> ordered.sort()
   1.557 +    >>> ordered
   1.558 +    [1, 2, 3]
   1.559 +    >>> int(ordered == unordered)
   1.560 +    1
   1.561 +
   1.562 +    """
   1.563 +    try:
   1.564 +        # Attempt fast algorithm.
   1.565 +        d = {}
   1.566 +        if preserve_order:
   1.567 +            # This is based on Dave Kirby's method (f8) noted in the post:
   1.568 +            # http://www.peterbe.com/plog/uniqifiers-benchmark
   1.569 +            return [x for x in seq if (x not in d) and not d.__setitem__(x, 0)]
   1.570 +        else:
   1.571 +            for x in seq:
   1.572 +                d[x] = 0
   1.573 +            return d.keys()
   1.574 +    except TypeError:
   1.575 +        # Have an unhashable object, so use slow algorithm.
   1.576 +        result = []
   1.577 +        app = result.append
   1.578 +        for x in seq:
   1.579 +            if x not in result:
   1.580 +                app(x)
   1.581 +        return result
   1.582 +
   1.583 +# Alias to noun form for backward compatibility.
   1.584 +unique = uniquify
   1.585 +
   1.586 +
   1.587 +def reverse_dict(d):
   1.588 +    """Reverse a dictionary so the items become the keys and vice-versa.
   1.589 +
   1.590 +    Note: The results will be arbitrary if the items are not unique.
   1.591 +
   1.592 +    >>> d = reverse_dict({'a': 1, 'b': 2})
   1.593 +    >>> d_items = d.items()
   1.594 +    >>> d_items.sort()
   1.595 +    >>> d_items
   1.596 +    [(1, 'a'), (2, 'b')]
   1.597 +
   1.598 +    """
   1.599 +    result = {}
   1.600 +    for key, value in d.items():
   1.601 +        result[value] = key
   1.602 +    return result
   1.603 +
   1.604 +    
   1.605 +def lsb(x, n):
   1.606 +    """Return the n least significant bits of x.
   1.607 +
   1.608 +    >>> lsb(13, 3)
   1.609 +    5
   1.610 +
   1.611 +    """
   1.612 +    return x & ((2 ** n) - 1)
   1.613 +
   1.614 +
   1.615 +def gray_encode(i):
   1.616 +    """Gray encode the given integer."""
   1.617 +
   1.618 +    return i ^ (i >> 1)
   1.619 +
   1.620 +
   1.621 +def random_vec(bits, max_value=None):
   1.622 +    """Generate a random binary vector of length bits and given max value."""
   1.623 +
   1.624 +    vector = ""
   1.625 +    for _ in range(int(bits / 10) + 1):
   1.626 +        i = int((2**10) * random.random())
   1.627 +        vector += int2bin(i, 10)
   1.628 +
   1.629 +    if max_value and (max_value < 2 ** bits - 1):
   1.630 +        vector = int2bin((int(vector, 2) / (2 ** bits - 1)) * max_value, bits)
   1.631 +    
   1.632 +    return vector[0:bits]
   1.633 +
   1.634 +
   1.635 +def binary_range(bits):
   1.636 +    """Return a list of all possible binary numbers in order with width=bits. 
   1.637 +    
   1.638 +    It would be nice to extend it to match the
   1.639 +    functionality of python's range() built-in function.
   1.640 +    
   1.641 +    """
   1.642 +    l = []
   1.643 +    v = ['0'] * bits
   1.644 +
   1.645 +    toggle = [1] + [0] * bits
   1.646 +    
   1.647 +    while toggle[bits] != 1:
   1.648 +        v_copy = v[:]
   1.649 +        v_copy.reverse()
   1.650 +        l.append(''.join(v_copy))
   1.651 +        
   1.652 +        toggle = [1] + [0]*bits
   1.653 +        i = 0
   1.654 +        while i < bits and toggle[i] == 1:
   1.655 +            if toggle[i]:
   1.656 +                if v[i] == '0':
   1.657 +                    v[i] = '1'
   1.658 +                    toggle[i+1] = 0
   1.659 +                else:
   1.660 +                    v[i] = '0'
   1.661 +                    toggle[i+1] = 1
   1.662 +            i += 1
   1.663 +    return l
   1.664 +
   1.665 +
   1.666 +def float_range(start, stop=None, step=None):
   1.667 +    """Return a list containing an arithmetic progression of floats.
   1.668 +
   1.669 +    Return a list of floats between 0.0 (or start) and stop with an
   1.670 +    increment of step. 
   1.671 +
   1.672 +    This is in functionality to python's range() built-in function 
   1.673 +    but can accept float increments.
   1.674 +
   1.675 +    As with range(), stop is omitted from the list.
   1.676 +
   1.677 +    """
   1.678 +    if stop is None:
   1.679 +        stop = float(start)
   1.680 +        start = 0.0
   1.681 +
   1.682 +    if step is None:
   1.683 +        step = 1.0
   1.684 +
   1.685 +    cur = float(start)
   1.686 +    l = []
   1.687 +    while cur < stop:
   1.688 +        l.append(cur)
   1.689 +        cur += step
   1.690 +
   1.691 +    return l
   1.692 +
   1.693 +
   1.694 +def find_common_fixes(s1, s2):
   1.695 +    """Find common (prefix, suffix) of two strings.
   1.696 +
   1.697 +    >>> find_common_fixes('abc', 'def')
   1.698 +    ('', '')
   1.699 +
   1.700 +    >>> find_common_fixes('abcelephantdef', 'abccowdef')
   1.701 +    ('abc', 'def')
   1.702 +
   1.703 +    >>> find_common_fixes('abcelephantdef', 'abccow')
   1.704 +    ('abc', '')
   1.705 +
   1.706 +    >>> find_common_fixes('elephantdef', 'abccowdef')
   1.707 +    ('', 'def')
   1.708 +
   1.709 +    """
   1.710 +    prefix = []
   1.711 +    suffix = []
   1.712 +
   1.713 +    i = 0
   1.714 +    common_len = min(len(s1), len(s2))
   1.715 +    while i < common_len:
   1.716 +        if s1[i] != s2[i]:
   1.717 +            break
   1.718 +
   1.719 +        prefix.append(s1[i])
   1.720 +        i += 1
   1.721 +
   1.722 +    i = 1
   1.723 +    while i < (common_len + 1):
   1.724 +        if s1[-i] != s2[-i]:
   1.725 +            break
   1.726 +        
   1.727 +        suffix.append(s1[-i])
   1.728 +        i += 1
   1.729 +
   1.730 +    suffix.reverse()
   1.731 +
   1.732 +    prefix = ''.join(prefix)
   1.733 +    suffix = ''.join(suffix)
   1.734 +        
   1.735 +    return (prefix, suffix)
   1.736 +
   1.737 +
   1.738 +def is_rotated(seq1, seq2):
   1.739 +    """Return true if the first sequence is a rotation of the second sequence.
   1.740 +
   1.741 +    >>> seq1 = ['A', 'B', 'C', 'D']
   1.742 +    >>> seq2 = ['C', 'D', 'A', 'B']
   1.743 +    >>> int(is_rotated(seq1, seq2))
   1.744 +    1
   1.745 +
   1.746 +    >>> seq2 = ['C', 'D', 'B', 'A']
   1.747 +    >>> int(is_rotated(seq1, seq2))
   1.748 +    0
   1.749 +
   1.750 +    >>> seq1 = ['A', 'B', 'C', 'A']
   1.751 +    >>> seq2 = ['A', 'A', 'B', 'C']
   1.752 +    >>> int(is_rotated(seq1, seq2))
   1.753 +    1
   1.754 +
   1.755 +    >>> seq2 = ['A', 'B', 'C', 'A']
   1.756 +    >>> int(is_rotated(seq1, seq2))
   1.757 +    1
   1.758 +
   1.759 +    >>> seq2 = ['A', 'A', 'C', 'B']
   1.760 +    >>> int(is_rotated(seq1, seq2))
   1.761 +    0
   1.762 +
   1.763 +    """
   1.764 +    # Do a sanity check.
   1.765 +    if len(seq1) != len(seq2):
   1.766 +        return False
   1.767 +    # Look for occurrences of second sequence head item in first sequence.
   1.768 +    start_indexes = []
   1.769 +    head_item = seq2[0]
   1.770 +    for index1 in range(len(seq1)):
   1.771 +        if seq1[index1] == head_item:
   1.772 +            start_indexes.append(index1)
   1.773 +    # Check that wrapped sequence matches.
   1.774 +    double_seq1 = seq1 + seq1
   1.775 +    for index1 in start_indexes:
   1.776 +        if double_seq1[index1:index1+len(seq1)] == seq2:
   1.777 +            return True
   1.778 +    return False
   1.779 +
   1.780 +def getmodule(obj):
   1.781 +    """Return the module that contains the object definition of obj.
   1.782 +
   1.783 +    Note: Use inspect.getmodule instead.
   1.784 +
   1.785 +    Arguments:
   1.786 +    obj -- python obj, generally a class or a function
   1.787 +
   1.788 +    Examples:
   1.789 +    
   1.790 +    A function:
   1.791 +    >>> module = getmodule(random.choice)
   1.792 +    >>> module.__name__
   1.793 +    'random'
   1.794 +    >>> module is random
   1.795 +    1
   1.796 +
   1.797 +    A class:
   1.798 +    >>> module = getmodule(random.Random)
   1.799 +    >>> module.__name__
   1.800 +    'random'
   1.801 +    >>> module is random
   1.802 +    1
   1.803 +
   1.804 +    A class inheriting from a class in another module:
   1.805 +    (note: The inheriting class must define at least one function.)
   1.806 +    >>> class MyRandom(random.Random):
   1.807 +    ...     def play(self):
   1.808 +    ...         pass
   1.809 +    >>> module = getmodule(MyRandom)
   1.810 +    >>> if __name__ == '__main__':
   1.811 +    ...     name = 'rad_util'
   1.812 +    ... else:
   1.813 +    ...     name = module.__name__
   1.814 +    >>> name
   1.815 +    'rad_util'
   1.816 +    >>> module is sys.modules[__name__]
   1.817 +    1
   1.818 +
   1.819 +    Discussion:
   1.820 +    This approach is slightly hackish, and won't work in various situations.
   1.821 +    However, this was the approach recommended by GvR, so it's as good as
   1.822 +    you'll get.
   1.823 +
   1.824 +    See GvR's post in this thread:
   1.825 +    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
   1.826 +    
   1.827 +    """
   1.828 +    if hasattr(obj, 'func_globals'):
   1.829 +        func = obj
   1.830 +    else:
   1.831 +        # Handle classes.
   1.832 +        func = None
   1.833 +        for item in obj.__dict__.values():
   1.834 +            if hasattr(item, 'func_globals'):
   1.835 +                func = item
   1.836 +                break
   1.837 +        if func is None:
   1.838 +            raise ValueError("No functions attached to object: %r" % obj)
   1.839 +    module_name = func.func_globals['__name__']
   1.840 +    # Get module.
   1.841 +    module = sys.modules[module_name]
   1.842 +    return module
   1.843 +
   1.844 +
   1.845 +def round_grid(value, grid, mode=0):
   1.846 +    """Round off the given value to the given grid size.
   1.847 +
   1.848 +    Arguments:
   1.849 +    value -- value to be roudne
   1.850 +    grid -- result must be a multiple of this
   1.851 +    mode -- 0 nearest, 1 up, -1 down
   1.852 +
   1.853 +    Examples:
   1.854 +    
   1.855 +    >>> round_grid(7.5, 5)
   1.856 +    10
   1.857 +
   1.858 +    >>> round_grid(7.5, 5, mode=-1)
   1.859 +    5
   1.860 +
   1.861 +    >>> round_grid(7.3, 5, mode=1)
   1.862 +    10
   1.863 +
   1.864 +    >>> round_grid(7.3, 5.0, mode=1)
   1.865 +    10.0
   1.866 +
   1.867 +    """
   1.868 +    off_grid = value % grid
   1.869 +    if mode == 0:
   1.870 +        add_one = int(off_grid >= (grid / 2.0))
   1.871 +    elif mode == 1 and off_grid:
   1.872 +        add_one = 1
   1.873 +    elif mode == -1 and off_grid:
   1.874 +        add_one = 0
   1.875 +    result = ((int(value / grid) + add_one) * grid)
   1.876 +    return result
   1.877 +
   1.878 +
   1.879 +def get_args(argv):
   1.880 +    """Store command-line args in a dictionary.
   1.881 +    
   1.882 +    -, -- prefixes are removed
   1.883 +    Items not prefixed with - or -- are stored as a list, indexed by 'args'
   1.884 +
   1.885 +    For options that take a value use --option=value
   1.886 +
   1.887 +    Consider using optparse or getopt (in Python standard library) instead.
   1.888 +
   1.889 +    """
   1.890 +    d = {}
   1.891 +    args = []
   1.892 +    
   1.893 +    for arg in argv:
   1.894 +            
   1.895 +        if arg.startswith('-'):
   1.896 +            parts = re.sub(r'^-+', '', arg).split('=')
   1.897 +            if len(parts) == 2:
   1.898 +                d[parts[0]] = parts[1]
   1.899 +            else:
   1.900 +                d[parts[0]] = None
   1.901 +        else:
   1.902 +            args.append(arg)
   1.903 +
   1.904 +    d['args'] = args
   1.905 +    
   1.906 +    return d
   1.907 +
   1.908 +
   1.909 +if __name__ == '__main__':
   1.910 +    import doctest
   1.911 +    doctest.testmod(sys.modules['__main__'])
   1.912 +