spiffyscore

Check-in [689adc054e]
Login
Overview
Comment:Program generates a render order for the instruments based on their sync order
Timelines: family | ancestors | descendants | both | master
Files: files | file ages | folders
SHA1:689adc054e647b134f3ebf9291e5c2b45aeb8542
User & Date: brian@linux-85dd.site on 2011-02-10 23:50:20
Other Links: manifest | tags
Context
2011-06-12
20:32
Made some changes to the parser. Don't remember what. Leaf check-in: 87435601e4 user: brian tags: master
20:31
Create new branch named "develop" check-in: 9f4c4666c5 user: brian tags: develop
2011-02-10
23:50
Program generates a render order for the instruments based on their sync order check-in: 689adc054e user: brian@linux-85dd.site tags: master
22:34
Added lexical support for parens instead of quotes for chords, cleaned up the yacc parser, added lex tokens for syncopation check-in: 702d933446 user: brian@linux-85dd.site tags: master
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Modified cfg.py from [82bf7ad059] to [e9b556b4f3].

     2      2   
     3      3   from __future__ import division
     4      4   import os
     5      5   import random
     6      6   import sys
     7      7   import time
     8      8   random.seed(time.time())
            9  +
     9     10   import parse
           11  +import topsort
           12  +import yaml
    10     13   
    11     14   def main():
    12     15       key = "A"
    13     16       bps = 60/60
    14     17       tempo = 1/bps
    15     18       max_duration = 1
    16     19   
    17         -    composition = {
    18         -        "overview": {
    19         -            "melody": {  # Instrument 'melody'
    20         -                "score_line": "i2 %(time)f %(duration)f 7000 %(octave)d.%(note)s 2",
    21         -                "octave": 8,
    22         -                "duration": 40,
    23         -                "grammars": {  # Notes for this instrument to use in this piece
    24         -                    "u": ["I V/2 V/2 V/2 I VII, IV' I IV I VII IV"],
    25         -                },
    26         -                "score": "u",
    27         -            },
    28         -            "rhythm": {
    29         -                "score_line": "i1 %(time)f %(duration)f 7000 %(octave)d.%(note)s %(octave)d.%(note)s 0 6",
    30         -                "octave": 7,
    31         -                "duration": 44,
    32         -                "grammars": {
    33         -                    "u": ['(I) (ii)/4 (ii)/4 (IV)/2 (V)2 (IV) (ii) u', '(I) (vii) (III) u', '(I) (v) (IV) u u'],
    34         -                },
    35         -                "score": "u",
    36         -            },
    37         -        },
    38         -    }
           20  +    composition = yaml.load(open("score.yaml"))
    39     21   
    40     22       max_t = 0  # max time encountered so far. Used for movement timing
    41         -    progression = "overview"
    42         -    for comp_name in progression.split():
    43         -        comp_start_time = max_t
    44         -        for instr_name, instr in composition[comp_name].iteritems():
    45         -            generated_score = generate_score(instr["score"], instr["grammars"])  # Fill in the scores by generating them based on the grammars
    46         -#            print generated_score
    47         -            score = parse.parse(generated_score, default_octave=instr["octave"])  # Return Node/Chord objects
           23  +    progression = "chorus"
           24  +
           25  +    for movement in progression.split():
           26  +        for section in ["intro", "core", "outro"]:
           27  +            if section in composition[movement].keys():
           28  +                try:
           29  +                    render_order = topsort.topsort([[composition[movement][section][instrument]["sync"], instrument] if "sync" in composition[movement][section][instrument].keys() else [None, instrument] for instrument in composition[movement][section]])
           30  +                except topsort.CycleError as ex:
           31  +                    print "Your instruments are synced in a circle! This makes no sense!"
           32  +                    print movement, section
           33  +                    print ex
           34  +                    sys.exit(1)
           35  +                
    48     36   
    49         -            # Generate timestamps for the notes 
    50         -            t = comp_start_time
    51         -            for note in range(len(score)):
    52         -                score[note].time = t
    53         -                score[note].duration *= tempo
    54         -                t += score[note].duration
    55         -#                print "time difference =", t-comp_start_time
    56         -#                print "instrument duration =",composition[comp_name][instr_name]["duration"]
    57         -                if (t-comp_start_time) > float(composition[comp_name][instr_name]["duration"]):
    58         -#                    print "here"
    59         -                    score = score[:note]
    60         -                    break
    61         -                max_t = t if t > max_t else max_t
    62         -            composition[comp_name][instr_name]["score"] = score
           37  +#    for comp_name in progression.split():
           38  +#        comp_start_time = max_t
           39  +#        for instr_name, instr in composition[comp_name].iteritems():
           40  +#            generated_score = generate_score(instr["score"], instr["grammars"])  # Fill in the scores by generating them based on the grammars
           41  +##            print generated_score
           42  +#            score = parse.parse(generated_score, default_octave=instr["octave"])  # Return Node/Chord objects
           43  +#
           44  +#            # Generate timestamps for the notes 
           45  +#            t = comp_start_time
           46  +#            for note in range(len(score)):
           47  +#                score[note].time = t
           48  +#                score[note].duration *= tempo
           49  +#                t += score[note].duration
           50  +##                print "time difference =", t-comp_start_time
           51  +##                print "instrument duration =",composition[comp_name][instr_name]["duration"]
           52  +#                if (t-comp_start_time) > float(composition[comp_name][instr_name]["duration"]):
           53  +##                    print "here"
           54  +#                    score = score[:note]
           55  +#                    break
           56  +#                max_t = t if t > max_t else max_t
           57  +#            composition[comp_name][instr_name]["score"] = score
    63     58   
    64     59       # Must be done after all note times keyed in, else you can't coordinate melodies with the rhythm chords
    65     60       print '''f1  0  512  10  1
    66     61               f2 0 8192 10 .24 .64 .88 .76 .06 .5 .34 .08
    67     62               f3 0 1025 10 1
    68     63       '''
    69     64       for comp_name in progression.split():

