#
# permchek.py -- Simple program to search signature permutations of Catalan Automorphisms
#                and other regular permutations from OEIS.
# Modified June 9 2007 from oeischek.py by Antti Karttunen and placed in Public Domain.
#
# Usage:
# from permchek import *

# catachek('*.txt','catsigs.lst') # (for example...)
# comprcatachek('*.txt','comprcatsigs.lst') # (for example...)
# binpermchek('*.txt','binperms.lst') # (for example...)


import os
import re



def listdir_by_pattern(path,filepattern):
  '''List all files matching with "filepattern" in the directory "path".'''
  filepattern = filepattern.replace('*','.*') + '$'
  filepat = re.compile(filepattern)

  olddir = os.getcwd()
  os.chdir(path)
  allfiles = os.listdir('.')
  files = filter(lambda(fn): filepat.match(fn),allfiles)
  os.chdir(olddir)

  return(files)



def skip_leading_zero_if_any(terms):
  '''Returns new sequence, where the leading zero has been removed from "terms".'''
  if((len(terms) > 0) and (0 == terms[0])): return(terms[1:])
  else: return(terms)



A000079 = [1,2,4,8,16,32,64,128,256,512,1024]

A000108 = [1,2,5,14,42,132,429,1430,4862,16796]

A014137 = [1,2,4,9,23,65,197,626,2056,6918,23714,82500,290512]


# Check that, from term 1 onward, the cycles of supposed
# permutation stay in range [seq(n-1)..seq(n)-1]

# E.g. [A014137(n-1)..A014137(n)-1]
def permutation_not_confined_by(anum,origterms,confseq,upto_n):
  '''Returns None if the "origterms" seems to be an integer permutation whose cycles are confined by "confseq". Otherwise returns a diagnostic string.'''
  uplim = confseq[upto_n] # Exclusive upper limit.

  terms = skip_leading_zero_if_any(origterms)

  if(len(terms) < 1+uplim): return("Not enough terms to determine.")

  inverse_perm = [None for i in range(uplim)]

  nonfixed_terms = 0
  confind = 0
  cyclowlim = confseq[confind] # Should be 1 at first.
  confind += 1
  cycuplim  = confseq[confind] # Exclusive upper limit.

  for i in range(uplim-1):
    i1 = i+1 # One-based index.
    t = terms[i]

#   print ("confind="+str(confind)+" cyclowlim="+str(cyclowlim)+" cycuplim="+str(cycuplim)
#          +" i="+str(i)+" i1="+str(i1)+" t="+str(t))

    if(t < 0): return("Negative term, not a permutation.")
    if(0 == t): return("More than one zero present, not a permutation.")
    if(t < cyclowlim): return("Terms not confined to given limits (less than).")
    if(t >= cycuplim): return("Terms not confined to given limits (greater than).")

    if(None != inverse_perm[t]): return("Term occurs more than once.")

    inverse_perm[t] = i1 # Mark this term as having been encountered.

    if(i1 != t): nonfixed_terms += 1

    if(i1 == (cycuplim-1)): # Crossing the confinement borders...
      confind += 1      
      cyclowlim = cycuplim
      cycuplim  = confseq[confind] # Exclusive

#   end of loop: for i in range(uplim-1)


  if((0 == nonfixed_terms) and ("A001477" != anum)):
    return("Only one version of A001477 considered!")

  return(None)



def binpermchek(filepat,outfile):
  '''Search for all OEIS-entries from "filepat" which seem to be permutations whose cycles are confined by A000079. Writes the results to a similar filename with extension ".lst".'''
  permchek(listdir_by_pattern('.',filepat),outfile,A000079,6,None)

def catachek(filepat,outfile):
  '''Search for all OEIS-entries from "filepat" which seem to be permutations whose cycles are confined by A014137. Writes the results to a similar filename with extension ".lst".'''
  permchek(listdir_by_pattern('.',filepat),outfile,A014137,5,re.compile(r'.*[Kk]arttu'))

def comprcatachek(filepat,outfile):
  '''Search for all OEIS-entries from "filepat" which seem to be permutations whose cycles are confined by A000108. Writes the results to a similar filename with extension ".lst".'''
  permchek(listdir_by_pattern('.',filepat),outfile,A000108,4,re.compile(r'.*[Kk]arttu'))

