bindings/python/rad_util.py
author Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
Sat, 04 Jul 2009 08:15:48 +0200
changeset 4654 2eaebe77d66b
permissions -rw-r--r--
Added tag ns-3.5 for changeset c975274c9707
gjc@3408
     1
# Copyright (c) 2007 RADLogic
gjc@3408
     2
# 
gjc@3408
     3
# Permission is hereby granted, free of charge, to any person obtaining a copy
gjc@3408
     4
# of this software and associated documentation files (the "Software"), to deal
gjc@3408
     5
# in the Software without restriction, including without limitation the rights
gjc@3408
     6
# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
gjc@3408
     7
# copies of the Software, and to permit persons to whom the Software is
gjc@3408
     8
# furnished to do so, subject to the following conditions:
gjc@3408
     9
# 
gjc@3408
    10
# The above copyright notice and this permission notice shall be included in
gjc@3408
    11
# all copies or substantial portions of the Software.
gjc@3408
    12
# 
gjc@3408
    13
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
gjc@3408
    14
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
gjc@3408
    15
# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
gjc@3408
    16
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
gjc@3408
    17
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
gjc@3408
    18
# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
gjc@3408
    19
# THE SOFTWARE.
gjc@3408
    20
"""Provide various handy Python functions.
gjc@3408
    21
gjc@3408
    22
Running this script directly will execute the doctests.
gjc@3408
    23
gjc@3408
    24
Functions:
gjc@3408
    25
int2bin(i, n) -- Convert integer to binary string.
gjc@3408
    26
bin2int(bin_string) -- Convert binary string to integer.
gjc@3408
    27
reverse(input_string) -- Reverse a string.
gjc@3408
    28
transpose(matrix) -- Transpose a list of lists.
gjc@3408
    29
polygon_area(points_list) -- Calculate the area of an arbitrary polygon.
gjc@3408
    30
timestamp() -- Return string containing current time stamp.
gjc@3408
    31
pt2str(point) -- Return prettier string version of point tuple.
gjc@3408
    32
gcf(a, b) -- Return the greatest common factor of two numbers.
gjc@3408
    33
lcm(a, b) -- Return the least common multiple of two numbers.
gjc@3408
    34
permutations(input_list) -- Generate all permutations of a list of items.
gjc@3408
    35
reduce_fraction(fraction) -- Reduce fraction (num, denom) to simplest form.
gjc@3408
    36
quantile(l, p) -- Return p quantile of list l. E.g. p=0.25 for q1.
gjc@3408
    37
trim(l) -- Discard values in list more than 1.5*IQR outside IQR.
gjc@3408
    38
nice_units(value) -- Return value converted to human readable units.
gjc@3408
    39
uniquify(seq) -- Return sequence with duplicate items in sequence seq removed.
gjc@3408
    40
reverse_dict(d) -- Return the dictionary with the items as keys and vice-versa.
gjc@3408
    41
lsb(x, n) -- Return the n least significant bits of x.
gjc@3408
    42
gray_encode(i) -- Gray encode the given integer.
gjc@3408
    43
random_vec(bits, max_value=None) -- Return a random binary vector.
gjc@3408
    44
binary_range(bits) -- Return list of all possible binary numbers width=bits.
gjc@3408
    45
float_range([start], stop, [step]) -- Return range of floats.
gjc@3408
    46
find_common_fixes(s1, s2) -- Find common (prefix, suffix) of two strings.
gjc@3408
    47
is_rotated(seq1, seq2) -- Return true if the list is a rotation of other list.
gjc@3408
    48
getmodule(obj) -- Return the module that contains the object definition of obj.
gjc@3408
    49
                  (use inspect.getmodule instead, though)
gjc@3408
    50
get_args(argv) -- Store command-line args in a dictionary.
gjc@3408
    51
gjc@3408
    52
This module requires Python >= 2.2
gjc@3408
    53
gjc@3408
    54
"""
gjc@3408
    55
__author__ = 'Tim Wegener <twegener@radlogic.com.au>'
gjc@3408
    56
__date__ = '$Date: 2007/03/27 03:15:06 $'
gjc@3408
    57
__version__ = '$Revision: 0.45 $'
gjc@3408
    58
__credits__ = """
gjc@3408
    59
              David Chandler, for polygon area algorithm.
gjc@3408
    60
               (http://www.davidchandler.com/AreaOfAGeneralPolygon.pdf)
gjc@3408
    61
              """
gjc@3408
    62
gjc@3408
    63
import re
gjc@3408
    64
import sys
gjc@3408
    65
import time
gjc@3408
    66
import random
gjc@3408
    67
gjc@3408
    68
try:
gjc@3408
    69
    True, False
gjc@3408
    70
except NameError:
gjc@3408
    71
    True, False = (1==1, 0==1)
gjc@3408
    72
gjc@3408
    73
gjc@3408
    74
def int2bin(i, n):
gjc@3408
    75
    """Convert decimal integer i to n-bit binary number (string).
gjc@3408
    76
gjc@3408
    77
    >>> int2bin(0, 8)
gjc@3408
    78
    '00000000'
gjc@3408
    79
gjc@3408
    80
    >>> int2bin(123, 8)
gjc@3408
    81
    '01111011'
gjc@3408
    82
gjc@3408
    83
    >>> int2bin(123L, 8)
gjc@3408
    84
    '01111011'
gjc@3408
    85
gjc@3408
    86
    >>> int2bin(15, 2)
gjc@3408
    87
    Traceback (most recent call last):
gjc@3408
    88
    ValueError: Value too large for given number of bits.
gjc@3408
    89
gjc@3408
    90
    """
gjc@3408
    91
    hex2bin = {'0': '0000', '1': '0001', '2': '0010', '3': '0011',
gjc@3408
    92
               '4': '0100', '5': '0101', '6': '0110', '7': '0111',
gjc@3408
    93
               '8': '1000', '9': '1001', 'a': '1010', 'b': '1011',
gjc@3408
    94
               'c': '1100', 'd': '1101', 'e': '1110', 'f': '1111'}
gjc@3408
    95
    # Convert to hex then map each hex digit to binary equivalent.
