# -*- Mode: Python -*-

# given a permutation:
#   find the cycles, generate a series of insns
#   to shuffle the values around accordingly, using
#   one temporary slot <t>
# 1 2 3 4 5
# 3 1 2 5 4
# =>
# 1->t
# 2->1
# 3->2
# t->3
# 4->t
# 5->4
# t->5

l = [(1,3),(2,1),(3,2),(4,5),(5,4),(6,7),(7,8)]
l2 = [(1,2),(2,3),(3,4),(4,5),(5,6),(6,7),(7,8)]

def find_cycles (l):
    """find the cycles and chains in the graph <l>
    <l> is a list of (<from>, <to>) tuples describing\n
    arcs in the graph"""
    # build forward and reverse maps of the graph
    # [yes, this is probably overkill]
    map_f = {}
    map_r = {}
    for f, t in l:
        map_f[f] = t
        map_r[t] = f
    r = []
    # while there are any unseen arcs
    while l:
        f, t = l.pop()
        # search backward to find the head of the chain, or perhaps a cycle
        chain = []
        while map_r.has_key (f):
            chain.append (f)
            t, f = f, map_r[f]
            try:
                l.remove ((f, t))
            except ValueError:
                # ah, we found a cycle...
                r.append (('cycle', chain))
                chain = []
                break
        else:
            # no cycle, now go forward from where the chain began,
            # collecting new arcs
            chain.append (f)
            chain.reverse()
            t = chain[-1]
            while map_f.has_key (t):
                f, t = t, map_f[t]
                chain.append (t)
                try:
                    l.remove ((f, t))
                except ValueError:
                    pass
            r.append (('chain', chain))
            chain = []
    return r

def reorder (l):
    """for the permutation described by <l>, emit a series of insns
    that will reorder the values accordingly, using at most one
    temporary slot (indicated by an index of '-1')"""
    cycles = find_cycles (l)
    print 'cycles=', cycles
    insns = []
    for kind, chain in cycles:
        if kind == 'chain':
            t = chain.pop()
            while chain:
                f = chain.pop()
                insns.append (('copy', f, t))
                t = f
        elif kind == 'cycle':
            t = chain.pop()
            insns.append (('copy', t, -1))
            while chain:
                f = chain.pop()
                insns.append (('copy', f, t))
                t = f
            insns.append (('copy', -1, t))
    return insns

if __name__ == '__main__':
    import sys
    sys.stderr.write ('permutation: %r\n' % (l,))
    sys.stderr.write ('insns to reorder: %r\n' % (reorder(l),))
    sys.stderr.write ('permutation: %r\n' % (l2,))
    sys.stderr.write ('insns to reorder: %r\n' % (reorder(l2),))