/*----------------------------------------------------------------*
 *
 * File : substractNegPools.body.c
 * Author : NTM
 * Created : 20/01/05
 *
 *
 * 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
 *
 *-----------------------------------------------------------------*/


/*!
  \file substractNegPools.body.c
  \brief This file contains the body of substractNegPoolsFromUnits
  (and instructions for building substractNegPoolsFromUnitsInclInval).
   
  It is not a stand-alone c source file, and should never be
  included directly! Instead, you should \#include substractNegPools.bodyFull.c
  exactly once, in unitClosures.c.<br>
  substractNegPools.bodyFull.c will be created by the perl
  script substractNegPools.body.make.pl, from the current file.
  You should only edit the body of substractNegPoolsFromUnits,
  and place any code specific to inclusion-invalidation under
  \#ifdef DO_NOT_DEFINE.<br>
  substractNegPools.body.make.pl will then copy this file, strip
  some of the comments, and append to it the body of 
  substractNegPoolsFromUnitsInclInval, obtained by copying the 
  body of substractNegPoolsFromUnits and removing the 
  \#ifdef DO_NOT_DEFINE and corresponding \#endifs.
  
  NOTE: the comment-stripping in substractNegPools.body.make.pl is
  very rudimentary, so compare the script's output with this file
  if something is strange.
*/

/* never define this! it's only used by substractNegPools.body.make.pl */
#undef DO_NOT_DEFINE


