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