/*
 * Jalview - A Sequence Alignment Editor and Viewer
 * Copyright (C) 2006 AM Waterhouse, J Procter, G Barton, M Clamp, S Searle
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
 */
package jalview.util;

import java.util.*;

/**
 * MapList
 * Simple way of bijectively mapping a non-contiguous linear range to another non-contiguous linear range
 * Use at your own risk!
 * TODO: efficient implementation of private posMap method
 * TODO: test/ensure that sense of from and to ratio start position is conserved (codon start position recovery)
 * TODO: optimize to use int[][] arrays rather than vectors.
 */
public class MapList
{
    public Vector fromShifts;
    public Vector toShifts;
    int fromRatio; // number of steps in fromShifts to one toRatio unit
    int toRatio; // number of steps in toShifts to one fromRatio
  public MapList(int from[], int to[], int fromRatio, int toRatio)
  {
    fromShifts = new Vector();
    for (int i=0;i<from.length; i+=2)
        fromShifts.add(new int[] { from[i], from[i+1]});
    toShifts = new Vector();
    for (int i=0;i<to.length; i+=2)
        toShifts.add(new int[] { to[i], to[i+1]});
    this.fromRatio=fromRatio;
    this.toRatio=toRatio;
  }
  /**
   * get all mapped positions from 'from' to 'to'
   * @return int[][] { int[] { fromStart, fromFinish, toStart, toFinish }, int [fromFinish-fromStart+2] { toStart..toFinish mappings}}
   */
  public int[][] makeFromMap() {
      return posMap(fromShifts, fromRatio, toShifts, toRatio);
  }
  /**
   * get all mapped positions from 'to' to 'from'
   * @return int[to position]=position mapped in from
   */
  public int[][] makeToMap() {
      return posMap(toShifts,toRatio, fromShifts, fromRatio);
  }
  /**
   * construct an int map for intervals in intVals
   * @param intVals
   * @return int[] { from, to pos in range }, int[range.to-range.from+1] returning mapped position
   */
  private int[][] posMap(Vector intVals, int ratio, Vector toIntVals, int toRatio) {
      Iterator iv = intVals.iterator();
      if (!iv.hasNext())
          return null;
      int[] intv=(int[]) iv.next();
      int from=intv[0],to=intv[1];
      if (from>to) {
          from = intv[1];
          to=intv[0];
      }
      while (iv.hasNext()) {
          intv = (int[]) iv.next();
          if (intv[0]<from)
              from=intv[0];
          if (intv[1]<from)
              from=intv[1];
          if (intv[0]>to)
              to=intv[0];
          if (intv[1]>to)
              to=intv[1];
      }
      int tF=0,tT=0;
      int mp[][] = new int[to-from+2][];
      for (int i=0;i<mp.length; i++) {
          int[] m = shift(i+from,intVals,ratio,toIntVals, toRatio);
          if (m!=null) {
              if (i==0) {
                  tF=tT=m[0];
              } else {
                  if (m[0]<tF) {
                      tF=m[0];
                  }
                  if (m[0]>tT) {
                      tT=m[0];
                  }
              }
          }
          mp[i] = m;
      }
      int[][] map=new int[][] { new int[]{from, to, tF, tT}, new int[to-from+2]};

      map[0][2] = tF;
      map[0][3] = tT;
      
      for (int i=0;i<mp.length; i++) {
          if (mp[i]!=null) {
              map[1][i] = mp[i][0]-tF;
          } else {
              map[1][i] = -1; // indicates an out of range mapping
          }
      }
      return map;
  }
  /**
   * addShift
   * @param pos start position for shift (in original reference frame)
   * @param shift length of shift
   *
  public void addShift(int pos, int shift)
  {
    int sidx = 0;
    int[] rshift=null;
    while (sidx<shifts.size() && (rshift=(int[]) shifts.elementAt(sidx))[0]<pos)
      sidx++;
    if (sidx==shifts.size())
      shifts.insertElementAt(new int[] { pos, shift}, sidx);
    else
      rshift[1]+=shift;
  }
*/
  /**
   * shift from pos to To(pos)
   *
   * @param pos int
   * @return int shifted position in To, frameshift in From
   */
  public int[] shiftFrom(int pos)
  {
      return shift(pos, fromShifts, fromRatio, toShifts, toRatio);
  }

