/*----------------------------------------------------------------*
 *
 * File : orderVectors.c
 * Author : NTM
 * Created : 01/07/06
 *
 *
 * 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
 *
 *-----------------------------------------------------------------*/

#include <stdio.h> // for printing
#include <stdlib.h> // malloc, exit...

#include "unitClosures.h" /* unitClosures */

#include "orderVectors.h"



/************************************************************************
 ******************* EXPORTED FUNCTIONS *********************************
 ************************************************************************/


/*!
  \brief return an orderVector of the indicated totalSize.
  unitNums is allocated but UNINITIALIZED, totalSize is 
  correctly set, and size and firstValid are 0.
  pre-condition: totalSize > 0.
*/
orderVector* buildVector(int totalSize)
{
  if (totalSize <= 0)
    {
      fprintf(stderr, "in buildVector, totalSize (%d) <= 0. Don't do this.\n", totalSize) ;
      exit(1) ;
    }

  orderVector* myVector = (orderVector*)malloc(sizeof(orderVector)) ;
  if (myVector == NULL)
    {
      fprintf(stderr, "in buildVector, no more memory for myVector\n") ;
      exit(1) ;
    }
  
  myVector->totalSize = totalSize ;
  myVector->size = 0 ;
  myVector->firstValid = 0 ;
  
  myVector->unitNums = (int*)malloc(totalSize*sizeof(int)) ;
  if (myVector->unitNums == NULL)
    {
      fprintf(stderr, "in buildVector, no more memory for unitNums\n") ;
      exit(1) ;
    }
  return(myVector) ;
}


/*!
  \brief free all memory relevant to myVector, including the 
  orderVector area itself.
*/
void freeVector(orderVector* myVector)
{
  free(myVector->unitNums) ;
  free(myVector) ;
}


/*!
  \brief fill myVector up to min(newSize,myVector->totalSize), 
  so that it holds the unitnums in myUnits of the
  units sorted by decreasing score.
  Previous unitnums (up to myVector->size) are not touched,
  but the newly added unitnums will all be valid units.
  Return: TRUE if myVector was modified, FALSE otherwise (ie if
  there were no more valid units to add).

  Algorithm: use insertion sort, because we can expect that 
  the units in myUnits are already somewhat sorted (they were
  sorted by decreasing initial score in the observed sig).
  In any case we must have a STABLE sort! otherwise the
  lastOldIndex related code must change!
*/
bool fillByScore(orderVector* myVector, unitClosures* myUnits, int newSize)
{
  /* shorthand notation */
  int* unitNums = myVector->unitNums ;

  int oldSize = myVector->size ;

  if (newSize <= oldSize)
    {
      fprintf(stderr, "fillByScore called with newSize (%d) <= oldSize (%d)\n",
	      newSize, oldSize) ;
      exit(1) ;
    }

  /* use newSize = min(newSize,totalSize) */
  if (newSize > myVector->totalSize)
    newSize = myVector->totalSize ;

  /* We won't touch the first myVector->size unitnums, but when 
     examining a new unit we have to know whether it's already
     among these first myVector->size. */
  /* index == oldSize-1, works also if oldSize==0 */
  int lastOldIndex = oldSize - 1 ;
  int lastOldScore = 0 ; /* dummy value for compiler warning */
  if (lastOldIndex >= 0)
    /* otherwise unitNums[lastOldIndex] not defined and lastOldScore not needed */
    lastOldScore = myUnits->scores[unitNums[lastOldIndex]] ;
  
  /* 
     Now:
     - any unit of score > lastOldScore must be already present in unitNums;
     - any unit of score < lastOldScore must be absent from unitNums;
     - if a unit's score is lastOldScore: if its unitNum is 
     <= unitNums[lastOldIndex], it is already present; otherwise it is not. 
     This uses the fact that our sort is stable. 
     CAVEAT: keep the sort stable!
  */

  /* we now examine each unit from myUnits */
  int i ; /* index of current unit in myUnits */
  int lastSorted ; /* index in unitNum of the last sorted unitNum */

  for (i=0, lastSorted=lastOldIndex ; i < myUnits->nbOfClosures ; i++)
    {
      /* invariant: all unitNum's in unitNums[0..lastSorted] are sorted */
      if (! myUnits->valid[i])
	/* unit i is invalid, just skip it */
	continue ;
      else
	{
	  /* see if i is among the old portion of unitNums */
	  int currentScore = myUnits->scores[i] ;

	  /* only do these tests if oldSize != 0 */
	  if (oldSize != 0)
	    {
	      if (currentScore > lastOldScore)
		/* already present and sorted, skip */
		continue ;
	      else if ((currentScore == lastOldScore) && (i <= unitNums[lastOldIndex]))
		/* already present, skip! */
		continue ;
	    }
	  if (lastSorted >= newSize-1)
	    {
	      /* unitNums full, if i gets inserted it kicks someone out */
	      if (currentScore > myUnits->scores[unitNums[lastSorted]])
		lastSorted-- ;
	      else
		/* i can be skipped */
		continue ;
	    }

	  /* place i (seen as a unitnum) at the 
	     right place in unitNum[oldSize..lastSorted+1] */
	  int j ;
	  for (j=lastSorted+1; (j>oldSize) && (myUnits->scores[unitNums[j-1]] < currentScore); j--)
	    unitNums[j] = unitNums[j-1] ;
	  
	  unitNums[j] = i ;
	  lastSorted++ ;
	}
    }

  /* set new size, can be smaller than newSize if we had many invalid units */
  myVector->size = lastSorted + 1 ;

  if (myVector->size != oldSize)
    return(TRUE) ;
  else
    return(FALSE) ;
}


