# remember to first load Farey Symbols:
# LoadPackage("congruence");  

# following function determines which edge an image ImL of
# a domain is the longest
#
#
# The function either returns a index of an edge
# which is a number between 1 and #L-1,
# or it returns "overlap" meaning that there is overlap, but not equality.


longest_edge := function(ImL)
   local i, minImL, maxImL, maxindex, minindex;
   for i in [1..Length(ImL)] do
      if ImL[i] = infinity then
        return "infinity";
      fi; 
   od;
   minImL := Minimum(ImL);
   maxImL := Maximum(ImL);
   maxindex := PositionNthOccurrence( ImL ,maxImL,1);
      return maxindex;
end;;

# this an algorithm to determine a word for
# a given matrix g in G in terms of the generators:


find_word_ver2 := function(FS,glue_list,g)
   local gens, L, ImL, done, word,letter,i, edge, h, maybesame, inf, gap;
   gens := GeneratorsByFareySymbol( FS );
   L := GeneralizedFareySequence( FS );
   ImL := PSL2multiply(g,L);
   word:=[];
   h := g;
   done := false;
   while not done do;      
      edge := longest_edge(ImL);
      if edge = "infinity" then
         # check equality of L and ImL:
         maybesame := true;
         i := 1;
         while i < Length(L) and maybesame do
            if not L[i] = ImL[i] then
              maybesame := false;
            fi;
            i := i+1;
         od;
         if maybesame then
            done := true;
            return Reversed(word);
         fi;         
         # now assume the domains are not equal
         inf := PositionNthOccurrence( ImL , infinity ,1);
#         if inf = 1 and
#            ImL[2]<L[Length(L)-1] and
#            ImL[Length(L)-1]>L[2] then              
#            return "g is not in the group";
#         elif
#            ImL[i+1]<L[Length(L)-1] and
#            ImL[i-1]>L[2] then              
#            return "g is not in the group";         
#         fi;
# above lines seem to have bug use following for moment:
      gap := which_gap(L,ImL);
      if gap = "overlap" then
         Print("matrix not in group\n");
         return word;
      fi;
         # now assume the domains do not overlap
         if ImL[inf+1] >= L[2] then
            letter := glue_list[inf];
         elif inf = 1 then
            letter := glue_list[Length(glue_list)];
         else
            letter := glue_list[inf-1];
         fi;
         Add(word,letter);
#         Print(word);
         h:=h*gens[AbsoluteValue(letter)]^(-SignInt(letter));
         ImL := PSL2multiply(h,L);
      else
         # get next "letter" in the word for the matrix:
         letter := glue_list[edge];
         Add(word,letter);
#         Print(word);
      h:=h*gens[AbsoluteValue(letter)]^(-SignInt(letter));
      ImL := PSL2multiply(h,L);
      fi;
   od;
   return Reversed(word);
end;;