import os, sys, re, string

# This Python code checks the facts about the set of genus 2 interval
# exchanges that are asserted in Section 10, after the statement of
# Thm 10.4.  In particular, it demonstrates that "tau_0" is contained
# in a sink of I_S of size 190.  


# The class of interval exchanges.  

class IE:

    # An interval exchange is specified by listing the labels of the
    # bands attached along the top and the bottom.
    
    def __init__(self, top, bottom):
        self.top, self.bottom = top, bottom

    def __repr__(self):
        return "<IE %s | %s>" % (self.top, self.bottom)

    def __cmp__(self, other):
        if isinstance(other, IE):
            return cmp(  [self.top, self.bottom], [other.top, other.bottom] )
        return -1

    def preserves_orientation(self, band_num):
        return (band_num in self.top) and (band_num in self.bottom)

    # Turn the IE over:
    
    def flip(self):
        return IE(self.bottom, self.top)

    # Canonize the labels on the bands to be the one which is
    # lexagraphically first.
    
    def normalize(self):
        labels = unique(self.top + self.bottom)
        return IE([ labels.index(x) for x in self.top],
                  [ labels.index(x) for x in self.bottom])

    # Moreover, lexagraphically first up to flipping the exchange
    # over.
    
    def full_normalize(self):
        return min(self.normalize(), self.flip().normalize())

    # Do a splitting move
    
    def split_top(self):
        t, b  = self.top[-1], self.bottom[-1]
        if self.preserves_orientation(t):
            return IE( subs(t, [t,b], self.top[:-1]) + [t], subs(t, [t,b], self.bottom[:-1]))
        else:
            return IE( subs(t, [b,t], self.top[:-1]) + [t], subs(t, [b,t], self.bottom[:-1]))

    def split_bottom(self):
        return self.flip().split_top().flip()
    
    # assumes that there is at least one orientation reversing band,
    # which there must be for our exchanges.

    def is_recurrent(self):
        t, b = self.top, self.bottom
        return len(unique(t)) < len(t) and len(unique(b)) < len(b) 

    # Do all possible recurrent splits
    
    def splits(self):
        return [ie.full_normalize() for ie in [self.split_top(), self.split_bottom()] if ie.is_recurrent()]

# helper functions

def unique(L):
    ans = []
    for l in L:
        if not l in ans:
            ans.append(l)

    return ans

# replaces "a" with the seq "x" in list L

def subs(a,x,L):
    ans = []
    for l in L:
        if l != a:
            ans.append(l)
        else:
            ans += x

    return ans

def concatenate(LofL):
    ans = []
    for L in LofL:
        ans += L
    return ans

# Computes the space of all IEs that result from splitting the given
# one.

def split_space( base_ie ):
    ies = [base_ie]
    new_ies = ies[:]
    while 1:
        new_ies = [ ie for ie in  unique(concatenate([ie.splits() for ie in new_ies])) if not ie in ies]
        if len(new_ies) == 0:
            return ies

        ies += new_ies

# The main test function

def main_test_genus_2():

    # This is the base interval exchange tau_0 from the paper.  

    base_ie = IE( [0, 1, 2, 3, 1, 2, 3], [4, 5, 6, 4, 5, 6, 0]).full_normalize()

    # compute the split space.
    
    base_space = split_space(base_ie)
    print "There are %d exchanges resulting from %s" % (len(base_space), base_ie)

    # Now check that this is a sink.
    
    for ie in base_space:
        ie_space = split_space(ie)
        print "For %s, the split space has %d elements, contains base_ie: %s " % (ie, len(ie_space), base_ie in ie_space)    

if __name__ == "__main__":
    main_test_genus_2()