gjc@3408
    96
    result = ''.join([hex2bin[x] for x in hex(i).lower().replace('l','')[2:]])
gjc@3408
    97
                      
gjc@3408
    98
    # Shrink result to appropriate length.
gjc@3408
    99
    # Raise an error if the value is changed by the truncation.
gjc@3408
   100
    if '1' in result[:-n]:
gjc@3408
   101
        raise ValueError("Value too large for given number of bits.")
gjc@3408
   102
    result = result[-n:]
gjc@3408
   103
    # Zero-pad if length longer than mapped result.
gjc@3408
   104
    result = '0'*(n-len(result)) + result
gjc@3408
   105
    return result
gjc@3408
   106
gjc@3408
   107
gjc@3408
   108
def bin2int(bin_string):
gjc@3408
   109
    """Convert binary number string to decimal integer.
gjc@3408
   110
    
gjc@3408
   111
    Note: Python > v2 has int(bin_string, 2)
gjc@3408
   112
gjc@3408
   113
    >>> bin2int('1111')
gjc@3408
   114
    15
gjc@3408
   115
gjc@3408
   116
    >>> bin2int('0101')
gjc@3408
   117
    5
gjc@3408
   118
gjc@3408
   119
    """
gjc@3408
   120
##     result = 0
gjc@3408
   121
##     bin_list = list(bin_string)
gjc@3408
   122
##     if len(filter(lambda x: x in ('1','0'), bin_list)) < len(bin_list):
gjc@3408
   123
##         raise Exception ("bin2int: Error - not a binary number: %s"
gjc@3408
   124
##                          % bin_string)
gjc@3408
   125
##     bit_list = map(int, bin_list)
gjc@3408
   126
##     bit_list.reverse()  # Make most significant bit have highest index.
gjc@3408
   127
##     for bit_place in range(len(bit_list)):
gjc@3408
   128
##         result = result + ((2**bit_place) * bit_list[bit_place])
gjc@3408
   129
##     return result
gjc@3408
   130
    return int(bin_string, 2)
gjc@3408
   131
gjc@3408
   132
gjc@3408
   133
def reverse(input_string):
gjc@3408
   134
    """Reverse a string. Useful for strings of binary numbers.
gjc@3408
   135
gjc@3408
   136
    >>> reverse('abc')
gjc@3408
   137
    'cba'
gjc@3408
   138
gjc@3408
   139
    """
gjc@3408
   140
    str_list = list(input_string)
gjc@3408
   141
    str_list.reverse()
gjc@3408
   142
    return ''.join(str_list)
gjc@3408
   143
gjc@3408
   144
gjc@3408
   145
def transpose(matrix):
gjc@3408
   146
    """Transpose a list of lists.
gjc@3408
   147
gjc@3408
   148
    >>> transpose([['a', 'b', 'c'], ['d', 'e', 'f'], ['g', 'h', 'i']])
gjc@3408
   149
    [['a', 'd', 'g'], ['b', 'e', 'h'], ['c', 'f', 'i']]
gjc@3408
   150
gjc@3408
   151
    >>> transpose([['a', 'b', 'c'], ['d', 'e', 'f']])
gjc@3408
   152
    [['a', 'd'], ['b', 'e'], ['c', 'f']]
gjc@3408
   153
gjc@3408
   154
    >>> transpose([['a', 'b'], ['d', 'e'], ['g', 'h']])
gjc@3408
   155
    [['a', 'd', 'g'], ['b', 'e', 'h']]
gjc@3408
   156
gjc@3408
   157
    """
gjc@3408
   158
    result = zip(*matrix)
gjc@3408
   159
    # Convert list of tuples to list of lists.
gjc@3408
   160
    # map is faster than a list comprehension since it is being used with
gjc@3408
   161
    # a built-in function as an argument.
gjc@3408
   162
    result = map(list, result)
gjc@3408
   163
    return result
gjc@3408
   164
gjc@3408
   165
gjc@3408
   166
def polygon_area(points_list, precision=100):
gjc@3408
   167
    """Calculate area of an arbitrary polygon using an algorithm from the web.
gjc@3408
   168
gjc@3408
   169
    Return the area of the polygon as a positive float. 
gjc@3408
   170
gjc@3408
   171
    Arguments:
gjc@3408
   172
    points_list -- list of point tuples [(x0, y0), (x1, y1), (x2, y2), ...]
gjc@3408
   173
                   (Unclosed polygons will be closed automatically.
gjc@3408
   174
    precision -- Internal arithmetic precision (integer arithmetic).
gjc@3408
   175
gjc@3408
   176
    >>> polygon_area([(0, 0), (0, 1), (1, 1), (1, 2), (2, 2), (2, 0), (0, 0)])
gjc@3408
   177
    3.0
gjc@3408
   178
gjc@3408
   179
    Credits:
gjc@3408
   180
    Area of a General Polygon by David Chandler
gjc@3408
   181
    http://www.davidchandler.com/AreaOfAGeneralPolygon.pdf
gjc@3408
   182
    
gjc@3408
   183
    """
gjc@3408
   184
    # Scale up co-ordinates and convert them to integers.
gjc@3408
   185
    for i in range(len(points_list)):
gjc@3408
   186
        points_list[i] = (int(points_list[i][0] * precision),
gjc@3408
   187
                          int(points_list[i][1] * precision))
gjc@3408
   188
    # Close polygon if not closed.
gjc@3408
   189
    if points_list[-1] != points_list[0]:
gjc@3408
   190
        points_list.append(points_list[0])
gjc@3408
   191
    # Calculate area.
gjc@3408
   192
    area = 0
gjc@3408
   193
    for i in range(len(points_list)-1):
gjc@3408
   194
        (x_i, y_i) = points_list[i]
gjc@3408
   195
        (x_i_plus_1, y_i_plus_1) = points_list[i+1]
gjc@3408
   196
        area = area + (x_i_plus_1 * y_i) - (y_i_plus_1 * x_i)
gjc@3408
   197
    area = abs(area / 2)
gjc@3408
   198
    # Unscale area.
gjc@3408
   199
    area = float(area)/(precision**2)
