/******************************************************************************
*
* CHIP C V5
*
* Ownership: Copyright (c) 1992-2004 Cosytec SA
*
* Author:    COSYTEC
*            4 rue Jean Rostand
*            91893 Orsay Cedex, France
*            Tel. +33 1 60 19 37 38
*            Fax. +33 1 60 19 36 20
*            e-mail: cosytec@cosytec.fr
*
* Program:   Example of scheduling with disjunctive constraints: 5-segment bridge
*
* Sccs:      chip_bridge5.c
*
*******************************************************************************/

#ifndef LINT
static char SCCSid[] = "%W% %G%\n";
#endif

#include <stdio.h>
#include "chipc.h"

#define DECLARE_CHOICE	 TrailPtr	trail;
#define REMEMBER_CHOICE	 c_choice_remember(&trail);
#define UNDO_CHOICE	c_choice_undo(trail);


/****************************************************************************
 * DATA.
 ***************************************************************************/

#define SIZE		46

int 	start = 0, a1 = 1, a2 = 2, a3 = 3, a4 = 4, a5 = 5, a6 = 6,
	p1 = 7, p2 = 8,
	ue = 9,
	s1 = 10, s2 = 11, s3 = 12, s4 = 13, s5 = 14, s6 = 15,
	b1 = 16, b2 = 17, b3 = 18,  b4 = 19, b5 = 20, b6 = 21,
	ab1 = 22, ab2 = 23, ab3 = 24, ab4 = 25, ab5 = 26, ab6 = 27,
	m1  = 28, m2  = 29, m3  = 30, m4  = 31, m5  = 32, m6  = 33,
	l1  = 34, t1  = 35, t2  = 36, t3  = 37, t4  = 38, t5  = 39,
	ua  = 40, v1  = 41, v2  = 42, k1  = 43,  k2  = 44, stop = 45;


/*
 * Maximum of unit resources
 */

int max_crane = 1;
int max_bricklaying = 1;
int max_schal = 1;
int max_excavator = 1;
int max_ram = 1;
int max_pump = 1;
int max_caterpillar = 1;

/*
 * data arrays: number of tasks using a given resource
 */
int n_crane = 6;
int n_bricklaying = 6;
int n_schal = 6;
int n_excavator	= 6;
int n_ram = 2;
int n_pump = 6;
int n_caterpillar = 2;

/*
 * one array per machine: all tasks using this machine
 */
static int crane[6];
static int bricklaying[6];
static int schal[6];
static int excavator[6];
static int ram[2];
static int pump[6];
static int caterpillar[2];


/*
 * all starting dates of staks + their corresponding durations
 */
DvarPtr	array[SIZE+1];
int	duration[SIZE+1];

/*
 * Symbolic names of tasks.
 */
char 	*task_names[SIZE+1] = 
	{
	"start",
	"a1","a2","a3","a4","a5","a6",
	"p1","p2",
	"ue",
	"s1","s2","s3","s4","s5","s6",
        "b1","b2","b3","b4","b5","b6",
	"ab1","ab2","ab3","ab4","ab5","ab6",
	"m1","m2","m3","m4","m5","m6",
        "l1",
	"t1","t2","t3","t4","t5",
	"ua",
	"v1","v2","k1","k2",
	"stop"
	};

/*
 * we use the array disj[][] to build disjunctions, which are used
 * by the labeling routine.
 */
int	disj[200][2];
int	ndisj = 0;


int do_chip_init()
{
	int res = c_chip_init();
	switch (res){
	case 1:	 return 1;
	case 2:	printf("CHIPC Initialisation: Environment variable CHIPCDIR not set\n"); return 0;
	case 3:	printf("CHIPC Initialisation: File .chiplicence not found\n"); return 0;
	case 4:	printf("CHIPC Initialisation: File .chiplicence not accessible in read mode\n"); return 0;
	case 5:	printf("CHIPC Initialisation: CHIP licence invalid\n"); return 0;
	case 6:	printf("CHIPC Initialisation: Memory allocation error\n"); return 0;
	case 7:	printf("CHIPC Initialisation: Can not allocate hash coding tables\n"); return 0;
	case 8:	printf("CHIPC Initialisation not called\n"); return 0;
	case 9:	printf("CHIPC Initialisation already called\n"); return 1;
	default: printf("CHIPC Initialisation: impossible returned value\n"); return 0;	
	}
}


