00001
00002
00003
00004
00005
00006
00007
00008
00009
00010 #include <limits>
00011
00012 #include <KDebug>
00013
00014 #include "itemspace.h"
00015
00016 ItemSpace::ItemSpace()
00017 : spaceAlignment(Qt::AlignTop|Qt::AlignLeft),
00018 workingGeom(QSizeF()),
00019 placementSpacing(0),
00020 screenSpacing(0),
00021 shiftingSpacing(0)
00022 {
00023 }
00024
00025 void ItemSpace::setWorkingArea(QSizeF area)
00026 {
00027 if (workingGeom.isValid()) {
00028
00029
00030
00031 if (((spaceAlignment & Qt::AlignRight) || (spaceAlignment & Qt::AlignBottom)) &&
00032 (area.width() != workingGeom.width() || area.height() != workingGeom.height())) {
00033 offsetPositions(QPointF(area.width()-workingGeom.width(), area.height()-workingGeom.height()));
00034 }
00035 }
00036 workingGeom = area;
00037 }
00038
00039 void ItemSpace::activate()
00040 {
00041 for (int groupId = 0; groupId < m_groups.size(); groupId++) {
00042 ItemGroup &group = m_groups[groupId];
00043
00044 for (int itemId = 0; itemId < group.m_groupItems.size(); itemId++) {
00045 ItemSpaceItem &item = group.m_groupItems[itemId];
00046
00047 qreal push;
00048 PushPower power;
00049
00050
00051
00052
00053
00054
00055
00056
00057 push = screenSpacing - item.lastGeometry.left();
00058 if (push > 0) {
00059 item.animateMovement = true;
00060 power = PushAwayFromPreferred;
00061 if ((spaceAlignment & Qt::AlignLeft)) {
00062 power |= PushOverBorder;
00063 }
00064 performPush(groupId, DirRight, push, power);
00065 }
00066
00067
00068 push = item.lastGeometry.right()+screenSpacing - workingGeom.width();
00069 if (push > 0) {
00070 item.animateMovement = true;
00071 power = PushAwayFromPreferred;
00072 if ((spaceAlignment & Qt::AlignRight)) {
00073 power |= PushOverBorder;
00074 }
00075 performPush(groupId, DirLeft, push, power);
00076 }
00077
00078
00079 push = screenSpacing - item.lastGeometry.top();
00080 if (push > 0) {
00081 item.animateMovement = true;
00082 power = PushAwayFromPreferred;
00083 if ((spaceAlignment & Qt::AlignTop)) {
00084 power |= PushOverBorder;
00085 }
00086 performPush(groupId, DirDown, push, power);
00087 }
00088
00089
00090 push = item.lastGeometry.bottom()+screenSpacing - workingGeom.height();
00091 if (push > 0) {
00092 item.animateMovement = true;
00093 power = PushAwayFromPreferred;
00094 if ((spaceAlignment & Qt::AlignBottom)) {
00095 power |= PushOverBorder;
00096 }
00097 performPush(groupId, DirUp, push, power);
00098 }
00099
00100
00101
00102
00103
00104
00105 if (item.pushBack) {
00106
00107 push = item.preferredGeometry.left() - item.lastGeometry.left();
00108 if (push > 0) {
00109 performPush(groupId, DirRight, push, NoPower);
00110 } else if (push < 0) {
00111 performPush(groupId, DirLeft, -push, NoPower);
00112 }
00113
00114 push = item.preferredGeometry.top() - item.lastGeometry.top();
00115 if (push > 0) {
00116 performPush(groupId, DirDown, push, NoPower);
00117 } else if (push < 0) {
00118 performPush(groupId, DirUp, -push, NoPower);
00119 }
00120 }
00121 }
00122 }
00123 }
00124
00125 qreal ItemSpace::positionVisibility (QRectF geom)
00126 {
00127 QRectF visibleArea = QRectF(QPointF(), workingGeom);
00128 QRectF visibleItemPart = visibleArea.intersected(geom);
00129 qreal itemSurface = geom.width() * geom.height();
00130 qreal itemVisibleSurface = visibleItemPart.width() * visibleItemPart.height();
00131 return (itemVisibleSurface / itemSurface);
00132 }
00133
00134 void ItemSpace::offsetPositions(const QPointF &offset)
00135 {
00136 for (int groupId = 0; groupId < m_groups.size(); groupId++) {
00137 ItemGroup &group = m_groups[groupId];
00138
00139 for (int itemId = 0; itemId < group.m_groupItems.size(); itemId++) {
00140 ItemSpaceItem &item = group.m_groupItems[itemId];
00141
00142 item.preferredGeometry.adjust(offset.x(), offset.y(), offset.x(), offset.y());
00143 item.lastGeometry.adjust(offset.x(), offset.y(), offset.x(), offset.y());
00144 }
00145 }
00146 }
00147
00148 qreal ItemSpace::performPush(int groupId, Direction direction, qreal amount, PushPower power)
00149 {
00150 ItemGroup &group = m_groups[groupId];
00151
00152 preparePush(direction, power);
00153 group.addRequest(this, ItemGroup::Request(-1, 0, amount));
00154 group.applyResults(this, -1);
00155 return group.m_pushAvailable;
00156 }
00157
00158 bool ItemSpace::positionedProperly(QRectF itemGeom)
00159 {
00160 QRectF fullGeom = itemGeom.adjusted(-placementSpacing, -placementSpacing, placementSpacing, placementSpacing);
00161 return (QRectF(QPointF(), workingGeom).contains(fullGeom));
00162 }
00163
00164 QList<QPointF> ItemSpace::positionVertically(
00165 const QSizeF &itemSize,
00166 Qt::Alignment align,
00167 bool limitedSpace,
00168 bool findAll
00169 ) const
00170 {
00171 qreal spL = placementSpacing;
00172 qreal spR = placementSpacing;
00173 qreal spT = placementSpacing;
00174 qreal spB = placementSpacing;
00175 QList<QPointF> possiblePositions;
00176
00177
00178
00179
00180
00181 QSizeF size = QSizeF(itemSize.width()+spL+spR, itemSize.height()+spT+spB);
00182
00183
00184
00185 qreal x = ((align & Qt::AlignLeft) ? 0 : workingGeom.width()-size.width());
00186
00187 for (int i = 0; i < 100; ++i) {
00188
00189 bool outOfX = ((align & Qt::AlignLeft) ? (x + size.width() > workingGeom.width()) : (x < 0));
00190 if (outOfX && limitedSpace) {
00191 break;
00192 }
00193
00194
00195
00196 qreal y = ((align & Qt::AlignTop) ? 0 : workingGeom.height()-size.height());
00197
00198 while (1) {
00199
00200 bool outOfY = ((align & Qt::AlignTop) ? (y + size.height() > workingGeom.height()) : (y < 0));
00201 if (outOfY && limitedSpace) {
00202 break;
00203 }
00204
00205
00206
00207
00208
00209
00210
00211
00212
00213
00214
00215 QRectF a;
00216 if ((align & Qt::AlignTop)) {
00217 a = itemInRegionEndingLastVert(QRectF(x, y, size.width(), size.height()));
00218 } else {
00219 a = itemInRegionStartingFirstVert(QRectF(x, y, size.width(), size.height()));
00220 }
00221
00222 if (!a.isValid()) {
00223
00224 possiblePositions.append(QPointF(x+spL, y+spT));
00225 if (!findAll) {
00226 return possiblePositions;
00227 }
00228
00229 break;
00230 }
00231
00232 Q_ASSERT( ((align & Qt::AlignTop) && a.bottom() > y) || ((align & Qt::AlignBottom) && a.y() - size.height() < y) );
00233
00234 y = ((align & Qt::AlignTop) ? a.bottom() : a.y() - size.height());
00235 }
00236
00237
00238
00239
00240
00241
00242
00243
00244
00245
00246
00247 QRectF a;
00248 if ((align & Qt::AlignLeft)) {
00249 a = itemInRegionEndingFirstHoriz(QRectF(x, 0, size.width(), workingGeom.height()));
00250 } else {
00251 a = itemInRegionStartingLastHoriz(QRectF(x, 0, size.width(), workingGeom.height()));
00252 }
00253
00254 if (!a.isValid()) {
00255 break;
00256 }
00257
00258 Q_ASSERT( ((align & Qt::AlignLeft) && a.right() > x) || ((align & Qt::AlignRight) && a.x() - size.width() < x) );
00259
00260 x = ((align & Qt::AlignLeft) ? a.right() : a.x() - size.width());
00261 }
00262
00263 return possiblePositions;
00264 }
00265
00266 QRectF ItemSpace::itemInRegionStartingFirstVert(const QRectF ®ion) const
00267 {
00268 QRectF ret = QRectF(0,0,-1,-1);
00269 qreal l = std::numeric_limits<qreal>::max();
00270
00271 for (int groupId = 0; groupId < m_groups.size(); groupId++) {
00272 const ItemGroup &group = m_groups[groupId];
00273
00274 for (int itemId = 0; itemId < group.m_groupItems.size(); itemId++) {
00275 const ItemSpaceItem &item = group.m_groupItems[itemId];
00276
00277 if (!item.lastGeometry.isValid()) {
00278 continue;
00279 }
00280 qreal cl = item.lastGeometry.y();
00281 if (item.lastGeometry.intersects(region) && cl < l) {
00282 ret = item.lastGeometry;
00283 l = cl;
00284 }
00285 }
00286 }
00287 return ret;
00288 }
00289
00290 QRectF ItemSpace::itemInRegionEndingLastVert(const QRectF ®ion) const
00291 {
00292 QRectF ret = QRectF(0,0,-1,-1);
00293 qreal l = -1;
00294
00295 for (int groupId = 0; groupId < m_groups.size(); groupId++) {
00296 const ItemGroup &group = m_groups[groupId];
00297
00298 for (int itemId = 0; itemId < group.m_groupItems.size(); itemId++) {
00299 const ItemSpaceItem &item = group.m_groupItems[itemId];
00300
00301 if (!item.lastGeometry.isValid()) {
00302 continue;
00303 }
00304 qreal cl = item.lastGeometry.y() + item.lastGeometry.height();
00305 if (item.lastGeometry.intersects(region) && cl > l) {
00306 ret = item.lastGeometry;
00307 l = cl;
00308 }
00309 }
00310 }
00311 return ret;
00312 }
00313
00314 QRectF ItemSpace::itemInRegionEndingFirstHoriz(const QRectF ®ion) const
00315 {
00316 QRectF ret = QRectF(0,0,-1,-1);
00317 qreal l = std::numeric_limits<qreal>::max();
00318
00319 for (int groupId = 0; groupId < m_groups.size(); groupId++) {
00320 const ItemGroup &group = m_groups[groupId];
00321
00322 for (int itemId = 0; itemId < group.m_groupItems.size(); itemId++) {
00323 const ItemSpaceItem &item = group.m_groupItems[itemId];
00324
00325 if (!item.lastGeometry.isValid()) {
00326 continue;
00327 }
00328 qreal cl = item.lastGeometry.x() + item.lastGeometry.width();
00329 if (item.lastGeometry.intersects(region) && cl < l) {
00330 ret = item.lastGeometry;
00331 l = cl;
00332 }
00333 }
00334 }
00335 return ret;
00336 }
00337
00338 QRectF ItemSpace::itemInRegionStartingLastHoriz(const QRectF ®ion) const
00339 {
00340 QRectF ret = QRectF(0,0,-1,-1);
00341 qreal l = -1;
00342
00343 for (int groupId = 0; groupId < m_groups.size(); groupId++) {
00344 const ItemGroup &group = m_groups[groupId];
00345
00346 for (int itemId = 0; itemId < group.m_groupItems.size(); itemId++) {
00347 const ItemSpaceItem &item = group.m_groupItems[itemId];
00348
00349 if (!item.lastGeometry.isValid()) {
00350 continue;
00351 }
00352 qreal cl = item.lastGeometry.x();
00353 if (item.lastGeometry.intersects(region) && cl > l) {
00354 ret = item.lastGeometry;
00355 l = cl;
00356 }
00357 }
00358 }
00359 return ret;
00360 }
00361
00362 ItemSpace::ItemGroup::Request::Request(
00363 int sourceGroup,
00364 qreal sourceGroupPushRequested,
00365 qreal pushRequested
00366 )
00367 : m_sourceGroup(sourceGroup),
00368 m_sourceGroupPushRequested(sourceGroupPushRequested),
00369 m_pushRequested(pushRequested),
00370 m_compensated(false)
00371 {
00372 }
00373
00374 void ItemSpace::ItemGroup::Request::activate (ItemSpace *itemSpace, ItemGroup *group)
00375 {
00376
00377
00378 if (group->m_largestPushRequested >= m_pushRequested) {
00379 return;
00380 }
00381
00382 qreal largest = group->m_largestPushRequested;
00383
00384 group->m_largestPushRequested = m_pushRequested;
00385
00386 if (group->m_pushAvailable < largest) {
00387 return;
00388 }
00389
00390
00391
00392 group->m_pushAvailable = m_pushRequested;
00393
00394
00395 for (int itemId = 0; itemId < group->m_groupItems.size(); itemId++) {
00396 ItemSpaceItem &item = group->m_groupItems[itemId];
00397 QRectF origGeom = item.lastGeometry;
00398 QRectF fullGeom = origGeom.adjusted(-itemSpace->shiftingSpacing, -itemSpace->shiftingSpacing,
00399 itemSpace->shiftingSpacing, itemSpace->shiftingSpacing);
00400
00401
00402 if (!(itemSpace->m_power & PushOverBorder)) {
00403 qreal limit;
00404 switch (itemSpace->m_direction) {
00405 case DirLeft:
00406 limit = origGeom.left() - itemSpace->screenSpacing;
00407 break;
00408 case DirRight:
00409 limit = itemSpace->workingGeom.width() - itemSpace->screenSpacing - origGeom.right();
00410 break;
00411 case DirUp:
00412 limit = origGeom.top() - itemSpace->screenSpacing;
00413 break;
00414 case DirDown:
00415 limit = itemSpace->workingGeom.height() - itemSpace->screenSpacing - origGeom.bottom();
00416 break;
00417 }
00418 group->m_pushAvailable = qMax(qreal(0.0), qMin(group->m_pushAvailable, limit));
00419 if (group->m_pushAvailable == 0) {
00420 break;
00421 }
00422 }
00423
00424
00425 if (!(itemSpace->m_power & PushAwayFromPreferred) && item.pushBack) {
00426 qreal limit;
00427 switch (itemSpace->m_direction) {
00428 case DirLeft:
00429 limit = origGeom.left() - item.preferredGeometry.left();
00430 break;
00431 case DirRight:
00432 limit = -(origGeom.left() - item.preferredGeometry.left());
00433 break;
00434 case DirUp:
00435 limit = origGeom.top() - item.preferredGeometry.top();
00436 break;
00437 case DirDown:
00438 limit = -(origGeom.top() - item.preferredGeometry.top());
00439 break;
00440 }
00441 limit = qMax(qreal(0.0), limit);
00442 group->m_pushAvailable = qMin(group->m_pushAvailable, limit);
00443 if (group->m_pushAvailable == 0) {
00444 break;
00445 }
00446 }
00447
00448
00449 for (int testGroupId = 0; testGroupId < itemSpace->m_groups.size(); testGroupId++) {
00450 QList<int> asa;
00451 if (testGroupId == group->m_id || group->groupIsAbove(itemSpace, asa, testGroupId)) {
00452 continue;
00453 }
00454 ItemGroup &testGroup = itemSpace->m_groups[testGroupId];
00455
00456
00457 qreal groupPush = 0;
00458 for (int testItemId = 0; testItemId < testGroup.m_groupItems.size(); testItemId++) {
00459 ItemSpaceItem &testItem = testGroup.m_groupItems[testItemId];
00460
00461 QRectF newlyTakenSpace;
00462 qreal push;
00463 switch (itemSpace->m_direction) {
00464 case DirLeft:
00465 newlyTakenSpace = QRectF(fullGeom.left() - group->m_pushAvailable, fullGeom.top(), group->m_pushAvailable, fullGeom.height());
00466 push = testItem.lastGeometry.right() - newlyTakenSpace.left();
00467 break;
00468 case DirRight:
00469 newlyTakenSpace = QRectF(fullGeom.right(), fullGeom.top(), group->m_pushAvailable, fullGeom.height());
00470 push = newlyTakenSpace.right() - testItem.lastGeometry.left();
00471 break;
00472 case DirUp:
00473 newlyTakenSpace = QRectF(fullGeom.left(), fullGeom.top() - group->m_pushAvailable, fullGeom.width(), group->m_pushAvailable);
00474 push = testItem.lastGeometry.bottom() - newlyTakenSpace.top();
00475 break;
00476 case DirDown:
00477 newlyTakenSpace = QRectF(fullGeom.left(), fullGeom.bottom(), fullGeom.width(), group->m_pushAvailable);
00478 push = newlyTakenSpace.bottom() - testItem.lastGeometry.top();
00479 break;
00480 }
00481
00482
00483 if (testItem.lastGeometry.intersects(newlyTakenSpace)) {
00484 groupPush = qMax(groupPush, push);
00485 }
00486 }
00487
00488 if (groupPush == 0) {
00489 continue;
00490 }
00491
00492
00493 if (!group->m_obstacles.contains(testGroupId)) {
00494 group->m_obstacles.append(testGroupId);
00495 }
00496 testGroup.addRequest(itemSpace, Request(group->m_id, group->m_pushAvailable, groupPush));
00497
00498
00499 if (testGroup.m_pushAvailable < groupPush) {
00500 group->m_pushAvailable = qMax(qreal(0.0), group->m_pushAvailable - (groupPush - testGroup.m_pushAvailable));
00501 if (group->m_pushAvailable == 0) {
00502 break;
00503 }
00504 }
00505 }
00506 }
00507 }
00508
00509 void ItemSpace::ItemGroup::resetPush(int id)
00510 {
00511 m_id = id;
00512 m_largestPushRequested = 0,
00513 m_pushAvailable = std::numeric_limits<qreal>::max();
00514 m_requests = QList<Request>();
00515 m_obstacles = QList<int>();
00516 }
00517
00518 void ItemSpace::ItemGroup::addRequest (ItemSpace *itemSpace, const class Request &request)
00519 {
00520 m_requests.append(request);
00521 m_requests.last().activate(itemSpace, this);
00522 }
00523
00524 void ItemSpace::ItemGroup::applyResults(ItemSpace *itemSpace, int cameFrom)
00525 {
00526 bool notComplete = false;
00527 for (int i = 0; i < m_requests.size(); i++) {
00528 Request &request = m_requests[i];
00529 if (request.m_sourceGroup == -1) {
00530 continue;
00531 }
00532
00533 if (request.m_sourceGroup == cameFrom) {
00534 qreal pushLost = request.m_sourceGroupPushRequested - itemSpace->m_groups[cameFrom].m_pushAvailable;
00535 request.m_pushRequested -= pushLost;
00536 request.m_compensated = true;
00537 } else if (!request.m_compensated) {
00538 notComplete = true;
00539 }
00540 }
00541
00542 if (notComplete) {
00543 return;
00544 }
00545
00546 qreal totalPushRequired = 0;
00547 for (int i = 0; i < m_requests.size(); i++) {
00548 Request &request = m_requests[i];
00549 totalPushRequired = qMax(totalPushRequired, request.m_pushRequested);
00550 }
00551 m_pushAvailable = qMin(m_pushAvailable, totalPushRequired);
00552
00553 for (int groupId = 0; groupId < m_groupItems.size(); groupId++) {
00554 ItemSpaceItem &groupItem = m_groupItems[groupId];
00555
00556 switch (itemSpace->m_direction) {
00557 case DirLeft:
00558 groupItem.lastGeometry = groupItem.lastGeometry.adjusted(-m_pushAvailable, 0, -m_pushAvailable, 0);
00559 break;
00560 case DirRight:
00561 groupItem.lastGeometry = groupItem.lastGeometry.adjusted(m_pushAvailable, 0, m_pushAvailable, 0);
00562 break;
00563 case DirUp:
00564 groupItem.lastGeometry = groupItem.lastGeometry.adjusted(0, -m_pushAvailable, 0, -m_pushAvailable);
00565 break;
00566 case DirDown:
00567 groupItem.lastGeometry = groupItem.lastGeometry.adjusted(0, m_pushAvailable, 0, m_pushAvailable);
00568 break;
00569 }
00570 }
00571
00572 foreach (int obstacleId, m_obstacles) {
00573 itemSpace->m_groups[obstacleId].applyResults(itemSpace, m_id);
00574 }
00575 }
00576
00577 bool ItemSpace::ItemGroup::groupIsAbove(ItemSpace *itemSpace, QList<int> &visited, int groupId)
00578 {
00579 foreach (const Request &request, m_requests) {
00580 if (request.m_sourceGroup == -1 || visited.contains(request.m_sourceGroup)) {
00581 continue;
00582 }
00583 if (request.m_sourceGroup == groupId) {
00584 return true;
00585 }
00586 visited.append(request.m_sourceGroup);
00587 if (itemSpace->m_groups[request.m_sourceGroup].groupIsAbove(itemSpace, visited, groupId)) {
00588 return true;
00589 }
00590 }
00591 return false;
00592 }
00593
00594
00595 void ItemSpace::addItem(ItemSpaceItem newItem)
00596 {
00597 QList<ItemSpaceItem> newGroupItems;
00598 QRectF newItemGeom = newItem.lastGeometry.adjusted(-shiftingSpacing, -shiftingSpacing,
00599 shiftingSpacing, shiftingSpacing);
00600
00601
00602 for (int groupId = 0; groupId < m_groups.size();) {
00603 ItemGroup &group = m_groups[groupId];
00604
00605
00606 bool removeGroup = false;
00607 for (int itemId = 0; itemId < group.m_groupItems.size(); itemId++) {
00608 ItemSpaceItem &item = group.m_groupItems[itemId];
00609 if (newItemGeom.intersects(item.lastGeometry)) {
00610 removeGroup = true;
00611 break;
00612 }
00613 }
00614
00615 if (removeGroup) {
00616 newGroupItems << group.m_groupItems;
00617 m_groups.removeAt(groupId);
00618 } else {
00619 groupId++;
00620 }
00621 }
00622
00623
00624 m_groups.append(ItemGroup());
00625 ItemGroup &newGroup = m_groups.last();
00626 newGroup.m_groupItems.append(newItem);
00627 newGroup.m_groupItems << newGroupItems;
00628 }
00629
00630
00631 void ItemSpace::removeItem(int removeGroup, int removeItemInGroup)
00632 {
00633
00634 m_groups[removeGroup].m_groupItems.removeAt(removeItemInGroup);
00635
00636 QList<ItemSpaceItem> otherGroupItems = m_groups[removeGroup].m_groupItems;
00637
00638 m_groups.removeAt(removeGroup);
00639
00640 foreach (const ItemSpaceItem &item, otherGroupItems) {
00641 addItem(item);
00642 }
00643 }
00644
00645
00646 void ItemSpace::updateItem(int group, int itemInGroup)
00647 {
00648 ItemSpaceItem copy = m_groups[group].m_groupItems[itemInGroup];
00649 removeItem(group, itemInGroup);
00650 addItem(copy);
00651 }
00652
00653 bool ItemSpace::locateItemByPosition(int pos, int *groupIndex, int *itemInGroup) const
00654 {
00655 int current = 0;
00656 for (int groupId = 0; groupId < m_groups.size(); groupId++) {
00657 ItemGroup group = m_groups[groupId];
00658 if (current + group.m_groupItems.size() > pos) {
00659 *groupIndex = groupId;
00660 *itemInGroup = pos - current;
00661 return true;
00662 }
00663 current += group.m_groupItems.size();
00664 }
00665 return false;
00666 }
00667
00668 bool ItemSpace::locateItemByUser(QVariant user, int *groupIndex, int *itemInGroup) const
00669 {
00670 for (int groupId = 0; groupId < m_groups.size(); groupId++) {
00671 ItemGroup group = m_groups[groupId];
00672 for (int itemId = 0; itemId < group.m_groupItems.size(); itemId++) {
00673 ItemSpaceItem &item = group.m_groupItems[itemId];
00674 if (item.user == user) {
00675 *groupIndex = groupId;
00676 *itemInGroup = itemId;
00677 return true;
00678 }
00679 }
00680 }
00681 return false;
00682 }
00683
00684 void ItemSpace::preparePush(Direction direction, PushPower power)
00685 {
00686 m_direction = direction;
00687 m_power = power;
00688
00689 for (int i=0; i<m_groups.size(); i++) {
00690 m_groups[i].resetPush(i);
00691 }
00692 }