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