Fixed search algorithm for iconview widget. This resolves bug 420.

(cherry picked from commit d6867cf92e3f65b61a7289a478f97910b9fa4965)
Signed-off-by: Michele Calgaro <michele.calgaro@yahoo.it>

2 files changed, 237 insertions, 217 deletions

diff --git a/src/iconview/qiconview.cpp b/src/iconview/qiconview.cpp
index 101582b..df9a1be 100644
--- a/src/iconview/qiconview.cpp
+++ b/src/iconview/qiconview.cpp
@@ -287,74 +287,8 @@ public:
     struct SortableItem {
 	QIconViewItem *item;
     };
-
-public:
-
-    /* finds the containers that intersect with \a searchRect in the direction \a dir relative to \a relativeTo */
-    QPtrList<ItemContainer>* findContainers(
-	QIconView:: Direction dir,
-	const QPoint &relativeTo,
-	const QRect &searchRect ) const;
-    //    friend int cmpIconViewItems( const void *n1, const void *n2 );
 };
 
-
-QPtrList<QIconViewPrivate::ItemContainer>* QIconViewPrivate::findContainers(
-	QIconView:: Direction dir,
-	const QPoint &relativeTo,
-	const QRect &searchRect ) const
-{
-
-    QPtrList<QIconViewPrivate::ItemContainer>* list =
-	new QPtrList<QIconViewPrivate::ItemContainer>();
-
-    if ( arrangement == QIconView::LeftToRight ) {
-	if ( dir == QIconView::DirLeft || dir == QIconView::DirRight ) {
-	    ItemContainer *c = firstContainer;
-	    for ( ; c; c = c->n )
-		if ( c->rect.intersects( searchRect ) )
-		    list->append( c );
-	} else {
-	    if ( dir == QIconView::DirDown ) {
-		ItemContainer *c = firstContainer;
-		for ( ; c; c = c->n )
-		    if ( c->rect.intersects( searchRect ) &&
-			 c->rect.bottom() >= relativeTo.y() )
-			list->append( c );
-	    } else {
-		ItemContainer *c = lastContainer;
-		for ( ; c; c = c->p )
-		    if ( c->rect.intersects( searchRect ) &&
-			 c->rect.top() <= relativeTo.y() )
-			list->append( c );
-	    }
-	}
-    } else {
-	if ( dir == QIconView::DirUp || dir == QIconView::DirDown ) {
-	    ItemContainer *c = firstContainer;
-	    for ( ; c; c = c->n )
-		if ( c->rect.intersects( searchRect ) )
-		    list->append( c );
-	} else {
-	    if ( dir == QIconView::DirRight ) {
-		ItemContainer *c = firstContainer;
-		for ( ; c; c = c->n )
-		    if ( c->rect.intersects( searchRect ) &&
-			 c->rect.right() >= relativeTo.x() )
-			list->append( c );
-	    } else {
-		ItemContainer *c = lastContainer;
-		for ( ; c; c = c->p )
-		    if ( c->rect.intersects( searchRect ) &&
-			 c->rect.left() <= relativeTo.x() )
-			list->append( c );
-	    }
-	}
-    }
-    return list;
-}
-
-
 #if defined(Q_C_CALLBACKS)
 extern "C" {
 #endif
@@ -5106,6 +5040,7 @@ void QIconView::keyPressEvent( QKeyEvent *e )
 	}
     } break;
 #endif
+
     case Key_Home: {
 	d->currInputString = QString::null;
 	if ( !d->firstItem )
@@ -5150,6 +5085,7 @@ void QIconView::keyPressEvent( QKeyEvent *e )
 			      e->state() & ControlButton, TRUE );
 	}
     } break;
+    
     case Key_End: {
 	d->currInputString = QString::null;
 	if ( !d->lastItem )
@@ -5193,50 +5129,7 @@ void QIconView::keyPressEvent( QKeyEvent *e )
  			      e->state() & ControlButton, TRUE );
 	}
     } break;