gjc@3408
   200
    return area
gjc@3408
   201
gjc@3408
   202
gjc@3408
   203
def timestamp():
gjc@3408
   204
    """Return string containing current time stamp.
gjc@3408
   205
gjc@3408
   206
    Note: In Python 2 onwards can use time.asctime() with no arguments.
gjc@3408
   207
gjc@3408
   208
    """
gjc@3408
   209
gjc@3408
   210
    return time.asctime()
gjc@3408
   211
gjc@3408
   212
gjc@3408
   213
def pt2str(point):
gjc@3408
   214
    """Return prettier string version of point tuple.
gjc@3408
   215
gjc@3408
   216
    >>> pt2str((1.8, 1.9))
gjc@3408
   217
    '(1.8, 1.9)'
gjc@3408
   218
gjc@3408
   219
    """
gjc@3408
   220
    return "(%s, %s)" % (str(point[0]), str(point[1]))
gjc@3408
   221
gjc@3408
   222
gjc@3408
   223
def gcf(a, b, epsilon=1e-16):
gjc@3408
   224
    """Return the greatest common factor of a and b, using Euclidean algorithm.
gjc@3408
   225
gjc@3408
   226
    Arguments:
gjc@3408
   227
    a, b -- two numbers
gjc@3408
   228
            If both numbers are integers return an integer result, 
gjc@3408
   229
            otherwise return a float result.
gjc@3408
   230
    epsilon -- floats less than this magnitude are considered to be zero
gjc@3408
   231
               (default: 1e-16)
gjc@3408
   232
gjc@3408
   233
    Examples:
gjc@3408
   234
gjc@3408
   235
    >>> gcf(12, 34)
gjc@3408
   236
    2
gjc@3408
   237
gjc@3408
   238
    >>> gcf(13.5, 4)
gjc@3408
   239
    0.5
gjc@3408
   240
gjc@3408
   241
    >>> gcf(-2, 4)
gjc@3408
   242
    2
gjc@3408
   243
gjc@3408
   244
    >>> gcf(5, 0)
gjc@3408
   245
    5
gjc@3408
   246
gjc@3408
   247
    By (a convenient) definition:
gjc@3408
   248
    >>> gcf(0, 0)
gjc@3408
   249
    0
gjc@3408
   250
gjc@3408
   251
    """
gjc@3408
   252
    result = max(a, b)
gjc@3408
   253
    remainder = min(a, b)
gjc@3408
   254
    while remainder and abs(remainder) > epsilon:
gjc@3408
   255
        new_remainder = result % remainder
gjc@3408
   256
        result = remainder
gjc@3408
   257
        remainder = new_remainder
gjc@3408
   258
    return abs(result)
gjc@3408
   259
gjc@3408
   260
def lcm(a, b, precision=None):
gjc@3408
   261
    """Return the least common multiple of a and b, using the gcf function.
gjc@3408
   262
gjc@3408
   263
    Arguments:
gjc@3408
   264
    a, b -- two numbers. If both are integers return an integer result, 
gjc@3408
   265
            otherwise a return a float result.
gjc@3408
   266
    precision -- scaling factor if a and/or b are floats.
gjc@3408
   267
gjc@3408
   268
    >>> lcm(21, 6)
gjc@3408
   269
    42
gjc@3408
   270
gjc@3408
   271
    >>> lcm(2.5, 3.5)
gjc@3408
   272
    17.5
gjc@3408
   273
gjc@3408
   274
    >>> str(lcm(1.5e-8, 2.5e-8, precision=1e9))
gjc@3408
   275
    '7.5e-08'
gjc@3408
   276
gjc@3408
   277
    By (an arbitary) definition:
gjc@3408
   278
    >>> lcm(0, 0)
gjc@3408
   279
    0
gjc@3408
   280
gjc@3408
   281
    """
gjc@3408
   282
    # Note: Dummy precision argument is for backwards compatibility.
gjc@3408
   283
    # Do the division first.
gjc@3408
   284
    # (See http://en.wikipedia.org/wiki/Least_common_multiple )
gjc@3408
   285
    denom = gcf(a, b)
gjc@3408
   286
    if denom == 0:
gjc@3408
   287
        result = 0
gjc@3408
   288
    else:
gjc@3408
   289
        result = a * (b / denom)
gjc@3408
   290
    return result
gjc@3408
   291
gjc@3408
   292
gjc@3408
   293
def permutations(input_list):
gjc@3408
   294
    """Return a list containing all permutations of the input list.
gjc@3408
   295
gjc@3408
   296
    Note: This is a recursive function.
gjc@3408
   297
gjc@3408
   298
    >>> perms = permutations(['a', 'b', 'c'])
gjc@3408
   299
    >>> perms.sort()
gjc@3408
   300
    >>> for perm in perms:
gjc@3408
   301
    ...     print perm
gjc@3408
   302
    ['a', 'b', 'c']
gjc@3408
   303
    ['a', 'c', 'b']
gjc@3408
   304
    ['b', 'a', 'c']
gjc@3408
   305
    ['b', 'c', 'a']
gjc@3408
   306
    ['c', 'a', 'b']
gjc@3408
   307
    ['c', 'b', 'a']
gjc@3408
   308
gjc@3408
   309
    """
gjc@3408
   310
    out_lists = []
gjc@3408
   311
    if len(input_list) > 1:
gjc@3408
   312
        # Extract first item in list.
gjc@3408
   313
        item = input_list[0]
gjc@3408
   314
        # Find all permutations of remainder of list. (Recursive call.)
gjc@3408
   315
        sub_lists = permutations(input_list[1:])
gjc@3408
   316
        # For every permutation of the sub list...
gjc@3408
   317
        for sub_list in sub_lists:
gjc@3408
   318
            # Insert the extracted first item at every position of the list.
gjc@3408
   319
            for i in range(len(input_list)):
gjc@3408
   320
                new_list = sub_list[:]
gjc@3408
   321
                new_list.insert(i, item)
gjc@3408
   322
                out_lists.append(new_list)
gjc@3408
   323
    else:
gjc@3408
   324
        # Termination condition: only one item in input list.
gjc@3408
   325
        out_lists = [input_list]