Added rad_util.py version [99f93e22cf].

            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  +

Added topsort.py version [810c677434].

            1  +# topsort - dependency (topological) sorting and cycle finding functions
            2  +# Copyright (C) 2007 RADLogic
            3  +# 
            4  +# This library is free software; you can redistribute it and/or
            5  +# modify it under the terms of the GNU Lesser General Public
            6  +# License as published by the Free Software Foundation; 
            7  +# version 2.1 of the License.
            8  +# 
            9  +# This library is distributed in the hope that it will be useful,
           10  +# but WITHOUT ANY WARRANTY; without even the implied warranty of
           11  +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
           12  +# Lesser General Public License for more details.
           13  +#
           14  +# See http://www.fsf.org/licensing/licenses/lgpl.txt for full license text.
           15  +"""Provide toplogical sorting (i.e. dependency sorting) functions.
           16  +
           17  +The topsort function is based on code posted on Usenet by Tim Peters.
           18  +
           19  +Modifications:
           20  +- added doctests
           21  +- changed some bits to use current Python idioms
           22  +  (listcomp instead of filter, +=/-=, inherit from Exception)
           23  +- added a topsort_levels version that ports items in each dependency level
           24  +  into a sub-list
           25  +- added find_cycles to aid in cycle debugging
           26  +
           27  +Run this module directly to run the doctests (unittests).
           28  +Make sure they all pass before checking in any modifications.
           29  +
           30  +Requires Python >= 2.2
           31  +(For Python 2.2 also requires separate sets.py module)
           32  +
           33  +This requires the rad_util.py module.
           34  +
           35  +"""
           36  +
           37  +# Provide support for Python 2.2*
           38  +from __future__ import generators
           39  +
           40  +__version__ = '$Revision: 0.9 $'
           41  +__date__ = '$Date: 2007/03/27 04:15:26 $'
           42  +__credits__ = '''Tim Peters -- original topsort code
           43  +Tim Wegener -- doctesting, updating to current idioms, topsort_levels,
           44  +               find_cycles
           45  +'''
           46  +
           47  +# Make Python 2.3 sets look like Python 2.4 sets.
           48  +try:
           49  +    set
           50  +except NameError:
           51  +    from sets import Set as set
           52  +
           53  +from rad_util import is_rotated
           54  +
           55  +
           56  +class CycleError(Exception):
           57  +    """Cycle Error"""
           58  +    pass
           59  +
           60  +
           61  +def topsort(pairlist):
           62  +    """Topologically sort a list of (parent, child) pairs.
           63  +
           64  +    Return a list of the elements in dependency order (parent to child order).
           65  +
           66  +    >>> print topsort( [(1,2), (3,4), (5,6), (1,3), (1,5), (1,6), (2,5)] ) 
           67  +    [1, 2, 3, 5, 4, 6]
           68  +
           69  +    >>> print topsort( [(1,2), (1,3), (2,4), (3,4), (5,6), (4,5)] )
           70  +    [1, 2, 3, 4, 5, 6]
           71  +
           72  +    >>> print topsort( [(1,2), (2,3), (3,2)] )
           73  +    Traceback (most recent call last):
           74  +    CycleError: ([1], {2: 1, 3: 1}, {2: [3], 3: [2]})
           75  +    
           76  +    """
           77  +    num_parents = {}  # element -> # of predecessors 
           78  +    children = {}  # element -> list of successors 
           79  +    for parent, child in pairlist: 
           80  +        # Make sure every element is a key in num_parents.
           81  +        if not num_parents.has_key( parent ): 
           82  +            num_parents[parent] = 0 
           83  +        if not num_parents.has_key( child ): 
           84  +            num_parents[child] = 0 
           85  +
           86  +        # Since child has a parent, increment child's num_parents count.
           87  +        num_parents[child] += 1
           88  +
           89  +        # ... and parent gains a child.
           90  +        children.setdefault(parent, []).append(child)
           91  +
           92  +    # Suck up everything without a parent.
           93  +    answer = [x for x in num_parents.keys() if num_parents[x] == 0]
           94  +
           95  +    # For everything in answer, knock down the parent count on its children.
           96  +    # Note that answer grows *in* the loop.
           97  +    for parent in answer: 
           98  +        del num_parents[parent]
           99  +        if children.has_key( parent ): 
          100  +            for child in children[parent]: 
          101  +                num_parents[child] -= 1
          102  +                if num_parents[child] == 0: 
          103  +                    answer.append( child ) 
          104  +            # Following "del" isn't needed; just makes 
          105  +            # CycleError details easier to grasp.
          106  +            del children[parent]
          107  +
          108  +    if num_parents: 
          109  +        # Everything in num_parents has at least one child -> 
          110  +        # there's a cycle.
          111  +        raise CycleError(answer, num_parents, children)
          112  +    return answer 
          113  +
          114  +def topsort_levels(pairlist):
          115  +    """Topologically sort a list of (parent, child) pairs into depth levels.
          116  +
          117  +    This returns a generator. 
          118  +    Turn this into a an iterator using the iter built-in function.
          119  +    (if you iterate over the iterator, each element gets generated when
          120  +    it is asked for, rather than generating the whole list up-front.)
          121  +
          122  +    Each generated element is a list of items at that dependency level.
          123  +
          124  +    >>> dependency_pairs = [(1,2), (3,4), (5,6), (1,3), (1,5), (1,6), (2,5)]
          125  +    >>> for level in iter(topsort_levels( dependency_pairs )):
          126  +    ...    print level
          127  +    [1]
          128  +    [2, 3]
          129  +    [4, 5]
          130  +    [6]
          131  +
          132  +    >>> dependency_pairs = [(1,2), (1,3), (2,4), (3,4), (5,6), (4,5)]
          133  +    >>> for level in iter(topsort_levels( dependency_pairs )):
          134  +    ...    print level
          135  +    [1]
          136  +    [2, 3]
          137  +    [4]
          138  +    [5]
          139  +    [6]
          140  +
          141  +    >>> dependency_pairs = [(1,2), (2,3), (3,4), (4, 3)]
          142  +    >>> try:
          143  +    ...     for level in iter(topsort_levels( dependency_pairs )):
          144  +    ...         print level
          145  +    ... except CycleError, exc:
          146  +    ...     print 'CycleError:', exc
          147  +    [1]
          148  +    [2]
          149  +    CycleError: ({3: 1, 4: 1}, {3: [4], 4: [3]})
          150  +
          151  +
          152  +    The cycle error should look like.
          153  +    CycleError: ({3: 1, 4: 1}, {3: [4], 4: [3]})
          154  +    # todo: Make the doctest more robust (i.e. handle arbitrary dict order).
          155  +
          156  +    """
          157  +    num_parents = {}  # element -> # of predecessors 
          158  +    children = {}  # element -> list of successors 
          159  +    for parent, child in pairlist: 
          160  +        # Make sure every element is a key in num_parents.
          161  +        if not num_parents.has_key( parent ): 
          162  +            num_parents[parent] = 0 
          163  +        if not num_parents.has_key( child ): 
          164  +            num_parents[child] = 0 
          165  +
          166  +        # Since child has a parent, increment child's num_parents count.
          167  +        num_parents[child] += 1
          168  +
          169  +        # ... and parent gains a child.
          170  +        children.setdefault(parent, []).append(child)
          171  +
          172  +    return topsort_levels_core(num_parents, children)
          173  +
          174  +def topsort_levels_core(num_parents, children):
          175  +    """Topologically sort a bunch of interdependent items based on dependency.
          176  +
          177  +    This returns a generator.
          178  +    Turn this into a an iterator using the iter built-in function.
          179  +    (if you iterate over the iterator, each element gets generated when
          180  +    it is asked for, rather than generating the whole list up-front.)
          181  +
          182  +    Each generated element is a list of items at that dependency level.
          183  +
          184  +    >>> list(topsort_levels_core(
          185  +    ...          {1: 0, 2: 1, 3: 1, 4: 1, 5: 2, 6: 2},
          186  +    ...          {1: [2, 3, 5, 6], 2: [5], 3: [4], 4: [], 5: [6]}))
          187  +    [[1], [2, 3], [4, 5], [6]]
          188  +
          189  +    >>> list(topsort_levels_core(
          190  +    ...          {1: 0, 2: 2, 3: 1},
          191  +    ...          {1: [2], 2: [3], 3: [2]}))
          192  +    Traceback (most recent call last):
          193  +    CycleError: ({2: 1, 3: 1}, {2: [3], 3: [2]})
          194  +
          195  +    This function has a more complicated interface than topsort_levels,
          196  +    but is useful if the data is easier to generate in this form.
          197  +
          198  +    Arguments:
          199  +    num_parents -- key: item, value: number of parents (predecessors)
          200  +    children -- key: item, value: list of children (successors)
          201  +
          202  +    """
          203  +    while 1:
          204  +        # Suck up everything without a predecessor.
          205  +        level_parents = [x for x in num_parents.keys() if num_parents[x] == 0]
          206  +
          207  +        if not level_parents:
          208  +            break
          209  +
          210  +        # Offer the next generated item,
          211  +        # which is a list of the items at this dependency level.
          212  +        yield level_parents
          213  +
          214  +        # For everything item in this level,
          215  +        # decrement the parent count,
          216  +        # since we have accounted for its parent.
          217  +        for level_parent in level_parents:
          218  +
          219  +            del num_parents[level_parent]
          220  +
          221  +            if children.has_key(level_parent):
          222  +                for level_parent_child in children[level_parent]:
          223  +                    num_parents[level_parent_child] -= 1
          224  +                del children[level_parent]
          225  +        
          226  +    if num_parents: 
          227  +        # Everything in num_parents has at least one child -> 
          228  +        # there's a cycle.
          229  +        raise CycleError(num_parents, children)
          230  +    else:
          231  +        # This is the end of the generator.
          232  +        raise StopIteration
          233  +
          234  +
          235  +def find_cycles(parent_children):
          236  +    """Yield cycles. Each result is a list of items comprising a cycle.
          237  +
          238  +    Use a 'stack' based approach to find all the cycles.
          239  +    This is a generator, so yields each cycle as it finds it.
          240  +
          241  +    It is implicit that the last item in each cycle list is a parent of the
          242  +    first item (thereby forming a cycle).
          243  +
          244  +    Arguments:
          245  +    parent_children -- parent -> collection of children
          246  +
          247  +    Simplest cycle:
          248  +    >>> cycles = list(find_cycles({'A': ['B'], 'B': ['A']}))
          249  +    >>> len(cycles)
          250  +    1
          251  +    >>> cycle = cycles[0]
          252  +    >>> cycle.sort()
          253  +    >>> print cycle
          254  +    ['A', 'B']
          255  +
          256  +    Simplest cycle with extra baggage at the start and the end:
          257  +    >>> cycles = list(find_cycles(parent_children={'A': ['B'],
          258  +    ...                                            'B': ['C'],
          259  +    ...                                            'C': ['B', 'D'],
          260  +    ...                                            'D': [],
          261  +    ...                                            }))
          262  +    >>> len(cycles)
          263  +    1
          264  +    >>> cycle = cycles[0]
          265  +    >>> cycle.sort()
          266  +    >>> print cycle
          267  +    ['B', 'C']
          268  +
          269  +    Double cycle:
          270  +    >>> cycles = list(find_cycles(parent_children={'A': ['B'],
          271  +    ...                                            'B': ['C1', 'C2'],
          272  +    ...                                            'C1': ['D1'],
          273  +    ...                                            'D1': ['E1'],
          274  +    ...                                            'E1': ['D1'],
          275  +    ...                                            'C2': ['D2'],
          276  +    ...                                            'D2': ['E2'],
          277  +    ...                                            'E2': ['D2'],
          278  +    ...                                            }))
          279  +    >>> len(cycles)
          280  +    2
          281  +    >>> for cycle in cycles:
          282  +    ...     cycle.sort()
          283  +    >>> cycles.sort()
          284  +    >>> cycle1 = cycles[0]
          285  +    >>> cycle1.sort()
          286  +    >>> print cycle1
          287  +    ['D1', 'E1']
          288  +    >>> cycle2 = cycles[1]
          289  +    >>> cycle2.sort()
          290  +    >>> print cycle2
          291  +    ['D2', 'E2']
          292  +
          293  +    Simple cycle with children not specified for one item:
          294  +    # todo: Should this barf instead?
          295  +    >>> cycles = list(find_cycles(parent_children={'A': ['B'],
          296  +    ...                                            'B': ['A'],
          297  +    ...                                            'C': ['D']}))
          298  +    >>> len(cycles)
          299  +    1
          300  +    >>> cycle = cycles[0]
          301  +    >>> cycle.sort()
          302  +    >>> print cycle
          303  +    ['A', 'B']
          304  +
          305  +    Diamond cycle
          306  +    >>> cycles = list(find_cycles(parent_children={'A': ['B1', 'B2'],
          307  +    ...                                            'B1': ['C'],
          308  +    ...                                            'B2': ['C'],
          309  +    ...                                            'C': ['A', 'B1']}))
          310  +    >>> len(cycles)
          311  +    3
          312  +    >>> sorted_cycles = []
          313  +    >>> for cycle in cycles:
          314  +    ...     cycle = list(cycle)
          315  +    ...     cycle.sort()
          316  +    ...     sorted_cycles.append(cycle)
          317  +    >>> sorted_cycles.sort()
          318  +    >>> for cycle in sorted_cycles:
          319  +    ...     print cycle
          320  +    ['A', 'B1', 'C']
          321  +    ['A', 'B2', 'C']
          322  +    ['B1', 'C']
          323  +
          324  +    Hairy case (order can matter if something is wrong):
          325  +    (Note order of B and C in the list.)
          326  +    >>> cycles = list(find_cycles(parent_children={
          327  +    ...                                           'TD': ['DD'],
          328  +    ...                                           'TC': ['DC'],
          329  +    ...                                           'DC': ['DQ'],
          330  +    ...                                           'C': ['DQ'],
          331  +    ...                                           'DQ': ['IA', 'TO'],
          332  +    ...                                           'IA': ['A'],
          333  +    ...                                           'A': ['B', 'C'],
          334  +    ...                                           }))
          335  +    >>> len(cycles)
          336  +    1
          337  +    >>> cycle = cycles[0]
          338  +    >>> cycle.sort()
          339  +    >>> print cycle
          340  +    ['A', 'C', 'DQ', 'IA']
          341  +
          342  +    """
          343  +    cycles = []
          344  +    visited_nodes = set()
          345  +
          346  +    for parent in parent_children:
          347  +        if parent in visited_nodes:
          348  +            # This node is part of a path that has already been traversed.
          349  +            continue
          350  +
          351  +        paths = [[parent]]
          352  +        while paths:
          353  +            path = paths.pop()
          354  +
          355  +            parent = path[-1]
          356  +            
          357  +            try:
          358  +                children = parent_children[parent]
          359  +            except KeyError:
          360  +                continue
          361  +
          362  +            for child in children:
          363  +                # Keeping a set of the path nodes, for O(1) lookups at the
          364  +                # expense of more memory and complexity, actually makes speed
          365  +                # worse. (Due to construction of sets.)
          366  +                # This is O(N).
          367  +                if child in path:
          368  +                    # This is a cycle.
          369  +                    cycle = path[path.index(child):]
          370  +                    # Check that this is not a dup cycle.
          371  +                    is_dup = False
          372  +                    for other_cycle in cycles:
          373  +                        if is_rotated(other_cycle, cycle):
          374  +                            is_dup = True
          375  +                            break
          376  +                    if not is_dup:
          377  +                        cycles.append(cycle)
          378  +                        yield cycle
          379  +                else:
          380  +                    # Push this new path onto the 'stack'.
          381  +                    # This is probably the most expensive part of the algorithm
          382  +                    # (a list copy).
          383  +                    paths.append(path + [child])
          384  +                    # Mark the node as visited.
          385  +                    visited_nodes.add(child)
          386  +
          387  +
          388  +if __name__ == '__main__':
          389  +    # Run the doctest tests.
          390  +    import sys
          391  +    import doctest
          392  +    doctest.testmod(sys.modules['__main__'])