/****************************************************************************
 * PRINT RESULTS
 ***************************************************************************/


print_result(int size)
{
	int i;

	for(i=0;i<size;i++) {
		printf("%s\t", task_names[i]);
		c_domain_array_print(stdout, &array[i], 1);
		printf("\tduration = %d\n", duration[i]);
	}
	printf("\n");
}

/****************************************************************************
 * SET INPUT
 ***************************************************************************/
set_duration()
{
	duration[start] = 0;
	duration[a1] = 4; duration[a2] = 2; duration[a3] = 2; 
	duration[a4] = 2; duration[a5] = 2; duration[a6] = 5;
	duration[p1] = 20; duration[p2] = 13;
	duration[ue] = 10;
	duration[s1] = 8; duration[s2] = 4; duration[s3] = 4;
	duration[s4] = 4; duration[s5] = 4; duration[s6] = 10;
	duration[b1] = 1; duration[b2] = 1; duration[b3] = 1;
	duration[b4] = 1; duration[b5] = 1; duration[b6] = 1;
	duration[ab1] = 1; duration[ab2] = 1; duration[ab3] = 1;
	duration[ab4] = 1; duration[ab5] = 1; duration[ab6] = 1;
	duration[m1] = 16; duration[m2] = 8; duration[m3] = 8;
	duration[m4] = 8; duration[m5] = 8; duration[m6] = 20;
	duration[l1] = 2;
	duration[t1] = 12; duration[t2] = 12; duration[t3] = 12;
	duration[t4] = 12; duration[t5] = 12;
	duration[ua] = 10;
	duration[v1] = 15; duration[v2] = 10;
	duration[k1] = 0; duration[k2] = 0;
	duration[stop] = 0;
}

/****************************************************************************
 * SETUP CONSTRAINTS
 ***************************************************************************/
int prec(int t1, int t2)
{
	return (int)c_dom_domcst(array[t2], GREATER_EQUAL, array[t1], duration[t1]);
}

int	make_precedence()
{
	return (
	prec(start,a1) && prec(start,a2) && prec(start,a3) && 
	prec(start,a4) && prec(start,a5) && 
        prec(start,a6) && prec(start,ue) && 
	prec(a1,s1) && prec(a2,s2) && prec(a5,s5) && 
        prec(a6,s6) && prec(a3,p1) && prec(a4,p2) && 
	prec(p1,s3) && prec(p2,s4) && 
        prec(p1,k1) && prec(p2,k1) && 
	prec(s1,b1) && prec(s2,b2) && 
        prec(s3,b3) && prec(s4,b4) && prec(s5,b5) && prec(s6,b6) && 
	prec(b1,ab1) && 
        prec(b2,ab2) && prec(b3,ab3) && prec(b4,ab4) && 
	prec(b5,ab5) && prec(b6,ab6) && 
        prec(ab1,m1) && prec(ab2,m2) && prec(ab3,m3) && 
	prec(ab4,m4) && prec(ab5,m5) && 
        prec(ab6,m6) && prec(m1,t1) && prec(m2,t1) && 
	prec(m2,t2) && prec(m3,t2) && 
        prec(m3,t3) && prec(m4,t3) && prec(m4,t4) && 
	prec(m5,t4) && prec(m5,t5) && 
        prec(m6,t5) && prec(m1,k2) && prec(m2,k2) && 
	prec(m3,k2) && prec(m4,k2) && 
        prec(m5,k2) && prec(m6,k2) && prec(l1,t1) && 
	prec(l1,t2) && prec(l1,t3) && 
        prec(l1,t4) && prec(l1,t5) && prec(t1,v1) &&
	prec(t5,v2) && prec(t2,stop) && 
        prec(t3,stop) && prec(t4,stop) && prec(v1,stop) && prec(v2,stop) && 
	prec(ua,stop) && prec(k2,stop)
	);
}

int max_nf(int A, int B, int C)
{
	int	C1;	
	C1 = C + duration[A];
	/* Ba <= Aa + C1 === Aa >= Ba - C1 */
	return (int)c_dom_domcst(array[A], GREATER_EQUAL, array[B], (-C1));
}

int	make_max_nf()
{
	return (
	max_nf(start,l1,30) && 
	max_nf(a1,s1,3) && max_nf(a2,s2,3) && max_nf(a5,s5,3) && 
        max_nf(a6,s6,3) && 
	max_nf(p1,s3,3) && max_nf(p2,s4,3)
	);
}

