from functools import partial
from toolz.compatibility import range, map


def hashable(x):
    try:
        hash(x)
        return True
    except TypeError:
        return False


def transitive_get(key, d):
    """ Transitive dict.get

    >>> d = {1: 2, 2: 3, 3: 4}
    >>> d.get(1)
    2
    >>> transitive_get(1, d)
    4
    """
    while hashable(key) and key in d:
        key = d[key]
    return key


def dicthash(d):
    return hash(frozenset(d.items()))


def raises(err, lamda):
    try:
        lamda()
        return False
    except err:
        return True

@@ -548,28 +548,1797 @@
 pt err:%0A        return True%0A
+%0A%0A# Taken from theano/theano/gof/sched.py%0A# Avoids licensing issues because this was written by Matthew Rocklin%0Adef _toposort(edges):%0A    %22%22%22 Topological sort algorithm by Kahn %5B1%5D - O(nodes + vertices)%0A%0A    inputs:%0A        edges - a dict of the form %7Ba: %7Bb, c%7D%7D where b and c depend on a%0A    outputs:%0A        L - an ordered list of nodes that satisfy the dependencies of edges%0A%0A    %3E%3E%3E _toposort(%7B1: (2, 3), 2: (3, )%7D)%0A    %5B1, 2, 3%5D%0A%0A    Closely follows the wikipedia page %5B2%5D%0A%0A    %5B1%5D Kahn, Arthur B. (1962), %22Topological sorting of large networks%22,%0A    Communications of the ACM%0A    %5B2%5D http://en.wikipedia.org/wiki/Toposort#Algorithms%0A    %22%22%22%0A    incoming_edges = reverse_dict(edges)%0A    incoming_edges = dict((k, set(val)) for k, val in incoming_edges.items())%0A    S = set((v for v in edges if v not in incoming_edges))%0A    L = %5B%5D%0A%0A    while S:%0A        n = S.pop()%0A        L.append(n)%0A        for m in edges.get(n, ()):%0A            assert n in incoming_edges%5Bm%5D%0A            incoming_edges%5Bm%5D.remove(n)%0A            if not incoming_edges%5Bm%5D:%0A                S.add(m)%0A    if any(incoming_edges.get(v, None) for v in edges):%0A        raise ValueError(%22Input has cycles%22)%0A    return L%0A%0A%0Adef reverse_dict(d):%0A    %22%22%22Reverses direction of dependence dict%0A%0A    %3E%3E%3E d = %7B'a': (1, 2), 'b': (2, 3), 'c':()%7D%0A    %3E%3E%3E reverse_dict(d)  # doctest: +SKIP%0A    %7B1: ('a',), 2: ('a', 'b'), 3: ('b',)%7D%0A%0A    :note: dict order are not deterministic. As we iterate on the%0A        input dict, it make the output of this function depend on the%0A        dict order. So this function output order should be considered%0A        as undeterministic.%0A%0A    %22%22%22%0A    result = %7B%7D%0A    for key in d:%0A        for val in d%5Bkey%5D:%0A            result%5Bval%5D = result.get(val, tuple()) + (key, )%0A    return result%0A

add toposort and reverse_dict from multipledispatch