gjc@3408
   326
    return out_lists
gjc@3408
   327
gjc@3408
   328
gjc@3408
   329
def reduce_fraction(fraction):
gjc@3408
   330
    """Reduce fraction tuple to simplest form. fraction=(num, denom)
gjc@3408
   331
    
gjc@3408
   332
    >>> reduce_fraction((14, 7))
gjc@3408
   333
    (2, 1)
gjc@3408
   334
gjc@3408
   335
    >>> reduce_fraction((-2, 4))
gjc@3408
   336
    (-1, 2)
gjc@3408
   337
gjc@3408
   338
    >>> reduce_fraction((0, 4))
gjc@3408
   339
    (0, 1)
gjc@3408
   340
gjc@3408
   341
    >>> reduce_fraction((4, 0))
gjc@3408
   342
    (1, 0)
gjc@3408
   343
    
gjc@3408
   344
    """
gjc@3408
   345
    (numerator, denominator) = fraction
gjc@3408
   346
    common_factor = abs(gcf(numerator, denominator))
gjc@3408
   347
    result = (numerator/common_factor, denominator/common_factor)
gjc@3408
   348
    return result
gjc@3408
   349
gjc@3408
   350
gjc@3408
   351
def quantile(l, p):
gjc@3408
   352
    """Return p quantile of list l. E.g. p=0.25 for q1.
gjc@3408
   353
gjc@3408
   354
    See:
gjc@3408
   355
    http://rweb.stat.umn.edu/R/library/base/html/quantile.html
gjc@3408
   356
gjc@3408
   357
    """
gjc@3408
   358
    l_sort = l[:]
gjc@3408
   359
    l_sort.sort()
gjc@3408
   360
    n = len(l)
gjc@3408
   361
    r = 1 + ((n - 1) * p)
gjc@3408
   362
    i = int(r)
gjc@3408
   363
    f = r - i
gjc@3408
   364
    if i < n:
gjc@3408
   365
        result =  (1-f)*l_sort[i-1] + f*l_sort[i]
gjc@3408
   366
    else:
gjc@3408
   367
        result = l_sort[i-1]
gjc@3408
   368
    return result
gjc@3408
   369
gjc@3408
   370
gjc@3408
   371
def trim(l):
gjc@3408
   372
    """Discard values in list more than 1.5*IQR outside IQR.
gjc@3408
   373
gjc@3408
   374
    (IQR is inter-quartile-range)
gjc@3408
   375
gjc@3408
   376
    This function uses rad_util.quantile
gjc@3408
   377
gjc@3408
   378
    1.5*IQR -- mild outlier
gjc@3408
   379
    3*IQR -- extreme outlier
gjc@3408
   380
gjc@3408
   381
    See:
gjc@3408
   382
    http://wind.cc.whecn.edu/~pwildman/statnew/section_7_-_exploratory_data_analysis.htm
gjc@3408
   383
gjc@3408
   384
    """
gjc@3408
   385
    l_sort = l[:]
gjc@3408
   386
    l_sort.sort()
gjc@3408
   387
    # Calculate medianscore  (based on stats.py lmedianscore by Gary Strangman)
gjc@3408
   388
    if len(l_sort) % 2 == 0:
gjc@3408
   389
        # If even number of scores, average middle 2.
gjc@3408
   390
        index = int(len(l_sort) / 2)  # Integer division correct
gjc@3408
   391
        median = float(l_sort[index] + l_sort[index-1]) / 2
gjc@3408
   392
    else:
gjc@3408
   393
        # int divsion gives mid value when count from 0
gjc@3408
   394
        index = int(len(l_sort) / 2)
gjc@3408
   395
        median = l_sort[index]
gjc@3408
   396
    # Calculate IQR.
gjc@3408
   397
    q1 = quantile(l_sort, 0.25)
gjc@3408
   398
    q3 = quantile(l_sort, 0.75)
gjc@3408
   399
    iqr = q3 - q1
gjc@3408
   400
    iqr_extra = iqr * 1.5
gjc@3408
   401
    def in_interval(x, i=iqr_extra, q1=q1, q3=q3):
gjc@3408
   402
        return (x >= q1-i and x <= q3+i)
gjc@3408
   403
    l_trimmed = [x for x in l_sort if in_interval(x)]
gjc@3408
   404
    return l_trimmed
gjc@3408
   405
gjc@3408
   406
gjc@3408
   407
def nice_units(value, dp=0, sigfigs=None, suffix='', space=' ',
gjc@3408
   408
               use_extra_prefixes=False, use_full_name=False, mode='si'):
gjc@3408
   409
    """Return value converted to human readable units eg milli, micro, etc.
gjc@3408
   410
gjc@3408
   411
    Arguments:
gjc@3408
   412
    value -- number in base units
gjc@3408
   413
    dp -- number of decimal places to display (rounded)
gjc@3408
   414
    sigfigs -- number of significant figures to display (rounded)
gjc@3408
   415
               This overrides dp if set.
gjc@3408
   416
    suffix -- optional unit suffix to append to unit multiplier
gjc@3408
   417
    space -- seperator between value and unit multiplier (default: ' ')
gjc@3408
   418
    use_extra_prefixes -- use hecto, deka, deci and centi as well if set.
gjc@3408
   419
                          (default: False)
gjc@3408
   420
    use_full_name -- use full name for multiplier symbol,
gjc@3408
   421
                     e.g. milli instead of m
gjc@3408
   422
                     (default: False)
gjc@3408
   423
    mode -- 'si' for SI prefixes, 'bin' for binary multipliers (1024, etc.)
gjc@3408
   424
            (Default: 'si')
gjc@3408
   425
gjc@3408
   426
    SI prefixes from:
gjc@3408
   427
    http://physics.nist.gov/cuu/Units/prefixes.html
gjc@3408
   428
    (Greek mu changed to u.)
gjc@3408
   429
    Binary prefixes based on:
gjc@3408
   430
    http://physics.nist.gov/cuu/Units/binary.html
gjc@3408
   431
gjc@3408
   432
    >>> nice_units(2e-11)
gjc@3408
   433
    '20 p'
gjc@3408
   434
gjc@3408
   435
    >>> nice_units(2e-11, space='')
gjc@3408
   436
    '20p'
gjc@3408
   437
gjc@3408
   438
    """