int max_ef(int A, int B, int C)
{
	int	C1;	
	C1 = duration[A] + C - duration[B];
	/* Ba <= Aa + C1 === Aa >= Ba - C1 */
	return (int)c_dom_domcst(array[A], GREATER_EQUAL, array[B], (-C1));
}

int	make_max_ef()
{
	return (
	max_ef(s1,b1,4) && max_ef(s2,b2,4) && 
	max_ef(s3,b3,4) && max_ef(s4,b4,4) && 
	max_ef(s5,b5,4) && max_ef(s6,b6,4)
	);
}

int min_af(int A, int B, int C)
{
	return (int)c_dom_domcst(array[B], GREATER_EQUAL, array[A], C);
}

int	make_min_af()
{
	return (
	min_af(ue,s1,6) && min_af(ue,s2,6) && 
	min_af(ue,s3,6) && min_af(ue,s4,6) && 
	min_af(ue,s5,6) && min_af(ue,s6,6)
	);
}

int	min_sf(int A, int B, int C)
{
	int	C1;	
	C1 = C - duration[B];
	/* Ba <= Aa + C1 === Aa >= Ba - C1 */
	return (int)c_dom_domcst(array[A], GREATER_EQUAL, array[B], (-C1));
}

int	make_min_sf()
{
	return (
	min_sf(ua,m1,2) && min_sf(ua,m2,2) && min_sf(ua,m3,2) &&
	min_sf(ua,m4,2) && min_sf(ua,m5,2) && min_sf(ua,m6,2)
	);
}

int	min_nf(int A, int B, int C)
{
	DvarPtr	Aa,	Ba;
	int	C1;	
	int res = FALSE;

	Aa = array[A];
	Ba = array[B];
	C1 = C + duration[A];
	return (int)c_dom_domcst(Ba, GREATER_EQUAL, Aa, C1);
}

int	make_min_nf()
{
	return min_nf(start,l1,30);
}

	       
/****************************************************************************
 * CREATE DISJUNCTIONS
 ***************************************************************************/
int add_disj(int *mach, int n)
{
	int	i, j;
	for(i = 0; i < n; i++) 
		for(j = i + 1; j <  n; j++) {
			disj[ndisj][0] = mach[i];
			disj[ndisj][1] = mach[j];
			ndisj++;
			printf("\t[%s, %s]", task_names[mach[i]],
						task_names[mach[j]]);
			if (! (ndisj % 5))
				printf("\n");
		}
	return ndisj;
}

/****************************************************************************
 * Set up resource data
 * Each resource is described by an array which contains all tasks
 * which are using it.
***********************************************************/	
int make_disj()
{	


	crane[0] = l1; crane[1]	= t1; crane[2] = t2;
	crane[3] = t3; crane[4]	= t4; crane[5] = t5;

 	bricklaying[0] = m1; bricklaying[1] = m2; bricklaying[2] = m3;
	bricklaying[3] = m4; bricklaying[4] = m5; bricklaying[5] = m6;

	schal[0] = s1; schal[1] = s2; schal[2] = s3; schal[3] = s4;
	schal[4] = s5; schal[5] = s6;

	excavator[0] = a1; excavator[1] = a2; excavator[2] = a3;
	excavator[3] = a4; excavator[4] = a5; excavator[5] = a6;

	ram[0] = p1; ram[1] = p2;

	pump[0] = b1; pump[1] = b2; pump[2] = b3; pump[3] = b4;
	pump[4] = b5; pump[5] = b6;

	caterpillar[0] = v1; caterpillar[1] = v2;
	
	/*
	 * compute all disjuctions and save them in array disj
	 * ndisj is the maximum number of disjunctions
	 */

	ndisj = 0;
	add_disj(crane, n_crane);
	add_disj(bricklaying, n_bricklaying);
	add_disj(schal, n_schal);
	add_disj(excavator, n_excavator);
	add_disj(ram, n_ram);
	add_disj(pump, n_pump);
	add_disj(caterpillar, n_caterpillar);
	printf("\n % d disjs %\n", ndisj);

	return TRUE;
}

/****************************************************************************
 * SETUP DISJUNCTIONS --NONDETERMINISM--
 * This labeling is valid only for disjunctive constraints
 ***************************************************************************/

