1/* BEGIN LICENSE BLOCK
2 * Version: CMPL 1.1
3 *
4 * The contents of this file are subject to the Cisco-style Mozilla Public
5 * License Version 1.1 (the "License"); you may not use this file except
6 * in compliance with the License.  You may obtain a copy of the License
7 * at www.eclipse-clp.org/license.
8 *
9 * Software distributed under the License is distributed on an "AS IS"
10 * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied.  See
11 * the License for the specific language governing rights and limitations
12 * under the License.
13 *
14 * The Original Code is  The ECLiPSe Constraint Logic Programming System.
15 * The Initial Developer of the Original Code is  Cisco Systems, Inc.
16 * Portions created by the Initial Developer are
17 * Copyright (C) 1997-2006 Cisco Systems, Inc.  All Rights Reserved.
18 *
19 * Contributor(s): Joachim Schimpf, IC-Parc
20 *
21 * END LICENSE BLOCK */
22/*----------------------------------------------------------------------
23* System:	ECLiPSe Constraint Logic Programming System
24* Version:	$Id: edge_finder.c,v 1.1 2006/09/23 01:53:26 snovello Exp $
25*----------------------------------------------------------------------*/
26
27/*
28 * Description:		Edge-finder in C
29 *			Nuijten's algorithms
30 *
31 * Author:		J.Schimpf, IC-Parc
32 *
33 */
34
35#include "eclipse.h"
36
37#ifdef STDC_HEADERS
38#include <stdlib.h>	/* for malloc() */
39#endif
40
41#define BOUND2
42#define BOUND3
43#define SET_BOOLEANS
44
45#ifndef NULL
46#define NULL 0
47#endif
48
49#define DOMAIN_MINF (-10000000)
50#define DOMAIN_PINF (10000000)
51
52#define OPT_QUADR	0
53#define OPT_CUBIC	1	/* bit-significant */
54#define OPT_BOOLS	2	/* bit-significant */
55
56typedef struct {
57    long	est, lst;	/* earliest/latest start time */
58    long	ect, lct;	/* earliest/latest completion time */
59    long	size;		/* size (resource usage) */
60    long	sz;		/* size index */
61    long	dur;		/* (min) duration */
62    long	area;		/* area, ie. size*duration */
63    long	lb, ub;		/* new bounds on start time */
64} task_t;
65
66typedef struct {
67    task_t	**asc_lct;	/* [ntasks] */
68    task_t	**asc_est;	/* [ntasks] */
69    task_t	*tasks;		/* [ntasks] */
70    long	*sizes;		/* [ntasks], only nsizes used */
71    long	*_G;		/* [ntasks*nsizes_max], may get reallocated */
72    long	*ECT;		/* [ntasks], also LST */
73    long	ntasks;
74    long	nsizes;		/* number of valid entries in sizes[] */
75    long	nsizes_max;	/* tracks the maximum of nsizes */
76    long	some_size_changed; /* bool: one or more tasks changed size */
77    long	capacity;
78    long	refcnt;
79    long	option;
80} ef_t;
81
82#define G(i)	(ef->_G + (i)*ef->nsizes)
83#define Size(j)	(ef->sizes[j])
84#define LST	ECT
85#define DELTA	ECT
86#define TaskNr(t)	((t)-ef->tasks)
87
88static void _ef_desc_free();
89static t_ext_ptr _ef_desc_copy();
90static pword _ef_desc_get();
91
92static t_ext_type ef_desc = {
93    _ef_desc_free,
94    _ef_desc_copy,
95    NULL,NULL,NULL,NULL,
96    _ef_desc_copy,
97    _ef_desc_get,
98    NULL
99};
100
101
102static void
103_ef_desc_free(obj)
104t_ext_ptr obj;
105{
106    ef_t *ef = (ef_t *)obj;
107    if (--ef->refcnt == 0)
108    {
109	free(ef->tasks);
110	free(ef->asc_est);
111	free(ef->asc_lct);
112	free(ef->sizes);
113	free(ef->ECT);
114	if (ef->_G)
115	    free(ef->_G);
116	free(ef);
117    }
118}
119
120static t_ext_ptr
121_ef_desc_copy(obj)
122t_ext_ptr obj;
123{
124    ((ef_t *)obj)->refcnt++;
125    return obj;
126}
127
128static pword
129_ef_desc_get(obj, i)
130t_ext_ptr obj;
131int i;
132{
133    return ec_term(ec_did("task",2),
134/*
135    return ec_term(ec_did("task",9),
136    	 ec_long(((ef_t *) obj)->tasks[i].est),
137    	 ec_long(((ef_t *) obj)->tasks[i].lst),
138    	 ec_long(((ef_t *) obj)->tasks[i].ect),
139    	 ec_long(((ef_t *) obj)->tasks[i].lct),
140    	 ec_long(((ef_t *) obj)->tasks[i].sz),
141    	 ec_long(((ef_t *) obj)->tasks[i].dur),
142    	 ec_long(((ef_t *) obj)->tasks[i].area),
143*/
144    	 ec_long(((ef_t *) obj)->tasks[i].lb),
145    	 ec_long(((ef_t *) obj)->tasks[i].ub)
146    );
147}
148
149int
150ec_init_ef( /* +N, +Capacity, +Option, -EfHandle */ )
151{
152    ef_t *ef;
153    long i,n,cap,opt;
154
155    if (ec_get_long(ec_arg(1), &n) != PSUCCEED)
156    	return TYPE_ERROR;
157    if (ec_get_long(ec_arg(2), &cap) != PSUCCEED)
158    	return TYPE_ERROR;
159    if (n <= 0)
160    	return RANGE_ERROR;
161    if (ec_get_long(ec_arg(3), &opt) != PSUCCEED)
162    	return TYPE_ERROR;
163
164    ef = (ef_t *) malloc(n*sizeof(ef_t));
165    ef->tasks = (task_t *) malloc(n*sizeof(task_t));
166    ef->asc_lct = (task_t **) malloc(n*sizeof(task_t*));
167    ef->asc_est = (task_t **) malloc(n*sizeof(task_t*));
168    ef->sizes = (long *) malloc(n*sizeof(long));
169    ef->ECT = (long *) malloc(n*sizeof(long));
170    for (i=0; i<n; i++)
171    {
172	ef->asc_lct[i] = ef->asc_est[i] = &ef->tasks[i];
173	ef->tasks[i].sz = n;	/* uninit */
174    }
175    ef->capacity = cap;
176    ef->ntasks = n;
177    ef->nsizes = ef->nsizes_max = 0;
178    ef->_G = NULL;
179    ef->refcnt = 1;
180    ef->option = opt;
181    ef->some_size_changed = 1;
182
183    return ec_unify_arg(4, ec_handle(&ef_desc, (t_ext_ptr)ef));
184}
185
186int
187ec_init_task( /*EfHandle,I,Est,Lst,Ect,Lct,Sz,Dur,Area*/ )
188{
189    ef_t *ef;
190    long i, size;
191
192    if (ec_get_handle(ec_arg(1), &ef_desc, (t_ext_ptr*)&ef) != PSUCCEED ||
193	ec_get_long(ec_arg(2), &i) != PSUCCEED ||
194	ec_get_long(ec_arg(3), &ef->tasks[i].est) != PSUCCEED ||
195	ec_get_long(ec_arg(4), &ef->tasks[i].lst) != PSUCCEED ||
196	ec_get_long(ec_arg(5), &ef->tasks[i].ect) != PSUCCEED ||
197	ec_get_long(ec_arg(6), &ef->tasks[i].lct) != PSUCCEED ||
198	ec_get_long(ec_arg(7), &size) != PSUCCEED ||
199	ec_get_long(ec_arg(8), &ef->tasks[i].dur) != PSUCCEED ||
200	ec_get_long(ec_arg(9), &ef->tasks[i].area) != PSUCCEED
201    )
202    {
203    	return TYPE_ERROR;
204    }
205
206    ef->tasks[i].lb = ef->tasks[i].est;
207    ef->tasks[i].ub = ef->tasks[i].lst;
208
209    if (!ef->some_size_changed  &&  size != ef->tasks[i].size)
210	ef->some_size_changed = 1;
211    ef->tasks[i].size = size;
212
213    return PSUCCEED;
214}
215
216static void
217_construct_size_table(ef)
218ef_t *ef;
219{
220    long i;
221    ef->nsizes = 0;
222    for (i=0; i<ef->ntasks; ++i)
223    {
224	long j = 0;		/* lookup */
225	while (j < ef->nsizes  &&  ef->tasks[i].size != Size(j))
226	    ++j;
227	if (j == ef->nsizes)	/* new size */
228	{
229	    Size(j) = ef->tasks[i].size;
230	    ++ef->nsizes;
231	}
232	ef->tasks[i].sz = j;
233    }
234    if (ef->nsizes > ef->nsizes_max)
235    {
236	/* we have more sizes than ever: need a bigger array for G */
237	ef->nsizes_max = ef->nsizes;
238	if (ef->_G)
239	    ef->_G = (long*) realloc(ef->_G, sizeof(long)*ef->nsizes_max*ef->ntasks);
240	else
241	    ef->_G = (long*) malloc(sizeof(long)*ef->nsizes_max*ef->ntasks);
242    }
243    ef->some_size_changed = 0;
244    return;
245}
246
247static int
248_asc_lct(t1, t2)
249task_t **t1, **t2;
250{
251    return (*t1)->lct > (*t2)->lct ? 1 : (*t1)->lct < (*t2)->lct ? -1 : 0;
252}
253
254static int
255_asc_est(t1, t2)
256task_t **t1, **t2;
257{
258    return (*t1)->est > (*t2)->est ? 1 : (*t1)->est < (*t2)->est ? -1 : 0;
259}
260
261#define upd_max(max, expr) {\
262	long _tmp = (expr);\
263	if (_tmp > max) max = _tmp;\
264}
265
266#define upd_min(min, expr) {\
267	long _tmp = (expr);\
268	if (_tmp < min) min = _tmp;\
269}
270
271#define upd_max_f(max, expr) {\
272	double _tmp = (expr);\
273	if (_tmp > max) max = _tmp;\
274}
275
276#define upd_min_f(min, expr) {\
277	double _tmp = (expr);\
278	if (_tmp < min) min = _tmp;\
279}
280
281#define Before(ti,tj) {\
282	int err = _before(ef, bools, ti, tj);\
283	if (err != PSUCCEED) return err;\
284}
285
286
287/* Set boolean such that Ti is before tj */
288
289static int
290_before(ef, bools, ti, tj)
291ef_t *ef;
292pword bools;
293task_t *ti, *tj;
294{
295    int err, idx;
296    long zero_one;
297    pword var;
298    int i = TaskNr(ti);
299    int j = TaskNr(tj);
300    if (i < j) { idx = j*(j-1)/2+i+1; zero_one = 0; }
301    else if (i > j) { idx = i*(i-1)/2+j+1; zero_one = 1; }
302    else return RANGE_ERROR;
303    err = ec_get_arg(idx, bools, &var);
304    if (err != PSUCCEED)
305    	return err;
306    return ec_unify(var, ec_long(zero_one));
307}
308
309int
310ec_ef_disj( /* EfHandle */ )
311{
312    ef_t *ef;
313    int y, x, i;
314    long g, h, p;
315    task_t **X, **Y;
316    pword bools;
317    bools = ec_arg(2);
318
319    if (ec_get_handle(ec_arg(1), &ef_desc, (t_ext_ptr*)&ef) != PSUCCEED)
320    	return TYPE_ERROR;
321
322    if (ec_get_nil(bools) != PSUCCEED)
323	ef->option |= OPT_BOOLS;
324
325    if (ef->some_size_changed)
326	_construct_size_table(ef);
327
328    qsort((void*) (ef->asc_lct), ef->ntasks, sizeof(task_t*), _asc_lct);
329    qsort((void*) (ef->asc_est), ef->ntasks, sizeof(task_t*), _asc_est);
330
331    Y = ef->asc_lct;
332    X = ef->asc_est;
333    for (y = 0; y < ef->ntasks; ++y)		/* asc lct */
334    {
335	if (y == ef->ntasks-1 || Y[y]->lct != Y[y+1]->lct)
336	{
337	    p = 0;
338	    g = DOMAIN_MINF;
339#ifdef BOUND2
340	    ef->ECT[ef->ntasks-1] = DOMAIN_PINF;
341#endif
342
343	    for (i = ef->ntasks-1; i >= 0; --i)	/* desc est */
344	    {
345		if (X[i]->lct <= Y[y]->lct)
346		{
347		    p += X[i]->dur;
348		    upd_max(g, X[i]->est + p);
349		    if (g > Y[y]->lct)
350		    	return PFAIL;
351#ifdef BOUND2
352		    upd_min(ef->ECT[i], X[i]->ect);
353#endif
354		}
355		ef->_G[i] = g;
356#ifdef BOUND2
357		if (i > 0)
358		    ef->ECT[i-1] = ef->ECT[i];
359#endif
360	    }
361
362	    h = DOMAIN_MINF;
363	    for (x = 0; x < ef->ntasks; ++x)	/* asc est */
364	    {
365		if (X[x]->lct > Y[y]->lct)
366		{
367		    if (X[x]->est + p + X[x]->dur > Y[y]->lct)
368		    {
369			upd_max(X[x]->lb, ef->_G[x]);
370#ifdef SET_BOOLEANS
371			if (ef->option & OPT_BOOLS)
372			{
373			    int v;
374			    for (v = x+1; v < ef->ntasks && X[v]->est < Y[y]->lct; ++v)
375			    {
376			        if (X[v]->lct <= Y[y]->lct)
377				    Before(X[v],X[x]);
378			    }
379			}
380#endif
381		    }
382		    if (h + X[x]->dur > Y[y]->lct)
383		    {
384			upd_max(X[x]->lb, g);
385#ifdef SET_BOOLEANS
386			if (ef->option & OPT_BOOLS)
387			{
388			    int v;
389			    for (v = 0; v < ef->ntasks && X[v]->est < Y[y]->lct; ++v)
390			    {
391			        if (X[v]->lct <= Y[y]->lct)
392				    Before(X[v],X[x]);
393			    }
394			}
395#endif
396		    }
397		}
398		else
399		{
400		    upd_max(h, X[x]->est + p);
401		    p -= X[x]->dur;
402		}
403#ifdef BOUND2
404		if (ef->option & OPT_CUBIC)
405		{
406		    int w;
407		    /* duration of those that must start later than w and
408		     * finish before y */
409		    long Pp = p + X[x]->dur;
410		    /* what remains if x is first: */
411		    long avail = Y[y]->lct - X[x]->est;
412		    for (w = x-1; w >= 0; --w)	/* desc est */
413		    {
414			if (X[w]->lct <= Y[y]->lct)
415			{
416			    if (ef->ECT[w] <= X[x]->est)
417			    	break;
418			    Pp += X[w]->dur;
419			    if (Pp > avail)
420				/* x can't be first, must be after w */
421				upd_max(X[x]->lb, ef->ECT[w]);
422			}
423		    }
424		}
425#endif
426	    }
427	}
428    }
429
430    Y = ef->asc_est;
431    X = ef->asc_lct;
432    for (y = ef->ntasks-1; y >= 0; --y)		/* desc est */
433    {
434	if (y == 0 || Y[y]->est != Y[y-1]->est)
435	{
436	    p = 0;
437	    g = DOMAIN_PINF;
438#ifdef BOUND2
439	    ef->LST[0] = DOMAIN_MINF;
440#endif
441
442	    for (i = 0; i < ef->ntasks; ++i)	/* asc lct */
443	    {
444		if (X[i]->est >= Y[y]->est)
445		{
446		    p += X[i]->dur;
447		    upd_min(g, X[i]->lct - p);
448		    if (g < Y[y]->est)
449		    	return PFAIL;
450#ifdef BOUND2
451		    upd_max(ef->LST[i], X[i]->lst);
452#endif
453		}
454		ef->_G[i] = g;
455#ifdef BOUND2
456		if (i < ef->ntasks-1)
457		    ef->LST[i+1] = ef->LST[i];
458#endif
459	    }
460
461	    h = DOMAIN_PINF;
462	    for (x = ef->ntasks-1; x >= 0; --x)	/* desc lct */
463	    {
464		if (X[x]->est < Y[y]->est)
465		{
466		    if (X[x]->lct - p - X[x]->dur < Y[y]->est)
467		    {
468			upd_min(X[x]->ub, ef->_G[x] - X[x]->dur);
469#ifdef SET_BOOLEANS
470			if (ef->option & OPT_BOOLS)
471			{
472			    int v;
473			    for (v = x-1; v >= 0 && X[v]->lct > Y[y]->est; --v)
474			    {
475			        if (X[v]->est >= Y[y]->est)
476				    Before(X[x],X[v]);
477			    }
478			}
479#endif
480		    }
481		    if (h - X[x]->dur < Y[y]->est)
482		    {
483			upd_min(X[x]->ub, g - X[x]->dur);
484#ifdef SET_BOOLEANS
485			if (ef->option & OPT_BOOLS)
486			{
487			    int v;
488			    for (v = ef->ntasks-1; v >= 0 && X[v]->lct > Y[y]->est; --v)
489			    {
490			        if (X[v]->est >= Y[y]->est)
491				    Before(X[x],X[v]);
492			    }
493			}
494#endif
495		    }
496		}
497		else
498		{
499		    upd_min(h, X[x]->lct - p);
500		    p -= X[x]->dur;
501		}
502#ifdef BOUND2
503		if (ef->option & OPT_CUBIC)
504		{
505		    int w;
506		    long Pp = p + X[x]->dur;
507		    long avail = X[x]->lct - Y[y]->est;
508		    for (w = x+1; w < ef->ntasks; ++w)	/* asc lct */
509		    {
510			if (X[w]->est >= Y[y]->est)
511			{
512			    if (ef->LST[w] >= X[x]->lct)
513			    	break;
514			    Pp += X[w]->dur;
515			    if (Pp > avail)
516				upd_min(X[x]->ub, ef->LST[w] - X[x]->dur);
517			}
518		    }
519		}
520#endif
521	    }
522	}
523    }
524    return PSUCCEED;
525}
526
527int
528ec_ef_cum( /* EfHandle */ )
529{
530    ef_t *ef;
531    int y, x, i, j;
532    long l, Ar, cap;
533    long *g;
534    double H;
535    task_t **X, **Y;
536
537    if (ec_get_handle(ec_arg(1), &ef_desc, (t_ext_ptr*)&ef) != PSUCCEED)
538    	return TYPE_ERROR;
539
540    if (ef->some_size_changed)
541	_construct_size_table(ef);
542
543    cap = ef->capacity;
544
545    qsort((void*) (ef->asc_lct), ef->ntasks, sizeof(task_t*), _asc_lct);
546    qsort((void*) (ef->asc_est), ef->ntasks, sizeof(task_t*), _asc_est);
547
548    Y = ef->asc_lct;
549    X = ef->asc_est;
550    for (y = 0; y < ef->ntasks; ++y)		/* asc lct */
551    {
552	if (y == ef->ntasks-1 || Y[y]->lct != Y[y+1]->lct)
553	{
554	    /*
555	     * We are looking at all task intervals ending at Y[y]->lct
556	     */
557
558	    Ar = 0;
559	    l = DOMAIN_MINF;
560	    g = G(ef->ntasks-1);	/* first i in next loop */
561	    for (j = 0; j < ef->nsizes; ++j)
562		g[j] = DOMAIN_MINF;
563#ifdef BOUND2
564	    ef->ECT[ef->ntasks-1] = DOMAIN_PINF;
565#endif
566
567	    for (i = ef->ntasks-1; i >= 0; --i)	/* desc est */
568	    {
569		if (X[i]->lct <= Y[y]->lct)
570		{
571		    /*
572		     * We are looking at the task interval between
573		     * X[i]->est .. Y[y]->lct (the actual upper end is l).
574		     * We compute g[sz] which is a lower bound for the
575		     * start time of a task of size sz which starts
576		     * after this task interval.
577		     */
578
579		    Ar += X[i]->area;
580		    if (X[i]->est + (Ar-1+cap)/cap > Y[y]->lct)
581		    	return PFAIL;
582#ifdef BOUND2
583		    upd_min(ef->ECT[i], X[i]->ect);
584#endif
585		    upd_max(l, X[i]->lct);
586		    for (j = 0; j < ef->nsizes; ++j)
587		    {
588			long size_j = Size(j);
589			long rest = Ar - (l-X[i]->est) * (cap-size_j);
590			if (rest > 0)
591			    upd_max(g[j], X[i]->est + (rest-1+size_j)/size_j);
592		    }
593		}
594		if (i > 0)	/* init g for the next iteration */
595		{
596		    for (j = 0; j < ef->nsizes; ++j)
597			G(i-1)[j] = g[j];
598		    g = G(i-1);
599#ifdef BOUND2
600		    ef->ECT[i-1] = ef->ECT[i];
601#endif
602		}
603	    }
604
605	    /* We have now
606	     * Ar	area of the largest task interval ending at Y[y]->lct
607	     *		(we reconstruct the smaller ones by subtracting).
608	     * G[i,sz]	For each task interval X[i]->est..Y[y]->lct and
609	     *		each size sz of possible subsequent task: a lower
610	     *		bound on the start time of such a subsequent task.
611	     *		(the G[i] for tasks not belonging to the task
612	     *		intervals have the same contents as the next
613	     *		subsequent member).
614	     */
615	    /*
616	     * H is an obvious lower bound on the start times, computed by
617	     * assuming that all tasks in a task interval are packed to the
618	     * and executed with full capacity (fuly elastic relaxation).
619	     * This is a float because we can't round up and we would lose
620	     * information by rounding down.
621	     */
622	    H = (double) DOMAIN_MINF;
623	    for (x = 0; x < ef->ntasks; ++x)	/* asc est */
624	    {
625		if (X[x]->lct > Y[y]->lct)
626		{
627		    /* X[x] is a task not belonging to the
628		     * task intervals under consideration
629		     */
630		    if (Ar + X[x]->area > (Y[y]->lct - X[x]->est) * cap)
631		    {
632			/*
633			 * X[x] must be after all tasks between
634			 * X[x]->est..Y[y]->lct.
635			 * We could set ordering booleans here.
636			 */
637			/* Apply lower bound G on starting time */
638			upd_max(X[x]->lb, G(x)[X[x]->sz]);
639		    }
640
641		    /* If X[x] doesn't fit in before Y[y]->lct, it
642		     * must start after _all_ tasks before Y[y]->lct
643		     */
644		    if (H + ((double) X[x]->area)/cap > Y[y]->lct)
645		    {
646			upd_max(X[x]->lb, g[X[x]->sz]);
647		    }
648#ifdef BOUND3
649		    if ((ef->option & OPT_CUBIC) && Ar > 0)
650		    {
651			long Arp = Ar;
652			/* find the next member k of the task interval */
653			int k = x;
654			while (X[k]->lct > Y[y]->lct)
655			    ++k;
656			while (Arp > 0 && X[k]->est < X[x]->ect)
657			{
658			    if (Arp + (X[x]->ect - X[k]->est) * Size(X[x]->sz)
659			      > (Y[y]->lct - X[k]->est) * cap)
660			    {
661				upd_max(X[x]->lb, G(x)[X[x]->sz]);
662			    }
663			    Arp -= X[k]->area;
664			    ++k;
665			    if (Arp > 0)
666				while (X[k]->lct > Y[y]->lct)
667				    ++k;
668			}
669		    }
670#endif
671		}
672		else	/* X[x] is a member of some task interval */
673		{
674		    upd_max_f(H, X[x]->est + ((double) Ar)/cap);
675		    Ar -= X[x]->area;
676		}
677#ifdef BOUND2
678		if (ef->option & OPT_CUBIC)
679		{
680		    int w;
681		    /* area of tasks w..y without x */
682		    long Arp = Ar;
683		    /* what remains if x is first: */
684		    long ect_x = X[x]->ect < Y[y]->lct ? X[x]->ect : Y[y]->lct;
685		    for (w = x-1; w >= 0; --w)	/* desc est */
686		    {
687			if (X[w]->lct <= Y[y]->lct)
688			{
689			    if (ef->ECT[w] <= X[x]->est)
690			    	break;
691			    Arp += X[w]->area;
692			    if (Arp + (ect_x - X[w]->est) * Size(X[x]->sz)
693			      > (Y[y]->lct - X[w]->est) * cap)
694				/* x can't be first, must be after w */
695				upd_max(X[x]->lb, ef->ECT[w]);
696			}
697		    }
698		}
699#endif
700	    }
701	}
702    }
703
704    Y = ef->asc_est;
705    X = ef->asc_lct;
706    for (y = ef->ntasks-1; y >= 0; --y)		/* desc est */
707    {
708	if (y == 0 || Y[y]->est != Y[y-1]->est)
709	{
710	    Ar = 0;
711	    l = DOMAIN_PINF;
712	    g = G(0);			/* first i in next loop */
713	    for (j = 0; j < ef->nsizes; ++j)
714		g[j] = DOMAIN_PINF;
715#ifdef BOUND2
716	    ef->LST[0] = DOMAIN_MINF;
717#endif
718
719	    for (i = 0; i < ef->ntasks; ++i)	/* asc lct */
720	    {
721		if (X[i]->est >= Y[y]->est)
722		{
723		    Ar += X[i]->area;
724		    if (X[i]->lct - (Ar-1+cap)/cap < Y[y]->est)
725		    	return PFAIL;
726#ifdef BOUND2
727		    upd_max(ef->LST[i], X[i]->lst);
728#endif
729		    upd_min(l, X[i]->est);
730		    for (j = 0; j < ef->nsizes; ++j)
731		    {
732			long size_j = Size(j);
733			long rest = Ar - (X[i]->lct-l) * (cap-size_j);
734			if (rest > 0)
735			    upd_min(g[j], X[i]->lct - (rest-1+size_j)/size_j);
736		    }
737		}
738		if (i < ef->ntasks-1)
739		{
740		    for (j = 0; j < ef->nsizes; ++j)
741			G(i+1)[j] = g[j];
742		    g = G(i+1);
743#ifdef BOUND2
744		    ef->LST[i+1] = ef->LST[i];
745#endif
746		}
747	    }
748
749	    H = (double) DOMAIN_PINF;
750	    for (x = ef->ntasks-1; x >= 0; --x)	/* desc lct */
751	    {
752		if (X[x]->est < Y[y]->est)
753		{
754		    if (Ar + X[x]->area > (X[x]->lct - Y[y]->est) * cap)
755			upd_min(X[x]->ub, G(x)[X[x]->sz] - X[x]->dur);
756
757		    if (H - ((double) X[x]->area)/cap < Y[y]->est)
758			upd_min(X[x]->ub, g[X[x]->sz] - X[x]->dur);
759#ifdef BOUND3
760		    if ((ef->option & OPT_CUBIC) && Ar > 0)
761		    {
762			long Arp = Ar;
763			int k = x;
764			while (X[k]->est < Y[y]->est)
765			    --k;
766			while (Arp > 0 && X[k]->lct > X[x]->lst)
767			{
768			    if (Arp + (X[k]->lct - X[x]->lst) * Size(X[x]->sz)
769			      > (X[k]->lct - Y[y]->est) * cap)
770			    {
771				upd_min(X[x]->ub, G(x)[X[x]->sz] - X[x]->dur);
772			    }
773			    Arp -= X[k]->area;
774			    --k;
775			    if (Arp > 0)
776				while (X[k]->est < Y[y]->est)
777				    --k;
778			}
779		    }
780#endif
781		}
782		else
783		{
784		    upd_min_f(H, X[x]->lct - ((double) Ar)/cap);
785		    Ar -= X[x]->area;
786		}
787#ifdef BOUND2
788		if (ef->option & OPT_CUBIC)
789		{
790		    int w;
791		    long Arp = Ar;
792		    long lst_x = X[x]->lst > Y[y]->est ? X[x]->lst : Y[y]->est;
793		    for (w = x+1; w < ef->ntasks; ++w)	/* asc lct */
794		    {
795			if (X[w]->est >= Y[y]->est)
796			{
797			    if (ef->LST[w] >= X[x]->lct)
798			    	break;
799			    Arp += X[w]->area;
800			    if (Arp + (X[w]->lct - lst_x) * Size(X[x]->sz)
801			      > (X[w]->lct - Y[y]->est) * cap)
802				upd_min(X[x]->ub, ef->LST[w] - X[x]->dur);
803			}
804		    }
805		}
806#endif
807	    }
808	}
809    }
810    return PSUCCEED;
811}
812
813
814int
815ec_ef_quad( /* EfHandle */ )
816{
817    ef_t *ef;
818    int i, j, k;
819    task_t **Y;
820    long Sjk;
821    long Pjk;
822    long delta;
823
824    if (ec_get_handle(ec_arg(1), &ef_desc, (t_ext_ptr*)&ef) != PSUCCEED)
825    	return TYPE_ERROR;
826
827    qsort((void*) (ef->asc_lct), ef->ntasks, sizeof(task_t*), _asc_lct);
828
829    Y = ef->asc_lct;
830    for (j = 0; j < ef->ntasks; ++j)		/* asc lct */
831    {
832	Pjk = 0;
833	delta = DOMAIN_PINF;
834	for (k = 0; k <= j; ++k)
835	{
836	    if (Y[k]->lst >= Y[j]->lst)
837	    	Pjk += Y[k]->dur;
838	    /* Sjk = DOMAIN_MINF; upd_min(delta, Y[k]->lct - Sjk); */
839	    ef->DELTA[k] = delta;
840	}
841	for (; k < ef->ntasks; ++k)
842	{
843	    if (Y[k]->lst >= Y[j]->lst)
844	    	Pjk += Y[k]->dur;
845	    Sjk = Pjk;
846	    upd_min(delta, Y[k]->lct - Sjk);
847	    ef->DELTA[k] = delta;
848	}
849
850	for (i = 0; i < ef->ntasks; ++i)
851	{
852	    if (Y[i]->lst < Y[j]->lst)
853	    {
854		if (Y[i]->lst > delta)
855		    upd_max(Y[i]->lb, Y[j]->lst);
856	    }
857	    else
858	    {
859		if ((i>0 && Y[i]->lst > ef->DELTA[i-1])  ||  Y[i]->est > delta)
860		    upd_max(Y[i]->lb, Y[j]->lst);
861	    }
862	}
863    }
864
865#if 0
866    qsort((void*) (ef->asc_est), ef->ntasks, sizeof(task_t*), _asc_est);
867
868    Y = ef->asc_est;
869    for (y = ef->ntasks-1; y >= 0; --y)		/* desc est */
870    {
871
872    }
873#endif
874
875    return PSUCCEED;
876}
877