-    case Key_Right: {
-	d->currInputString = QString::null;
-	QIconViewItem *item;
-	selectCurrent = FALSE;
-	Direction dir = DirRight;
-
-	QRect r( 0, d->currentItem->y(), contentsWidth(), d->currentItem->height() );
-	item = findItem( dir, d->currentItem->rect().center(), r );
-
-	// search the row below from the right
-	while ( !item && r.y() < contentsHeight() ) {
-	    r.moveBy(0, d->currentItem->height() );
-	    item = findItem( dir, QPoint( 0, r.center().y() ), r );
-	}
-
-	if ( item ) {
-	    QIconViewItem *old = d->currentItem;
-	    setCurrentItem( item );
-	    ensureItemVisible( item );
-	    handleItemChange( old, e->state() & ShiftButton, e->state() & ControlButton );
-	}
-    } break;
-    case Key_Left: {
-	d->currInputString = QString::null;
-	QIconViewItem *item;
-	selectCurrent = FALSE;
-	Direction dir = DirLeft;
-
-	QRect r( 0, d->currentItem->y(), contentsWidth(), d->currentItem->height() );
-	item = findItem( dir, d->currentItem->rect().center(), r );
-
-	// search the row above from the left
-	while ( !item && r.y() >= 0 ) {
-	    r.moveBy(0, - d->currentItem->height() );
-	    item = findItem( dir, QPoint( contentsWidth(), r.center().y() ), r );
-	}
-
-	if ( item ) {
-	    QIconViewItem *old = d->currentItem;
-	    setCurrentItem( item );
-	    ensureItemVisible( item );
-	    handleItemChange( old, e->state() & ShiftButton, e->state() & ControlButton );
-	}
-    } break;
+    
     case Key_Space: {
 	d->currInputString = QString::null;
 	if ( d->selectionMode == Single)
@@ -5244,51 +5137,65 @@ void QIconView::keyPressEvent( QKeyEvent *e )
 
 	d->currentItem->setSelected( !d->currentItem->isSelected(), TRUE );
     } break;
-    case Key_Enter: case Key_Return:
+    
+    case Key_Enter: 
+    case Key_Return:
 	d->currInputString = QString::null;
 	emit returnPressed( d->currentItem );
 	break;
+	
+    case Key_Right: {
+	d->currInputString = QString::null;
+	selectCurrent = FALSE;
+	Direction dir = DirRight;
+	QIconViewItem *item = findItem(dir, d->currentItem);
+	if (item) {
+	    QIconViewItem *old=d->currentItem;
+	    setCurrentItem(item);
+	    ensureItemVisible(item);
+	    handleItemChange(old, e->state() & ShiftButton, e->state() & ControlButton );
+        }
+    } break;
+    
+    case Key_Left: {
+	d->currInputString = QString::null;
+	selectCurrent = FALSE;
+	Direction dir = DirLeft;
+	QIconViewItem *item = findItem(dir, d->currentItem);
+	if (item) {
+	    QIconViewItem *old=d->currentItem;
+	    setCurrentItem(item);
+	    ensureItemVisible(item);
+	    handleItemChange(old, e->state() & ShiftButton, e->state() & ControlButton );
+        }
+    } break;
+    
     case Key_Down: {
 	d->currInputString = QString::null;
-	QIconViewItem *item;
 	selectCurrent = FALSE;
 	Direction dir = DirDown;
-
-	QRect r( d->currentItem->x(), 0, d->currentItem->width(), contentsHeight() );
-	item = findItem( dir, d->currentItem->rect().center(), r );
-
-	// finding the closest item below and to the right
-	while ( !item && r.x() < contentsWidth() ) {
-	    r.moveBy( r.width() , 0 );
-	    item = findItem( dir, QPoint( r.center().x(), 0 ), r );
-	}
-
-
-	QIconViewItem *i = d->currentItem;
-	setCurrentItem( item );
-	item = i;
-	handleItemChange( item, e->state() & ShiftButton, e->state() & ControlButton );
+	QIconViewItem *item = findItem(dir, d->currentItem);
+	if (item) {
+	    QIconViewItem *old=d->currentItem;
+	    setCurrentItem(item);
+	    ensureItemVisible(item);
+	    handleItemChange(old, e->state() & ShiftButton, e->state() & ControlButton );
+        }
     } break;
