/*----------------------------------------------------------------*
 *
 * File : solvexpNaive.h
 * Author : NTM
 * Created : 09/09/04
 *
 *
 * Copyright (C) Nicolas Thierry-Mieg, 2006.
 *
 *
 * This file is part of InterPool, written by 
 * Nicolas Thierry-Mieg (CNRS, France) Nicolas.Thierry-Mieg@imag.fr
 *
 * InterPool 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.
 *
 * InterPool 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 InterPool; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 *
 *-----------------------------------------------------------------*/

#ifndef _solvexpNaive_h_
#define _solvexpNaive_h_

#include "types.h" /* MOT */
#include "signa.h" /* setOfSigs */



/*!
  \file solvexpNaive.h
  \brief This file holds the slightly improved but still naive 
  decoding method for noisy observations.
  It should only be used for validating and benchmarking other methods,
  since it is very slow (exponential in the distance to the closest
  coherent signature): in general it is too slow to perform a reasonable
  number of simulations when distance > 5 or so.
  Furthermore, it only works with the Hamming distance, 
  ie DIST_xxx = 1 forall xxx. I haven't generalized it to arbitrary 
  distances (NOTE: NB had tried, but it was buggy).

  The algorithm is roughly the following:
  for (d = 0; d < PROFMAX; d++)
  {
     examine all signatures at distance d from the observed sig.
     if at least one sig is coherent, break: we have the set of
     nearest coherent signatures.
  }

  To improve this naive algorithm, 2 tricks are used:
  - 1. We never try to change a pos/weak pool if it is non-conflicting 
       in the observed sig. This relies on the observation (also used in the 
       closures method) that a nearest coherent signature cannot have changed 
       a non-conflicting (pos) pool's value.<br>
       This is implemented via:
       - firstDecoding (which calls updateVVandFlagConflicts to 
         identify conflicting pos pools)
       - nextNeighbour (which calls nextValidToChange to skip signatures 
         where a non-conflicting pos pool was changed).

  - 2. To find out if a neighbour signature is coherent, we:
       - build Negative Summary Vectors (NegSVs) when examining the observed sig,
         by partitioning the pools into NBPARTS parts, and building a NegSV for 
	 each part which reflects the fact that all neg pools in this part are negative;
       - when examining a neighbour, calculate the VV which reflects the fact that all
         its neg pools are negative by :
         - simply using the NegSV for each part containing no changed pools;
	 - if a part contains a changed (ex-)positive, we use the NegSV and also take 
	   this extra new neg pool into account;
	 - and when a part contains a changed neg, we completely recalculate its NegSV
	   (but this doesn't happen too often if NBPARTS is chosen in accordance with the 
	   expected noise level).
       - the resulting VV finally allows the detection of conflicts, by testing each
         pos pool with it (and this is done in 2 steps: first test each previously
	 conflicting pos pool and each changed neg, and if no conflict is detected take
	 into account the non-conflicting pos pools to potentially retag some ambi vars 
	 as posvars).
       This is implemented via firstDecoding and solveSig, but the real work happens in:
       - updateVVAllNegPools (which builds and stores the NegSVs when called on the 
         observed sig by firstDecoding; and then uses these NegSVs to calculate the
	 VV induced by neg pools, as described above, when called on a neighbour sig
	 by solveSig);
       - updateVVandFlagConflicts (called by firstDecoding, it identifies conflicting
         pos pools);
       - updateVVAllPosPools (called by solveSig, it performs the coherency check in
         the 2 steps described above).

*/




/*! 
  \brief Given an observation mySig, find all nearest coherent
  interpretations and return them in a setOfSigs.
  This function uses a naive algorithm, and stops if no coherent sigs were 
  found at a distance <= PROFMAX (defined in solvexpNaive.c). 
  In this case, the returned setOfSigs has distance==PROFMAX and nbOfSigs==0.
  NOTES:
  - this function only works with the Hamming distance, ie DIST_xxx = 1 forall xxx.
  - mySig is an observation: it can have only SIG_POS, SIG_WEAK,
  SIG_FAINT or SIG_NEG (no SIG_xxxCONF).
  - The returned setOfSigs is a set of interpretations, it only has
  SIG_POS or SIG_NEG.
  - mySig used to be modified by this function, but this no longer happens.
*/
setOfSigs solvexpNaive(MOT* tabpool, signature* mySig, int n) ;



#endif
