/* Copyright (C) 2010 Univ. of Massachusetts Amherst, Computer Science Dept.
   This file is part of "MALLET" (MAchine Learning for LanguagE Toolkit).
   http://www.cs.umass.edu/~mccallum/mallet
   This software is provided under the terms of the Common Public License,
   version 1.0, as published by http://www.opensource.org.  For further
   information, see the file `LICENSE' included with this distribution. */

package cc.mallet.fst.semi_supervised.constraints;

import gnu.trove.TIntArrayList;
import gnu.trove.TIntObjectHashMap;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.HashMap;

import cc.mallet.fst.SumLattice;
import cc.mallet.fst.semi_supervised.StateLabelMap;
import cc.mallet.types.FeatureVector;
import cc.mallet.types.FeatureVectorSequence;
import cc.mallet.types.Instance;
import cc.mallet.types.InstanceList;

/**
 * A set of constraints on individual input feature label pairs.   
 * 
 * This is to be used with GE, and penalizes the
 * L_2^2 difference between model and target distributions.
 * 
 * Multiple constraints are grouped together here
 * to make things more efficient.
 * 
 * @author Gregory Druck
 */

public class OneLabelL2RangeGEConstraints implements GEConstraint {

  // maps between input feature indices and constraints
  protected TIntObjectHashMap<OneLabelL2IndGEConstraint> constraints;
  protected StateLabelMap map;
  
  // cache of set of constrained features that fire at last FeatureVector
  // provided in preprocess call
  protected TIntArrayList cache;

  public OneLabelL2RangeGEConstraints() {
    this.constraints = new TIntObjectHashMap<OneLabelL2IndGEConstraint>();
    this.cache = new TIntArrayList();
  }
  
  protected OneLabelL2RangeGEConstraints(TIntObjectHashMap<OneLabelL2IndGEConstraint> constraints, StateLabelMap map) {
    this.constraints = constraints;
    this.map = map;
    this.cache = new TIntArrayList();
  }
  
  public void addConstraint(int fi, int li, double lower, double upper, double weight) {
    if (!constraints.containsKey(fi)) {
      constraints.put(fi,new OneLabelL2IndGEConstraint());
    }
    constraints.get(fi).add(li, lower, upper, weight);
  }
  
  public boolean isOneStateConstraint() {
    return true;
  }
  
  public void setStateLabelMap(StateLabelMap map) {
    this.map = map;
  }
  
  public void preProcess(FeatureVector fv) {
    cache.resetQuick();
    int fi;
    // cache constrained input features
    for (int loc = 0; loc < fv.numLocations(); loc++) {
      fi = fv.indexAtLocation(loc);
      if (constraints.containsKey(fi)) {
        cache.add(fi);
      }
    }
    if (constraints.containsKey(fv.getAlphabet().size())) {
      cache.add(fv.getAlphabet().size());
    }
  }
  
  // find examples that contain constrained input features
  public BitSet preProcess(InstanceList data) {
    // count
    int ii = 0;
    int fi;
    FeatureVector fv;
    BitSet bitSet = new BitSet(data.size());
    for (Instance instance : data) {
      FeatureVectorSequence fvs = (FeatureVectorSequence)instance.getData();
      for (int ip = 0; ip < fvs.size(); ip++) {
        fv = fvs.get(ip);
        for (int loc = 0; loc < fv.numLocations(); loc++) {
          fi = fv.indexAtLocation(loc);
          if (constraints.containsKey(fi)) {
            constraints.get(fi).count += 1;
            bitSet.set(ii);
          }
        }
        if (constraints.containsKey(fv.getAlphabet().size())) {
          bitSet.set(ii);
          constraints.get(fv.getAlphabet().size()).count += 1;
        }
      }

      ii++;
    }
    return bitSet;
  }    
  
  public double getCompositeConstraintFeatureValue(FeatureVector fv, int ip, int si1, int si2) {
    double value = 0;
    int li2 = map.getLabelIndex(si2);
    for (int i = 0; i < cache.size(); i++) {
      value += constraints.get(cache.getQuick(i)).getGradientContribution(li2);
    }
    return value;
  }