+    
     case Key_Up: {
 	d->currInputString = QString::null;
-	QIconViewItem *item;
 	selectCurrent = FALSE;
 	Direction dir = DirUp;
-
-	QRect r( d->currentItem->x(), 0, d->currentItem->width(), contentsHeight() );
-	item = findItem( dir, d->currentItem->rect().center(), r );
-
-	// finding the closest item above and to the left
-	while ( !item && r.x() >= 0 ) {
-	    r.moveBy(- r.width(), 0 );
-	    item = findItem( dir, QPoint(r.center().x(), contentsHeight() ), r );
-	}
-
-	QIconViewItem *i = d->currentItem;
-	setCurrentItem( item );
-	item = i;
-	handleItemChange( item, e->state() & ShiftButton, e->state() & ControlButton );
+	QIconViewItem *item = findItem(dir, d->currentItem);
+	if (item) {
+	    QIconViewItem *old=d->currentItem;
+	    setCurrentItem(item);
+	    ensureItemVisible(item);
+	    handleItemChange(old, e->state() & ShiftButton, e->state() & ControlButton );
+        }
     } break;
+    
     case Key_Next: {
 	d->currInputString = QString::null;
 	selectCurrent = FALSE;
@@ -5311,6 +5218,7 @@ void QIconView::keyPressEvent( QKeyEvent *e )
 	    handleItemChange( item, e->state() & ShiftButton, e->state() & ControlButton );
 	}
     } break;
+    
     case Key_Prior: {
 	d->currInputString = QString::null;
 	selectCurrent = FALSE;
@@ -5333,6 +5241,7 @@ void QIconView::keyPressEvent( QKeyEvent *e )
 	    handleItemChange( item, e->state() & ShiftButton, e->state() & ControlButton );
 	}
     } break;
+    
     default:
 	if ( !e->text().isEmpty() && e->text()[ 0 ].isPrint() ) {
 	    selectCurrent = FALSE;
@@ -5403,79 +5312,195 @@ void QIconView::keyPressEvent( QKeyEvent *e )
 }
 
 /*
-  Finds the closest item in the Direction \a dir relative from the point \a relativeTo
-  which intersects with the searchRect.
-
-  The function choses the closest item with its center in the searchRect.
+  Finds the closest item in the direction \a dir starting from the specified \a fromItem.
+  If the arrangement is LeftToRight (icon view mode): use center as item reference
+  If the arrangement is TopToBottom (multicolumn view mode): use left top corner as item reference
 */