gjc@3408
   439
    si_prefixes = {1e24:  ('Y', 'yotta'),
gjc@3408
   440
                   1e21:  ('Z', 'zetta'),
gjc@3408
   441
                   1e18:  ('E', 'exa'),
gjc@3408
   442
                   1e15:  ('P', 'peta'),
gjc@3408
   443
                   1e12:  ('T', 'tera'),
gjc@3408
   444
                   1e9:   ('G', 'giga'),
gjc@3408
   445
                   1e6:   ('M', 'mega'),
gjc@3408
   446
                   1e3:   ('k', 'kilo'),
gjc@3408
   447
                   1e-3:  ('m', 'milli'),
gjc@3408
   448
                   1e-6:  ('u', 'micro'),
gjc@3408
   449
                   1e-9:  ('n', 'nano'),
gjc@3408
   450
                   1e-12: ('p', 'pico'),
gjc@3408
   451
                   1e-15: ('f', 'femto'),
gjc@3408
   452
                   1e-18: ('a', 'atto'),
gjc@3408
   453
                   1e-21: ('z', 'zepto'),
gjc@3408
   454
                   1e-24: ('y', 'yocto')
gjc@3408
   455
                   }
gjc@3408
   456
    if use_extra_prefixes:
gjc@3408
   457
        si_prefixes.update({1e2:  ('h', 'hecto'),
gjc@3408
   458
                            1e1:  ('da', 'deka'),
gjc@3408
   459
                            1e-1: ('d', 'deci'),
gjc@3408
   460
                            1e-2: ('c', 'centi')
gjc@3408
   461
                            })
gjc@3408
   462
    bin_prefixes = {2**10: ('K', 'kilo'),
gjc@3408
   463
                    2**20: ('M', 'mega'),
gjc@3408
   464
                    2**30: ('G', 'mega'),
gjc@3408
   465
                    2**40: ('T', 'tera'),
gjc@3408
   466
                    2**50: ('P', 'peta'),
gjc@3408
   467
                    2**60: ('E', 'exa')
gjc@3408
   468
                    }
gjc@3408
   469
    if mode == 'bin':
gjc@3408
   470
        prefixes = bin_prefixes
gjc@3408
   471
    else:
gjc@3408
   472
        prefixes = si_prefixes
gjc@3408
   473
    prefixes[1] = ('', '')  # Unity.
gjc@3408
   474
    # Determine appropriate multiplier.
gjc@3408
   475
    multipliers = prefixes.keys()
gjc@3408
   476
    multipliers.sort()
gjc@3408
   477
    mult = None
gjc@3408
   478
    for i in range(len(multipliers) - 1):
gjc@3408
   479
        lower_mult = multipliers[i]
gjc@3408
   480
        upper_mult = multipliers[i+1]
gjc@3408
   481
        if lower_mult <= value < upper_mult:
gjc@3408
   482
            mult_i = i
gjc@3408
   483
            break
gjc@3408
   484
    if mult is None:
gjc@3408
   485
        if value < multipliers[0]:
gjc@3408
   486
            mult_i = 0
gjc@3408
   487
        elif value >= multipliers[-1]:
gjc@3408
   488
            mult_i = len(multipliers) - 1
gjc@3408
   489
    mult = multipliers[mult_i]
gjc@3408
   490
    # Convert value for this multiplier.
gjc@3408
   491
    new_value = value / mult
gjc@3408
   492
    # Deal with special case due to rounding.
gjc@3408
   493
    if sigfigs is None:
gjc@3408
   494
        if mult_i < (len(multipliers) - 1) and \
gjc@3408
   495
               round(new_value, dp) == \
gjc@3408
   496
               round((multipliers[mult_i+1] / mult), dp):
gjc@3408
   497
            mult = multipliers[mult_i + 1]
gjc@3408
   498
            new_value = value / mult
gjc@3408
   499
    # Concatenate multiplier symbol.
gjc@3408
   500
    if use_full_name:
gjc@3408
   501
        label_type = 1
gjc@3408
   502
    else:
gjc@3408
   503
        label_type = 0
gjc@3408
   504
    # Round and truncate to appropriate precision.
gjc@3408
   505
    if sigfigs is None:
gjc@3408
   506
        str_value = eval('"%.'+str(dp)+'f" % new_value', locals(), {})
gjc@3408
   507
    else:
gjc@3408
   508
        str_value = eval('"%.'+str(sigfigs)+'g" % new_value', locals(), {})
gjc@3408
   509
    return str_value + space + prefixes[mult][label_type] + suffix
gjc@3408
   510
gjc@3408
   511
gjc@3408
   512
