1/*
2 * Copyright 2006, Ingo Weinhold <bonefish@cs.tu-berlin.de>.
3 * All rights reserved. Distributed under the terms of the MIT License.
4 */
5
6#include "SimpleLayouter.h"
7
8#include <math.h>
9
10#include <LayoutUtils.h>
11#include <List.h>
12#include <Size.h>
13
14
15// no lround() under BeOS R5 x86
16#ifdef HAIKU_TARGET_PLATFORM_LIBBE_TEST
17#	define lround(x)	(long)floor((x) + 0.5)
18#endif
19
20
21// ElementLayoutInfo
22class SimpleLayouter::ElementLayoutInfo {
23public:
24	int32	size;
25	int32	location;
26
27	ElementLayoutInfo()
28		: size(0),
29		  location(0)
30	{
31	}
32};
33
34// ElementInfo
35class SimpleLayouter::ElementInfo {
36public:
37	int32	index;
38	int32	min;
39	int32	max;
40	int32	preferred;
41	float	weight;
42	int64	tempWeight;
43
44	ElementInfo()
45		: index(0),
46		  min(0),
47		  max(B_SIZE_UNLIMITED),
48		  preferred(0),
49		  weight(1),
50		  tempWeight(0)
51	{
52	}
53
54	ElementInfo(int index)
55		: index(index),
56		  min(0),
57		  max(B_SIZE_UNLIMITED),
58		  preferred(0),
59		  weight(1),
60		  tempWeight(0)
61	{
62	}
63
64	void Assign(const ElementInfo& info)
65	{
66		min = info.min;
67		max = info.max;
68		preferred = info.preferred;
69		weight = info.weight;
70		tempWeight = info.tempWeight;
71	}
72};
73
74// MyLayoutInfo
75class SimpleLayouter::MyLayoutInfo : public LayoutInfo {
76public:
77	int32				fSize;
78	ElementLayoutInfo*	fElements;
79	int32				fElementCount;
80
81	MyLayoutInfo(int32 elementCount)
82		: fSize(0),
83		  fElementCount(elementCount)
84	{
85		fElements = new ElementLayoutInfo[elementCount];
86	}
87
88	virtual ~MyLayoutInfo()
89	{
90		delete[] fElements;
91	}
92
93	virtual float ElementLocation(int32 element)
94	{
95		if (element < 0 || element >= fElementCount) {
96			// error
97			return 0;
98		}
99
100		return fElements[element].location;
101	}
102
103	virtual float ElementSize(int32 element)
104	{
105		if (element < 0 || element >= fElementCount) {
106			// error
107			return -1;
108		}
109
110		return fElements[element].size - 1;
111	}
112};
113
114
115// constructor
116SimpleLayouter::SimpleLayouter(int32 elementCount, float spacing)
117	: fElementCount(elementCount),
118	  fSpacing((int32)spacing),
119	  fMin(0),
120	  fMax(B_SIZE_UNLIMITED),
121	  fPreferred(0),
122	  fMinMaxValid(false),
123	  fLayoutInfo(NULL)
124{
125	fElements = new ElementInfo[elementCount];
126	for (int i = 0; i < elementCount; i++)
127		fElements[i].index = i;
128}
129
130// destructor
131SimpleLayouter::~SimpleLayouter()
132{
133	delete[] fElements;
134}
135
136// AddConstraints
137void
138SimpleLayouter::AddConstraints(int32 element, int32 length,
139	float _min, float _max, float _preferred)
140{
141	if (element < 0 || element >= fElementCount) {
142		// error
143		return;
144	}
145	if (length != 1) {
146		// error
147		return;
148	}
149
150	int32 min = (int32)_min + 1;
151	int32 max = (int32)_max + 1;
152//	int32 preferred = (int32)_preferred + 1;
153
154	ElementInfo& info = fElements[element];
155	info.min = max_c(info.min, min);
156	info.max = min_c(info.max, max);
157	info.preferred = max_c(info.min, min);
158
159	fMinMaxValid = false;
160}
161
162// SetWeight
163void
164SimpleLayouter::SetWeight(int32 element, float weight)
165{
166	if (element < 0 || element >= fElementCount) {
167		// error
168		return;
169	}
170
171	fElements[element].weight = weight;
172}
173
174// MinSize
175float
176SimpleLayouter::MinSize()
177{
178	_ValidateMinMax();
179	return fMin - 1;
180}
181
182// MaxSize
183float
184SimpleLayouter::MaxSize()
185{
186	_ValidateMinMax();
187	return fMax - 1;
188}
189
190// PreferredSize
191float
192SimpleLayouter::PreferredSize()
193{
194	_ValidateMinMax();
195	return fPreferred - 1;
196}
197
198// CreateLayoutInfo
199LayoutInfo*
200SimpleLayouter::CreateLayoutInfo()
201{
202	return new MyLayoutInfo(fElementCount);
203}
204
205// Layout
206void
207SimpleLayouter::Layout(LayoutInfo* layoutInfo, float _size)
208{
209	int32 size = int32(_size + 1);
210
211	fLayoutInfo = (MyLayoutInfo*)layoutInfo;
212
213	_ValidateMinMax();
214
215	if (fElementCount == 0)
216		return;
217
218	fLayoutInfo->fSize = max_c(size, fMin);
219
220	// layout the elements
221	if (fLayoutInfo->fSize >= fMax)
222		_LayoutMax();
223	else
224		_LayoutStandard();
225
226	// set locations
227	int location = 0;
228	for (int i = 0; i < fElementCount; i++) {
229		fLayoutInfo->fElements[i].location = location;
230		location += fSpacing + fLayoutInfo->fElements[i].size;
231	}
232}
233
234// CloneLayouter
235Layouter*
236SimpleLayouter::CloneLayouter()
237{
238	SimpleLayouter* layouter = new SimpleLayouter(fElementCount, fSpacing);
239
240	for (int i = 0; i < fElementCount; i++)
241		layouter->fElements[i].Assign(fElements[i]);
242
243	layouter->fMin = fMin;
244	layouter->fMax = fMax;
245	layouter->fPreferred = fPreferred;
246
247	return layouter;
248}
249
250// DistributeSize
251void
252SimpleLayouter::DistributeSize(int32 size, float weights[], int32 sizes[],
253	int32 count)
254{
255	// create element infos
256	BList elementInfos(count);
257	for (int32 i = 0; i < count; i++) {
258		ElementInfo* info = new ElementInfo(i);
259		info->weight = weights[i];
260		elementInfos.AddItem(info);
261	}
262
263	// compute integer weights
264	int64 sumWeight = _CalculateSumWeight(elementInfos);
265
266	// distribute the size
267	int64 weight = 0;
268	int32 sumSize = 0;
269	for (int32 i = 0; i < count; i++) {
270		ElementInfo* info = (ElementInfo*)elementInfos.ItemAt(i);
271		weight += info->tempWeight;
272		int32 oldSumSize = sumSize;
273		sumSize = (int32)(size * weight / sumWeight);
274		sizes[i] = sumSize - oldSumSize;
275
276		delete info;
277	}
278}
279
280// _CalculateSumWeight
281long
282SimpleLayouter::_CalculateSumWeight(BList& elementInfos)
283{
284	if (elementInfos.IsEmpty())
285		return 0;
286	int32 count = elementInfos.CountItems();
287
288	// sum up the floating point weight, so we get a scale
289	double scale = 0;
290	for (int32 i = 0; i < count; i++) {
291		ElementInfo* info = (ElementInfo*)elementInfos.ItemAt(i);
292		scale += info->weight;
293	}
294
295	int64 weight = 0;
296
297	if (scale == 0) {
298		// The weight sum is 0: We assign each info a temporary weight of 1.
299		for (int32 i = 0; i < count; i++) {
300			ElementInfo* info = (ElementInfo*)elementInfos.ItemAt(i);
301			info->tempWeight = 1;
302			weight += info->tempWeight;
303		}
304	} else {
305		// We scale the weights so that their sum is about 100000. This should
306		// give us ample resolution. If possible make the scale integer, so that
307		// integer weights will produce exact results.
308		if (scale >= 1 && scale <= 100000)
309			scale = lround(100000 / scale);
310		else
311			scale = 100000 / scale;
312
313		for (int32 i = 0; i < count; i++) {
314			ElementInfo* info = (ElementInfo*)elementInfos.ItemAt(i);
315			info->tempWeight = (int64)(info->weight * scale);
316			weight += info->tempWeight;
317		}
318	}
319
320	return weight;
321}
322
323// _ValidateMinMax
324void
325SimpleLayouter::_ValidateMinMax()
326{
327	if (fMinMaxValid)
328		return;
329
330	fMinMaxValid = true;
331
332	if (fElementCount == 0) {
333		fMin = 0;
334		fMax = B_SIZE_UNLIMITED;
335		fPreferred = 0;
336		return;
337	}
338
339	int spacing = (fElementCount - 1) * fSpacing;
340	fMin = spacing;
341	fMax = spacing;
342	fPreferred = spacing;
343
344	for (int i = 0; i < fElementCount; i++) {
345		ElementInfo& info = fElements[i];
346
347		// correct the preferred and maximum sizes
348		if (info.max < info.min)
349			info.max = info.min;
350		if (info.preferred < info.min)
351			info.preferred = info.min;
352		else if (info.preferred > info.max)
353			info.preferred = info.max;
354
355		// sum up
356		fMin += info.min;
357		fMax = BLayoutUtils::AddSizesInt32(fMax, info.max);
358		fPreferred = BLayoutUtils::AddSizesInt32(fPreferred, info.preferred);
359	}
360}
361
362// _LayoutMax
363void
364SimpleLayouter::_LayoutMax()
365{
366	ElementInfo* infos = fElements;
367	int32 count = fElementCount;
368	if (count == 0)
369		return;
370
371	int32 additionalSpace = fLayoutInfo->fSize - fMax;
372
373	// layout to the maximum first
374	for (int i = 0; i < count; i++)
375		fLayoutInfo->fElements[infos[i].index].size = infos[i].max;
376
377// Mmh, distributing according to the weights doesn't look that good.
378//	// Now distribute the additional space according to the weights.
379//	int64 sumWeight = calculateSumWeight(Arrays.asList(infos));
380//	int64 weight = 0;
381//	int64 sumSize = 0;
382//	for (int i = 0; i < infos.length; i++) {
383//		weight += infos[i].tempWeight;
384//		int64 oldSumSize = sumSize;
385//		sumSize = (int)(additionalSpace * weight / sumWeight);
386//		fLayoutInfo.fElements[infos[i].index].size += sumSize - oldSumSize;
387//	}
388
389	// distribute the additional space equally
390	int64 sumSize = 0;
391	for (int i = 0; i < count; i++) {
392		int64 oldSumSize = sumSize;
393		sumSize = additionalSpace * (i + 1) / count;
394		fLayoutInfo->fElements[infos[i].index].size
395			+= int32(sumSize - oldSumSize);
396	}
397}
398
399// _LayoutStandard
400void
401SimpleLayouter::_LayoutStandard()
402{
403	int32 space = fLayoutInfo->fSize - (fElementCount - 1) * fSpacing;
404
405	BList infosToLayout(fElementCount);
406	for (int i = 0; i < fElementCount; i++) {
407		infosToLayout.AddItem(&fElements[i]);
408		fLayoutInfo->fElements[i].size = 0;
409	}
410
411	BList infosUnderMax(fElementCount);
412	BList infosOverMin(fElementCount);
413	while (infosToLayout.CountItems() > 0) {
414		int32 remainingSpace = 0;
415		int32 infoCount = infosToLayout.CountItems();
416		int64 sumWeight = _CalculateSumWeight(infosToLayout);
417		int64 assignedWeight = 0;
418		int32 assignedSize = 0;
419
420		for (int32 i = 0; i < infoCount; i++) {
421			ElementInfo* info = (ElementInfo*)infosToLayout.ItemAt(i);
422			ElementLayoutInfo& layoutInfo = fLayoutInfo->fElements[info->index];
423			// The simple algorithm is this:
424			// info.size += (int)(space * info.tempWeight / sumWeight);
425			// I.e. we simply assign space according to the weight. To avoid the
426			// rounding problematic, we make it a bit more complicated. We
427			// assign the difference of total assignment for all infos including
428			// the current one minus the total excluding the current one.
429			assignedWeight += info->tempWeight;
430			int32 oldAssignedSize = assignedSize;
431			assignedSize = (int32)(space * assignedWeight / sumWeight);
432			layoutInfo.size += assignedSize - oldAssignedSize;
433
434			if (layoutInfo.size < info->min) {
435				remainingSpace += layoutInfo.size - info->min;
436				layoutInfo.size = info->min;
437			} else if (layoutInfo.size > info->max) {
438				remainingSpace += layoutInfo.size - info->max;
439				layoutInfo.size = info->max;
440			}
441
442			if (layoutInfo.size > info->min)
443				infosOverMin.AddItem(info);
444			if (layoutInfo.size < info->max)
445				infosUnderMax.AddItem(info);
446		}
447
448		infosToLayout.MakeEmpty();
449		if (remainingSpace > 0)
450			infosToLayout.AddList(&infosUnderMax);
451		else if (remainingSpace < 0)
452			infosToLayout.AddList(&infosOverMin);
453		infosUnderMax.MakeEmpty();
454		infosOverMin.MakeEmpty();
455		space = remainingSpace;
456	}
457}
458