/*!
  \brief fill myVector up to min(newSize,myVector->totalSize), 
  so that it holds the unitnums in myUnits of the
  units sorted by increasing negPoolsCost.
  Previous unitnums (up to myVector->size) are not touched,
  but the newly added unitnums will all be valid units.
  Return: TRUE if myVector was modified, FALSE otherwise (ie if
  there were no more valid units to add).

  Algorithm: use insertion sort, because we can expect that 
  the units in myUnits are already somewhat sorted (they were
  sorted by decreasing initial score in the observed sig,
  and score and negPoolCost are negatively correlated).
  In any case we must have a STABLE sort! otherwise the
  lastOldIndex related code must change!

  Code is very similar to fillByScore except we sort by
  increasing values (not decreasing).
*/
bool fillByCost(orderVector* myVector, unitClosures* myUnits, int newSize)
{
  /* shorthand notation */
  int* unitNums = myVector->unitNums ;

  int oldSize = myVector->size ;

  if (newSize <= oldSize)
    {
      fprintf(stderr, "fillByCost called with newSize (%d) <= oldSize (%d)\n",
	      newSize, oldSize) ;
      exit(1) ;
    }

  /* use newSize = min(newSize,totalSize) */
  if (newSize > myVector->totalSize)
    newSize = myVector->totalSize ;

  /* We won't touch the first myVector->size unitnums, but when 
     examining a new unit we have to know whether it's already
     among these first myVector->size. */
  /* index == oldSize-1, works also if oldSize==0 */
  int lastOldIndex = oldSize - 1 ;
  int lastOldCost = 0 ; /* dummy value for compiler warning */
  if (lastOldIndex >= 0)
    /* otherwise unitNums[lastOldIndex] not defined and lastOldCost not needed */
    lastOldCost = myUnits->negPoolCosts[unitNums[lastOldIndex]] ;
  
  /* 
     Now:
     - any unit of cost < lastOldCost must be already present in unitNums;
     - any unit of cost > lastOldCost must be absent from unitNums;
     - if a unit's cost is lastOldCost: if its unitNum is 
     <= unitNums[lastOldIndex], it is already present; otherwise it is not. 
     This uses the fact that our sort is stable. 
     CAVEAT: keep the sort stable!
  */

  /* we now examine each unit from myUnits */
  int i ; /* index of current unit in myUnits */
  int lastSorted ; /* index in unitNum of the last sorted unitNum */

  for (i=0, lastSorted=lastOldIndex ; i < myUnits->nbOfClosures ; i++)
    {
      /* invariant: all unitNum's in unitNums[0..lastSorted] are sorted */
      if (! myUnits->valid[i])
	/* unit i is invalid, just skip it */
	continue ;
      else
	{
	  /* see if i is among the old portion of unitNums */
	  int currentCost = myUnits->negPoolCosts[i] ;

	  /* only do these tests if oldSize != 0 */
	  if (oldSize != 0)
	    {
	      if (currentCost < lastOldCost)
		/* already present and sorted, skip */
		continue ;
	      else if ((currentCost == lastOldCost) && (i <= unitNums[lastOldIndex]))
		/* already present, skip! */
		continue ;
	    }
	  if (lastSorted >= newSize-1)
	    {
	      /* unitNums full, if i gets inserted it kicks someone out */
	      if (currentCost < myUnits->negPoolCosts[unitNums[lastSorted]])
		lastSorted-- ;
	      else
		/* i can be skipped */
		continue ;
	    }

	  /* place i (seen as a unitnum) at the 
	     right place in unitNum[oldSize..lastSorted+1] */
	  int j ;
	  for (j=lastSorted+1; (j>oldSize) && (myUnits->negPoolCosts[unitNums[j-1]] > currentCost); j--)
	    unitNums[j] = unitNums[j-1] ;
	  
	  unitNums[j] = i ;
	  lastSorted++ ;
	}
    }

  /* set new size, can be smaller than newSize if we had many invalid units */
  myVector->size = lastSorted + 1 ;

  if (myVector->size != oldSize)
    return(TRUE) ;
  else
    return(FALSE) ;
}

