////////////////////////////////////////////////////////////////////
// DESCOUENS Francois Maitrise de Mathematiques ////////////////////
//    Universite de Marne-La-Vallee      ///////////////////////////
// $Id: chemin.cc,v 1.1.1.1 2003/09/19 15:11:47 nthiery Exp $
////////////////////////////////////////////////////////////////////

#include"chemin.h"
#include"stdio.h"
//Problem for solution : Find all the solutions in decrease lexicographic order verifying frames without slope.

//Function for the first list in decrease lexicographic order

integerList *WithoutSlopeFirst (long sum, long minLng, long maxLng, long start, integerList floor, integerList ceiling)
{
  long curPos = start;      //integer for current position
  long remSum = sum;    //integer for remaining sum
  long diff;            //integer for place in current position
 
  integerList result;  //solution vector

  if ( minLng <= 0 )
    minLng = 0;

  while (floor[curPos] <= remSum && curPos - start < maxLng && remSum != 0)   //filling with floor conditions while possible
    {   
      result.push_back(floor[curPos]);        //filling the current column with floor conditions
      remSum -= floor[curPos];                //modifie the remaining sum to fill
      curPos++;                                       //we advance of one column
    }
  if (remSum == 0 && curPos - start >= minLng)                //the floor condition give us a solution enough long
    return new integerList(result);
  if (remSum == 0 && curPos - start < minLng)                 //the floor condition give us a solution not enough long
    {
      while (curPos - start < minLng && floor[curPos] == 0)   // finding if we can complete with zero for having good min length
	{
	  result.push_back(0);
	  curPos++;
	}
      if (curPos - start < minLng)                            // not enough consecutive floor at zero for having good length
	return(NULL);
      return new integerList(result);                 // enough zero and we have the lex smallest
    }
  if (curPos - start< minLng)                                //the sum is reached before the min length
    return(NULL);                                   
  curPos--;                        // re-adjustement of curpos 
  
  while (curPos >= start)                             //we move back to place the remaining sum
    {
      diff = ceiling[curPos] - result[curPos - start];       //place free for filling the current column
      if (remSum <= diff)
	{
	  result[curPos - start] += remSum;                  //if there is enough place in current column we fill with
	  return new integerList(result);                    //all the remaining sum
	}
      result[curPos - start] = ceiling[curPos];              //else filling with ceiling and go back for find the next free column
      remSum -= diff;                                        //new value of remaining sum
      curPos--;                                              //we go back
    }
  if (curPos == start - 1)                                   //there is not enough place for put the sum in the diagramm
    return(NULL);                                            //the sum is too big for free space
  
  return new integerList(result) ;                         
}


integerList *WithoutSlopeNext(integerList first, long sum, long minLng, long maxLng, integerList floor , integerList ceiling)
{
  long curPos;             //current position starting from the end of the array
  long remSum = 0;;        //remaining sum
  long concat;             //integer for concatenation
  long temp1=0;
  
  integerList result;
  integerList *temp;
  curPos = first.size();
  do {
      if ((--curPos) < 0) return(NULL);
      remSum += first[curPos];
  }
  while (curPos <= minLng && first[curPos] == floor[curPos]);
 
  do {
    if ((--curPos) < 0) return(NULL);
    remSum += first[curPos];
  }
  while (curPos >= 0 && first[curPos] == ceiling[curPos]);
    
  // two case at the end of this while: curPos == 0 or first[curPos] == ceiling([curPos])

  while (1)
    {
	temp1 = floor[curPos];
	floor[curPos] = first[curPos]+1; 
	temp = WithoutSlopeFirst(remSum, minLng - curPos, maxLng - curPos, curPos , floor, ceiling);
	floor[curPos] = temp1;
	if (temp != NULL) 
	{
	    for (concat = 0; concat < curPos; concat++)
		result.push_back(first[concat]);                                 
	    for (concat = curPos; concat < curPos + (*temp).size(); concat++)
		result.push_back((*temp)[concat - curPos]);
	    return new integerList(result);
	}
	if ((--curPos) < 0) return(NULL);
	remSum +=first[curPos];
	
	while (first[curPos] == ceiling[curPos])
      	{
	    if ((--curPos) < 0) return(NULL);
	    remSum +=first[curPos];
	}
    }

}
   