  /**
   * inverse of shiftFrom - maps pos in To to a position in From
   * @param pos (in To)
   * @return shifted position in From, frameshift in To
   */
  public int[] shiftTo(int pos) {
      return shift(pos, toShifts, toRatio, fromShifts, fromRatio);
  }
  /**
   * 
   * @param fromShifts
   * @param fromRatio
   * @param toShifts
   * @param toRatio
   * @return
   */
  private int[] shift(int pos, Vector fromShifts, int fromRatio, Vector toShifts, int toRatio) {
      int[] fromCount = countPos(fromShifts.iterator(), pos);
      if (fromCount==null)
          return null;
      int fromRemainder=(fromCount[0]-1) % fromRatio;
      int toCount = 1+(((fromCount[0]-1) / fromRatio) * toRatio);
      int[] toPos = countToPos(toShifts.iterator(), toCount);
      if (toPos==null)
          return null; // throw new Error("Bad Mapping!");
      //System.out.println(fromCount[0]+" "+fromCount[1]+" "+toCount);
      return new int[] {toPos[0], fromRemainder};
  }
  /**
   * count how many positions pos is along the series of intervals.
   * @param intVals
   * @param pos
   * @return number of positions or null if pos is not within intervals
   */
  private int[] countPos(Iterator intVals, int pos) {
      int count=0,intv[];
      while (intVals.hasNext()) {
          intv = (int[])intVals.next();
          if (intv[0] <= intv[1]) {
              if (pos>=intv[0] && pos<=intv[1]) {
                  return new int[] { count+pos-intv[0]+1, +1 };
              } else {
                  count+=intv[1]-intv[0]+1;
              }
          } else {
              if (pos>=intv[1] && pos<=intv[0]) {
                  return new int[] { count+intv[0]-pos+1, -1 };
              } else {
                  count+=intv[0]-intv[1]+1;
              }
          }
      }
      return null;
  }
  /**
   * count out pos positions into a series of intervals and return the position
   * @param intVals
   * @param pos
   * @return position pos in interval set
   */
  private int[] countToPos(Iterator intVals, int pos) {
      int count=0,diff=0,intv[]={0,0};
      while (intVals.hasNext()) {
          intv = (int[])intVals.next();
          diff = intv[1]-intv[0];
          if (diff>=0) {
              if (pos<=count+1+diff) {
                  return new int[] { pos-count-1+intv[0],+1 };
              } else {
                  count+=1+diff;
              }
          } else {
              if (pos<=count+1-diff) {
                  return new int[] { intv[0]-(pos-count-1),-1 };
              } else {
                  count+=1-diff;
              }
          }
      }
      return null;//(diff<0) ? (intv[1]-1) : (intv[0]+1);
  }
  public static void testMap(MapList ml, int fromS,int fromE) {
      for (int from=1; from<=25; from++) {
          int[] too=ml.shiftFrom(from);
          System.out.print("ShiftFrom("+from+")==");
          if (too==null)
              System.out.print("NaN\n");
          else {
              System.out.print(too[0]+" % "+too[1]);
              System.out.print("\t+--+\t");
              int[] toofrom=ml.shiftTo(too[0]);
              if (toofrom!=null)
                  System.out.println("ShiftTo("+too[0]+")=="+toofrom[0]+" % "+toofrom[1]);
              else
                  System.out.println("ShiftTo("+too[0]+")=="+"NaN! - not Bijective Mapping!");
          }
      }
      int mmap[][] = ml.makeFromMap();
      System.out.println("FromMap : ("+mmap[0][0]+" "+mmap[0][1]+" "+mmap[0][2]+" "+mmap[0][3]+" ");
      for (int i=1;i<=mmap[1].length; i++) {
          if (mmap[1][i-1]==-1) {
              System.out.print(i+"=XXX");
              
          } else {
              System.out.print(i+"="+(mmap[0][2]+mmap[1][i-1]));
          }
          if (i % 20==0)
              System.out.print("\n");
          else
              System.out.print(",");
      }
      System.out.print("\n");
  }
  public static void main(String argv[]) {
      MapList ml=new MapList(new int[] { 1,5,10,15,25,20}, 
              new int[] { 51,1}, 1, 3);
      MapList ml1=new MapList(new int[] { 1,3,17,4}, 
              new int[] { 51,1}, 1, 3);
      
      // test internal consistency
      int to[] = new int[51];
      MapList.testMap(ml, 1, 25);
      /*
      for (int from=1; from<=51; from++) {
          int[] too=ml.shiftTo(from);
          int[] toofrom=ml.shiftFrom(too[0]);
          System.out.println("ShiftFrom("+from+")=="+too[0]+" % "+too[1]+"\t+-+\tShiftTo("+too[0]+")=="+toofrom[0]+" % "+toofrom[1]);
      }*/
      System.out.print("Success?\n"); // if we get here - something must be working!
  }
}