/**
 * This file is part of choco-solver, http://choco-solver.org/
 *
 * Copyright (c) 2017, IMT Atlantique. All rights reserved.
 *
 * Licensed under the BSD 4-clause license.
 * See LICENSE file in the project root for full license information.
 */
package org.chocosolver.solver.search.strategy.selectors.variables;

import org.chocosolver.memory.IStateInt;
import org.chocosolver.solver.Model;
import org.chocosolver.solver.variables.IntVar;

/**
 * <b>First fail</b> variable selector.
 * It chooses the variable with the smallest domain (instantiated variables are ignored).
 * <br/>
 *
 * @author Charles Prud'homme
 * @since 2 juil. 2010
 */
public class FirstFail implements VariableSelector<IntVar>, VariableEvaluator<IntVar> {

    private IStateInt lastIdx; // index of the last non-instantiated variable

    /**
     * <b>First fail</b> variable selector.
     * @param model reference to the model (does not define the variable scope)
     */
    public FirstFail(Model model){
        lastIdx = model.getEnvironment().makeInt(0);
    }

    @Override
    public IntVar getVariable(IntVar[] variables) {
        int small_idx = -1;
        int small_dsize = Integer.MAX_VALUE;
        boolean got = false;
        for (int idx = lastIdx.get(); idx < variables.length; idx++) {
            int dsize = variables[idx].getDomainSize();

            if (!got && !variables[idx].isInstantiated()) {
                //got is just to call 'set' at most once
                lastIdx.set(idx);
                got = true;
            }

            if (dsize > 1 && dsize < small_dsize) {
                small_dsize = dsize;
                small_idx = idx;
            }

            if (small_dsize == 2) {
                break;
            }
        }
        return small_idx > -1 ? variables[small_idx] : null;
    }

    @Override
    public double evaluate(IntVar variable) {
        return variable.getDomainSize();
    }
}

@@ -498,24 +498,33 @@
 chooses the 
+leftmost 
 variable wit
@@ -624,16 +624,33 @@
 ud'homme
+, Arnaud Malapert
 %0A * @sin
@@ -770,16 +770,22 @@
 private 
+final 
 IStateIn
@@ -1069,32 +1069,41 @@
 keInt(0);%0A    %7D%0A
+    %0A    
 %0A    @Override%0A 
@@ -1165,26 +1165,30 @@
     
-i
+I
 nt
+Var
  small
-_idx = -1
+Var = null
 ;%0A  
@@ -1198,27 +1198,26 @@
    int small
-_ds
+DS
 ize = Intege
@@ -1241,28 +1241,72 @@
     
-boolean got = false;
+// get and update the index of the first uninstantiated variable
 %0A   
@@ -1314,13 +1314,8 @@
     
-for (
 int 
@@ -1334,17 +1334,31 @@
 x.get();
- 
+%0A        while(
 idx %3C va
@@ -1375,321 +1375,488 @@
 ngth
-; idx++) %7B%0A            int dsize = variables%5Bidx%5D.getDomainSize();%0A%0A            if (!got && !variables%5Bidx%5D.isInstantiated()) %7B%0A                //got is just to call 'set' at most once%0A                lastIdx.set(idx);%0A                got = true;%0A            %7D%0A%0A            if (dsize %3E 1 && dsize %3C small_dsize) %7B
+ && variables%5Bidx%5D.isInstantiated()) %7B%0A            idx++;%0A        %7D%0A        lastIdx.set(idx);%0A        //search for the leftmost variable with smallest domain%0A        while(idx %3C variables.length) %7B%0A            final int dsize = variables%5Bidx%5D.getDomainSize();%0A            if (dsize %3C smallDSize && dsize %3E 1) %7B%0A             // the variable is candidate for having the smallest domain%0A             //and  the variable is not instantiated %0A                smallVar = variables%5Bidx%5D;
 %0A   
@@ -1869,27 +1869,26 @@
        small
-_ds
+DS
 ize = dsize;
@@ -1908,40 +1908,56 @@
     
-small_idx = idx;%0A            %7D%0A%0A
+// cannot be smaller than a boolean domain %0A    
     
@@ -1970,16 +1970,9 @@
   if
- (small_
+(
 dsiz
@@ -1980,16 +1980,23 @@
  == 2) %7B
+break;%7D
 %0A       
@@ -2004,18 +2004,9 @@
     
-    break;
+%7D
 %0A   
@@ -2006,33 +2006,38 @@
   %7D%0A            
-%7D
+idx++;
 %0A        %7D%0A     
@@ -2055,55 +2055,19 @@
 mall
-_idx %3E -1 ? variables%5Bsmall_idx%5D : null
+Var
 ;%0A    %7D%0A
 %0A   
@@ -2062,16 +2062,20 @@
 ;%0A    %7D%0A
+    
 %0A    @Ov

optimize first fail variable selector (#493)