def uniquify(seq, preserve_order=False):
gjc@3408
   513
    """Return sequence with duplicate items in sequence seq removed.
gjc@3408
   514
gjc@3408
   515
    The code is based on usenet post by Tim Peters.
gjc@3408
   516
gjc@3408
   517
    This code is O(N) if the sequence items are hashable, O(N**2) if not.
gjc@3408
   518
    
gjc@3408
   519
    Peter Bengtsson has a blog post with an empirical comparison of other
gjc@3408
   520
    approaches:
gjc@3408
   521
    http://www.peterbe.com/plog/uniqifiers-benchmark
gjc@3408
   522
gjc@3408
   523
    If order is not important and the sequence items are hashable then
gjc@3408
   524
    list(set(seq)) is readable and efficient.
gjc@3408
   525
gjc@3408
   526
    If order is important and the sequence items are hashable generator
gjc@3408
   527
    expressions can be used (in py >= 2.4) (useful for large sequences):
gjc@3408
   528
    seen = set()
gjc@3408
   529
    do_something(x for x in seq if x not in seen or seen.add(x))
gjc@3408
   530
gjc@3408
   531
    Arguments:
gjc@3408
   532
    seq -- sequence
gjc@3408
   533
    preserve_order -- if not set the order will be arbitrary
gjc@3408
   534
                      Using this option will incur a speed penalty.
gjc@3408
   535
                      (default: False)
gjc@3408
   536
gjc@3408
   537
    Example showing order preservation:
gjc@3408
   538
gjc@3408
   539
    >>> uniquify(['a', 'aa', 'b', 'b', 'ccc', 'ccc', 'd'], preserve_order=True)
gjc@3408
   540
    ['a', 'aa', 'b', 'ccc', 'd']
gjc@3408
   541
gjc@3408
   542
    Example using a sequence of un-hashable items:
gjc@3408
   543
gjc@3408
   544
    >>> uniquify([['z'], ['x'], ['y'], ['z']], preserve_order=True)
gjc@3408
   545
    [['z'], ['x'], ['y']]
gjc@3408
   546
gjc@3408
   547
    The sorted output or the non-order-preserving approach should equal
gjc@3408
   548
    that of the sorted order-preserving approach output:
gjc@3408
   549
    
gjc@3408
   550
    >>> unordered = uniquify([3, 3, 1, 2], preserve_order=False)
gjc@3408
   551
    >>> unordered.sort()
gjc@3408
   552
    >>> ordered = uniquify([3, 3, 1, 2], preserve_order=True)
gjc@3408
   553
    >>> ordered.sort()
gjc@3408
   554
    >>> ordered
gjc@3408
   555
    [1, 2, 3]
gjc@3408
   556
    >>> int(ordered == unordered)
gjc@3408
   557
    1
gjc@3408
   558
gjc@3408
   559
    """
gjc@3408
   560
    try:
gjc@3408
   561
        # Attempt fast algorithm.
gjc@3408
   562
        d = {}
gjc@3408
   563
        if preserve_order:
gjc@3408
   564
            # This is based on Dave Kirby's method (f8) noted in the post:
gjc@3408
   565
            # http://www.peterbe.com/plog/uniqifiers-benchmark
gjc@3408
   566
            return [x for x in seq if (x not in d) and not d.__setitem__(x, 0)]
gjc@3408
   567
        else:
gjc@3408
   568
            for x in seq:
gjc@3408
   569
                d[x] = 0
gjc@3408
   570
            return d.keys()
gjc@3408
   571
    except TypeError:
gjc@3408
   572
        # Have an unhashable object, so use slow algorithm.
gjc@3408
   573
        result = []
gjc@3408
   574
        app = result.append
gjc@3408
   575
        for x in seq:
gjc@3408
   576
            if x not in result:
gjc@3408
   577
                app(x)
gjc@3408
   578
        return result
gjc@3408
   579
gjc@3408
   580
# Alias to noun form for backward compatibility.
gjc@3408
   581
unique = uniquify
gjc@3408
   582
gjc@3408
   583
gjc@3408
   584
def reverse_dict(d):
gjc@3408
   585
    """Reverse a dictionary so the items become the keys and vice-versa.
gjc@3408
   586
gjc@3408
   587
    Note: The results will be arbitrary if the items are not unique.
gjc@3408
   588
gjc@3408
   589
    >>> d = reverse_dict({'a': 1, 'b': 2})
gjc@3408
   590
    >>> d_items = d.items()
gjc@3408
   591
    >>> d_items.sort()
gjc@3408
   592
    >>> d_items
gjc@3408
   593
    [(1, 'a'), (2, 'b')]
gjc@3408
   594
gjc@3408
   595
    """
gjc@3408
   596
    result = {}
gjc@3408
   597
    for key, value in d.items():
gjc@3408
   598
        result[value] = key
gjc@3408
   599
    return result
gjc@3408
   600
gjc@3408
   601
    
gjc@3408
   602
def lsb(x, n):
gjc@3408
   603
    """Return the n least significant bits of x.
gjc@3408
   604
gjc@3408
   605
    >>> lsb(13, 3)
gjc@3408
   606
    5
gjc@3408
   607
gjc@3408
   608
    """
gjc@3408
   609
    return x & ((2 ** n) - 1)
gjc@3408
   610
gjc@3408
   611
gjc@3408
   612
def gray_encode(i):
gjc@3408
   613
    """Gray encode the given integer."""
gjc@3408
   614
gjc@3408
   615
    return i ^ (i >> 1)
gjc@3408
   616
gjc@3408
   617
gjc@3408
   618
def random_vec(bits, max_value=None):
gjc@3408
   619
    """Generate a random binary vector of length bits and given max value."""
gjc@3408
   620
gjc@3408
   621
    vector = ""
gjc@3408
   622
    for _ in range(int(bits / 10) + 1):
gjc@3408
   623
        i = int((2**10) * random.random())
gjc@3408
   624
        vector += int2bin(i, 10)
gjc@3408
   625
gjc@3408
   626
    if max_value and (max_value < 2 ** bits - 1):
gjc@3408
   627
        vector = int2bin((int(vector, 2) / (2 ** bits - 1)) * max_value, bits)
gjc@3408
   628
    
gjc@3408
   629
    return vector[0:bits]
gjc@3408
   630
gjc@3408
   631
gjc@3408
   632
def binary_range(bits):
gjc@3408
   633
    """Return a list of all possible binary numbers in order with width=bits. 
gjc@3408
   634
    
gjc@3408
   635
    It would be nice to extend it to match the
gjc@3408
   636
    functionality of python's range() built-in function.
gjc@3408
   637
    
gjc@3408
   638
    """
gjc@3408
   639
    l = []
gjc@3408
   640
    v = ['0'] * bits
gjc@3408
   641
gjc@3408
   642
    toggle = [1] + [0] * bits
gjc@3408
   643
    
gjc@3408
   644
    while toggle[bits] != 1:
gjc@3408
   645
        v_copy = v[:]
gjc@3408
   646
        v_copy.reverse()
gjc@3408
   647
        l.append(''.join(v_copy))
gjc@3408
   648
        
gjc@3408
   649
        toggle = [1] + [0]*bits
gjc@3408
   650
        i = 0
gjc@3408
   651
        while i < bits and toggle[i] == 1:
gjc@3408
   652
            if toggle[i]:
gjc@3408
   653
                if v[i] == '0':
gjc@3408
   654
                    v[i] = '1'
