1/*
2 * Copyright 2007, Ingo Weinhold <bonefish@cs.tu-berlin.de>.
3 * All rights reserved. Distributed under the terms of the MIT License.
4 */
5
6#include "ComplexLayouter.h"
7
8#include <math.h>
9#include <stdio.h>
10#include <string.h>
11
12#include <new>
13
14#include <OS.h>
15#include <Size.h>
16
17#include <AutoDeleter.h>
18
19#include "LayoutOptimizer.h"
20#include "SimpleLayouter.h"
21
22
23//#define TRACE_COMPLEX_LAYOUTER	1
24#if TRACE_COMPLEX_LAYOUTER
25#	define TRACE(format...)	printf(format);
26#	define TRACE_ONLY(x)	x
27#else
28#	define TRACE(format...)
29#	define TRACE_ONLY(x)
30#endif
31
32using std::nothrow;
33
34
35// MyLayoutInfo
36class ComplexLayouter::MyLayoutInfo : public LayoutInfo {
37public:
38	MyLayoutInfo(int32 elementCount, int32 spacing)
39		: fCount(elementCount),
40		  fSpacing(spacing)
41	{
42		// We also store the location of the virtual elementCountth element.
43		// Thus fLocation[i + 1] - fLocation[i] is the size of the ith element
44		// (not considering spacing).
45		fLocations = new(nothrow) int32[elementCount + 1];
46	}
47
48	~MyLayoutInfo()
49	{
50		delete[] fLocations;
51	}
52
53	void InitFromSizes(int32* sizes)
54	{
55		fLocations[0] = 0;
56		for (int32 i = 0; i < fCount; i++)
57			fLocations[i + 1] = fLocations[i] + sizes[i] + fSpacing;
58	}
59
60	virtual float ElementLocation(int32 element)
61	{
62		if (element < 0 || element >= fCount)
63			return 0;
64
65		return fLocations[element];
66	}
67
68	virtual float ElementSize(int32 element)
69	{
70		if (element < 0 || element >= fCount)
71			return -1;
72
73		return fLocations[element + 1] - fLocations[element] - 1
74			- fSpacing;
75	}
76
77	virtual float ElementRangeSize(int32 position, int32 length)
78	{
79		if (position < 0 || length < 0 || position + length > fCount)
80			return -1;
81
82		return fLocations[position + length] - fLocations[position] - 1
83			- fSpacing;
84	}
85
86	void Dump()
87	{
88		printf("ComplexLayouter::MyLayoutInfo(): %" B_PRId32 " elements:\n",
89			fCount);
90		for (int32 i = 0; i < fCount + 1; i++) {
91			printf("  %2" B_PRId32 ": location: %4" B_PRId32 "\n", i,
92				fLocations[i]);
93		}
94	}
95
96public:
97	int32	fCount;
98	int32	fSpacing;
99	int32*	fLocations;
100};
101
102
103// Constraint
104struct ComplexLayouter::Constraint {
105	Constraint(int32 start, int32 end, int32 min, int32 max)
106		: start(start),
107		  end(end),
108		  min(min),
109		  max(max),
110		  next(NULL)
111	{
112		if (min > max)
113			max = min;
114		effectiveMax = max;
115	}
116
117	void Restrict(int32 newMin, int32 newMax)
118	{
119		if (newMin > min)
120			min = newMin;
121		if (newMax < max)
122			max = newMax;
123		if (min > max)
124			max = min;
125		effectiveMax = max;
126	}
127
128	bool IsSatisfied(int32* sumValues) const
129	{
130		int32 value = sumValues[end] - sumValues[start - 1];
131		return (value >= min && value <= max);
132	}
133
134	int32		start;
135	int32		end;
136	int32		min;
137	int32		max;
138	int32		effectiveMax;
139	Constraint*	next;
140};
141
142
143// SumItem
144struct ComplexLayouter::SumItem {
145	int32	min;
146	int32	max;
147	bool	minDirty;
148	bool	maxDirty;
149};
150
151
152// SumItemBackup
153struct ComplexLayouter::SumItemBackup {
154	int32	min;
155	int32	max;
156};
157
158
159// #pragma mark - ComplexLayouter
160
161
162// constructor
163ComplexLayouter::ComplexLayouter(int32 elementCount, float spacing)
164	: fElementCount(elementCount),
165	  fSpacing((int32)spacing),
166	  fConstraints(new(nothrow) Constraint*[elementCount]),
167	  fWeights(new(nothrow) float[elementCount]),
168	  fSums(new(nothrow) SumItem[elementCount + 1]),
169	  fSumBackups(new(nothrow) SumItemBackup[elementCount + 1]),
170	  fOptimizer(new(nothrow) LayoutOptimizer(elementCount)),
171	  fUnlimited(B_SIZE_UNLIMITED / (elementCount == 0 ? 1 : elementCount)),
172	  fMinMaxValid(false),
173	  fOptimizerConstraintsAdded(false)
174{
175	if (fConstraints)
176		memset(fConstraints, 0, sizeof(Constraint*) * fElementCount);
177
178	if (fWeights) {
179		for (int32 i = 0; i < fElementCount; i++)
180			fWeights[i] = 1.0f;
181	}
182}
183
184
185// destructor
186ComplexLayouter::~ComplexLayouter()
187{
188	for (int32 i = 0; i < fElementCount; i++) {
189		Constraint* constraint = fConstraints[i];
190		fConstraints[i] = NULL;
191		while (constraint != NULL) {
192			Constraint* next = constraint->next;
193			delete constraint;
194			constraint = next;
195		}
196	}
197
198	delete[] fConstraints;
199	delete[] fWeights;
200	delete[] fSums;
201	delete[] fSumBackups;
202  	delete fOptimizer;
203}
204
205
206// InitCheck
207status_t
208ComplexLayouter::InitCheck() const
209{
210	if (!fConstraints || !fWeights || !fSums || !fSumBackups || !fOptimizer)
211		return B_NO_MEMORY;
212	return fOptimizer->InitCheck();
213}
214
215
216// AddConstraints
217void
218ComplexLayouter::AddConstraints(int32 element, int32 length,
219	float _min, float _max, float _preferred)
220{
221	if (element < 0 || length <= 0 || element + length > fElementCount)
222		return;
223
224	TRACE("%p->ComplexLayouter::AddConstraints(%ld, %ld, %ld, %ld, %ld)\n",
225		this, element, length, (int32)_min, (int32)_max, (int32)_preferred);
226
227	int32 spacing = fSpacing * (length - 1);
228	int32 min = (int32)_min + 1 - spacing;
229	int32 max = (int32)_max + 1 - spacing;
230
231	if (min < 0)
232		min = 0;
233	if (max > fUnlimited)
234		max = fUnlimited;
235
236	int32 end = element + length - 1;
237	Constraint** slot = fConstraints + end;
238	while (*slot != NULL && (*slot)->start > element)
239		slot = &(*slot)->next;
240
241	if (*slot != NULL && (*slot)->start == element) {
242		// previous constraint exists -- use stricter values
243		(*slot)->Restrict(min, max);
244	} else {
245		// no previous constraint -- create new one
246		Constraint* constraint = new(nothrow) Constraint(element, end, min,
247			max);
248		if (!constraint)
249			return;
250		constraint->next = *slot;
251		*slot = constraint;
252	}
253
254	fMinMaxValid = false;
255}
256
257
258// SetWeight
259void
260ComplexLayouter::SetWeight(int32 element, float weight)
261{
262	if (element < 0 || element >= fElementCount)
263		return;
264
265	fWeights[element] = max_c(weight, 0);
266}
267
268
269// MinSize
270float
271ComplexLayouter::MinSize()
272{
273	_ValidateLayout();
274	return fMin;
275}
276
277
278// MaxSize
279float
280ComplexLayouter::MaxSize()
281{
282	_ValidateLayout();
283	return fMax;
284}
285
286
287// PreferredSize
288float
289ComplexLayouter::PreferredSize()
290{
291	return fMin;
292}
293
294
295// CreateLayoutInfo
296LayoutInfo*
297ComplexLayouter::CreateLayoutInfo()
298{
299	MyLayoutInfo* layoutInfo = new(nothrow) MyLayoutInfo(fElementCount,
300		fSpacing);
301	if (layoutInfo && !layoutInfo->fLocations) {
302		delete layoutInfo;
303		return NULL;
304	}
305
306	return layoutInfo;
307}
308
309
310// Layout
311void
312ComplexLayouter::Layout(LayoutInfo* _layoutInfo, float _size)
313{
314	TRACE("%p->ComplexLayouter::Layout(%ld)\n", this, (int32)_size);
315
316	if (fElementCount == 0)
317		return;
318
319	_ValidateLayout();
320
321	MyLayoutInfo* layoutInfo = (MyLayoutInfo*)_layoutInfo;
322
323	int32 min = fSums[fElementCount].min;
324	int32 max = fSums[fElementCount].max;
325
326	int32 size = (int32)_size + 1 - (fElementCount - 1) * fSpacing;
327	if (size < min)
328		size = min;
329	if (size > max)
330		size = max;
331
332	SumItem sums[fElementCount + 1];
333	memcpy(sums, fSums, (fElementCount + 1) * sizeof(SumItem));
334
335	sums[fElementCount].min = size;
336	sums[fElementCount].max = size;
337	sums[fElementCount].minDirty = (size != min);
338	sums[fElementCount].maxDirty = (size != max);
339
340	// propagate the size
341	_PropagateChangesBack(sums, fElementCount - 1, NULL);
342	_PropagateChanges(sums, fElementCount - 1, NULL);
343
344#if TRACE_COMPLEX_LAYOUTER
345	TRACE("Layout(%ld)\n", size);
346	for (int32 i = 0; i < fElementCount; i++) {
347		SumItem& sum = sums[i + 1];
348		TRACE("[%ld] minc = %4ld,  maxc = %4ld\n", i + 1, sum.min, sum.max);
349	}
350#endif
351
352	int32 sizes[fElementCount];
353	if (!_Layout(size, sums, sizes)) {
354	}
355
356	layoutInfo->InitFromSizes(sizes);
357}
358
359
360// CloneLayouter
361Layouter*
362ComplexLayouter::CloneLayouter()
363{
364	ComplexLayouter* layouter
365		= new(nothrow) ComplexLayouter(fElementCount, fSpacing);
366	ObjectDeleter<ComplexLayouter> layouterDeleter(layouter);
367	if (!layouter || layouter->InitCheck() != B_OK
368		|| !layouter->fOptimizer->AddConstraintsFrom(fOptimizer)) {
369		return NULL;
370	}
371
372	// clone the constraints
373	for (int32 i = 0; i < fElementCount; i++) {
374		Constraint* constraint = fConstraints[i];
375		Constraint** end = layouter->fConstraints + i;
376		while (constraint) {
377			*end = new(nothrow) Constraint(constraint->start, constraint->end,
378				constraint->min, constraint->max);
379			if (!*end)
380				return NULL;
381
382			end = &(*end)->next;
383			constraint = constraint->next;
384		}
385	}
386
387	// copy the other stuff
388	memcpy(layouter->fWeights, fWeights, fElementCount * sizeof(float));
389	memcpy(layouter->fSums, fSums, (fElementCount + 1) * sizeof(SumItem));
390	memcpy(layouter->fSumBackups, fSumBackups,
391		(fElementCount + 1) * sizeof(SumItemBackup));
392	layouter->fMin = fMin;
393	layouter->fMax = fMax;
394	layouter->fMinMaxValid = fMinMaxValid;
395
396	return layouterDeleter.Detach();
397}
398
399
400// _Layout
401bool
402ComplexLayouter::_Layout(int32 size, SumItem* sums, int32* sizes)
403{
404	// prepare the desired solution
405	SimpleLayouter::DistributeSize(size, fWeights, sizes, fElementCount);
406	if (_SatisfiesConstraints(sizes)) {
407		// The desired solution already satisfies all constraints.
408		return true;
409	}
410
411	double realSizes[fElementCount];
412	for (int32 i = 0; i < fElementCount; i++)
413		realSizes[i] = sizes[i];
414
415	if (!_AddOptimizerConstraints())
416		return false;
417
418
419	// prepare a feasible solution (the minimum)
420	double values[fElementCount];
421	for (int32 i = 0; i < fElementCount; i++)
422		values[i] = sums[i + 1].min - sums[i].min;
423
424#if TRACE_COMPLEX_LAYOUTER
425	TRACE("feasible solution vs. desired solution:\n");
426	for (int32 i = 0; i < fElementCount; i++)
427		TRACE("%8.4f   %8.4f\n", values[i], realSizes[i]);
428#endif
429
430	// solve
431	TRACE_ONLY(bigtime_t time = system_time();)
432	if (!fOptimizer->Solve(realSizes, size, values))
433		return false;
434	TRACE_ONLY(time = system_time() - time;)
435
436	// compute integer solution
437	// The basic strategy is to floor() the sums. This guarantees that the
438	// difference between two rounded sums remains in the range of floor()
439	// and ceil() of their real value difference. Since the constraints have
440	// integer values, the integer solution will therefore satisfy all
441	// constraints the real solution satisfied.
442	TRACE("computed solution in %lld us:\n", time);
443
444	double realSum = 0;
445	double previousSum = 0;
446	for (int32 i = 0; i < fElementCount; i++) {
447		realSum += values[i];
448		double roundedRealSum = floor(realSum);
449		if (fuzzy_equals(realSum, roundedRealSum + 1))
450			realSum = roundedRealSum + 1;
451		sizes[i] = int32(roundedRealSum - previousSum);
452		previousSum = roundedRealSum;
453
454		TRACE("x[%ld] = %8.4f   %4ld\n", i, values[i], sizes[i]);
455	}
456
457	return _SatisfiesConstraints(sizes);
458}
459
460
461// _AddOptimizerConstraints
462bool
463ComplexLayouter::_AddOptimizerConstraints()
464{
465	if (fOptimizerConstraintsAdded)
466		return true;
467
468	fOptimizer->RemoveAllConstraints();
469
470	// add constraints
471	for (int32 i = 0; i < fElementCount; i++) {
472		SumItem& sum = fSums[i + 1];
473
474		Constraint* constraint = fConstraints[i];
475		while (constraint != NULL) {
476			SumItem& base = fSums[constraint->start];
477			int32 sumMin = base.min + constraint->min;
478			int32 baseMax = sum.max - constraint->min;
479			bool minRedundant = (sumMin < sum.min && baseMax > base.max);
480
481			int32 sumMax = base.max + constraint->effectiveMax;
482			int32 baseMin = sum.min - constraint->effectiveMax;
483			bool maxRedundant = (sumMax > sum.max && baseMin < base.min);
484
485			if (!minRedundant || !maxRedundant) {
486				bool success = true;
487				if (constraint->min == constraint->effectiveMax) {
488					// min and max equal -- add an equality constraint
489					success = fOptimizer->AddConstraint(constraint->start - 1,
490						constraint->end, constraint->min, true);
491				} else {
492					// min and max not equal -- add them individually,
493					// unless redundant
494					if (!minRedundant) {
495						success |= fOptimizer->AddConstraint(
496							constraint->start - 1, constraint->end,
497							constraint->min, false);
498					}
499					if (!maxRedundant) {
500						success |= fOptimizer->AddConstraint(constraint->end,
501							constraint->start - 1,
502							-constraint->effectiveMax, false);
503					}
504				}
505
506				if (!success)
507					return false;
508			}
509
510			constraint = constraint->next;
511		}
512	}
513
514	fOptimizerConstraintsAdded = true;
515	return true;
516}
517
518
519// _SatisfiesConstraints
520bool
521ComplexLayouter::_SatisfiesConstraints(int32* sizes) const
522{
523	int32 sumValues[fElementCount + 1];
524	sumValues[0] = 0;
525	for (int32 i = 0; i < fElementCount; i++)
526		sumValues[i + 1] = sumValues[i] + sizes[i];
527
528	return _SatisfiesConstraintsSums(sumValues);
529}
530
531
532// _SatisfiesConstraintsSums
533bool
534ComplexLayouter::_SatisfiesConstraintsSums(int32* sumValues) const
535{
536	for (int32 i = 0; i < fElementCount; i++) {
537		Constraint* constraint = fConstraints[i];
538		while (constraint) {
539			if (!constraint->IsSatisfied(sumValues))
540				return false;
541
542			constraint = constraint->next;
543		}
544	}
545
546	return true;
547}
548
549
550// _ValidateLayout
551void
552ComplexLayouter::_ValidateLayout()
553{
554	// The general idea for computing the min and max for the given constraints
555	// is that we rewrite the problem a little. Instead of considering the
556	// x_1, ... x_n (n = fElementCount) and the constraints of the form
557	//   x_i + ... + x_{i+j} >= min[i,j] and
558	//   x_i + ... + x_{i+j} >= max[i,j], with i >= 1, j >= 0, i + j <= n
559	//   and min[i,j], max[i,j] >= 0
560	// we define
561	//   c[0] = 0
562	//   c[i] = \sum_{k=1}^i x_k, for all i, 1 <= i <= n
563	// and thus the constraints read:
564	//   c[i+j] - c[i-1] >= min[i,j]
565	//   c[i+j] - c[i-1] <= max[i,j]
566	//
567	// Let minc[i] and maxc[i] the limits imposed by the given constraints, i.e.
568	//   minc[i] <= c[i] <= maxc[i] for any tuple of (c[i])_i satisfying the
569	// constraints (minc[i] and maxc[i] are unique), then we gain:
570	//   minc[i+j] >= c[i-1] + min[i,j]
571	//   maxc[i+j] <= c[i-1] + min[i,j]
572	//   minc[i-1] >= minc[i+j] - max[i,j]
573	//   maxc[i-1] >= maxc[i+j] - min[i,j]
574	// We can compute the minc[i] and maxc[i] in an iterative process,
575	// propagating the first to kinds of constraints forward and the other two
576	// backwards. First we start considering all min constraints only. They
577	// can't contradict each other and are usually to be enforced over max
578	// constraints. Afterwards we add the max constraints one by one. For each
579	// one of them we propagate resulting changes back and forth. In case of
580	// a conflict, we relax the max constraint as much as necessary to yield
581	// a consistent set of constraints. After all constraints have been
582	// incorporated, the resulting minc[n] and maxc[n] are the min and max
583	// limits we wanted to compute.
584
585	if (fMinMaxValid)
586		return;
587
588	fSums[0].min = 0;
589	fSums[0].max = 0;
590
591	int32 maxSum = 0;
592	for (int32 i = 0; i < fElementCount; i++) {
593		SumItem& sum = fSums[i + 1];
594		sum.min = 0;
595		sum.max = maxSum += fUnlimited;
596		sum.minDirty = false;
597		sum.maxDirty = false;
598	}
599
600	// apply min constraints forward:
601	//   minc[i+j] >= minc[i-1] + min[i,j]
602	for (int32 i = 0; i < fElementCount; i++) {
603		SumItem& sum = fSums[i + 1];
604
605		Constraint* constraint = fConstraints[i];
606		while (constraint != NULL) {
607			int32 minSum = fSums[constraint->start].min + constraint->min;
608			if (minSum > sum.min) {
609				sum.min = minSum;
610			} else {
611				TRACE("min constraint is redundant: x%ld + ... + x%ld >= %ld\n",
612					constraint->start, constraint->end, constraint->min);
613			}
614
615			constraint = constraint->next;
616		}
617	}
618
619	// apply min constraints backwards:
620	//   maxc[i-1] <= maxc[i+j] - min[i,j]
621	for (int32 i = fElementCount - 1; i >= 0; i--) {
622		SumItem& sum = fSums[i + 1];
623
624		Constraint* constraint = fConstraints[i];
625		while (constraint != NULL) {
626			SumItem& base = fSums[constraint->start];
627			int32 baseMax = sum.max - constraint->min;
628			if (baseMax < base.max)
629				base.max = baseMax;
630
631			constraint = constraint->next;
632		}
633	}
634
635	// apply max constraints
636	for (int32 i = 0; i < fElementCount; i++) {
637		Constraint* constraint = fConstraints[i];
638		while (constraint != NULL) {
639			_ApplyMaxConstraint(constraint, i);
640
641			constraint = constraint->next;
642		}
643	}
644
645#if TRACE_COMPLEX_LAYOUTER
646	for (int32 i = 0; i < fElementCount; i++) {
647		SumItem& sum = fSums[i + 1];
648		TRACE("[%ld] minc = %4ld,  maxc = %4ld\n", i + 1, sum.min, sum.max);
649	}
650#endif
651
652	if (fElementCount == 0) {
653		fMin = -1;
654		fMax = B_SIZE_UNLIMITED;
655	} else {
656		int32 spacing = (fElementCount - 1) * fSpacing;
657		fMin = fSums[fElementCount].min + spacing - 1;
658		fMax = fSums[fElementCount].max + spacing - 1;
659		if (fMax >= fUnlimited)
660			fMax = B_SIZE_UNLIMITED;
661	}
662
663	fOptimizerConstraintsAdded = false;
664	fMinMaxValid = true;
665}
666
667
668// _ApplyMaxConstraint
669void
670ComplexLayouter::_ApplyMaxConstraint(Constraint* currentConstraint, int32 index)
671{
672	SumItem& sum = fSums[index + 1];
673	SumItem& base = fSums[currentConstraint->start];
674
675	// We want to apply:
676	//   c[i+j] <= c[i-1] + max[i,j]
677	//
678	// This has the following direct consequences (let k = i + j):
679	// (1) maxc[k] <= maxc[i-1] + max[i,j]
680	// (2) minc[i-1] >= minc[k] - max[i,j]
681	//
682	// If maxc[k] or minc[i-i] changed, those changes have to be propagated
683	// back.
684
685	// apply (1) maxc[k] <= maxc[i-1] + max[i,j]
686	int32 max = currentConstraint->effectiveMax;
687	int32 sumMax = base.max + max;
688
689	// enforce maxc[i+j] >= minc[i+j]
690	if (sumMax < sum.min) {
691		sumMax = sum.min;
692		max = sumMax - base.max;
693	}
694
695	// apply (2) minc[i-1] >= minc[k] - max[i,j]
696	// and check minc[i-1] <= maxc[i-1]
697	int32 baseMin = sum.min - max;
698	if (baseMin > base.max) {
699		baseMin = base.max;
700		max = sum.min - baseMin;
701		sumMax = base.max + max;
702	}
703
704	if (currentConstraint->effectiveMax != max) {
705		TRACE("relaxing conflicting max constraint (1): "
706			"x%ld + ... + x%ld <= %ld -> %ld\n", currentConstraint->start,
707			currentConstraint->end, currentConstraint->effectiveMax, max);
708	}
709	currentConstraint->effectiveMax = max;
710
711	if (baseMin <= base.min && sumMax >= sum.max) {
712		TRACE("max constraint is redundant: x%ld + ... + x%ld <= %ld\n",
713			currentConstraint->start, currentConstraint->end,
714			currentConstraint->effectiveMax);
715		return;
716	}
717
718	// backup old values, in case we detect a conflict later
719	_BackupValues(index);
720
721	int32 diff;
722	do {
723		// apply the changes
724		int32 changedIndex = currentConstraint->start;
725
726		if (baseMin > base.min) {
727			base.min = baseMin;
728			base.minDirty = true;
729		}
730
731		if (sumMax < sum.max) {
732			changedIndex = index;
733			sum.max = sumMax;
734			sum.maxDirty = true;
735		}
736
737		// propagate the changes
738		_PropagateChangesBack(fSums, changedIndex, currentConstraint);
739		_PropagateChanges(fSums, index, currentConstraint);
740
741		// check the new constraint again -- if it doesn't hold, it
742		// conflicts with the other constraints
743		diff = 0;
744
745		// check (1) maxc[k] <= maxc[i-1] + max[i,j]
746		max = currentConstraint->effectiveMax;
747		sumMax = base.max + max;
748		if (sumMax < sum.max)
749			diff = sum.max - sumMax;
750
751		// check (2) minc[i-1] >= minc[k] - max[i,j]
752		baseMin = sum.min - max;
753		if (baseMin > base.min)
754			diff = max_c(diff, baseMin - base.min);
755
756		// clear the dirty flags
757		for (int32 i = 0; i <= changedIndex; i++) {
758			SumItem& sum = fSums[i + 1];
759			sum.minDirty = false;
760			sum.maxDirty = false;
761		}
762
763		// if we've got a conflict, we relax the constraint and try again
764		if (diff > 0) {
765			max += diff;
766			TRACE("relaxing conflicting max constraint (2): "
767				"x%ld + ... + x%ld <= %ld -> %ld\n", currentConstraint->start,
768				currentConstraint->end, currentConstraint->effectiveMax, max);
769			currentConstraint->effectiveMax = max;
770
771			_RestoreValues(index);
772
773			sumMax = base.max + max;
774			baseMin = sum.min - max;
775
776			if (baseMin <= base.min && sumMax >= sum.max)
777				return;
778		}
779	} while (diff > 0);
780}
781
782
783// _PropagateChanges
784/*!	Propagate changes forward using min and max constraints. Max constraints
785	Beyond \a toIndex or at \a to toIndex after (and including)
786	\a lastMaxConstraint will be ignored. To have all constraints be
787	considered pass \c fElementCount and \c NULL.
788*/
789void
790ComplexLayouter::_PropagateChanges(SumItem* sums, int32 toIndex,
791	Constraint* lastMaxConstraint)
792{
793	for (int32 i = 0; i < fElementCount; i++) {
794		SumItem& sum = sums[i + 1];
795
796		bool ignoreMaxConstraints = (i > toIndex);
797
798		Constraint* constraint = fConstraints[i];
799		while (constraint != NULL) {
800			SumItem& base = sums[constraint->start];
801
802			if (constraint == lastMaxConstraint)
803				ignoreMaxConstraints = true;
804
805			// minc[k] >= minc[i-1] + min[i,j]
806			if (base.minDirty) {
807				int32 sumMin = base.min + constraint->min;
808				if (sumMin > sum.min) {
809					sum.min = sumMin;
810					sum.minDirty = true;
811				}
812			}
813
814			// maxc[k] <= maxc[i-1] + max[i,j]
815			if (base.maxDirty && !ignoreMaxConstraints) {
816				int32 sumMax = base.max + constraint->effectiveMax;
817				if (sumMax < sum.max) {
818					sum.max = sumMax;
819					sum.maxDirty = true;
820				}
821			}
822
823			constraint = constraint->next;
824		}
825
826		if (sum.minDirty || sum.maxDirty) {
827			if (sum.min > sum.max) {
828				// TODO: Can this actually happen?
829				TRACE("adjusted max in propagation phase: index: "
830					"%ld: %ld -> %ld\n", i, sum.max, sum.min);
831				sum.max = sum.min;
832				sum.maxDirty = true;
833			}
834		}
835	}
836}
837
838
839// _PropagateChangesBack
840void
841ComplexLayouter::_PropagateChangesBack(SumItem* sums, int32 changedIndex,
842	Constraint* lastMaxConstraint)
843{
844	for (int32 i = changedIndex; i >= 0; i--) {
845		SumItem& sum = sums[i + 1];
846
847		bool ignoreMaxConstraints = false;
848
849		Constraint* constraint = fConstraints[i];
850		while (constraint != NULL) {
851			SumItem& base = sums[constraint->start];
852
853			if (constraint == lastMaxConstraint)
854				ignoreMaxConstraints = true;
855
856			// minc[i-1] >= minc[k] - max[i,j]
857			if (sum.minDirty && !ignoreMaxConstraints) {
858				int32 baseMin = sum.min - constraint->effectiveMax;
859				if (baseMin > base.min) {
860					if (baseMin > base.max) {
861						TRACE("min above max in back propagation phase: index: "
862							"(%ld -> %ld), min: %ld, max: %ld\n", i,
863							constraint->start, baseMin, base.max);
864					}
865					base.min = baseMin;
866					base.minDirty = true;
867				}
868			}
869
870			// maxc[i-1] <= maxc[k] - min[i,j]
871			if (sum.maxDirty) {
872				int32 baseMax = sum.max - constraint->min;
873				if (baseMax < base.max) {
874					if (baseMax < base.min) {
875						TRACE("max below min in back propagation phase: index: "
876							"(%ld -> %ld), max: %ld, min: %ld\n", i,
877							constraint->start, baseMax, base.min);
878					}
879					base.max = baseMax;
880					base.maxDirty = true;
881				}
882			}
883
884			constraint = constraint->next;
885		}
886	}
887}
888
889
890// _BackupValues
891void
892ComplexLayouter::_BackupValues(int32 maxIndex)
893{
894	for (int32 i = 0; i <= maxIndex; i++) {
895		SumItem& sum = fSums[i + 1];
896		fSumBackups[i + 1].min = sum.min;
897		fSumBackups[i + 1].max = sum.max;
898	}
899}
900
901
902// _RestoreValues
903void
904ComplexLayouter::_RestoreValues(int32 maxIndex)
905{
906	for (int32 i = 0; i <= maxIndex; i++) {
907		SumItem& sum = fSums[i + 1];
908		sum.min = fSumBackups[i + 1].min;
909		sum.max = fSumBackups[i + 1].max;
910	}
911}
912
913