/*!
  \brief Return a unitClosures, where every unit marked invalid in myUnitsP
  is TRASHED (it doesn't exist in the returned unitClosures)

  At the end of the function:
  - nbOfCLosures and nbValid are set correctly ;
  - negPools and faintPools are the result of substracting 
    currentClosureP->negPools from each valid unit closure's 
    negPools and faintPools in myUnits;
  - negPoolCosts and scores are copies of myUnits, but updated 
    to reflect the currentClosureP->negPools substractions;
  - posPools and weakPools are simply copied from myUnitsP;
  - valid is initially all TRUE (since any invalid units in 
    myUnits are trashed), but is then updated as follows:
    - If any unit's negPoolCosts is (still) > maxNegPoolCost, 
      invalidate it;
    - Else if any unit's negPools+faintPools becomes empty, 
      update currentClosureP->posPools and currentClosureP->score 
      by doing the union with this unit's posPools and weakPools, 
      then invalidate the unit.
  In fact, the 2 invalidations just described are implemented 
  so that the invalidated units get overwritten: they are trashed 
  and don't exist in the returned unitClosures, just like the units 
  which were already invalid in myUnitsP.
  Therefore, all units in the returned unitClosures are VALID!

  In addition, it performs inclusion-invalidation (in its InclInval form):
  if any valid unit in myUnitsP contains the negPools+faintPools for 
  unit unitNum in myUnitsP, mark it as invalid in myUnitsP.<br>
  The justification is the following: the unit in question WILL be explored
  in the children of currentClosureP; and since unitNum's negpools+faintpools
  are included in it's negpools+faintpools, choosing it in a younger 
  brother of currentClosure is exactly equivalent to choosing it in some 
  child; hence we avoid doing the same work twice by only examining the 
  second situation.<br>
  If you use this feature, myUnitsP MUST BE substracted! (whereas with
  substractNegPoolsFromUnits, it doesn't matter).

  pre-condition: myUnitsP->nbValid > 0 (because we call buildEmptyUnitClosures, 
  and anyways there is no point in calling this function if no more valid 
  units exist).

  NOTE: this function modifies currentClosureP (adds some posPools), and in it's
  InclInval form it also changes myUnitsP (invalidates some units, update nbValid 
  accordingly).
*/
unitClosures* substractNegPoolsFromUnits(closure* currentClosureP, unitClosures* myUnitsP, 
#ifdef DO_NOT_DEFINE
					 int unitNum,
#endif /* DO_NOT_DEFINE */
					 int maxNegPoolCost, int nbPools)
{
#ifdef DEBUG
  /* count number of invalidations of each type */
  int invalInSource = 0 ;
  int invalTooBig = 0 ;
  int invalEmpty = 0 ;
#endif /* DEBUG */
  
#ifdef DO_NOT_DEFINE
  /* get the negPools for unit unitNum in myUnitsP (which must be substracted!) */
  const MOT* smallUnitNeg = getUnitNegPools(myUnitsP, unitNum, nbPools) ;
  const MOT* smallUnitFaint = getUnitFaintPools(myUnitsP, unitNum, nbPools);
#endif /* DO_NOT_DEFINE */

  /* allocate all memory and initialize nbOfClosures.
   myUnitsP->nbValid > 0 is a pre-condition of substractNegPoolsFromUnits, 
   so we can call buildEmptyUnitClosures safely */
  unitClosures* newUnitsP = buildEmptyUnitClosures(myUnitsP->nbValid, nbPools) ;

  /* number of units actually present in newUnitsP (ie not invalid
     in myUnitsP and not invalidated during substraction).
     At the end, set newUnitsP->nbValid and resize newUnitsP using 
     this value */
  int finalNbOfClosures = 0 ;

  /* number of MOTs to store a pools vector */
  int motsInPools = nbMotsPerPoolsVec(nbPools) ;
  /* number of bytes to store a pools vector */
  int bytesInPools = motsInPools * sizeof(MOT) ;

  /* pointers where the next unit's data comes from */
  const MOT* srcNegPools = myUnitsP->negPools ;
  const MOT* srcFaintPools = myUnitsP->faintPools ;
  const int* srcNegPoolCosts = myUnitsP->negPoolCosts ;
  const MOT* srcPosPools = myUnitsP->posPools ;
  const MOT* srcWeakPools = myUnitsP->weakPools ;
  const int* srcScores = myUnitsP->scores ;
  bool* srcValid = myUnitsP->valid ; /* not const, for inclusion-invalidation */

  /* pointers where the next unit's data goes */
  MOT* dstNegPools = newUnitsP->negPools ;
  MOT* dstFaintPools = newUnitsP->faintPools ;
  int* dstNegPoolCosts = newUnitsP->negPoolCosts ;
  MOT* dstPosPools = newUnitsP->posPools ;
  MOT* dstWeakPools = newUnitsP->weakPools ;
  int* dstScores = newUnitsP->scores ;
  bool* dstValid = newUnitsP->valid ;

  int unitCounter ; /* counter for the src unit closure being substracted from */
  for (unitCounter= myUnitsP->nbOfClosures; unitCounter > 0; unitCounter--)
    {
      if (! *srcValid)
	{
	  /* this unit is invalid, skip it */
	  srcNegPools += motsInPools ;
	  srcFaintPools += motsInPools ;
	  /* other src pointers will get incremented at the end, whether
	     current unit is valid or not */
	}
      else
	{
	  /* copy negPoolCosts and scores */
	  *dstNegPoolCosts = *srcNegPoolCosts ;
	  *dstScores = *srcScores ;
	  /* substract currentNegPools from this unit's negpools and faintpools */
	  const MOT* currentNegPools = currentClosureP->negPools ;
	  
#ifdef DO_NOT_DEFINE
	  /* invalidateInSrc: TRUE if current unit should be invalidated in 
	     myUnitsP for inclusion.
	     If it becomes FALSE (ie we have found that there is no inclusion),
	     the inclusion test is no longer performed */
	  bool invalidateInSrc = TRUE ;
	  const MOT* thisSmallUnitNeg = smallUnitNeg ;
	  const MOT* thisSmallUnitFaint = smallUnitFaint ;
#endif /* DO_NOT_DEFINE */

	  int motCounter ;
	  for (motCounter = motsInPools ; motCounter > 0 ; motCounter--)
	    {
	      /* substract from neg pools */
	      *dstNegPools = (*srcNegPools) & ~(*currentNegPools) ;
	      /* diffBits holds a 1 whenever src and dst are different */
	      MOT diffBits = (*srcNegPools) & (*currentNegPools) ;
	      while(diffBits != 0)
		{
		  /* clear the lowest-weight 1 bit in diffBits */
		  diffBits &= (diffBits-1) ;
		  (*dstNegPoolCosts) -= DIST_NEG ;
		  (*dstScores) += DIST_NEG ;
		}

	      /* substract from faint pools */
	      *dstFaintPools = (*srcFaintPools) & ~(*currentNegPools) ;
	      /* diffBits holds a 1 whenever src and dst are different */
	      diffBits = (*srcFaintPools) & (*currentNegPools) ;
	      while(diffBits != 0)
		{
		  /* clear the lowest-weight 1 bit in diffBits */
		  diffBits &= (diffBits-1) ;
		  (*dstNegPoolCosts) -= DIST_FAINT ;
		  (*dstScores) += DIST_FAINT ;
		}
	      
#ifdef DO_NOT_DEFINE
	      /* inclusion invalidation: */
	      if (invalidateInSrc)
		{
		  if ( (((*thisSmallUnitNeg) & ~(*srcNegPools)) != 0) || 
		       (((*thisSmallUnitFaint) & ~(*srcFaintPools)) != 0) )
		    /* some bit is at 1 in smallUnitNeg or Faint and at 0 in srcNeg or srcFaint: no inclusion */
		    invalidateInSrc = FALSE ;
		  else
		    /* this mot of smallUnitNeg is included in srcNeg, try next MOT */
		    {
		      thisSmallUnitNeg++ ;
		      thisSmallUnitFaint++ ;
		    }
		}

#endif /* DO_NOT_DEFINE */

	      srcNegPools++ ;
	      srcFaintPools++ ;
	      currentNegPools++ ;
	      dstNegPools++ ;
	      dstFaintPools++ ;
	    }

#ifdef DO_NOT_DEFINE
	  /* if invalidateInSrc is TRUE, invalidate current unit in myUnitsP */
	  if (invalidateInSrc)
	    {
#ifdef DEBUG
	      invalInSource++ ;
#endif /* DEBUG */
	      *srcValid = FALSE ;
	      myUnitsP->nbValid-- ;
	    }
#endif /* DO_NOT_DEFINE */


	  /* Now perform the invalidation tests on newUnitsP: */

	  /* if current dst unit's negPools+faintPools is now empty, update 
	     currentClosure's posPools and score by doing the union with 
	     ((srcPos+srcWeak) - currentPos); then invalidate the dst unit */
	  if ((*dstNegPoolCosts) == 0)
	    {
	      MOT* currentPosPools = currentClosureP->posPools ;
	      /* copy srcPosPools so we can still increment it in a uniform way at
		 the end of the "for unitCounter" loop, along with the other src pointers */
	      const MOT* srcPosPools2 = srcPosPools ;
	      const MOT* srcWeakPools2 = srcWeakPools ;
	      for (motCounter = motsInPools ; motCounter > 0 ; motCounter--)
		{
		  /* diffBits: bits that will be turned on in currentPos, coming from srcPos */
		  MOT diffBits = (*srcPosPools2) & ~(*currentPosPools) ;
		  /* update currentPos (AFTER calculating diffBits!) */
		  *currentPosPools = (*srcPosPools2) | (*currentPosPools) ;
		  while(diffBits != 0)
		    {
		      /* clear the lowest-weight 1 bit in diffBits */
		      diffBits &= (diffBits-1) ;
		      currentClosureP->score += DIST_POS ;
		    }

		  /* diffBits: bits that will be turned on in currentPos, coming from srcWeak */
		  diffBits = (*srcWeakPools2) & ~(*currentPosPools) ;
		  /* update currentPos (AFTER calculating diffBits!) */
		  *currentPosPools = (*srcWeakPools2) | (*currentPosPools) ;
		  while(diffBits != 0)
		    {
		      /* clear the lowest-weight 1 bit in diffBits */
		      diffBits &= (diffBits-1) ;
		      currentClosureP->score += DIST_WEAK ;
		    }
		  currentPosPools++ ;
		  srcPosPools2++ ;
		  srcWeakPools2++ ;
		}
	      /* invalidate this unit in newUnitsP: simply restore dstNegPools and don't 
		 increment other dst pointers */
	      
	      dstNegPools -= motsInPools ;
	      dstFaintPools -= motsInPools ;
#ifdef DEBUG
	      invalEmpty++ ;
#endif /* DEBUG */
	    }

	  /* else if current dst unit's negPoolCost is too big to be of any use, 
	     invalidate it (in dst, ie just don't increment the dst pointers) */
	  else if ((*dstNegPoolCosts) > maxNegPoolCost)
	    {
	      dstNegPools -= motsInPools ;
	      dstFaintPools -= motsInPools ;
#ifdef DEBUG
	      invalTooBig++ ;
#endif /* DEBUG */
	    }

	  /* else, current unit in newUnitsP remains valid: increment pointers and copy posPools */
	  else
	    {
	      /* set dstValid */
	      *dstValid = TRUE ;
	      /* copy posPools */
	      memcpy(dstPosPools, srcPosPools, bytesInPools) ;
	      memcpy(dstWeakPools, srcWeakPools, bytesInPools) ;
	      /* increment pointers (except dstNegPools and dstFaintPools, 
		 which are already set for the next unit) */
	      dstNegPoolCosts++ ;
	      dstPosPools += motsInPools ;
	      dstWeakPools += motsInPools ;
	      dstScores++ ;
	      dstValid++ ;
	      /* also increment finalNbOfClosures */
	      finalNbOfClosures++ ;
	    }
	}

      srcNegPoolCosts++ ;
      srcPosPools += motsInPools ;
      srcWeakPools += motsInPools ;
      srcScores++ ;
      srcValid++ ;
    }

  /* finally, resize newUnitsP to the number of units that were really built */
  resizeUnitClosures(newUnitsP, finalNbOfClosures, nbPools) ;
  /* all units in newUnitsP are valid, set nbValid */
  newUnitsP->nbValid = finalNbOfClosures ;

  
#ifdef DEBUG
  fprintf(stderr,
	  "In substractNegPoolsFromUnits: invalidated %d in source, %d in new for being too big, and %d in new for being empty.\n",
	  invalInSource, invalTooBig, invalEmpty) ;
#endif /* DEBUG */

  return(newUnitsP) ;
}