gjc@3408
   655
                    toggle[i+1] = 0
gjc@3408
   656
                else:
gjc@3408
   657
                    v[i] = '0'
gjc@3408
   658
                    toggle[i+1] = 1
gjc@3408
   659
            i += 1
gjc@3408
   660
    return l
gjc@3408
   661
gjc@3408
   662
gjc@3408
   663
def float_range(start, stop=None, step=None):
gjc@3408
   664
    """Return a list containing an arithmetic progression of floats.
gjc@3408
   665
gjc@3408
   666
    Return a list of floats between 0.0 (or start) and stop with an
gjc@3408
   667
    increment of step. 
gjc@3408
   668
gjc@3408
   669
    This is in functionality to python's range() built-in function 
gjc@3408
   670
    but can accept float increments.
gjc@3408
   671
gjc@3408
   672
    As with range(), stop is omitted from the list.
gjc@3408
   673
gjc@3408
   674
    """
gjc@3408
   675
    if stop is None:
gjc@3408
   676
        stop = float(start)
gjc@3408
   677
        start = 0.0
gjc@3408
   678
gjc@3408
   679
    if step is None:
gjc@3408
   680
        step = 1.0
gjc@3408
   681
gjc@3408
   682
    cur = float(start)
gjc@3408
   683
    l = []
gjc@3408
   684
    while cur < stop:
gjc@3408
   685
        l.append(cur)
gjc@3408
   686
        cur += step
gjc@3408
   687
gjc@3408
   688
    return l
gjc@3408
   689
gjc@3408
   690
gjc@3408
   691
def find_common_fixes(s1, s2):
gjc@3408
   692
    """Find common (prefix, suffix) of two strings.
gjc@3408
   693
gjc@3408
   694
    >>> find_common_fixes('abc', 'def')
gjc@3408
   695
    ('', '')
gjc@3408
   696
gjc@3408
   697
    >>> find_common_fixes('abcelephantdef', 'abccowdef')
gjc@3408
   698
    ('abc', 'def')
gjc@3408
   699
gjc@3408
   700
    >>> find_common_fixes('abcelephantdef', 'abccow')
gjc@3408
   701
    ('abc', '')
gjc@3408
   702
gjc@3408
   703
    >>> find_common_fixes('elephantdef', 'abccowdef')
gjc@3408
   704
    ('', 'def')
gjc@3408
   705
gjc@3408
   706
    """
gjc@3408
   707
    prefix = []
gjc@3408
   708
    suffix = []
gjc@3408
   709
gjc@3408
   710
    i = 0
gjc@3408
   711
    common_len = min(len(s1), len(s2))
gjc@3408
   712
    while i < common_len:
gjc@3408
   713
        if s1[i] != s2[i]:
gjc@3408
   714
            break
gjc@3408
   715
gjc@3408
   716
        prefix.append(s1[i])
gjc@3408
   717
        i += 1
gjc@3408
   718
gjc@3408
   719
    i = 1
gjc@3408
   720
    while i < (common_len + 1):
gjc@3408
   721
        if s1[-i] != s2[-i]:
gjc@3408
   722
            break
gjc@3408
   723
        
gjc@3408
   724
        suffix.append(s1[-i])
gjc@3408
   725
        i += 1
gjc@3408
   726
gjc@3408
   727
    suffix.reverse()
gjc@3408
   728
gjc@3408
   729
    prefix = ''.join(prefix)
gjc@3408
   730
    suffix = ''.join(suffix)
gjc@3408
   731
        
gjc@3408
   732
    return (prefix, suffix)
gjc@3408
   733
gjc@3408
   734
gjc@3408
   735
def is_rotated(seq1, seq2):
gjc@3408
   736
    """Return true if the first sequence is a rotation of the second sequence.
gjc@3408
   737
gjc@3408
   738
    >>> seq1 = ['A', 'B', 'C', 'D']
gjc@3408
   739
    >>> seq2 = ['C', 'D', 'A', 'B']
gjc@3408
   740
    >>> int(is_rotated(seq1, seq2))
gjc@3408
   741
    1
gjc@3408
   742
gjc@3408
   743
    >>> seq2 = ['C', 'D', 'B', 'A']
gjc@3408
   744
    >>> int(is_rotated(seq1, seq2))
gjc@3408
   745
    0
gjc@3408
   746
gjc@3408
   747
    >>> seq1 = ['A', 'B', 'C', 'A']
gjc@3408
   748
    >>> seq2 = ['A', 'A', 'B', 'C']
gjc@3408
   749
    >>> int(is_rotated(seq1, seq2))
gjc@3408
   750
    1
gjc@3408
   751
gjc@3408
   752
    >>> seq2 = ['A', 'B', 'C', 'A']
gjc@3408
   753
    >>> int(is_rotated(seq1, seq2))
gjc@3408
   754
    1
gjc@3408
   755
gjc@3408
   756
    >>> seq2 = ['A', 'A', 'C', 'B']
gjc@3408
   757
    >>> int(is_rotated(seq1, seq2))
gjc@3408
   758
    0
gjc@3408
   759
gjc@3408
   760
    """
gjc@3408
   761
    # Do a sanity check.
gjc@3408
   762
    if len(seq1) != len(seq2):
gjc@3408
   763
        return False
gjc@3408
   764
    # Look for occurrences of second sequence head item in first sequence.
gjc@3408
   765
    start_indexes = []
gjc@3408
   766
    head_item = seq2[0]
gjc@3408
   767
    for index1 in range(len(seq1)):
gjc@3408
   768
        if seq1[index1] == head_item:
gjc@3408
   769
            start_indexes.append(index1)
gjc@3408
   770
    # Check that wrapped sequence matches.
gjc@3408
   771
    double_seq1 = seq1 + seq1
gjc@3408
   772
    for index1 in start_indexes:
gjc@3408
   773
        if double_seq1[index1:index1+len(seq1)] == seq2:
gjc@3408
   774
            return True
gjc@3408
   775
    return False
gjc@3408
   776
gjc@3408
   777
