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
     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