typedef struct {
	DvarPtr    *array;
	int         size;
	LabelingPtr info;
} Arg_minmax, *Arg_minmaxPtr;
	

int label_disj(int k_disj, int index)
{
	int		perm 	= 0;
	int		k	= 0;
	DECLARE_CHOICE;

	if (index >= k_disj) {
	  return	TRUE;
	} else {
	  REMEMBER_CHOICE
	  while(index < k_disj) {
	    if (c_dom_domcst(array[disj[index][1]], GREATER_EQUAL, array[disj[index][0]],
			     duration[disj[index][0]]) &&
		label_disj(k_disj, index+1)) {
	      return TRUE;
	    } 
	    UNDO_CHOICE

	    if (! perm) {
	      k = disj[index][0];
	      disj[index][0] = disj[index][1];
	      disj[index][1] = k;
	      perm++;
	    } else {
	      return FALSE;
            }
	  }
	}
	return FALSE;		
}

nosol(int step)
{
	printf("No solution until step: %d\n", step);
	exit(1);
}

int labeling(Arg_minmaxPtr arg)
{

	if (label_disj(ndisj, 0)) {
		return c_labeling(arg->array, arg->size, METHOD_FIRST_FAIL, arg->info);
	}
	return FALSE;
}

/****************************************************************************
 * The bridge main program
 ***************************************************************************/
bridge()
{
	int		Min = 0;
	int		Max = 200;
	int		step = 0;
	Labeling        info;
	Min_max		minmaxinfo;
	Arg_minmax      arg;

/*	DECLARE_CHOICE;*/

	/*
	 * Step 1: create all domain variables : starting dates
	 */
	c_create_domain_array(array, SIZE, Min, Max, INTERVAL);
	set_duration();

	/*
	 * Step 2: setup all constraints:precedence, etc...
	 */
	step++;
	if ( ! (make_precedence() && make_max_nf() && make_max_ef() &&
		make_min_af() && make_min_sf() && make_min_nf() ))
		nosol(step);
	/*
	 * step 3: setup disjunctions.
	 */
	step++;
	if (!make_disj()) nosol(step);

	/*
	 * Labeling info
	 */

	info.type 	= LABELING_INDOMAIN;
	info.indomain	= LABELING_INDOMAIN_MIN;
	info.middle	= 0;
	info.solution 	= LABELING_FIRST_SOL;
	info.continue_var = NULL;
	info.continue_all = NULL;	
	info.search_type = CHIP_DEFAULT_SEARCH;	

	/*
	 * Compute the optimal, solution.
	 */
        minmaxinfo.lower = 0;
	minmaxinfo.upper = 200;
	minmaxinfo.percent = 0;
	minmaxinfo.timeout = 0;
	minmaxinfo.optimal_solution_found = 0;
	minmaxinfo.print = TRUE;

	/*
	 * What to pass the labeling routine
	 */
	arg.array = array;
	arg.size  = SIZE;
	arg.info  = &info;

       if (c_min_max_user(labeling, (void *)&arg, array, SIZE, &array[stop], 1, &minmaxinfo)) {
	  fprintf(stdout, "\n Generating the optimal solution succeeds...\n");
	  print_result(SIZE);
	} else { 
	  fprintf(stdout, "\n Generating the optimal solution fails...\n");
	}
}

/****************************************************************************
 * MAIN PROGRAM
 ***************************************************************************/

int main()
{
	if (!do_chip_init()) return FALSE;
  c_wflags(64);

  c_debug_set_header(CHIP_DEBUG_DATE,"2004-05-07 19:27:05");
  c_debug_set_header(CHIP_DEBUG_SOLVER,"CHIPC 5.5.0.5");
  c_debug_set_header(CHIP_DEBUG_SOURCE,"Bridge in CHIP");
  c_debug_set_header(CHIP_DEBUG_CREATOR,"COSYTEC SA");
  c_debug_set_header(CHIP_DEBUG_CONTRIBUTOR,"COSYTEC SA");
  c_debug_set_header(CHIP_DEBUG_DESCRIPTION,"");
  c_debug_set_header(CHIP_DEBUG_PARAMETERS,"bridge5()");

  c_chip_debug_init(100000, 1024, 1);

	bridge();

	c_chip_debug_end();
	c_chip_end();
	fflush(stdout);
	return 0;
}