def getmodule(obj):
gjc@3408
   778
    """Return the module that contains the object definition of obj.
gjc@3408
   779
gjc@3408
   780
    Note: Use inspect.getmodule instead.
gjc@3408
   781
gjc@3408
   782
    Arguments:
gjc@3408
   783
    obj -- python obj, generally a class or a function
gjc@3408
   784
gjc@3408
   785
    Examples:
gjc@3408
   786
    
gjc@3408
   787
    A function:
gjc@3408
   788
    >>> module = getmodule(random.choice)
gjc@3408
   789
    >>> module.__name__
gjc@3408
   790
    'random'
gjc@3408
   791
    >>> module is random
gjc@3408
   792
    1
gjc@3408
   793
gjc@3408
   794
    A class:
gjc@3408
   795
    >>> module = getmodule(random.Random)
gjc@3408
   796
    >>> module.__name__
gjc@3408
   797
    'random'
gjc@3408
   798
    >>> module is random
gjc@3408
   799
    1
gjc@3408
   800
gjc@3408
   801
    A class inheriting from a class in another module:
gjc@3408
   802
    (note: The inheriting class must define at least one function.)
gjc@3408
   803
    >>> class MyRandom(random.Random):
gjc@3408
   804
    ...     def play(self):
gjc@3408
   805
    ...         pass
gjc@3408
   806
    >>> module = getmodule(MyRandom)
gjc@3408
   807
    >>> if __name__ == '__main__':
gjc@3408
   808
    ...     name = 'rad_util'
gjc@3408
   809
    ... else:
gjc@3408
   810
    ...     name = module.__name__
gjc@3408
   811
    >>> name
gjc@3408
   812
    'rad_util'
gjc@3408
   813
    >>> module is sys.modules[__name__]
gjc@3408
   814
    1
gjc@3408
   815
gjc@3408
   816
    Discussion:
gjc@3408
   817
    This approach is slightly hackish, and won't work in various situations.
gjc@3408
   818
    However, this was the approach recommended by GvR, so it's as good as
gjc@3408
   819
    you'll get.
gjc@3408
   820
gjc@3408
   821
    See GvR's post in this thread:
gjc@3408
   822
    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
   823
    
gjc@3408
   824
    """
gjc@3408
   825
    if hasattr(obj, 'func_globals'):
gjc@3408
   826
        func = obj
gjc@3408
   827
    else:
gjc@3408
   828
        # Handle classes.
gjc@3408
   829
        func = None
gjc@3408
   830
        for item in obj.__dict__.values():
gjc@3408
   831
            if hasattr(item, 'func_globals'):
gjc@3408
   832
                func = item
gjc@3408
   833
                break
gjc@3408
   834
        if func is None:
gjc@3408
   835
            raise ValueError("No functions attached to object: %r" % obj)
gjc@3408
   836
    module_name = func.func_globals['__name__']
gjc@3408
   837
    # Get module.
gjc@3408
   838
    module = sys.modules[module_name]
gjc@3408
   839
    return module
gjc@3408
   840
gjc@3408
   841
gjc@3408
   842
def round_grid(value, grid, mode=0):
gjc@3408
   843
    """Round off the given value to the given grid size.
gjc@3408
   844
gjc@3408
   845
    Arguments:
gjc@3408
   846
    value -- value to be roudne
gjc@3408
   847
    grid -- result must be a multiple of this
gjc@3408
   848
    mode -- 0 nearest, 1 up, -1 down
gjc@3408
   849
gjc@3408
   850
    Examples:
gjc@3408
   851
    
gjc@3408
   852
    >>> round_grid(7.5, 5)
gjc@3408
   853
    10
gjc@3408
   854
gjc@3408
   855
    >>> round_grid(7.5, 5, mode=-1)
gjc@3408
   856
    5
gjc@3408
   857
gjc@3408
   858
    >>> round_grid(7.3, 5, mode=1)
gjc@3408
   859
    10
gjc@3408
   860
gjc@3408
   861
    >>> round_grid(7.3, 5.0, mode=1)
gjc@3408
   862
    10.0
gjc@3408
   863
gjc@3408
   864
    """
gjc@3408
   865
    off_grid = value % grid
gjc@3408
   866
    if mode == 0:
gjc@3408
   867
        add_one = int(off_grid >= (grid / 2.0))
gjc@3408
   868
    elif mode == 1 and off_grid:
gjc@3408
   869
        add_one = 1
gjc@3408
   870
    elif mode == -1 and off_grid:
gjc@3408
   871
        add_one = 0
gjc@3408
   872
    result = ((int(value / grid) + add_one) * grid)
gjc@3408
   873
    return result
gjc@3408
   874
gjc@3408
   875
gjc@3408
   876
def get_args(argv):
gjc@3408
   877
    """Store command-line args in a dictionary.
gjc@3408
   878
    
gjc@3408
   879
    -, -- prefixes are removed
gjc@3408
   880
    Items not prefixed with - or -- are stored as a list, indexed by 'args'
gjc@3408
   881
gjc@3408
   882
    For options that take a value use --option=value
gjc@3408
   883
gjc@3408
   884
    Consider using optparse or getopt (in Python standard library) instead.
gjc@3408
   885
gjc@3408
   886
    """
gjc@3408
   887
    d = {}
gjc@3408
   888
    args = []
gjc@3408
   889
    
gjc@3408
   890
    for arg in argv:
gjc@3408
   891
            
gjc@3408
   892
        if arg.startswith('-'):
gjc@3408
   893
            parts = re.sub(r'^-+', '', arg).split('=')
gjc@3408
   894
            if len(parts) == 2:
gjc@3408
   895
                d[parts[0]] = parts[1]
gjc@3408
   896
            else:
gjc@3408
   897
                d[parts[0]] = None
gjc@3408
   898
        else:
gjc@3408
   899
            args.append(arg)
gjc@3408
   900
gjc@3408
   901
    d['args'] = args
gjc@3408
   902
    
gjc@3408
   903
    return d
gjc@3408
   904
gjc@3408
   905
gjc@3408
   906
if __name__ == '__main__':
gjc@3408
   907
    import doctest
gjc@3408
   908
    doctest.testmod(sys.modules['__main__'])
gjc@3408
   909