def permchek(filenames,outfilename,confseq,uplim,authorpat):
  '''Opens "filenames" for reading and writes results to "outfilename".'''
  outfp = open(outfilename,'w')

  linepat = re.compile(r'^%(.) (A[0-9]+)')
  bfilepat = re.compile(r'.*(b[0-9]+\.txt)"\>([^<]*)')
  permindexpat = re.compile(r'.*(#IntegerPermutation[A-Za-z0-9]*)') # Also #IntegerPermutationCatAuto
  gatopat = re.compile(r'.*[Gg]atomor')
  deadpat = re.compile(r'.*dead')

  suspected_cases = 0
  obsolete_nomenclature = 0
  bfiles_referenced = 0
  indexes_referenced = 0
  CatAuto_indexes_referenced = 0
  dead_ones = 0
  other_authors = 0

  prev_anum = cur_anum = ""


  obsolete_terms_used = 0
  seq_name = ""
  terms = []
  bfile_referenced = ""
  index_referenced = ""
  keywords = ""
  authors = ""
  filenames_where_present = []

  for filename in filenames:
    outfp.write("--- Opening " + filename + " ---\n")
    infp = open(filename,'r')

    for line in infp.xreadlines(): 
      m = linepat.match(line)
      if(m):
        key  = m.group(1) #
        anum = m.group(2) #
        contents = m.string[m.end(2)+1:-1] # The rest, sans newline
  
        gatom = gatopat.match(contents)
        if(gatom):
          obsolete_terms_used = 1
  
  #     print "key=" + key + ":anum=" + anum + ":cur_anum=" + cur_anum + ":"
  
        if('I' == key):
          if(anum == prev_anum):
            outfp.write("ERROR: Non-unique A-number on the line:\n" + line)
  
          cur_anum = anum
        elif(anum != cur_anum):
          if("" == cur_anum):
            outfp.write("ERROR: Missing %I-line (or superfluous lines) before the line:\n" + line)
          else:
            outfp.write("ERROR: Out of place A-number (expected " + cur_anum + ") on the line:\n" + line)
  
        if(('N' == key)): seq_name = contents
  
        elif(('K' == key)): keywords = contents
  
        elif(('A' == key)): authors = contents
  
        elif(('S' == key) or ('T' == key) or ('U' == key)):
          terms += map(int,contents.replace(',',' ').split())
        elif(('H' == key)):
          mb = bfilepat.match(contents)
          mp = permindexpat.match(contents)
  
          if(mb):
            bfile_referenced = mb.group(1)
            bfile_caption = mb.group(2)
          if(mp): index_referenced = mp.group(1)
  
      elif (cur_anum != ""): # Should be the first empty line after the entry.
        reason = permutation_not_confined_by(anum,terms,confseq,uplim)
        if(None != reason):
  #       outfp.write("%N " + cur_anum + " was filtered out, because: " + reason + "\n")
          anum = anum
        else: # if(not permutation_not_confined_by(terms,confseq,uplim)):
  
          outfp.write("%N " + cur_anum + " " + seq_name)
  
          # Print author-info on the same line!
          if("" == authors):
            authors = "ERROR: Author-line missing!"

          if(None == authorpat):
            outfp.write(" /// %A " + cur_anum + " " + authors + "\n")
  
          elif(not authorpat.match(authors)):
            outfp.write(" /// %A " + cur_anum + " " + authors + "\n")
            outfp.write("%S " + cur_anum + " " + str(terms[0]))
            for t in terms[1:]: outfp.write("," + str(t))
            outfp.write("\n")
            other_authors += 1

          else: outfp.write("\n")
  
          if(not(filename in filenames_where_present)):
            filenames_where_present.append(filename)

          suspected_cases += 1
          if(obsolete_terms_used):
            outfp.write(" " + cur_anum + " uses obsolete terms, replace with \"Catalan automorphisms\"\n")
            obsolete_nomenclature += 1
  
          if("" != bfile_referenced):
            outfp.write(" " + cur_anum + " Includes a b-file: " + bfile_referenced
                         + ": " + bfile_caption + "\n")
            bfiles_referenced += 1
  
          if("" != index_referenced):
            outfp.write(" " + cur_anum + " Includes a link to index: " + index_referenced + "\n")
            indexes_referenced +=1
            if("#IntegerPermutationCatAuto" == index_referenced): CatAuto_indexes_referenced += 1
  
          if(("" != keywords) and (deadpat.match(keywords))):
            outfp.write("%K " + cur_anum + " " + keywords + "\n")
            dead_ones += 1
  
          outfp.write("\n")
  
  
        terms = []
        prev_anum = cur_anum
        cur_anum = ""
        seq_name = ""
        obsolete_terms_used = 0
        bfile_referenced = ""
        index_referenced = ""
        keywords = ""
        authors = ""
  
  #   else: Something else, just skip!
    infp.close()
# End of loop: for filename in filenames:

  outfp.write("------------- Summary follows -------------\n")
  outfp.write("Total of " + str(suspected_cases) + " cases were found.\n")
  outfp.write("In the following files: " + str(filenames_where_present) + "\n")
  if(obsolete_nomenclature > 0):
    outfp.write(str(obsolete_nomenclature) + " entries used the obsolete term \"gatomorphism\".\n")
  outfp.write(str(bfiles_referenced) + " entries included a b-file.\n")
  outfp.write(str(indexes_referenced) + " entries included a %H-link to a permutation index,"
    + " of which " + str(CatAuto_indexes_referenced)
    + " were references to #IntegerPermutationCatAuto.\n")
 
  outfp.write(str(dead_ones) + " entries were dead.\n")
  outfp.write(str(other_authors) + " entries were submitted by \"other authors\".\n")
      
  outfp.close()




# This module ends here.