/*
 * TSPOrderOne.java
 *
 * Created on May 23, 2006, 8:30 PM
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */

package cz.pcland.ga.crossover;
import cz.pcland.ga.BaseIndividual;
import cz.pcland.ga.MyRand;
import cz.pcland.ga.TSPIntegerIndividual;
import java.util.*;
/**
 *
 * @author petr
 */
public class TSPOrderOne implements CrossoverOpearator{
    int cutpoint1;
    int cutpoint2;
    int strLen;
    int lastFree = -1;
    
    int[] integer1;
    int[] integer2;
    
    int positions1[];
    int positions2[];
    
    int off1[];
    int off2[];
    
    int lastNotIn1 = -1;
    int lastNotIn2 = -1;
    /** Creates a new instance of TSPOrderOne */
    public TSPOrderOne() {
    }
    
    public String toString() {
       return "TSP order 1 (2 points)";
    }
    
    public int nextFreeFromRight() {
        if(lastFree == -1) lastFree = cutpoint2 + 1;
        return (lastFree++)%strLen;
        
    }
    
    public int getNextNotIn1(){
       if(lastNotIn1 == -1) lastNotIn1 = cutpoint2 + 1; 
       
       for(int i = lastNotIn1; i < (lastNotIn1 + strLen); i++) {
            if(positions1[integer2[i%strLen]] == -1){
                lastNotIn1 = (i+1)%strLen;
                return integer2[i%strLen];
            }
        }
        
        return -1;
    }
    
    public int getNextNotIn2(){
       if(lastNotIn2 == -1) lastNotIn2 = cutpoint2 + 1; 
       
       for(int i = lastNotIn2; i < (lastNotIn2 + strLen); i++) {
            if(positions2[integer1[i%strLen]] == -1){
                lastNotIn2 = (i+1)%strLen;
                return integer1[i%strLen];
            }
        }
        
        return -1;
    }
    
    public void print(String str, int[] a){
        System.out.print(str + ": " );
        for(int i=0; i<a.length;i++) {
            
            System.out.print(a[i] + " ");
        }
        System.out.print("\n");
    }
    
    public BaseIndividual[] crossOver(BaseIndividual i1, BaseIndividual i2, int strLen) {
        this.strLen = strLen;
        cutpoint1 = Math.abs(MyRand.getInt())%strLen;
        cutpoint2 = Math.abs(MyRand.getInt())%strLen;
        
        if(cutpoint1 > cutpoint2){
            int tmp = cutpoint1;
            cutpoint1 = cutpoint2;
            cutpoint2 = tmp;
        }
        
        lastFree = -1;
        lastNotIn1 = -1;
        lastNotIn2 = -1;
        
        
        integer1 = ((TSPIntegerIndividual)i1).getString();
        integer2 = ((TSPIntegerIndividual)i2).getString();
        
        off1 = new int[strLen];
        off2 = new int[strLen];
        
        positions1 = new int[strLen];
        positions2 = new int[strLen];
        
        for(int i=0;i<strLen;i++) {
            positions1[i] = -1;
            positions2[i] = -1;
        }
        
        
        for(int i=0;i<strLen;i++) {
            if(i >= cutpoint1 && i <= cutpoint2) {
                off1[i] = integer1[i];
                off2[i] = integer2[i];
                
                positions1[off1[i]] = i;
                positions2[off2[i]] = i;
            } else {
                off1[i] = -1;
                off2[i] = -1;
            }
        }
        

        int free;
        while ( (free = nextFreeFromRight()) != this.cutpoint1 ){
            off1[free] = this.getNextNotIn1();
            off2[free] = this.getNextNotIn2();
        }
       
        TSPIntegerIndividual[] ret = {new TSPIntegerIndividual(strLen), new TSPIntegerIndividual(strLen)};
        ret[0].setString(off1);
        ret[1].setString(off2);
        
        return ret;
    }
    
    
}
