workspace/plasma/containments/desktop/itemspace.cpp

   1 /*
   2   Copyright (c) 2008 Ambroz Bizjak <ambro@b4ever.net>
   3
   4   This program is free software; you can redistribute it and/or modify
   5   it under the terms of the GNU General Public License as published by
   6   the Free Software Foundation; either version 2 of the License, or
   7   (at your option) any later version.
   8 */
   9
  10 #include <limits>
  11
  12 #include <KDebug>
  13
  14 #include "itemspace.h"
  15
  16 ItemSpace::ItemSpace()
  17   : spaceAlignment(Qt::AlignTop|Qt::AlignLeft),
  18     workingGeom(QSizeF()),
  19     placementSpacing(0),
  20     screenSpacing(0),
  21     shiftingSpacing(0)
  22 {
  23 }
  24
  25 void ItemSpace::setWorkingArea(QSizeF area)
  26 {
  27     if (workingGeom.isValid()) {
  28         // if the working area size changed and alignment includes right or bottom,
  29         // the difference is added to all positions to keep items in the same place
  30         // relative to the borders of alignment
  31         if (((spaceAlignment & Qt::AlignRight) || (spaceAlignment & Qt::AlignBottom)) &&
  32             (area.width() != workingGeom.width() || area.height() != workingGeom.height())) {
  33             offsetPositions(QPointF(area.width()-workingGeom.width(), area.height()-workingGeom.height()));
  34         }
  35     }
  36     workingGeom = area;
  37 }
  38
  39 void ItemSpace::activate()
  40 {
  41     for (int groupId = 0; groupId < m_groups.size(); groupId++) {
  42         ItemGroup &group = m_groups[groupId];
  43
  44         for (int itemId = 0; itemId < group.m_groupItems.size(); itemId++) {
  45             ItemSpaceItem &item = group.m_groupItems[itemId];
  46
  47             qreal push;
  48             PushPower power;
  49
  50             /*
  51               Push items intersecting working area borders inside.
  52               For borders adjunct to the corner of alignment, allow pushing
  53               over the opposite border (and items there may be temporarily placed).
  54             */
  55
  56             // left border
  57             push = screenSpacing - item.lastGeometry.left();
  58             if (push > 0) {
  59                 item.animateMovement = true;
  60                 power = PushAwayFromPreferred;
  61                 if ((spaceAlignment & Qt::AlignLeft)) {
  62                     power |= PushOverBorder;
  63                 }
  64                 performPush(groupId, DirRight, push, power);
  65             }
  66
  67             // right border
  68             push = item.lastGeometry.right()+screenSpacing - workingGeom.width();
  69             if (push > 0) {
  70                 item.animateMovement = true;
  71                 power = PushAwayFromPreferred;
  72                 if ((spaceAlignment & Qt::AlignRight)) {
  73                     power |= PushOverBorder;
  74                 }
  75                 performPush(groupId, DirLeft, push, power);
  76             }
  77
  78             // top border
  79             push = screenSpacing - item.lastGeometry.top();
  80             if (push > 0) {
  81                 item.animateMovement = true;
  82                 power = PushAwayFromPreferred;
  83                 if ((spaceAlignment & Qt::AlignTop)) {
  84                     power |= PushOverBorder;
  85                 }
  86                 performPush(groupId, DirDown, push, power);
  87             }
  88
  89             // bottom border
  90             push = item.lastGeometry.bottom()+screenSpacing - workingGeom.height();
  91             if (push > 0) {
  92                 item.animateMovement = true;
  93                 power = PushAwayFromPreferred;
  94                 if ((spaceAlignment & Qt::AlignBottom)) {
  95                     power |= PushOverBorder;
  96                 }
  97                 performPush(groupId, DirUp, push, power);
  98             }
  99
 100             /*
 101               Push items back towards their perferred positions.
 102               Cannot push items out of the working area,
 103               cannot push items away from their preferred positions.
 104             */
 105             if (item.pushBack) {
 106                 // left/right
 107                 push = item.preferredGeometry.left() - item.lastGeometry.left();
 108                 if (push > 0) {
 109                     performPush(groupId, DirRight, push, NoPower);
 110                 } else if (push < 0) {
 111                     performPush(groupId, DirLeft, -push, NoPower);
 112                 }
 113                 // up/down
 114                 push = item.preferredGeometry.top() - item.lastGeometry.top();
 115                 if (push > 0) {
 116                     performPush(groupId, DirDown, push, NoPower);
 117                 } else if (push < 0) {
 118                     performPush(groupId, DirUp, -push, NoPower);
 119                 }
 120             }
 121         }
 122     }
 123 }
 124
 125 qreal ItemSpace::positionVisibility (QRectF geom)
 126 {
 127     QRectF visibleArea = QRectF(QPointF(), workingGeom);
 128     QRectF visibleItemPart = visibleArea.intersected(geom);
 129     qreal itemSurface = geom.width() * geom.height();
 130     qreal itemVisibleSurface = visibleItemPart.width() * visibleItemPart.height();
 131     return (itemVisibleSurface / itemSurface);
 132 }
 133
 134 void ItemSpace::offsetPositions(const QPointF &offset)
 135 {
 136     for (int groupId = 0; groupId < m_groups.size(); groupId++) {
 137         ItemGroup &group = m_groups[groupId];
 138
 139         for (int itemId = 0; itemId < group.m_groupItems.size(); itemId++) {
 140             ItemSpaceItem &item = group.m_groupItems[itemId];
 141
 142             item.preferredGeometry.adjust(offset.x(), offset.y(), offset.x(), offset.y());
 143             item.lastGeometry.adjust(offset.x(), offset.y(), offset.x(), offset.y());
 144         }
 145     }
 146 }
 147
 148 qreal ItemSpace::performPush(int groupId, Direction direction, qreal amount, PushPower power)
 149 {
 150     ItemGroup &group = m_groups[groupId];
 151
 152     preparePush(direction, power);
 153     group.addRequest(this, ItemGroup::Request(-1, 0, amount));
 154     group.applyResults(this, -1);
 155     return group.m_pushAvailable;
 156 }
 157
 158 bool ItemSpace::positionedProperly(QRectF itemGeom)
 159 {
 160     QRectF fullGeom = itemGeom.adjusted(-placementSpacing, -placementSpacing, placementSpacing, placementSpacing);
 161     return (QRectF(QPointF(), workingGeom).contains(fullGeom));
 162 }
 163
 164 QList<QPointF> ItemSpace::positionVertically(
 165     const QSizeF &itemSize,
 166     Qt::Alignment align,
 167     bool limitedSpace,
 168     bool findAll
 169 ) const
 170 {
 171     qreal spL = placementSpacing;
 172     qreal spR = placementSpacing;
 173     qreal spT = placementSpacing;
 174     qreal spB = placementSpacing;
 175     QList<QPointF> possiblePositions;
 176
 177     // basically, position searching is done by repetedly looking for obstacles at
 178     // one position and looking for a next position to try
 179
 180     // add spacing to the size
 181     QSizeF size = QSizeF(itemSize.width()+spL+spR, itemSize.height()+spT+spB);
 182
 183     // the initial x coordinate to start testing
 184     // start either on the left or the right, and advance inside
 185     qreal x = ((align & Qt::AlignLeft) ? 0 : workingGeom.width()-size.width());
 186     // try different x coordinates
 187     for (int i = 0; i < 100; ++i) {
 188         // stop testing if we're limited by the working area and positions at the next x would reach outside
 189         bool outOfX = ((align & Qt::AlignLeft) ? (x + size.width() > workingGeom.width()) : (x < 0));
 190         if (outOfX && limitedSpace) {
 191             break;
 192         }
 193
 194         // the initial y coordinate to start testing heights at the current x
 195         // start either on the top or the bottom, and advance inside
 196         qreal y = ((align & Qt::AlignTop) ? 0 : workingGeom.height()-size.height());
 197         // try different y coordinates
 198         while (1) {
 199             // stop testing at this x if we're limited by the working area and positions at the next y would reach outside
 200             bool outOfY = ((align & Qt::AlignTop) ? (y + size.height() > workingGeom.height()) : (y < 0));
 201             if (outOfY && limitedSpace) {
 202                 break;
 203             }
 204
 205             // Z would come here :)
 206
 207             // Check for intersecting items, or a new y coordinate to try.
 208             // Suppose we're aligning to top:
 209             // Find all items that intersect the region we're testing.
 210             // If no items were found, we have space.
 211             // Oterwise pick the one with the lowest bottom border
 212             // and use that border as the new y coordinate to try.
 213             // The logic is inverted when aligning to bottom.
 214
 215             QRectF a;
 216             if ((align & Qt::AlignTop)) {
 217                 a = itemInRegionEndingLastVert(QRectF(x, y, size.width(), size.height()));
 218             } else {
 219                 a = itemInRegionStartingFirstVert(QRectF(x, y, size.width(), size.height()));
 220             }
 221
 222             if (!a.isValid()) {
 223                 // found a valid position
 224                 possiblePositions.append(QPointF(x+spL, y+spT));
 225                 if (!findAll) {
 226                     return possiblePositions;
 227                 }
 228                 // don't look at this X anymore, one position is enough
 229                 break;
 230             }
 231
 232             Q_ASSERT( ((align & Qt::AlignTop) && a.bottom() > y) || ((align & Qt::AlignBottom) && a.y() - size.height() < y) );
 233
 234             y = ((align & Qt::AlignTop) ? a.bottom() : a.y() - size.height());
 235         }
 236
 237         // Find next possible x coordinate
 238         // Suppose we're aligning to left:
 239         // Take a vertical strap of the area we have been testing previously,
 240         // extending over the height of the working area.
 241         // Find all items that intersect the region we're testing.
 242         // If no items were found, stop all testing.
 243         // Otherwise, pick the one with the most-left right border
 244         // and use that border as the new x coordinate to try.
 245         // The logic is inverted when aligning to right.
 246
 247         QRectF a;
 248         if ((align & Qt::AlignLeft)) {
 249             a = itemInRegionEndingFirstHoriz(QRectF(x, 0, size.width(), workingGeom.height()));
 250         } else {
 251             a = itemInRegionStartingLastHoriz(QRectF(x, 0, size.width(), workingGeom.height()));
 252         }
 253
 254         if (!a.isValid()) {
 255             break;
 256         }
 257
 258         Q_ASSERT( ((align & Qt::AlignLeft) && a.right() > x) || ((align & Qt::AlignRight) && a.x() - size.width() < x) );
 259
 260         x = ((align & Qt::AlignLeft) ? a.right() : a.x() - size.width());
 261     }
 262
 263     return possiblePositions;
 264 }
 265
 266 QRectF ItemSpace::itemInRegionStartingFirstVert(const QRectF &region) const
 267 {
 268     QRectF ret = QRectF(0,0,-1,-1);
 269     qreal l = std::numeric_limits<qreal>::max();
 270
 271     for (int groupId = 0; groupId < m_groups.size(); groupId++) {
 272         const ItemGroup &group = m_groups[groupId];
 273
 274         for (int itemId = 0; itemId < group.m_groupItems.size(); itemId++) {
 275             const ItemSpaceItem &item = group.m_groupItems[itemId];
 276
 277             if (!item.lastGeometry.isValid()) {
 278               continue;
 279             }
 280             qreal cl = item.lastGeometry.y();
 281             if (item.lastGeometry.intersects(region) && cl < l) {
 282                 ret = item.lastGeometry;
 283                 l = cl;
 284             }
 285         }
 286     }
 287     return ret;
 288 }
 289
 290 QRectF ItemSpace::itemInRegionEndingLastVert(const QRectF &region) const
 291 {
 292     QRectF ret = QRectF(0,0,-1,-1);
 293     qreal l = -1;
 294
 295     for (int groupId = 0; groupId < m_groups.size(); groupId++) {
 296         const ItemGroup &group = m_groups[groupId];
 297
 298         for (int itemId = 0; itemId < group.m_groupItems.size(); itemId++) {
 299             const ItemSpaceItem &item = group.m_groupItems[itemId];
 300
 301             if (!item.lastGeometry.isValid()) {
 302               continue;
 303             }
 304             qreal cl = item.lastGeometry.y() + item.lastGeometry.height();
 305             if (item.lastGeometry.intersects(region) && cl > l) {
 306                 ret = item.lastGeometry;
 307                 l = cl;
 308             }
 309         }
 310     }
 311     return ret;
 312 }
 313
 314 QRectF ItemSpace::itemInRegionEndingFirstHoriz(const QRectF &region) const
 315 {
 316     QRectF ret = QRectF(0,0,-1,-1);
 317     qreal l = std::numeric_limits<qreal>::max();
 318
 319     for (int groupId = 0; groupId < m_groups.size(); groupId++) {
 320         const ItemGroup &group = m_groups[groupId];
 321
 322         for (int itemId = 0; itemId < group.m_groupItems.size(); itemId++) {
 323             const ItemSpaceItem &item = group.m_groupItems[itemId];
 324
 325             if (!item.lastGeometry.isValid()) {
 326               continue;
 327             }
 328             qreal cl = item.lastGeometry.x() + item.lastGeometry.width();
 329             if (item.lastGeometry.intersects(region) && cl < l) {
 330                 ret = item.lastGeometry;
 331                 l = cl;
 332             }
 333         }
 334     }
 335     return ret;
 336 }
 337
 338 QRectF ItemSpace::itemInRegionStartingLastHoriz(const QRectF &region) const
 339 {
 340     QRectF ret = QRectF(0,0,-1,-1);
 341     qreal l = -1;
 342
 343     for (int groupId = 0; groupId < m_groups.size(); groupId++) {
 344         const ItemGroup &group = m_groups[groupId];
 345
 346         for (int itemId = 0; itemId < group.m_groupItems.size(); itemId++) {
 347             const ItemSpaceItem &item = group.m_groupItems[itemId];
 348
 349             if (!item.lastGeometry.isValid()) {
 350               continue;
 351             }
 352             qreal cl = item.lastGeometry.x();
 353             if (item.lastGeometry.intersects(region) && cl > l) {
 354                 ret = item.lastGeometry;
 355                 l = cl;
 356             }
 357         }
 358     }
 359     return ret;
 360 }
 361
 362 ItemSpace::ItemGroup::Request::Request(
 363     int sourceGroup,
 364     qreal sourceGroupPushRequested,
 365     qreal pushRequested
 366 )
 367   : m_sourceGroup(sourceGroup),
 368     m_sourceGroupPushRequested(sourceGroupPushRequested),
 369     m_pushRequested(pushRequested),
 370     m_compensated(false)
 371 {
 372 }
 373
 374 void ItemSpace::ItemGroup::Request::activate (ItemSpace *itemSpace, ItemGroup *group)
 375 {
 376     // don't do anything if the group was already asked to move at
 377     // least as much as we ask
 378     if (group->m_largestPushRequested >= m_pushRequested) {
 379         return;
 380     }
 381
 382     qreal largest = group->m_largestPushRequested;
 383     // record our request as the largest
 384     group->m_largestPushRequested = m_pushRequested;
 385     // don't do anything if the group already hit an unmovable obstacle
 386     if (group->m_pushAvailable < largest) {
 387         return;
 388     }
 389
 390     // set the available push to our requested value
 391     // and limit it as obstacles are found
 392     group->m_pushAvailable = m_pushRequested;
 393
 394     // look for obstacles for every item in the group
 395     for (int itemId = 0; itemId < group->m_groupItems.size(); itemId++) {
 396         ItemSpaceItem &item = group->m_groupItems[itemId];
 397         QRectF origGeom = item.lastGeometry;
 398         QRectF fullGeom = origGeom.adjusted(-itemSpace->shiftingSpacing, -itemSpace->shiftingSpacing,
 399                                             itemSpace->shiftingSpacing, itemSpace->shiftingSpacing);
 400
 401         // limit push by screen boundaries
 402         if (!(itemSpace->m_power & PushOverBorder)) {
 403             qreal limit;
 404             switch (itemSpace->m_direction) {
 405                 case DirLeft:
 406                     limit = origGeom.left() - itemSpace->screenSpacing;
 407                     break;
 408                 case DirRight:
 409                     limit = itemSpace->workingGeom.width() - itemSpace->screenSpacing - origGeom.right();
 410                     break;
 411                 case DirUp:
 412                     limit = origGeom.top() - itemSpace->screenSpacing;
 413                     break;
 414                 case DirDown:
 415                     limit = itemSpace->workingGeom.height() - itemSpace->screenSpacing - origGeom.bottom();
 416                     break;
 417             }
 418             group->m_pushAvailable = qMax(qreal(0.0), qMin(group->m_pushAvailable, limit));
 419             if (group->m_pushAvailable == 0) {
 420                 break;
 421             }
 422         }
 423
 424         // limit push to not push the item away from its preferred position
 425         if (!(itemSpace->m_power & PushAwayFromPreferred) && item.pushBack) {
 426             qreal limit;
 427             switch (itemSpace->m_direction) {
 428                 case DirLeft:
 429                     limit = origGeom.left() - item.preferredGeometry.left();
 430                     break;
 431                 case DirRight:
 432                     limit = -(origGeom.left() - item.preferredGeometry.left());
 433                     break;
 434                 case DirUp:
 435                     limit = origGeom.top() - item.preferredGeometry.top();
 436                     break;
 437                 case DirDown:
 438                     limit = -(origGeom.top() - item.preferredGeometry.top());
 439                     break;
 440             }
 441             limit = qMax(qreal(0.0), limit);
 442             group->m_pushAvailable = qMin(group->m_pushAvailable, limit);
 443             if (group->m_pushAvailable == 0) {
 444                 break;
 445             }
 446         }
 447
 448         // look for items in the way
 449         for (int testGroupId = 0; testGroupId < itemSpace->m_groups.size(); testGroupId++) {
 450             QList<int> asa;
 451             if (testGroupId == group->m_id || group->groupIsAbove(itemSpace, asa, testGroupId)) {
 452                 continue;
 453             }
 454             ItemGroup &testGroup = itemSpace->m_groups[testGroupId];
 455
 456             // calculate how much the offending group needs to be pushed
 457             qreal groupPush = 0;
 458             for (int testItemId = 0; testItemId < testGroup.m_groupItems.size(); testItemId++) {
 459                 ItemSpaceItem &testItem = testGroup.m_groupItems[testItemId];
 460
 461                 QRectF newlyTakenSpace;
 462                 qreal push;
 463                 switch (itemSpace->m_direction) {
 464                 case DirLeft:
 465                     newlyTakenSpace = QRectF(fullGeom.left() - group->m_pushAvailable, fullGeom.top(), group->m_pushAvailable, fullGeom.height());
 466                     push = testItem.lastGeometry.right() - newlyTakenSpace.left();
 467                     break;
 468                 case DirRight:
 469                     newlyTakenSpace = QRectF(fullGeom.right(), fullGeom.top(), group->m_pushAvailable, fullGeom.height());
 470                     push = newlyTakenSpace.right() - testItem.lastGeometry.left();
 471                     break;
 472                 case DirUp:
 473                     newlyTakenSpace = QRectF(fullGeom.left(), fullGeom.top() - group->m_pushAvailable, fullGeom.width(), group->m_pushAvailable);
 474                     push = testItem.lastGeometry.bottom() - newlyTakenSpace.top();
 475                     break;
 476                 case DirDown:
 477                     newlyTakenSpace = QRectF(fullGeom.left(), fullGeom.bottom(), fullGeom.width(), group->m_pushAvailable);
 478                     push = newlyTakenSpace.bottom() - testItem.lastGeometry.top();
 479                     break;
 480                 }
 481
 482                 // check if it is an obstacle
 483                 if (testItem.lastGeometry.intersects(newlyTakenSpace)) {
 484                     groupPush = qMax(groupPush, push);
 485                 }
 486             }
 487
 488             if (groupPush == 0) {
 489                 continue;
 490             }
 491
 492             // post a move request to the obstacle
 493             if (!group->m_obstacles.contains(testGroupId)) {
 494                 group->m_obstacles.append(testGroupId);
 495             }
 496             testGroup.addRequest(itemSpace, Request(group->m_id, group->m_pushAvailable, groupPush));
 497
 498             // limit our push by how much the obstacle can actually move
 499             if (testGroup.m_pushAvailable < groupPush) {
 500                 group->m_pushAvailable = qMax(qreal(0.0), group->m_pushAvailable - (groupPush - testGroup.m_pushAvailable));
 501                 if (group->m_pushAvailable == 0) {
 502                     break;
 503                 }
 504             }
 505         }
 506     }
 507 }
 508
 509 void ItemSpace::ItemGroup::resetPush(int id)
 510 {
 511     m_id = id;
 512     m_largestPushRequested = 0,
 513     m_pushAvailable = std::numeric_limits<qreal>::max();
 514     m_requests = QList<Request>();
 515     m_obstacles = QList<int>();
 516 }
 517
 518 void ItemSpace::ItemGroup::addRequest (ItemSpace *itemSpace, const class Request &request)
 519 {
 520     m_requests.append(request);
 521     m_requests.last().activate(itemSpace, this);
 522 }
 523
 524 void ItemSpace::ItemGroup::applyResults(ItemSpace *itemSpace, int cameFrom)
 525 {
 526     bool notComplete = false;
 527     for (int i = 0; i < m_requests.size(); i++) {
 528         Request &request = m_requests[i];
 529         if (request.m_sourceGroup == -1) {
 530             continue;
 531         }
 532
 533         if (request.m_sourceGroup == cameFrom) {
 534             qreal pushLost = request.m_sourceGroupPushRequested - itemSpace->m_groups[cameFrom].m_pushAvailable;
 535             request.m_pushRequested -= pushLost;
 536             request.m_compensated = true;
 537         } else if (!request.m_compensated) {
 538             notComplete = true;
 539         }
 540     }
 541
 542     if (notComplete) {
 543         return;
 544     }
 545
 546     qreal totalPushRequired = 0;
 547     for (int i = 0; i < m_requests.size(); i++) {
 548         Request &request = m_requests[i];
 549         totalPushRequired = qMax(totalPushRequired, request.m_pushRequested);
 550     }
 551     m_pushAvailable = qMin(m_pushAvailable, totalPushRequired);
 552
 553     for (int groupId = 0; groupId < m_groupItems.size(); groupId++) {
 554         ItemSpaceItem &groupItem = m_groupItems[groupId];
 555
 556         switch (itemSpace->m_direction) {
 557             case DirLeft:
 558                 groupItem.lastGeometry = groupItem.lastGeometry.adjusted(-m_pushAvailable, 0, -m_pushAvailable, 0);
 559                 break;
 560             case DirRight:
 561                 groupItem.lastGeometry = groupItem.lastGeometry.adjusted(m_pushAvailable, 0, m_pushAvailable, 0);
 562                 break;
 563             case DirUp:
 564                 groupItem.lastGeometry = groupItem.lastGeometry.adjusted(0, -m_pushAvailable, 0, -m_pushAvailable);
 565                 break;
 566             case DirDown:
 567                 groupItem.lastGeometry = groupItem.lastGeometry.adjusted(0, m_pushAvailable, 0, m_pushAvailable);
 568                 break;
 569         }
 570     }
 571
 572     foreach (int obstacleId, m_obstacles) {
 573         itemSpace->m_groups[obstacleId].applyResults(itemSpace, m_id);
 574     }
 575 }
 576
 577 bool ItemSpace::ItemGroup::groupIsAbove(ItemSpace *itemSpace, QList<int> &visited, int groupId)
 578 {
 579     foreach (const Request &request, m_requests) {
 580         if (request.m_sourceGroup == -1 || visited.contains(request.m_sourceGroup)) {
 581             continue;
 582         }
 583         if (request.m_sourceGroup == groupId) {
 584             return true;
 585         }
 586         visited.append(request.m_sourceGroup);
 587         if (itemSpace->m_groups[request.m_sourceGroup].groupIsAbove(itemSpace, visited, groupId)) {
 588             return true;
 589         }
 590     }
 591     return false;
 592 }
 593
 594 // TODO: optimize
 595 void ItemSpace::addItem(ItemSpaceItem newItem)
 596 {
 597     QList<ItemSpaceItem> newGroupItems;
 598     QRectF newItemGeom = newItem.lastGeometry.adjusted(-shiftingSpacing, -shiftingSpacing,
 599                                                       shiftingSpacing, shiftingSpacing);
 600
 601     // look for items overlapping with the new item
 602     for (int groupId = 0; groupId < m_groups.size();) {
 603         ItemGroup &group = m_groups[groupId];
 604
 605         // if any item in the group overlaps it, save its items and remove the group
 606         bool removeGroup = false;
 607         for (int itemId = 0; itemId < group.m_groupItems.size(); itemId++) {
 608             ItemSpaceItem &item = group.m_groupItems[itemId];
 609             if (newItemGeom.intersects(item.lastGeometry)) {
 610                 removeGroup = true;
 611                 break;
 612             }
 613         }
 614
 615         if (removeGroup) {
 616             newGroupItems << group.m_groupItems;
 617             m_groups.removeAt(groupId);
 618         } else {
 619             groupId++;
 620         }
 621     }
 622
 623     // create the new group
 624     m_groups.append(ItemGroup());
 625     ItemGroup &newGroup = m_groups.last();
 626     newGroup.m_groupItems.append(newItem);
 627     newGroup.m_groupItems << newGroupItems;
 628 }
 629
 630 // TODO: optimize
 631 void ItemSpace::removeItem(int removeGroup, int removeItemInGroup)
 632 {
 633     // remove items from group
 634     m_groups[removeGroup].m_groupItems.removeAt(removeItemInGroup);
 635     // save other group items
 636     QList<ItemSpaceItem> otherGroupItems = m_groups[removeGroup].m_groupItems;
 637     // remove group
 638     m_groups.removeAt(removeGroup);
 639     // re-add other group items
 640     foreach (const ItemSpaceItem &item, otherGroupItems) {
 641         addItem(item);
 642     }
 643 }
 644
 645 // TODO: optimize
 646 void ItemSpace::updateItem(int group, int itemInGroup)
 647 {
 648     ItemSpaceItem copy = m_groups[group].m_groupItems[itemInGroup];
 649     removeItem(group, itemInGroup);
 650     addItem(copy);
 651 }
 652
 653 bool ItemSpace::locateItemByPosition(int pos, int *groupIndex, int *itemInGroup) const
 654 {
 655     int current = 0;
 656     for (int groupId = 0; groupId < m_groups.size(); groupId++) {
 657         ItemGroup group = m_groups[groupId];
 658         if (current + group.m_groupItems.size() > pos) {
 659             *groupIndex = groupId;
 660             *itemInGroup = pos - current;
 661             return true;
 662         }
 663         current += group.m_groupItems.size();
 664     }
 665     return false;
 666 }
 667
 668 bool ItemSpace::locateItemByUser(QVariant user, int *groupIndex, int *itemInGroup) const
 669 {
 670     for (int groupId = 0; groupId < m_groups.size(); groupId++) {
 671         ItemGroup group = m_groups[groupId];
 672         for (int itemId = 0; itemId < group.m_groupItems.size(); itemId++) {
 673             ItemSpaceItem &item = group.m_groupItems[itemId];
 674             if (item.user == user) {
 675                 *groupIndex = groupId;
 676                 *itemInGroup = itemId;
 677                 return true;
 678             }
 679         }
 680     }
 681     return false;
 682 }
 683
 684 void ItemSpace::preparePush(Direction direction, PushPower power)
 685 {
 686     m_direction = direction;
 687     m_power = power;
 688
 689     for (int i=0; i<m_groups.size(); i++) {
 690         m_groups[i].resetPush(i);
 691     }
 692 }