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
22 class SimpleLayouter::ElementLayoutInfo {
23 public:
24 int32 size;
25 int32 location;
26
ElementLayoutInfo()27 ElementLayoutInfo()
28 : size(0),
29 location(0)
30 {
31 }
32 };
33
34 // ElementInfo
35 class SimpleLayouter::ElementInfo {
36 public:
37 int32 index;
38 int32 min;
39 int32 max;
40 int32 preferred;
41 float weight;
42 int64 tempWeight;
43
ElementInfo()44 ElementInfo()
45 : index(0),
46 min(0),
47 max((int32)B_SIZE_UNLIMITED),
48 preferred(0),
49 weight(1),
50 tempWeight(0)
51 {
52 }
53
ElementInfo(int index)54 ElementInfo(int index)
55 : index(index),
56 min(0),
57 max((int32)B_SIZE_UNLIMITED),
58 preferred(0),
59 weight(1),
60 tempWeight(0)
61 {
62 }
63
Assign(const ElementInfo & info)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
75 class SimpleLayouter::MyLayoutInfo : public LayoutInfo {
76 public:
77 int32 fSize;
78 ElementLayoutInfo* fElements;
79 int32 fElementCount;
80
MyLayoutInfo(int32 elementCount)81 MyLayoutInfo(int32 elementCount)
82 : fSize(0),
83 fElementCount(elementCount)
84 {
85 fElements = new ElementLayoutInfo[elementCount];
86 }
87
~MyLayoutInfo()88 virtual ~MyLayoutInfo()
89 {
90 delete[] fElements;
91 }
92
ElementLocation(int32 element)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
ElementSize(int32 element)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
SimpleLayouter(int32 elementCount,float spacing)116 SimpleLayouter::SimpleLayouter(int32 elementCount, float spacing)
117 : fElementCount(elementCount),
118 fSpacing((int32)spacing),
119 fMin(0),
120 fMax((int32)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
~SimpleLayouter()131 SimpleLayouter::~SimpleLayouter()
132 {
133 delete[] fElements;
134 }
135
136 // AddConstraints
137 void
AddConstraints(int32 element,int32 length,float _min,float _max,float _preferred)138 SimpleLayouter::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
163 void
SetWeight(int32 element,float weight)164 SimpleLayouter::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
175 float
MinSize()176 SimpleLayouter::MinSize()
177 {
178 _ValidateMinMax();
179 return fMin - 1;
180 }
181
182 // MaxSize
183 float
MaxSize()184 SimpleLayouter::MaxSize()
185 {
186 _ValidateMinMax();
187 return fMax - 1;
188 }
189
190 // PreferredSize
191 float
PreferredSize()192 SimpleLayouter::PreferredSize()
193 {
194 _ValidateMinMax();
195 return fPreferred - 1;
196 }
197
198 // CreateLayoutInfo
199 LayoutInfo*
CreateLayoutInfo()200 SimpleLayouter::CreateLayoutInfo()
201 {
202 return new MyLayoutInfo(fElementCount);
203 }
204
205 // Layout
206 void
Layout(LayoutInfo * layoutInfo,float _size)207 SimpleLayouter::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
235 Layouter*
CloneLayouter()236 SimpleLayouter::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
251 void
DistributeSize(int32 size,float weights[],int32 sizes[],int32 count)252 SimpleLayouter::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
281 long
_CalculateSumWeight(BList & elementInfos)282 SimpleLayouter::_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
324 void
_ValidateMinMax()325 SimpleLayouter::_ValidateMinMax()
326 {
327 if (fMinMaxValid)
328 return;
329
330 fMinMaxValid = true;
331
332 if (fElementCount == 0) {
333 fMin = 0;
334 fMax = (int32)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
363 void
_LayoutMax()364 SimpleLayouter::_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
400 void
_LayoutStandard()401 SimpleLayouter::_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