  public double getValue() {
    double value = 0.0;
    for (int fi : constraints.keys()) {
      OneLabelL2IndGEConstraint constraint = constraints.get(fi);
      if ( constraint.count > 0.0) {
        // value due to current constraint
        for (int labelIndex = 0; labelIndex < map.getNumLabels(); ++labelIndex) {
          value -= constraint.getValueContribution(labelIndex);
        }
      }
    }
    assert(!Double.isNaN(value) && !Double.isInfinite(value));
    return value;
  }

  public void zeroExpectations() {
    for (int fi : constraints.keys()) {
      constraints.get(fi).expectation = new double[constraints.get(fi).getNumConstrainedLabels()];
    }
  }
  
  public void computeExpectations(ArrayList<SumLattice> lattices) {
    double[][] gammas;    
    TIntArrayList cache = new TIntArrayList();
    for (int i = 0; i < lattices.size(); i++) {
      if (lattices.get(i) == null) { continue; }
      SumLattice lattice = lattices.get(i);
      FeatureVectorSequence fvs = (FeatureVectorSequence)lattice.getInput();
      gammas = lattice.getGammas();
      for (int ip = 0; ip < fvs.size(); ++ip) {
        cache.resetQuick();
        FeatureVector fv = fvs.getFeatureVector(ip);
        int fi;
        for (int loc = 0; loc < fv.numLocations(); loc++) {
          fi = fv.indexAtLocation(loc);
          // binary constraint features
          if (constraints.containsKey(fi)) {
            cache.add(fi);
          }
        }
        if (constraints.containsKey(fv.getAlphabet().size())) {
          cache.add(fv.getAlphabet().size());
        }
        for (int s = 0; s < map.getNumStates(); ++s) {
          int li = map.getLabelIndex(s);
          if (li != StateLabelMap.START_LABEL) {
            double gammaProb = Math.exp(gammas[ip+1][s]);
            for (int j = 0; j < cache.size(); j++) {
              constraints.get(cache.getQuick(j)).incrementExpectation(li,gammaProb);
            }
          }
        }
      }
    }
  }
  
  public GEConstraint copy() {
    return new OneLabelL2RangeGEConstraints(this.constraints, this.map); 
  }
  
  protected class OneLabelL2IndGEConstraint {
    
    protected int index;
    protected double count;
    protected ArrayList<Double> lower;
    protected ArrayList<Double> upper;
    protected ArrayList<Double> weights;
    protected HashMap<Integer,Integer> labelMap;
    protected double[] expectation;

    public OneLabelL2IndGEConstraint() {
      lower = new ArrayList<Double>();
      upper = new ArrayList<Double>();
      weights = new ArrayList<Double>();
      labelMap = new HashMap<Integer,Integer>();
      index = 0;
      count = 0;
    }
    
    public void add(int label, double lower, double upper, double weight) {
      this.lower.add(lower);
      this.upper.add(upper);
      this.weights.add(weight);
      labelMap.put(label, index);
      index++;
    }
    
    public void incrementExpectation(int li, double value) {
      if (labelMap.containsKey(li)) {
        int i = labelMap.get(li);
        expectation[i] += value;
      }
    }
    
    public double getValueContribution(int li) {
      if (labelMap.containsKey(li)) {
        int i = labelMap.get(li);
        assert(this.count != 0);
        
        double ex = this.expectation[i] / this.count;
        if (ex < lower.get(i)) {
          return weights.get(i) * Math.pow(lower.get(i) - ex,2);
        }
        else if (ex > upper.get(i)) {
          return weights.get(i) * Math.pow(upper.get(i) - ex,2);         
        }
      }
      return 0;
    }
    
    public int getNumConstrainedLabels() {
      return index;
    }
    
    public double getGradientContribution(int li) {
      if (labelMap.containsKey(li)) {
        int i = labelMap.get(li);
        assert(this.count != 0);
        
        double ex = this.expectation[i] / this.count;
        if (ex < lower.get(i)) {
          return 2 * weights.get(i) * (lower.get(i) / count - expectation[i] / (count * count));
        }
        else if (ex > upper.get(i)) {
          return 2 * weights.get(i) * (upper.get(i) / count - expectation[i] / (count * count));          
        }
      }
      return 0;
    }
  }
}