-QIconViewItem* QIconView::findItem( Direction dir,
-				    const QPoint &relativeTo,
-				    const QRect &searchRect ) const
+QIconViewItem* QIconView::findItem(Direction dir, const QIconViewItem *fromItem) const
 {
-    QIconViewItem *item;
-    QIconViewItem *centerMatch = 0;
-    int centerMatchML = 0;
-
-    // gets list of containers with potential items
-    QPtrList<QIconViewPrivate::ItemContainer>* cList =
-	d->findContainers( dir, relativeTo, searchRect);
-
-    cList->first();
-    while ( cList->current() && !centerMatch ) {
-	QPtrList<QIconViewItem> &list = (cList->current())->items;
-	for ( item = list.first(); item; item = list.next() ) {
-	    if ( neighbourItem( dir, relativeTo, item ) &&
-		 searchRect.contains( item->rect().center() ) &&
-		 item != currentItem() ) {
- 		int ml = (relativeTo - item->rect().center()).manhattanLength();
-		if ( centerMatch ) {
-		    if ( ml < centerMatchML ) {
-			centerMatch = item;
-			centerMatchML = ml;
-		    }
-		} else {
-		    centerMatch = item;
-		    centerMatchML = ml;
-		}
-	    }
-	}
-	cList->next();
+    QIconViewItem *closestItem=NULL;
+    int distPri=0, distSec=0;
+    int itemDistancePri=0, itemDistanceSec=0;
+    
+    QPoint pos;
+    if (d->arrangement == LeftToRight) {
+      pos=fromItem->rect().center();
     }
-    delete cList;
-    return centerMatch;
-}
-
-
-/*
-  Returns TRUE if the items orientation compared to
-  the point \a relativeTo is correct.
-*/
-bool QIconView::neighbourItem( Direction dir,
-			       const QPoint &relativeTo,
-			       const QIconViewItem *item ) const
-{
-    switch ( dir ) {
-    case DirUp:
-	if ( item->rect().center().y() < relativeTo.y() )
-	    return TRUE;
-	break;
-    case DirDown:
-	if ( item->rect().center().y() > relativeTo.y() )
-	    return TRUE;
-	break;
-    case DirLeft:
-	if ( item->rect().center().x() < relativeTo.x() )
-	    return TRUE;
-	break;
-    case DirRight:
-	if ( item->rect().center().x() > relativeTo.x() )
-	    return TRUE;
-	break;
-    default:
-	// nothing
-	break;
+    else {
+      pos=fromItem->rect().topLeft();
     }
-    return FALSE;
+    
+    QRect searchRect;
+    switch (dir) {
+        case DirDown:
+            searchRect.setCoords(pos.x(), 0, contentsWidth(), contentsHeight());
+            break;
+    
+        case DirUp:
+            searchRect.setCoords(0, 0, pos.x(), contentsHeight());
+            break;
+    
+        case DirRight:
+            searchRect.setCoords(0, pos.y(), contentsWidth(), contentsHeight());
+            break;
+    
+        case DirLeft:
+            searchRect.setCoords(0, 0, contentsWidth(), pos.y());
+            break;
+    }
+    
+    for (QIconViewPrivate::ItemContainer *c=d->firstContainer; c; c=c->n) {
+        if (c->rect.intersects(searchRect)) {
+            QPtrList<QIconViewItem> &list = c->items;
+            for (QIconViewItem *item=list.first(); item; item=list.next()) {
+                if (item != fromItem) {
+                    bool itemOK = true;
+                    const QRect &ir = item->rect();
+                    // DirDown/DirUp   : primary distance X, secondary distance Y
+                    // DirLeft/DirRight: primary distance Y, secondary distance X
+                    if (d->arrangement == LeftToRight) {
+                        // Left to right arrangement (icon view mode): use center as item reference
+                        switch (dir) {
+                            case DirDown:
+                                if (ir.center().x() > pos.x()) {
+                                    distPri = ir.center().x()-pos.x();
+                                    distSec = ir.center().y();
+                                    }
+                                else if (ir.center().x() == pos.x() && ir.center().y() > pos.y()) {
+                                    distPri = 0;
+                                    distSec = ir.center().y()-pos.y();
+                                    }
+                                else {
+                                    itemOK = false;
+                                    }
+                                break;
+                            
+                            case DirUp:
+                                if (ir.center().x() < pos.x()) {
+                                    distPri = pos.x()-ir.center().x();
+                                    distSec = contentsHeight()-ir.center().y();
+                                    }
+                                else if (ir.center().x() == pos.x() && ir.center().y() < pos.y()) {
+                                    distPri = 0;
+                                    distSec = pos.y()-ir.center().y();
+                                    }
+                                else {
+                                    itemOK = false;
+                                    }
+                                break;
+                            
+                            case DirRight:
+                                if (ir.center().y() > pos.y()) {
+                                    distPri = ir.center().y()-pos.y();
+                                    distSec = ir.center().x();
+                                    }
+                                else if (ir.center().y() == pos.y() && ir.center().x() > pos.x()) {
+                                    distPri = 0;
+                                    distSec = ir.center().x()-pos.x();
+                                    }
+                                else {
+                                    itemOK = false;
+                                    }
+                                break;
+                            
+                            case DirLeft:
+                                if (ir.center().y() < pos.y()) {
+                                    distPri = pos.y()-ir.center().y();
+                                    distSec = contentsWidth()-ir.center().x();
+                                    }
+                                else if (ir.center().y() == pos.y() && ir.center().x() < pos.x()) {
+                                    distPri = 0;
+                                    distSec = pos.x()-ir.center().x();
+                                    }
+                                else {
+                                    itemOK = false;
+                                    }
+                                break;
+                                
+                            default:
+                                itemOK = false;
+                                break;
+                        }	
+                    }
+                    else {            
+                        // Top to bottom arrangement (multicolumn view mode): use left top corner as item reference
+                        switch (dir) {
+                            case DirDown:
+                                if (ir.left() > pos.x()) {
+                                    distPri = ir.left()-pos.x();
+                                    distSec = ir.top();
+                                    }
+                                else if (ir.left() == pos.x() && ir.top() > pos.y()) {
+                                    distPri = 0;
+                                    distSec = ir.top()-pos.y();
+                                    }
+                                else {
+                                    itemOK = false;
+                                    }
+                                break;
+                            
+                            case DirUp:
+                                if (ir.left() < pos.x()) {
+                                    distPri = pos.x()-ir.left();
+                                    distSec = contentsHeight()-ir.top();
+                                    }
+                                else if (ir.left() == pos.x() && ir.top() < pos.y()) {
+                                    distPri = 0;
+                                    distSec = pos.y()-ir.top();
+                                    }
+                                else {
+                                    itemOK = false;
+                                    }
+                                break;
+                            
+                            case DirRight:
+                                if (ir.top() > pos.y()) {
+                                    distPri = ir.top()-pos.y();
+                                    distSec = ir.left();
+                                    }
+                                else if (ir.top() == pos.y() && ir.left() > pos.x()) {
+                                    distPri = 0;
+                                    distSec = ir.left()-pos.x();
+                                    }
+                                else {
+                                    itemOK = false;
+                                    }
+                                break;
+                            
+                            case DirLeft:
+                                if (ir.top() < pos.y()) {
+                                    distPri = pos.y()-ir.top();
+                                    distSec = contentsWidth()-ir.left();
+                                    }
+                                else if (ir.top() == pos.y() && ir.left() < pos.x()) {
+                                    distPri = 0;
+                                    distSec = pos.x()-ir.left();
+                                    }
+                                else {
+                                    itemOK = false;
+                                    }
+                                break;
+                                
+                            default:
+                                itemOK = false;
+                                break;
+                        }	
+                    }
+                        
+                    if (itemOK) {
+                        if (!closestItem ||
+                            ((distPri < itemDistancePri) ||
+                            (distPri == itemDistancePri && distSec < itemDistanceSec))) {
+                            closestItem = item;
+                            itemDistancePri = distPri;
+                            itemDistanceSec = distSec;
+                        } 
+                    }
+                }
+            }
+        }
+    }
+    return closestItem;
 }
 
 /*!
diff --git a/src/iconview/qiconview.h b/src/iconview/qiconview.h
index 4504690..e6c4548 100644
--- a/src/iconview/qiconview.h
+++ b/src/iconview/qiconview.h
@@ -497,12 +497,7 @@ private:
 	DirLeft,
 	DirRight
     };
-    QIconViewItem* findItem( Direction dir,
-			     const QPoint &relativeTo,
-			     const QRect &searchRect ) const;
-    bool neighbourItem( Direction dir,
-			const QPoint &relativeTo,
-			const QIconViewItem *item ) const;
+    QIconViewItem* findItem(Direction dir, const QIconViewItem *fromItem) const;
     QBitmap mask( QPixmap *pix ) const;
     int visibleWidthSB() const;
     int visibleHeightSB() const;